Здесь есть несколько вещей.
Чтобы узнать, что два изображения (почти) равны, необходимо найти гомографическую проекцию двух, такую, чтобы проекция приводила к минимальной ошибке между местоположениями проецируемых объектов.Грубое принуждение возможно, но не эффективно, поэтому хитрость заключается в том, чтобы предположить, что похожие изображения, как правило, также имеют местоположения объектов в одном и том же месте (немного или немного).Например, при сшивании изображений изображение для сшивания обычно берется только под немного другим углом и / или в другом месте;даже если нет, расстояния, вероятно, будут расти («пропорционально») до разницы в ориентации.
Это означает, что вы можете - в качестве широкой фазы - выбрать изображения-кандидаты, найдя k пары точек с минимальнымпространственное расстояние (k ближайших соседей) между всеми парами изображений и выполняют гомографию только по этим точкам.Только тогда вы сравниваете проецируемое попарно пространственное расстояние и сортируете изображения по указанному расстоянию;самое низкое расстояние подразумевает наилучшее возможное совпадение (учитывая обстоятельства).
Если я не ошибаюсь, дескрипторы ориентированы по наибольшему углу в гистограмме угла.Театр означает, что вы также можете принять евклидово (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 (запрос).Теперь вы идете на позицию q в списке и принимаете k окружающие записи.Это ваши примерные ближайшие соседи. Теперь возьмите расстояние из этих пространственных объектов этих k значений и отсортируйте по наименьшему расстоянию - лучшие из них являются вашими лучшими кандидатами.
Возвращаясь к последнему изображению, примите верхнюю точкуэто наш запрос.Его проекция составляет 1.58, а приблизительный ближайший сосед (из четырех проецируемых точек) - это тот, у которого 1.17.Они не действительно близки в пространстве признаков, но, учитывая, что мы только что сравнили два 64-мерных вектора, используя только два значения, это тоже не так уж и плохо.
Вы видите ограничения там ианалогичные проекции вовсе не требуют, чтобы исходные значения были близки, что, конечно, приведет к довольно творческим совпадениям.Чтобы приспособиться к этому, вы просто генерируете больше базовых векторов B, C и т. Д. - скажем, n из них - и отслеживаете отдельный список для каждого.Возьмите k лучших совпадений для всех из них, отсортируйте список k*n 64-мерных векторов в соответствии с их евклидовым расстоянием до вектора запроса, выполните гомографию с лучшими и выберите тот, который имеет наименьшую ошибку проецирования.
Изюминка в том, что если у вас есть n (случайные, нормализованные) оси проекции и вы хотите искать в 64-мерном пространстве, вы просто умножаете каждый дескриптор на матрицу n x 64, что приводит кn скаляры.