/dev/log

Blog technique de Benjamin Billet

Le problème de la détection d'images similaires

Rédigé par Benjamin Billet -
Classé dans : Projet similarity-finder - Mots clés : phash, hash perceptuel

A la base de ce projet viens un besoin simple : j'ai accumulé au fil du temps de nombreuses images qui sont dispersées à travers mon disque dur et je veux trouver quelles images sont en double, même avec des tailles et des résolutions différentes. Dans le cas des photos, je souhaite aussi trouver les images dont le cadrage, la colorimétrie ou l'exposition sont légèrement différents.

S'il existe effectivement des logiciels pour trouver des doublons et des images similaires, par exemple Anti-Twin et VisiPics, ils ont toutefois pour inconvénient d'être plutôt lents lorsque le nombre d'images à analyser devient grand. Typiquement, Anti-Twin met plusieurs heures pour analyser un dossier de 25000 images, ce qui m'a conduit à m'intéresser aux algorithmes de comparaison d'images.

Pour détecter des images identiques bit à bit, le calcul d'une empreinte MD5 ou SHA1 suffit, par contre pour détecter des images légèrement différentes nous devons utiliser un algorithme de hashage perceptuel : au lieu de calculer une empreinte à partir des bits qui composent l'image, ces algorithmes calculent une empreinte à partir de ses caractéristiques visuelles. De fait, deux images visuellement proches auront des empreintes proches.

Quelques algorithmes de hashage perceptuel

Histogramme des couleurs

Un histogramme des couleurs représente la distribution des couleurs dans l'image, c'est-à-dire le nombre de pixels dont la couleur appartient à une plage donnée, les différentes plages couvrant la totalité de l'espace colorimétrique (voir cet exemple très parlant). L'histogramme nous donne donc une représentation statistique de l'image, deux images étant analysées en comparant leurs histogrammes. Cette méthode, bien que très simple à implémenter, présente toutefois le désavantage d'être purement colorimétrique : en pratique, deux images aux sujets très différents peuvent avoir des histogrammes très proches.

Moyenne par bloc

Cette méthode est elle aussi assez simple et consiste à diviser l'image en blocs et à calculer la moyenne colorimétrique de chaque bloc. La comparaison se fait en calculant la moyenne des différences de couleur entre les blocs de chaque image, sous réserve que les deux images aient été hashées avec le même nombre de blocs. Cette méthode détecte bien les images ayant été redimensionnée ou recompressée, mais pas les images retaillées.

findimagedupes.pl

Ce script applique des transformations à l'image au moyen de la librairie Image Magick, de façon à extraire une empreinte. Les opérations sont les suivantes, extraites depuis le code du script :

  1. $image->Sample("160x160!"); # redimensionner en 160x160px
  2. $image->Modulate(saturation=>-100); # convertir en niveaux de gris
  3. $image->Blur(radius=>5); # appliquer un flou gaussien pour réduire l'impact du bruit dans la comparaison
  4. $image->Normalize(); # redistribue l'histogramme des gris (a pour effet d'augmenter le contraste)
  5. $image->Equalize(); # égalise l'histogramme des gris (idem)
  6. $image->Sample("16x16"); # redimensionner en 16x16
  7. $image->Threshold(); # réduire à un bit par pixel (bpp) : blanc ou noir
  8. $image->Set(magick=>'mono'); # convertit au format MONO : "bi-level bitmap in least-significant-byte first order"
L'empreinte de l'image transformée est construite à partir des 32 premiers bits. Comparer deux images consiste à appliquer un XOR bit à bit sur les deux empreintes, le score de similarité étant donné par le nombre de bits actifs dans le résultat.

Empreinte fréquentielle (pHash)

Cette approche consiste à filtrer les hautes fréquences spatiales, qui représentent les détails, pour ne garder que les basses fréquences, qui représentent la structure basique de l'image. L'algorithme produit une empreinte de 64 bits et se détaille ainsi :

  1. transformer l'image en niveaux de gris.
  2. redimensionner l'image en 32x32 pixels.
  3. calculer la transformée en cosinus discrète (DCT), qui produit une image 2D (fréquence et scalaire) en niveaux de gris.
  4. extraire les 8x8 pixels du coin supérieur gauche de l'image, cette portion représentant les basses fréquences.
  5. calculer la valeur médiane de ce bloc.
  6. l'empreinte est composée de 64 bits, chaque bit étant mis à 1 si le pixel correspondant a une valeur inférieure à la médiane.
Pour comparer deux images, la distance de hamming doit être calculée entre les deux empreintes. En pratique, d'après mes expériences, deux images très différentes ont une distance supérieure à 14 et deux images fortement similaires ont une distance inférieure à 6.

Empreinte par ondelettes

Cette approche exploite la transformée par ondelette discrète basée sur l'ondelette formulée par le mathématicien Alfréd Haar. Si l'on se penche sur l'implémentation fournie dans ImgSeek, on trouve les opérations suivantes :

  1. redimensionner en 128x128.
  2. convertir dans l'espace YIQ.
  3. décomposer en trois canaux distincts Y, I et Q.
  4. calculer la transformée de Haar, qui produit un tableau de 128x128 coefficients par canal.
  5. sélectionner les 40 coefficients les plus élevés (valeur absolue) de chaque canal, qui forment l'empreinte.
Comparer deux images consiste à calculer un score correspondant à la somme pondérée des coefficients identiques sur les deux images. Voir le code complet pour le détail de la méthode et la liste des poids utilisés.

Conclusion

En pratique, les empreintes fréquentielles et les empreintes par ondelettes obtiennent des résultats assez similaires. J'ai plutôt choisi, dans un premier lieu, de me tourner vers le premier, étant donné l'existence d'une implémentation open source autonome (http://phash.org). Selon les résultats, il sera peut être aussi intéressant d'extraire le code du calcul d'empreinte par ondelette depuis les sources d'ImgSeek.