Comment évaluer la similitude de deux histogrammes?

Un article récent qui peut valoir la peine dêtre lu est:

Cao, Y. Petzold, L. Limites de précision et mesure des erreurs dans la simulation stochastique de systèmes à réaction chimique, 2006.

Bien que cet article se concentre sur la comparaison dalgorithmes de simulation stochastique, lidée principale est essentiellement de comparer deux histogrammes .

Vous pouvez accéder au pdf depuis la page Web de lauteur.

Commentaires

• Salut, son beau papier, merci davoir donné le lien pdf .. Je ‘ vais sûrement parcourir ce papier ..
• À la place de fournir une référence, il serait bon que vous ‘ résumiez les principaux points de larticle. Les liens meurent, donc à lavenir votre réponse pourrait devenir inutile pour les non-abonnés de ce journal (et la grande majorité de la population humaine est constituée de non-abonnés).

Il existe de nombreux mesures de distance entre deux histogrammes. Vous pouvez lire une bonne catégorisation de ces mesures dans:

K. Meshgi et S. Ishii, « Expanding Histogram of Colors with Gridding to Improve Tracking Accuracy », dans Proc. of MVA15, Tokyo, Japon, mai 2015.

Les fonctions de distance les plus populaires sont répertoriées ici pour votre commodité:

• $ L_0 $ ou Hellinger Distance

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

• $ L_1 $ , Manhattan ou la distance dun pâté de maisons

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

• $ L = 2 $ ou Distance euclidienne

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

• L $ _ {\ infty} $ ou Chybyshev Distance

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

• L $ _ p $ ou fractionnaire Distance (fait partie de la famille de distances de Minkowski)

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

• Intersection dhistogramme

$ 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)} $

• Distance cosinus

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

• Distance 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)} $

• Coefficient de corrélation 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 \ gauche (h_2 (i) – \ frac {1} {n} \ droite) ^ 2}} $

• Divergance Kolmogorov-Smirnov

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

• Distance de correspondance

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

• Distance Cramer-von Mises

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

• $ \ chi ^ 2 $ Statistiques

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

• Distance de Bhattacharyya

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

• Accord carré

$ 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 (cest le premier membre de Distances de transport qui intègrent les informations de regroupement $ A $ dans la distance, pour plus dinformations, veuillez consulter larticle susmentionné ou Wikipedia entrée.

$ 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) $ et $ f_ {ij} $ représente le flux de $ i $ vers $ j $

• Dist quadratique ance

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

• Quadratic-Chi Distance

$ 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) \ droite) \ droite) ^ m} \ droite) \ gauche (\ frac {h_1 (j) – h_2 (j)} {\ gauche (\ sum_c A_ {cj} \ gauche (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ et $ \ frac {0} {0} \ equiv 0 $

Une implémentation Matlab de certaines de ces distances est disponible à partir de mon dépôt GitHub: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Vous pouvez également rechercher des gars comme Yossi Rubner, Ofir Pele, Marco Cuturi et Haibin Ling pour des distances plus modernes.

Mise à jour: Une explication alternative pour les distances apparaît ici et là dans la littérature, donc je les énumère ici par souci dexhaustivité.

• Distance de Canberra (autre version)

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

• Dissimilarité de Bray-Curtis, Distance de Sorensen (depuis la la somme des histogrammes est égale à un, elle est égale à $ 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)} $

• Jaccard Distance (cest-à-dire intersection sur union, une autre version)

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

Commentaires

• Bienvenue sur notre site! Merci pour cette contribution.
• Voici le lien papier: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Merci, une liste est merveilleuse, alors quelle ne permet pas ‘ de créer un opérateur de comparaison pour lhistogramme, par exemple pour dire que hist1 < hist2
• Votre divergence KS est implémentée dans le code comme $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Cela semble incompatible avec léquation que vous avez ci-dessus. Est-ce que je manque quelque chose?
• Je suppose que cest une erreur dans mon code. Je vais examiner cela. Merci de lavoir signalé

La réponse standard à cette question est le test du chi carré . Le test KS concerne les données non groupées et non les données groupées. (Si vous avez les données non groupées, alors utilisez certainement un test de style KS, mais si vous navez que lhistogramme, le test KS nest pas approprié.)

Commentaires

• Vous avez raison de dire que le test KS nest pas approprié pour les histogrammes lorsquil est compris comme un test dhypothèse sur la distribution des données sous-jacentes, mais je ne vois aucune raison pour laquelle la statistique KS ne ‘ t fonctionnerait bien comme mesure de la similitude de deux histogrammes quelconques.
• Une explication des raisons pour lesquelles le test de Kolmogorov-Smirnov nest pas approprié avec des données groupées serait utile.
• Cela peut ne pas être aussi utile dans le traitement dimage que dans lévaluation statistique de lajustement. Souvent, dans le traitement dimage, un histogramme de données est utilisé comme descripteur pour une région dune image, et lobjectif est une distance entre les histogrammes pour refléter la distance entre les patchs dimage. On ne sait pas grand-chose, voire rien du tout, sur les statistiques de population générale des données dimage sous-jacentes utilisées pour obtenir lhistogramme. Par exemple, les statistiques de population sous-jacentes lors de lutilisation dhistogrammes de dégradés orientés différeraient considérablement en fonction du contenu réel des images.
• naught101 ‘ a été répondu par Stochtastic: stats.stackexchange.com/a/108523/37373

Vous « cherchez le test de Kolmogorov-Smirnov . Noubliez pas de diviser les hauteurs des barres par la somme de toutes les observations de chaque histogramme.

Notez que le test KS rapporte également une différence si par exemple les moyennes des distributions sont décalées les unes par rapport aux autres. Si la traduction de lhistogramme le long de laxe des x nest pas significative dans votre application, vous pouvez dabord soustraire la moyenne de chaque histogramme.

Commentaires

• La soustraction de la moyenne modifie la distribution nulle de la statistique KS. @David Wright soulève de toute façon une objection valide à lapplication du test KS aux histogrammes.

Comme La réponse de David souligne que le test du chi carré est nécessaire pour les données groupées car le test KS suppose des distributions continues. En ce qui concerne les raisons pour lesquelles le test KS est inapproprié (commentaire de naught101), il y a eu une discussion sur le problème dans lapplication la littérature statistique qui mérite dêtre soulevée ici.

Un échange amusant a commencé avec laffirmation ( García-Berthou et Alcaraz, 2004 ) quun tiers des articles Nature contiennent des erreurs statistiques. Cependant, un article ultérieur ( Jeng, 2006 , «  Erreur dans les tests statistiques derreur dans les tests statistiques  » – peut-être mon tout- time favorite paper title) ont montré que Garcia-Berthou et Alcaraz (2005) ont utilisé des tests KS sur des données discrètes, ce qui a conduit à rapporter des valeurs p inexactes dans leur méta-étude. Larticle de Jeng (2006) fournit une belle discussion sur la question, montrant même que lon peut modifier le test KS pour quil fonctionne pour des données discrètes. Dans ce cas précis, la distinction se résume à la différence entre une distribution uniforme du chiffre de fin sur [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (dans le test KS incorrect) et une distribution en peigne des fonctions delta, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (sous la forme correcte et modifiée).À la suite de lerreur dorigine, Garcia-Berthou et Alcaraz (2004) ont rejeté à tort la valeur nulle, contrairement au test du chi carré et du KS modifié. Dans tous les cas, le test du chi carré est le choix standard dans ce scénario, même si KS peut être modifié pour fonctionner ici.