The RANSAC (Random Sample Consensus) algorithm is a robust estimation method used to fit a model to data that contains a significant number of outliers. Its primary purpose is to estimate parameters of a mathematical model from a dataset that is contaminated by outliers, when standard estimation techniques (like least squares) would fail or produce poor results. A single outlier can drastically skew the result of a least-squares fit. RANSAC’s genius is that it doesn’t try to fit all the points. Instead, it seeks to find the best model that explains the inliers.
How It Works (The Intuition)
The algorithm is based on a simple but powerful iterative process:
- Randomly select the smallest number of points required to define your model (e.g., 2 points for a line, 3 points for a circle).
- Fit a model to this small, randomly chosen subset.
- Test all other data points against this model. Points that fit the model well within a pre-defined error tolerance are considered part of the “consensus set” (inliers).
- Repeat steps 1-3 many times. The model with the largest consensus set (most inliers) is considered the best.
- Re-fit the final model using all the inliers from the best consensus set to improve the estimate.
Using the minimum number of points makes each candidate model sensitive to noise, which creates a variance problem. Two noisy points can give a poor estimate of a line; fitting more inlier points at step 1 would usually give a more reliable estimate.But RANSAC does not yet know which points are inliers. The more points you select, the greater the chance of including an outlier and spoiling the candidate model.
Key Parameters
- Error Tolerance: How close a point must be to the model to be considered an inlier.
For early stopping, we also require
- Number of Iterations: How many random samples to try. This is chosen to ensure a high probability that at least one sample is free of outliers.
- Inlier Threshold: The minimum number of inliers required for a model to be considered good.
Early stopping means ending RANSAC before reaching its maximum allowed number of iterations because a sufficiently good model has already been found. For example, suppose we allow 1,000 iterations, but decide that a model fitting at least 90 of our 100 points is good enough. If such a model appears at iteration 80, we stop there and refit it using its inliers. Thus, in your list, Number of Iterations is the stopping limit; the minimum inlier count provides a possible early-stopping condition. Stopping early saves computation, but does not guarantee that a later iteration would not find a better model.
Common Applications
RANSAC is ubiquitous in computer vision and data analysis:
- Image Stitching (Panorama Creation): Finding overlapping keypoints between images to compute the homography matrix. Many keypoint matches are incorrect, so RANSAC is essential to find the correct geometric transformation.
- 3D Point Cloud Registration: Aligning two 3D scans by finding the best rigid transformation (rotation and translation). The algorithm must be robust to noise and non-overlapping regions.
- Fundamental Matrix Estimation in Stereo Vision: Estimating the epipolar geometry between two camera views, where many feature correspondences may be erroneous.
- Line/Circle/Shape Detection: Extracting geometric primitives from noisy sensor data (e.g., from LIDAR or edge detectors).
Note: RANSAC is very similar to non-maximum supression.