RANSAC
- Also called: Random Sample Consensus
- Category: Sensing › Perception outputs
- Tags: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus: a robust fitting method that repeatedly fits a model to small random subsets of the data and keeps the model that agrees with the most points, ignoring outliers.
Definition
RANSAC (Random Sample Consensus), introduced by Fischler and Bolles in 1981, estimates the parameters of a model from data that contain many outliers. Least-squares fitting uses every point, so a few gross errors can pull the result far from the truth. RANSAC instead repeats a simple loop: draw the minimum number of points needed to define the model (two for a line, three for a plane, a small fixed number for a camera pose or a fundamental matrix), fit the model to them, and count how many of all the data points lie within a threshold of it. Those points are the consensus set, or inliers. After a number of iterations, the model with the largest consensus set is kept and is usually refit to all of its inliers by least squares.
The number of iterations follows from probability. If w is the fraction of inliers and s the sample size, a random sample contains only inliers with probability wˢ, so the number of iterations k needed to draw at least one clean sample with confidence p is k = log(1 − p) / log(1 − wˢ). This grows quickly as the inlier fraction falls or the sample size rises, which is why minimal solvers that need fewer points, such as five-point relative pose, matter in vision. The inlier threshold is the other key parameter: it should match the expected noise of true inliers and must be set in the units of the residual being measured.
Many variants improve on the basic loop. MSAC and MLESAC score hypotheses with a robust cost rather than a raw inlier count, PROSAC samples the most promising matches first, LO-RANSAC locally refines good hypotheses, and adaptive versions update k as the inlier fraction is estimated. In robotics, RANSAC is used for plane and primitive segmentation in point clouds, feature-match filtering in visual odometry and SLAM, Perspective-n-Point pose estimation, point-cloud registration from feature correspondences, and calibration. Because the procedure is random, results can differ between runs unless the random seed is fixed.
Why it matters
Real sensor data are full of outliers: wrong feature matches, reflections, moving objects and points belonging to other surfaces. RANSAC is the standard way to fit geometric models despite them, and it sits inside most visual odometry, SLAM, calibration and point-cloud segmentation pipelines.
Key applications
- Plane, cylinder and sphere segmentation in point clouds
- Outlier rejection for feature matches in visual odometry and SLAM
- Camera pose estimation with Perspective-n-Point
- Estimating fundamental, essential and homography matrices
- Global point-cloud registration from feature correspondences
- Fitting lines and calibration models to noisy sensor data
In practice
A mobile manipulator needs to find a table top in a depth-camera point cloud before placing objects. The software downsamples the cloud and runs RANSAC plane fitting: it repeatedly picks three points, computes the plane through them, and counts the points within a distance threshold set slightly above the sensor's depth noise. The plane with the most inliers is refit by least squares, its inliers are removed, and the remaining points above it are clustered into objects. Engineers check that the plane's normal points roughly upward, because with a large wall or floor in view RANSAC may return that surface instead, and they fix the random seed in tests so results are repeatable.
Common misconceptions
- RANSAC finds the optimal model — it returns the best hypothesis it happened to sample, so results are probabilistic and can differ between runs
- More iterations make up for a poor threshold — the threshold decides what counts as agreement, and a bad choice biases the result however many iterations are run
- RANSAC copes with any proportion of outliers — the required iterations grow rapidly as the inlier fraction drops, and with very few inliers it can fail or lock onto a spurious structure
- RANSAC can only find one model — the basic algorithm finds one, but sequential and multi-model variants extract several structures by removing inliers and repeating
Who should know this
- Perception and computer-vision engineers
- SLAM and visual-odometry developers
- Engineers processing point clouds for manipulation
- Calibration and metrology engineers
Related technologies
- Least-Squares Fitting
- M-Estimators
- MSAC and MLESAC
- PROSAC
- Hough Transform
- Point Cloud Library
Related terms
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
Related projects
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
Videos
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision