Go-ICP: Solving 3D Registration Efficiently and Globally Optimally

Abstract

Registration is a fundamental task in computer vision. The Iterative Closest Point (ICP) algorithm is one of the widely-used methods for solving the registration problem. Based on local iteration, ICP is however well-known to suffer from local minima. Its performance critically relies on the quality of initialization, and only local optimality is guaranteed. This paper provides the very first globally optimal solution to Euclidean registration of two 3D point sets or two 3D surfaces under the L2 error. Our method is built upon ICP, but combines it with a branch-and-bound (BnB) scheme which searches the 3D motion space SE(3) efficiently. By exploiting the special structure of the underlying geometry, we derive novel upper and lower bounds for the ICP error function. The integration of local ICP and global BnB enables the new method to run efficiently in practice, and its optimality is exactly guaranteed. We also discuss extensions, addressing the issue of outlier robustness.

Keywords

InitializationIterative closest pointMaxima and minimaRobustness (evolution)Computer scienceOutlierAlgorithmMathematical optimizationEuclidean distanceArtificial intelligenceMathematicsPoint cloud

Affiliated Institutions

Beijing Institute of Technology CN

Related Publications

A Global Geometric Framework for Nonlinear Dimensionality Reduction

Joshua B. Tenenbaum , Vin de Silva , John Langford

Scientists working with large volumes of high-dimensional data, such as global climate patterns, stellar spectra, or human gene distributions, regularly confront the problem of ...

2000 Science 13453 citations

Graphical templates for model registration

Yali Amit , Augustine Kong

A new method of model registration is proposed using graphical templates. A graph of landmarks is chosen in the template image. All possible candidates for these landmarks are f...

1996 IEEE Transactions on Pattern Analysis... 130 citations

VoxelNet: End-to-End Learning for Point Cloud Based 3D Object Detection

Yin Zhou , Oncel Tuzel

Accurate detection of objects in 3D point clouds is a central problem in many applications, such as autonomous navigation, housekeeping robots, and augmented/virtual reality. To...

2018 4245 citations

Distributed Geodesic Control Laws for Flocking of Nonholonomic Agents

Nima Moshtagh , Ali Jadbabaie , Kostas Daniilidis

We study the problem of flocking and coordination of a group of kinematic nonholonomic agents in 2 and 3 dimensions. By analyzing the velocity vectors of agents on a circle (for...

2006 49 citations

PCA-SIFT: a more distinctive representation for local image descriptors

Ke Yan , Rahul Sukthankar

Stable local feature detection and representation is a fundamental component of many image registration and object recognition algorithms. Mikolajczyk and Schmid (June 2003) rec...

2004 3204 citations

Publication Info

Year: 2013
Type: article
Citations: 466
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Go-ICP: Solving 3D Registration Efficiently and Globally Optimally

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

466

OpenAlex

Cite This

APA Style

                            
                                    Jiaolong Yang, 
                                
                                    Hongdong Li, 
                                
                                    Yunde Jia
                                
                            (2013). 
                            Go-ICP: Solving 3D Registration Efficiently and Globally Optimally. 
                            
                            .
                            https://doi.org/10.1109/iccv.2013.184

Identifiers

DOI: 10.1109/iccv.2013.184