mathematics//statistics//robust statistics//RANSAC

RANSAC (random sample consensus) is a robust fitting algorithm that fits a model to many small random subsets of the data and keeps the fit that the largest number of points agree with, and it is the standard way to find a plane in a lidar point cloud, a line in an edge image or the geometry between two camera views when a large share of the data belongs to something else. It takes the data, a model with its minimal number of points (three for a plane), a distance tolerance and a number of tries; it returns the model and the list of points that fit it, the **inliers**.

RANSAC (random sample consensus) is a robust fitting algorithm that fits a model to many small random subsets of the data and keeps the fit that the largest number of points agree with, and it is the standard way to find a plane in a lidar point cloud, a line in an edge image or the geometry between two camera views when a large share of the data belongs to something else. It takes the data, a model with its minimal number of points (three for a plane), a distance tolerance and a number of tries; it returns the model and the list of points that fit it, the inliers.

The loop is short. Pick the minimal subset at random, fit the model to it exactly, count how many of all the points lie within the tolerance, and remember the best count; after enough tries, refit by least squares on the inliers of the winner. A lidar scan of a warehouse floor with pallets, legs and people on it is the everyday picture: least squares on all points tilts the ground plane toward the obstacles, while three points drawn from the floor produce a plane that thousands of other floor points confirm, and no obstacle-based plane comes close to that consensus.

The number of tries follows from probability. If a share www of the points are inliers and each try draws sss points, the chance that one try is all-inlier is wsw^sws, and to succeed with probability ppp one needs

N=log⁡(1−p)log⁡ ⁣(1−ws).N=\frac{\log(1-p)}{\log\!\left(1-w^{s}\right)} .N=log(1−ws)log(1−p)​.

For a plane (s=3s=3s=3) with half the points on it and p=0.99p=0.99p=0.99, N≈35N\approx35N≈35 tries; with a fifth on it, about 570.

It survives what other robust methods do not. The median and the Huber loss of robust statistics fail once outliers approach half the data; RANSAC can find a structure supported by a minority, as long as no other structure has more support.

The tolerance is the real tuning knob. Too tight and good points are rejected as noise; too loose and a nearby box joins the floor. It is set from the sensor's noise (a few centimetres for a typical lidar), and the cost grows quickly with sss and with the outlier share.

Several structures are found by repetition: remove the inliers of the floor and run again for a wall. Point cloud libraries ship it ready to use (Open3D's segment_plane), and it runs in the perception stack of most mobile robots.