c# - surfear - surf en los angeles
Cómo hacer coincidir los puntos de interés de SURF con una base de datos de imágenes. (2)
Estoy utilizando el algoritmo SURF en C # (OpenSurf) para obtener una lista de puntos de interés de una imagen. Cada uno de estos puntos de interés contiene un vector de descriptores, una coordenada x (int), una coordenada y (int), la escala (flotante) y la orientación (flotante).
Ahora, quiero comparar los puntos de interés de una imagen con una lista de imágenes en una base de datos que también tiene una lista de puntos de interés, para encontrar la imagen más similar. Es decir: [Imagen (IP)] COMPARETO [Lista de imágenes (IP)]. => Mejor partido. La comparación de las imágenes sobre una base individual produce resultados insatisfactorios.
Cuando busco stackoverflow u otros sitios, la mejor solución que he encontrado es crear un índice de FLANN y al mismo tiempo hacer un seguimiento de dónde provienen los puntos de interés. Pero antes de la implementación, tengo algunas preguntas que me desconciertan:
1) Cuando coinciden las imágenes basadas en sus puntos de interés SURF, un algoritmo que he encontrado hace la comparación al comparar su distancia (x1, y1-> x2, y2) entre sí y encontrar la imagen con la distancia total más baja. ¿Los descriptores u orientación nunca se utilizan al comparar los puntos de interés?
2) Si se usan los descriptores, ¿cómo los comparo? No puedo averiguar cómo comparar vectores X de 64 puntos (1 imagen) con vectores Y de 64 puntos (varias imágenes) utilizando un árbol indexado.
Realmente apreciaría alguna ayuda. Todos los lugares en los que he buscado o la API que encontré, solo son compatibles para hacer coincidir una imagen con otra, pero no para hacer coincidir una imagen con una lista de imágenes.
Estoy bastante seguro de que la distancia se calcula entre los descriptores y no sus coordenadas (x, y). Puedes comparar directamente solo un descriptor contra otro. Propongo la siguiente solución posible (seguramente no la óptima)
Puede encontrar para cada descriptor en la imagen de consulta los vecinos más cercanos a k superior en su conjunto de datos, y luego tomar todas las listas de top k y encontrar la imagen más común allí.
Hay varias cosas aquí.
Para saber que dos imágenes son (casi) iguales, debe encontrar la proyección homográfica de las dos, de modo que la proyección resulte en un error mínimo entre las ubicaciones de las características proyectadas. La fuerza bruta es posible pero no eficiente, por lo que un truco es asumir que las imágenes similares tienden a tener las ubicaciones de las características también en el mismo lugar (más o menos). Por ejemplo, al coser imágenes, la imagen a coser generalmente se toma solo desde un ángulo y / o ubicación ligeramente diferente; incluso si no, las distancias probablemente aumentarán ("proporcionalmente") a la diferencia de orientación.
Esto significa que puede, como una fase amplia, seleccionar imágenes candidatas encontrando k pares de puntos con la distancia espacial mínima (los k vecinos más cercanos) entre todos los pares de imágenes y realizar homografía solo en estos puntos. Solo entonces usted compara la distancia espacial proyectada de pares de puntos y ordena las imágenes por dicha distancia; la distancia más baja implica la mejor coincidencia posible (dadas las circunstancias).
Si no me equivoco, los descriptores están orientados por el ángulo más fuerte en el histograma de ángulo. Theat significa que también puede decidir tomar la distancia euclidiana (L2) de los descriptores de características de 64 o 128 dimensiones directamente para obtener la similitud real de espacio de características de dos características dadas y realizar homografía en los mejores k candidatos. (Sin embargo, no comparará la escala en la que se encontraron los descriptores, porque eso anularía el propósito de la invarianza de escala).
Ambas opciones consumen mucho tiempo y dependen directamente del número de imágenes y características; en otras palabras: idea estúpida.
Aproximadamente los vecinos más cercanos
Un buen truco es no usar distancias reales, sino distancias aproximadas . En otras palabras, usted desea un algoritmo de aproximación más cercano, y FLANN (aunque no para .NET) sería uno de ellos.
Un punto clave aquí es el algoritmo de búsqueda de proyección. Funciona así: Suponiendo que desea comparar los descriptores en un espacio de características de 64 dimensiones. Genera un vector aleatorio de 64 dimensiones y lo normaliza, lo que resulta en un vector de unidad arbitrario en el espacio de características; llamémoslo A Ahora (durante la indexación) usted forma el producto punto de cada descriptor contra este vector. Esto proyecta cada vector de 64 días en A , dando como resultado un solo número real a_n . (Este valor a_n representa la distancia del descriptor a lo largo de A en relación con el origen de A).
Esta imagen que tomé prestada de this respuesta en CrossValidated con respecto a PCA lo demuestra visualmente; piense en la rotación como resultado de diferentes elecciones aleatorias de A , donde los puntos rojos corresponden a las proyecciones (y, por lo tanto, los escalares a_n ). Las líneas rojas muestran el error que comete al usar ese enfoque, esto es lo que hace que la búsqueda sea aproximada.
Necesitarás A nuevo para buscar, así que lo guardas. También realiza un seguimiento de cada valor proyectado a_n y el descriptor del que proviene; además, alinea cada a_n (con un enlace a su descriptor) en una lista, ordenada por a_n .
Para aclarar el uso de otra imagen desde here , nos interesa la ubicación de los puntos proyectados a lo largo del eje A :
Los valores a_0 .. a_3 de los 4 puntos proyectados en la imagen son aproximadamente sqrt(0.5²+2²)=1.58 , sqrt(0.4²+1.1²)=1.17 , -0.84 y -0.95 , correspondiente a su distancia a A '' s origen.
Si ahora desea encontrar imágenes similares, haga lo mismo: proyecte cada descriptor en A , lo que da como resultado un q escalar (consulta). Ahora ve a la posición de q en la lista y toma las k entradas circundantes. Estos son sus vecinos más cercanos aproximados. Ahora tome la distancia del espacio de características de estos valores k y ordene por la distancia más baja; los mejores son sus mejores candidatos.
Volviendo a la última imagen, supongamos que el punto más alto es nuestra consulta. Su proyección es de 1.58 y su vecino aproximado más cercano (de los cuatro puntos proyectados) es el de 1.17 . No están realmente cerca en el espacio de características, pero dado que solo comparamos dos vectores de 64 dimensiones usando solo dos valores, tampoco es tan malo.
Usted ve los límites allí y, las proyecciones similares no requieren en absoluto que los valores originales estén cerca, por supuesto, esto dará como resultado coincidencias bastante creativas. Para adaptarse a esto, simplemente genere más vectores base B , C , etc., diga n de ellos, y realice un seguimiento de una lista separada para cada uno. Tome las k mejores coincidencias en todas ellas, ordene esa lista de k*n 64 vectores tridimensionales de acuerdo con su distancia euclidiana al vector de consulta, realice una homografía en los mejores y seleccione la que tenga el error de proyección más bajo.
Lo mejor de esto es que si tiene n ejes de proyección (aleatorios, normalizados) y desea buscar en un espacio de 64 dimensiones, simplemente está multiplicando cada descriptor con una matriz nx 64 , lo que da como resultado n escalas.