mlsanityData to 7 Oct 2026

Robust Fitting in Computer Vision: Easy or Hard?

arXiv 1802.06464 ↗First posted 18 Feb 2018cs.CV cs.CCcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 6; 2024: 4; 2025: 2; 2026: 2.

25 papers.

Sort:

  1. 2023Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagationcited by 33
  2. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  3. 2021Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimizationcited by 21
  4. 2022A Hybrid Quantum-Classical Algorithm for Robust Fittingcited by 16
  5. 2024FastMAC: Stochastic Spectral Sampling of Correspondence Graphcited by 16
  6. 2022ARCS: Accurate Rotation and Correspondence Searchcited by 15
  7. 2023Accelerating Globally Optimal Consensus Maximization in Geometric Visioncited by 14
  8. 2021Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systemscited by 12
  9. 2026Advances in Global Solvers for 3D Visioncited by 12
  10. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  11. 2023G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Modelcited by 11
  12. 2023Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithmscited by 7
13 more
  1. 2024Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Cloudscited by 7
  2. 2022Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypointscited by 6
  3. 2024Robust Fitting on a Gate Quantum Computercited by 5
  4. 2021Unsupervised Learning for Robust Fitting:A Reinforcement Learning Approachcited by 4
  5. 2021Consensus Maximisation Using Influences of Monotone Boolean Functionscited by 3
  6. 2023Transformation Decoupling Strategy based on Screw Theory for Deterministic Point Cloud Registration with Gravity Priorcited by 3
  7. 2024CLIPPER: Robust Data Association without an Initial Guesscited by 3
  8. 2022Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Searchcited by 2
  9. 2021Maximum Consensus by Weighted Influences of Monotone Boolean Functionscited by 1
  10. 2023A Revisit of the Normalized Eight-Point Algorithm and A Self-Supervised Deep Solutioncited by 1
  11. 2025Robustness of Generalized Median Computation for Consensus Learning in Arbitrary Spacescited by 1
  12. 2026DMDSC: A Dynamic-Margin Deep Simplex Classifier for Open-Set Recognition on Medical Image Datasetscited by 1
  13. 2025Event-driven Robust Fitting on Neuromorphic Hardwarecited by 0