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.
Unlike RANSAC, which builds models from minimal data subsets, ADAPT adopts a "global-to-local" approach:
- 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.
- Iterative Trimming: It calculates residuals for all measurements and adaptively trims those with the highest errors.
- 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.
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