Comparer deux histogrammes

Pour un petit projet, je dois comparer une image avec une autre – pour déterminer si les images sont à peu près identiques ou non. Les images sont petites, variant de 25 à 100 pixels. Les images sont censées être des mêmes données d’image, mais elles sont très différentes, de sorte qu’une simple vérification d’égalité des pixels ne fonctionnera pas. Considérez ces deux scénarios possibles:

  1. Une caméra de sécurité (CCTV) dans un musée regardant une exposition: nous voulons voir rapidement si deux images vidéo différentes montrent la même scène, mais de légères différences d’éclairage et de mise au sharepoint la caméra signifient qu’elles ne seront pas identiques.
  2. Une image d’une icône GUI d’ordinateur vectoriel affichée à 64×64 par rapport à la même icône affichée à 48×48 (mais les deux images seraient réduites à 32×32 pour que les histogrammes aient le même nombre total de pixels).

J’ai décidé de représenter chaque image en utilisant des histogrammes, en utilisant trois histogrammes 1D: un pour chaque canal RVB – il est prudent d’utiliser simplement la couleur et d’ignorer les histogrammes de texture et de bord (une autre approche utilise mais j’évite cela car cela ajoute une complexité supplémentaire). Par conséquent, je devrai comparer les histogrammes pour voir à quel point ils sont similaires et si la mesure de similarité dépasse une valeur de seuil, je peux affirmer que les images respectives sont identiques. 1 histogramme rouge avec l’histogramme rouge de l’image 2, puis l’histogramme bleu de l’image 1 avec l’histogramme bleu de l’image 2, puis les histogrammes verts. Je ne comparerais pas l’histogramme rouge de l’image 1 à l’histogramme bleu de l’image 2.

Disons que j’ai ces trois histogrammes, qui représentent un résumé du canal RVB rouge pour trois images (en utilisant 5 cases pour des images de 7 pixels pour plus de simplicité):

H1 H2 H3 XXX XXXXX XXXXXXXXXXXXX 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 ] 

L’image 1 ( H1 ) est mon image de référence et je veux voir si l’image 2 ( H2 ) et / ou l’image 3 ( H3 ) est similaire à l’image 1. Notez que dans cet exemple, l’image 2 est similaire à l’image 1, mais L’image 3 ne l’est pas.

Lorsque j’ai fait une recherche rapide des algorithmes de “différence d’histogramme” (du moins ceux que je pouvais comprendre), j’ai trouvé qu’une approche populaire consistait simplement à additionner les différences entre chaque casier.

Pour démontrer le problème avec cette approche, en code C #, comme ceci:

 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; } 

Le résultat est:

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

Ceci est une erreur.

Est-il possible de déterminer la différence entre deux histogrammes prenant en compte la forme de la dissortingbution?

La comparaison des histogrammes est un sujet en soi.

Vous avez deux grandes classes de fonctions de comparaison: la comparaison bin-to-bin et la comparaison cross-bin.

  • Comparaison bin-to-bin: Comme vous l’avez dit, la sum standard des différences est assez mauvaise. Il y a une amélioration, la distance du Chi-carré , qui dit que si H1.red[0] = 0.001 and H2.red[0] = 0.011 est beaucoup plus important que si H1.red[0] = 0.1 and H2.red[0] = 0.11 , même si dans les deux cas |H1.red[0] - H2.red[0]| = 0.01 |H1.red[0] - H2.red[0]| = 0.01 .
  • Comparaison de bin-bin: Un exemple standard appelé la masortingce bin-similarity nécessite une masortingce de similarité M où, dans M(i,j) trouve la similarité entre les biners i et j. Supposons que bin[i] est rouge. Si bin[j] est rouge foncé, alors M(i,j) est grand. Si bin[j] est vert, M(i,j) est petit. La distance entre les histogrammes H1 et H2 serait alors sqrt((H1-H2)*M*(H1-H2)) . Cette méthode prend en compte ce que vous avez dit à propos des bacs “proches”! La distance de déplacement de la Terre (EMD) est un autre type de distance croisée.

Pour finir, j’ai trois points:

  • Vous devriez lire cet article sur la distance de l’histogramme . C’est assez facile et vous présente les distances d’histogramme. Toutes les distances dont j’ai parlé se résument bien au chapitre 1. Honnêtement, la dernière chose décrite dans l’article n’est pas si complexe, mais c’est probablement exagéré pour votre cas.
  • La distance entre les cases est très bonne, mais peut être coûteuse (c’est-à-dire longue à calculer, car elle implique une masortingce, donc O (n ^ 2)). Le moyen le plus simple de contourner le calcul coûteux des bacs croisés (et cela est largement pratiqué) consiste à effectuer des affectations souples: si un pixel est rouge, vous devez remplir TOUS les bacs qui ressemblent à du rouge (bien sûr, cela donne plus poids aux couleurs les plus proches). Ensuite, vous pouvez utiliser un algorithme bin-to-bin.
  • Un peu plus centré sur les mathématiques: le point précédent consistait à réduire une comparaison entre cases à une comparaison entre bin et bin. En fait, elle consiste à diagonaliser implicitement la masortingce de similarité M. Si vous pouvez diagonaliser M = P'*D*PP' est la transposée de P , alors sqrt((H1-H2)'*M*(H1-H2)) = sqrt((H1-H2)'*P'*D*P*(H1-H2)) = sqrt((P(H1-H2))'*D*(P(H1-H2))) . En fonction de la facilité avec laquelle vous calculez P(H1-H2) , cela peut vous faire gagner du temps de calcul. Intuitivement, si H1 est votre histogramme d’origine, P*H1 est une affectation douce et vous utilisez la masortingce de similarité implicite M = P'*Id*P

Je suis surpris que personne n’ait mentionné l’implémentation de la comparaison d’histogramme, et que je puisse facilement manipuler des images multicanaux (niveaux de gris, RVB, RVB, etc.) de formats différents (uchar, float, double, etc.).

Comprend les méthodes de distance Bhattacharyya, Chi-carré, de corrélation et d’intersection. Vous pouvez trouver le

 compareHist(InputArray H1, InputArray H2, int method) 

fonction dans le manuel ici .

La distance de déplacement de la terre (EMD) est souvent utilisée pour ce type de comparaison d’histogramme. EMD utilise une valeur qui définit le coût de «déplacement» des pixels d’une corbeille de l’histogramme à une autre et fournit le coût total de la transformation d’un histogramme spécifique en un histogramme cible. Plus un bac est éloigné, plus le coût est élevé.

Dans votre exemple, déplacer 5 unités du rouge [0] au rouge 1 coûterait (c*1*5) en déplaçant 5 unités du rouge [0] au rouge [10] coûterait (c*10*5) .

Il existe plusieurs implémentations. FastEMD a du code en C ++, Java et Matlab. Je crois que OpenCV a aussi un certain support.

De nombreux articles ont été publiés en utilisant cette technique pour la recherche de similarités dans les bases de données d’images volumineuses.

Je trouve que le test du chi-carré est un bon sharepoint départ pour comparer les histogrammes. Si vous n’avez pas le même nombre d’entrées dans chaque histogramme, vous devez être un peu plus prudent car vous ne pouvez pas utiliser l’expression «normale». De mémoire, si vous supposez que les histogrammes ont des nombres d’entrées inégaux, le test du Khi-deux se généralise à

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

M et N sont le nombre total d’entrées dans chaque histogramme, mi est le nombre d’entrées dans la case i de l’histogramme M et ni est le nombre d’entrées dans la case i de l’histogramme N.

Un autre test est le test de Kolmogorov-Smirnov. Ce test examine la différence maximale entre les dissortingbutions de probabilités cumulées des deux histogrammes. C’est plus difficile à mettre en œuvre, je pense que les recettes numériques en C ont un extrait de code en C et sont sûres de Matlab. Si vous êtes plus intéressé par la différence entre la forme de l’histogramme et moins les valeurs exactes, cela peut être un meilleur test aussi non paramésortingque.

Vous voulez essentiellement regarder une distance de probabilité . Il y en a beaucoup et vous devez décider lequel convient le mieux à votre demande. Dernièrement, j’ai eu de la chance avec le Chi-carré et Kullback-Leibler.

Normalisez vos histogrammes en divisant la valeur de chaque case dans un histogramme entrant par le nombre total de pixels sur lesquels l’histogramme est basé. Utilisez ensuite EMD de @tkerwin .

Je pense que EMD est une bonne solution pour résoudre les problèmes croisés par comparaison avec la méthode bin to bin. Cependant, comme certains le mentionnent, EMD est très long. Pourriez-vous me suggérer une autre approche pour le cross-bin?

Comme d’autres l’ont mentionné, la distance de Earth Mover ou EMD (ou mésortingque de Wasserstein) est probablement la solution optimale. La méthode Shortlist pour le calcul rapide EMD est disponible dans le package R, transport . Il a été introduit dans un article de 2014 en le comparant à d’autres méthodes, montrant des temps de calcul plus rapides. Le seul inconvénient est qu’il est en R, ce qui n’est pas rapide sauf en C ++ sous le capot.