RANSAC

The RANdom Sample And Consesus algorithm is an iterative algorithm for estimating the parameters of a model when the data set is strongly affected by outliers; algorithm (FB81) is nondeterministic and based on the random selection of the elements that generate the model.

RANSAC and all its variants can be viewed as algorithms that iteratively alternate between two phases: hypothesis generation and hypothesis evaluation.

In brief, the algorithm consists of randomly selecting $s$ samples from all $n$ input samples $X=\{\mathbf{x}_1 , \ldots, \mathbf{x}_n \}$, with $s$ large enough to determine a model (the hypothesis). Once a hypothesis has been obtained, the number of $n$ elements of $X$ that are sufficiently close to it to belong to it is counted. A sample $\mathbf{x} \in S$ belongs or does not belong to the hypothesized model (that is, it is a hypothesized inlier or outlier) according to whether its distance from model $d_{\boldsymbol\beta} (\mathbf{x})$ is below or above a given threshold $\tau$, which normally depends on the problem. The threshold $\tau$ presents a difficulty in practical problems where the additive error is Gaussian, that is, where the support is infinite. In this case, it is nevertheless necessary to define a probability $p$ of detecting inliers in order to define a threshold $\tau$.

All samples satisfying the hypothesis are called consensus samples (consensus).

The set of consensus samples $S$ associated with hypothesis $\boldsymbol\beta$ is the consensus set of $\boldsymbol\beta$:

$$S(\boldsymbol\beta) = \left\{ \mathbf{x} \in X : d_{\boldsymbol\beta} (\mathbf{x}) < \tau \right\}$$ (4.132)

Among all randomly generated models, the model satisfying a given metric is selected; in the original RANSAC, for example, this is the model with the largest consensus-set cardinality.

One problem is determining how many hypotheses to generate in order to have a high probability of obtaining the correct model.

There is a statistical relationship between the number of iterations $N$ and the probability $p$ of finding a solution consisting entirely of inliers. The number of trials $N$ must satisfy $(1 - P)^N \le 1 - p$, that is,

$$N \ge \frac{\log (1 - p) }{\log(1 - P)}$$ (4.133)

where $P$ is the probability that a solution consisting entirely of inliers has been selected.

Normally, $P$ can be approximated by $P=(1 - \epsilon)^{s}$^4.4, and therefore

$$N = \frac{ \log ( 1 - p ) } { \log ( 1 - (1 - \epsilon)^{s} ) }$$ (4.134)

where $\epsilon$ is the prior probability of selecting an outlier and $s$ is the number of elements required to define the model. The size of a minimum consensus set can be statistically inferred simply as $T = (1 - \epsilon) n$.

Normally, $s$ is chosen to be equal to the number of elements required to create the model. However, if it is larger than this number, the generated model must be constructed through numerical regression with respect to the given constraints. This is necessary when the noise variance is high, although it increases the risk of including outliers among the elements satisfying the constraints.

Footnotes

...#tex2html_wrap_inline15696#^4.4

The exact estimate is $P=\frac{\binom{pn}{s}}{\binom{n}{s}}$, where $pn$ is the total number of inliers, $n$ is the total number of elements, and $s$ is the number of elements required.