Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration
This addresses the computational inefficiency in global rigid registration for applications requiring high accuracy, representing an incremental improvement over existing BnB algorithms.
The paper tackles the problem of globally optimizing rigid registration by proposing a Quasi Branch and Bound framework that replaces linear lower bounds with quadratic quasi-lower bounds, achieving linear convergence with O(log(1/ε)) time complexity and showing significantly higher efficiency than state-of-the-art methods in experiments.
In recent years, several branch-and-bound (BnB) algorithms have been proposed to globally optimize rigid registration problems. In this paper, we suggest a general framework to improve upon the BnB approach, which we name Quasi BnB. Quasi BnB replaces the linear lower bounds used in BnB algorithms with quadratic quasi-lower bounds which are based on the quadratic behavior of the energy in the vicinity of the global minimum. While quasi-lower bounds are not truly lower bounds, the Quasi-BnB algorithm is globally optimal. In fact we prove that it exhibits linear convergence -- it achieves $ε$-accuracy in $~O(\log(1/ε)) $ time while the time complexity of other rigid registration BnB algorithms is polynomial in $1/ε$. Our experiments verify that Quasi-BnB is significantly more efficient than state-of-the-art BnB algorithms, especially for problems where high accuracy is desired.