Эффективный способ сопоставления дескрипторов SIFT

Есть 2 изображения A и B. Я извлекаю из них ключевые точки (a[i] и b[i]).
Интересно, как я могу эффективно определить соответствие между a[i] и b[j]?

Мне приходит на ум очевидный метод — сравнить каждую точку в A с каждой точкой в ​​B. Но это требует много времени для больших баз данных изображений. Как я могу просто сравнить точку a [i] только с b [k], где k имеет небольшой диапазон?

Я слышал, что kd-tree может быть хорошим выбором, не так ли? Есть ли хорошие примеры о kd-tree?

Любые другие предложения?


opencv match kdtree feature-descriptor
person vancexu    schedule 10.10.2012    source источник
comment
kd-дерево как таковое неэффективно для дескрипторов с такой высокой размерностью, как SIFT (это известно как размерности). Однако существуют и другие стратегии индексации для приближенного поиска ближайшего соседа в многомерных пространствах. FLANN, включенный в OpenCV, является одним из них. И есть реализация сопоставления ключевых точек с использованием FLANN, см. ссылку в моем ответе   -  person remi    schedule 10.10.2012

Ответы (3)


arrow_upward
11
arrow_downward

Дерево KD хранит обученные дескрипторы таким образом, чтобы действительно быстрее найти наиболее похожий дескриптор при выполнении сопоставления.

С OpenCV действительно легко использовать kd-tree, я приведу пример для сопоставления flann:

flann::GenericIndex< cvflann::L2<int> >  *tree; // the flann searching tree
tree = new flann::GenericIndex< cvflann::L2<int> >(descriptors, cvflann::KDTreeIndexParams(4)); // a 4 k-d tree

Затем, когда вы выполняете сопоставление:

const cvflann::SearchParams params(32);
tree.knnSearch(queryDescriptors, indices, dists, 2, cvflann::SearchParams(8));
person Jav_Rock    schedule 10.10.2012
comment
Когда вы помечаете ответы, которые должны быть комментариями или просто ссылками, отмечайте их как «Не ответ», а не «Очень низкое качество», это помогает нам с точки зрения рабочего процесса. Но продолжайте отмечать, мы ценим это! - person casperOne; 11.10.2012

arrow_upward
10
arrow_downward

Вопрос в том, хотите ли вы на самом деле определить соответствие ключевых точек между двумя изображениями или вычислить меру сходства.

Если вы хотите определить соответствие, то, боюсь, вам придется перебирать все возможные пары дескрипторов между двумя изображениями (есть более продвинутые методы, такие как FLANN — Fast Approximate Nearest Neighbor Search, но ускорение не имеет значения, если у вас меньше или около 2000 ключевых точек на изображение — по крайней мере, по моему опыту). Чтобы получить более точное соответствие (не быстрее, а просто лучше), я могу предложить вам взглянуть на:

Если, с другой стороны, вам нужна только мера сходства для большой базы данных, то подходящим местом для начала будет:

person penelope    schedule 10.10.2012

arrow_upward
4
arrow_downward

В OpenCV реализовано несколько стратегий для сопоставления наборов ключевых точек. Ознакомьтесь с документацией по общим интерфейсам средств сопоставления дескрипторов.

person remi    schedule 10.10.2012