Globally Optimal Point Cloud Registration Without Initialization

41 concepts36 papers1 proposal

Aligning two spatial datasets—whether they are 3D point clouds from a LiDAR sweep, 2D images, or medical scans—is a foundational problem in computer vision. Traditionally, this is treated as a chicken-and-egg problem: if you know which points correspond to each other, calculating the optimal spatial transformation is trivial; conversely, if you know the exact transformation, finding point correspondences is simple.

For decades, the standard solution has been the Iterative Closest Point (ICP) algorithm. ICP starts with an initial guess, finds the closest points as temporary correspondences, updates the transformation, and repeats. While fast, ICP is a local optimizer. It relies entirely on a high-quality initialization. If the initial guess is poor—such as when a robot is completely lost or an object is heavily rotated—the algorithm gets trapped in local minima, snapping the shapes together incorrectly.

To overcome this limitation, a powerful research direction has emerged: initialization-independent, globally optimal registration. Instead of refining a single guess, these methods systematically search the space of possible transformations to guarantee the discovery of the mathematically best alignment, regardless of how the shapes are initially positioned.


How can an algorithm search the infinite, continuous space of 3D rigid transformations ($SE(3)$) without checking every single possibility? The primary mechanism is Branch-and-Bound (BnB) optimization.

Imagine enclosing the entire search space of rotations and translations inside a high-dimensional box. A BnB algorithm operates by systematically splitting this box into smaller sub-boxes (branching) and evaluating each one. For any given sub-box representing a region of candidate transformations, the algorithm computes two values:

  1. An upper bound: The error of the best valid alignment found so far.
  2. A lower bound: A mathematically guaranteed, optimistic estimate of the lowest possible error any transformation inside this sub-box could achieve.
[ Full Search Space ]
       /        \
  [Box A]      [Box B]  <-- Lower bound is worse than current best upper bound?
    /   \         |
[A1]     [A2]  (PRUNED) <-- Discard entire region without searching inside

If a sub-box's lower bound is worse than the global upper bound, it means even the most optimistic transformation in that region cannot beat our current best solution. The algorithm safely discards (prunes) that entire volume of space.

Yang et al. pioneered this approach with Go-ICP, combining the global search guarantees of BnB with the local efficiency of traditional ICP. By bounding the $L_2$ error metric over the 3D rotation and translation spaces, the authors demonstrated a deterministic method that consistently reaches the true global minimum from arbitrary starting orientations. Similarly, Campbell et al. introduced GOGMA, which applies BnB to align Gaussian Mixture Models (GMMs), removing the dependency on discrete point-to-point correspondences while maintaining global optimality.


Taming the Dimensionality: Decoupling Parameters

Searching the full 6-DoF space of rigid transformations ($SE(3)$) via BnB is computationally expensive because the number of sub-boxes scales exponentially with dimensionality. To make global registration tractable, researchers focus on decoupling the transformation parameters.

Separating Rotation and Translation

The most common strategy is to solve for rotation and translation independently. For instance, Li et al. decoupled rotation and correspondence search by transforming the error metric to ensure Lipschitz continuity, allowing a BnB search to run solely over the 3-DoF rotation space.

Conversely, Liu et al. introduced GoTS (Global Translation Search), which uses Rotation Invariant Features (RIF). Because these features do not change when the point cloud rotates, the algorithm can perform a BnB search purely within the 3D translation space first, drastically reducing the search volume before computing the final rotation. In multiway mosaicking, Iro Armeni leveraged a BnB translation re-estimation technique to find the maximal overlap of 3D spheres representing alignment candidates, providing a robust consensus mechanism against noisy pairwise matches.

Frequency Domain and Dimensionality Reduction

Another way to bypass explicit spatial search is to move into the frequency domain. Liao et al. developed DPCN++, which uses the Fourier transform to decouple rotation, scale, and translation. By performing an exhaustive search in the frequency domain, the framework achieves global convergence without requiring explicit point correspondences or a close initial pose.

Alternatively, the problem can be projected into lower-dimensional geometric spaces. Le et al. mapped 3D surface alignment into a 2D domain using conformal geometry, transforming the spatial search into an optimal Möbius transformation search. For 2D point sets, Ask et al. proved that under robust loss functions, the search space can be reduced to a 1D search over rotation angles, achieving guaranteed polynomial time complexity.


Constructing Tight Bounds via Mathematical Relaxations

The practical speed of a Branch-and-Bound algorithm depends entirely on the tightness of its lower bounds. If a lower bound is too loose (too optimistic), the algorithm cannot prune regions effectively, causing it to devolve into an expensive exhaustive search. Researchers use advanced mathematical relaxations to construct tight, computationally efficient lower bounds.

Linear Matrix Inequalities and Sum-of-Squares

Paudel et al. demonstrated that 2D-3D registration can be formulated using Linear Matrix Inequalities (LMIs). This formulation allows a branch-and-prune framework to systematically partition the scene volume and discard non-optimal regions without relying on noisy intermediate steps like point triangulation. The authors extended this concept in another work by integrating Sum-of-Squares (SoS) optimization with BnB, enabling the algorithm to identify and reject outliers with mathematical certainty.

This geometric bounding strategy is also highly effective when matching semantic regions rather than raw points. Van Gool et al. framed semantic alignment as a "polytope-to-ellipsoid" containment constraint, using LMIs to guide a branch-and-prune search that eliminates the need for traditional point-to-point correspondences. To maximize the number of matching semantic regions, Speciale et al. formulated the search as a Mixed-Integer Semi-Definite Program, utilizing BnB to guarantee a global consensus even when up to 75% of the data consists of outliers.

Polynomial and Quadratic Bounding

When dealing with partial overlaps, the optimization landscape becomes highly non-convex. Lian et al. addressed this by modeling point set registration as a cubic polynomial problem. They utilized trilinear and bilinear programming to relax the polynomial constraints, creating tight lower bounds that allow successful global optimization even when the relative orientation of partially overlapping sets is completely unknown. For affine transformations, Li et al. derived a novel convex quadratic lower bound by modeling point clouds as Gaussian Mixture Models, ensuring deterministic convergence across the entire range of possible affine distortions.

Energy
  ^
  |       /\          _---_  <-- Actual Non-Convex Energy
  |      /  \        /     \
  |____ /____\______/_______\____
  |   /        \   /         \
  |  /__________\_/___________\  <-- Convex Lower Bound (Relaxed)
  +------------------------------> Transformation Space

Alternative Paths to Global Convergence

While Branch-and-Bound remains the bedrock of deterministic global registration, other paradigms bypass local minima by altering the optimization landscape itself or changing how data is represented.

  • Distributional Alignment: Instead of minimizing point-to-point distances, Mi et al. introduced Regularized Wasserstein Means (RWM) to align data as continuous distributions. This global perspective smooths out the optimization landscape, preventing the algorithm from getting trapped in local minima during extreme spatial rotations.
  • Physics-Inspired Fields: Wu et al. treated point clouds as physical particles interacting within a gravitational field. By minimizing a novel potential energy loss function, the optimization naturally glides toward global alignment, bypassing the narrow basins of attraction that trap standard gradient-descent methods.
  • Game Theory: Albarelli et al. mapped the correspondence problem to evolutionary game theory. In this framework, potential alignments are treated as players in a game where payoffs represent geometric compatibility. The system naturally evolves toward a global consensus, completely removing the need for a separate coarse-alignment phase.
  • Sequence-Based Matching: When data has a temporal or sequential progression, spatial proximity becomes secondary. Ramadani et al. utilized Dynamic Time Warping (DTW) to register catheter paths over time, leveraging the geometric progression of the trajectory to achieve global registration without any manual initialization.

By shifting from local refinement to deterministic space-searching and mathematical relaxations, initialization-independent registration transforms a fragile, hand-tuned alignment process into a robust, mathematically verifiable guarantee.

Key Foundational Work

The 3D-3D Registration Problem Revisited (2007) — contributed 2 concept elements to this direction.
The Registration Problem Revisited: Optimal Solutions From Points, Lines and Planes (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_initialization_independent_registration_7478fc90,
  title = {initialization-independent registration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/initialization-independent-registration/rdr_7478fc904f01422d835b7ae0a0294448},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_initialization_independent_registration_7478fc90_v1,
  title = {initialization-independent registration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/initialization-independent-registration/rdr_7478fc904f01422d835b7ae0a0294448/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake