RANSAC Back to SOTA: A Two-Stage Consensus Filtering for Real-Time 3D Registration

Pengcheng Shi, Shaocheng Yan, Yilin Xiao, Xinyi Liu, Yongjun Zhang, Jiayuan Li

TL;DR

The proposed Two-stage Consensus Filtering (TCF) framework revitalizes the classic RANSAC algorithm for 3D point cloud registration, achieving state-of-the-art accuracy with up to a 1000x speedup over existing methods. By cascading one-point and two-point geometric filtering steps before the standard three-point RANSAC, the method drastically reduces the required iterations and outlier ratios, enabling robust, real-time performance.

What Problem Does This Paper Address?

3D Point Cloud Registration (PCR) is the process of aligning two 3D scans into a single coordinate system—a fundamental task for self-driving cars and robotic mapping. The biggest hurdle is the presence of "outliers": incorrect point matches caused by sensor noise, occlusions, or repetitive patterns.

The traditional solution is RANSAC (Random Sample Consensus), which randomly picks small subsets of matches to find a valid alignment. However, RANSAC has a major flaw: as the percentage of outliers increases, the number of random trials needed to find a "clean" subset grows exponentially. In many real-world 3D scenarios, outlier ratios can exceed 95%, making standard RANSAC either painfully slow or highly inaccurate (see Figure 2). Modern alternatives like MAC or TEASER are more robust but often come with high computational costs, sometimes taking minutes to process a single pair of scans.

Registration recall of RANSAC vs. iterations. Standard RANSAC requires millions of iterations to reach 100% recall when outliers are prevalent.

Methods

The authors introduce a cascaded pipeline called TCF-based PCR that filters outliers in stages of increasing geometric complexity:

  1. One-point RANSAC: Instead of picking three points to estimate a full pose, it picks just one match and uses a "length consistency" constraint. It checks if the distance between two points in the source cloud matches the distance between their corresponding points in the target cloud. This rapidly identifies a large "consensus set" of likely-correct matches.
  2. Two-point RANSAC: This stage refines the previous set using "angle consistency." It ensures that the triangles formed by matches have similar shapes (congruency) across both clouds, catching outliers that might have accidentally passed the length check (see Figure 5).
  3. Three-point RANSAC: Because the first two stages have already eliminated the vast majority of outliers, the standard three-point RANSAC now only needs a handful of iterations to find a high-quality coarse pose.
  4. Scale-adaptive Cauchy IRLS: A final optimization step (Iteratively Reweighted Least Squares) fine-tunes the 6-DOF pose, using a robust estimator to ignore any remaining noise.
The overall TCF framework showing the progression from raw correspondences to a refined 6-DOF pose.

Datasets

The method was evaluated on two major benchmarks:

  • ETH Dataset: Challenging terrestrial laser scans of various environments (arch, courtyard, facade, office, trees). The "trees" sequence is particularly difficult due to complex geometry and high outlier ratios.
  • KITTI Dataset: A large-scale outdoor LiDAR dataset for autonomous driving, featuring highway and urban sequences with significant motion and feature distortion.

Key Insights and Ideas

  • Lowering the Sampling Dimension: The core "aha" moment is that RANSAC's complexity is tied to the sample size ($s$). By starting with $s=1$ and $s=2$ for filtering, the authors bypass the exponential explosion of the standard $s=3$ approach.
  • Geometric Pruning: Simple constraints like length and angle consistency are computationally "cheap" but incredibly effective at rejecting outliers before expensive pose estimation begins.
  • RANSAC is Back: This paper demonstrates that "old-school" geometric algorithms, when optimized with modern filtering strategies, can outperform complex graph-based or deep-learning-based methods in both speed and reliability.

Key Results

  • Massive Speedup: On the ETH "trees" sequence, TCF achieved 100% recall in just 59 ms. In comparison, the previous state-of-the-art method, MAC, took over 331 seconds to achieve the same result—a speedup of over three orders of magnitude (see Figure 1).
  • High Robustness: TCF maintained near-perfect recall even in environments where the initial inlier ratio was as low as 1.1%.
  • SOTA Accuracy: Across both KITTI and ETH, TCF consistently matched or exceeded the accuracy of much slower competitors like TEASER and SC2PCR.
Recall vs. Runtime on the ETH tree sequence. TCF (red star) sits in the top-left corner, indicating it is both the fastest and most accurate.

Limitations and Future Work

  • Feature Dependency: Like most correspondence-based methods, TCF's performance is still linked to the quality of the initial feature descriptors (e.g., FPFH). If the initial matching produces zero correct inliers, no amount of filtering can recover the pose.
  • Parameter Sensitivity: While the authors automated some noise bounds, the method still relies on a few hyperparameters (like the noise threshold $\tau$) that might need tuning for vastly different sensor types.
  • Future Directions: The authors suggest that TCF's filtering modules are "plug-and-play" and could be integrated into other registration frameworks to boost their efficiency.

Summary updated

Abstract

Correspondence-based point cloud registration (PCR) plays a key role in robotics and computer vision. However, challenges like sensor noises, object occlusions, and descriptor limitations inevitably result in numerous outliers. RANSAC family is the most popular outlier removal solution. However, the requisite iterations escalate exponentially with the outlier ratio, rendering it far inferior to existing methods (SC2PCR [Chen et al., 2022], MAC [Zhang et al., 2023], etc.) in terms of accuracy or speed. Thus, we propose a two-stage consensus filtering (TCF) that elevates RANSAC to state-of-the-art (SOTA) speed and accuracy. Firstly, one-point RANSAC obtains a consensus set based on length consistency. Subsequently, two-point RANSAC refines the set via angle consistency. Then, three-point RANSAC computes a coarse pose and removes outliers based on transformed correspondence's distances. Drawing on optimizations from one-point and two-point RANSAC, three-point RANSAC requires only a few iterations. Eventually, an iterative reweighted least squares (IRLS) is applied to yield the optimal pose. Experiments on the large-scale KITTI and ETH datasets demonstrate our method achieves up to three-orders-of-magnitude speedup compared to MAC while maintaining registration accuracy and recall.
BibTeX
@article{shi2024ransac,
  author = {Pengcheng Shi and Shaocheng Yan and Yilin Xiao and Xinyi Liu and Yongjun Zhang and Jiayuan Li},
  title = {{RANSAC Back to SOTA: A Two-Stage Consensus Filtering for Real-Time 3D Registration}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2024},
  url = {https://openreview.net/forum?id=iFj4Rp8Sng},
}

Loading related content...

Figure