Direct Fitting of Gaussian
Mixture Models
Leonid Keselman, Martial Hebert
Robotics Institute
Carnegie Mellon University
May 29, 2019https://github.com/leonidk/direct_gmm
1Representations of 3D data

Point Cloud

Point Cloud+ Normals

Nearest Neighbor Plane Fit

Triangular
Mesh

Screened Poisson Surface Reconstruction2

Gaussian Mixture Models for 3D Shapes
GMM fit to object surface
Benefits• Closed-form expression• Can represent contiguous surfaces• Easy to build from noisy data
• Sparse3Gaussian Mixture Model (GMM)(! " = $ )* +("; .* , Σ* )%&'$ )* = 1*)* ≥ 0

Σ* is symmetric,
positive-semidefinite
4

Gaussian Mixtures as a shape representation
Efficient Representation

Mesh Registration

B. Eckart, K. Kim, J. Kautz.
ECCV (2018)
B. Eckart, K. Kim, A. Troccoli, A. Kelly, J. Kautz.
CVPR (2016)

Frame Registration

W. Tabib, C. O’Meadhra, N. MichaelIEEE R-AL (2018)5

Fitting a Gaussian Mixture Model
1.
2.
3.

Obtain 3D Point Cloud
Select Initial Parameters
Iterate Expectation & Maximizationi.
E-Step: Each point gets a likelihood
ii. M-Step: Each mixture gets parameters

67

The E-Step (Given GMM parameters)
1!"# = '" ((*# ; ," , Σ" )&#Affiliation between point j & mixture i&# = 0 '1 ((*# ; ,1 , Σ1 )1Normalization constant for point j

8

The M-Step (Given point-mixture weights)
points mixtures(*!" = $ $ +)% log /) 0(2% ; 4) , Σ) )lower-bound loss%&' )&'To get new parameters: takes derivatives, set equal to zero, and solve

8!"
=08/)

8!"=084);)/) ==14) =$ <)% 2%;)%8!"=08Σ)<)% = +)%;) = $ <)%1Σ) =$ <)% (2% −4) )(2% −4) )?
;)
%%9

10

Geometric Objects in a Probability Distribution

Known curve in a given 2D probability distribution

11

Geometric Objects in a Probability Distribution,ℓ curve ≅ ( -(/) ))*+

Consider sampling N points from this curve

12Geometric Objects in a Probability Distribution,+,ℓ curve ≅ ( -(/) ))*+Take a geometric mean to account for sample number

13

Geometric Objects in a Probability Distribution,+,ℓ curve ≅ ( -(/) ))*+,ℓ curve = lim+,( -(/) ),→6)*+,+,= lim exp log ( -(/) ),→6)*+,1= lim exp
= log(-(/) )),→6<)*+

The curve will be the value in the limit

14

Geometric Objects in a Probability Distribution,+,ℓ curve ≅ ( -(/) ))*+,

ℓ curve = lim+,( -(/) ),→6)*+,+,= lim exp log ( -(/) ),→6)*+,1= lim exp
= log(-(/) )),→6<)*+= exp > log(-(/)) ?/15

Geometric Objects in a Probability Distribution! = exp & log(+(,)) .,1.
2.

If +(,) = 0 on curve, then L= 0
Invariant to reparameterization

16

!" Area of each triangle#" Centroid of each triangle$" , &" , '" Triangle vertices

17

The E-Step (Given GMM parameters)
1!"# = '" ((*# ; ," , Σ" )&#Affiliation between point j & mixture i&# = 0 '1 ((*# ; ,1 , Σ1 )1Normalization constant for point j
2# Area of each triangle,# Centroid of each triangle
3# , 4# , &# Triangle vertices

18

The New E-Step (Given GMM parameters)
1!"# = '" (# )(+# ; +" , Σ" )&#Taylor Approximation(2 terms)

Affiliation between object j & mixture i&# = 0 '1 (1 )(+# ; +1 , Σ1 )1Normalization constant for object j(# Area of each triangle+# Centroid of each triangle
2# , 3# , &# Triangle vertices

19

The M-Step (Given point-mixture weights)
%"
*" =+

("' = 1"'

1!" =& ("' )'%"'%" = & ("''1Σ" =& ("' ()' −!" )()' −!" )0%"'20The New M-Step (Given point-mixture weights)%"*" =+("' = 2' 3"'

1!" =& ("' )'%"'%" = & ("''1& ("' ()' −!" )()' −!" )0 + Σ'
Σ" =%"'2' Area of each triangle!' Centroid of each triangle
4' , 6' , 7' Triangle vertices

1
Σ' =4' 4'0 + 6' 6'0 + 7' 7'0 − 3 !' !'0
1221

What is Σ" ?

22

23

Results
Did all that math actually help us fit better/faster GMMs?

24

Using different inputs
classic algorithm• Vertices of the mesh• Triangle centroids
our method• Approximate (E only)• Exact (E + M steps)

Evaluate across a wide
range of mixtures(6 to 300)

Measure the likelihoodof a high-density pointcloud (higher is better)

25

Full E+M method works in all cases

26

Stable under even random initialization!

27

Applications
Are these models actually more useful?

28Mesh Registration (P2D)
Method
1. Apply a random rotation + translation to the point cloud
2. Find transformation to maximize the likelihood of the points• Perform P2D with GMMs fit toi.
ii.

mesh vertices
mesh triangles

Eckart, Kim, Kautz.
“HGMR: Hierarchical Gaussian Mixtures for Adaptive 3D Registration.”
ECCV (2018)29

Mesh-based GMMs are more accurate

30

Across multiple models
Rotation Error(% of ICP)

Translation Error(% of ICP)

150

200

100

100500Armadillo

BunnyDragon

points

mesh

Happy

Lucy0

Armadillo

BunnyDragon

points

Happy

Lucy

mesh31

Frame Registration (D2D)
Method
1. Use a sequence from an RGBD Sensor• 2,500 frame TUM sequence from a Microsoft Kinect

2. Pairwise registration between t & t-1 frames• Optimize the D2D L2 distance• Build GMMs using square pixels as the geometric object

W. Tabib, C. O’Meadhra, N. Michael.
“On-Manifold GMM Registration”
IEEE R-AL (2018)32

Representing points using pixel squares

33

D2D Registration Results

Compared to standard GMM• 2.4% improvement in RMSE
• 22% faster D2D convergence34

Questions?
! = exp & log(+(,)) .,35

The End!

36

Extra Slides

37

How to fit a Gaussian Mixture Model?
1. Obtain any collection of objects
2. Perform Expectation + Maximizationi.
ii.

E-Step: Each point gets a likelihood
M-Step: Each mixture gets new parameters

38Extension to arbitrary primitives

Vasconcelos, Lippman. "Learning mixture hierarchies.”
Advances in Neural Information Processing Systems (1999)

39

Approximation

area-weighted geometric mean using the primitive’s centroids40

Product Integral Formulation• Product integrals provide a resampling-invariant loss function• Given S samples, of M primitives, with N mixture components• This can be evaluated in the limit of samples (with a geometric mean)

41

42

43

44

For GMMs we will use the lower bound45

P2D Registration Results
ModelRotation Error(% of ICP)

Translation Error(% of ICP)

pointsmeshpoints

meshArmadillo

127

37

161

33

Bunny

50

2841

17

Dragon

68

25

40

19

Happy

101

27

85

27

Lucy

95

23

122

35

46

Mesh Registration with P2DMethod
1. Apply a random rotation + translation to the point cloud
2. Point-to-Distribution (P2D) registration of point cloud to GMM• Perform tests with GMMs fit toi.
ii.

mesh vertices
mesh triangles• Optimize the GMM likelihood with rigid body transformation (q & t)
• BFGS Optimization using numerical gradients, starting from identity

Eckart, Kim, Kautz.
“HGMR: Hierarchical Gaussian Mixtures for Adaptive 3D Registration.”
ECCV (2018)47

Acknowledgements• Martial Hebert• Robotics Institute• Reviewers• Funding?

48

Representing points using pixel squares

49