Ответ 1
Здесь есть несколько вещей.
Чтобы знать, что два изображения (почти) равны, вам нужно найти гомографическую проекцию двух таких, чтобы проекция приводила к минимальной ошибке между местами проецируемых объектов. Жесткое форсирование возможно, но не эффективно, поэтому уловка состоит в том, чтобы предположить, что подобные изображения имеют тенденцию иметь места расположения объектов в том же месте (дайте или возьмите немного). Например, при сшивании изображений изображение в строчку обычно выполняется только с немного другого угла и/или местоположения; даже если нет, расстояния, вероятно, будут расти ( "пропорционально" ) на разницу в ориентации.
Это означает, что вы можете - как широкую фазу - выбирать изображения кандидатов, находя пары k точек с минимальным пространственным расстоянием (ближайших соседей k) между всеми парами изображений и выполнять гомографию только в этих точках. Только тогда вы сравниваете проецируемое попарно пространственное расстояние и сортируете изображения по указанному расстоянию; наименьшее расстояние подразумевает наилучшее совпадение (учитывая обстоятельства).
Если я не ошибаюсь, дескрипторы ориентируются самым сильным углом в гистограмме угла. Theat означает, что вы также можете принять эйклидовое (L2) расстояние от 64- или 128-мерных дескрипторов функций напрямую, чтобы получить реальное сходство двух пространственных объектов и выполнить гомографию с лучшими кандидатами k. (Вы не будете сравнивать масштаб, в котором были найдены дескрипторы, потому что это победит цель масштабной инвариантности.)
Оба варианта занимают много времени и напрямую зависят от количества изображений и функций; в другом слове: глупая идея.
Приблизительные ближайшие соседи
Чистый трюк состоит в том, чтобы не использовать фактические расстояния вообще, а приблизительные расстояния. Другими словами, вам нужен приблизительный алгоритм ближайшего соседа, и FLANN (хотя и не для .NET) будет одним из них.
Одним из ключевых моментов здесь является алгоритм поискового поиска. Он работает следующим образом:
Предполагая, что вы хотите сравнить дескрипторы в 64-мерном пространстве объектов. Вы генерируете случайный 64-мерный вектор и нормализуете его, приводя к произвольному единичному вектору в пространстве объектов; позвоните ему A. Теперь (при индексировании) вы формируете точечный продукт каждого дескриптора против этого вектора. Это проектирует каждый 64-й вектор на A, что приводит к одному действительному числу a_n. (Это значение a_n представляет расстояние дескриптора вдоль A по отношению к началу A.)
Это изображение, взятое из этого ответа на CrossValidated относительно PCA, демонстрирует его визуально; подумайте о вращении в результате различных случайных выборов A, где красные точки соответствуют проекциям (и, следовательно, скалярам a_n). Красные линии показывают ошибку, которую вы делаете, используя этот подход, и это приближает поиск.
Вам понадобится A снова для поиска, поэтому вы сохраните его. Вы также отслеживаете каждое прогнозируемое значение a_n и дескриптор, из которого он пришел; кроме того, вы выравниваете каждый a_n (со ссылкой на его дескриптор) в списке, отсортированном по a_n.
Чтобы уточнить использование другого изображения из здесь, нас интересует расположение проецируемых точек вдоль оси A:
Значения a_0 .. a_3 из 4 проецируемых точек на изображении приблизительно равны sqrt(0.5²+2²)=1.58, sqrt(0.4²+1.1²)=1.17, -0.84 и -0.95, что соответствует их расстоянию до начала A.
Если вы хотите найти похожие изображения, вы делаете то же самое: проектируйте каждый дескриптор на A, в результате получим скаляр q (query). Теперь вы переходите в позицию q в списке и берете k окружающие записи. Это ваши приближенные ближайшие соседи. Теперь возьмите расстояние по пространству-пространству этих значений k и отсортируйте по наименьшему расстоянию - лучшие из них - ваши лучшие кандидаты.
Возвращаясь к последнему изображению, предположим, что самая верхняя точка - наш запрос. Его проекция 1.58, и она приближается к ближайшему соседу (из четырех проецируемых точек), который находится в 1.17. Они не очень близки к пространству объектов, но при условии, что мы просто сравнили два 64-мерных вектора, используя только два значения, это тоже не так плохо.
Вы видите границы там, и аналогичные прогнозы вообще не требуют, чтобы исходные значения были близкими, это, конечно же, приведет к довольно творческим совпадениям. Чтобы разместить это, вы просто генерируете больше базовых векторов B, C и т.д. - скажите n из них - и отслеживайте отдельный список для каждого. Возьмите наилучшие совпадения k для всех из них, отсортируйте список из k*n 64-мерных векторов в соответствии с их эвклидовым расстоянием до вектора запроса, выполните гомографию на лучших и выберите ту, которая имеет наименьшую ошибку проектирования.
Оптимальная часть этого состоит в том, что если у вас есть n (случайные, нормализованные) оси проекции и вы хотите искать в 64-мерном пространстве, вы просто умножаете каждый дескриптор на матрицу n x 64, в результате получим n скаляры.