Как совместить точки интереса SURF с базой данных изображений

Я использую алгоритм SURF в С# (OpenSurf), чтобы получить список точек интереса из изображения. Каждая из этих точек интереса содержит вектор дескрипторов, координату x (int), координату y (int), масштаб (float) и ориентацию (float).

Теперь я хочу сравнить точки интереса от одного изображения к списку изображений в базе данных, которые также имеют список точек интереса, чтобы найти наиболее похожее изображение. То есть: [Изображение (I.P.)] COMPARETO [Список изображений (I.P.)]. = > Лучшее совпадение. Сравнение изображений на индивидуальной основе дает неудовлетворительные результаты.

При поиске stackoverflow или других сайтов лучшим решением, которое я нашел, является создание индекса FLANN и в то же время отслеживание того, откуда возникают точки интереса. Но перед реализацией у меня есть некоторые вопросы, которые меня озадачат:

1) При сопоставлении изображений на основе их точек интереса SURF найденный мной алгоритм сопоставляет их путем сравнения их расстояния (x1, y1- > x2, y2) друг с другом и нахождения изображения с наименьшим итогом расстояние. Разве дескрипторы или ориентация никогда не используются при сравнении процентных точек?

2) Если используются дескрипторы, чем я могу их сравнить? Я не могу понять, как сравнить X-векторы из 64 точек (1 изображение) с Y-векторами из 64 точек (несколько изображений) с использованием индексированного дерева.

Я бы очень признателен за помощь. Все места, которые я искал, или API, которые я нашел, поддерживают только сопоставление одного изображения с другим, но не для эффективного сопоставления одного изображения с списком изображений.

Ответ 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 скаляры.

Ответ 2

Я уверен, что расстояние вычисляется между дескрипторами, а не их координатами (x, y). Вы можете сравнить только один дескриптор с другим. Я предлагаю следующее возможное решение (конечно, не оптимальное)

Вы можете найти для каждого дескриптора в изображении запроса верхние k ближайших соседей в вашем наборе данных, а затем взять все списки top-k и найти наиболее распространенное изображение.