Альтернатива метрике расстояния в алгоритме ближайшего соседа? - PullRequest
Новая
       29

Альтернатива метрике расстояния в алгоритме ближайшего соседа?

3 голосов
/ 30 июня 2010

Я столкнулся с реализацией алгоритма ближайшего соседа для поиска совпадений между определенными ключевыми точками в двух похожих изображениях.Ключевые точки были сгенерированы алгоритмом SIFT.Точки описываются вектором 128 размеров, и на обоих изображениях имеется много таких точек.

Алгоритм сопоставления использует поиск ближайших соседей и для каждой точки в одном изображении вычисляет соответствующую ближайшую точку в другомобраз.«Близость» описывается минимальным евклидовым расстоянием между векторами точек.Наилучшие такие совпадения выбираются путем взятия только тех пар точек, расстояние которых лежит ниже определенного порога.

Однако реализация, с которой я столкнулся, умножает все векторы ключевых точек на одном изображении на все векторы на другом изображении, таким образом, образуя матрицу продуктов.Затем он находит точки, произведение которых выше заданного порога.

Эта реализация дает правильные результаты, но я хотел бы знать, как она работает.Использует ли он корреляцию между векторами в качестве метрики или здесь происходит что-то еще?

1 Ответ

2 голосов
/ 30 июня 2010

Кажется, что дело не в разных внутренних продуктах, и не в самом точечном продукте. Оказывается, это вопрос простой математики.

В основном ...

Предположим, что 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)

...