RANSAC Scoring Done Right

Addressing the Achilles' Heel of RANSAC

Traditional RANSAC (Random Sample Consensus) algorithms, widely used for robust model estimation in the presence of outliers, have long struggled with a critical dependency: the need for a user-supplied parameter related to the inlier scale. This parameter, often a residual threshold, dictates how candidate models are scored, typically by counting inliers or summing per-point scores. The challenge lies in the fact that this inlier scale itself must be estimated from potentially noisy and contaminated data, making the process prone to errors and requiring extensive manual tuning for different datasets.

This inherent circularity—estimating a scale to then score against it—introduces a significant bottleneck in RANSAC's practical application. Miscalibration of this threshold can lead to substantial degradation in performance, limiting the algorithm's robustness and requiring considerable effort from practitioners to achieve optimal results across varied scenarios, from image processing to 3D reconstruction.

A Paradigm Shift in Inlier Scale Inference

The paper proposes a fundamental shift in the inference process to overcome this limitation. Instead of the conventional approach of estimating the inlier scale and then using it for scoring, the authors introduce a method that analytically marginalizes the inlier scale. This is achieved by employing a conjugate Inverse-Gamma prior for a fixed inlier partition, effectively integrating out the scale parameter from the scoring formula. The result is a single, closed-form expression that inherently adapts to different data regimes.

Crucially, this new score spans both non-informative Jeffreys limits and informative empirical-Bayes priors, allowing the same algorithm to perform effectively in both data-rich and data-scarce environments without any modification. This innovation marks the first RANSAC score where the inlier scale is genuinely absent from the formula, simplifying its application and enhancing its theoretical elegance. The computational efficiency is also addressed, with the proposed score admitting an O(N log N) computation via a sort-and-sweep mechanism.

Unprecedented Robustness and Accuracy

The empirical validation of this new RANSAC score demonstrates significant improvements over the state of the art. Tested on a comprehensive benchmark of nearly 70,000 image pairs, encompassing various two-view estimation problems and both engineered and learned feature pipelines, the proposed method consistently outperforms existing RANSAC variants like MSAC, GaU, and MAGSAC. A key finding is its remarkable stability under threshold miscalibration, where baseline methods typically degrade significantly.

Furthermore, the new score achieves near-optimal accuracy with as few as two validation pairs, a stark contrast to baselines that often require hundreds of times more data. Its ability to tighten prior regularization as validation data becomes scarce further underscores its adaptability and robustness. These results suggest a substantial leap forward in the practical utility and theoretical soundness of RANSAC, promising more reliable and autonomous model estimation in complex computer vision tasks.