Random sample consensus: Difference between revisions

Revision as of 00:54, 6 March 2023

Revision as of 23:59, 7 March 2023

Line 179:

The threshold value to determine when a data point fits a model ({{mvar|t}}), and the number of inliers (data points fitted to the model within ''t'') required to assert that the model fits well to data ({{mvar|d}}) are determined based on specific requirements of the application and the dataset, and possibly based on experimental evaluation. The number of iterations ({{mvar|k}}), however, can be roughly determined as a function of the desired probability of success ({{mvar|p}}) as shown below.

Let {{mvar|p}} be the desired probability that the RANSAC algorithm provides at least one useful result after running. In extreme (for simplifying the derivation), RANSAC returns a successful result if in some iteration it selects only inliers from the input data set when it chooses {{mvar|n}} points from the data set from which the model parameters are estimated. (i.e.In other words, all the selected {{mvar|n}} data points asare inliers of the model estimated by these points). Let <math>w</math> be the probability of choosing an inlier each time a single data point is selected, that is roughly,

:<math>w</math> = number of inliers in data / number of points in data

A common case is that <math>w</math> is not well known beforehand because of an unknown number of inliers in data before running the RANSAC algorithm, but some rough value can be given. With a given (rough) value of <math>w</math>, and roughly assuming that the {{mvar|n}} points needed for estimating a model are selected independently (It is a rough assumption because each data point selection reduces the number of data point candidates to choose in the next selection in reality), <math>w^{n}</math> is the probability that all ''n'' points are inliers and <math>1 - w^{n}</math> is the probability that at least one of the {{mvar|n}} points is an outlier, a case which implies that a bad model will be estimated from this point set. That probability to the power of {{mvar|k}} (the number of iterations in running the algorithm) is the probability that the algorithm never selects a set of {{mvar|n}} points which all are inliers, and this is the same as <math>1 - p</math> (the probability that the algorithm does not result in a successful model estimation) in extreme. Consequently,

:<math>