Comparación de dos histogramas


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 más pequeñas, variando de 25 a 100px de ancho. Las imágenes están destinadas a ser de los mismos datos de imagen, pero son diferentes, por lo que una simple comprobación de igualdad de píxeles no funcionará. Considere estos dos escenarios posibles:

  1. Una cámara de seguridad (CCTV) en un museo mirando una exhibición: queremos ver rápidamente si dos fotogramas de video diferentes muestran lo mismo la escena, pero las ligeras diferencias en la iluminación y el enfoque de la cámara significa que no serán idénticas.
  2. Una imagen de un icono GUI de computadora vectorial renderizado a 64x64 en comparación con el mismo icono renderizado a 48x48 (pero ambas imágenes se reducirían a 32x32 para que los histogramas tengan el mismo recuento total de píxeles).

He decidido representar cada imagen usando histogramas, usando tres histogramas 1D: uno para cada canal RGB - es seguro para mí simplemente usar el color e ignorar la textura y el borde histogramas (Un enfoque alternativo utiliza un único histograma 3D para cada imagen, pero estoy evitando que, ya que añade complejidad adicional). Por lo tanto, tendré que comparar los histogramas para ver qué tan similares son, y si la medida de similitud pasa algún valor umbral, entonces puedo decir con confianza que las imágenes respectivas son visualmente las mismas: Estaría comparando los histogramas de canal correspondientes de cada imagen (por ejemplo, el histograma rojo de la imagen 1 con el histograma rojo de la imagen 2, histograma con el histograma azul de la imagen 2, luego los histogramas verdes, así que no estoy comparando el histograma rojo de la imagen 1 con el histograma azul de la imagen 2, eso sería una tontería).

Digamos que tengo estos tres histogramas, que representan un resumen del canal RGB rojo 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 la 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 lo es.

Cuando hice una búsqueda superficial de algoritmos de "diferencia de histograma" (al menos aquellos que podía entender) encontré un enfoque popular que consistía en 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 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;
}

Cuya salida es:

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

Esto es incorrecto.

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

Author: Dai, 2011-06-28

8 answers

Comparar histogramas es un tema en sí mismo.

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

  • Comparación Bin-to-bin : Como usted dijo, la suma estándar de diferencias es bastante mala. Hay una mejora, la distancia Chi-cuadrada , 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.
  • Comparación entre bin: Un ejemplo estándar llamado el bin-similarity matrix requiere alguna matriz de similitud M donde en M(i,j) es la similitud entre los contenedores i y j. Asumir 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 histogramas H1 y H2 sería sqrt((H1-H2)*M*(H1-H2)). Este método tiene en cuenta lo que has dicho acerca de "cerrar" contenedores! La Distancia de Movimiento de la Tierra (EMD) es otro tipo de distancia de compartimiento cruzado.

Para terminar, tengo tres puntos :

  • Deberías leer este artículo sobre la distancia del histograma. Es bastante fácil y te introduce a las distancias del histograma. Todas las distancias de las que hablé se resumen muy bien en el capítulo 1. Honestamente, lo último que se describe en el artículo no es tan complejo, pero probablemente sea excesivo para su caso.
  • La distancia entre bin es muy buena, pero puede ser costosa (es decir : larga de calcular, porque implica una matriz, por lo tanto es O(n^2)). La forma más sencilla de eludir la el costoso cálculo de compartimientos cruzados (y se hace ampliamente) es hacer alguna asignación suave : si un píxel es rojo, entonces debe llenar TODOS los compartimientos que se ven remotamente rojos (por supuesto, dando más peso a los colores más cercanos). A continuación, puede utilizar un algoritmo bin-to-bin.
  • Un poco más centrado en las matemáticas : el punto anterior era todo acerca de la reducción de una comparación bin-a-bin a una comparación bin-a-bin. De hecho, consiste en diagonalizar implícitamente la matriz de similitud M. Si se 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 lo trivial que sea 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
 68
Author: Fezvez,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-02-10 12:35:28

Me sorprende que nadie haya mencionado la implementación opencv de la comparación de histogramas, y pueda manejar fácilmente imágenes multicanal (escala de grises, rgb, rgba, etc) de diferente formato (uchar, float, double, etc)

Incluye los métodos de distancia Bhattacharyya, Chi-Cuadrado, correlación e intersección. Usted puede encontrar el

compareHist(InputArray H1, InputArray H2, int method)

Función en el manual aquí.

 19
Author: nkint,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-12-27 16:40:15

La Distancia del motor de la Tierra (EMD) se usa a menudo para este tipo de comparación de histogramas. EMD utiliza un valor que define el costo en' mover ' píxeles de un bin del histograma a otro, y proporciona el costo total en la transformación de un histograma específico a uno de destino. Cuanto más lejos esté un contenedor, mayor será el costo.

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

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

Hay muchos artículos publicados usando esta técnica para la búsqueda de similitud de la base de datos de imágenes grandes.

 14
Author: tkerwin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-06-27 22:55:28

Encuentro que la prueba de chi-cuadrado es un buen lugar para comenzar al comparar histogramas. Si no tienes el mismo número de entradas en cada histograma tienes que ser un poco más cuidadoso ya que no puedes usar la expresión 'normal'. De memoria, si usted asume que los histogramas tienen números desiguales de entradas la prueba del chi-cuadrado generaliza a

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 bin i del histograma M y ni es el número de entradas en 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 numerical recipes en C tiene un fragmento de código en C y estoy bastante seguro de que está en Matlab. Si usted está más interesado en la diferencia es la forma del histograma y no tanto los valores exactos esto puede ser una mejor prueba también su no paramétrico.

 6
Author: Bowler,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-07-01 14:30:16

Básicamente quieres buscar un distancias de probabilidad. Hay muchos y usted tiene que decidir cuál es el adecuado para su solicitud. Últimamente, he tenido suerte con Chi-squared y Kullback-Leibler.

 4
Author: Chris A.,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-06-27 22:59:43

Normalice sus histogramas dividiendo el valor de cada bin en un histograma entrante por el número total de píxeles en los que se basa el histograma. A continuación, utilice @tkerwin 's EMD.

 2
Author: jilles de wit,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:09:26

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

 0
Author: user8264,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-09-19 09:49:00

Como otros han mencionado, la Distancia del Motor de la Tierra o EMD (también conocida como métrica de Wasserstein) es probablemente la solución óptima. El Método Shortlist para el cálculo rápido de EMD está disponible en el paquete R, transport. Se introdujo en un documento de 2014 comparándolo con otros métodos, mostrando tiempos de cálculo 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ó.

 0
Author: Adam Erickson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-12-08 23:36:58