RANSAC

RANdom SAmple Consensus popularly knowns as RANSAC method is used to fit a model to data, and helps to identify the outliers.

Let’s see how this method works, for this post consider the data distribution shown below. The majority of the data points follow a linear trend (inliers) and are the ones we are interested in modeling. The rest of the point, the noise points, are the outliers.

If we try to fit a curve, a line in this case, without removing any of the data points, we will end up with a fit as shown in the figure below. For this post, we will focus on fitting a line, but this method can be used for any curve.

The line is the best line we can fit, however, it looks wrong! The line doesn’t seem to describe the data! Can we do better than this without removing the data? Here RANSAC comes into picture.

STEP 1: Randomly select a number of data points from your data set. Since we are fitting a line in this example, let’s select 2.

STEP 2: Use the random sample to fit a line.

STEP 3: count how many data point are within a predefined distance to the line, shown in orange in the plot below. These data points, are the inliers, while the blue ones are the outliers. Finally, we record the number of inlier events.

If count of inliers is less than threshold inliers then abandon this sample and go to Step 1.

STEP 4: Repeat the process several times with a new random sample each time, and keep track of the number of inlier events. When to stop? You can stop after a predetermined number of steps or once a predetermined number of inliers has been reached.

STEP 5: Keep the data set with the highest number of inliers, or the first data set the reaches a predefined threshold.

Applying the RANSAC Regressor to our original data set, we are able to fit the data, but we also have a way of identifying outliers!

Applications of RANSAC

1. Determining the Homography Matrix -: RANSAC method is used to find the homogrpahy between sets of matching points. If matching points are outliers it can lead to false match and incorrect homography. Homography matrix is sensitive to outliers thus RANSAC helps in filtering out the outliers and produce correct homography.

2. Landmark extraction -: In SLAM based problems RANSAC is used on the measurement space to extract landmarks.