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 the presence of outliers. It is a nondeterministic algorithm (FB81) based on the random selection of the elements generating 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$ sufficiently large to recover a model (the hypothesis). Once a hypothesis has been obtained, the number of the $n$ elements of $X$ sufficiently close to it to belong to it is counted. A sample $\mathbf{x} \in S$ belongs or does not belong to the hypothetical model (that is, it is a hypothetical inlier or outlier) if its distance from the model $d_{\boldsymbol\beta} (\mathbf{x})$ is below or above a given threshold $\tau$, which normally depends on the problem. The threshold $\tau$ poses a problem in practical cases 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 the inliers in order to define a threshold $\tau$.

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

The set of consensus elements $S$ associated with the 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.127)

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

One problem is determining how many hypotheses to generate in order to have a good 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 only 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.128)

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

Normally, $P=(1 - \epsilon)^{s}$ can be used as an approximation of $P$^4.3, and therefore

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

where $\epsilon$ is the a priori 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 supplied 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_inline15694#^4.3

The correct 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.