c++ - sirve - ventajas y desventajas de mysql
Comparando las características de SIFT almacenadas en una base de datos mysql (4)
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 en Google el título. 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 Trabajé en ello. Puede encontrar una presentación en powerpoint en la página web de los 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 histogramas 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.
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 subproceso aquí en SO, pero aún no he investigado mucho.
Como no conozco una manera 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 todo el conjunto de datos 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.
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), entonces definitivamente vale la pena mirar el núcleo de Pyramid Match. En realidad, es un histograma 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 trata de agrupar las características locales para formar un "vocabulario visual". Nuevamente, en este caso, una vez que tenga sus "palabras visuales" no necesita calcular las 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 para 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 todo lo que desea hacer es encontrar duplicados, puede acelerar su búsqueda considerablemente utilizando un descriptor de imagen global, como un histograma de color, para eliminar imágenes que son obviamente diferentes. La comparación de dos histogramas de color es más rápida que la comparación de dos conjuntos, cada uno de los cuales contiene cientos de características SIFT. Puede crear una lista corta de candidatos usando histogramas de color y luego refinar su búsqueda usando SIFT.
La clave, creo, es que esta no es una pregunta de 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 del vecino más cercano" y ver qué tipo de métodos están disponibles. Si necesita resultados exactos, intente: "buscar el vecino más cercano".
El rendimiento de todas estas estructuras de datos geométricos (como los kd-trees) se degradan 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.
Tengo algunas herramientas en Python con las que puedes jugar here . 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, lo que 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 pequeña aplicación 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).