Introduction
Point cloud registration—the process of aligning two sets of 3D points—is a cornerstone of computer vision, robotics, and autonomous driving. It involves a fundamental "chicken and egg" dilemma: finding the best alignment requires correct matches (correspondences), while finding matches requires the sets to be aligned. The industry standard, Iterative Closest Point (ICP), is a local optimizer that frequently converges to suboptimal local minima. This paper introduces the first provable constant-factor approximation for the registration problem, providing a global solution with mathematical guarantees.
The Witness Set Method
The core innovation is the concept of a Witness Set. The authors prove that for any two point clouds, there exists a subset of only $d$ points (e.g., 3 points for 3D data) that "witnesses" the optimal transformation. This theory effectively decouples the search for optimal rotation and translation from the search for full correspondence.
The paper proposes several algorithms based on this insight:
- ALIGN (Algorithm 1): A novel method that takes a witness set and produces a transformation through iterative rotations and projections. It aligns one direction, projects the remaining points onto an orthogonal hyperplane, and repeats, ensuring subsequent steps do not disrupt previous alignments.
- P-RANSAC / ALIGN-AND-MATCH: Since the witness set is unknown, these algorithms use RANSAC-style sampling to find it, keeping the best result from multiple random subsets.
- PROB-ALIGN: A randomized, linear-time version that prioritizes points with a larger impact on the cost function.
Crucially, these methods work for a wide variety of cost functions, including outlier-resistant M-estimators like the Huber loss.
Key Results and Performance
The authors evaluated their approach using the Stanford 3D Scanning Repository (Bunny, Armadillo, Asian Dragon), synthetic data, and real-world RGB-D scans from the SUN3D dataset.
Accuracy and Robustness
In registration tests with noise, the proposed "Provable ICP" (P-ICP) achieved errors 2x to 10x smaller than standard ICP, CPD, and Go-ICP. Qualitative results demonstrate that P-ICP-Refined can successfully align complex models where standard ICP fails.
Outlier Robustness and Efficiency
The method remains stable even when 20% to 50% of the points are outliers. In these scenarios, it significantly outperformed state-of-the-art methods like TEASER++ in both accuracy and computational efficiency. While the theoretical approximation factor is $(1+\sqrt{2})^d$, empirical results show that the error is often very close to 1 (near-optimal), and sampling as few as 40 subsets is often sufficient in practice.
Limitations and Future Work
The algorithm's runtime and theoretical approximation factor depend exponentially on the dimension $d$. While efficient for 3D vision, it becomes computationally expensive for high-dimensional data. Future research directions include generalizing the framework to non-rigid registration and using deep learning to intelligently predict witness sets rather than relying on random sampling.
Summary updated