Vous trouverez les supports de cours à l'adresse : http://mrim.imag.fr/HMUL8R6B/COURS.
Vous trouverez quelques examens des années précédentes à l'adresse : http://mrim.imag.fr/HMUL8R6B/EXAMENS (notez que le programme du cours a pu changer pour les plus anciens).
Le but de ce projet est de réaliser un système de recherche dans une base d'image à partir d'une image requête. Les images sont recherchées dans la base selon la similarité de leurs distributions de couleur ou de mots visuels avec celles de l'image. Le distribution de couleurs sera représentée par un histogramme tridimensionnel de couleurs. Le distribution de mots visuels représentée par un histogramme de descripteurs locaux de type SIFT.
Bien que ce ne soit pas obligatoire, le système pourra fonctionnera sur le web (par la CGI). Une alternative plus simple est de seulement générer une page web puis de l'afficher avec un navigateur. Dans tous les cas, il faut pouvoir afficher l'image requête et une liste des images les plus proches au sens de la couleur et/ou des descripteurs SIFT.
Les images que allez utiliser sont issues du projet VOC 2010 sur la classification automatique d'images (pour information, vous n'avez pas besoin d'étudier ce site).
Vous travaillerez sur la sous collection de test : (test,
9637 images). Le répertoire test contient:
list.txt ;urls.txt .Vous pourrez utiliser les éléments de code : cgiu.h/cgiu.c, utilitaire pour la CGI, et proc.h/proc.c qui contient d'autres fonctions utiles pour la réalisation du projet. Un programme testproc.c vous permet de tester quelques fonctions de ce module et vous montre comment les utiliser. Il se compile avec :
cc cgiu.c proc.c testproc.c -o testproc
(tout n'est pas utile pour ces TPs).
Si vous voulez faire une interface par CGI, vous pouvez partir du formulaire et du programme suivants : form_post4.html et post4.c. Pour plus d'informations à propos de CGI, voir html-cgi.pdf et langageC.pdf.
Vous pouvez regarder le TP2 de l'ancien cours RICM4-RIM pour des informations relatives au placement du formulaire HTML et du programme CGI, ainsi qu'au lien entre les deux avec le serveur HTTP de goedel.
Nous vous fournissons aussi un module pour charger en mémoire des images au format JPEG : rdjpeg.h/rdjpeg.c et un programme exemple qui charge une image en mémoire et affiche les plans rouge, vert et bleu du premier bloc 8×8 ce cette image : read_image.c. Il se compile avec :
cc rdjpeg.c read_image.c -o read_image
Un executable Linux djpeg est fourni pour le cas où il ne serait pas disponible sur votre système. S'il ne fonctionne pas, vous pouvez l'installer sur ubuntu avec la commande :
sudo apt-get install libjpeg-progs
Ça installe tout ce qui concerne le JPEG, y compris djpeg qui doit
alors se retrouver dans /usr/bin .
Il y a deux programmes à écrire (ou un seul avec deux options).
Étapes :
Tri :
Affichage des résultats :
<IMG SRC=“…”> et de rediriger la sortie du programme vers un fichier out.html qu'il n'y a plus qu'à charger dans un navigateur.Il existe des approches qui permettent d'extraire des carcatéristiques visuelles, basées sur des informations localisées autour d'un point d'une image. Ces approches proposent également des manières de déterminer autour de quel point travailler et également à quelle distance autour du point effectuer l'extraction de caractéristique.
L'approche SIFT (pour Scale Invariant Feature Transform) et une approche qui donne de très bons résultats. Il existe quelques programmes qui réalisent cette extraction, comme par exemple colorDescriptor de Koen van de Sande (vous pouvez regarder cela en dehors du TP). Comme ce programme est assez lent (quelques secondes par image…). Nous vous proposons d'utiliser les fichiers générés par ce programme comme source pour votre travail.
L'exécutable Linux 64-bits de colorDescriptor est disponible dans http://mrim.imag.fr/HMUL8R6B/PROJET/colorDescriptor.<br> L'exécutable MacOS de colorDescriptor est disponible dans http://mrim.imag.fr/HMUL8R6B/PROJET/colorDescriptor-mac.<br>
Pour obtenir le fichier sift correspondant à ceux déjà extraits, il faut utiliser la commande :
colorDescriptor --descriptor sift sample.jpg --output sample.sift
Une difficulté de ces approches est qu'il n'y a pas un nombre prédéfini de caractéristiques extraites pour chaque image (à l'inverse de ce qui se passe pour les histogrammes de couleurs vous avez calculés). Il faut alors avoir recours à une étape de clustering (point suivant).
Le programme de Koen van de Sande génère une liste de caractéristiques à 128 dimensions, selon le format suivant :
KOEN1 128 < entier : nb de caractéristiques extraites > (< ligne de caractéristiques >)*
avec une ligne de caractéristiques telle que :
<CIRCLE <entier> <entier> <réel> <entier> <réel>>;entier (entier)*;
Par exemple :
<CIRCLE 159 154 1.78381 0 0.000296159>; 0 0 31 20 8 0 0 0 0 2 13 13 2 0 10 10 0 4 22 2 0 7 32 4 0 2 18 3 1 4 12 0 7 0 0 6 16 0 0 3 99 7 0 1 2 1 59 140 22 4 0 0 0 100 140 69 0 0 0 0 0 44 140 11 11 4 0 6 16 0 0 0 140 140 19 0 1 0 6 33 56 114 140 15 1 35 75 22 0 8 140 16 1 15 116 9 0 1 0 4 14 0 0 0 10 62 28 1 1 0 0 0 1 39 140 7 0 0 0 0 8 3 140 7 0 0 5 18;
qui veut dire que dans la région de centre (159,154) une caractéristique à été extraite à une échelle 1,78381 avec une orientation de 0 et un degré de visibilité de 0.000296159.
Afin de pouvoir utiliser ces caractéristiques pour le clustering, il faut les mettre en forme, c'est-à-dire éliminer les informations autres que les caractéristiques elles-mêmes. Pour cela, on élimine les entêtes (les 3 premières lignes d'un fichier généré par colorDescriptor), on enlève aussi la partie “tag” des lignes de caractéristiques, sans oublier d'enlever les “;”. TRES IMPORTANT : une ligne ne doit pas se terminer par un espace (le retour charriot doit être juste après la dernière dimension).
Il vous est donc demandé de créer, pour chaque fichier sift de l'ensemble test fourni en /home/Public/quenotg/HMUL8R6B/PROJET/test/sift/, les fichiers nettoyés en ne gardant qu'une ligne sur 150. Il vous est demandé d’éviter de générer toutes les lignes pour des raisons de place occupée sur disque.
Le problème avec le compte quenotg à l'UFR a été réglé et les données sont maintenant accessibles comme elles le devraient, il faut par contre utiliser un chemin différent : /home/Public/quenotg/HMUL8R6B/PROJET.
Ensuite, vous aller concaténer tous ces fichiers (rappelons que ces fichiers ne contiennent qu'une ligne de caractéristiques toutes les 150 par exemple) afin de créer un fichier samples.txt qui n'a pas trop d'échantillons (plus le nombre d'échantillons est grand, plus le clustering va nécessiter de la mémoire et plus le traitement sera long, jusqu'à… plusieurs jours, et des dizaines de GB…). C'est ce fichier qui va être utiliser pour le clustering.
L'objectif du fichier samples.txt est de générer des regroupements (clusters) on en fixe a priori le nombre. Pour cela, nous allons utiliser le logiciel R
R est un environnement gratuit pour des calculs statistique. Il permet en particulier de réaliser du clustering automatique.
Nous vous fournissons ici les instructions R qui permettent de réaliser un clustering de type Kmoyennes (Kmeans en anglais). Pour cela, vous devez récupérer le code kmeans_clustering.R, et de l'utiliser de la manière suivante :
R --slave --no-save --no-restore --no-environ --args ./samples.txt 256 ./centers256.txt 10 < kmeans_clustering.R
Cet appel indique que l'on utilise R en mode non interactif, avec pour arguments : le fichier samples.txt, le nombre de clusters attendu (ici 256), le fichier qui va stocker les centroïdes des clusters, et enfin le nombre d'itérations pour le clustering (ici 10).
Le résultat de cet appel est donc la génération des centroïdes de chaque cluster. Cette étape est longue et peut prendre 10 minutes pour s'éxécuter, évitez donc de le lancer plusieurs fois. Il faut ensuite passer en revue chaque caractéristique visuelle extraite pour lui assigner son cluster, c'est l'objectif de l'étape suivante : le mapping.
NOTE : R n'est pas installé sur toutes les machines de l'ufr. Il est installé sur mandelbrot, vous devez donc vous connecter sur mandelbrot pour l'utiliser..
Le mapping consiste à déterminer, pour chaque caractéristique visuelle extraite, le cluster qui lui correspond (dont le centroide est le plus proche.
Pour cela, nous allons encore faire appel à R, avec le code qui vous est fourni en 1nn.R. Le nom 1nn vient du fait que l'on trouve, pour une caractéristique le plus proche voisin, c'est-à-dire le “One Nearest Neighbour” (1nn). Ce code appelle R et lui demande, pour chaque élément d'une liste de caractéristriques, de renvoyer l'identifiant du cluster auquel il est rattaché. NOTE : le numéro de cluster commence à 1.
Un utilisation type de ce code est :
R --slave --no-save --no-restore --no-environ --args centers256.txt 256 all_for_R_demo_30 res1nn.txt < 1nn.R
qui indique que R attend le fichier de centroïdes (généré précédemment), qu'il travaille sur 256 dimensions (clusters), qu'il doit s'appliquer sur un fichier appelé ici all_for_R_demo_30 et mettre de résultat dans le fichier res1nn.txt. Bien entendu, les noms de fichiers sont indicatifs.
Pour un fichier de caractéristiques composé de 3 lignes:
0 0 1 0 0 0 0 0 0 0 0 1 13 1 0 0 1 0 0 0 41 8 3 4 6 8 1 6 74 1 0 0 1 28 29 12 2 3 2 0 8 9 48 34 40 14 4 4 8 2 2 3 172 94 74 19 65 29 4 16 172 109 9 14 0 9 11 8 7 35 31 2 26 11 23 16 11 32 41 49 23 3 2 9 169 64 18 30 38 0 0 1 172 172 132 73 1 14 33 9 2 6 9 2 6 13 49 17 0 5 13 11 9 10 15 13 33 24 7 7 0 0 5 7 27 77 107 20 2 0 0 0 2 0 0 2 14 3 1 0 0 0 3 26 14 17 29 28 10 0 0 4 0 0 3 20 17 0 0 0 57 1 0 4 5 0 0 21 119 18 10 6 20 43 40 119 21 35 119 119 96 65 12 13 0 0 23 83 35 2 0 0 70 21 0 1 14 15 4 3 119 119 106 21 32 30 11 27 16 38 62 43 119 119 39 6 1 0 1 3 8 108 23 1 6 9 1 4 36 23 5 0 14 59 70 2 0 1 1 0 119 119 41 11 6 41 25 12 25 20 17 52 83 119 26 9 9 22 23 10 0 0 0 0 21 23 24 20 2 0 0 0 5 7 12 46 28 1 1 0 0 0 0 2 10 4 9 16 60 61 99 87 27 0 0 10 115 115 115 115 9 0 0 6 58 43 92 115 52 8 29 21 17 9 2 30 45 36 84 83 44 27 14 81 38 1 1 7 85 51 31 81 26 0 0 11 73 115 31 71 17 0 3 8 28 111 25 56 78 25 10 7 2 1 0 6 12 6 115 90 0 3 22 34 20 3 19 71 0 8 43 17 14 1 0 78 0 12 51 32 43 12 3 49 0
Le résultat généré est de la forme :
189 101 146
Qui indique que la première caractéristique est assignée au cluster numéro 189, la seconde au cluster 101 et la troisième au cluster 146.
Vous devez donc, à partir du fichier de caratéristiques de chaque image de test, générer le fichier de mapping et le stocker.
Pour simplifier votre problème, nous vous fournissons le code (shell script) qui permet de génerer les fichiers de mapping en process_1nn_sift.sh. Ce code suppose que :
sift/test/1nn à partir du répertoire courant,centers256.txt . Vous pouvez changer cela en éditant ce fichier.
Le fichier résultat est une liste des numéros des centres de cluster les plus proches. Il y en a un par image. Il faut ensuite faire un histogramme par image de ces numéros de centres, ces numéros étant les catégories.
Ensuite, tout se passe comme avec les histogrammes de couleur.
La recherche combinée s'effectue en fusionnant les valeurs des distances selon la couleur et selon les mots visuels. La fusion peut être effectuée soit par une moyenne, éventuellement pondérée, soit par un opérateur maximum entre les deux distances. Avant le moyennage ou l'application de l'opérateur maximum, il convient de normaliser les distances par modalité (couleur ou texture). La normalisation peut se faire au niveau des descripteurs avant le calcul de la distance en divisant tous les descripteurs (requête et images de la base) par la norme moyenne des descripteurs des images de la base.
Vous devrez faire un compte rendu et fournir les codes sources de vos programmes et les différents scripts que vous utilisez pour les lancer. Vous enverrez le compte-rendu et les sources (pas les fichiers de données) dans une archive zip ou tgz pour le 21 avril au plus tard (Georges.Quenot@imag.fr). Vous montrerez ce qui tourne lors de la séance du 7 avril.
Le compte rendu doit comprendre une très courte introduction expliquant quel est le problème que votre système traite, l'organisation logicielle globale de votre système, comment vous avez implémenté les différents éléments (vous pouvez en choisir un en particulier que vous détaillez), et des exemples de résultats obtenus illustrant les capacités du système et en montrant des cas où il fonctionne de manière satisfaisante et d'autre où il fonctionne moins bien. Ne reproduisez pas le sujet et n'incluez pas le code et les scripts dans le compte rendu, à l'exception éventuelle d'extraits courts.