Random sample consensus: Difference between revisions

Revision as of 04:48, 13 November 2024

Revision as of 04:57, 13 November 2024

Line 15:

==Overview==

The RANSAC algorithm is a learning technique to estimate parameters of a model by random sampling of observed data. Given a dataset whose data elements contain both inliers and outliers, RANSAC uses the voting scheme to find the optimal fitting result. Data elements in the dataset are used to vote for one or multiple models. The implementation of this voting scheme is based on two assumptions: that the noisy features will not vote consistently for any single model (few outliers) and there are enough features to agree on a good model (few missing data). The RANSAC algorithm is essentially composed of two steps that are iteratively repeated:

# In the first step, aA sample subset containing minimal number of data items is randomly selected from the input dataset. A fitting model with model parameters is computed using only the elements of this sample subset. The cardinality of the sample subset (e.g., the amount of data in this subset) is sufficient to determine the model parameters.

# In the second step, theThe algorithm checks which elements of the entire dataset are consistent with the model instantiated by the estimated model parameters obtained from the first step. A data element will be considered as an outlier if it does not fit the model within some error threshold defining the maximum data deviation of inliers. (Datadata elements beyond this deviation are outliers.).

The set of inliers obtained for the fitting model is called the ''consensus set''. The RANSAC algorithm will iteratively repeat the above two steps until the obtained consensus set in certain iteration has enough inliers.

The input to the RANSAC algorithm is a set of observed data values, a model to fit to the observations, and some [[confidence interval|confidence]] parameters defining outliers. In more details than the aforementioned RANSAC algorithm overview, RANSAC achieves its goal by repeating the following steps:

# Select a random subset of the original data. Call this subset the ''hypothetical inliers''.

# A model is fitted to the set of hypothetical inliers.

Line 29 ⟶ 28:

To converge to a sufficiently good model parameter set, this procedure is repeated a fixed number of times, each time producing either the rejection of a model because too few points are a part of the consensus set, or a refined model with a consensus set size larger than the previous consensus set.

[[File:RANSAC Inliers and Outliers.png|thumb|center|500px|RANSAC: Inliersinliers and Outliersoutliers. The linear fitting to data points in this example is with 7 inliers (data points fitted well with the model under some criteria). It is not a good fitting, since there is a linear line where most data points are distributed near it (i.e., more inliers).]]

<gallery widths="286" heights="255" perrow="2">

File:RANSAC Inliers and Outliers.png|RANSAC: Inliers and Outliers. The linear fitting to data points in this example is with 7 inliers (data points fitted well with the model under some criteria). It is not a good fitting since there is a linear line where most data points are distributed near it (i.e., more inliers).

</gallery>

== Pseudocode ==