Detección de imágenes casi duplicadas [cerrado]

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

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

De manera óptima, estoy buscando un algoritmo que le dé a cada imagen una puntuación (por ejemplo, una puntuación entera, como el promedio de RGB) y puedo ordenar por esa puntuación. Puntajes idénticos o puntajes próximos entre sí son posibles duplicados.

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

El promedio de RGB por imagen apesta, ¿hay algo similar?

Se han realizado muchas investigaciones sobre la búsqueda de imágenes y las medidas de similitud. No es un problema fácil. En general, una sola intno será suficiente para determinar si las imágenes son muy similares. Tendrá una alta tasa de falsos positivos.

Sin embargo, dado que se han realizado muchas investigaciones, puede echar un vistazo a algunas de ellas. Por ejemplo, este documento (PDF) proporciona un algoritmo de toma de huellas digitales de imágenes compacto que es adecuado para encontrar imágenes duplicadas rápidamente y sin almacenar muchos datos. Parece que este es el enfoque correcto si quieres algo robusto.

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

Recomendaría considerar dejar de usar un histograma RGB.

Se puede obtener un mejor resumen de su imagen si toma una wavelet de Haar 2d de la imagen (es mucho más fácil de lo que parece, es solo una gran cantidad de promedios y algunas raíces cuadradas que se usan para ponderar sus coeficientes) y simplemente retiene el k más grande coeficientes ponderados en la ondícula como un vector disperso, normalícelo y guárdelo para reducir su tamaño. Debería cambiar la escala de RG y B utilizando pesos perceptivos 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 una 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 punto más grandes serán muy similares en estructura. Esto tiene la ventaja de ser ligeramente resistente al cambio de tamaño, cambio de tono y marca de agua, y es realmente fácil de implementar y compacto.

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

Ordenar por una sola puntuación numérica será intratable para este tipo de problema de clasificación. Si lo piensa, 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 las ondas de Haar, es aproximadamente donde ocurren las discontinuidades más nítidas en la imagen. Puede calcular una distancia entre imágenes por pares, pero dado que todo lo que tiene es una métrica de distancia, un orden 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 completamente verde, una imagen que sea completamente roja y una imagen que sea completamente azul).

Eso significa que cualquier solución real a su problema necesitará operaciones O (n ^ 2) en la cantidad de imágenes que tiene. Mientras que si hubiera sido posible linealizar la medida, podría requerir solo O (n log n) u O (n) si la medida fuera adecuada para, digamos, una ordenación de base. Dicho esto, no necesitas gastar O (n ^ 2) ya que en la práctica no necesitas examinar todo el conjunto, solo necesitas encontrar las cosas que están más cerca de un umbral. Entonces, al aplicar una de varias técnicas para dividir su espacio vectorial disperso, puede obtener asintóticos mucho más rápidos para el problema de 'encontrarme k de las imágenes que son más similares que un umbral dado' que comparar ingenuamente cada imagen con cada imagen, lo que le da lo que probablemente necesite ... si no es precisamente lo que pidió.

En cualquier caso, utilicé esto hace unos años con buenos resultados personalmente cuando intentaba 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 de Haar (o el histograma) para manejar las ediciones de manera más sólida:

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 ondas para encontrar secciones de imágenes rotadas o escaladas, etc., pero eso probablemente va más allá de la cantidad de trabajo que usted necesita. quisiera hacer.

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

Implementé un algoritmo muy confiable para esto llamado Fast Multiresolution Image Querying . Mi código (antiguo, sin mantener) para eso está aquí .

Lo que hace Fast Multiresolution Image Querying es dividir la imagen en 3 partes según el espacio de color YIQ (mejor para igualar diferencias que RGB). Luego, la imagen se comprime esencialmente mediante un algoritmo 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 probabilidades hay de que las imágenes sean similares.

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

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

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

Si le pidiera que asignara un solo entero a las ciudades del mundo, para poder decir cuáles están cerca, los resultados no serían excelentes. Por ejemplo, puede elegir la zona horaria como su único entero y obtener buenos resultados con determinadas ciudades. Sin embargo, una ciudad cerca del polo norte y otra ciudad cerca del polo sur también pueden estar en la misma zona horaria, aunque estén en extremos opuestos del planeta. Si te dejo usar dos enteros, podrías obtener muy buenos resultados con latitud y longitud. El problema es el mismo para la similitud de imágenes.

Dicho todo esto, existen algoritmos que intentan agrupar imágenes similares, que es efectivamente lo que está pidiendo. Esto es lo que sucede cuando haces detección de rostros con Picasa. Incluso antes de identificar cualquier rostro, agrupa los similares para que sea fácil pasar por un conjunto de rostros similares y darles el mismo nombre a la mayoría de ellos.

También existe una técnica llamada Análisis de componentes principales, que le permite reducir los datos n-dimensionales a cualquier número menor de dimensiones. Entonces, una imagen con n características podría reducirse a una característica. Sin embargo, este todavía no es el mejor enfoque para comparar imágenes.

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

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

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

Apuesto a que puede encontrar muchas "llamadas cercanas" dividiendo las imágenes en piezas de 4x4 y obteniendo un color promedio para cada celda de la cuadrícula. Tendría dieciséis partituras 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 solo concepto como tono, brillo o contraste.

Esta es tu idea:

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

Primero que nada, voy a asumir que estos son 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 excesiva.

Pasar al espacio HSV sería mejor. Puede esparcir los bits de HSV en el hash, o simplemente establecer H o ​​S o V individualmente, o podría tener tres hash por imagen.

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

En la era de los servicios web, puede probar http://tineye.com

La pregunta ¿ Buena forma de identificar imágenes similares? parece proporcionar una solución a su pregunta.

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 la 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);

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, puede realizar una FFT en cada imagen y hacer un promedio de ejes para recuperar un solo 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 qué tan pequeña sea la diferencia que elija ignorar y cuánta aceleración requiera. Déjeme saber si estas soluciones son interesantes y podemos discutir o puedo proporcionar un código de muestra.

La mayoría de los enfoques modernos para detectar la detección de imágenes casi duplicadas utilizan la detección de puntos interesantes y descriptores que describen el área alrededor de dichos puntos. A menudo se utiliza SIFT . Luego, puede dividir los descriptores en cinco y utilizar grupos como vocabulario visual de palabras.

Entonces, si vemos una proporción de palabras visuales comunes de dos imágenes a todas las palabras visuales de estas imágenes, estima la similitud entre las imágenes. Hay muchos artículos interesantes. Uno de ellos es Detección de imágenes casi duplicadas: ponderación minHash y tf-idf

Por ejemplo, utilizando la extensión IMMI e IMMI, puede examinar muchas formas diferentes de medir la similitud entre imágenes: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension- para rapidminer-5

Al definir algún umbral y seleccionar algún método, puede medir la similitud.