Source-linked AI summary
MAGSAC: marginalizing sample consensus
Daniel Barath, Jana Noskova, Jiri Matas
TL;DR
RANSAC depends on a user-specified noise scale that varies across scenes and determines the inlier-outlier threshold. The paper marginalizes over noise scales through σ-consensus, introducing MAGSAC plus σ-independent quality and termination criteria. MAGSAC improves geometric accuracy across tested estimation tasks, while one-shot post-processing nearly always improves robust-estimator outputs with only a few milliseconds of added processing time.
Problem
RANSAC's critical noise scale σ varies scene by scene, so standard variants require a user-provided threshold-setting parameter for robust estimation.
Method
σ-consensus marginalizes over a range of noise scales for weighted least-squares fitting, model quality evaluation, and RANSAC termination, and MAGSAC applies it during robust estimation.
Results
MAGSAC was superior in geometric accuracy to state-of-the-art methods on real-world datasets for fundamental matrix, essential matrix, and homography estimation.
Takeaways & Limitations
Applying σ-consensus once as post-processing nearly always improved outputs from RANSAC, MSAC, or LO-RANSAC with at most a few milliseconds of added processing time.
Takeaways & Limitations
The probabilistic interpretation of the termination confidence η holds only for the standard {0, 1} cost function.
Abstract
from arXiv · showhide
A method called, sigma-consensus, is proposed to eliminate the need for a user-defined inlier-outlier threshold in RANSAC. Instead of estimating the noise sigma, it is marginalized over a range of noise scales. The optimized model is obtained by weighted least-squares fitting where the weights come from the marginalization over sigma of the point likelihoods of being inliers. A new quality function is proposed not requiring sigma and, thus, a set of inliers to determine the model quality. Also, a new termination criterion for RANSAC is built on the proposed marginalization approach. Applying sigma-consensus, MAGSAC is proposed with no need for a user-defined sigma and improving the accuracy of robust estimation significantly. It is superior to the state-of-the-art in terms of geometric accuracy on publicly available real-world datasets for epipolar geometry (F and E) and homography estimation. In addition, applying sigma-consensus only once as a post-processing step to the RANSAC output always improved the model quality on a wide range of vision problems without noticeable deterioration in processing time, adding a few milliseconds. The source code is at https://github.com/danini/magsac.
1. Introduction
RANSAC is widely used in computer vision, but its critical noise-scale parameter varies across scenes and strongly affects the inlier-outlier threshold. The paper introduces σ-consensus and MAGSAC to remove the need for a precise user-defined scale while improving model estimation.
- RANSAC repeatedly fits models to randomly selected subsets and returns the highest-quality model after polishing.Its quality is commonly measured by support, such as the number of inliers, followed by least-squares fitting on those inliers.
- The noise scale σ determines the inlier-outlier threshold and strongly influences RANSAC's outcome.Standard RANSAC variants require users to provide σ, limiting fully automatic out-of-the-box use.
- The probabilistic interpretation of the confidence value η applies only to the standard {0, 1} cost function.
- Four real datasets show that σ varies from scene to scene, so no single setting works for all cases.
- σ-consensus eliminates the need for σ by marginalizing over noise scales and using the resulting weights in weighted least-squares fitting.Only an upper limit on the noise scale is required.
- The paper also proposes a σ-independent model-quality function and a termination criterion based on the same marginalization approach.These contributions address model evaluation and stopping without relying on a single inlier set or inlier ratio.
2. Notation
The notation formalizes input points, models, fitting, residuals, inlier selection, and model-quality functions used to describe robust estimation. It also records the residual-based quality definitions for RANSAC and MSAC.
- Input points are represented as P, with each point p in R^k, where k denotes the point dimension.Examples include k = 2 for 2D points and k = 4 for point correspondences.
- The model parameter vector θ lies on a model manifold Θ, and fitting function F computes model parameters from at least m points.For 2D lines, d = 2 represents angle and offset, while m = 2 is the minimum fitting-point count.
- Residual function D measures the point-to-model residual, while inlier-selection function I selects points under a threshold σ.For RANSAC, points satisfying D(θ, p) < σ are selected as inliers.
- Model quality Q assigns a real-valued score in which higher values indicate better models.RANSAC uses the number of selected inliers as its quality, whereas MSAC uses a residual-based quality function.
3. Marginalizing sample consensus
MAGSAC removes the need to manually choose the inlier noise scale by marginalizing over σ, then uses the resulting likelihoods for model quality, fitting, and termination.
- MAGSAC eliminates the threshold parameter from RANSAC-like robust model estimation by marginalizing over the noise scale σ.
- The model-quality function marginalizes likelihood over σ instead of relying on a particular inlier threshold or inlier set.
- σ is modeled as uniformly distributed on [0, σmax] when no prior information is available.
- Weighted least-squares fitting uses each point’s marginalized likelihood of being an inlier as its weight.
- Because a fixed σ and inlier ratio are unavailable, MAGSAC marginalizes the termination calculation over σ and updates the required iteration count when a better model appears.
4. Algorithms using σ-consensus
The algorithms apply σ-consensus either throughout MAGSAC or once to polish another estimator’s output, with discretization and early rejection used to control cost. Experiments report improved accuracy with little added processing time.
- Algorithms using σ-consensus: The paper proposes full MAGSAC polishing and a one-time σ-consensus post-processing step for outputs of other robust estimators.
- Post-processing: Applying σ-consensus once improved input models without noticeable processing-time deterioration, adding at most a few milliseconds.
- Speeding up the procedure: The σ range is limited by σmax, and uniform partitioning reduces least-squares fittings from K to d, with d set to 10 in experiments.
- Speeding up the procedure: SPRT skips σ-consensus for models that cannot improve the current best, using τref only for early evaluation rejection.
- Experimental examples: 2.9 pixels versus 4.3 for LO-MSC on homogr, and 4.4 versus 9.1 for LO-RSC on EVD, are reported as MAGSAC’s example homography errors.
- Experimental results: For fundamental-matrix estimation, post-processing improved results in nearly all tests, reduced errors by approximately 8%, and caused negligible processing-time deterioration.
- MAGSAC: MAGSAC estimates each model by sampling a minimal set, fitting and validating it, applying σ-consensus, and updating the best model and iteration count.
5. Experimental Results
Experiments on synthetic and real-world two-view geometry show that σ-consensus and MAGSAC improve geometric accuracy, with MAGSAC especially effective under high outlier ratios.
- Synthetic Tests: 500-run synthetic homography tests evaluated accuracy across noise levels and outlier ratios, plus processing time and fixed-iteration comparisons.The methods included RANSAC, MSAC, LO-RANSAC, LO-MSAC, and MAGSAC, with and without σ-consensus post-processing.
- Synthetic Tests: σ-consensus almost always improved the compared methods; LO-MSC + σ had lower geometric error than LO-MSC at every tested noise level.The synthetic tests used outlier ratios of 0.2, 0.5, and 0.8 at confidence 0.95.
- Synthetic Tests: MAGSAC was superior to competitors at every outlier ratio, less sensitive to noise, and more robust to outliers.It was slower when noise σ < 0.3 pixels but became fastest thereafter because it required significantly fewer iterations.
- Synthetic Tests: With fixed iteration counts, MAGSAC remained significantly more accurate than competitors and found the desired model in most high-outlier cases.For outlier ratio 0.8 the fixed count was 4 314 iterations, while for 0.9 it was 69 074.
- Real World Experiments: For fundamental matrices, post-processing improved results in nearly all tests with negligible processing-time deterioration, reducing errors by approximately 8%.MAGSAC was most accurate on kusvod2 and Multi-H and third on AdelaideRMF, 0.03 pixels behind the best method.
- Real World Experiments: Real-world evaluation covered 545 image pairs across fundamental, homography, and essential matrix estimation, averaging 100 runs per image pair.Table 1 reports geometric error, processing time, required samples, and failure proportion.
6. Conclusion
The paper introduces σ-consensus to remove the user-defined noise threshold from robust estimation and applies it in MAGSAC and a one-time polishing step. These methods improve geometric accuracy broadly, while MAGSAC is often faster at high outlier ratios.
- Conclusion: σ-consensus removes the user-defined threshold by marginalizing over a range of noise scales, while also supplying a model-quality function and termination criterion.These designs avoid requiring a fixed inlier set for quality evaluation.
- Conclusion: MAGSAC applies σ-consensus to models estimated from minimal samples and is superior in geometric accuracy on real-world F, E, and homography datasets.The conclusion also reports that MAGSAC is often faster than other RANSAC variants at high outlier ratios.
- Conclusion: The post-processing step applies σ-consensus once to polish a RANSAC output and nearly always improves model quality across vision problems.The reported processing-time increase is at most a few milliseconds.