CGGC Seminar: Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration

Speaker:
Nadav Dym (Duke University)
Date:
Wednesday, 3.7.2019, 11:30
Place:
Taub 401 Taub Bld.

Rigid registration is the problem of finding the optimal rigid motion and correspondence between two shapes, so that they are as similar as possible in terms of an appropriate energy.

We will describe several popular algorithms for this problem: PCA alignment and ICP, which are very efficient but are not globally optimal, as well as sampling and branch and bound (BnB) algorithms which exhibit slow convergence but are globally optimal.

Next we suggest our quasi BnB algorithm as an improvement upon the BnB approach. Quasi BnB replaces the linear lower bounds used in BnB algorithms with quadratic quasi-lower bounds. While quasi-lower bounds are not truly lower bounds, the Quasi-BnB algorithm is globally optimal. Our experiments show that Quasi-BnB is dramatically more efficient than BnB algorithms. Theoretically we show that quasi-BnB 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/ϵ.

Back to the index of events