Math @ Duke
|
Publications [#347632] of Shahar Kovalsky
Papers Published
- Dym, N; Kovalsky, S, Linearly converging quasi branch and bound algorithms for global rigid registration,
Proceedings of the Ieee International Conference on Computer Vision, vol. 2019-October
(October, 2019),
pp. 1628-1636 [doi]
(last updated on 2020/07/31)
Abstract: © 2019 IEEE. 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 emph{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.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|