Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration

Nadav Dym, Shahar Ziv Kovalsky; Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2019, pp. 1628-1636

Abstract


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 epsilon accuracy in O(log(1/epsilon)) time while the time complexity of other rigid registration BnB algorithms is polynomial in 1/epsilon. 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.

Related Material


[pdf] [supp] [video]
[bibtex]
@InProceedings{Dym_2019_ICCV,
author = {Dym, Nadav and Kovalsky, Shahar Ziv},
title = {Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration},
booktitle = {Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)},
month = {October},
year = {2019}
}