אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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/ϵ.