Provably Approximated ICP

The goal of the alignment problem is to align a (given) point cloud P = p1,cdots,pn to another (observed) point cloud Q = q1,cdots,qn. That is, to compute a rotation matrix R ∈ ℝ3 × 3 and a translation vector t ∈ ℝ3 that minimize the sum of paired distances sumi=1n D(Rpi-t,qi) for some distance function D. A harder version is the 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 always exists a "witness" set of 3 pairs in P × 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 x10 times smaller than state-of-the-art algorithms.