RANSAC Consensus Line Fitting

Random Sample Consensus (RANSAC) is an iterative method used to estimate parameters of a mathematical model from a set of observed data that contains outliers. Unlike ordinary least squares which attempts to fit all data points, RANSAC separates the data into inliers and outliers based on a threshold and then fits the model only using the consensus set of inliers.

Worked Example

Consider fitting a line through the "One outlier" dataset with a trial budget of 1 and a residual threshold of 0.25. The first trial pair in the schedule is index 1 and index 2.

The dataset has points: (0,1), (1,3), (2,-4), (3,7), (4,9), (5,11).
Trial 1 selects points at indices 1 and 2: (1,3) and (2,-4).
Calculate the hypothesis line passing through these two points. The slope m = (-4 - 3) / (2 - 1) = -7. The intercept b = 3 - (-7 * 1) = 10. The line is y = -7x + 10.
Evaluate all points against this line with threshold 0.25. We check if |dx*(y - yi) - dy*(x - xi)| <= 0.25 * |dx|, where dx = 1 and dy = -7.
For point (0,1): |1*(1 - 3) - (-7)*(0 - 1)| = |-2 - 7| = 9. This is > 0.25. Outlier.
For point (1,3): |1*(3 - 3) - (-7)*(1 - 1)| = 0. Inlier.
For point (2,-4): |1*(-4 - 3) - (-7)*(2 - 1)| = |-7 + 7| = 0. Inlier.
For point (3,7): |1*(7 - 3) - (-7)*(3 - 1)| = |4 + 14| = 18. Outlier.
The total inlier count is 2. The consensus set is the two sampled points themselves.
We refit using these two inliers. Since it's exactly two points, the refitted line is the same: y = -7x + 10.

Experiment

Open the RANSAC Consensus Line Fitting module and verify the behavior of the deterministic consensus approach.

Select the Dataset to "One outlier".
Set the Residual threshold to 0.25 and the Trial budget to 1. Notice that the resulting refit slope is -7, matching our manual calculation.
Increase the Trial budget to 6. The algorithm now tests more hypotheses, finding the true underlying line supported by the 5 clean points, resulting in a slope of 2.

Limitations

This module uses a frozen pedagogical schedule of predetermined unordered pairs to make the trials deterministic and repeatable. In a real application, RANSAC relies on random sampling, providing a probabilistic guarantee of finding a good model if one exists, which depends on the proportion of inliers and the number of trials. Additionally, RANSAC's strict binary inlier/outlier classification based on a hard threshold differs from robust continuous regression techniques like Huber loss, which apply a continuous penalty to outliers instead of ignoring them completely.

References

For further reading on robust regression using the RANSAC algorithm and its implementation, see the scikit-learn documentation.

scikit-learn RANSACRegressor Documentation

RANSAC Consensus Line Fitting