Альтернатива метриці відстані в найближчому алгоритмі сусіда? - комп'ютерне бачення, найближчий сусід, кореляція, kdtree, просіяти

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

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

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

Ця реалізація дає правильні результати, але мені б хотілося знати, як вона працює. Чи використовує вона кореляцію між векторами як метрику чи тут відбувається щось інше.

Відповіді:

Здається, це не питання різної внутрішньої продукції, а також питання не самого крапкового продукту. Виявляється, це питання простої математики.

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

Припустимо 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)