Go-ICP: Solving 3D Registration Efficiently and Globally Optimally
Citations Over TimeTop 1% of 2013 papers
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.
Related Papers
- → Reducing Neural Network Parameter Initialization Into an SMT Problem (Student Abstract)(2021)2 cited
- → Eliminating all bad Local Minima from Loss Landscapes without even adding an Extra Unit(2019)3 cited
- A USEFUL BP ALGORITHM TO OVERCOME LOCAL MINIMA(1995)
- Faster escaping from local minima for back-propagation algorithm(2008)
- → Comparison of Random Weight Initialization to New Weight Initialization CONEXP(2020)