How does the Lowe's ratio test work?

Question

Suppose I have a set of N images and I have already computed the SIFT descriptors of each image. I know would like to compute the matches between the different features. I have heard that a common approach is the Lowe's ratio test but I cannot understand how it works. Can someone explain it to me?

Bitstock

You can read the tutorial below: docs.opencv.org/3.0-beta/doc/tutorials/features2d/… To summarize, each feature descriptor is matched to n number of closest neighbors. (n=2 in the case below) matcher.knnMatch(desc1, desc2, nn_matches, 2); Then the Lowe's ratio test, tries to figure out which of the two is the best match. – Hudis

@Hudis The ratio test doesn't figure which of the two is the best match. The ratio test checks if matches are ambiguous and should be removed. You can see it as a outlier removal technique. – Aesop

dear @dari, could you explain it in a clearer way? – Bitstock

@Bitstock If the ratio is close to 1, both matches are equally good and choosing one would give you an outlier in around 50%. Therefore it is usually better to discard both matches. – Aesop

Is it possible to fall in love with an algorithm? (Thanks to the o.g. Lowe and to all answerers - I learned something today!) – Quandary

Answer 1

Short version: each keypoint of the first image is matched with a number of keypoints from the second image. We keep the 2 best matches for each keypoint (best matches = the ones with the smallest distance measurement). Lowe's test checks that the two distances are sufficiently different. If they are not, then the keypoint is eliminated and will not be used for further calculations.

Long version:

David Lowe proposed a simple method for filtering keypoint matches by eliminating matches when the second-best match is almost as good. Do note that, although popularized in the context of computer vision, this method is not tied to CV. Here I describe the method, and how it is implemented/applied in the context of computer vision.

Let's suppose that L1 is the set of keypoints of image 1, each keypoint having a description that lists information about the keypoint, the nature of that info really depending on the descriptor algorithm that was used. And L2 is the set of keypoints for image 2. A typical matching algorithm will work by finding, for each keypoint in L1, the closest match in L2. If using Euclidian distance, like in Lowe's paper, this means the keypoint from set L2 that has the smallest Euclidian distance from the keypoint in L1.

Here we could be tempted to just set a threshold and eliminate all the pairings where the distance is above that threshold. But it's not that simple because not all variables inside the descriptors are as "discriminant": two keypoints could have a small distance measurement because most of the variables inside their descriptors have similar values, but then those variables could be irrelevant to the actual matching. One could always add weighting to the variables of the descriptors so that the more discriminating traits "count" more. Lowe proposes a much simpler solution, described below.

First, we match the keypoints in L1 with two keypoints in L2. Working from the assumption that a keypoint in image 1 can't have more than one equivalent in image 2, we deduce that those two matches can't both be right: at least one of them is wrong. Following Lowe's reasoning, the match with the smallest distance is the "good" match, and the match with the second-smallest distance the equivalent of random noise, a base rate of sorts. If the "good" match can't be distinguished from noise, then the "good" match should be rejected because it does not bring anything interesting, information-wise. So the general principle is that there needs to be enough difference between the best and second-best matches.

How the concept of "enough difference" is operationalized is important: Lowe uses a ratio of the two distances, often expressed a such:

if distance1 < distance2 * a_constant then ....

Where distance1 is the distance between the keypoint and its best match, and distance2 is the distance between the keypoint and its second-best match. The use of a "smalled than" sign can be somewhat confusing, but that becomes obvious when taking into consideration that a smaller distance means that the point is closer. In OpenCV world, the knnMatch function will return the matches from best to worst, so the 1st match will have a smaller distance. The question is really "how smaller?" To figure that out we multiply distance2 by a constant that has to be between 0 and 1, thus decreasing the value of distance2. Then we look at distance1 again: is it still smaller than distance2? If it is, then it passed the test and will be added to the list of good points. If not, it must be eliminated.

So that explans the "smaller than" part, but what about the multiplication? Since we are looking at the difference between the distances, why not just use an actual mathematical difference between distance1 and distance2? Although technically we could, the resulting difference would be in absolute terms, it would be too dependent on the variables inside the descriptors, the type of distance measurement that we use, etc. What if the code for extracting descriptions changes, affecting all distance measurements? In short, doing distance1 - distance2 would be less robust, would require frequent tweaking and would make methodological comparisons more complicated. It's all about the ratio.

Take-away message: Lowe's solution is interesting not only because of it's simplicity, but because it is in many ways algorithm-agnostic.

Swint

I think this applies well outside computer vision contexts as well, it is a nice method of selecting distances without using a hard threshold – Masoretic

You are right. I added a sentence to express the idea that the ratio test is not tied to CV. – Swint

What about if you use bf.knnMatch(des1, des2, k=3) or, in general, k > 2? In that case, it will return a list of lists, each of which has size k. How should Lowe's ratio test be performed? – Walloper

nbro: For k > 2, the other pairings would be 3rd best, 4th best and so on. Lowe's test compares the best and 2nd best because the 2nd best is considered as the best pairing amongst the "noise" (bad pairings). It's like the algo is saying "Give me the pairing that you assume is the right one. Now give the best of your bad pairings for the same keypoint. I see no significant difference, therefore any pairing associated with that keypoint can't be used to calculate the homography". – Swint

Medium version: Get the top two best results for keypoint matches. If these matches have a similar "distance" between the keypoints, then they're likely not very good matches and should be discarded. If the best result has a distance that is sufficiently different from the second best match, it's likely a "good" match and should be retained. – Quandary

This is the best explanation of Lowe's Ratio Test I've seen and read, and I've read many. If I can take a leap, this is even better than what was explained in the original SIFT paper. Nice going! – Faye

Answer 2

Lowe's Ratio Test

---

Algorithm:

1. First, we compute the distance between feature f_i in image one and all the features f_j in image two.
2. We choose feature f_c in image two with the minimum distance to feature f_i in image of one as our closest match.
3. We then proceed to get feature f_s the feature in image two with the second closest distance to the feature f_i.
4. Then we find how much nearer our closest match f_c is over our second closest match f_s through the distance ratio.
5. Finally we keep the matches with distance ratio < distance ratio threshold.

---

The distance ratio = d(fi, fc)/d(fi, fs) can be defined as the distance computed between feature f_i in image one and f_c the closest match in image two. Over the distance computed between feature f_i and f_s, the second closest match in image two.

We usually set the distance ratio threshold (ρ) to around 0.5, which means that we require our best match to be at least twice as close as our second best match to our initial features descriptor. Thus discarding our ambiguous matches and retaining the good ones.

Aniseed

Answer 3

For better understanding the ratio test, you need to read his article. Only by reading the article you will find out your answer. The simple answer is that it is low, which Lowe achieved during his experiments and suggest that for choosing between two similar distance, choose the one which its distance is 0.7 other one.

check the below link: https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf

Riarial

I went all in and wrote an answer that is a summary of Lowe's article and adds a few pointers that were not self-evident in the paper. Please take a look. :) – Swint