# Robust Fitting in Computer Vision: Easy or Hard?

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2018.

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

- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Accelerating Globally Optimal Consensus Maximization in Geometric Vision](https://mlsanity.com/paper/2304.05156/) (2023)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [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)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [Unsupervised Learning for Robust Fitting:A Reinforcement Learning Approach](https://mlsanity.com/paper/2103.03501/) (2021)
- [Consensus Maximisation Using Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2103.04200/) (2021)
- [Transformation Decoupling Strategy based on Screw Theory for Deterministic Point Cloud Registration with Gravity Prior](https://mlsanity.com/paper/2311.01432/) (2023)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Maximum Consensus by Weighted Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2112.00953/) (2021)
- [A Revisit of the Normalized Eight-Point Algorithm and A Self-Supervised Deep Solution](https://mlsanity.com/paper/2304.10771/) (2023)
- [Robustness of Generalized Median Computation for Consensus Learning in Arbitrary Spaces](https://mlsanity.com/paper/2503.05215/) (2025)
- [DMDSC: A Dynamic-Margin Deep Simplex Classifier for Open-Set Recognition on Medical Image Datasets](https://mlsanity.com/paper/2605.00675/) (2026)
- [Event-driven Robust Fitting on Neuromorphic Hardware](https://mlsanity.com/paper/2508.09466/) (2025)

## Abstract (arXiv)

Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus maximisation, which strives to find the model parameters that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack of fundamental analysis of the problem in the computer vision literature. In particular, whether consensus maximisation is "tractable" remains a question that has not been rigorously dealt with, thus making it difficult to assess and compare the performance of proposed algorithms, relative to what is theoretically achievable. To shed light on these issues, we present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem, and resolve several ambiguities existing in the literature.