Table of Contents:

Minimal Solvers

RANSAC

Let P = desired confidence, e.g. 0.99

\[& \epsilon = outlier probability & proportion of inliers p = 1 - \epsilon & P(sample with all inliers) = p^s & P(sample with an outlier) = 1- p^s & P(N samples are all outlier) = (1-p^s)^N\]

We want P(N samples are all outliers) < 1-P

\[(1-p^s)^N &< 1-P \\ log{ (1-p^s)^N } &< log { 1-P } \\ N * log(1-p^s) &< log { 1-P } \\ N &> log(1-P) / log(1-p^s) \\\]

References

  1. Frank Dellaert. “Alignment”. PDF.

  2. Robert Collins. “Robust Estimation : RANSAC”. PDF.