/dev/log

Ajouter le support d'ImageMagick à CImg

Benjamin Billet — Wed, 03 Jun 2015 17:12:00 +0200

Pour lire des fichiers gif, CImg peut utiliser Image Magick (libMagick), à condition de définir la constante cimg_use_magick. En ce qui concerne la configuration de g++, la commande Magick++-config permet de générer les paramètres automatiquement, tout comme wx-config pour wxWidgets :

$> Magick++-config --cxxflags
-fopenmp -DMAGICKCORE_HDRI_ENABLE=0 -DMAGICKCORE_QUANTUM_DEPTH=16 -I/usr/include/ImageMagick-6

Remarque : ne pas oublier d'installer le paquet pkg-config pour que Magick++-config puisse fonctionner.

La configuration d'Eclipse se fait de manière analogue à wx-config (se référer à la note sur le sujet) :

C++ Compiler Ajouter `/bin/Magick++-config --cxxflags` à la commande g++ (adapter le chemin si nécessaire).

C++ Linker Changer le Command Line Pattern en déplaçant le bloc FLAGS à la fin puis ajouter `/bin/Magick++-config --ldflags` dans le champ Linker flags de Miscellaneous

Résoudre le conflit entre wxMSW (wxWidget) et libjpeg

Benjamin Billet — Tue, 02 Jun 2015 22:09:00 +0200

CImg et wxWidget entrent en conflit car CImg importe les entêtes de libjpeg et wxMSW importe les entêtes de l'API WIN32 qui, toutes deux, définissent le type boolean :

/usr/include/jmorecfg.h:234:13: error: conflicting declaration 'typedef int boolean'
 typedef int boolean;
             ^
...
/usr/include/w32api/rpcndr.h:65:25: note: previous declaration as 'typedef unsigned char boolean'
   typedef unsigned char boolean;
                         ^

libjpeg prévoit cette éventualité et permet d'éviter la déclaration de typedef int boolean en définissant la constante HAVE_BOOLEAN. Toutefois, si cette constante est définie, libjpeg ne fonctionne plus correctement, provoquant une erreur dans CImg :

[CImg] *** CImgIOException *** [instance(0,0,0,0,0x0,non-shared)] CImg::load(): Failed to recognize format of file 'images\IMG_6225.jpg'.

Je n'ai, pour le moment, pas trouvé de solution satisfaisante à ce problème, hormis modifier le fichier rpcndr.h de façon à changer la déclaration du type boolean :

[C99] typedef unsigned char boolean; // devient typedef int boolean; [/C99]

Ce changement entraîne un problème dans wtypesbase.h, qui doit lui aussi être modifié pour commenter la déclaration de BOOLEAN :

[C99] // la ligne doit être commentée typedef boolean BOOLEAN; [/C99] Si vous connaissez quelque chose de mieux, merci de m'envoyer un mail et je l'ajouterais ici.

wxWidget : résoudre l'erreur de compilation "undefined reference to `_IID_IPersistFile'", "undefined reference to `glFrustum'", etc.

Benjamin Billet — Thu, 28 May 2015 21:00:00 +0200

Lors de la compilation de wxWidgets (ici 3.0.2), il peut arriver que la compilation échoue sur l'erreur suivante :

g++ -shared -o /home/win7/wxWidgets-3.0.2/lib/cygwxbase30u_gcc_custom-0.dll basedll_version_rc.o basedll_any.o basedll_appbase.o basedll_arcall.o basedll_arcfind.o basedll_archive.o basedll_arrstr.o basedll_base64.o basedll_clntdata.o basedll_cmdline.o basedll_config.o basedll_convauto.o basedll_datetime.o basedll_datetimefmt.o basedll_datstrm.o basedll_dircmn.o basedll_dynarray.o basedll_dynlib.o basedll_dynload.o basedll_encconv.o basedll_evtloopcmn.o basedll_extended.o basedll_ffile.o basedll_file.o basedll_fileback.o basedll_fileconf.o basedll_filefn.o basedll_filename.o basedll_filesys.o basedll_filtall.o basedll_filtfind.o basedll_fmapbase.o basedll_fs_arc.o basedll_fs_filter.o basedll_hash.o basedll_hashmap.o basedll_init.o basedll_intl.o basedll_ipcbase.o basedll_languageinfo.o basedll_list.o basedll_log.o basedll_longlong.o basedll_memory.o basedll_mimecmn.o basedll_module.o basedll_mstream.o basedll_numformatter.o basedll_object.o basedll_platinfo.o basedll_powercmn.o basedll_process.o basedll_regex.o basedll_stdpbase.o basedll_sstream.o basedll_stdstream.o basedll_stopwatch.o basedll_strconv.o basedll_stream.o basedll_string.o basedll_stringimpl.o basedll_stringops.o basedll_strvararg.o basedll_sysopt.o basedll_tarstrm.o basedll_textbuf.o basedll_textfile.o basedll_threadinfo.o basedll_common_time.o basedll_timercmn.o basedll_timerimpl.o basedll_tokenzr.o basedll_translation.o basedll_txtstrm.o basedll_unichar.o basedll_uri.o basedll_ustring.o basedll_variant.o basedll_wfstream.o basedll_wxcrt.o basedll_wxprintf.o basedll_xlocale.o basedll_xti.o basedll_xtistrm.o basedll_zipstrm.o basedll_zstream.o basedll_fswatchercmn.o basedll_fswatcherg.o basedll_basemsw.o basedll_crashrpt.o basedll_debughlp.o basedll_dde.o basedll_msw_dir.o basedll_dlmsw.o basedll_evtloopconsole.o basedll_msw_mimetype.o basedll_power.o basedll_regconf.o basedll_registry.o basedll_msw_snglinst.o basedll_msw_stackwalk.o basedll_msw_stdpaths.o basedll_msw_thread.o basedll_timer.o basedll_msw_utils.o basedll_msw_utilsexc.o basedll_fswatcher.o  basedll_event.o basedll_fs_mem.o basedll_msgout.o basedll_utilscmn.o basedll_main.o basedll_mslu.o basedll_volume.o     -L/home/win7/wxWidgets-3.0.2/lib  -Wl,--out-implib=/home/win7/wxWidgets-3.0.2/lib/libwx_baseu-3.0.dll.a      -lwxregexu-3.0  -lz -lrpcrt4 -loleaut32 -lole32 -luuid -lwinspool -lwinmm -lshell32 -lcomctl32 -lcomdlg32 -ladvapi32 -lwsock32 -lgdi32 -lkernel32 -luser32  -lz -lrpcrt4 -loleaut32 -lole32 -luuid -lwinspool -lwinmm -lshell32 -lcomctl32 -lcomdlg32 -ladvapi32 -lwsock32 -lgdi32 -lkernel32 -luser32
basedll_filename.o:filename.cpp:(.text+0x511c): undefined reference to `IID_IShellLinkW'
basedll_filename.o:filename.cpp:(.text+0x5162): undefined reference to `IID_IPersistFile'
collect2: error: ld returned 1 exit status
Makefile:15531: recipe for target '/home/win7/wxWidgets-3.0.2/lib/cygwxbase30u_gcc_custom-0.dll' failed
make: *** [/home/win7/wxWidgets-3.0.2/lib/cygwxbase30u_gcc_custom-0.dll] Error 1

Cette erreur se produit lorsque libuuid-devel est installé, conduisant l'option -luuid à lier /usr/lib/libuuid.a au lieu de /usr/lib/w32api/libuuid.a. Pour résoudre ce problème, il est nécessaire d'éditer le fichier Makefile et d'ajouter -L /usr/lib/w32api à la variable LDFLAGS. Ainsi, ayant connaissance du répertoire approprié, g++ va lier la bonne librairie.

Une fois ce problème résolu, une autre erreur survient un peu plus tard, indiquant notamment que des éléments d'OpenGL sont manquants :

g++ -shared -o /home/win7/wxWidgets-3.0.2/lib/cygwxmsw30u_gl_gcc_custom-0.dll gldll_version_rc.o gldll_glcmn.o gldll_msw_glcanvas.o    -L/home/win7/wxWidgets-3.0.2/lib  -Wl,--out-implib=/home/win7/wxWidgets-3.0.2/lib/libwx_mswu_gl-3.0.dll.a   -L /usr/lib/w32api  -lwxtiff-3.0 -lwxjpeg-3.0 -lwxpng-3.0    -lwxregexu-3.0 -lwxexpat-3.0 -lz -lrpcrt4 -loleaut32 -lole32 -luuid -lwinspool -lwinmm -lshell32 -lcomctl32 -lcomdlg32 -ladvapi32 -lwsock32 -lgdi32 -lkernel32 -luser32  -lwx_mswu_core-3.0 -lwx_baseu-3.0  -lopengl32 -lglu32 -lz -lrpcrt4 -loleaut32 -lole32 -luuid -lwinspool -lwinmm -lshell32 -lcomctl32 -lcomdlg32 -ladvapi32 -lwsock32 -lgdi32 -lkernel32 -luser32
gldll_glcmn.o:glcmn.cpp:(.text+0x363): undefined reference to `glFrustum'
gldll_glcmn.o:glcmn.cpp:(.text+0x428): undefined reference to `glGetBooleanv'
gldll_glcmn.o:glcmn.cpp:(.text+0x91a): undefined reference to `glColor3f'
gldll_glcmn.o:glcmn.cpp:(.text+0xae1): undefined reference to `glIndexi'
gldll_glcmn.o:glcmn.cpp:(.text+0x371): undefined reference to `glBegin'
gldll_glcmn.o:glcmn.cpp:(.text+0x381): undefined reference to `glTexCoord2f'
gldll_glcmn.o:glcmn.cpp:(.text+0x391): undefined reference to `glVertex3f'
gldll_glcmn.o:glcmn.cpp:(.text+0x3a1): undefined reference to `glNormal3f'
gldll_glcmn.o:glcmn.cpp:(.text+0x3b1): undefined reference to `glColor4f'
gldll_glcmn.o:glcmn.cpp:(.text+0x3c1): undefined reference to `glColor3f'
gldll_glcmn.o:glcmn.cpp:(.text+0x3d1): undefined reference to `glEnd'
collect2: error: ld returned 1 exit status
Makefile:16086: recipe for target '/home/win7/wxWidgets-3.0.2/lib/cygwxmsw30u_gl_gcc_custom-0.dll' failed
make: *** [/home/win7/wxWidgets-3.0.2/lib/cygwxmsw30u_gl_gcc_custom-0.dll] Error 1

Il semble que le lien avec OpenGL ne soit pas fait et doive être ajouté. De la même façon que le problème précédent, il est nécessaire d'aller modifier le fichier Makefile. Il suffit de trouver la variable EXTRALIBS_OPENGL et d'y ajouter -lGl.

Compiler wxWidget 3.0.2 avec cygwin 2.0.0 sous windows

Benjamin Billet — Tue, 26 May 2015 21:01:00 +0200

En premier lieu, il est nécessaire d'installer cygwin (2.0.0) avec les paquets suivants : automake, autoconf, make, gcc-g++.

Concrètement, wxWidgets spécifie un ensemble d'API communes, qui sont implémentées sur différentes plateformes. Pour windows, nous allons compiler wxMSW mais nous pourrions aussi utiliser wxX11 ou wxGTK.

Après s'être placé dans le dossier des sources de wxWidgets-3.0.2 avec la console cygwin, la configuration/compilation est classique :

$> ./configure --with-msw --enable-unicode
$> make
$> make install

Par défaut la compilation construit des librairies dynamiques, les librairies statiques pouvant être générées avec l'option --disable-shared. De nombreuses options sont disponibles pour le ./configure, la liste complète pouvant être obtenue avec :

$> ./configure --help

A noter que wxWidgets est directement fourni avec le code source de ses dépendances, la configuration permettant de préciser s'il est préférable d'utiliser les versions fournies (p. ex. --with-jpeg=builtin) ou les librairies éventuellement installées sur le système (p. ex. --with-jpeg=sys).

Une fois l'installation terminée, la commande suivante devrait être disponible :

$> wx-config --version
3.0.2

Pour un test plus poussé, il est possible de compiler les exemples fournis dans le dossier "samples" :

$> cd samples/treelist
$> make

Après avoir intégré les dll de wxWidgets, disponibles dans wxWidgets-3.0.2/lib, et celles de cygwin (/bin), l'exécutable treelist.exe devrait s'afficher ainsi :

Environnement

J'utilise Eclipse IDE for C/C++ pour gérer le projet mais, globalement, les informations suivantes s'appliquent à tout projet basé sur wxWidget. Le type de projet C/C++ crée est un Makefile project vide. Pour assurer que toutes les options de configurations soient disponibles (constantes, flags, includes, libs, etc.), il faut en outre activer la génération automatique du makefile (options du projet -> C/C++ Build).
Remarque : pour une détection de Cygwin par Eclipse, il suffit d'ajouter simplement le dossier chemin/vers/cygwin/bin au PATH de windows.

C++ Compiler Concrètement, la commande wx-config génère les paramètres cohérents pour g++ :

$> wx-config --static=no --cxxflags --linkdeps
-I/usr/local/lib/wx/include/msw-unicode-3.0 -I/usr/local/include/wx-3.0 -D_FILE_OFFSET_BITS=64 -DWXUSINGDLL -D__WXMSW__

Aussi, la configuration d'Eclipse se fait simplement en ajoutant `/usr/local/bin/wx-config --static=no --cxxflags --linkdeps` à la commande g++ (adapter le chemin si nécessaire).

C++ Linker Ici, il est nécessaire de changer le Command Line Pattern en déplaçant le bloc FLAGS à la fin :

${COMMAND} ${FLAGS} ${OUTPUT_FLAG}${OUTPUT_PREFIX}${OUTPUT} ${INPUTS}
devient
${COMMAND} ${OUTPUT_FLAG}${OUTPUT_PREFIX}${OUTPUT} ${INPUTS} ${FLAGS}

En effet, nous utilisons les flags pour qu'Eclipse construise le makefile avec la commande wx-config à la fin de la commande g++. Pour ce faire, dans Miscellaneous, nous spécifions `/usr/local/bin/wx-config --libs --static=no` dans le champ Linker flags. En outre les paramètres suivants peuvent être ajoutés à ce champ :

-mwindows : ne pas afficher de console à l'ouverture de l'application
-Wl,--enable-auto-import n'est pas toujours nécessaire car activé par défaut dans cygwin : https://sourceware.org/binutils/docs-2.17/ld/WIN32.html

Utiliser windres pour avoir un rendu visuel conforme à Window

Si l'on crée un nouveau projet vierge à partir des fichiers treelist.cpp et treelist.h fourni dans l'exemple samples/treelist et que l'on compile, l'application s'affiche comme suit :

Contrairement à la première capture, les composants graphiques s'affichent ici comme si l'application était exécutée sous Windows 95. Pour résoudre ce problème, il est nécessaire de créer un fichier de ressource (voir Ressource Windows), de le "compiler" avec windres (fourni avec wxWidgets) et de linker la ressource compilée à notre projet.

wxWidgets fournit un fichier de ressource basique, samples/sample.rc :

[C99] ///////////////////////////////////////////////////////////////////////////// // Name: samples/samples.rc // Purpose: a standard Win32 .rc file for the wxWindows samples // Author: Vadim Zeitlin // Modified by: // Created: 04.08.03 // Copyright: (c) 2003 Vadim Zeitlin // Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// // this minimal resource file is all what is needed for most of the wxWindows // samples // note that the icon used by the Explorer (i.e. the programs icon) is the // first icon in the executable and the icons are sorted both by their order // (Win9x) and by alphabetically (!) (NT), so put this icon first and give it // a name starting with "a" aaaaaaaa ICON "sample.ico" // this icon is used with wxFrame::SetIcon() sample ICON "sample.ico" // set this to 1 if you don't want to use manifest resource (manifest resource // is needed to enable visual styles on Windows XP - see docs/msw/winxp.txt // for more information) #define wxUSE_NO_MANIFEST 0 // this is not always needed but doesn't hurt (except making the executable // very slightly larger): this file contains the standard icons, cursors, ... #include "wx/msw/wx.rc" [/C99]

Ce fichier doit être ajouté aux sources du projet Eclipse et sa compilation par windres est spécifiée dans les Pre Build Steps du projet. Il est nécessaire de préciser explicitement le chemin vers les headers de wxWidgets ainsi que le chemin vers le fichier ressource (ici, my_resource_file.rc) : windres -i"../src/my_resource_file.rc" -omy_resource_file_rc.o -I"/usr/local/include/wx-3.0". Enfin, dans la configuration du C++ Linker, nous ajoutons my_resource_file_rc.o à la liste Other Objects de Miscellaneous.

Extraire l'essentiel de pHash 0.9.6

Benjamin Billet — Sat, 23 May 2015 19:47:00 +0200

L'implémentation de pHash 0.9.6 fournit différentes fonctionnalités :

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

Mon problème de recherche d'images similaires ne requiert que la partie image de la librairie pHash, c'est-à-dire une centaine de ligne sur les 2000+ du projet. Concrètement, seules trois fonctions sont nécessaires et peuvent directement être extraites de pHash.cpp : [C99] // 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* ph_dct_matrix(const int N); [/C99] Qui plus est, le bloc permettant d'assurer l'existence du type ulong64 (utilisé pour stocker les hash) doit être récupéré dans pHash.h : [C99] #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 [/C99] Remarque : pour afficher un ulong64 avec un printf, %llu doit être utilisé.

Environnement

CImg se présente sous la forme d'un unique fichier CImg.h qui doit être intégré statiquement au projet. Il est nécessaire de définir les constantes suivante, au niveau du Makefile, du projet Eclipse ou directement dans le code :

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.

[C99] #define cimg_display 0 #define cimg_use_png #define cimg_use_jpeg #define cimg_use_tiff #define __CYGWIN__ [/C99]

Crash de pHash avec les PNG transparent

Lors de mes premiers tests, pHash crashait systématiquement sur les fichiers PNG avec transparence. Après lecture du code, il apparaît qu'il s'agit d'un bug dans ph_dct_imagehash. Le crash est simplement du au fait que les variables width, height et depth du test src.spectrum() == 4 sont assignées à partir de l'image vide img au lieu de l'image à hasher src. [C99] int ph_dct_imagehash(const char* file,ulong64 &hash) { ... CImg 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); } ... [/C99] Concrètement, la modification à effectuer est la suivante : [C99] // 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(); [/C99]

Gérer les warnings de libpng et libtiff

Lors de l'exécution de ph_dct_imagehash, des warnings peuvent apparaître dans la console :

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.

Une méthode simple pour ne plus polluer la console avec ces warnings consiste à rediriger stderr vers un fichier : [C99] freopen("stderr.log", "a", stderr); // a = appending, w = overwrite [/C99]

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.

Cas libtiff (enregistrement global en début de programme) [C99] 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)); ... } [/C99] Cas libpng (enregistrement local dans CImg, au moment où un png_structp pour la lecture est crée) [C99] 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); [/C99] En créant au préalable la fonction vide my_warning_handler. [C99] 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 } [/C99]

Sources

J'ai intégré ce code avec une interface ligne de commande basique, voir la page du projet similarity-finder.

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

Benjamin Billet — Sat, 16 May 2015 18:22:00 +0200

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 :

$image->Sample("160x160!"); # redimensionner en 160x160px
$image->Modulate(saturation=>-100); # convertir en niveaux de gris
$image->Blur(radius=>5); # appliquer un flou gaussien pour réduire l'impact du bruit dans la comparaison
$image->Normalize(); # redistribue l'histogramme des gris (a pour effet d'augmenter le contraste)
$image->Equalize(); # égalise l'histogramme des gris (idem)
$image->Sample("16x16"); # redimensionner en 16x16
$image->Threshold(); # réduire à un bit par pixel (bpp) : blanc ou noir
$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 :

transformer l'image en niveaux de gris.
redimensionner l'image en 32x32 pixels.
calculer la transformée en cosinus discrète (DCT), qui produit une image 2D (fréquence et scalaire) en niveaux de gris.
extraire les 8x8 pixels du coin supérieur gauche de l'image, cette portion représentant les basses fréquences.
calculer la valeur médiane de ce bloc.
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 :

redimensionner en 128x128.
convertir dans l'espace YIQ.
décomposer en trois canaux distincts Y, I et Q.
calculer la transformée de Haar, qui produit un tableau de 128x128 coefficients par canal.
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.