RANSAC: fitting when some points are wrong

This page explains random sample consensus (RANSAC), which fits a line, a plane, a circle or a cylinder to a set of points. It is meant for the case where many of those points belong to something else. It answers four questions, and the first of them is how RANSAC finds the right shape when a third or half of the points are wrong. The other three are how many tries it needs, where a robot arm uses it, and what makes it fail.

It is for a reader who has read the page on least-squares fitting. That page explains parameters, residuals and the root mean square (RMS) residual, and it shows that one bad point can move a least-squares line a long way. This page starts from that problem, and every number on it comes from a real run of the diagram script, docs/diagrams/fitting_and_estimation.py.

RANSAC is the standard way a table-top robot finds the table in a depth camera's point cloud. Although Martin Fischler and Robert Bolles published it as long ago as 1981, it is still the first thing most perception pipelines run on a new point cloud.

Contents#

1. What this page answers
2. The idea in one sentence
3. How it works, step by step · The loop · A worked example: a table edge with stray points · The steps as pseudocode · How many tries are enough · Planes and cylinders in a point cloud · Choosing the distance limit
4. Where it is used on a robot arm
5. Where it is useful, and where it is not
6. Libraries that provide it
7. Why RANSAC, and what it costs
8. The learned alternative
9. Where to read next
10. Using it in Python

1. What this page answers#

Real point clouds are messy, and a depth camera looking at a table shows why. It sees the table, but it also sees the objects standing on it, the edge of the table and the floor beyond. Then there are the false readings, which are scattered points that appear where the light hit a shiny surface. So if you want the table's plane, only some of those points belong to it.

Least squares uses every point, so the other points drag the answer away. You could remove them first, but to know which points to remove you would need to know where the table is, and that is the question you started with.

RANSAC breaks this circle, because it does not need to know in advance which points are good. Instead, it finds the shape and the points that belong to it at the same time. The points that belong to the shape are called inliers, and the rest are called outliers.

2. The idea in one sentence#

Section 1 said that RANSAC finds the shape and its good points at the same time. However, it did not say how, and the answer fits into a single sentence.

Guess the shape from a few randomly chosen points, count how many other points agree with the guess, repeat many times, and keep the guess that most points agree with.

Here is an everyday example, in which a group of people each point at where they think a lost ball landed. Most of them saw it, so they point near the same spot, while a few are guessing and point all over the field. If you take the average of all the pointing directions, the guessers drag it away from the true spot. Instead, you pick one person at random and ask everyone else whether they agree with that person, give or take a metre. If most hands go up, then you have found the spot. But if only two hands go up, you picked a guesser, so you pick someone else and ask again.

The key point is that a guess made only from good points will be agreed with by all the other good points. However, a guess that includes even one bad point will be agreed with by almost nobody. So you do not need to know which points are good. You only need to keep trying until one guess is made entirely from good points.

3. How it works, step by step#

The loop#

Section 2 gave the idea as one sentence, so this section turns that sentence into a loop you could program. RANSAC needs three things from you: the kind of shape, the smallest number of points that defines one such shape, and a distance limit.

• The smallest number of points is 2 for a line, 3 for a plane and 3 for a circle on a table.
• The distance limit says how close a point must be to the shape to count as agreeing with it, so it should be a little larger than the sensor's noise.

Once you have given it those three things, it runs this loop:

1. Pick the smallest number of points at random.
2. Make the one shape that passes exactly through them.
3. Measure every point's distance from that shape, and count the points closer than the distance limit, because those points are this try's inliers.
4. If this try has more inliers than the best try so far, remember it.
5. Repeat from step 1 a fixed number of times.
6. Take the inliers of the best try, and fit the shape to all of them with least squares, so that this last step uses every good point and not just the two or three that were picked.

A worked example: a table edge with stray points#

The example has 55 points in a side view of a table edge, measured in millimetres. Forty of them lie along the edge, whose true line is y = 0.25 x + 20, with 1.5 mm of noise. The other fifteen are stray readings scattered above the edge. So 27% of the points are outliers.

The picture below shows three of the 100 tries RANSAC made, with a distance limit of 4 mm.

Try 1 picked a stray point and an edge point. Its line therefore crosses the edge at an angle, so only 7 points lie within 4 mm of it. Try 3 picked two edge points close together at the right end, and their noise tilts the line a little. So it fits the right part of the edge and misses the left part, which leaves only 20 points agreeing. Try 9 picked two edge points 65 mm apart, so its line follows the whole edge and all 40 edge points agree with it. No try did better than 40, which is why try 9 is the one RANSAC kept.

The final step fits a least-squares line to those 40 inliers, and the picture below compares the result with a least-squares line through all 55 points.

The least-squares line through everything is y = 0.188 x + 34.0. Its offset is therefore 14 mm too high, and its slope is a quarter too shallow. The RANSAC line is y = 0.260 x + 19.1, which is close to the true y = 0.25 x + 20. RANSAC also labelled every one of the 55 points correctly, with the 40 edge points as inliers and the 15 stray points as outliers.

The steps as pseudocode#

function ransac(points, sample_size, distance_limit, tries):
    best_inliers = empty set
    repeat tries times:
        sample = choose sample_size points at random, without repeats
        shape = the shape that passes exactly through sample
        if shape could not be made (for example, the points are on one line):
            continue with the next try
        inliers = every point whose distance to shape < distance_limit
        if size of inliers > size of best_inliers:
            best_inliers = inliers
    final_shape = least-squares fit of the shape to best_inliers
    inliers = every point whose distance to final_shape < distance_limit
    return final_shape, inliers

Two common improvements to this loop are worth knowing, and the first of them stops early. Once a new best try is found, recompute how many tries are needed from the share of inliers just found. The next section gives that formula, and you stop as soon as that many tries have been done. The second improvement, called MSAC, scores each try by how close the agreeing points are, not just how many there are, which breaks ties between guesses more sensibly.

How many tries are enough#

The loop above repeats a fixed number of times, so the next thing to work out is what that number should be. A try succeeds when every point in its sample is an inlier. So if a share w of the points are inliers and a sample has s points, one try succeeds with a chance of w multiplied by itself s times, written wˢ. To be sure, with a chance p such as 99%, that at least one try succeeds, you need this many tries:

tries = log(1 − p) / log(1 − wˢ)

In the worked example, w is 40 out of 55, which is 0.727, and s is 2. So one try succeeds with a chance of 0.53. For 99% certainty the formula gives 6.1, which means 7 tries are enough, and yet the example used 100. That is common in practice, because a line or plane try is cheap, so people use a generous number.

The picture below plots the formula for a line, a plane and a shape that needs 6 points.

The number of tries grows slowly at first and then very fast. For a plane with half the points as outliers, 35 tries are enough. But for a plane with 70% outliers, 168 tries are needed. A shape that needs 6 points, with half the points as outliers, needs 292 tries. This is why RANSAC works best for shapes defined by very few points. It is also why it slows down sharply when the wanted shape is only a small part of the scene.

Planes and cylinders in a point cloud#

A plane needs a sample of only 3 points, so it is one of the cheap shapes in the chart above. This is also the shape a table-top robot wants most often. The plane through those 3 points has a normal, which is the direction at right angles to the plane. Because the three points make a triangle, that normal is equal to the cross product of two edges of the triangle. The cross product is a standard operation that gives the direction at right angles to two other directions. A point's distance from the plane is then the size of its offset from one of the three points, measured along the normal.

The picture below runs RANSAC on a simulated depth camera view of a table with a box and a cup on it, plus 25 stray readings. It used 200 tries and a distance limit of 5 mm.

Of the 1669 points, 1120 are on the table plane and 549 are left over. The fitted plane's normal is (−0.030, 0.020, 0.999). The table itself was made tilted with a normal of (−0.030, 0.020, 0.999), so the fit matches to three decimal places. The top of the box is also a plane, but it has only 90 points against the table's 1100 or so, so RANSAC keeps the table. The leftover points go to clustering, which splits them into one group per object.

A cylinder, such as a can, a bottle or a pipe, is harder, because two or three positions alone do not fix its axis. The usual method therefore works out each point's normal first, meaning the direction the surface faces at that point, from a small plane fit to its nearest neighbours. Then a try picks 2 points together with their normals. Because both normals on a cylinder point straight away from the axis, the axis must run at right angles to both. That gives the axis direction, and from the axis direction the position and the radius follow. A point agrees if its distance from the axis is close to the radius and its normal points away from the axis. The Point Cloud Library (PCL) does this with its cylinder model, which section 6 describes.

Choosing the distance limit#

Of the three things RANSAC needs from you, the distance limit is the one that matters most. A good start is two to three times the sensor's noise. For example, on a table half a metre away, a depth camera has about 1.5 mm of noise, so a limit of 4 to 5 mm is common.

If the limit is too small, real surface points count as outliers. So the inlier count of the true shape drops, and a wrong shape can win. If the limit is too large, points just above the surface count as inliers. On a table, that means the bottom few millimetres of every object are deleted along with the table. That matters most for flat objects such as a coin or a phone lying down, because those can vanish completely.

4. Where it is used on a robot arm#

The sections above explained how the loop works and how to set it up, so this section says where a real arm uses it. RANSAC is mostly a perception tool, but it also appears in calibration and sensing.

• Removing the table. The classic table-top recipe finds the biggest plane, deletes it, and clusters what is left into objects. Book 2 describes this in remove the plane, then cluster, and the tools and libraries page shows it as real Open3D code.
• Finding walls and bin sides. A robot picking from a bin runs RANSAC several times: find the biggest plane (the bin floor), remove its points, find the next (a wall), and so on, until what is left is the parts.
• Fitting cylinders. A robot that picks cans, bottles or pipes fits a cylinder to each cluster to get its axis and radius, and so the direction to approach it from.
• Finding a circle in a noisy rim. A glass's rim seen by a camera often has a few pixels from a reflection or from a neighbouring glass, so a circle RANSAC finds the rim first, and then least squares refines it.
• Matching features between pictures. When a camera on the arm moves, a program matches small patches between the old and the new picture, and some of those matches are wrong, so RANSAC finds the camera movement that most matches agree with. The same idea finds an object's pose from matched points, which OpenCV provides as solvePnPRansac.
• Calibration. When some checkerboard corners or marker detections in a calibration set are wrong, a RANSAC step can drop those poses before the final least-squares fit, which the calibration page covers.
• Checking a known table. When the table is fixed to the arm and measured once, RANSAC is not needed on every picture, as the glass-picking project in the sibling repo explains in its clustering notes. RANSAC can still run now and then, to check that the camera has not been knocked.

5. Where it is useful, and where it is not#

All of the uses above work for the same reason, so it is worth saying plainly when RANSAC is the right tool. The shape you want must be the biggest single shape in the data, and it must be defined by a few points. You must also be able to say how far from the shape a good point may be, because that distance is what decides which points agree. Once those conditions hold, it copes with half or more of the points being outliers, which almost nothing else does.

But once one of them fails, RANSAC fails with it, so the table below lists the ways that happens. Each row gives the cause, the sign you would see, and what people use instead.

6. Libraries that provide it#

Section 3 showed the loop as pseudocode, but you do not have to write that code yourself, because RANSAC is built into every major point cloud and vision library. The table below lists well-known ones, and each row gives the library, the languages it is used from, the function or class, and a note.

For a table plane in Python, the Open3D call is a single line. The tools and libraries page calls it with distance_threshold=0.005, which is 5 mm written in metres, and 3 points per try.

7. Why RANSAC, and what it costs#

The libraries above make RANSAC easy to call, so the question left is why you would call it instead of something simpler. RANSAC is a fitting method that tries many shapes, each one through a few random points, and keeps the shape that most points agree with. It gives the arm the right shape even when many of the points belong to other things. It also says which of the points belong to that shape.

The obvious alternative is least squares on all the points, perhaps after throwing away the points far from a first fit and fitting again. That works when only a few points are bad. But the first fit is already pulled towards the bad points, so it may throw away good points and keep bad ones. In the worked example, the first least-squares line was 14 mm too high at the left end. The turn-top-flat project's repeated refit, described on the least-squares page, works because only a thin strip of edge points was wrong. RANSAC never averages bad points in, so it works when a third or half of the points are bad.

A second alternative is a robust loss: a least-squares variant that counts large errors less, such as the Huber loss in SciPy's least_squares. It is smooth and repeatable, and it is good when outliers are a small share. But it starts from a guess, so with many outliers it can settle on the wrong shape, while RANSAC needs no starting guess at all.

RANSAC costs you five things, and the first is that it uses random choices, so two runs can give slightly different answers unless the seed is fixed. Second, it needs a distance limit, which means you must know the sensor's noise before you can set it. Third, it is slower than one least-squares fit, because it makes many tries, and it gets very slow for shapes that need many points. Fourth, it finds only the biggest shape, which may not be the one you meant. Finally, it needs a least-squares refit at the end to get the best accuracy.

8. The learned alternative#

Section 7 weighed RANSAC against other ways of fitting a shape, but there is also an alternative that does not fit a shape at all. A segmentation model, described in Book 7's point cloud models, gives every point a name, such as "mug", "box" or "table". So it replaces RANSAC when no single shape dominates the scene, such as a cluttered pile of parts. For shapes that need many points to define, a pose model from keypoints and object pose finds the object's pose directly. But a point cloud model needs labelled 3D data, which is much scarcer than labelled photos. It also needs a graphics card for large clouds, and it knows only the kinds of object it was trained on. RANSAC is still the better choice for the table, the walls of a bin and other simple shapes. This is because it needs no training, runs on an ordinary processor and says exactly which points belong to the shape.

9. Where to read next#

This page left several things to other documents, so the list below says where each of them is covered.

• Least-squares fitting explains the final refit and the plane and circle fits that RANSAC calls.
• The Kalman filter handles readings that arrive over time, rather than one batch of points.
• Clustering takes the points left after the table is removed and splits them into objects.
• Nearest-neighbour search finds the neighbours used to compute each point's normal before a cylinder fit.
• Book 2 shows the full recipe in remove the plane, then cluster.

10. Using it in Python#

Section 6 said that the Open3D call for a table plane is a single line, and section 3 said that choosing the distance limit is the part you cannot avoid. This section puts the two together in a program you can run. After it you will be able to remove a table from a point cloud and fit a robust line to a set of two-dimensional points, and you will know which number in each call you have to justify.

The two libraries below are worth showing together because they are used in genuinely different ways. Open3D works on a point cloud object and knows what a plane is, so the plane fit is one method call. scikit-learn works on plain NumPy arrays and knows nothing about geometry, so you hand it the model you want made robust and it wraps RANSAC around it.

import numpy as np
import open3d as o3d
from sklearn.linear_model import RANSACRegressor, LinearRegression

# --- a table plane in a point cloud, in metres
cloud = o3d.io.read_point_cloud("scene.ply")
plane, inliers = cloud.segment_plane(distance_threshold=0.005,
                                     ransac_n=3,
                                     num_iterations=1000)
a, b, c, d = plane                       # the plane is a*x + b*y + c*z + d = 0
objects = cloud.select_by_index(inliers, invert=True)   # what stood on the table

# --- a robust line through two-dimensional points, in millimetres
x = np.loadtxt("edge_points.txt")[:, [0]]     # one column, as scikit-learn wants
y = np.loadtxt("edge_points.txt")[:, 1]
fit = RANSACRegressor(estimator=LinearRegression(),
                      residual_threshold=2.0,
                      max_trials=100).fit(x, y)
slope = fit.estimator_.coef_[0]
kept = fit.inlier_mask_                  # True for each point the line agreed with

On a made-up scene of 4000 table points scattered by 2 mm, 600 points belonging to a box and 200 stray points, segment_plane with a 5 mm limit finds a plane of about (0.0005, 0.0006, 1.0, −0.0001) and keeps 3966 of the 4800 points as inliers. That leaves 834 points standing above the table, which is the box and the strays together, and is the input the clustering page starts from.

The libraries give you the whole loop from section 3. They pick the random samples, fit the candidate shape, count the agreeing points, repeat, and return the best shape together with the list of points that agreed with it. Open3D also gives you select_by_index with invert=True, which is how you keep everything that was not part of the plane.

What you still have to write is the step before and the step after. Before the call you have to load the cloud and cut it down, because RANSAC on a full-frame depth picture wastes time on the floor and the walls, and the thresholding page shows the box crop that removes them. After the call you have to check that the shape is the one you wanted, because RANSAC always returns its best guess and a table-shaped guess can just as easily be a wall. Checking usually means testing that the plane faces roughly upwards and that the number of inliers is a reasonable share of the points.

What you have to decide or measure is distance_threshold, and it is the one number on this page that nobody can choose for you. It has to be a little larger than your sensor's own depth noise, because otherwise the real table points count as outliers, and it has to be smaller than the thinnest object you want to keep, because otherwise the bottom of a sheet of paper is swallowed by the table. For the depth cameras used on arm workcells, 5 mm written as 0.005 is the usual starting point, and section 3 explains how to measure the noise that justifies it. You also choose ransac_n, which is 3 because three points define a plane, and num_iterations, which section 3 shows how to work out from the share of points you expect to be good.