Low-rank matrix approximations for Coherent point drift

• We test non-rigid Coherent point drift with different low-rank matrix approximations.
• We designed a clustering-based method of approximating eigenvectors.
• CPD preprocessing times have been decreased to about one third.
• Both precision of registration and robustness are sufficient for most applications.

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 Nyström 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.