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

93

¿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?

El desconocido
fuente
5
Una pregunta clave, pensando en lo que ha escrito y en algunas de las respuestas a la pregunta relacionada que señaló Naaff, es posible que desee definir más claramente lo que significa "similitud". ¿Sería "similar" una imagen idéntica, pero con cinco píxeles de compensación? Visualmente sí ... pero para un algoritmo ... probablemente no, a menos que lo hayas pensado y lo hayas tenido en cuenta. ¿Puede proporcionar más detalles? ¿Los duplicados serían exactos o simplemente "cercanos"? ¿Está mirando escaneos en los que podrían diferir en una pequeña medida de ángulo? ¿Qué tal la intensidad? Hay muchas variables aquí ...
Beska
¿En qué se diferencian los 'duplicados'? por ejemplo, ¿serían imágenes del mismo lugar con diferentes poses / cambios? Parece que desea algo que sea O (nlog (n)) con el número de imágenes. ¿Alguien sabe si esto es posible? Parece que puede ser ..
Justin Scheiner
@ The Unknown: Si no está satisfecho con alguna de las respuestas actuales, ¿podría darnos más orientación? Hemos hecho todo lo posible para responder a su pregunta, pero sin comentarios es poco probable que encontremos algo mejor.
Naaff
Este es actualmente uno de los grandes problemas no resueltos de la informática. Buena suerte amigo.
john ktejik

Respuestas:

70

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.

Naaff
fuente
2
ese documento es de 2004, ¿no está seguro de si sigue siendo la mejor respuesta?
Andrew
50

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

Edward KMETT
fuente
Parece que está describiendo indirectamente árboles kd y cosas por el estilo para buscar en el espacio posibles candidatos. Podría valer la pena señalar esto.
Boojum
1
Bueno, la razón por la que no especifiqué técnicas más allá de una especie de alusión vaga es que los árboles kd funcionan bien cuando tienes un número relativamente pequeño de dimensiones en tu espacio. Aquí probablemente tenga ~ 128 o más dimensiones que están escasamente pobladas. Dado que son escasos, la mayoría de los valores serán cero, por lo que ir por turnos a través de las dimensiones para particionar en estilo kd es en realidad casi inútil. De la misma manera, los árboles R se rompen, dejando probablemente como su mejor opción: los árboles X. Desafortunadamente, también están cerca del límite de su desempeño cuando se enfrentan a tantas dimensiones.
Edward KMETT
"y simplemente retener los k coeficientes ponderados más grandes en la ondícula como un vector disperso", ¿retener por fila o para toda la ondícula?
ivan.ukr
"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". - ¿y luego que? ¿Wavelet solo para Y o lo hace para todos los canales? Si lo hace para todos los canales, ¿cómo medir la similitud de imágenes con múltiples canales? agregar productos escalares de cada canal y considerar esto como una medida de similitud o debería ser una adición ponderada?
ivan.ukr
15

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.

Luke Francl
fuente
¿Aún puede reconocer imágenes rotadas?
endolito
Dudo que funcione muy bien para eso. Probablemente desee codificar las imágenes para cada rotación para maximizar las coincidencias pertinentes.
Luke Francl
El enlace a retrievr parece estar caído, ¿está archivado en algún lugar?
mmigdol
10

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.

Neil
fuente
1
Es un punto discutible, pero PUEDE usar un solo entero para representar la combinación de cualquier número de características, si, por ejemplo, la característica x = 2 y la característica y = 3 y la característica z = 5 y la característica aa = 7, etcétera, entonces, la potencia a la que se elevó esa base principal en la forma factorizada de un solo entero sería el valor de la característica para esa imagen específica. De nuevo, un punto discutible porque el tamaño del número sería absurdo. Aunque ese tamaño podría reducirse aún más ... solo estamos hablando de datos estructurados.
argyle
Cierto. Pero el punto real es organizar los números de modo que imágenes similares estén juntas numéricamente. A pesar de lo que dije anteriormente, esto es posible. En resumen, podría resolver el problema del vendedor ambulante para encontrar una ruta mínima (o casi mínima) a través de las imágenes en un espacio n-dimensional (donde n es la cantidad de características que desea usar para comparar las imágenes). Pero eso es caro.
Neil
8

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é.

nadie
fuente
5

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.

Nosredna
fuente
5

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

zproxy
fuente
3
El código detrás de tineye parece ser exactamente lo que busca el interrogador, pero no creo que como servicio web sea muy útil, ya que no hay una forma (obvia) de darle dos imágenes y preguntar "¿son iguales? " - la segunda imagen tendría que estar en una página web e indexada por tineye
dbr
1
¿Quizás están proporcionando API para usuarios comerciales? Deberían ser contactados sobre eso.
zproxy
Existe una API comercial que proporciona exactamente eso services.tineye.com/MatchEngine .
Gajus
1

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);
Ian Boyd
fuente
2
La mayoría de las imágenes naturales tienen un contenido de frecuencia muy similar, por lo que dudo que sea una métrica muy buena.
Hannes Ovrén
1

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.

Pablo
fuente
FFT solo le proporciona información de color y ninguna información sobre la posición. El cambio de tamaño ignora todas las características por debajo de un tamaño determinado, independientemente del impacto en la imagen resultante. Una imagen gris y un tablero de ajedrez pueden ser idénticos bajo esa medida. Un enfoque de ondículas (Daubechies, Haar, etc.) tiene las ventajas de proporcionar información de color y posición al intercambiar la proporción de información de color y posición en cada punto de datos.
Edward KMETT
2
No, la FFT de una imagen contiene toda la información espacial del original. Puede reconstruir el original a partir de la FFT. homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm Sin embargo, un histograma, que puede ser lo que estaba pensando, no lo hace.
Paul
1

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

ton4eg
fuente