劳氏比率测试如何工作? [英] How does the Lowe's ratio test work?

问题描述

假设我有一组 N 个图像，并且我已经计算了每个图像的 SIFT 描述符.我知道想计算不同特征之间的匹配.我听说一种常见的方法是劳氏比率测试，但我不明白它是如何工作的.有人可以向我解释吗?

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?

推荐答案

短版: 第一个图像的每个关键点都与第二个图像的多个关键点相匹配.我们为每个关键点保留 2 个最佳匹配(最佳匹配 = 距离测量值最小的那些).劳氏检验检查这两个距离是否足够不同.如果不是，则该关键点被消除，不再用于进一步计算.

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.

加长版:

David Lowe 提出了一种过滤关键点匹配的简单方法，即在次优匹配几乎相同时消除匹配.请注意，尽管在计算机视觉的背景下得到普及，但这种方法与 CV 无关.在这里，我描述了该方法，以及它是如何在计算机视觉环境中实现/应用的.

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.

假设 L1 是图像 1 的一组关键点，每个关键点都有一个描述，其中列出了有关关键点的信息，该信息的性质实际上取决于所使用的描述符算法.L2 是图像 2 的关键点集.典型的匹配算法将通过为 L1 中的每个关键点找到 L2 中最接近的匹配来工作.如果使用欧几里得距离，就像在 Lowe 的论文中一样，这意味着集合 L2 中的关键点与 L1 中的关键点的欧几里得距离最小.

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.

在这里，我们可能只想设置一个阈值并消除距离高于该阈值的所有配对.但这并不是那么简单，因为并非描述符中的所有变量都具有判别性":两个关键点的距离测量值可能很小，因为它们的描述符中的大多数变量具有相似的值，但是这些变量可能与实际匹配无关.人们总是可以为描述符的变量添加权重，以便更具区分性的特征计数"更多.Lowe 提出了一个更简单的解决方案，如下所述.

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.

首先，我们将 L1 中的关键点与 L2 中的 两个 关键点进行匹配.根据图像 1 中的关键点在图像 2 中不能有多个等价点的假设，我们推断这两个匹配不可能都是正确的:至少其中一个是错误的.按照 Lowe 的推理，距离最小的匹配是好"匹配，距离第二小的匹配相当于随机噪声，一种基本速率.如果好"匹配无法与噪声区分开来，那么好"匹配应该被拒绝，因为它不会带来任何有趣的信息.所以一般原则是最佳匹配和次佳匹配之间需要有足够的差异.

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.

足够的差异"的概念如何操作很重要:Lowe 使用两个距离的比率，通常表示如下:

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 ....

其中 distance1 是关键点与其最佳匹配之间的距离，distance2 是关键点与其次佳匹配之间的距离.使用小于"符号可能会有些混乱，但当考虑到较小的距离意味着该点更近时，这一点就变得很明显了.在 OpenCV 世界中，knnMatch 函数会从最好到最差的顺序返回匹配，因此第一个匹配的距离会更小.问题实际上是有多小?"为了弄清楚这一点，我们将 distance2 乘以一个必须在 0 和 1 之间的常数，从而减小 distance2 的值.那我们再看distance1:还是比distance2小吗?如果是，那么它通过了测试，并将被添加到好点列表中.如果不是，就必须淘汰.

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.

这样就解释了小于"部分，但是乘法呢?既然我们正在查看距离之间的差异，为什么不直接使用距离 1 和距离 2 之间的实际数学差异呢?虽然从技术上讲我们可以，但产生的差异将是绝对的，它太依赖于描述符中的变量，我们使用的距离测量类型等.如果提取描述的代码发生变化，影响所有距离测量怎么办?简而言之，进行距离1 - 距离2 的鲁棒性会降低，需要经常进行调整，并且会使方法比较更加复杂.关键在于比例.

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.

要点:Lowe 的解决方案很有趣，不仅因为它简单，而且因为它在很多方面与算法无关.

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

这篇关于劳氏比率测试如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！