Comparando las características de SIFT almacenadas en una base de datos mysql

Actualmente estoy extendiendo una biblioteca de imágenes que se usa para categorizar imágenes y quiero encontrar imágenes duplicadas, imágenes transformadas e imágenes que contengan o estén contenidas en otras imágenes.
He probado la implementación SIFT de OpenCV y funciona muy bien, pero sería bastante lento para varias imágenes. Demasiado rápido, pensé que podría extraer las características y guardarlas en una base de datos, ya que muchos de los metadatos relacionados con la imagen ya se encuentran allí.

¿Cuál sería la forma más rápida de comparar las características de una nueva imagen con las características en la base de datos?
Por lo general, la comparación se realiza calculando la distancia euclidiana utilizando kd-trees, FLANN o con el Kernel de Pyramid Match que encontré en otro hilo aquí en SO, pero aún no he investigado mucho.

Como no conozco una forma de guardar y buscar un árbol kd en una base de datos de manera eficiente, actualmente solo veo tres opciones:
* Permita que MySQL calcule la distancia euclidiana a cada característica en la base de datos, aunque estoy seguro de que tomará un tiempo irrazonable para más de unas pocas imágenes.
* Cargue el conjunto de datos completo en la memoria al principio y genere los kd-tree (s). Esto probablemente sea rápido, pero requiere mucha memoria. Además, todos los datos deberían ser transferidos desde la base de datos.
* Guardar los árboles generados en la base de datos y cargarlos todos, sería el método más rápido, pero también generaría grandes cantidades de tráfico, ya que con las nuevas imágenes, los kd-trees tendrían que reconstruirse y enviarse al servidor.

Estoy usando la implementación SIFT de OpenCV, pero no estoy completamente decidido. Si hay un extractor de características más adecuado para esta tarea (y aproximadamente igual de robusto), me alegro si alguien pudiera sugerir una.

Así que básicamente hice algo muy similar a esto hace unos años. El algoritmo que desea examinar fue propuesto hace unos años por David Nister, el documento es: “Reconocimiento escalable con un árbol de vocabulario”. Casi tienen una solución exacta a su problema que puede escalar a millones de imágenes.

Aquí hay un enlace al resumen, puede encontrar un enlace de descarga buscando el título en Google. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

La idea básica es construir un árbol con un algoritmo jerárquico de k-medias para modelar las características y luego aprovechar la distribución dispersa de las características en ese árbol para encontrar rápidamente a sus vecinos más cercanos … o algo así, han pasado algunos años desde Trabajé en ello. Puede encontrar una presentación en powerpoint en la página web de autores aquí: http://www.vis.uky.edu/~dnister/Publications/publications.html

Algunas otras notas:

  • No me molestaría con el kernel de emparejamiento piramidal, es realmente más para mejorar el reconocimiento de objetos que la detección de imágenes duplicadas / transformadas.

  • No almacenaría ninguna de estas características en una base de datos SQL. Dependiendo de su aplicación, a veces es más efectivo calcular sus características sobre la marcha, ya que su tamaño puede exceder el tamaño de la imagen original cuando se calcula densamente. Los histogtwigs de características o punteros a nodos en un árbol de vocabulario son mucho más eficientes.

  • Las bases de datos SQL no están diseñadas para realizar cálculos masivos de vectores de punto flotante. Puede almacenar cosas en su base de datos, pero no la use como una herramienta para el cálculo. Intenté esto una vez con SQLite y terminó muy mal.

  • Si decide implementar esto, lea el documento en detalle y mantenga una copia a mano mientras lo implementa, ya que hay muchos detalles menores que son muy importantes para hacer que el algoritmo funcione de manera eficiente.

La clave, creo, es que esta no es una pregunta SIFT. Es una pregunta acerca de la búsqueda aproximada de vecinos más cercanos. Al igual que la coincidencia de imágenes, esto también es un problema de investigación abierta. Puede intentar buscar en Google “búsqueda aproximada de vecinos más cercanos” y ver qué tipo de métodos están disponibles. Si necesita resultados exactos, intente: “buscar vecino más cercano”.

El rendimiento de todas estas estructuras de datos geométricos (como los kd-trees) se degrada a medida que aumenta el número de dimensiones, por lo que creo que la clave es que es posible que deba representar sus descriptores SIFT en un número menor de dimensiones (por ejemplo, 10-30). de 256-1024) para tener búsquedas de vecinos más cercanos realmente eficientes (use PCA por ejemplo).

Una vez que tenga esto, creo que se convertirá en secundario si los datos se almacenan en MySQL o no.

Creo que la velocidad no es el problema principal aquí. El problema principal es cómo usar las funciones para obtener los resultados que desea.

Si desea categorizar las imágenes (por ejemplo, persona, automóvil, casa, gato), definitivamente vale la pena mirar el núcleo de Pyramid Match. En realidad, es un histogtwig de los descriptores de características locales, por lo que no es necesario comparar características individuales entre sí. También hay una clase de algoritmos conocida como “bolsa de palabras”, que intenta agrupar las características locales para formar un “vocabulario visual”. Nuevamente, en este caso, una vez que tenga sus “palabras visuales” no necesita calcular distancias entre todos los pares de descriptores SIFT, sino que debe determinar a qué grupo pertenece cada característica. Por otro lado, si desea obtener correspondencias de puntos entre pares de imágenes, como decidir si una imagen está contenida en otra, o calcular la transformación entre las imágenes, entonces necesita encontrar los vecinos más cercanos exactos.

Además, hay características locales distintas de SIFT. Por ejemplo, SURF son características similares a SIFT, pero son más rápidas de extraer y se ha demostrado que funcionan mejor para ciertas tareas.

Si lo único que quiere hacer es encontrar duplicados, puede acelerar su búsqueda considerablemente utilizando un descriptor de imagen global, como un histogtwig de color, para eliminar imágenes que son obviamente diferentes. La comparación de dos histogtwigs de color es más rápida que la comparación de dos conjuntos, cada uno de los cuales contiene cientos de funciones SIFT. Puede crear una lista corta de candidatos usando histogtwigs de color y luego refinar su búsqueda usando SIFT.

Tengo algunas herramientas en Python con las que puedes jugar aquí . Básicamente es un paquete que utiliza vectores transformados SIFT, y luego calcula un hashing de celosía más cercano de cada vector de tamiz 128d. El hash es la parte importante, ya que es sensible a la localidad, simplemente significa que los vectores cercanos al espacio R ^ n dan como resultado probabilidades de colisión de hash equivalentes. El trabajo que proporciono es una extensión de Andoni que proporciona una heurística adaptativa de consulta para eliminar las listas de búsqueda exactas de LSH, así como una implementación CUDA optimizada de la función de hashing. También tengo una aplicación pequeña que realiza búsquedas en la base de datos de imágenes con comentarios visuales agradables, todo bajo bsd (la excepción es SIFT, que tiene algunas restricciones adicionales).