Goal

Reduce the number of samples RANSAC needs to reach a given confidence, and improve the quality of the returned model, by correcting the assumption underlying the standard termination criterion — that a model instantiated from one outlier-free minimal sample is consistent with the entire inlier set. Input: $N$ correspondences, minimal sample size $m$, inlier threshold $\theta$. Output: model parameters and the achieved inlier set, reached with the same termination guarantee as standard RANSAC but in measurably fewer trials, using no additional input information beyond what standard RANSAC requires.

Algorithm

Let $\eta$ denote the probability of having missed the full inlier set after $k$ samples. Let $P_I$ denote the probability that an $m$-point minimal sample is entirely outlier-free, and $\varepsilon = I/N$ the inlier fraction. Let $\theta$ denote the inlier-distance threshold and $K$ a threshold multiplier used by the iterative local-optimization variant. Let $I_k$ denote the inlier count of the $k$-th sampled hypothesis.

Procedure

Five local-optimization variants are compared for step 3:

1. Standard — no local optimization (baseline RANSAC).
2. Simple — collect all points with error below $\theta$ under the minimal-sample model and re-fit by a non-minimal linear algorithm.
3. Iterative — collect points with error below $K\theta$ (a looser threshold), re-fit, then shrink the threshold toward $\theta$ and repeat. Restricting the first re-fit to points already close to a sample-consistent model excludes leverage points that would otherwise corrupt a naive iteratively-reweighted least-squares pass over the whole data set.
4. Inner RANSAC — run a fresh, smaller RANSAC restricted to the $I_k$ inlier points of the current best model, drawing non-minimal inner samples of size $\min(I_k/2, 14)$ for epipolar geometry or $\min(I_k/2, 12)$ for homography, repeated 10 times, and verified against the full data set.
5. Inner RANSAC with iteration — method 4, with each inner-RANSAC sample additionally refined by method 3's threshold-shrinking re-fit.

Implementation

The outer loop with a pluggable local-optimization hook, implementing method 5 (Inner RANSAC with iteration), in Rust:

pub trait LocalOptimizer<M, P> {
    /// Draw a non-minimal inner sample from `inliers`, refit, and shrink
    /// the acceptance threshold toward `theta` across `rounds` passes.
    fn refine(&self, model: &M, points: &[P], inliers: &[usize], theta: f64) -> Option<M>;
}

/// One outer LO-RANSAC iteration: fit a minimal-sample model, count inliers,
/// and run local optimization when a new best is found (Algorithm 1, §2).
pub fn lo_ransac_step<M, P, L: LocalOptimizer<M, P>>(
    sample_model: M,
    points: &[P],
    theta: f64,
    residual: impl Fn(&M, &P) -> f64,
    best_inliers: usize,
    optimizer: &L,
) -> Option<(M, Vec<usize>)> {
    let inliers: Vec<usize> = points
        .iter()
        .enumerate()
        .filter(|(_, p)| residual(&sample_model, p) <= theta)
        .map(|(i, _)| i)
        .collect();

    if inliers.len() <= best_inliers {
        return None; // not a new best; no local optimization invoked
    }

    // New best: invoke local optimization (bounded to O(log k) calls per run).
    let refined = optimizer
        .refine(&sample_model, points, &inliers, theta)
        .unwrap_or(sample_model);
    Some((refined, inliers))
}

Remarks

• Reported speed-up is "two to three fold" with 10–20% more inliers than standard RANSAC across five two-view-geometry experiments.
• Method 5's efficiency ratio (actual samples over the theoretically expected count) is close to 1.0 — for example 1.01 on one experiment and 1.16 on another — against standard RANSAC's 2.63–3.35 on the same experiments.
• Local optimization is invoked at most $O(\log k)$ times per run; the empirical invocation count stays below the $\log k$ bound across all tested experiments and methods.
• Non-iterative re-fitting alone (methods 2 and 4) underperforms its iterative counterpart (methods 3 and 5, respectively) with no compensating time saving.
• Method 5's inner resampling is a liability when the inlier fraction is high and the total correspondence count is low, since resampling cost then dominates; method 3 was faster in that regime in one of the five reported experiments.
• The modification "makes no new assumptions about the data" and is explicitly compatible with (not competing against) other RANSAC extensions such as MLESAC, R-RANSAC, and NAPSAC; see ransac for the four design axes that organise the modern RANSAC family. USAC incorporates LO-RANSAC's local optimization as its pluggable stage-4 module (see raguram-usac).

When to choose LO-RANSAC over MAGSAC

MAGSAC removes the need to tune a fixed inlier threshold $\theta$ by marginalising the RANSAC quality function over an unknown noise scale $\sigma \in [0, \sigma_\mathrm{max}]$, at the cost of $d = 10$ per-hypothesis model re-fits in its $\sigma$-consensus loop. LO-RANSAC keeps a fixed, user-supplied threshold $\theta$ and instead spends its extra cost on at most $O(\log k)$ local-optimization refits per run. MAGSAC's own applicability note names LO-RANSAC directly as the faster alternative "for tight-threshold well-calibrated setups" and reports it is the slowest method of those compared when the noise level is low ($\sigma < 0.3$ px), because $\sigma$-consensus runs on every minimal-sample model rather than only the current best.

Choose LO-RANSAC when the inlier threshold is well-calibrated for the imagery and stable across the dataset, when the scene noise level is low enough that $\sigma$-consensus's per-hypothesis overhead is not worth paying, or when no extra input beyond a single scalar threshold is available to tune. Choose MAGSAC when the inlier threshold is unknown or varies scene-to-scene, when geometric accuracy on real data is the primary metric, or when the outlier ratio is high enough that $\sigma$-consensus's iteration-count reduction outweighs its per-hypothesis cost.

References

1. O. Chum, J. Matas, J. Kittler. Locally Optimized RANSAC. DAGM 2003 (Lecture Notes in Computer Science). PDF
2. M. A. Fischler, R. C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Communications of the ACM, 1981. dl.acm.org
3. R. Raguram, O. Chum, M. Pollefeys, J. Matas, J.-M. Frahm. USAC: A Universal Framework for Random Sample Consensus. IEEE TPAMI, 2013. ieeexplore.ieee.org
4. D. Barath, J. Matas, J. Noskova. MAGSAC: Marginalizing Sample Consensus. CVPR, 2019. arxiv.org