RANSAC

Line estimation with RANSAC – Wikipedia Image

Ransac is a technique for estimating a mathematical model from a set of data, as might be the method of least squares. The latter works well if all the data are very close to the expected pattern. However, if there are outliers in the data, they are going to disturb the estimation of the model.

Ransac works as follows (the indications for estimating a straight line are in italics):

  1. n points are randomly selected. 2 points are enought for a line estimation.
  2. The mathematical model est computed from the set. The slope of the line is computed with this two points.
  3. The others points are tested, in order to see how many of them confirm the model. Concretely, the distance between a point and the model is computed. If the distance is less than a fixed threshold, then the point validates the model. The nuber of validating points is saved.
  4. If there are enough points, the model is validated. Else, we go back to part 1).

Once the model is validated, it can be refined by using least square because there are no outliers anymore.

RANSAC can be used in order to estimate 2D or 3D transformations.

Here is an illustration of the estimation of a 2D transformation (rotation, translation and zoom) by using matching points :

Ransac
Matching points. The inliers found with RANSAC are draw in red.

The C# source code is available here : Ransac.