2019/04/03 by Nadav Dym, Dym, Nadav, Kovalsky Shahar +1 · 1 citation
Computer Science · Engineering · Medicine · #Computational Geometry (cs.CG) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Head and Neck Surgical Oncology #Optimization and Search Problems #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1904.02204
openalex publication_date 2019/04/03 · openalex created_date 2020/07/23 · openalex updated_date 2026/07/28
In recent years, several branch-and-bound (BnB) algorithms have been proposed\nto globally optimize rigid registration problems. In this paper, we suggest a\ngeneral framework to improve upon the BnB approach, which we name Quasi BnB.\nQuasi BnB replaces the linear lower bounds used in BnB algorithms with\nquadratic quasi-lower bounds which are based on the quadratic behavior of the\nenergy in the vicinity of the global minimum. While quasi-lower bounds are not\ntruly lower bounds, the Quasi-BnB algorithm is globally optimal. In fact we\nprove that it exhibits linear convergence -- it achieves \ε-accuracy in\n~O(\log(1/\ε)) time while the time complexity of other rigid\nregistration BnB algorithms is polynomial in 1/\ε . Our experiments\nverify that Quasi-BnB is significantly more efficient than state-of-the-art BnB\nalgorithms, especially for problems where high accuracy is desired.\n