Low-rank matrix approximations for Coherent point drift

Coherent point drift (CPD) is a powerful non-rigid point cloud registration algorithm. A speed-up technique that allows it to operate on large sets in reasonable time, however depends on efficient low-rank decomposition of a large affinity matrix. The originally used algorithm for finding eigenvectors in this case is based on Arnoldi's iteration which, though very precise, requires the calculation of numerous large matrix-vector products, which even with further speed-up techniques is computationally intensive. We use a different method of finding that approximation, based on Nystrom sampling and design a modification that significantly accelerates the preprocessing stage of CPD. We test our modifications on a variety of situations, including different point counts, added Gaussian noise, outliers and deformation of the registered clouds. The results indicate that using our proposed approximation technique the desirable qualities of CPD such as robustness and precision are only minimally affected, while the preprocessing times are lowered considerably. (C) 2014 Published by Elsevier B.V.