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.
- 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.
- The Pruning Rule: If $\hat{p}_k < l$, then correspondence $k$ is guaranteed to be a "true outlier" and is discarded.
- 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.
- 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.
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.
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