PROSAC (Progressive Sample Consensus)

This documentation was generated with the assistance of AI. Please report any inaccuracies.

RANSAC treats every sample as equally likely to be an inlier and draws subsets uniformly at random from the whole dataset. Very often, though, a rough quality score is already available for each sample — a descriptor-matching similarity, a correlation score — that, while far from perfect, is at least somewhat correlated with whether that sample is actually an inlier. PROSAC exploits this ordering to draw its random subsets from progressively larger pools of the best-scoring samples first, converging to plain RANSAC in the worst case but often finding the same answer one to two orders of magnitude faster. It is described in Chum and Matas, 2005, and implemented as PROSACRobustEstimator in the com.irurueta.numerical.robust package. This library’s implementation is itself explicitly modeled on a reference C implementation by Frédéric Devernay, cited directly in the class’s source code.

Notation

Sort the samples in descending order by quality, so denotes the full sorted set and the subset of its highest-quality samples. A sample (subset) of size has quality equal to its worst member: .

The growth function

Imagine RANSAC drawing uniformly random subsets of size , and re-ordering that same sequence of subsets by their quality, best first. PROSAC’s insight is that this re-ordered sequence can be generated directly, without ever drawing the "bad" subsets first. Let be the expected number of subsets in that sequence built entirely from :

which satisfies the recurrence:

Since is not generally an integer, an integer running counter tracks it (starting from ):

and the growth function — how large a pool should be sampled from after trials — is defined as the smallest whose has not yet been reached:

At trial , the drawn subset always includes the sample at the current growth boundary, , plus other samples drawn at random from within — until the growth boundary reaches the maximality-based termination length described below, at which point PROSAC falls back to drawing all points uniformly from , exactly like plain RANSAC.

flowchart TD A["t = 0, n = m, sample-size-star = N;\ncompute initial T_n, T'_n = 1"] --> B["t = t + 1"] B --> C{"t > T'_n and n has not reached\nsample-size-star yet?"} C -->|"yes"| D["Grow the pool: n = n + 1;\nupdate T_n, T'_n via the recurrence"] C -->|"no"| E{"t > T'_n ?"} D --> E E -->|"yes (finishing stage)"| F["Draw m points uniformly from U_n\n(standard RANSAC sampling)"] E -->|"no"| G["Draw m-1 points from U_(n-1) at random,\nplus the boundary point u_n"] F --> H["Fit candidate model(s); verify against ALL N samples"] G --> H H --> I["Update the termination length n*\nif a better inlier ratio was found (see below)"] I --> J{"stopping criteria satisfied\n(non-randomness and maximality)?"} J -->|"no"| B J -->|"yes"| K["Return the best model found"]

Stopping criteria

PROSAC stops once the current best solution, found within a pool with inliers, satisfies two conditions simultaneously.

Non-randomness

The number of "inliers" a wrong model could accumulate purely by chance follows a binomial distribution , where is the (problem-specific) probability that an incorrect model happens to be consistent with an arbitrary sample. Approximating this binomial with a normal distribution gives a minimum inlier count below which a result cannot be trusted:

using a chi-squared value of (corresponding to a two-tailed significance level of 10%, or a one-tailed as in the original paper). A solution is only accepted once .

Maximality

Exactly as in RANSAC's own confidence-based termination, the number of samples needed to be reasonably sure (probability , typically 5%) that no better solution exists is:

At every improvement, PROSAC additionally searches over all possible pool sizes for whichever one minimizes (i.e. maximizes the inlier ratio ) while still satisfying the non-randomness test above, and adopts that as the new termination length — this is why the algorithm can stop having sampled from a smaller, higher-quality prefix of the data than the full , rather than only ever expanding outward.

Library implementation

PROSACRobustEstimator<T> requires a PROSACRobustEstimatorListener<T>, which extends RANSACRobustEstimatorListener<T> (see Robust Estimation Framework) with one addition:

  • getQualityScores() — one score per sample, where a larger value means higher quality; the estimator sorts samples by this internally.

Beyond the shared getConfidence() / setConfidence(double) and getMaxIterations() / setMaxIterations(int) described in Robust Estimation Framework, PROSAC-specific tuning is available via:

  • getMaxOutliersProportion() / setMaxOutliersProportion(double) — the assumed worst-case outlier fraction, used to compute (the point at which PROSAC’s sampling becomes identical to RANSAC’s); default 0.8.

  • getEta0() / setEta0(double) — the maximality significance level ; default 0.05.

  • getBeta() / setBeta(double) — the non-randomness parameter ; default 0.01. This is problem-specific and, per Chum and Matas, 2005, should be estimated from geometric considerations about the specific model being fit.

After estimate() completes, getBestResult() and getBestInliersData() (a PROSACInliersData) behave the same as in RANSAC (Random Sample Consensus).

The quality scores do not need to be an accurate probability of correctness — only "not worse than random," i.e. on average, a higher-quality sample should be at least as likely to be an inlier as a lower-quality one. Chum and Matas, 2005 found this mild assumption to hold for several standard similarity measures across a range of test scenes, with observed speedups over RANSAC of up to two orders of magnitude.

Example

The same line-fitting problem as RANSAC (Random Sample Consensus), now with a per-point quality score (e.g. a matching score from whatever process produced the candidate points) guiding the sampling:

final var listener = new PROSACRobustEstimatorListener<double[]>() {
    @Override
    public int getTotalSamples() {
        return xCoords.length;
    }

    @Override
    public int getSubsetSize() {
        return 2;
    }

    @Override
    public double getThreshold() {
        return 1.0;
    }

    @Override
    public double[] getQualityScores() {
        return qualityScores; // higher = better, one entry per sample
    }

    @Override
    public void estimatePreliminarSolutions(final int[] samplesIndices, final List<double[]> solutions) {
        final var x1 = xCoords[samplesIndices[0]];
        final var y1 = yCoords[samplesIndices[0]];
        final var x2 = xCoords[samplesIndices[1]];
        final var y2 = yCoords[samplesIndices[1]];

        final var b = (y2 - y1) / (x2 - x1);
        final var a = y1 - b * x1;
        solutions.add(new double[]{a, b});
    }

    @Override
    public double computeResidual(final double[] currentEstimation, final int i) {
        final var a = currentEstimation[0];
        final var b = currentEstimation[1];
        return Math.abs(yCoords[i] - (a + b * xCoords[i]));
    }
};

final var estimator = new PROSACRobustEstimator<>(listener);
estimator.setConfidence(0.99);
final var line = estimator.estimate(); // [a, b], typically found much faster than plain RANSAC