Guaranteed Outlier Removal for Point Cloud Registration with Correspondences

Álvaro Parra Bustos, Tat-Jun Chin

This paper introduces Guaranteed Outlier Removal (GORE), a deterministic preprocessing technique designed to tackle the "needle in a haystack" problem of 3D point cloud registration. By using fast geometric consistency checks, GORE aggressively prunes false correspondences while mathematically guaranteeing that the globally optimal solution remains in the dataset.

TL;DR

GORE is a fast, deterministic preprocessor that slashes outlier rates in 3D point cloud correspondences (often from >95% down to <30%) before optimization begins. Unlike heuristic filters, it provides a theoretical guarantee that no true inliers are removed, enabling both RANSAC and globally optimal solvers to run orders of magnitude faster.

What Problem Does This Paper Address?

3D point cloud registration—aligning two sets of 3D points—is fundamental to robotics and computer vision. While we often use keypoint descriptors (like SIFT for 3D) to find matching points, 3D descriptors are notoriously noisy. It is common to face outlier rates exceeding 95%, where the vast majority of "matches" are simply wrong.

Standard robust estimators like RANSAC struggle here because their runtime increases exponentially with the outlier ratio. Conversely, globally optimal methods like Branch-and-Bound (BnB) are theoretically sound but practically too slow for large, noisy datasets. The authors identify a critical gap: we need a way to "clean" the data before the heavy lifting of optimization starts, without accidentally throwing away the correct solution.

Methods

The core of GORE is a "reject-only" strategy based on a simple but powerful observation: if a specific correspondence $k$ cannot possibly belong to a consensus set larger than the one we've already found, then $k$ must be an outlier.

  1. Lower and Upper Bounds: The algorithm maintains a lower bound ($l$), which is the size of the best consensus set found so far. For every correspondence $k$, it calculates an upper bound ($\hat{p}_k$) representing the maximum number of other points that could theoretically be aligned if $k$ were a true inlier.
  2. The Pruning Rule: If $\hat{p}_k < l$, then correspondence $k$ is guaranteed to be a "true outlier" and is discarded.
  3. Geometric Kernels:
    • For Rotation (3 DoF): The authors use a clever "interval stabbing" approach. They bound the possible rotation angles that could align a point pair and find the maximum overlap of these intervals.
  4. For Rigid Transformation (6 DoF): To avoid the complexity of a 6D search, they translate the problem into a rotation-only subproblem by doubling the error threshold ($2\xi$). This provides a valid, though looser, upper bound that is much faster to compute.
Illustration of GORE reducing a massive set of 2000 correspondences (98% outliers) to a tiny, manageable set of 60 (28% outliers) in just 4.6 seconds.

Datasets

The authors evaluated GORE across a wide variety of challenging scenarios:

  • Synthetic Data: Used to rigorously test performance across varying outlier rates (up to 99%) and data sizes.
  • Standard 3D Models: The Stanford Repository (bunny, dragon, armadillo, buddha) and Mian’s dataset (t-rex, chef).
  • Real-World Large Scale: Laser scans of underground mines and remote sensing data (ISPRS Vaihingen).
  • RGB-D Data: Microsoft 7-scenes (office, kitchen) and the RGB-D Object Dataset for object localization in cluttered scenes.

Key Insights and Ideas

  • Deterministic vs. Stochastic: Unlike RANSAC, which is random and might miss the best solution, GORE is deterministic. It doesn't "guess"; it proves that certain points are junk.
  • The "Guaranteed" Property: The most significant insight is the proof that $I^* \subseteq \mathcal{H}' \subseteq \mathcal{H}$. This means the reduced set $\mathcal{H}'$ is guaranteed to contain the global optimum $I^*$. This allows researchers to use GORE as a "safe" front-end for any other algorithm.
  • Threshold Doubling: The mathematical trick of doubling the threshold to eliminate translation parameters is a highly effective way to simplify 6 DoF problems into 3 DoF problems for bounding purposes.

Key Results

  • Massive Data Reduction: On real datasets like mining and remote sensing, GORE eliminated nearly 90% of true outliers. In one example (Figure 1), it reduced the outlier rate from 98% to 28%.
  • Speedups: Preprocessing with GORE allowed RANSAC to converge two orders of magnitude faster. For globally optimal BnB, GORE typically halved the total runtime.
  • Robustness: GORE proved effective even in cases with "structured outliers" (e.g., self-similar channels in mines) where standard methods often fail.
Fig. 2. Relating the Euclidean and the angular error. (a) A solid ball intersects the surface of a sphere at a spherical patch, which has a circular outline in the sphere (highlighted in red). (b) Side view of the circular outline.

Limitations and Future Work

  • Low Outlier Regimes: The authors acknowledge that GORE is a "heavy" preprocessor. If your data is already relatively clean (e.g., <30% outliers), the time spent running GORE might exceed the time saved during optimization.
  • Worst-Case Complexity: While efficient in practice, the worst-case complexity for the 6 DoF version involves BnB, which is theoretically exponential. However, because GORE runs this on a much smaller, pruned subset, it remains fast for practical applications.
  • Future Directions: The authors suggest that the geometric consistency principles used here could be extended to other robust estimation problems beyond point cloud registration, such as fundamental matrix estimation in 2D vision.

Summary updated

Abstract

An established approach for 3D point cloud registration is to estimate the registration function from 3D keypoint correspondences. Typically, a robust technique is required to conduct the estimation, since there are false correspondences or outliers. Current 3D keypoint techniques are much less accurate than their 2D counterparts, thus they tend to produce extremely high outlier rates. A large number of putative correspondences must thus be extracted to ensure that sufficient good correspondences are available. Both factors (high outlier rates, large data sizes) however cause existing robust techniques to require very high computational cost. In this paper, we present a novel preprocessing method called \emph{guaranteed outlier removal} for point cloud registration. Our method reduces the input to a smaller set, in a way that any rejected correspondence is guaranteed to not exist in the globally optimal solution. The reduction is performed using purely geometric operations which are deterministic and fast. Our method significantly reduces the population of outliers, such that further optimization can be performed quickly. Further, since only true outliers are removed, the globally optimal solution is preserved. On various synthetic and real data experiments, we demonstrate the effectiveness of our preprocessing method. Demo code is available as supplementary material.
BibTeX
@article{bustos2018guaranteed,
  author = {Álvaro Parra Bustos and Tat-Jun Chin},
  title = {{Guaranteed Outlier Removal for Point Cloud Registration with Correspondences}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2018},
  url = {https://openreview.net/forum?id=rmVEv4He_6S},
}
Figure