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

By Jiaolong Yang, Hongdong Li, Dylan Campbell, Yunde Jia. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016

1,133 citations recorded by the source corpus.

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 <inline-formula><tex-math notation="LaTeX">$L_2$</tex-math><alternatives> <inline-graphic xlink:type="simple" xlink:href="yang-ieq1-2513405.gif"/></alternatives></inline-formula> error metric defined in ICP. The Go-ICP method is based on a branch-and-bound scheme that searches the entire 3D motion space <inline-formula> <tex-math notation="LaTeX">$SE(3)$</tex-math><alternatives> <inline-graphic xlink:type="simple" xlink:href="yang-ieq2-2513405.gif"/></alternatives></inline-formula>. By exploiting the special structure of <inline-formula><tex-math notation="LaTeX">$SE(3)$</tex-math><alternatives> <inline-graphic xlink:type="simple" xlink:href="yang-ieq3-2513405.gif"/></alternatives></inline-formula> 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.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/9956619795b48410283be50fae12c15fa3695161

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

Citations in the corpus

RPM-Net: Robust Point Matching Using Learned Features (2020, background): “A notable exception, Go-ICP [40] uses a branch-and-bound scheme to search for the globally optimal registration at the trade-off of much longer computation times.”
Fast Global Registration (2016, methodology): “GoICP-Trimming produces accurate alignment in many cases but suffers from poor accuracy on others, presumably because its computational costs necessitate operation on downsampled point clouds.”
A comprehensive survey on point cloud registration (2021, methodology): “Given correspondences, the SVD-based estimation methods [6], [90], [9], [106], [7] perform singular value decomposition (SVD) to the difference of correspondences.”
DeepIM: Deep Iterative Matching for 6D Pose Estimation (2018, neutral): “Global registration methods (Mellado et al. 2014; Theiler et al. 2015; Zhou et al. 2016; Yang et al. 2016) solve a more challenging problem by not assuming an initial pose estimate.”
Feature-Metric Registration: A Fast Semi-Supervised Approach for Robust Point Cloud Registration Without Correspondences (2020, methodology): “There are plenty of literature focus on solving point cloud registration problem [24, 14, 26, 12, 25, 9].”
TEASER: Fast and Certifiable Point Cloud Registration (2020, methodology): “In general, the literature is divided between heuristics, that are fast but brittle, and global methods that are guaranteed to be robust, but run in worst-case exponential time (e.g., branch-&-bound methods, such as Go-ICP [20]).”
PRNet: Self-Supervised Learning for Partial-to-Partial Registration (2019, methodology): “Another trend is to improve the optimization: [13] applies Levenberg—Marquardt to the ICP objective, while global methods seek a solution using branch-and-bound [14], Riemannian optimization [15], convex relaxation [16], mixed-integer programming [17], and semideﬁnite programming [18].”
Deep Closest Point: Learning Representations for Point Cloud Registration (2019, methodology): “ModelNet40: Test on unseen point clouds Model MSE(R) RMSE(R) MAE(R) MSE(t) RMSE(t) MAE(t) ICP 892.601135 29.876431 23.626110 0.086005 0.293266 0.251916 Go-ICP [55] 192.258636 13.865736 2.914169 0.000491 0.022154 0.006219 FGR [61] 97.002747 9.848997 1.445460 0.000182 0.013503 0.002231 PointNetLK [18]”
Fast and Robust Iterative Closest Point (2020, methodology): “Besides ICP, other methods formulate registration as a global optimization problem [31], [32], [33], which produces globally optimal results at the expense of higher computational costs.”
Colored Point Cloud Registration Revisited (2017, background): “Such initial alignment can be obtained via global registration algorithms [18, 43, 47].”
DeepVCP: An End-to-End Deep Neural Network for Point Cloud Registration (2019, neutral): “[3, 37, 26, 39, 44] are some representative works among them.”
Deep Global Registration (2020, methodology): “We show that our modules are robust, accurate, and fast in comparison to both classical global registration algorithms [50, 35, 45] and recent end-to-end approaches [31, 41, 2].”
Image Matching from Handcrafted to Deep Features: A Survey (2020, methodology): “In the 3-D case, the rigid versions of GMM and CPD as well as ICP (Besl and McKay 1992) and GoICP (Yang et al. 2016) are evaluated.”