RANSAC

What it computes

Least squares fits a model to all the data, so a few wild points can drag it anywhere. RANSAC (random sample consensus) is built for data full of outliers: it finds the model that the largest number of points agree with, and ignores the rest.

The algorithm

A plane needs only three points. So:

best = none
repeat iters times:
    pick 3 random points a, b, c
    n = (b - a) x (c - a), normalised    # skip if the points are in a line
    d = -n . a                           # the plane n . p + d = 0
    inliers = |points . n + d| < threshold
    keep (n, d, inliers) if it has more inliers than best
refit n, d to best's inliers with least squares

For the refit, centre the inliers on their mean $\bar p$. The normal is then the direction of least spread: the last row of $V^T$ from np.linalg.svd(inliers - p_mean). Finally $d = -n \cdot \bar p$.

How many iterations? If a fraction $w$ of the points are inliers, one sample is all-inlier with probability $w^3$. After $k$ tries you miss every time with probability $(1 - w^3)^k$. For $w = 0.6$, 200 tries miss with probability below $10^{-10}$.

The program

The camera on its stand has been bumped to an unknown pose. The program turns its depth image into 3-D points in the camera's frame, and adds 2 mm of noise, as a real depth sensor would. Most of the points are table; the rest are balls, the cup, the floor and the robot. Your plane gives the camera's height ($|d|$) and its tilt from vertical, and your inliers are shown in the Images tab.

Your task

Implement ransac_plane(points, threshold, iters). It returns (n, d, inliers): a unit normal, an offset, and a boolean mask with one entry per point. The grader also runs it on three synthetic clouds with 40% outliers.