image processing - superponer - Comparando dos histogramas

superponer graficas en r

Question

Para un proyecto pequeño, necesito comparar una imagen con otra, para determinar si las imágenes son aproximadamente iguales o no. Las imágenes son pequeñas, varían de 25 a 100 píxeles de ancho. Las imágenes están destinadas a tener los mismos datos de imagen, pero son muy diferentes, por lo que una simple comprobación de igualdad de píxeles no funcionará. Considere estos dos posibles escenarios:

1. Una cámara de seguridad (CCTV) en un museo que mira una exposición: queremos ver rápidamente si dos marcos de video diferentes muestran la misma escena, pero pequeñas diferencias en la iluminación y el enfoque de la cámara significa que no serán idénticos.
2. Una imagen de un icono de la interfaz gráfica de usuario de la computadora de vectores representada en 64x64 en comparación con el mismo icono procesado en 48x48 (pero ambas imágenes se reducirán a 32x32 para que los histogramas tengan el mismo recuento total de píxeles).

Decidí representar cada imagen usando histogramas, usando tres histogramas 1D: uno para cada canal RGB. Para mí es seguro usar color e ignorar los histogramas de texturas y bordes (un enfoque alternativo usa un solo histograma 3D para cada imagen, pero lo evito porque agrega complejidad extra). Por lo tanto, tendré que comparar los histogramas para ver qué tan similares son, y si la medida de similitud supera cierto valor umbral, puedo decir con confianza que las imágenes respectivas son visualmente iguales: estaría comparando los histogramas de cada canal de imagen correspondiente (p. Ej. El histograma rojo de 1 con el histograma rojo de la imagen 2, el histograma azul de la imagen 1 con el histograma azul de la imagen 2 y los histogramas verdes, por lo que no comparo el histograma rojo de la imagen 1 con el histograma azul de la imagen 2, sería una tontería).

Digamos que tengo estos tres histogramas, que representan un resumen del canal rojo RGB para tres imágenes (usando 5 contenedores para imágenes de 7 píxeles para simplificar):

H1            H2            H3 

  X           X                     X
  X   X       X       X             X
X X   X X     X X   X X     X X X X X
0 1 2 3 4     0 1 2 3 4     0 1 2 3 4

H1 = [ 1, 3, 0, 2, 1 ]
H2 = [ 3, 1, 0, 1, 2 ]
H3 = [ 1, 1, 1, 1, 3 ] 

La imagen 1 ( H1 ) es mi imagen de referencia, y quiero ver si la Imagen 2 ( H2 ) y / o Imagen 3 ( H3 ) es similar a la Imagen 1. Tenga en cuenta que en este ejemplo, la Imagen 2 es similar a la Imagen 1, pero La imagen 3 no es.

Cuando hice una búsqueda superficial de algoritmos de "diferencia de histograma" (al menos aquellos que pude entender) encontré que un enfoque popular era solo sumar las diferencias entre cada bin, sin embargo, este enfoque a menudo falla porque pesa todas las diferencias de bin de la misma manera.

Para demostrar el problema con este enfoque, en el código C #, así:

Int32[] image1RedHistogram = new Int32[] { 1, 3, 0, 2, 1 };
Int32[] image2RedHistogram = new Int32[] { 3, 2, 0, 1, 2 };
Int32[] image3RedHistogram = new Int32[] { 1, 1, 1, 1, 3 };

Int32 GetDifference(Int32[] x, Int32[] y) {
    Int32 sumOfDifference = 0;
    for( int i = 0; i < x.Length; i++ ) {
        sumOfDifference += Math.Abs( x[i] - y[i] );
    }
    return sumOfDifferences;
}

El resultado de esto es:

GetDifference( image1RedHistogram, image2RedHistogram ) == 6
GetDifference( image1RedHistogram, image3RedHistogram ) == 6

Esto es incorrecto.

¿Hay alguna manera de determinar la diferencia entre dos histogramas que tenga en cuenta la forma de la distribución?

Answer 1

Básicamente, quieres ver las distancias de probabilidad . Hay muchos y debe decidir cuál es el adecuado para su aplicación. Últimamente he tenido suerte con Chi-squared y Kullback-Leibler.

Answer 2

Como han mencionado otros, la distancia o la EMD (también conocida como métrica Wasserstein) de Earth Mover es probablemente la solución óptima. El Método de lista restringida para el cálculo rápido de EMD está disponible en el paquete R, transport . Fue presentado en un documento de 2014 comparándolo con otros métodos, mostrando tiempos de computación más rápidos. El único inconveniente es que está en R, que no es rápido a menos que esté programado en C ++ bajo el capó.

Answer 3

Comparar histogramas es todo un tema en sí mismo.

Tienes dos grandes clases de funciones de comparación: comparación bin-to-bin y comparación de bin-bin.

• Comparación bin-a-bin: Como dijiste, la suma estándar de diferencias es bastante mala. Hay una mejora, la distancia Chi-cuadrado , que dice que si H1.red[0] = 0.001 and H2.red[0] = 0.011 es mucho más importante que si H1.red[0] = 0.1 and H2.red[0] = 0.11 , aunque en ambos casos |H1.red[0] - H2.red[0]| = 0.01 |H1.red[0] - H2.red[0]| = 0.01 .
• Comparación de compartimentos cruzados: Un ejemplo estándar llamado matriz bin-similitud requiere una matriz de similitud M donde M(i,j) es la similitud entre los contenedores i y j. Supongamos que bin[i] es rojo. Si bin[j] es rojo oscuro, entonces M(i,j) es grande. Si bin[j] es verde, M(i,j) es pequeño. Entonces, la distancia entre los histogramas H1 y H2 sería sqrt((H1-H2)*M*(H1-H2)) . ¡Este método tiene en cuenta lo que ha dicho sobre los contenedores "cercanos"! La distancia de movimiento de la Tierra (EMD) es otro tipo de distancia de contenedor cruzado.

Para terminar, tengo tres puntos:

• Deberías leer este artículo sobre la distancia del histograma . Es bastante fácil y te presenta las distancias del histograma. Todas las distancias de las que hablé se resumen muy bien en el capítulo 1. Honestamente, la última cosa descrita en el artículo no es tan compleja, pero probablemente sea excesiva para su caso.
• La distancia entre compartimentos es muy buena, pero puede ser costosa (es decir: larga para calcular, porque involucra una matriz, por lo tanto, es O (n ^ 2)). La forma más sencilla de eludir el costoso cálculo de contenedores cruzados (y está ampliamente hecho) es hacer una asignación suave: si un píxel es rojo, entonces debe llenar TODOS los contenedores que se parecen remotamente al rojo (por supuesto, dar más peso a los colores más cercanos). Luego puede usar un algoritmo bin-to-bin.
• Un poco más centrado en las matemáticas: el punto anterior tenía que ver con la reducción de una comparación de bin a una comparación bin-a-bin. De hecho, consiste en diagonalizar implícitamente la matriz de similitud M. Si puede diagonalizar M = P''*D*P donde P'' es la transposición de P , entonces sqrt((H1-H2)''*M*(H1-H2)) = sqrt((H1-H2)''*P''*D*P*(H1-H2)) = sqrt((P(H1-H2))''*D*(P(H1-H2))) . Dependiendo de cuán trivial es para usted calcular P(H1-H2) , esto puede ahorrarle tiempo de cálculo. Intuitivamente, si H1 es su histograma original, P*H1 es una asignación suave y está utilizando la matriz de similitud implícita M = P''*Id*P

Answer 4

Creo que EMD es una buena solución para resolver problemas de bin cruzado en comparación con el método de bin a bin. Sin embargo, como algunos mencionan, EMD es mucho tiempo. ¿Podrías sugerirme algún otro enfoque para cross-bin?

Answer 5

Encuentro que la prueba de chi-cuadrado es un buen lugar para comenzar cuando comparo los histogramas. Si no tiene el mismo número de entradas en cada histograma, tiene que ser un poco más cuidadoso ya que no puede usar la expresión ''normal''. De la memoria, si supone que los histogramas tienen un número desigual de entradas, la prueba de ji cuadrado se generaliza

1 / (MN) SUM_i [((Mni - Nmi) ^ 2) / (mi + ni)].

M y N son el número total de entradas en cada histograma, mi es el número de entradas en el bin i del histograma M y ni es el número de entradas en el bin i del histograma N.

Otra prueba es la prueba de Kolmogorov-Smirnov. Esta prueba analiza la diferencia máxima entre las distribuciones de probabilidad acumuladas de los dos histogramas. Esto es más difícil de implementar, creo que las recetas numéricas en C tienen un fragmento de código en C y estoy bastante seguro de que está en Matlab. Si está más interesado en la diferencia es la forma del histograma y no tanto en los valores exactos, esta puede ser una mejor prueba y tampoco es paramétrica.

Answer 6

La distancia de Earth Mover (EMD) se usa a menudo para este tipo de comparación de histogramas. EMD usa un valor que define el costo de "mover" píxeles de un contenedor del histograma a otro, y proporciona el costo total para transformar un histograma específico en uno objetivo. Cuanto más lejos esté un cubo, mayor será el costo.

En su ejemplo, mover 5 unidades del rojo [0] al rojo 1 costaría (c*1*5) mientras que mover 5 unidades del rojo [0] al rojo [10] costaría (c*10*5) .

Hay varias implementaciones por ahí. 1 tiene código en C ++, Java y Matlab. Creo que OpenCV también tiene algo de apoyo.

Hay muchos artículos publicados que usan esta técnica para la búsqueda de similitudes de bases de datos de imágenes grandes.

Answer 7

Me sorprende que nadie mencionó la implementación de Opencv de la comparación del histograma, y ​​puede manejar fácilmente imágenes de varios canales (escala de grises, rgb, rgba, etc.) de diferentes formatos (uchar, float, double, etc.)

Incluye la distancia de Bhattacharyya, Chi-Cuadrado, métodos de correlación e intersección. Puedes encontrar el

compareHist(InputArray H1, InputArray H2, int method)

función en el manual here .

Answer 8

Normalice sus histogramas dividiendo el valor en cada contenedor en un histograma entrante por el número total de píxeles en los que se basa el histograma. Luego use el EMD de @tkerwin .