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

arXiv: https://arxiv.org/abs/1903.11683 · HTML: https://mlsanity.com/paper/1903.11683/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2019.

## Built on by (most cited first, 10 of 10)

- [A Single Correspondence Is Enough: Robust Global Registration to Avoid Degeneracy in Urban Environments](https://mlsanity.com/paper/2203.06612/) (2022)
- [KISS-Matcher: Fast and Robust Point Cloud Registration Revisited](https://mlsanity.com/paper/2409.15615/) (2024)
- [TriVoC: Efficient Voting-based Consensus Maximization for Robust Point Cloud Registration with Extreme Outlier Ratios](https://mlsanity.com/paper/2111.00657/) (2021)
- [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023)
- [DANIEL: A Fast and Robust Consensus Maximization Method for Point Cloud Registration with High Outlier Ratios](https://mlsanity.com/paper/2110.05075/) (2021)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [IRON: Invariant-based Highly Robust Point Cloud Registration](https://mlsanity.com/paper/2103.04357/) (2021)
- [Practical, Fast and Robust Point Cloud Registration for 3D Scene Stitching and Object Localization](https://mlsanity.com/paper/2111.04228/) (2021)
- [Discrete-Continuous Smoothing and Mapping](https://mlsanity.com/paper/2204.11936/) (2022)
- [Outlier-Robust Geometric Perception: A Novel Thresholding-Based Estimator with Intra-Class Variance Maximization](https://mlsanity.com/paper/2204.01324/) (2022)

## Abstract (arXiv)

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.