Manera eficiente para la coincidencia del descriptor SIFT

Question

Hay 2 imágenes A y B. Extracto los puntos clave (a [i] y b [i]) de ellos.
Me pregunto cómo puedo determinar la coincidencia entre a [i] y b [j], de manera eficiente?

El método obvio es que comparo cada punto en A con cada punto en B. Pero consume mucho tiempo para bases de datos de imágenes grandes. ¿Cómo puedo simplemente comparar el punto a [i] con solo b [k] donde k es de rango pequeño?

Escuché que kd-tree puede ser una buena opción, ¿no? ¿Hay algún buenos ejemplos sobre kd-tree?

¿Alguna otra sugerencia?

Answer 1

KD tree almacena los descriptores formados de forma que es realmente más rápido encontrar el descriptor más parecido al realizar la coincidencia.

Con OpenCV es muy fácil de usar KD-árbol, te daré un ejemplo para el matcher 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 

Entonces, cuando lo hace el juego:

const cvflann::SearchParams params(32); 
tree.knnSearch(queryDescriptors, indices, dists, 2, cvflann::SearchParams(8)); 

Answer 2

La pregunta es tiempo de que realmente desea determinar un punto clave juego entre dos imágenes, o calcular una medida de similitud .

Si desea determinar una coincidencia, me temo que tendrá que realizar una búsqueda de fuerza bruta a través de todos los pares de descriptores posibles entre dos imágenes (hay algunos métodos más avanzados como FLANN - Búsqueda aproximada de vecinos más cercanos, pero la aceleración no es significativa si tienes menos o alrededor de 2000 puntos clave por imagen, al menos en mi experiencia). Para obtener una coincidencia más exacta (no más rápido, sólo mejores partidos), puedo sugerirle que tome vistazo a:

• D.G. Lowe. Distinctive image features from scale-invariant keypoints - la comparación con el partido más cercano segundo
• J. Sivic and A. Zisserman. Video Google: A text retrieval approach to object matching in videos - la sección acerca de la coherencia espacial

Si, por el contrario, desea que sólo una medida de similitud sobre una base de datos grande , entonces el lugar apropiado para empezar sería:

• D. Nistér and H. Stewénius. Scalable recognition with a vocabulary tree - donde utilizan un enfoque jerárquico basado en una estructura llamada árbol vocabulario ser capaz de calcular una medida de similitud consulta una imagen y una imagen a partir de una gran base de datos
• J. Sivic and A. Zisserman. Video Google: A text retrieval approach to object matching in videos entre - el mismo papel que arriba, pero es muy útil para understan el enfoque en Nister, Stewénius

Answer 3

en OpenCV hay varias estrategias implementadas para que coincida con conjuntos de puntos clave. Eche un vistazo a la documentación sobre Common Interfaces of Descriptor Matchers.