Detección de imagen casi duplicada [cerrado]

Question

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

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

Óptimamente, estoy buscando un algoritmo que otorgue a cada imagen una puntuación (por ejemplo, una puntuación entera, como el Promedio RGB) y puedo ordenar por esa puntuación. Puntuaciones idénticas o puntuaciones una al lado de la otra son posibles duplicados.

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

Promedio RGB por imagen apesta, ¿hay algo similar?

Answer 1

Ha habido mucha investigación sobre búsqueda de imágenes y medidas de similitud. No es un problema fácil. En general, un solo int no 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 huella digital de imagen compacta 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.

Answer 2

Recomendaría considerar alejarse de solo usar un histograma RGB.

Se puede obtener un mejor resumen de su imagen si toma una wavelet Haar 2d de la imagen (es mucho más fácil de lo que parece, es solo un promedio y algunas raíces cuadradas utilizadas para ponderar sus coeficientes) y simplemente retiene los k coeficientes ponderados más grandes en la wavelet como vector disperso, normalícelo y guárdelo para reducir su tamaño. Debería reescalar R G y B utilizando pesos perceptuales de antemano al menos o recomendaría cambiar a YIQ (o YCoCg, para evitar el ruido de cuantización) para que pueda muestrear información de crominancia con importancia reducida.

Ahora puede utilizar el producto escalar de dos de estos vectores normalizados dispersos como medida de similitud. Los pares de imágenes con los productos de punto más grandes tendrán una estructura muy similar. Esto tiene la ventaja de ser ligeramente resistente al cambio de tamaño, cambio de tono y marca de agua, y ser realmente fácil de implementar y compacto.

Puede intercambiar almacenamiento y precisión aumentando o disminuyendo k.

Ordenar por un solo puntaje numérico será intratable para este tipo de problema de clasificación. Si lo piensa, requerirá que las imágenes solo puedan 'cambiar' a lo largo de un eje, pero no lo hacen. Es por eso que necesita un vector de características. En el caso de la wavelet de Haar es aproximadamente donde ocurren las discontinuidades más agudas en la imagen. Puede calcular una distancia entre imágenes por parejas, 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 son igualmente distantes. (es decir, piense en una imagen que es toda verde, una imagen que es toda roja y una imagen que es toda azul).

Eso significa que cualquier solución real a su problema necesitará operaciones O (n ^ 2) 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 fuera adecuada para, por ejemplo, una clasificación de radix. Dicho esto, no necesita gastar O (n ^ 2) ya que en la práctica no necesita examinar todo el conjunto, solo necesita encontrar las cosas que están más cerca de un umbral. Entonces, al aplicar una de varias técnicas para dividir su escaso espacio vectorial, puede obtener asintóticos mucho más rápidos para el problema 'encontrarme k de las imágenes que son más similares que un umbral dado' que comparar ingenuamente cada imagen contra cada imagen, dándole lo que probablemente necesites ... si no es exactamente lo que pediste.

En cualquier caso, lo utilicé hace unos años con buenos resultados personalmente al tratar de 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 comparándolo con 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 tratar las ediciones con mayor solidez:

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 wavelets para encontrar secciones de imágenes rotadas o escaladas, etc., pero eso probablemente va mucho más allá de la cantidad de trabajo que te gustaría hacer.

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

Answer 3

Implementé un algoritmo muy confiable para esto llamado Consulta rápida de imágenes de resolución múltiple . Mi código (antiguo, sin mantenimiento) para eso es aquí .

Lo que hace la consulta rápida de imágenes de resolución múltiple es dividir la imagen en 3 partes según el espacio de color YIQ (mejor para hacer coincidir las diferencias que RGB). Luego, la imagen se comprime esencialmente usando 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 en la imagen de consulta se comparan con las de la base de datos almacenada. Cuantas más coincidencias, más probable es que las imágenes sean similares.

El algoritmo se usa a menudo para " consulta por boceto " funcionalidad 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, descubrí que funcionó excepcionalmente bien para hacer coincidir las miniaturas con 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 la fuente ¡Muy genial! Pruébelo a través de un boceto o usando una imagen de origen, y podrá ver qué tan bien funciona.

Answer 4

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 n-dimensional.

Si te pidiera que asignaras un número entero a las ciudades del mundo, para saber cuáles están cerca, los resultados no serían excelentes. Puede, por ejemplo, elegir la zona horaria como su entero único y obtener buenos resultados con ciertas 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, a pesar de que 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 imagen.

Dicho todo esto, hay algoritmos que intentan agrupar imágenes similares, lo que efectivamente es lo que estás pidiendo. Esto es lo que sucede cuando haces detección de rostros con Picasa. Incluso antes de identificar cualquier cara, agrupa a otras similares para que sea fácil pasar por un conjunto de caras similares y dar a la mayoría de ellas 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 número menor de dimensiones. Por lo tanto, una imagen con n características podría reducirse a una característica. Sin embargo, este aún no es el mejor enfoque para comparar imágenes.

Answer 5

Hay una biblioteca C (" libphash " - http://phash.org/ ) que calculará un `` hash perceptual '' de una imagen y le permite 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é.

Answer 6

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

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

Apuesto a que puedes encontrar muchas '' llamadas cerradas '' dividiendo las imágenes en trozos de 4x4 y obteniendo un color promedio para cada celda de la cuadrícula. Tendrías dieciséis puntuaciones por imagen. Para juzgar la similitud, simplemente haría una suma de cuadrados de diferencias entre las imágenes.

No creo que un solo hash tenga sentido, a menos que esté en contra de un solo concepto como tono, brillo o contraste.

Aquí está tu idea:

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

En primer lugar, voy a suponer 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 está ponderado de forma desmesurada.

Moverse al espacio HSV sería mejor. Podría difundir los bits de HSV sale en el hash, o simplemente puede colocar H o ??S o V individualmente, o puede tener tres hash por imagen.

---

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

Una solución es realizar una RMS / RSS en cada par de imágenes requeridas para realizar una clasificación de burbujas. En segundo lugar, puede realizar un FFT en cada imagen y hacer un promedio de algunos 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 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 discutir o puedo proporcionar un código de muestra.

Answer 11

Los enfoques más 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 cuantificar los descriptores y usar grupos como vocabulario visual de palabras.

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

Answer 12

Por ejemplo, usando la extensión IMMI y 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-for-rapidminer-5

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