Random Sample Consensus

Repeatedly fitting a model to small random subsets of data and keeping the one most data points agree with, to reject outliers.

Random Sample Consensus (RANSAC) was proposed by Fischler and Bolles at SRI in 1981. Real-world data is often mixed with a large number of wrong points (outliers), and fitting directly with least squares gets skewed by them. RANSAC instead randomly draws the minimum number of samples needed to fit the model (for example, 3 points to fit a plane) and computes a candidate model; counts how many data points fall within an error threshold of it (inliers); repeats this many times and keeps the model with the most inliers; and finally refines that model once more using all of its inliers. It is a foundational tool in computer vision, commonly used to estimate a homography or fundamental matrix after feature matching, to solve for camera pose together with PnP, and to do coarse alignment before point cloud registration. In a robot tabletop scene, it is often used first to fit and remove the tabletop plane, leaving only the points belonging to objects on the table.

ExampleRunning RANSAC plane-fitting on an RGB-D point cloud finds and removes the tabletop; clustering what remains then yields the individual objects sitting on it.

Also called

RANSAC, RANSAC Algorithm

Related

Feature Matching · Homography · Perspective-n-Point · Point Cloud Registration · Epipolar Geometry · Point Cloud Segmentation

Sources

Random sample consensus - Wikipedia