SDRSAC: Semidefinite-Based Randomized Approach for Robust Point Cloud Registration Without Correspondences

Huu M. Le, Thanh-Toan Do, Tuan Hoang, Ngai-Man Cheung

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.
Visual representation of successful point cloud registration on the Redwood dataset, showing the alignment of source (red) and target (blue) scans.

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.

Performance comparison showing # Correspondences (left) and Run Time (right) across varying overlapping rates. SDRSAC (red) maintains high correspondence counts with competitive computational efficiency.

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

Abstract

This paper presents a novel randomized algorithm for robust point cloud registration without correspondences. Most existing registration approaches require a set of putative correspondences obtained by extracting invariant descriptors. However, such descriptors could become unreliable in noisy and contaminated settings. In these settings, methods that directly handle input point sets are preferable. Without correspondences, however, conventional randomized techniques require a very large number of samples in order to reach satisfactory solutions. In this paper, we propose a novel approach to address this problem. In particular, our work enables the use of randomized methods for point cloud registration without the need of putative correspondences. By considering point cloud alignment as a special instance of graph matching and employing an efficient semi-definite relaxation, we propose a novel sampling mechanism, in which the size of the sampled subsets can be larger-than-minimal. Our tight relaxation scheme enables fast rejection of the outliers in the sampled sets, resulting in high-quality hypotheses. We conduct extensive experiments to demonstrate that our approach outperforms other state-of-the-art methods. Importantly, our proposed method serves as a generic framework which can be extended to problems with known correspondences.
BibTeX
@inproceedings{le2019sdrsac,
  author = {Huu M. Le and Thanh-Toan Do and Tuan Hoang and Ngai-Man Cheung},
  title = {{SDRSAC: Semidefinite-Based Randomized Approach for Robust Point Cloud Registration Without Correspondences}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2019},
  doi = {10.1109/cvpr.2019.00021},
}
Figure