Source-linked AI summary
MAGSAC++, a fast, reliable and accurate robust estimator
Daniel Barath, Jana Noskova, Maksym Ivashechkin, Jiri Matas
TL;DR
Robust estimation must handle threshold choices, costly model refinement, and sampling failures caused by localized or spatially incoherent inliers. MAGSAC++ introduces threshold-independent scoring and IRLS-based marginalization, alongside Progressive NAPSAC sampling. Across six real-world homography and fundamental-matrix datasets, it was faster, more geometrically accurate, and failed less often than state-of-the-art robust methods.
Problem
Robust estimators face threshold dependence, expensive repeated least-squares fittings, and sampling weaknesses when inliers are localized or spatially incoherent.
Method
MAGSAC++ uses a model-quality function without an inlier-outlier decision, IRLS-based marginalization, and Progressive NAPSAC's transition from local to global sampling.
Results
Across six real-world homography and fundamental-matrix datasets, MAGSAC++ produced superior results, being faster, more geometrically accurate, and less failure-prone than state-of-the-art robust methods.
Takeaways & Limitations
The combined estimator and sampler provide a robust-estimation approach that finds local structures early while avoiding the weaknesses of purely localized sampling.
Takeaways & Limitations
The original MAGSAC requires time-consuming repeated least-squares fittings, while NAPSAC assumes spatially coherent inliers and can fail for sparse, non-coherent points.
Abstract
from arXiv · showhide
A new method for robust estimation, MAGSAC++, is proposed. It introduces a new model quality (scoring) function that does not require the inlier-outlier decision, and a novel marginalization procedure formulated as an iteratively re-weighted least-squares approach. We also propose a new sampler, Progressive NAPSAC, for RANSAC-like robust estimators. Exploiting the fact that nearby points often originate from the same model in real-world data, it finds local structures earlier than global samplers. The progressive transition from local to global sampling does not suffer from the weaknesses of purely localized samplers. On six publicly available real-world datasets for homography and fundamental matrix fitting, MAGSAC++ produces results superior to state-of-the-art robust methods. It is faster, more geometrically accurate and fails less often.
1. Introduction
RANSAC-like robust estimation faces threshold sensitivity, expensive refinement, and sampling failures when inliers are localized or spatially incoherent. MAGSAC++ addresses these issues with threshold-free scoring, efficient reweighting, and Progressive NAPSAC, achieving stronger real-world performance.
- Motivation: RANSAC repeatedly fits models from minimal random subsets, supporting many computer-vision tasks but treating samples without spatial proximity.Its variants have been applied to motion segmentation, stereo, matching, geometric primitive detection, mosaicing, and multi-model fitting.
- Prior approaches: Existing robust estimators reduce threshold dependence through likelihood, posterior, noise-scale selection, or marginalization strategies.MLESAC, MAPSAC, MINPRAN, a contrario RANSAC, and MAGSAC each modify model-quality estimation under different assumptions or procedures.
- Contributions: MAGSAC++ replaces MAGSAC's expensive repeated least-squares fittings with an iteratively re-weighted least-squares procedure and a new model-quality function.The new scoring function does not require an inlier-outlier decision, while the reformulated procedure avoids multiple costly LS estimations.
- Sampling limitations: Purely localized NAPSAC sampling can produce poorly conditioned or degenerate models and often fails when points are sparse and not spatially coherent.Its local samples increase the chance of all-inlier selections, but the resulting models may be imprecise or invalid for tasks such as seven-point fundamental-matrix fitting.
- Contributions: Progressive NAPSAC samples from gradually growing neighborhoods, finding local structures early while progressively blending local and global sampling.The blending factor depends on the input data, avoiding the weaknesses of purely localized samplers.
- Results: On six real-world datasets for homography and fundamental-matrix fitting, MAGSAC++ combined with P-NAPSAC was superior in speed, accuracy, and failure rate.Figure 1 shows image pairs where the tested alternatives failed while MAGSAC++ found inlier correspondences.
2. MAGSAC++
MAGSAC++ reformulates MAGSAC’s noise marginalization as IRLS, replacing repeated least-squares fits while retaining distribution-based weighting and model scoring.
- MAGSAC++: MAGSAC assumes uniformly distributed noise σ over (0, σmax) and χ2-distributed inlier residuals scaled by σ.For residuals, the paper uses the square root of the χ2-distribution and trims the distribution at a σ-dependent quantile.
- MAGSAC++: The original MAGSAC obtains final parameters by weighted least squares with weights formed by marginalizing point likelihoods over σ.For each possible σ, it selects inliers and performs least-squares fitting to obtain a σ-specific model.
- MAGSAC++: MAGSAC++ reformulates noise-level marginalization as iteratively reweighted least squares instead of requiring several least-squares fittings.The model parameters at iteration i+1 are computed from weighted residuals, starting from the minimal-sample model.
- MAGSAC++: MAGSAC++ interprets its weight function as the marginal density of inlier residuals and uses it in an M-estimator solved by IRLS.The weight is positive and decreasing, so each IRLS iteration does not increase the loss and the procedure converges to a local minimum.
- MAGSAC++: For point correspondences, σ-consensus++ uses τ(σ) = 3.64σ and σmax is typically set to a fairly high value such as 10 pixels.The procedure is applied to non-minimal samples and as post-processing for outputs from robust estimators.
- MAGSAC++: MAGSAC++ combines a new quality function with σ-consensus++ for estimating model parameters.The quality and loss calculations can use precise or approximate gamma-function values, with lookup tables making per-point computation fast.
3. Progressive NAPSAC sampling
Progressive NAPSAC combines localized and global sampling by progressively enlarging neighborhoods around selected points. This design seeks early local structures while avoiding the imprecision, degeneracy, and delayed global discovery associated with purely local sampling.
- Progressive sampling strategy: Progressive NAPSAC begins with localized minimal samples and gradually transitions toward global RANSAC-like sampling when local sampling does not terminate.The neighborhood growth balances the strict localization of NAPSAC with the global treatment of RANSAC.
- Progressive sampling strategy: The sampler selects an initial point, forms a neighborhood around it, and draws the remaining sample points from that neighborhood.The neighborhood is defined by points within a hyper-sphere, with the initial point and nearby points forming the minimal sample.
- Motivation and limitations: Local sampling can produce imprecise or degenerate models, including fundamental-matrix estimates from correspondences confined to one plane.These issues arise because localized samples may have poor conditioning or fail geometric requirements of the fitted model.
- Motivation and limitations: P-NAPSAC finds local structures earlier when points are spatially coherent and reaches global structures without noticeable delay when they are not.Its progressive neighborhood expansion is intended to retain the benefits of local sampling while avoiding the weaknesses of purely localized samplers.
- Neighborhood growth: Neighborhoods grow data-dependently as points are repeatedly selected, using hit numbers and a growth function to determine when enlargement occurs.P-NAPSAC increases each point's neighborhood when its selection count reaches the corresponding growth threshold.
- Implementation: A multi-layer grid is proposed to estimate neighborhoods efficiently because exhaustive spatial-relation computation can outweigh the benefits of early sampling.The method is designed for point correspondences and can be modified for other input data.
4. Experimental Results
Experiments on six real-world datasets evaluate MAGSAC++ for fundamental matrix and homography fitting, alongside Progressive NAPSAC sampling. MAGSAC++ generally improves accuracy, failure rate, threshold robustness, and speed, while P-NAPSAC accelerates estimation.
- Evaluation setup: MAGSAC++ was evaluated on fundamental matrix and homography fitting across six publicly available real-world datasets.The compared methods used common USAC components, with thresholds selected to maximize accuracy and confidence set to 0.99.
- Fundamental matrix fitting: MAGSAC++ was the most accurate estimator on CPC, Tanks and Temples, and TUM, while all methods had similar accuracy on easy short-baseline KITTI pairs.Accuracy was assessed using CDFs of symmetric geometric distance errors.
- Fundamental matrix fitting: MAGSAC++ was best on three of four fundamental-matrix datasets in both median error and failure rate, and was fastest on KITTI.Across the tested datasets, it was usually as fast as other robust estimators while providing superior accuracy and failure rate.
- Homography fitting: On EVD, MAGSAC++ had the highest accuracy, fewest failures, best median accuracy, and was 2.5 times faster than MAGSAC.On homogr, its accuracy was similar to GC-RANSAC, RANSAC, and MSAC, while it was almost an order of magnitude faster than those methods.
- Threshold sensitivity: MAGSAC and MAGSAC++ were significantly less sensitive to the inlier-outlier threshold than the other robust estimators.The comparison used average log10 errors as a function of the threshold in pixels.
- Progressive NAPSAC: P-NAPSAC required the fewest iterations and processing time, running approximately 1.6 times faster than PROSAC with similar accuracy.A relaxation factor γ = 0.1 substantially reduced iterations and processing time without noticeably worsening results.
5. Conclusion
The paper contributes MAGSAC++'s threshold-free scoring and iteratively re-weighted least-squares marginalization, together with Progressive NAPSAC sampling. Across six real-world datasets, the combined approach is faster, more accurate, and less failure-prone than state-of-the-art robust estimators.
- Contributions: MAGSAC++ introduces a model quality function without an inlier-outlier decision and formulates marginalization as iteratively re-weighted least squares.These changes avoid the expensive repeated least-squares fittings used by the original MAGSAC.
- Contributions: Progressive NAPSAC finds local structures early and progressively transitions to global sampling without purely localized samplers' weaknesses.The sampler exploits the tendency of nearby points to originate from the same model in real-world data.
- Conclusion: On six real-world homography and fundamental-matrix datasets, MAGSAC++ was faster, more geometrically accurate, and failed less often than state-of-the-art robust methods.The two proposed improvements can be combined with USAC components and P-NAPSAC sampling.