¿Cómo puedo medir la similitud entre dos imágenes? [cerrado]

94

Me gustaría comparar una captura de pantalla de una aplicación (podría ser una página web) con una captura de pantalla tomada anteriormente para determinar si la aplicación se muestra correctamente. No quiero una comparación de coincidencia exacta, porque el aspecto podría ser ligeramente diferente (en el caso de una aplicación web, dependiendo del navegador, algún elemento podría estar en una ubicación ligeramente diferente). Debería dar una medida de qué tan similares son las capturas de pantalla.

¿Existe una biblioteca / herramienta que ya haga eso? ¿Cómo lo implementaría?

Antoine Aubry
fuente
1
Hay algunas buenas respuestas en esta otra pregunta similar: stackoverflow.com/questions/75891/…
blak
1
Es hora de actualizar las respuestas a la luz de los avances recientes en Machine Learning y, más específicamente, en "Deep Learning".
jldupont
Mi laboratorio también necesitaba resolver este problema y usó el flujo de trabajo que se describe aquí: douglasduhaime.com/posts/…
duhaime

Respuestas:

73

Esto depende completamente de cuán inteligente quieras que sea el algoritmo.

Por ejemplo, aquí hay algunos problemas:

  • imágenes recortadas frente a una imagen sin recortar
  • imágenes con un texto agregado frente a otro sin
  • imágenes reflejadas

El algoritmo más fácil y simple que he visto para esto es simplemente realizar los siguientes pasos para cada imagen:

  1. escalar a algo pequeño, como 64x64 o 32x32, ignorar la relación de aspecto, usar un algoritmo de escala de combinación en lugar del píxel más cercano
  2. Escale los rangos de color para que el más oscuro sea el negro y el más claro el blanco.
  3. gire y voltee la imagen para que el color más claro sea el de arriba a la izquierda, y luego el de arriba a la derecha sea el siguiente más oscuro, el de abajo a la izquierda sea el siguiente más oscuro (en la medida de lo posible, por supuesto)

Editar un algoritmo de escalado combinado es aquel que al escalar 10 píxeles a uno lo hará usando una función que toma el color de todos esos 10 píxeles y los combina en uno. Se puede hacer con algoritmos como promediar, valor medio o más complejos como splines bicúbicos.

Luego, calcule la distancia media píxel por píxel entre las dos imágenes.

Para buscar una posible coincidencia en una base de datos, almacene los colores de los píxeles como columnas individuales en la base de datos, indexe algunos de ellos (pero no todos, a menos que use una imagen muy pequeña) y haga una consulta que use un rango para cada uno. valor de píxel, es decir. cada imagen en la que el píxel de la imagen pequeña esté entre -5 y +5 de la imagen que desea buscar.

Esto es fácil de implementar y bastante rápido de ejecutar, pero por supuesto no manejará las diferencias más avanzadas. Para eso necesitas algoritmos mucho más avanzados.

Lasse V. Karlsen
fuente
14
¿Qué es un "algoritmo de escalado combinado"?
Gregg Lind
32

La forma 'clásica' de medir esto es dividir la imagen en un número canónico de secciones (digamos, una cuadrícula de 10x10) y luego calcular un histograma de valores RGB dentro de cada celda y comparar los histogramas correspondientes. Se prefiere este tipo de algoritmo debido tanto a su simplicidad como a su invariancia al escalado y a la traducción (¡pequeña!).

Louis Brandy
fuente
6
¿No es esto similar a hacer un solo histograma para toda la imagen, pero con los inconvenientes adicionales de no ser resistente al espejo y rotar?
dodgy_coder
2 histogramas de 2 mitades de imagen tendrán una mejor precisión de coincidencia que 1 histograma de un todo. Aunque tiene los inconvenientes que mencionaste, depende del problema que estés resolviendo.
psycho brm
25

Utilice un histograma de color normalizado. (Lea la sección sobre aplicaciones aquí ), se usan comúnmente en sistemas de recuperación / coincidencia de imágenes y son una forma estándar de emparejar imágenes que es muy confiable, relativamente rápida y muy fácil de implementar.

Básicamente, un histograma de color capturará la distribución de color de la imagen. Esto luego se puede comparar con otra imagen para ver si las distribuciones de color coinciden.

Este tipo de coincidencia es bastante resistente al escalado (una vez que se normaliza el histograma) y la rotación / desplazamiento / movimiento, etc.

Evite las comparaciones píxel por píxel, ya que si la imagen se gira / desplaza ligeramente, puede dar lugar a que se informe una gran diferencia.

Los histogramas serían sencillos de generar usted mismo (asumiendo que puede obtener acceso a los valores de píxeles), pero si no le apetece, la biblioteca OpenCV es un gran recurso para hacer este tipo de cosas. Aquí hay una presentación de PowerPoint que le muestra cómo crear un histograma usando OpenCV.

Lehane
fuente
14

¿Los algoritmos de codificación de video como MPEG no calculan la diferencia entre cada cuadro de un video para poder codificar el delta? Puede ver cómo los algoritmos de codificación de video calculan esas diferencias de cuadros.

Mire esta aplicación de búsqueda de imágenes de código abierto http://www.semanticmetadata.net/lire/ . Describe varios algoritmos de similitud de imágenes, tres de los cuales son del estándar MPEG-7: ScalableColor, ColorLayout, EdgeHistogram y Auto Color Correlogram.

Marca B
fuente
1
Esto no respondería a la pregunta aquí. La pregunta no es sobre la comparación de píxel por píxel.
Kousha
@Kousha Cierto, pero sigue siendo una dirección interesante para pensar.
significado importa
13

Puede usar un enfoque matemático puro de O(n^2), pero será útil solo si está seguro de que no hay compensación o algo así. (Aunque eso si tiene algunos objetos con colores homogéneos, aún funcionará bastante bien).

De todos modos, la idea es calcular el producto escalar normalizado de las dos matrices. C = sum(Pij*Qij)^2/(sum(Pij^2)*sum(Qij^2)).

Esta fórmula es en realidad el "coseno" del ángulo entre las matrices (extraño). Cuanto mayor sea la similitud (digamos Pij=Qij), C será 1, y si son completamente diferentes, digamos para cada i,j Qij = 1(evitando la división cero) Pij = 255, entonces, para el tamaño nxn, cuanto más grande nsea, más cerca de cero estaremos obtener. (Por cálculo aproximado:) C=1/n^2.

Shachar
fuente
8

Necesitará reconocimiento de patrones para eso. Para determinar pequeñas diferencias entre dos imágenes, las redes Hopfield funcionan bastante bien y son bastante fáciles de implementar. Sin embargo, no conozco ninguna implementación disponible.

Konrad Rudolph
fuente
7

Una solución de rubí se puede encontrar aquí.

Desde el archivo Léame:

Phashion es una envoltura de Ruby alrededor de la biblioteca pHash, "hash perceptual", que detecta archivos multimedia duplicados y casi duplicados.

edk750
fuente
5

Cómo medir la similitud entre dos imágenes depende completamente de lo que le gustaría medir, por ejemplo: contraste, brillo, modalidad, ruido ... y luego elija la mejor medida de similitud adecuada que haya para usted. Puede elegir entre MAD (diferencia media absoluta), MSD (diferencia cuadrática media) que son buenos para medir el brillo ... también está disponible CR (coeficiente de correlación) que es bueno para representar la correlación entre dos imágenes. También puede elegir entre medidas de similitud basadas en histogramas como SDH (desviación estándar del histograma de imagen de diferencia) o medidas de similitud multimodal como MI (información mutua) o NMI (información mutua normalizada).

Debido a que estas medidas de similitud cuestan mucho tiempo, se recomienda reducir la escala de las imágenes antes de aplicar estas medidas en ellas.

Gregor Simončič
fuente
4

Me pregunto (y realmente estoy lanzando la idea para que sea derribada) si algo podría derivarse restando una imagen de la otra, y luego comprimiendo la imagen resultante como un jpeg de gif, y tomando el tamaño del archivo como una medida de similitud.

Si tuviera dos imágenes idénticas, obtendría un cuadro blanco, que se comprimiría realmente bien. Cuanto más difirieran las imágenes, más compleja sería su representación y, por tanto, menos compresible.

Probablemente no sea una prueba ideal, y probablemente mucho más lenta de lo necesario, pero podría funcionar como una implementación rápida y sucia.

Matt Sheppard
fuente
Piense en girar 90 grados; las imágenes siguen siendo similares.
significado importa
3

Puede mirar el código de la herramienta de código abierto findimagedupes , aunque parece haber sido escrito en perl, así que no puedo decir qué tan fácil será analizarlo ...

Al leer la página de findimagedupes que me gustó, veo que hay una implementación en C ++ del mismo algoritmo . Es de suponer que esto será más fácil de entender.

Y parece que también puedes usar gqview .

dmckee --- ex-gatito moderador
fuente
2

Bueno, no para responder a su pregunta directamente, pero he visto que esto sucedió. Microsoft lanzó recientemente una herramienta llamada PhotoSynth que hace algo muy similar para determinar áreas superpuestas en una gran cantidad de imágenes (que podrían tener diferentes proporciones).

Me pregunto si tienen bibliotecas o fragmentos de código disponibles en su blog.

Vaibhav
fuente
1
Esta tecnología. Ha sido descontinuado.
Joseph Rosson
2

Para ampliar la nota de Vaibhav, hugin es un 'autoajuste' de código abierto que debería tener alguna idea del problema.

tostadas caseras
fuente
2

Existe un software para la recuperación de imágenes basada en contenido, que hace (parcialmente) lo que necesita. Todas las referencias y explicaciones están vinculadas desde el sitio del proyecto y también hay un libro de texto breve (Kindle): LIRE

Mathias
fuente
1

Puede usar Siamese Network para ver si las dos imágenes son similares o diferentes siguiendo este tutorial . Este tutorial agrupa las imágenes similares, mientras que puede usar la L2distancia para medir la similitud de dos imágenes.

cpwah
fuente
0

Si esto es algo que va a hacer ocasionalmente y no necesita automatización, puede hacerlo en un editor de imágenes que admita capas, como Photoshop o Paint Shop Pro (probablemente GIMP o Paint.Net también, pero yo ' no estoy seguro de esos). Abra ambas capturas de pantalla y coloque una como capa encima de la otra. Cambie el modo de fusión de capas a Diferencia, y todo lo que sea igual entre los dos se volverá negro. Puede mover la capa superior para minimizar las diferencias de alineación.

Mark Ransom
fuente
Otra herramienta que hace que este tipo de diferenciación sea muy simple es kaleidoscopeapp.com
Michael Osofsky
0

Beyond Compare tiene una comparación píxel por píxel para las imágenes, por ejemplo,

ingrese la descripción de la imagen aquí

emallove
fuente
@xilpex, el OP pregunta: ¿Hay alguna biblioteca / herramienta que ya haga eso ? Mi respuesta incluye un enlace a dicha biblioteca / herramienta.
emallove
-1

Bueno, un método realmente básico para usar podría pasar por cada color de píxel y compararlo con el color de píxel correspondiente en la segunda imagen, pero esa es probablemente una solución muy, muy lenta.

Ross
fuente