Provably Approximated ICP

The goal of the emph{alignment problem} is to align a (given) point cloud $P = {p_1,cdots,p_n}$ to another (observed) point cloud $Q = {q_1,cdots,q_n}$. That is, to compute a rotation matrix $R in mathbb{R}^{3 times 3}$ and a translation vector $t in mathbb{R}^{3}$ that minimize the sum of paired distances $sum_{i=1}^n D(Rp_i-t,q_i)$ for some distance function $D$. A harder version is the emph{registration problem}, where the correspondence is unknown, and the minimum is also over all possible correspondence functions from $P$ to $Q$. Heuristics such as the Iterative Closest Point (ICP) algorithm and its variants were suggested for these problems, but none yield a provable non-trivial approximation for the global optimum. We prove that there emph{always} exists a witness set of $3$ pairs in $P times Q$ that, via novel alignment algorithm, defines a constant factor approximation (in the worst case) to this global optimum. We then provide algorithms that recover this witness set and yield the first provable constant factor approximation for the: (i) alignment problem in $O(n)$ expected time, and (ii) registration problem in polynomial time. Such small witness sets exist for many variants including points in $d$-dimensional space, outlier-resistant cost functions, and different correspondence types. Extensive experimental results on real and synthetic datasets show that our approximation constants are, in practice, close to $1$, and up to x$10$ times smaller than state-of-the-art algorithms.