# Graph-Cut RANSAC

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

## Key facts

- Cited by 133 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2017.

## Built on by (most cited first, 30 of 133)

- [MASt3R-SfM: a Fully-Integrated Solution for Unconstrained Structure-from-Motion](https://mlsanity.com/paper/2409.19152/) (2024)
- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [3D Registration with Maximal Cliques](https://mlsanity.com/paper/2305.10854/) (2023)
- [Reloc3r: Large-Scale Training of Relative Camera Pose Regression for Generalizable, Fast, and Accurate Visual Localization](https://mlsanity.com/paper/2412.08376/) (2024)
- [SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration](https://mlsanity.com/paper/2203.14453/) (2022)
- [MeshLoc: Mesh-Based Visual Localization](https://mlsanity.com/paper/2207.10762/) (2022)
- [DPODv2: Dense Correspondence-Based 6 DoF Pose Estimation](https://mlsanity.com/paper/2207.02805/) (2022)
- [Robust Outlier Rejection for 3D Registration with Variational Bayes](https://mlsanity.com/paper/2304.01514/) (2023)
- [Generalized Differentiable RANSAC](https://mlsanity.com/paper/2212.13185/) (2022)
- [SGAligner : 3D Scene Alignment with Scene Graphs](https://mlsanity.com/paper/2304.14880/) (2023)
- [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021)
- [Point-TTA: Test-Time Adaptation for Point Cloud Registration Using Multitask Meta-Auxiliary Learning](https://mlsanity.com/paper/2308.16481/) (2023)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Neural Correspondence Field for Object Pose Estimation](https://mlsanity.com/paper/2208.00113/) (2022)
- [Visual Localization using Imperfect 3D Models from the Internet](https://mlsanity.com/paper/2304.05947/) (2023)
- [Relative Pose Estimation through Affine Corrections of Monocular Depth Priors](https://mlsanity.com/paper/2501.05446/) (2025)
- [Neural Reprojection Error: Merging Feature Learning and Camera Pose Estimation](https://mlsanity.com/paper/2103.07153/) (2021)
- [Cuboids Revisited: Learning Robust 3D Shape Fitting to Single RGB Images](https://mlsanity.com/paper/2105.02047/) (2021)
- [VSAC: Efficient and Accurate Estimator for H and F](https://mlsanity.com/paper/2106.10240/) (2021)
- [SC6D: Symmetry-agnostic and Correspondence-free 6D Object Pose Estimation](https://mlsanity.com/paper/2208.02129/) (2022)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (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)
- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [A Large Scale Homography Benchmark](https://mlsanity.com/paper/2302.09997/) (2023)
- [Deep Graph-based Spatial Consistency for Robust Non-rigid Point Cloud Registration](https://mlsanity.com/paper/2303.09950/) (2023)
- [Accelerating Globally Optimal Consensus Maximization in Geometric Vision](https://mlsanity.com/paper/2304.05156/) (2023)
- [Multiway Point Cloud Mosaicking with Diffusion and Global Optimization](https://mlsanity.com/paper/2404.00429/) (2024)
- [Learning to Make Keypoints Sub-Pixel Accurate](https://mlsanity.com/paper/2407.11668/) (2024)
- [TurboReg: TurboClique for Robust and Efficient Point Cloud Registration](https://mlsanity.com/paper/2507.01439/) (2025)

## Abstract (arXiv)

A novel method for robust estimation, called Graph-Cut RANSAC, GC-RANSAC in short, is introduced. To separate inliers and outliers, it runs the graph-cut algorithm in the local optimization (LO) step which is applied when a so-far-the-best model is found. The proposed LO step is conceptually simple, easy to implement, globally optimal and efficient. GC-RANSAC is shown experimentally, both on synthesized tests and real image pairs, to be more geometrically accurate than state-of-the-art methods on a range of problems, e.g. line fitting, homography, affine transformation, fundamental and essential matrix estimation. It runs in real-time for many problems at a speed approximately equal to that of the less accurate alternatives (in milliseconds on standard CPU).