Introduction
Point cloud registration—the process of aligning two 3D scans into a common coordinate system—is a fundamental challenge in computer vision, essential for applications ranging from autonomous driving to 3D reconstruction. Traditionally, this process relies on a two-step pipeline: extracting unique geometric feature descriptors and then matching those descriptors to find correspondences.
However, real-world data is often noisy, sparse, or characterized by repetitive structures where traditional descriptors fail. In such scenarios, practitioners often turn to Random Sample Consensus (RANSAC). Standard RANSAC uses minimal subsets (typically three points) to generate alignment hypotheses. Yet, when outlier ratios are high (e.g., 90%), the probability of selecting a "clean" subset becomes prohibitively low, leading to extreme computational costs. SDRSAC (Semidefinite-Based Randomized Approach for Robust Registration) addresses these limitations by introducing a descriptor-free framework that leverages structural geometry through semidefinite programming.
Methodology
SDRSAC reimagines the registration problem by moving away from local descriptors and focusing on the global geometric consistency of point subsets. The method introduces two primary innovations:
1. Larger-than-Minimal Sampling
Unlike standard RANSAC, which picks the bare minimum of points required to define a transformation, SDRSAC selects a larger subset (typically $N=16$). Statistically, a larger subset is more likely to capture the underlying structural "shape" of the object. While this increases the chance of including outliers in the sample, the framework uses a sophisticated "oracle" to handle them.
2. Graph Matching via SDP Relaxation
To find correspondences within these larger subsets without descriptors, the authors treat the problem as a Graph Matching task. Under the assumption of rigid transformation, the Euclidean distance between any two points in the source set must be preserved in the target set.
Matching these graphs is a Quadratic Assignment Problem, which is NP-hard. SDRSAC employs a tight Semidefinite Programming (SDP) relaxation to transform this discrete problem into a continuous, convex optimization. By introducing specific constraints to enforce one-to-one matching and prune geometrically inconsistent pairs, the relaxation becomes "tight," allowing the solver to quickly reject outliers and propose high-quality alignment hypotheses within the RANSAC loop.
Experimental Evaluation
The authors evaluated SDRSAC against state-of-the-art methods, including 4PCS, Super4PCS, Go-ICP, and standard ICP, using both synthetic and real-world datasets:
- Synthetic Data: The Stanford Bunny was used to test varying levels of Gaussian noise and outlier ratios (up to 50% non-overlapping regions).
- Real-World Data: The Redwood 3D dataset provided challenging indoor scenes (Office and Living Room) with large planar surfaces that typically confound descriptor-based methods.
Key Results and Discussion
Experimental results demonstrate that SDRSAC offers superior robustness in low-overlap scenarios. As shown in the performance metrics, SDRSAC maintains a significantly higher number of correct correspondences as the overlapping rate decreases, whereas competing methods like 4PCS and Go-ICP experience rapid performance degradation.
In real-world tests on the Redwood "Office" scene, SDRSAC identified 6,990 matches in approximately 8.69 seconds, outperforming Super4PCS, which found 6,388 matches in 10.05 seconds. Despite the mathematical complexity of SDP, the randomized framework allows for faster convergence to a global solution than many "globally optimal" branch-and-bound methods.
Conclusion
SDRSAC provides a robust alternative for 3D registration when feature descriptors are unavailable or unreliable. By combining the statistical advantages of larger-than-minimal sampling with the optimization power of SDP-based graph matching, the method achieves high-quality alignments in the presence of extreme noise and outliers. While currently limited to rigid registration, the framework establishes a powerful precedent for using convex relaxation techniques within randomized search architectures.
Summary updated