Comparación de las características de SIFT almacenadas en una base de datos mysql

Question

Actualmente extiendo una biblioteca de imágenes utilizada para categorizar imágenes y quiero encontrar imágenes duplicadas, imágenes transformadas e imágenes que contienen 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 múltiples imágenes. Demasiado rápido, pensé que podría extraer las características y guardarlas en una base de datos, ya que muchos otros metadatos relacionados con imágenes ya se están reteniendo allí.

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

Ya que no sé de una manera de ahorrar y buscar un kd-árbol en una base de datos de manera eficiente, estoy actualmente sólo ver tres opciones:
* Vamos MySQL calcular la distancia euclídea a todas las características de la base de datos , aunque estoy seguro de que tomará un tiempo irrazonable para más de unas pocas imágenes.
* Cargue todo el conjunto de datos en la memoria al principio y construya los kd-tree (s). Esto probablemente sea rápido, pero con mucha memoria. Además, todos los datos deberían transferirse desde la base de datos.
* Guardar los árboles generados en la base de datos y cargarlos a 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 árboles-kd tendrían que reconstruirse y enviarse al servidor.

Estoy usando la implementación SIFT de OpenCV, pero no estoy totalmente equivocado. Si hay un extractor de funciones más adecuado para esta tarea (y más o menos igualmente robusto) me alegra que alguien pueda sugerir uno.

Answer 1

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

Aquí hay un enlace a lo abstracto, se puede encontrar un enlace de descarga por googleing el título. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

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

A otras pocas notas:

• no me molestaría con el núcleo partido pirámide, es realmente más para mejorar el reconocimiento de objetos de duplicar/detección de imágenes transformadas.

• no habría almacenar cualquiera de estas cosas entidad en una base de datos SQL. Dependiendo de su aplicación, es veces más eficaz para calcular sus características sobre la marcha, ya que su tamaño puede exceder el tamaño de la imagen original cuando computarizada densamente. Los histogramas de características o punteros a nodos en un árbol de vocabulario son mucho más eficientes.

• bases de datos SQL no están diseñados para hacer cálculos masivos punto vector flotantes. Puede almacenar cosas en su base de datos, pero no las 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 tenga una copia a mano mientras lo implementa, ya que hay muchos detalles menores que son muy importantes para que el algoritmo funcione de manera eficiente.

Answer 2

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

El rendimiento de todas estas estructuras de datos geométricos (como kd-trees) se degrada a medida que aumenta el número de dimensiones, por lo que la clave es que puede necesitar representar sus descripciones SIFT en un menor número de dimensiones (por ejemplo 10-30 en lugar de 256-1024) para tener búsquedas realmente eficaces en el vecino más cercano (use PCA por ejemplo).

Una vez que tenga esto, creo que se volverá secundario si los datos están almacenados en MySQL o no.

Answer 3

Creo que la velocidad no es el problema principal aquí. El problema principal es cómo usar las características 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 Pyramid Match. En realidad, es un histograma de los descriptores de las características locales, por lo que no es necesario comparar las características individuales entre sí. También hay una clase de algoritmos conocida como la "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 determina a qué grupo pertenece cada característica. Por otro lado, si desea obtener correspondencias de puntos entre pares de imágenes, como para decidir si una imagen está contenida en otra, o para calcular la transformación entre las imágenes, entonces necesita encontrar los vecinos más cercanos.

Además, hay características locales distintos a cribar. 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 todo lo que quiere hacer es encontrar duplicados, puede acelerar su búsqueda considerablemente utilizando un descriptor de imagen global, como un histograma de color, para eliminar las imágenes que son obviamente diferentes. La comparación de dos histogramas de color es mucho más rápida que la comparación de dos conjuntos que contienen cientos de características SIFT. Puede crear una lista breve de candidatos usando histogramas de color y luego refinar su búsqueda utilizando SIFT.

Answer 4

Tengo algunas herramientas en python con las que puedes jugar con here. Básicamente es un paquete que usa vectores transformados SIFT, y luego calcula el hashing de celosía más cercano de cada vector de cribado de 128d. El hash es la parte importante, ya que es sensible a la localidad, lo que significa que los vectores cercanos en el espacio R^n dan como resultado probabilidades de colisión 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 exacta de LSH, así como una implementación CUDA optimizada de la función de hashing. También tengo una pequeña aplicación que realiza búsquedas en la base de datos de imágenes con buenos comentarios visuales, todo bajo bsd (la excepción es SIFT, que tiene algunas restricciones adicionales).