Random sample consensus (RANSAC) is an iterative method to estimate parameters of a mathematical model from a set of observed data that contains outliers, when outliers do not affect the values of the estimates. Therefore, it also can be interpreted as an outlier detection method. It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at SRI International in 1981. They used RANSAC to solve the location determination problem (LDP), where the goal is to determine the points in the space that project onto an image into a set of landmarks with known locations.
RANSAC uses repeated random sub-sampling. A basic assumption is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, though may be subject to noise, and "outliers", which are data that do not fit the model. The outliers can come, for example, from extreme values of the noise or from erroneous measurements or incorrect hypotheses about the interpretation of data. RANSAC also assumes that, given a (usually small) set of inliers, there exists a procedure that can estimate the parameters of a model optimally explaining or fitting this data.
Example A simple example is fitting a line in two dimensions to a set of observations. Assuming that this set contains both inliers, i.e., points which approximately can be fitted to a line, and outliers, points which cannot be fitted to this line, a simple least squares method for line fitting will generally produce a line with a bad fit to the data including inliers and outliers. The reason is that it is optimally fitted to all points, including the outliers. RANSAC, on the other hand, attempts to exclude the outliers and find a linear model that only uses the inliers in its calculation. This is done by fitting linear models to several random samplings of the data and returning the model that has the best fit to a subset of the data. Since the inliers tend to be more linearly related than a random mixture of inliers and outliers, a random subset that consists entirely of inliers will have the best model fit. In practice, there is no guarantee that a subset of inliers will be randomly sampled, and the probability of the algorithm succeeding depends on the proportion of inliers in the data as well as the choice of several algorithm parameters.
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: A 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 (i.e., the amount of data in this subset) is sufficient to determine the model parameters. The 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 (data 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 a 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 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. All data are then tested against the fitted model. All the data points (of the original data) that fit the estimated model well, according to some model-specific loss function, are called the consensus set (i.e., the set of inliers for the model). The estimated model is reasonably good if sufficiently many data points have been classified as a part of the consensus set. The model may be improved by re-estimating it by using all the members of the consensus set. The fitting quality as a measure of how well the model fits to the consensus set will be used to sharpen the model fitting as iterations goes on (e.g., by setting this measure as the fitting quality criteria at the next iteration).
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.
Pseudocode
The generic RANSAC algorithm works as the following pseudocode:
Given: data – A set of observations. model – A model to explain the observed data points. n – The minimum number of data points required to estimate the model parameters. k – The maximum number of iterations allowed in the algorithm. t – A threshold value to determine data points that are fit well by the model (inlier). d – The number of close data points (inliers) required to assert that the model fits well to the data.
Return: bestFit – The model parameters which may best fit the data (or null if no good model is found).
iterations = 0 bestFit = null bestErr = something really large // This parameter is used to sharpen the model parameters to the best data fitting as iterations go on.
while iterations < k do maybeInliers := n randomly selected values from data maybeModel := model parameters fitted to maybeInliers confirmedInliers := empty set for every point in data do if point fits maybeModel with an error smaller than t then add point to confirmedInliers end if end for if the number of elements in confirmedInliers is > d then // This implies that we may have found a good model. // Now test how good it is. betterModel := model parameters fitted to all the points in confirmedInliers thisErr := a measure of how well betterModel fits these points if thisErr < bestErr then bestFit := betterModel bestErr := thisErr end if end if increment iterations end while
return bestFit
Example code
A Python implementation mirroring the pseudocode. This also defines a LinearRegressor based on least squares, applies RANSAC to a 2D regression problem, and visualizes the outcome:
from copy import copy import numpy as np from numpy.random import default_rng rng = default_rng()
class RANSAC: def __init__(self, n=10, k=100, t=0.05, d=10, model=None, loss=None, metric=None): self.n = n # `n`: Minimum number of data points to estimate parameters self.k = k # `k`: Maximum iterations allowed self.t = t # `t`: Threshold value to determine if points are fit well self.d = d # `d`: Number of close data points required to assert model fits well self.model = model # `model`: class implementing `fit` and `predict` self.loss = loss # `loss`: function of `y_true` and `y_pred` that returns a vector self.metric = metric # `metric`: function of `y_true` and `y_pred` and returns a float self.best_fit = None self.best_error = np.inf
def fit(self, X, y) -> Self: for _ in range(self.k): ids = rng.permutation(X.shape)
maybe_inliers = ids[: self.n] maybe_model = copy(self.model).fit(X[maybe_inliers], y[maybe_inliers])
thresholded = ( self.loss(y[ids][self.n :], maybe_model.predict(X[ids][self.n :])) < self.t )
inlier_ids = ids[self.n :][np.flatnonzero(thresholded).flatten()]
if inlier_ids.size > self.d: inlier_points = np.hstack([maybe_inliers, inlier_ids]) better_model = copy(self.model).fit(X[inlier_points], y[inlier_points])
this_error = self.metric( y[inlier_points], better_model.predict(X[inlier_points]) )
if this_error < self.best_error: self.best_error = this_error self.best_fit = better_model
return self
def predict(self, X): return self.best_fit.predict(X)
def square_error_loss(y_true, y_pred): return (y_true - y_pred) ** 2
def mean_square_error(y_true, y_pred): return np.sum(square_error_loss(y_true, y_pred)) / y_true.shape
class LinearRegressor: def __init__(self): self.params = None
def fit(self, X: np.ndarray, y: np.ndarray) -> Self: r, _ = X.shape X = np.hstack([np.ones((r, 1)), X]) self.params = np.linalg.inv(X.T @ X) @ X.T @ y return self
def predict(self, X: np.ndarray): r, _ = X.shape X = np.hstack([np.ones((r, 1)), X]) return X @ self.params
if __name__ == "__main__":
regressor = RANSAC(model=LinearRegressor(), loss=square_error_loss, metric=mean_square_error)
X = np.array([-0.848,-0.800,-0.704,-0.632,-0.488,-0.472,-0.368,-0.336,-0.280,-0.200,-0.00800,-0.0840,0.0240,0.100,0.124,0.148,0.232,0.236,0.324,0.356,0.368,0.440,0.512,0.548,0.660,0.640,0.712,0.752,0.776,0.880,0.920,0.944,-0.108,-0.168,-0.720,-0.784,-0.224,-0.604,-0.740,-0.0440,0.388,-0.0200,0.752,0.416,-0.0800,-0.348,0.988,0.776,0.680,0.880,-0.816,-0.424,-0.932,0.272,-0.556,-0.568,-0.600,-0.716,-0.796,-0.880,-0.972,-0.916,0.816,0.892,0.956,0.980,0.988,0.992,0.00400]).reshape(-1,1) y = np.array([-0.917,-0.833,-0.801,-0.665,-0.605,-0.545,-0.509,-0.433,-0.397,-0.281,-0.205,-0.169,-0.0531,-0.0651,0.0349,0.0829,0.0589,0.175,0.179,0.191,0.259,0.287,0.359,0.395,0.483,0.539,0.543,0.603,0.667,0.679,0.751,0.803,-0.265,-0.341,0.111,-0.113,0.547,0.791,0.551,0.347,0.975,0.943,-0.249,-0.769,-0.625,-0.861,-0.749,-0.945,-0.493,0.163,-0.469,0.0669,0.891,0.623,-0.609,-0.677,-0.721,-0.745,-0.885,-0.897,-0.969,-0.949,0.707,0.783,0.859,0.979,0.811,0.891,-0.137]).reshape(-1,1)
regressor.fit(X, y)
import matplotlib.pyplot as plt plt.style.use("seaborn-darkgrid") fig, ax = plt.subplots(1, 1) ax.set_box_aspect(1)
plt.scatter(X, y)
line = np.linspace(-1, 1, num=100).reshape(-1, 1) plt.plot(line, regressor.predict(line), c="peru") plt.show()
Parameters The threshold value to determine when a data point fits a model (), and the number of inliers (data points fitted to the model within t) required to assert that the model fits well to data () are determined based on specific requirements of the application and the dataset, and possibly based on experimental evaluation. The number of iterations (), however, can be roughly determined as a function of the desired probability of success () as shown below.
Let 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 points from the data set from which the model parameters are estimated. (In other words, all the selected data points are inliers of the model estimated by these points). Let be the probability of choosing an inlier each time a single data point is selected, that is roughly,
= number of inliers in data / number of points in data