Source-linked AI summary
GOGMA: Globally-Optimal Gaussian Mixture Alignment
Dylan Campbell, Lars Petersson
TL;DR
Gaussian mixture alignment is more robust than correspondence-based registration, but local optimization leaves it dependent on initialization. GOGMA uses branch-and-bound and SE(3)-based objective bounds to guarantee global optimality for 3D rigid alignment under the L2 distance. It found the global optimum in all 144 self-alignment registrations and performed very well on challenging field datasets.
Problem
Gaussian mixture alignment avoids explicit point correspondences and can be robust to partial overlap, but its local optimization remains initialization-dependent and cannot guarantee global optimality.
Source: §1 · p. 1Method
GOGMA uses branch-and-bound over SE(3), with bounds derived from the geometry of rigid motions and local GMA optimization to accelerate convergence without voiding the global-optimality guarantee.
Source: §1 · p. 1Results
All 144 self-alignment registrations reached the global optimum, and GOGMA performed very well on challenging field datasets.
Source: §6.1 · p. 6, §7 · p. 8Takeaways & Limitations
The L2 density distance is less susceptible to partial overlap than ICP’s closest-point error, though the global optimum need not be the ground-truth transformation.
Source: §6 · p. 6For partially overlapping point sets, an alignment with a smaller objective value than the ground-truth alignment may exist.
Source: §6 · p. 6
Abstract
from arXiv · showhide
Gaussian mixture alignment is a family of approaches that are frequently used for robustly solving the point-set registration problem. However, since they use local optimisation, they are susceptible to local minima and can only guarantee local optimality. Consequently, their accuracy is strongly dependent on the quality of the initialisation. This paper presents the first globally-optimal solution to the 3D rigid Gaussian mixture alignment problem under the L2 distance between mixtures. The algorithm, named GOGMA, employs a branch-and-bound approach to search the space of 3D rigid motions SE(3), guaranteeing global optimality regardless of the initialisation. The geometry of SE(3) was used to find novel upper and lower bounds for the objective function and local optimisation was integrated into the scheme to accelerate convergence without voiding the optimality guarantee. The evaluation empirically supported the optimality proof and showed that the method performed much more robustly on two challenging datasets than an existing globally-optimal registration solution.
1. Introduction
Point-set registration methods such as ICP can fail without good initialization, while Gaussian mixture alignment improves robustness but still lacks a global-optimality guarantee. GOGMA addresses that gap with branch-and-bound over SE(3), using objective bounds derived from its geometry.
1. Introduction
- Gaussian mixture alignment also applies to scan merging, object recognition, sensor localization, and estimating relative sensor poses.It addresses the same alignment problem for point sets as point-set registration.Source: §1 · p. 1
- ICP is vulnerable to local minima without good initialization and can fail when closest-point correspondences are unreliable because of misalignment, occlusion, or partial overlap.Different viewpoints and dynamic objects commonly produce occlusion and partial overlap.Source: §1 · p. 1
- Gaussian mixture alignment avoids explicit point correspondences and can widen the convergence basin, but it still requires good initialization and cannot guarantee global optimality.The L2 distance between mixtures provides a robust objective.Source: §1 · p. 1
- Go-ICP globally minimizes ICP’s closest-point L2 error, but its cost remains sensitive to occlusion and partial overlap; trimming adds runtime and requires a parameter.Go-ICP uses branch-and-bound to address local minima.Source: §1 · p. 1
- GOGMA is the first globally optimal solution to 3D rigid Gaussian mixture alignment under the L2 distance, using SE(3)-based bounds and local optimization to accelerate convergence without voiding the guarantee.Its branch-and-bound search guarantees global optimality regardless of initialization.Source: §1 · p. 1
2. Related Work
Related approaches seek robustness through Gaussian mixtures, heuristic global search, or globally optimal registration. Their respective limitations include dependence on initialization, lack of convergence guarantees, and restrictive assumptions or sensitivity to partial overlap.
2. Related Work
- Gaussian-mixture methods improve robustness to poor initialization, noise, and outliers, but rely on local optimization and therefore depend on the initial pose.Examples include Robust Point Matching, Coherent Point Drift, Kernel Correlation, GMMReg, NDT, and SVR.Source: §2 · p. 2
- Heuristic global-alignment methods include stochastic optimization and feature-based correspondence search, but are not guaranteed to converge.Examples include particle filtering, genetic algorithms, simulated annealing, and feature-based methods using random sampling, greedy algorithms, Hough transforms, or branch-and-bound.Source: §2 · p. 2
- Existing globally optimal 3D registration methods can be slow or require restrictive assumptions about point sets, correspondences, or transformations.Examples include known correspondences, equal-sized point sets with pure rotation, or known translation.Source: §2 · p. 2
- Go-ICP globally optimizes closest-point L2 error and uses local ICP as a subroutine, but remains sensitive to occlusion and partial overlap.Its trimming strategy increases runtime, requires an overlap estimate, and may make the solution ambiguous.Source: §2 · p. 2
3. Gaussian Mixture Alignment
The section formulates Gaussian mixture alignment as minimizing a discrepancy between point-set GMMs, using the L2 density distance. The objective has a closed form, and local optimization minimizes it over rigid transformations.
3. Gaussian Mixture Alignment
- Point sets can be converted to GMMs using kernel density estimation, expectation maximisation, or a support vector machine, then aligned by minimizing a discrepancy between mixtures.The paper uses the L2 distance formulation, which is closed-form, efficiently implemented, and inherently robust to outliers.Source: §3 · p. 2
- The rigid transformation applies rotation R in SO(3) and translation t in R^3 to one mixture before measuring its L2 distance from the other.The mixtures are constructed from point sets and have component means and variances.Source: §3 · p. 2
- The integral of the cross-mixture density term has a closed form, yielding the GMA objective function.The local GMA implementation minimizes that objective with L-BFGS-B.Source: §3 · p. 3
4. Branch-and-Bound
GOGMA applies branch-and-bound over a parameterized SE(3) domain, using geometric bounds to discard suboptimal branches. The section develops the domain representation and pairwise residual bounds that support this search.
4.1. Parametrising and Branching the Domain
- SE(3) is searched as a six-dimensional hypercube, with angle-axis rotation coordinates and a bounded translation cube partitioned by a hyperoctree.The rotation domain is a cube circumscribing the radius-π ball; choosing τ = 1 covers every feasible translation, while a smaller τ accepts a minimum detectable bounding-box overlap.Source: §4.1 · p. 3, Figure 1 · p. 3
4.2. Bounding the Branches
- Pairwise residual bounds use a translation sphere and rotation geometry, then combine across Gaussian pairs to bound the objective over each branch.The objective bounds require isotropic covariances; translation uncertainty is bounded by a sphere circumscribing the translation cube.Source: §4.2 · pp. 3–5
- Tight spherical-cap lower bounds converge to the upper bound as sub-cubes shrink, improving on the sphere-distance bound and the bound in.The minimum distance is radial when the target lies within the rotation cone, and otherwise is the distance to the cap edge.Source: §4.2 · pp. 4–5, Figure 3 · p. 5
5. The GOGMA Algorithm
GOGMA combines branch-and-bound with local GMA optimization to search for better minima while refining the best-so-far solution. It stops at ε-optimality, though runtime-limited runs may return a best guess without that guarantee.
5. The GOGMA Algorithm
- GOGMA terminates at ε-optimality when the gap between the best function value and the global lower bound is less than ε.Bounds for 4096 sub-cubes are computed simultaneously on the GPU; the remaining code runs on the CPU.Source: §5 · p. 6
- Branch-and-bound explores sub-cubes while local GMA refines the best-so-far value, helping discard branches whose lower bounds exceed it.GMA runs at initialization and when a sub-cube’s upper bound improves the current best; branch-and-bound directs the search toward lower local minima.Source: §5 · p. 6
- Runtime-limited runs can return the best-so-far transformation, but do not guarantee ε-optimality; batch-initialized GOGMA runs GMA on every sub-cube in the first subdivision.The batch variant updates the best function value from that batch.Source: §5 · p. 6
6. Experimental Results
Experiments tested GOGMA on objective-optimality checks, fully overlapping scans, and partially overlapping field data. The reported results include global-optimum recovery and successful coarse alignment across the field-dataset cases.
6.1. Optimality
- 144 registrations reached the global optimum; mean separations were 9×10−8 for DRAGON and 3×10−7 for BUNNY, with mean runtimes of 17s and 14s, respectively.The registrations aligned reconstructed models with transformed copies using 72 ISOI rotations.Source: §6.1 · p. 6
- Batch initialization generally captured the global minimum early; the remaining time raised the lower bound until ϵ-optimality, and batch initialization usually reduced runtime.The bound evolution for DRAGON and BUNNY is plotted against time in Figure 4.Source: §6.1 · p. 7, Figure 4 · p. 7
6.2. Fully-Overlapping Registration
- GOGMA found the correct alignment in all 1080 DRAGON single-view scan cases using the standard parameter settings.The cases aligned one reconstructed model with 15 partial scans initialized by 72 base ISOI rotations.Source: §6.2 · p. 7
- m,n=50: KDE results were poor; EM had suitable alignment accuracy but took 4 663s per model and ~256s per scan, so SVGMs are recommended for speed and accuracy.The KDE and EM comparisons fixed the number of components at 50.Source: §6.2 · p. 7
- For ϵ near zero, runtime rises steeply; larger ϵ speeds termination but loosens optimality guarantees, and ϵ=0.1 achieved 100% success.Runtime also increased with component counts and depended on lower-bound quality; the GOGMA lower bound was tighter than Go-ICP’s.Source: §6.2 · p. 7
6.3. Partially-Overlapping Registration
- GOGMA found the correct transformation in all cases under the coarse criterion, and refinement found it in virtually all cases under the fine criterion.The field experiments used coarse, medium, and fine inlier criteria on STAIRS and WOOD-SUMMER.Source: §6.3 · p. 8, Table 3 · p. 8, Table 4 · p. 8
- At ϵ=5×10−5, Go-ICP failed to coarsely align 19% of STAIRS and 16% of WOOD-SUMMER cases; ICP and CPD usually converged to local minima without good pose priors.Tighter Go-ICP settings, larger point counts, or trimming made runtime prohibitively slow.Source: §6.3 · p. 8
- GOGMA correctly localized all four perturbed APARTMENT room scans within the map.The scans were perturbed by 72 ISOI rotations to simulate a kidnapped robot.Source: §6.3 · p. 8, Table 5 · p. 8, Figure 7 · p. 8
7. Conclusion
GOGMA provides globally optimal 3D Gaussian mixture alignment under the L2 distance, with local optimisation to accelerate convergence. It performed well on challenging field datasets, while GPU optimisation, dynamic branching, and full-covariance bounds remain avenues for further work.
7. Conclusion
- GOGMA guarantees global optimality for 3D Gaussian mixture alignment under the L2 distance regardless of initialisation.It uses branch-and-bound and local optimisation to accelerate convergence, with objective bounds derived from the geometry of SE(3).Source: §7 · p. 8
- The algorithm performed very well on challenging field datasets, with an objective function robust to outliers induced by partial overlap and occlusion.Source: §7 · p. 8
- GPU implementation of local optimisation and dynamic branching could improve runtime benefits and parallelism, respectively.Dynamic branching could allow more parallelism for the same memory requirements.Source: §7 · p. 8
- Extending the lower bound to full covariances would enable applying the algorithm to more general Gaussian mixtures.Source: §7 · p. 8