Goal

Robustly fit a parametric model to a set $P$ of $N$ data points where an unknown fraction are inliers consistent with the true model within threshold $\varepsilon$, and the remainder are outliers with arbitrary residuals. Inputs: data set $P$; minimal sample size $s$; inlier-distance threshold $\varepsilon$; confidence target $\eta_0$ (typically 0.95 or 0.99); a per-point quality ordering for the PROSAC sampler; SPRT type-I error $\alpha$ and type-II error $\beta$. Outputs: model parameters $\theta^*$, inlier set $I^*$, and a locally-refined model fitted on a nonminimal sample drawn from $I^*$. The defining property is that USAC is an engineering framework that decomposes the RANSAC hypothesise-and-verify loop into four independently pluggable stages — sampling, model verification, degeneracy handling, and local optimisation — and integrates the best-known variant per stage (PROSAC, SPRT, DEGENSAC, LO-RANSAC) into a single reference open-source C++ implementation, USAC-1.0. Tested inlier-ratio range: 10–92% across homography, fundamental matrix, and essential matrix benchmarks.

Algorithm

Let $P$ denote the data set and $N = |P|$ the number of points. Let $s$ denote the minimal sample size required to instantiate the model. Let $\varepsilon$ denote the inlier-distance threshold. Let $\eta_0$ denote the confidence target for the stopping criterion. Let $\delta$ denote the probability that a randomly chosen datum is consistent with an incorrect model. Let $\Lambda_j$ denote the cumulative SPRT likelihood ratio after evaluating $j$ data points. Let $A$ denote the SPRT decision threshold. Let $T_N$ denote the PROSAC sample-count parameter — the number of draws at which the sampler expands to the full set. Let $\gamma$ denote the nonrandomness significance level used in the stopping criterion.

Procedure

Implementation

SPRT verification stage in Rust:

pub trait Sampler<P> {
    fn next_sample<'a>(&mut self, points: &'a [P], s: usize) -> Vec<&'a P>;
}

pub trait Verifier<M> {
    /// SPRT decision threshold A; depends on epsilon, delta, type-I/II errors.
    fn threshold(&self) -> f64;
    /// Per-point likelihood ratio increment p(x | H_b) / p(x | H_g).
    fn lr(&self, model: &M, point_residual: f64) -> f64;
}

pub trait LocalOptimizer<M> {
    /// Refit on a nonminimal sample drawn from the inlier set; return improved model.
    fn optimize(&self, model: &M, inliers: &[usize]) -> Option<M>;
}

pub trait DegeneracyChecker<M> {
    /// Return true if the minimal sample is degenerate for this model class.
    fn is_degenerate(&self, sample_residuals: &[f64]) -> bool;
}

/// SPRT verification inner loop (Eq. 9). Returns the inlier count or
/// None if the model was rejected early.
pub fn usac_verify<M, V: Verifier<M>>(
    model: &M,
    residuals: impl Iterator<Item = f64>,
    eps: f64,
    verifier: &V,
) -> Option<usize> {
    let a = verifier.threshold();
    let mut lambda: f64 = 1.0;
    let mut inliers = 0usize;
    for r in residuals {
        lambda *= verifier.lr(model, r);
        if lambda > a {
            return None;
        }
        if r <= eps { inliers += 1; }
    }
    Some(inliers)
}

Remarks

• USAC is a unifying engineering decomposition, not a single new mathematical technique. The reference C++ implementation (USAC-1.0) makes every module independently switchable, enabling isolated evaluation of SPRT-only, PROSAC-only, or LO-only effects on the same code path.
• SPRT verification reduces the mean number of point evaluations per hypothesis by a factor of 2–9× over the standard consensus count on homography and fundamental-matrix benchmarks (§3.4.3).
• The LO-RANSAC inner loop reduces the number of required outer iterations by a factor of 2–3 compared with vanilla RANSAC, bringing the observed iteration count in line with the theoretical prediction of Eq. (3) (§3.5.1).
• DEGENSAC handles planar degeneracy in fundamental-matrix estimation: when $\geq 5$ of the 7 minimal-sample correspondences lie on a common 3D plane, a model-completion step recovers the correct solution. Degeneracy modules for homography or essential-matrix degeneracies are not bundled in USAC-1.0 and require separate implementation.
• The SPRT-corrected stopping criterion uses nonrandomness significance level $\gamma = 0.05$ (§4.5.1, Eq. 12). Tightening $\gamma$ to 0.01 increases the required sample count; loosening to 0.10 risks accepting spurious solutions.
• See ransac for the four design axes that organise the modern RANSAC family, and fischler-bolles-ransac for the founding paradigm USAC unifies.

When to choose USAC over MAGSAC

MAGSAC addresses a different axis of practical RANSAC: it eliminates the user-tuned inlier threshold $\varepsilon$ by treating the noise scale $\sigma$ as a random variable on $[0, \sigma_\mathrm{max}]$ and marginalising the quality function over $\sigma$ ($\sigma$-consensus, IRLS-refit). USAC instead unifies an engineering decomposition (PROSAC + SPRT + LO-RANSAC + DEGENSAC) but keeps a fixed scalar $\varepsilon$. The two are orthogonal, not competing.

Choose USAC when (1) the inlier threshold $\varepsilon$ is well calibrated for the imagery and stable across the dataset; (2) sub-millisecond hypothesis verification matters and SPRT's 2–9× speedup pays for itself; (3) the problem is fundamental-matrix estimation under planar-degenerate scenes — DEGENSAC's model-completion step is built in.

Choose MAGSAC when (1) the inlier threshold is unknown or varies scene-to-scene — $\sigma_\mathrm{max} = 10$ px is a less sensitive upper bound; (2) geometric accuracy on real-world data outweighs verification speed — the IRLS refit on marginal-likelihood weights produces consistently lower transfer-error on public benchmarks; (3) the user wants a single hyperparameter ($\sigma_\mathrm{max}$) rather than a per-problem $\varepsilon$ tune.

The two are stackable: MAGSAC reuses the SPRT pre-screen from USAC (with $\tau_\mathrm{ref} = 1$ px) and PROSAC ordering for sampling; USAC's LO-RANSAC inner loop can be replaced with MAGSAC's IRLS refit. The MAGSAC++ follow-up (CVPR 2020) integrates both into a single pipeline.

References

1. R. Raguram, O. Chum, M. Pollefeys, J. Matas, J.-M. Frahm. USAC: A Universal Framework for Random Sample Consensus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8)
   –2038, 2013. ieeexplore.ieee.org