La comparación de dos histogramas

Para un proyecto pequeño, necesito comparar una imagen con otro – para determinar si las imágenes son aproximadamente de la misma o no. Las imágenes son más bien pequeñas, que varían de 25 a 100px de ancho. Las imágenes están destinados a ser de la misma imagen, pero están sublty diferentes, por lo que un simple pixel igualdad de verificación no funciona. Considerar estos dos escenarios posibles:

  1. De seguridad (CCTV) de la cámara en un museo viendo una exposición: queremos ver rápidamente si dos diferentes fotogramas de vídeo muestran la misma escena, pero con ligeras diferencias en la iluminación y el enfoque de la cámara significa que no sean idénticos.
  2. Una imagen de un vector de equipo GUI icono representa en 64 x 64 en comparación con el mismo icono que representa en 48×48 (pero ambas imágenes se reducirá a 32 x 32 para los histogramas tienen la misma cantidad total de píxeles).

Me he decidido a representar a cada imagen usando histogramas, utilizando tres 1D histogramas: uno para cada canal RGB – es seguro para mí el uso del color y a ignorar la textura y el borde de los histogramas (Un enfoque alternativo que usa una sola 3D histograma para cada imagen, pero estoy evitando, a medida que se agrega una complejidad adicional). Por lo tanto voy a necesitar para comparar los histogramas para ver lo que se parecen, y si la medida de similitud pases un valor de umbral, a continuación, puedo decir con confianza las respectivas imágenes visuales en el mismo – yo sería la comparación de cada imagen correspondiente histogramas de canal (por ejemplo, la imagen 1 del histograma rojo con la imagen 2 del histograma rojo, luego la imagen 1 del histograma azul con la imagen 2 del histograma azul, luego verde histogramas – así que no estoy comparando la imagen 1 del histograma rojo con la imagen 2 del histograma azul, eso sería tonto).

Digamos que tengo estos tres histogramas, que representan un resumen de la roja de canal RGB para tres imágenes (con 5 contenedores para la de 7 de imágenes de píxeles por simplicidad):

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 ] 

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 de 2 es similar a la Imagen 1, pero la Imagen 3 no.

Cuando hice un somero de la búsqueda para «histograma » diferencia» de los algoritmos (al menos los que he podido entender) me encontré con un enfoque muy popular fue la suma de las diferencias entre cada contenedor, sin embargo, este método a menudo se produce un error debido a que su peso es de todos bin diferencias de la misma.

Para demostrar el problema con este enfoque, en el código de C#, como este:

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 lo que es:

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

Esto es incorrecto.

Hay una manera de determinar la diferencia entre dos histogramas que toma en cuenta la forma de la distribución?

  • ¿Cuál es su objetivo? Para comparar los histogramas o para encontrar imágenes duplicadas? Si desea que la imagen de comparación, histogramas podría no ser la mejor manera. Te sugiero algo como filtros de gabor.
  • Dado un conjunto de imágenes, todas de las mismas dimensiones, identificar cuáles son duplicados de las otras, sin embargo las imágenes duplicadas se tienen sutiles diferencias entre ellos, como el escalado de objetos y ligeramente diferente coloración.
  • Sólo tengo que señalar que la premisa es errónea. Dos imágenes idénticas histogramas no necesitan ser visualmente la misma. De hecho, pueden ser totalmente diferentes, en todas las formas posibles, pero sólo está compuesta por los mismos colores y en las mismas proporciones. Es la relación espacial entre estos colores que definen lo que se ve una imagen como. También, dos muy similares, las imágenes pueden tener muy diferentes histogramas. Para un ejemplo muy bueno, mire la página 22 en esta tesis.
InformationsquelleAutor Dai | 2011-06-27

8 Kommentare

  1. 75

    La comparación de los histogramas es todo un tema en sí mismo.

    Tienes dos grandes clases de funciones de comparación : bin-a-bin de la comparación y de la cruz-bin comparación.

    • Bin al-bin comparación : Como se dijo, estándar de la suma de las diferencias es bastante malo. Hay una mejora, el Chi-cuadrado de la distancia, 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.
    • Cruz-bin comparación : Un ejemplo estándar llamado la bin-matriz de similitud requiere cierta similitud de la matriz M, donde en M(i,j) es la similitud entre los cubos de basura de i y j. Asumir bin[i] es de color rojo. Si bin[j] es de color rojo oscuro, entonces M(i,j) es grande. Si bin[j] es de color verde, M(i,j) es pequeño. Entonces, la distancia entre los histogramas de H1 y H2 sería sqrt((H1-H2)*M*(H1-H2)). Este método toma en cuenta lo que usted ha dicho acerca de «cerrar» las papeleras! De Movimiento de tierra Distancia (EMD) es otra especie de cruz-bin distancia.

    Para terminar, tengo tres puntos :

    • Usted debe leer este artículo sobre el histograma distancia. Es muy sencillo y presenta el histograma de distancias. Todas las distancias que yo hablaba se resume muy bien el capítulo 1. Honestamente, la última cosa que se describe en el artículo no es muy compleja, pero es probablemente una exageración para su caso.
    • Cruz-bin distancia es muy bueno, pero puede ser costoso (he.e : largo para calcular, porque se trata de una matriz, por lo tanto es O(n^2)). La forma más sencilla para eludir el caro cruz-bin de la computación (y se hace) es hacer un poco de suave asignación : si un píxel es de color rojo, entonces usted debe llenar TODOS los recipientes que son de forma remota el aspecto de rojo (por supuesto, dar más peso a los más cercanos a los colores). A continuación, puede utilizar un bin al-bin algoritmo.
    • Un poco más de matemáticas centrado en : el punto anterior fue todo acerca de la reducción de la cruz-bin comparación a un bin al-bin comparación. De hecho, consiste en implícitamente diagonalizing la matriz de similitud M. Si usted puede diagonalize M = P'*D*P donde P' es la transpuesta 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 es para usted para calcular P(H1-H2), esto le puede ahorrar tiempo de cálculo. Intuitivamente, si H1 es el original de su histograma, P*H1 es una suave asignación y usted está utilizando la implícita matriz de similitud M = P'*Id*P
    • Creo Chi Cuadrado de la distancia puede ser superado por considerar las medidas más precisamente – algunas publicaciones acerca de este 2014-2016 en Matemáticas. ¿Cuál crees que es la situación ahora?
    • Estoy bastante seguro de que el Chi-cuadrado puede ser superado. La situación es que el dominio de conocimiento específico realiza mucho mejor que en general la regla-de-pulgar algoritmo tales como el chi-cuadrado.
    • Alguien ha estudiado el tema acerca de la toma de decisiones de un dominio específico de conocimiento? – – Realmente me gustaría comparar algunos regla-de-pulgar algoritmos (Odds ratio, …) con algún dominio específico de conocimiento, etc en el análisis de regresión logístico etc etc en señales ECG.
    • Por desgracia, aquí es donde mi conocimiento se detiene. Recuerdo que yo tenía que estudiar este campo, porque yo quería histograma de colores para la visión por ordenador. La conclusión final fue que la selección de una adecuada representación de color (se trataba de algo más que RGB) obtuvo resultados mucho mejores que el uso de RGB con lujo de algoritmos. Por supuesto, el mejor fue por medio de una adecuada representación de color Y de fantasía de los algoritmos. De todos modos, no sé mucho más, lo siento
    • Presentación de Color es fácil de sí mismo. Mathematica tiene mejores herramientas para que, en comparación con Matlab. CIELAB/… es con gran visión de computadora. – – Sería genial para entender el funcionamiento de Mathematica mapa de colores de la visión de computadora realmente funcionan. Hay gran algoritmos para la tarea en Mathematica.
    • Siento que usted es banalizar el tema. La representación del color depende del problema en cuestión, y en la misma forma que en el fondo las redes neuronales construir personalizado descriptores que superan hechos a mano de los descriptores, siento que hecho a mano de color de representación, tales como el método CIELAB no siempre ofrecen resultados óptimos.

  2. 23

    Estoy sorprendido de que nadie mencionó opencv implementación del histograma de comparación, y puede manejar fácilmente multicanal imágenes (escala de grises, rgb, rgba, etc) de diferente formato (uchar, float, double, etc)

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

    compareHist(InputArray H1, InputArray H2, int method)
    

    función en el manual aquí.

  3. 14

    Tierra de la empresa de Mudanzas Distancia (EMD) es a menudo utilizado para este tipo de histograma de comparación.
    EMD utiliza un valor que define el costo en ‘movimiento’ píxeles de un bin del histograma a otro, y proporciona el costo total en la transformación de un determinado histograma para un destino de uno. Cuanto más lejos un bin, mayor será el costo.

    En su ejemplo, el desplazamiento de 5 unidades de red[0] a redUno costaría (c*1*5) mientras se mueve a 5 unidades de red[0] rojo[10] costo (c*10*5).

    Hay varias implementaciones de allí. FastEMD tiene el código en C++, Java y Matlab. Creo que OpenCV tiene algún apoyo.

    Hay muchos trabajos publicados en el uso de esta técnica para la gran imagen de la base de datos de búsqueda de similitud.

    • Para los histogramas calculados a partir de diferentes tamaños de imagen, normalizar el histograma dividiendo el valor de cada grupo por el número de píxeles de cada imagen.
    • Sí, usted va a querer normalizar el histograma transformándolo en un PMF (función de masa de probabilidad).
  4. 6

    Puedo encontrar la prueba de chi-cuadrado para ser un buen lugar para empezar cuando la comparación de los histogramas. Si usted no tiene el mismo número de entradas en cada histograma tienes que ser un poco más cuidadoso, ya que no puede utilizar el ‘normal’ de la expresión. De la memoria, si se asume que los histogramas tienen números desiguales de las entradas de la prueba de chi-cuadrado se 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 un bin i de histograma M y ni es el número de entradas en un bin i de histograma N.

    Otra prueba es la prueba de Kolmogorov-Smirnov. Esta prueba examina la máxima diferencia entre el acumulado de las distribuciones de probabilidad de los dos histogramas. Esto es más difícil de implementar, creo recetas numéricos en C tiene un fragmento de código en C y estoy bastante seguro de su en Matlab. Si te interesa más la diferencia es el histograma de la forma y no tanto los valores exactos que esta puede ser una mejor prueba también su no-paramétricas.

  5. 0

    Creo EMD es una buena solución para resolver cruz-bin problema compara con la papelera de reciclaje método. Sin embargo, como algunas menciones, EMD es muy largo de tiempo. Podría usted sugerir a algún otro enfoque para la cruz de reciclaje?

  6. 0

    Como otros han mencionado, la Tierra se mueve a Pie o EMD (aka Wasserstein métrica) es probablemente la solución óptima. La Lista de preseleccionados Método para la rápida EMD de cálculo está disponible en el paquete de R, transporte. Fue introducido en un papel de 2014 comparándolo con otros métodos, mostrando más rápido tiempos de cómputo. El único inconveniente es que está en R, que no es rápido, a menos que programar en C++ bajo el capó.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea