Provably Approximated Point Cloud Registration

The goal of the alignment problem is to align a (given) point cloud P = p1, ⋯,pn to another (observed) point cloud Q = q1, ⋯,qn. That is, to compute a rotation matrix R ∈ ℝ3×3 and a translation vector t ∈ ℝ3 that minimize the sum of paired distances between every transformed point Rpi − t, to its corresponding point qi, over every i ∈ 1, ⋯,n. 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. Algorithms such as the Iterative Closest Point (ICP) 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, in practice, our approximation constants are close to 1 and our error is up to x10 times smaller than state-of-the-art algorithms.