RANSAC Explained for SIFT Feature Matching and Homography


Introduction

Image transformations play an important role in computer vision. They are used under the hood of complex algorithms, enabling solutions to problems such as creating panoramas from a set of images, reconstructing 3D scenes, or even measuring the length of objects or the distance between them.

Problem

In the previous articles, we learned about projective transformation, which allows us to project an image from one plane to another using homography. Under the hood, homography requires at least k ≥ 4 matching points from a pair of images to perform this transformation.

We have also looked at the SIFT algorithm, which finds pairs of matching features in images that can then be fed into the homography to derive a perfect projection.

The problem is that, despite its robustness and invariance to scaling and rotation, SIFT does not guarantee that features across images will be matched correctly.

For example, there can be regions in both images that look very similar and have a similar distribution of neighboring gradients, but in reality they correspond to different 3D projected points. Given that, SIFT will assign similar descriptors to these features, and as a result, they will have a high probability of being considered a matched pair.

An example showing how SIFT can incorrectly match feature pairs (in red) when the features look very similar in both images.

With a considerable number of incorrect matches, SIFT will fail to derive a correct transformation. That is why we need a post-processing step to filter out incorrect matches. This is where the RANSAC algorithm comes into play.

Idea

Let’s understand how RANSAC works in general (it is not only used in computer vision). For that, let’s imagine that we have n data samples and we want to find a model that best fits the data, given that the input data can contain inliers (which we want to detect) and outliers (which we want the model not to consider).

Read Also:  5 Real-World Use Cases for AI Agents Transforming Industries

First, RANSAC randomly selects k out of n data points. Typically, k is set to the minimum number of samples required to fit the model. For example, in the case of a homography, k = 4.

Secondly, the selected points are then fed into the model.

img 6b0323764570c
An example of one possible iteration of RANSAC. k = 5 points in red were chosen randomly by RANSAC and fed into the linear regression model. There are 6 points from the dataset that lie within the ε-error threshold zone of the fitting line.

Once the model has been trained, all samples are passed through it. All fitted points within the ε error threshold are considered inliers, and their count is recorded. Those lying outside the threshold are considered outliers.

The whole process is repeated for a given number of iterations, and after the procedure ends, the fitted model with the most predicted inliers is selected.

img 6b0323774fcc3
The best regression line found by RANSAC, fitting 8 data points within the ε-error threshold.

Optionally, for greater accuracy, the chosen model with the most predicted inliers can be retrained on all inliers.

Homography case

For homography, at each iteration, RANSAC selects k = 4 random matched feature pairs and fits them to the homography model. After the homography matrix H is obtained, the first image is projected onto the second image using H. Then the distance between each projected point from the first image and its corresponding point in the second image is computed.

All matching points within the ε-threshold error are considered inliers, and their count is recorded.

After repeating this procedure many times, the best homography matrix H with the most inliers is selected, and then a new matrix H is computed using all detected inliers.

The final matrix H is returned as the homography matrix for the input image pair.

Condition

For homography, RANSAC tends to be efficient when the number of outliers is small relative to the number of inliers.

Read Also:  Deb8flow: Orchestrating Autonomous AI Debates with LangGraph and GPT-4o

However, depending on the number of points required to fit the model and the chosen number of iterations, RANSAC can still perform relatively well even when there are more outliers than inliers.Preview

Conclusion

RANSAC is a robust algorithm widely used in combination with SIFT and homography to remove incorrectly matched feature pairs. With only the number of iterations and the error threshold as its parameters, RANSAC is very easy to use and interpret.

RANSAC is used under the hood of other complex algorithms, such as COLMAP, which reconstructs a 3D scene from a set of images. RANSAC’s versatility allows it to be applied to other problems as well.

Resources

All images unless otherwise noted are by the author

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top