PaperlayerView exact revision on arXiv

Source-linked AI summary

Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration

Jiaolong Yang, Hongdong Li, Dylan Campbell, Yunde Jia

arXiv:1605.03344v1cs.CV

TL;DR

ICP can become trapped in local minima and requires good initialization, while Go-ICP seeks a globally optimal 3D Euclidean registration solution. It uses branch-and-bound over SE(3) with geometry-based error bounds and achieves reliable registration across the reported tasks, including under partial overlap.

  • Problem

    ICP's non-convex local optimization can become trapped in local minima, making its result dependent on initialization and leaving no reliable way to detect failure.

  • Method

    Go-ICP applies branch-and-bound to 3D Euclidean registration under ICP's L2 closest-point error, using SE(3)-based error bounds and supporting trimming and other robust extensions.

  • Results

    Go-ICP achieved 100% correct registration on all 2,000 bunny and dragon registration tasks, with rotation errors below 2 degrees and translation errors below 0.01.

  • Takeaways & Limitations

    Go-ICP is useful when an exactly optimal solution is desired or a reliable initialization is unavailable, particularly when real-time performance is not critical.

  • Takeaways & Limitations

    Choosing the trimming percentage required visually estimating the non-overlapping ratio, although the reported results were not very sensitive to that parameter.

Abstract

from arXiv · show

The Iterative Closest Point (ICP) algorithm is one of the most widely used methods for point-set registration. However, being based on local iterative optimization, ICP is known to be susceptible to local minima. Its performance critically relies on the quality of the initialization and only local optimality is guaranteed. This paper presents the first globally optimal algorithm, named Go-ICP, for Euclidean (rigid) registration of two 3D point-sets under the L2 error metric defined in ICP. The Go-ICP method is based on a branch-and-bound (BnB) scheme that searches the entire 3D motion space SE(3). By exploiting the special structure of SE(3) geometry, we derive novel upper and lower bounds for the registration error function. Local ICP is integrated into the BnB scheme, which speeds up the new method while guaranteeing global optimality. We also discuss extensions, addressing the issue of outlier robustness. The evaluation demonstrates that the proposed method is able to produce reliable registration results regardless of the initialization. Go-ICP can be applied in scenarios where an optimal solution is desirable or where a good initialization is not always available.

1 INTRODUCTION

3D point-set registration is widely used, but ICP can converge to unreliable local minima because of nonconvexity and dependence on initialization. Go-ICP addresses this gap with a globally optimal SE(3) branch-and-bound search that preserves ICP’s error metric and can incorporate local ICP refinement.

  • Motivation: ICP alternates closest-point matching and transformation estimation, but its local iterative procedure can become trapped in local minima.Without good initialization, the resulting estimate may be far from the optimum, and ICP provides no reliable way to detect this failure.
  • Previous Work: Earlier approaches widen convergence basins, use heuristic global search, or perform coarse alignment, but they do not guarantee global optimality.Feature-based methods may also be unreliable or inapplicable for sparsely sampled or nonsmooth point-sets.
  • Contribution: Go-ICP is presented as the first globally optimal solution to ICP-defined Euclidean registration of two 3D point-sets.The method returns the exact globally optimal solution up to the desired accuracy.
  • Contribution: Go-ICP searches the six-dimensional SE(3) motion space with branch-and-bound and derives registration-error bounds adapted to its geometry.The method extends SO(3) space search to combined rotation and translation, a more challenging search problem.
  • Contribution: Local ICP is invoked whenever a better solution is found, using its result to update the branch-and-bound upper bound.This integration accelerates the search while retaining the global-search framework.
  • Extensions: The method follows ICP’s L2 closest-point residual metric and supports trimming, robust kernels, and robust norms for outlier handling.These extensions broaden the method beyond the outlier-free formulation.

2 PROBLEM FORMULATION

The paper formulates registration as minimizing the L2 closest-point error over rigid rotation and translation. Because closest-point distances and rotation domains are generally nonconvex, ICP’s alternating solution procedure guarantees only local convergence, while outliers can distort even a global optimum.

  • Registration Objective: Given data points X and model points Y, the objective estimates rotation R and translation t that minimize the L2 registration error.The formulation follows the standard point-to-point ICP metric.
  • Correspondences: For each transformed data point, the optimal correspondence is the closest model point in Y.The correspondence index j* varies with both the motion (R, t) and the data point x_i.
  • Optimization: ICP alternates between estimating the transformation and finding closest-point matches, yielding convergence to a local minimum.The transformation and correspondence subproblems are individually tractable, but their joint solution is not trivial.
  • Nonconvexity: The registration objective is generally nonconvex because discrete model point-sets are nonconvex and the rotation space is nonconvex.Translation can satisfy a convex-domain condition, but the discrete geometry of Y usually violates the distance-convexity condition.
  • Outliers: L2 least-squares fitting is sensitive to outliers, so the formulation initially assumes no outliers and later uses trimming for robustness.A small number of outliers may produce erroneous registration even when the global optimum is reached.

3 THE BRANCH AND BOUND ALGORITHM

Go-ICP applies branch-and-bound to search the full SE(3) motion space for globally optimal 3D registration. It parameterizes rotation and translation domains so they can be recursively subdivided and bounded.

  • 3 THE BRANCH AND BOUND ALGORITHM: BnB searches the nonconvex SE(3) registration domain by branching motion subdomains and computing upper and lower error bounds.The method must address both motion-domain parametrization and efficient bound construction.
  • 3.1 Domain Parametrization: SE(3) is minimally parameterized by a 3D angle-axis rotation vector and a 3D translation vector.The rotation matrix R_r is obtained from the angle-axis vector through the matrix exponential map.
  • 3.1 Domain Parametrization: The rotation domain is represented by the minimum cube [−π, π]3 enclosing the solid radius-π angle-axis ball.Angles below π have unique angle-axis representations, while boundary rotations can have two.
  • 3.1 Domain Parametrization: Translation is bounded within a cube [−ξ, ξ]3, with ξ set sufficiently large to contain the optimal translation.This bounded translation domain complements the rotation cube in the SE(3) search.
  • 3.1 Domain Parametrization: Octree subdivision recursively divides the initial rotation and translation cubes into smaller sub-cubes during BnB search.The resulting subdomains are denoted C_r and C_t.

4 BOUNDING FUNCTION DERIVATION

Go-ICP bounds registration error over each SE(3) subdomain by enclosing all possible transformed points within uncertainty balls. These radii yield valid per-point and aggregate L2-error bounds for branch-and-bound.

  • 4 BOUNDING FUNCTION DERIVATION: The bounding derivation seeks upper and lower bounds for the ICP L2 error within each rotation-translation domain C_r × C_t.The method first constructs uncertainty radii, then derives residual and total-error bounds.
  • 4.1 Uncertainty Radius: For a point x, uncertainty regions under rotations or translations are enclosed by balls characterized by rotation and translation uncertainty radii.The rotation radius is point-dependent, written γ_ri, while the translation radius is γ_t.
  • 4.1 Uncertainty Radius: The rotation uncertainty radius bounds the distance between R_r x and the center-transformed point R_r0 x for every rotation r in C_r.The derivation uses the angular relationship between rotations and their angle-axis representations.
  • 4.1 Uncertainty Radius: The translation uncertainty radius bounds the distance between x + t and x + t0 for every translation t in C_t.Together with rotation uncertainty, it places each transformed point within a ball centered at R_r0 x + t0 with radius γ_ri + γ_t.
  • 4.2 Bounding the L2 Error: For each data point, the lower residual bound is the nonnegative distance from the model point-set to the uncertainty ball around the center-transformed point.Any transformed point inside that ball therefore has closest-point residual no smaller than this bound.
  • 4.2 Bounding the L2 Error: Summing squared per-point residual bounds produces upper and lower bounds on the optimal L2 registration error over C_r × C_t.The upper bound can be obtained by evaluating the error at any motion inside the domain, whereas the lower bound requires the uncertainty-ball construction.

5 THE GO-ICP ALGORITHM

Go-ICP searches rotation and translation with nested branch-and-bound, using bounds to prune motion regions and ICP to refine promising candidates. The method also supports trimming and other robust ICP extensions.

  • Nested BnBs: A nested BnB searches SO(3) externally and solves optimal translations with an inner translation BnB, avoiding inefficient direct 6D branching.The nested structure maintains two queues, reduces redundant rotations, and exploits cheaper translation operations.
  • Nested BnBs: The rotation and translation BnBs use upper and lower registration-error bounds to decide which motion cubes to refine or discard.The search repeatedly subdivides cubes, evaluates bounds, and stops when the best error and current lower bound differ by less than ϵ.
  • Integration with ICP: Whenever a promising rotation cube improves the current bound, conventional ICP is initialized at its center and corresponding translation to refine the best solution.ICP is invoked when the cube’s upper bound is below the current best function value, after which the best error and motion are updated.
  • Integration with ICP: BnB guides ICP toward undiscarded cubes with small lower bounds, while ICP lowers the current-best error and thereby accelerates BnB convergence.This collaboration lets global search guide local refinement and lets local refinement improve pruning efficiency.
  • Outlier Handling with Trimming: Trimming robustifies Go-ICP by retaining the K points with smallest closest distances and deriving corresponding trimmed-error bounds for BnB.Trimmed ICP decreases registration error monotonically to a local minimum, allowing it to be integrated into the BnB procedure.
  • Outlier Handling with Trimming: The method can also accommodate robust kernels and Lp-norm ICP variants, including the robustness-promoting L1-norm.The paper additionally notes adaptation to LM-ICP through a robust kernelized lower bound.

6 EXPERIMENTS

Experiments show that Go-ICP achieves globally correct registrations across synthetic, benchmark, noisy, thresholded, outlier-containing, localization, and calibration settings, with runtime shaped by distance computation and convergence conditions.

  • 6.1 Optimality: Go-ICP produced correct registrations with both the distance transform and kd-tree, while remaining rotation domains contained the optima.The remaining domains were highly consistent across the two distance-computation methods.
  • 6.2 “Partial” to “Full” Registration: 100% correct registration was achieved on all 2 000 bunny and dragon tasks, with rotation errors below 2 degrees and translation errors below 0.01.With a distance transform, mean/longest runtimes were 1.6s/22.3s for bunny and 1.5s/28.9s for dragon.
  • 6.2 “Partial” to “Full” Registration: Distance-transform closest-point retrieval made runtime largely insensitive to model-point count and produced an approximately linear trend with the number of data points.The reported retrieval complexity was O(1).
  • 6.2 “Partial” to “Full” Registration: Runtime decreased as Gaussian noise increased until σ = 0.02, because noise smoothed the error landscape and widened the global minimum’s convergence basin.The stated mechanism especially concerns noise added to model points.
  • 6.2 “Partial” to “Full” Registration: With ϵ = 0.001×N, Go-ICP achieved a 100% success rate on bunny and dragon; smaller thresholds increased runtime and can help when local minima are small or near-optimal.The threshold was scaled linearly with N because registration error sums over the N data points.
  • 6.2 “Partial” to “Full” Registration: When RMS error increased to ∼0.04, the global minimum was found at about 25s, after which runtime was devoted to increasing the lower bound.For RMS error below 0.03, runtime remained almost constant in the reported experiment.
  • 6.3 Registration with Partial Overlap: Outlier-containing registrations took longer than outlier-free cases because outliers introduced additional local minima and trimming required extra computation.The trimming percentages were selected by visually estimating non-overlap and were not very sensitive in the reported bunny example.
  • 6.4 More Applications: Go-ICP successfully localized a baseball cap in 42 seconds using a distance transform and was evaluated for camera localization and RGB-D extrinsic calibration.The calibration experiment compared initial registration, ICP, and Go-ICP results for sparse color-camera reconstruction against dense depth data.

7 CONCLUSION

The paper introduces Go-ICP as a globally optimal solution for 3D Euclidean registration using ICP’s L2-norm error. Its BnB search exploits SE(3) geometry to guarantee global optimality regardless of initialization, making it useful when exact optimality or reliable initialization is unavailable.

  • 7 CONCLUSION: Go-ICP provides a globally optimal solution to 3D Euclidean registration under ICP’s L2-norm closest-point error metric.The method is presented as a solution whose global optimality is guaranteed.
  • 7 CONCLUSION: Branch-and-Bound search over SE(3), with registration error bounds derived from SE(3) geometry, guarantees global optimality regardless of initialization.The conclusion identifies the SE(3)-based error bounds as the key innovation.
  • 7 CONCLUSION: Go-ICP is especially useful when an exactly optimal solution is desired or when a good initialization is not reliably available.For non-real-time scenarios, it can also be applied directly or used as an optimality benchmark.
Loading 1605.03344v1…