Source-linked AI summary
Graph-Cut RANSAC
Daniel Barath, Jiri Matas
TL;DR
Robust geometric estimation requires separating inliers from outliers despite imperfect random samples and costly local optimization. GC-RANSAC uses graph-cut labeling with model refitting in its local optimization step, and the paper reports greater geometric accuracy than state-of-the-art methods while remaining real-time for many problems. Its local optimization is globally optimal for the current best model and can be inserted into broader RANSAC systems.
Problem
RANSAC local optimization can become computationally expensive, ad hoc, complex, and parameter-heavy, while pointwise decisions overlook spatial coherence among inliers and outliers.
Method
GC-RANSAC alternates graph-cut labeling that models spatial coherence with model refitting during local optimization of the so-far-best model.
Results
GC-RANSAC is more geometrically accurate than state-of-the-art methods across several estimation problems, often with real-time speed approximately matching less accurate alternatives.
Takeaways & Limitations
The graph-cut local optimization is globally optimal for the so-far-best model and can be combined with components such as PROSAC sampling, degeneracy testing, and early termination.
Takeaways & Limitations
A RANSAC-like procedure using 7m-size samples in local optimization had high computational overhead without significantly improving accuracy in the experiments.
Abstract
from arXiv · showhide
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).
1. Introduction
GC-RANSAC addresses limitations of ad hoc local optimization in RANSAC by using graph cuts to exploit spatial coherence when a promising model is found. Experiments report improved accuracy, iteration efficiency, and real-time speed across geometric estimation problems.
- RANSAC background: RANSAC repeatedly hypothesizes models from random subsets, verifies point support, and returns the highest-support model, optionally polished using inliers.The approach underlies applications including stereo, motion segmentation, mosaicing, primitive detection, and multi-model fitting.
- Prior RANSAC extensions: Sampling variants such as NAPSAC, PROSAC, and EVSAC improve early all-inlier sampling by using spatial coherence, point ordering, or estimated inlier confidence.MLESAC and MSAC instead modify model-support estimation through likelihood-based costs.
- Local optimization: LO-RANSAC adds local optimization because random all-inlier samples can still produce poorly conditioned models that fail to separate all inliers.Its original implementation uses iterated least-squares refitting with a shrinking threshold.
- Local optimization: The established LO procedure becomes a computational bottleneck for models with many inliers and remains ad hoc, complex, and parameter-heavy despite subset-based acceleration.Using a 7m-sized inlier subset reduces fitting cost, where m is the minimum sample size.
- GC-RANSAC contribution: GC-RANSAC alternates graph-cut labeling and model refitting in local optimization, exploiting spatial coherence with globally optimal, efficient, and simpler processing.The method uses a few intuitive or learnable parameters and experimentally improves accuracy and required iterations over LO-RANSAC variants, while often being faster.
2. Local Optimization and Spatial Coherence
The paper formulates RANSAC inlier selection as binary energy minimization and adds spatially coherent pairwise terms to the distance-based unary costs. Graph cuts then obtain a globally optimal labeling efficiently.
- Energy formulation: The formulation represents points, model parameters, and point-to-model assignment costs using a binary inlier–outlier labeling.The model is parameterized by θ, and the distance function φ measures assignment cost.
- Unary energy: Standard RANSAC is recovered by penalizing only labels inconsistent with the inlier threshold ϵ: close points labeled outliers or far points labeled inliers.The labeling L assigns each point either 0 or 1.
- Unary energy: A continuous kernel loss replaces the binary loss to approximate maximum-likelihood estimation, improving accuracy and reducing sensitivity to threshold ϵ.GC-RANSAC uses this kernel-based unary energy in graph-cut verification.
- Spatial coherence: Pairwise energy incorporates point proximity, but uniform Potts penalties can let numerous nearby outliers overwhelm fewer inliers.GC-RANSAC assigns pair-specific penalties based on each point’s inlier probability to avoid this domination.
- Optimization: The total energy E(L) = EK(L) + λES(L) balances model fit and spatial coherence, and graph cuts determine its globally optimal labeling in polynomial time.λ controls the balance between unary and pairwise terms.
3. GC-RANSAC
GC-RANSAC integrates an energy-minimization local optimization into RANSAC, alternating graph-cut labeling with model re-fitting and using a data-driven criterion to limit LO applications.
- Main algorithm: The main algorithm builds a neighborhood graph, samples minimal point sets, estimates models, computes support, and applies LO when a new best model meets the criterion.The neighborhood graph uses a predefined sphere radius r and Fast Approximate Nearest Neighbors.
- Local optimization: GC-RANSAC makes local optimization simpler and cleaner than LO-RANSAC by alternating graph-cut labeling with model re-fitting.The graph-cut determines an optimal labeling, after which model parameters are re-estimated using selected or complete inliers.
- Implementation trade-offs: Selecting 7m-sized random inlier subsets during local optimization incurs high computational overhead without significantly improving accuracy in the experiments.The procedure is described as straightforward but was not beneficial relative to its added cost.
- LO scheduling: RANSAC’s required iteration count depends on confidence µ, minimal sample size m, and current inlier ratio estimated from |L∗|.The algorithm calculates the required iteration number from the current so-far-the-best model’s inlier count.
- LO scheduling: The LO application criterion replaces an initial iteration limit with q12 > ϵconf, a user-defined threshold for a significant confidence increase.The criterion is motivated by observations that optimizing models leading to termination often substantially increases confidence.
4. Experimental Results
GC-RANSAC is evaluated on synthetic line-fitting tests and real image pairs across fundamental matrix, homography, essential matrix, and affine transformation estimation. It generally achieves high geometric accuracy, while spatial coherence and selective local optimization improve performance without sacrificing speed.
- Synthetic Tests on 2D Lines: GC-RANSAC produces more accurate 2D line estimates than competitor algorithms across tested noise levels and outlier counts.The synthetic tests cover straight and dashed lines with 100 or 500 outliers and 1000 runs per noise level.
- Estimation of Fundamental Matrix: GC-RANSAC obtains the most accurate fundamental matrix models while using fewer samples than competing methods.The evaluation covers 48 image pairs from three publicly available datasets.
- Estimation of Homography: GC-RANSAC obtains the most accurate homography models in all but one test case: the EVD dataset under a time limit.The homography evaluation uses the homogr and EVD datasets, comprising 31 image pairs with short- and wide-baseline changes.
- Estimation of Essential Matrix: GC-RANSAC obtains the most accurate essential matrices in both time-limited and confidence-based experiments.The evaluation uses 467 image pairs; all methods show a significant accuracy drop when a time limit is imposed.
- Affine Transformation: GC-RANSAC is slightly more accurate than competing methods for affine transformations and remains faster than real time.Its marginally higher runtime is attributed to neighborhood computation.
- Parameter and Processing-Time Evaluation: Nonzero spatial-coherence weights reduce geometric error relative to λ = 0, with λ = 0.1 most accurate on average.The selected setting was used in the tests; replacing the standard local-optimization criterion also improves processing time without accuracy deterioration.
5. Conclusion
GC-RANSAC combines globally optimal graph-cut local optimization with a criterion that substantially reduces processing time without reducing accuracy. It is more geometrically accurate than state-of-the-art methods, runs in real time for many problems, and is simpler to implement reproducibly.
- GC-RANSAC is more geometrically accurate than state-of-the-art methods.
- It runs in real time for many problems at a speed approximately equal to less accurate alternatives.
- Its local optimization step is globally optimal for the so-far-the-best model parameters.
- The proposed local-optimization criterion significantly improves processing time without deteriorating accuracy.
- GC-RANSAC is simpler to implement reproducibly than competing RANSAC methods with local optimization.
- It can be inserted into USAC and combined with PROSAC sampling, degeneracy testing, and fast evaluation with early termination.