2012-10-10 6 views
6

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?Manera eficiente para la coincidencia del descriptor SIFT

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?

+1

KD- el árbol como tal no es eficiente para descriptores con una alta dimensionalidad como SIFT (esto se conoce como [maldición de dimensión] (http://en.wikipedia.org/wiki/Curse_of_dimensionality)). Sin embargo, existen otras estrategias de indexación para la búsqueda aproximada del vecino más cercano en espacios de alta dimensión. FLANN, incluido en OpenCV, es uno. Y hay una implementación de la coincidencia de puntos clave usando FLANN, vea el enlace en mi respuesta – remi

Respuesta

11

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)); 
+2

Cuando está marcando las respuestas que deberían ser comentarios o solo son enlaces, márquelas como "No es una respuesta" en lugar de "Muy baja calidad" , nos ayuda desde una perspectiva de flujo de trabajo. Pero sigue marcando, ¡lo apreciamos! – casperOne

8

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:

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:

Cuestiones relacionadas