Outlier-Robust Spatial Perception: Hardness, General-Purpose Algorithms, and Guarantees

Vasileios Tzoumas, Pasquale Antonante, Luca Carlone

Abstract

Spatial perception—encompassing tasks like 3D registration, Simultaneous Localization and Mapping (SLAM), and camera geometry—is critical for autonomous robotics. However, these systems are often compromised by outliers resulting from incorrect data associations or sensor noise. This paper presents a rigorous study of outlier-robust spatial perception. We prove that the problem is fundamentally inapproximable in quasi-polynomial time, suggesting that universal polynomial-time guarantees are unlikely. In response, we propose ADAPT (Adaptive Trimming), a general-purpose framework that utilizes global solvers to iteratively identify and prune outliers. Crucially, ADAPT provides a posteriori certificates of sub-optimality. Our evaluations show that ADAPT maintains high accuracy in regimes with up to 90% outliers, outperforming standard heuristics like RANSAC.

Introduction: The Challenge of Outliers

Spatial perception serves as the "backbone" of modern robotics. Despite its importance, current algorithms struggle with outliers. Existing solutions typically fall into two categories: fast but brittle heuristics like RANSAC, which fail when outliers exceed 50%, or provably robust but computationally expensive methods like branch-and-bound, which are unsuitable for real-time applications. This work seeks a middle ground: an efficient, general-purpose framework that provides theoretical guarantees on the quality of the returned solution.

Theoretical Hardness and Verification

A key contribution of this work is the proof that outlier rejection in spatial perception is inapproximable. This theoretical result shifts the focus from seeking a "perfect" universal algorithm to developing methods that can verify their own performance. To this end, we developed a method to calculate "sub-optimality bounds" after an algorithm has executed. This allows a robotic system to assess the reliability of its perception results on the fly, identifying when a solution is likely close to the ground truth.

The ADAPT Algorithm

We introduce ADAPT (Adaptive Trimming), a framework designed to be algorithm-agnostic and applicable across various perception tasks.

Spatial perception tasks addressed by the ADAPT framework.

Unlike RANSAC, which builds models from minimal data subsets, ADAPT adopts a "global-to-local" approach:

  1. Global Initialization: It begins by considering the entire dataset and employs a "black-box" global solver (e.g., SE-Sync for SLAM) to find an initial estimate.
  2. Iterative Trimming: It calculates residuals for all measurements and adaptively trims those with the highest errors.
  3. Convergence: The process repeats, refining the threshold and the set of inliers until the solution converges.

Experimental Evaluation

The ADAPT framework was evaluated across three core domains using standard benchmarks:

  • 3D Registration: Stanford Bunny and ETH Hauptgebaude.
  • Two-View Geometry: Synthetic data and the EuRoC micro aerial vehicle dataset.
  • SLAM: 2D (MIT, Intel, CSAIL) and 3D (Sphere2500) datasets.

Key Results

ADAPT demonstrates exceptional robustness in high-outlier environments. In 3D registration tasks, it maintained near-zero error even with 90% outliers, matching the performance of specialized state-of-the-art solvers while remaining more general. In the MIT SLAM dataset, ADAPT successfully handled 20% outliers, whereas local methods like Dynamic Covariance Scaling (DCS) failed even with clean data due to local minima.

Predicted vs. actual performance bounds as a function of outlier percentage.

Furthermore, the theoretical bounds developed in this work were shown to be remarkably tight. As shown in the figure above, the predicted performance bounds closely track the actual error, providing a reliable metric for real-world deployment.

Conclusion

While ADAPT is computationally more intensive than local iterative methods—often by 1-2 orders of magnitude—its robustness makes it a superior choice for safety-critical robotics applications. By acknowledging the fundamental hardness of the problem and providing a way to certify results, this work offers a principled path forward for robust robotic perception. Future work will explore extending this framework to non-least-squares error norms and more complex robust cost functions.

Summary updated

Abstract

Spatial perception is the backbone of many robotics applications, and spans a broad range of research problems, including localization and mapping, point cloud alignment, and relative pose estimation from camera images. Robust spatial perception is jeopardized by the presence of incorrect data association, and in general, outliers. Although techniques to handle outliers do exist, they can fail in unpredictable manners (e.g., RANSAC, robust estimators), or can have exponential runtime (e.g., branch-and-bound). In this paper, we advance the state of the art in outlier rejection by making three contributions. First, we show that even a simple linear instance of outlier rejection is inapproximable: in the worst-case one cannot design a quasi-polynomial time algorithm that computes an approximate solution efficiently. Our second contribution is to provide the first per-instance sub-optimality bounds to assess the approximation quality of a given outlier rejection outcome. Our third contribution is to propose a simple general-purpose algorithm, named adaptive trimming, to remove outliers. Our algorithm leverages recently-proposed global solvers that are able to solve outlier-free problems, and iteratively removes measurements with large errors. We demonstrate the proposed algorithm on three spatial perception problems: 3D registration, two-view geometry, and SLAM. The results show that our algorithm outperforms several state-of-the-art methods across applications while being a general-purpose method.
BibTeX
@inproceedings{tzoumas2019outlier,
  author = {Vasileios Tzoumas and Pasquale Antonante and Luca Carlone},
  title = {{Outlier-Robust Spatial Perception: Hardness, General-Purpose Algorithms, and Guarantees}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=JBWodZK7uX},
}
Figure