casi duplicados Detección de imagen

Question

¿Qué es una forma rápida de resolver un determinado conjunto 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.

Optimalmente estoy buscando un algoritmo que dé a cada imagen una puntuación (por ejemplo, una puntuación entera, como el promedio RGB) y puedo ordenar por esa puntuación. 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 Media por imagen, ¿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á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, this paper (PDF) proporciona un algoritmo de huella dactilar de imagen compacta que es adecuado para encontrar imágenes duplicadas rápidamente y sin almacenar mucha información. Parece que este es el enfoque a la derecha si desea algo sólido.

Si está buscando algo más simple, pero definitivamente más ad-hoc, this SO question tiene algunas ideas correctas.

Answer 2

Supuse que otro software de búsqueda de imágenes duplicado 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 se puede comparar dos imágenes para equalness por el cálculo de la distancia entre los vectores de pesos de dos imágenes:

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

Answer 3

Usted tiene que decidir lo que es "similar". ¿Contraste? ¿Matiz?

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

Apuesto a que puede 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 vaya contra un concepto único como el tono, el brillo o el contraste.

Aquí es tu idea:

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

En primer lugar, voy a asumir estos son números decimales que son R * (2^16) + G * (2^8) + B, o algo como eso. Obviamente, eso no es bueno porque el rojo tiene una ponderación desmesurada.

Moving into HSV space sería mejor. Puede spread the bits of HSV out en el hash, o puede ajustar 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.

Answer 4

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 hashes (para que no tenga que comparar cada imagen directamente contra cada otra imagen) pero lamentablemente no parecía ser muy preciso cuando lo probé.

Answer 5

Una solución es realizar una comparación de RMS/RSS en cada par de imágenes necesarias para realizar una clasificación de burbujas. En segundo lugar, podría realizar un 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.

Answer 6

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

Todo lo dicho, 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.

Answer 7

En la era de los servicios web que podría intentar http://tineye.com

Answer 8

he implementado un algoritmo muy fiable para este llamado Fast Multiresolution Image Querying. Mi (antiguo, no mantenido) código para eso es 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 utiliza 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 como fuente las imágenes de Flickr. ¡Muy genial! Pruébelo mediante un boceto o usando una imagen de origen, y podrá ver qué tan bien funciona.

Answer 9

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

Se puede obtener un mejor resumen de su imagen si toma 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 para ponderar sus coeficientes) y solo retenga los k coeficientes ponderados más grandes en la ondícula como un vector disperso, normalícelo y guárdelo para reducir su tamaño. Debería reescalar R G y B usando 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 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 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 sacrificar 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 totalmente verde, una imagen que sea roja y una imagen en azul).

Eso significa que cualquier solución real a su problema necesitará O (n^2) operaciones en el cantidad de imágenes que tienes 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 el número 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 la clasificación histograma):

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

Si necesita una mayor precisión en la detección, el minhash y algoritmos TF-IDF se pueden utilizar con la wavelet Haar (o el histograma) para tratar las ediciones más robustas:

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

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

Answer 10

mayoría de los enfoques modernos para detectar Cerca de duplicar la imagen uso de detección de detección y descriptores que describen el área alrededor de tales puntos puntos interesantes. A menudo se usa SIFT. Luego puede poner en cuarteto descriptores y usar agrupamientos como vocabulario de palabras visuales.

De modo que si vemos 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 Near Duplicate Image Detection: minHash and tf-idf Weighting

Answer 11

La pregunta Good way to identify similar images? parece proporcionar una solución a su pregunta.

Answer 12

Por ejemplo, usando la extensión IMMI y IMMI se puede examinar muchas maneras diferentes de cómo medir la similitud entre las imágenes: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension-for-rapidminer-5

Al definir un umbral y la selección de un método que se puede medir la similitud.