¿Cómo evaluar la similitud de dos histogramas?

Un artículo reciente que puede valer la pena leer es:

Cao, Y. Petzold, L. Limitaciones de precisión y medición de errores en la simulación estocástica de sistemas que reaccionan químicamente, 2006.

Aunque el enfoque de este artículo es comparar algoritmos de simulación estocástica, esencialmente la idea principal es cómo comparar dos histogramas .

Puede acceder al pdf desde la página web del autor.

Comentarios

• Hola, es lindo documento, gracias por dar el enlace pdf. Yo ‘ seguramente leeré este documento ..
• En su lugar de proporcionar una referencia, sería bueno que ‘ resumiera los puntos principales del artículo. Los enlaces mueren, por lo que en el futuro su respuesta podría volverse inútil para los no suscriptores de esta revista (y la gran mayoría de la población humana son los no suscriptores).

Hay muchos medidas de distancia entre dos histogramas. Puede leer una buena categorización de estas medidas en:

K. Meshgi y S. Ishii, “Expanding Histogram of Colors con Gridding para mejorar la precisión del seguimiento ”, en Proc. de MVA15, Tokio, Japón, mayo de 2015.

Las funciones de distancia más populares se enumeran aquí para su conveniencia:

• $ L_0 $ o Distancia Hellinger

$ D_ {L0} = \ sum \ limits_ {i} h_1 (i) \ neq h_2 (i) $

• $ L_1 $ , Manhattan o distancia de cuadra de la ciudad

$ D_ {L1} = \ sum_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• $ L = 2 $ o distancia euclidiana

$ D_ { L2} = \ sqrt {\ sum_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2} $

• L $ _ {\ infty} $ o Chybyshev Distancia

$ D_ {L \ infty} = max_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• L $ _ p $ o fraccional Distancia (parte de la familia de distancias de Minkowski)

$ D_ {Lp} = \ left (\ sum \ limits_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert ^ p \ right) ^ {1 / p} $ y $ 0 < p < 1 $

• Intersección de histograma

$ D _ {\ cap} = 1 – \ frac {\ sum_ {i} \ left (min (h_1 (i) , h_2 (i) \ right)} {min \ left (\ vert h_1 (i) \ vert, \ vert h_2 (i) \ vert \ right)} $

• Distancia del coseno

$ D_ {CO} = 1 – \ sum_i h_1 (i) h2_ (i) $

• Distancia de Canberra

$ D_ {CB} = \ sum_i \ frac {\ lvert h_1 (i) -h_2 (i ) \ rvert} {min \ left (\ lvert h_1 (i) \ rvert, \ lvert h_2 (i) \ rvert \ right)} $

• Coeficiente de correlación de Pearson

$ D_ {CR} = \ frac {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right ) \ left (h_2 (i) – \ frac {1} {n} \ right)} {\ sqrt {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right) ^ 2 \ sum_i \ left (h_2 (i) – \ frac {1} {n} \ right) ^ 2}} $

• Kolmogorov-Smirnov Divergance

$ D_ {KS} = max_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Distancia de coincidencia

$ D_ {MA} = \ sum \ limits_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Distancia Cramer-von Mises

$ D_ {CM} = \ sum \ limits_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2 $

• $ \ chi ^ 2 $ Estadísticas

$ D _ {\ chi ^ 2 } = \ sum_i \ frac {\ left (h_1 (i) – h_2 (i) \ right) ^ 2} {h_1 (i) + h_2 (i)} $

• Distancia de Bhattacharyya

$ D_ {BH} = \ sqrt {1- \ sum_i \ sqrt {h_1 (i) h_2 (i)}} $ & hellinger

• Acorde al cuadrado

$ D_ {SC} = \ sum_i \ left (\ sqrt {h_1 (i)} – \ sqrt {h_2 (i)} \ right) ^ 2 $

• Kullback -Liebler Divergance

$ D_ {KL} = \ sum_i h_1 (i) log \ frac {h_1 (i)} {m (i)} $

• Jefferey Divergence

$ D_ {JD} = \ sum_i \ left (h_1 (i) log \ frac {h_1 (i)} {m (i)} + h_2 (i) log \ frac {h_2 (i)} {m (i)} \ right) $

• Earth Mover «s Distance (este es el primer miembro de Distancias de transporte que incorporan información de agrupamiento $ A $ en la distancia. Para obtener más información, consulte el documento mencionado anteriormente o Wikipedia entrada.

$ D_ {EM} = \ frac {min_ {f_ {ij}} \ sum_ {i, j} f_ {ij} A_ {ij}} {sum_ {i, j} f_ {ij}} $ $ \ sum_j f_ {ij} \ leq h_1 (i), \ sum_j f_ {ij} \ leq h_2 (j), \ sum_ {i, j} f_ {ij} = min \ left (\ sum_i h_1 (i) \ sum_j h_2 (j) \ right) $ y $ f_ {ij} $ representa el flujo desde $ i $ a $ j $

• Dist cuadrática ance

$ D_ {QU} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (h_1 (i) – h_2 (j) \ right) ^ 2} $

• Distancia cuadrática-Chi

$ D_ {QC} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (\ frac {h_1 (i) – h_2 (i)} {\ left (\ sum_c A_ {ci} \ left (h_1 (c) + h_2 (c) \ derecha) \ derecha) ^ m} \ derecha) \ izquierda (\ frac {h_1 (j) – h_2 (j)} {\ izquierda (\ sum_c A_ {cj} \ izquierda (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ y $ \ frac {0} {0} \ equiv 0 $

Una implementación de Matlab de algunas de estas distancias está disponible en mi repositorio de GitHub: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance También puedes buscar a tipos como Yossi Rubner, Ofir Pele, Marco Cuturi y Haibin Ling para distancias más avanzadas.

Actualización: La explicación alternativa de las distancias aparece aquí y allá en la literatura, por lo que las enumero aquí para completarlo.

• Distancia de Canberra (otra versión)

$ D_ {CB} = \ sum_i \ frac {| h_1 (i) -h_2 (i) |} {| h_1 (i) | + | h_2 (i) |} $

• Disimilaridad Bray-Curtis, distancia de Sorensen (desde el suma de histogramas es igual a uno, es igual a $ D_ {L0} $ )

$ D_ {BC} = 1 – \ frac {2 \ sum_i h_1 (i) = h_2 (i)} {\ sum_i h_1 (i) + \ sum_i h_2 (i)} $

• Distancia Jaccard (es decir, intersección sobre unión, otra versión)

$ D_ {IOU} = 1 – \ frac { \ sum_i min (h_1 (i), h_2 (i))} {\ sum_i max (h_1 (i), h_2 (i))} $

Comentarios

• ¡Bienvenido a nuestro sitio! Gracias por esta contribución.
• Aquí está el enlace del documento: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Gracias, una lista es maravillosa, mientras que no ‘ no permite crear un operador de comparación para histograma, p. ej. para decir que hist1 < hist2
• Su divergencia de KS se implementa en el código como $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Esto parece inconsistente con la ecuación que tienes arriba. ¿Me falta algo?
• Supongo que es un error en mi código. Voy a mirar en esto. Gracias por señalarlo

La respuesta estándar a esta pregunta es prueba de chi-cuadrado . La prueba KS es para datos no agrupados, no agrupados. (Si tiene los datos no agrupados, utilice una prueba de estilo KS, pero si solo tiene el histograma, la prueba KS no es apropiada).

Comentarios

• Tiene razón en que la prueba KS no es apropiada para histogramas cuando se entiende como una prueba de hipótesis sobre la distribución de los datos subyacentes, pero no veo ninguna razón por la cual la estadística no ‘ t funcionaría bien como una medida de uniformidad de dos histogramas.
• Una explicación de por qué la prueba de Kolmogorov-Smirnov no es apropiada con datos agrupados sería útil.
• Esto puede no ser tan útil en el procesamiento de imágenes como en la evaluación de ajuste estadístico. A menudo, en el procesamiento de imágenes, se utiliza un histograma de datos como descriptor de una región de una imagen y el objetivo es que la distancia entre los histogramas refleje la distancia entre los parches de la imagen. Es posible que se sepa poco, o posiblemente nada en absoluto, sobre las estadísticas de la población general de los datos de imagen subyacentes utilizados para obtener el histograma. Por ejemplo, las estadísticas de población subyacentes al usar histogramas de gradientes orientados diferirían considerablemente en función del contenido real de las imágenes.
• naught101 ‘ la pregunta fue respondida Estochtastic: stats.stackexchange.com/a/108523/37373

Estás buscando la prueba de Kolmogorov-Smirnov . No olvides dividir las alturas de las barras por la suma de todas las observaciones de cada histograma.

Tenga en cuenta que la prueba KS también informa una diferencia si, por ejemplo, las medias de las distribuciones se desplazan entre sí. Si la traslación del histograma a lo largo del eje x no es significativa en su aplicación, es posible que desee restar primero la media de cada histograma.

Comentarios

• Restar la media cambia la distribución nula de la estadística KS. @David Wright plantea una objeción válida a la aplicación de la prueba KS a histogramas de todos modos.

Como La respuesta de David señala que la prueba de chi-cuadrado es necesaria para los datos agrupados, ya que la prueba de KS asume distribuciones continuas. Con respecto a por qué la prueba de KS es inapropiada (comentario de naught101), ha habido cierta discusión sobre el tema en la aplicación literatura estadística que vale la pena plantear aquí.

Un divertido intercambio comenzó con la afirmación ( García-Berthou y Alcaraz, 2004 ) de que un tercio de los artículos de Nature contienen errores estadísticos. Sin embargo, un artículo posterior ( Jeng, 2006 , « Error en pruebas estadísticas de error en pruebas estadísticas «, quizás mi todo) título del artículo favorito en el tiempo) mostró que García-Berthou y Alcaraz (2005) usaron pruebas de KS en datos discretos, lo que llevó a que informaran valores p inexactos en su meta-estudio. El artículo de Jeng (2006) proporciona una buena discusión sobre el tema, incluso mostrando que se puede modificar la prueba KS para que funcione con datos discretos. En este caso específico, la distinción se reduce a la diferencia entre una distribución uniforme del dígito final en [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (en la prueba KS incorrecta) y una distribución de peine de funciones delta, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (en la forma correcta y modificada).Como resultado del error original, García-Berthou y Alcaraz (2004) rechazaron incorrectamente el nulo, mientras que la prueba chi-cuadrado y KS modificada no lo hicieron. En cualquier caso, la prueba de chi-cuadrado es la opción estándar en este escenario, incluso si KS puede modificarse para que funcione aquí.