titles tag attribute and image image-processing sorting cbir

tag - image title html



Detección de imágenes casi duplicadas (12)

¿Cuál es una forma rápida de ordenar un conjunto dado de imágenes por su similitud entre sí?

Por el momento tengo un sistema que hace un análisis de histograma entre dos imágenes, pero esta es una operación muy costosa y parece demasiado exagerada.

De manera óptima, estoy buscando un algoritmo que dé a cada imagen un puntaje (por ejemplo, un puntaje entero, como el promedio RGB) y puedo ordenar por ese puntaje. Los puntajes idénticos o puntajes uno al lado del otro son posibles duplicados.

0299393 0599483 0499994 <- possible dupe 0499999 <- possible dupe 1002039 4995994 6004994

RGB Promedio por imagen es una mierda, ¿hay algo similar?

Ha habido mucha investigación sobre búsqueda de imágenes y medidas de similitud. No es un problema fácil. En general, una sola int no será suficiente para determinar si las imágenes son muy similares. Tendrás una alta tasa de falsos positivos.

Sin embargo, dado que se ha realizado una gran cantidad de investigaciones, puede echar un vistazo a algunas de ellas. Por ejemplo, este documento (PDF) ofrece un algoritmo de huella dactilar de imagen compacta que es adecuado para encontrar imágenes duplicadas de forma rápida y sin almacenar mucha información. Parece que este es el enfoque correcto si quieres algo sólido.

Si está buscando algo más simple, pero definitivamente más ad-hoc, esta pregunta SO tiene algunas ideas decentes.

Hay una biblioteca C ("libphash" - http://phash.org/ ) que calculará un "hash perceptual" de una imagen y le permitirá detectar imágenes similares al comparar hash (para que no tenga que comparar cada imagen) directamente contra cada otra imagen) pero lamentablemente no parecía ser muy preciso cuando lo probé.

Implementé un algoritmo muy confiable para este llamado Consulta de imagen Fast Multiresolution . Mi (antiguo, no mantenido) código para eso está here .

Lo que Fast Multiresolution Image Querying hace es dividir la imagen en 3 piezas basadas en el espacio de color YIQ (mejor para las diferencias de coincidencia que RGB). Luego, la imagen se comprime esencialmente utilizando un algoritmo de wavelet hasta que solo estén disponibles las características más destacadas de cada espacio de color. Estos puntos se almacenan en una estructura de datos. Las imágenes de consulta pasan por el mismo proceso y las características destacadas de la imagen de consulta se comparan con las de la base de datos almacenada. Cuantas más coincidencias, más posibilidades hay de que las imágenes sean similares.

El algoritmo se usa a menudo para la funcionalidad "consultar por boceto". Mi software solo permitía ingresar imágenes de consulta a través de URL, por lo que no había interfaz de usuario. Sin embargo, encontré que funcionó excepcionalmente bien para unir miniaturas a la versión grande de esa imagen.

Mucho más impresionante que mi software es retrievr que le permite probar el algoritmo FMIQ utilizando imágenes de Flickr como fuente. ¡Muy genial! Pruébelo mediante un boceto o usando una imagen de origen, y podrá ver qué tan bien funciona.

La mayoría de los enfoques modernos para detectar la detección de imágenes casi duplicadas utilizan detecciones de puntos interesantes y descripciones que describen el área alrededor de dichos puntos. A menudo se usa SIFT . Luego puede poner en cuarteto descriptores y usar agrupamientos como vocabulario de palabras visuales.

Entonces, si vemos en la proporción de palabras visuales comunes de dos imágenes a todas las palabras visuales de estas imágenes, se estima la similitud entre las imágenes. Hay muchos artículos interesantes. Uno de ellos es la http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

Tienes que decidir qué es "similar". ¿Contraste? ¿Matiz?

¿Es una imagen "similar" a la misma imagen al revés?

Apuesto a que puedes encontrar muchas "llamadas cercanas" al dividir las imágenes en piezas de 4x4 y obtener un color promedio para cada celda de la grilla. Tendría dieciséis puntajes por imagen. Para juzgar la similitud, simplemente haría una suma de cuadrados de diferencias entre imágenes.

No creo que un solo hash tenga sentido, a menos que sea contra un concepto único como el tono, el brillo o el contraste.

Aquí está tu idea:

0299393 0599483 0499994 <- possible dupe 0499999 <- possible dupe 1002039 4995994 6004994

En primer lugar, supongo que se trata de números decimales que son R * (2 ^ 16) + G * (2 ^ 8) + B, o algo así. Obviamente, eso no es bueno porque el rojo tiene una ponderación desmesurada.

Mudarse al espacio de HSV sería mejor. Puede separar los bits de HSV en el hash, o puede establecer H, S o V individualmente, o puede tener tres hash por imagen.

Una cosa más. Si pesas R, G y B. Peso verde más alto, luego rojo, luego azul para que coincida con la sensibilidad visual humana.

Una imagen tiene muchas características, por lo tanto, a menos que se reduzca a una, como el brillo promedio, se trata de un espacio problemático n-dimensional.

Si te pedí que asignaras un solo entero a las ciudades del mundo, para poder decir cuáles están cerca, los resultados no serían buenos. Por ejemplo, puede elegir la zona horaria como su entero individual y obtener buenos resultados en ciertas ciudades. Sin embargo, una ciudad cerca del polo norte y otra ciudad cerca del polo sur también pueden estar en el mismo huso horario, aunque se encuentren en los extremos opuestos del planeta. Si te dejo usar dos enteros, podrías obtener muy buenos resultados con la latitud y la longitud. El problema es el mismo para la similitud de la imagen.

Dicho todo esto, hay algoritmos que intentan agrupar imágenes similares, que es efectivamente lo que estás pidiendo. Esto es lo que sucede cuando te enfrentas a la detección con Picasa. Incluso antes de identificar las caras, agrupa las similares para que sea fácil pasar por un conjunto de caras similares y otorgarle a la mayoría el mismo nombre.

También existe una técnica llamada Análisis de Componentes Principales, que le permite reducir los datos n-dimensionales a cualquier cantidad menor de dimensiones. Por lo tanto, una imagen con n características podría reducirse a una función. Sin embargo, este no es el mejor enfoque para comparar imágenes.

Una solución es realizar una comparación RMS/RSS en cada par de imágenes necesarias para realizar una clasificación de burbujas. En segundo lugar, podría realizar una FFT en cada imagen y hacer un promedio de ejes para recuperar un único entero para cada imagen que usaría como índice para ordenar. Puede considerar hacer cualquier comparación en una versión redimensionada (25%, 10%) del original, dependiendo de cuán pequeña sea la diferencia que elija ignorar y cuánta aceleración requiera. Avíseme si estas soluciones son interesantes, y podemos analizar o puedo proporcionar un código de muestra.

Yo recomendaría considerar dejar de usar solo un histograma RGB.

Se puede obtener un mejor resumen de tu imagen si tomas una 2d Haar wavelet de la imagen (es mucho más fácil de lo que parece, es solo un promedio y algunas raíces cuadradas se usan para ponderar tus coeficientes) y solo conservas la k más grande coeficientes ponderados en la wavelet como un vector disperso, normalízalo y guárdalo para reducir su tamaño. Debería reescalar RG y B utilizando pesos perceptuales de antemano al menos o recomendaría cambiar a YIQ (o YCoCg, para evitar el ruido de cuantificación) para que pueda muestrear la información de crominancia con importancia reducida.

Ahora puede usar el producto escalar de dos de estos vectores normalizados dispersos como medida de similitud. Los pares de imágenes con los productos de puntos más grandes serán muy similares en estructura. Esto tiene el beneficio de ser ligeramente resistente al cambio de tamaño, cambio de matiz y marca de agua, y ser realmente fácil de implementar y compacto.

Puede cambiar el almacenamiento y la precisión aumentando o disminuyendo k.

Ordenar por un solo puntaje numérico va a ser intratable para este tipo de problema de clasificación. Si lo piensas, requeriría que las imágenes solo puedan ''cambiar'' a lo largo de un eje, pero no es así. Es por eso que necesita un vector de características. En el caso de Haar wavelet es aproximadamente donde ocurren las discontinuidades más agudas en la imagen. Puede calcular una distancia entre imágenes por parejas, pero como todo lo que tiene es una medida de distancia, un ordenamiento lineal no tiene forma de expresar un "triángulo" de 3 imágenes que están todas igualmente distantes. (es decir, piense en una imagen que sea todo verde, una imagen que sea todo roja y una imagen que sea todo azul).

Eso significa que cualquier solución real a su problema necesitará O (n ^ 2) operaciones en la cantidad de imágenes que tenga. Mientras que si hubiera sido posible linealizar la medida, podría requerir solo O (n log n), u O (n) si la medida era adecuada para, por ejemplo, una ordenación de radix. Dicho esto, no es necesario gastar O (n ^ 2) ya que en la práctica no es necesario examinar todo el conjunto, solo necesita encontrar las cosas que están más cerca que un umbral. Por lo tanto, al aplicar una de varias técnicas para particionar su espacio vectorial disperso, puede obtener asíntotas mucho más rápidas para el problema ''encontrándome k de las imágenes que son más similares que un umbral determinado'' que ingenuamente comparando cada imagen con cada imagen, dándole es probable que necesites ... si no precisamente lo que pediste.

En cualquier caso, utilicé esto hace unos años para tener un buen efecto personal al intentar minimizar la cantidad de texturas diferentes que estaba almacenando, pero también ha habido mucho ruido de investigación en este espacio que muestra su eficacia (y en este caso comparando a una forma más sofisticada de clasificación de histograma):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Si necesita una mayor precisión en la detección, los algoritmos minHash y tf-idf se pueden usar con la wavelet Haar (o el histograma) para tratar las ediciones de forma más robusta:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

Finalmente, Stanford tiene una búsqueda de imágenes basada en una variante más exótica de este tipo de enfoque, basada en hacer más extracción de características de las ondículas para encontrar secciones de imágenes giradas o escaladas, etc., pero eso probablemente va más allá de la cantidad de trabajo que Quisiera hacer

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

supuse que otro software de búsqueda de imágenes duplicadas realiza una FFT en las imágenes y almacena los valores de las diferentes frecuencias como vectores:

Image1 = (u1, u2, u3, ..., un) Image2 = (v1, v2, v3, ..., vn)

y luego puede comparar dos imágenes para igualdad calculando la distancia entre los vectores de peso de dos imágenes:

distance = Sqrt( (u1-v1)^2 + (u2-v2)^2 + (u2-v3)^2 + ... (un-vn)^2);