• image hash (requiert CImg 1.3+)
• video hash (requiert CImg 1.3+ et FFmpeg)
• audio hash (requiert libsndfile, libsamplerate, libmpg123)

// calcul d'un hash à partir d'un fichier
int ph_dct_imagehash(const char* file,ulong64 &hash);
// calcul de la distance entre deux hash
int ph_hamming_distance(const ulong64 hash1,const ulong64 hash2); 
// utilisé par ph_dct_imagehash
CImg<float>* ph_dct_matrix(const int N);

#if defined( _MSC_VER) || defined(_BORLANDC_)
typedef unsigned _uint64 ulong64;
typedef signed _int64 long64;
#else
typedef unsigned long long ulong64;
typedef signed long long long64;
#endif

Environnement

• Selon les formats d'image désirés, il sera nécessaire d'installer les librairies correspondantes : dans mon cas, libpng, libjpeg et libtiff seront utilisées (installer les versions *-devel). Pour que CImg puisse exploiter ces librairies, les constantes cimg_use_png, cimg_use_jpeg et cimg_use_tiff doivent être définies.
• Les constantes WIN32, WIN64 ou unix doivent être définies en fonction du système d'exploitation pour assurer que CImg charge les bons entêtes. Ici, nous opterons plutôt pour __CYGWIN__.
• Comme nous allons uniquement utiliser les fonctions de lecture et de traitement d'images de CImg, nous pouvons définir cimg_display = 0 pour désactiver les fonctionnalités de création/manipulation de fenêtres.

#define cimg_display 0
#define cimg_use_png
#define cimg_use_jpeg
#define cimg_use_tiff
#define __CYGWIN__

Crash de pHash avec les PNG transparent

int ph_dct_imagehash(const char* file,ulong64 &hash) {
    ...
    CImg<float> img; // img est vide
    if (src.spectrum() == 3) {
        img = src.RGBtoYCbCr().channel(0).get_convolve(meanfilter);
    } else if (src.spectrum() == 4) {
        int width = img.width(); // width = 0
        int height = img.height(); // height = 0
        int depth = img.depth(); // depth = 0
        // les trois variables étant nulles, width-1, height-1 et depth-1 équivalent à -1 => crash de CImg
        img = src.crop(0,0,0,0,width-1,height-1,depth-1,2).RGBtoYCbCr().channel(0).get_convolve(meanfilter);
    } else {
        img = src.channel(0).get_convolve(meanfilter);
    }
    ...

// remplacer ces lignes :
int width = img.width();
int height = img.height();
int depth = img.depth();
// par ces lignes :
int width = src.width();
int height = src.height();
int depth = src.depth();

Gérer les warnings de libpng et libtiff

TIFFReadDirectory: Warning, Unknown field with tag 20624 (0x5090) encountered.
TIFFReadDirectory: Warning, Unknown field with tag 20625 (0x5091) encountered.
TIFFReadDirectory: Warning, Unknown field with tag 33434 (0x829a) encountered.
...
libpng warning: iCCP: known incorrect sRGB profile
libpng warning: iCCP: cHRM chunk does not match sRGB

• Les warnings de libtiff sont levés dès lors qu'un fichier .tif utilise des tags spécifiques à un logiciel ou à une extension du standard. La règle est d'ignorer ces tags, ce que fait libtiff en levant toutefois des warnings.
• Les warnings de libpng sont levés, depuis la version 1.6, dès lors qu'un fichier .png utilise un profil sRGB trop ancien.

freopen("stderr.log", "a", stderr); // a = appending, w = overwrite

Si l'on souhaite aller un peu plus en profondeur et filtrer explicitement les messages, libtiff et libpng proposent tous deux de définir des fonctions qui vont capturer les warnings. Cependant, si libtiff permet de définir un handler global, libpng associe un handler à un png_structp, typiquement lors de la création de la structure en lecture ou en écriture. Aussi, dans le cas de libpng, nous devrons modifier le code de CImg.

void my_tiff_warning_handler(const char *module, const char *fmt, va_list ap) {
    // voir http://libtiff.org/man/TIFFError.3t.html
}

int main(int argc, const char* argv[]) {
    ...
    // définir le nouveau handler
    TIFFErrorHandler oldHandler = TIFFSetWarningHandler(&(my_tiff_warning_handler));
    ...
}

png_voidp user_error_ptr = 0;
// remplacer cette ligne :
png_error_ptr user_error_fn = 0, user_warning_fn = 0;
// par cette ligne :
png_error_ptr user_error_fn = 0, user_warning_fn = &(my_png_warning_handler);
png_structp png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING,user_error_ptr,user_error_fn,user_warning_fn);

void my_png_warning_handler(png_structp png_ptr, png_const_charp warning_message) {
    // voir png_error_ptr dans http://www.libpng.org/pub/png/libpng-manual.txt
}

Sources

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"

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.

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.

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.