computer-vision - 最近邻算法中距离度量的替代方案？

Question

我遇到了最近邻算法的实现，该算法用于在两个相似图像中的某些关键点之间找到匹配项。关键点由 SIFT 算法生成。这些点用一个128维的向量来描述，两幅图像中都有很多这样的点。

匹配算法使用最近邻搜索，对于一幅图像中的每个点，计算另一幅图像中对应的最近点。 “接近度”由点向量之间的最小欧几里德距离描述。通过仅采用距离低于特定阈值的那些点对来选择最佳匹配。

然而，我遇到的实现是将一幅图像中关键点的所有向量与另一幅图像中的所有向量相乘，从而形成乘积矩阵。然后它找到其乘积高于给定阈值的点。

这个实现给出了正确的结果，但我想知道它是如何工作的。它是使用向量之间的相关性作为度量，还是这里有其他事情发生。

Answer 1

看来这毕竟不是内积不同的问题，也不是点积本身的问题。事实证明这是一个简单的数学问题。

基本上...

假设 abs(a + b) = C，其中 C 是某个常数。 a * b 的最大可能值将始终是 a == b == +- C/2 的结果。因此，当 a 和 b 的乘积最大时，它们之间的距离将最小，反之亦然。这适用于所有实数(包括正数和负数)并且还扩展到多个维度，因此它可能也适用于复数(尽管我还没有用它测试过)。

C = 20 的示例:

((a, b), 距离, 乘积)

((0, 20), 20.0, 0)
((1, 19), 18.0, 19)
((2, 18), 16.0, 36)
((3, 17), 14.0, 51)
((4, 16), 12.0, 64)
((5, 15), 10.0, 75)
((6, 14), 8.0, 84)
((7, 13), 6.0, 91)
((8, 12), 4.0, 96)
((9, 11), 2.0, 99)
((10, 10), 0.0, 100) (如您所见，距离最小，乘积最大。)
((11, 9), 2.0, 99)
((12, 8), 4.0, 96)
((13, 7), 6.0, 91)
((14, 6), 8.0, 84)
((15, 5), 10.0, 75)
((16, 4), 12.0, 64)
((17, 3), 14.0, 51)
((18, 2), 16.0, 36)
((19, 1), 18.0, 19)
((20, 0), 20.0, 0)