Alternative to distance metric in nearest neighbor algorithm?

Question

Hi, I came across an implementation of the nearest neighbor algorithm for finding matches between certain keypoints in two similar images. The keypoints were generated by the SIFT algorithm. The points are described by a 128 dimension vector, and there are many such points in both images.

The matching algorithm uses the nearest neighbor search and for each point in one image, calculates the corresponding closest point in the other image. The 'closeness' is depicted by minimum euclidean distance between the vectors of the points. The best such matches are selected by taking only those pairs of points whose distance lies below a certain threshold.

However the implementation I came across multiplies all the vectors of the keypoints in one image, with those in the other image, thus forming a matrix of products. It then finds the points whose product is higher than a given threshold.

This implementation gives correct results, but I'd like to know how it works. Does it use correlation between the vectors as the metric or is there something else going on here.

Answer 1

It seems it's not a matter of differing inner products after all, nor is it a matter of the dot product itself. Turns out it's a matter of simple math.

Basically...

Assume abs(a + b) = C, where C is some constant. The maximum possible value of a * b will always be the result(s) where a == b == +- C / 2. Therefore, the distance between a and b will be minimum when their product is maximum, and vice versa. This works for all real numbers (both positive and negative) and also extends into multiple dimensions, so it probably works with complex numbers as well (though I haven't tested it with such).

Example with C = 20:

((a, b), distance, product)

((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)       (As you can see, the distance is minimum while the product is maximum.)
((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)