TD indexation Master MI2PRO 26/03/15 11:01
Anne Guerin-Dugue
[email protected]Master MI2PRO - TP documents multimedia - 15h
Les rapports et executables sont à rendre pour le mardi 24 avril. La note sera divisée par deux à chaque journée de retard.
Objectif : mettre en oeuvre d'un algorithme d'indexation d'images.
premiere partie : Le système devra extraire un vecteur de caractéristiques par image, et utiliser une métrique associée pour le calcul des
similarités entre images. Pour cela, on construira un vecteur de caractéristique basé sur les points d'intérêt des images. Cette premier phase
devra aboutir à la génération d'une matrice de distances (matrices NxN, où N est le nombre d'images), et sera validée par la visualisation des
images les plus proches d'une image donnée (cf. bandeau vu en cours).
deuxieme partie : Le deuxième objectif concerne l'affichage de ces images par similarité visuelle. Vous implémenterez l'algorithme Multi
Dimensional Scaling (MDS) qui permet de visualiser sur un plan 2D les N images indexées, placées selon leurs similarités visuelles. Cet
algorithme prend en entrée une matrice de distance, et ressort les coordonnées (x, y) de chaque image. Vous constaterez que cette approche
pose le problème du chevauchement des images dans le plan 2D. Nous étudierons et proposerons des techniques pour afficher les images sans
chevauchement.
Donnees fournies :
1. Une base d'image est mise à disposition pour les tests : BDImages.zip
2. une matrice de similarite en exemple : distances_rgb_1.txt
3. lien vers la librairie openCV, le wiki et un tutoriel + lien vers la librairie CImg
Premiere partie : points d'intérêts et matrice de similarité
I.1 Construction d'un vecteur caractéristique par image
Pour chaque image, l'objectif ici est de déterminer les points d'intérêt par le détecteur de Harris, et de calculer le descripteur SIFT pour chaque
point d'intérêt. Un descripteur SIFT correspond à un vecteur de taille 128. Le vecteur de caractéristique d'une image sera alors la concaténation
de ces descripteurs. Une image sera alors décrite par un vecteur de taille 128 * nbre de points d'intérêt détectés.
1. Pour cela, on utilisera l'executable (linux) extract_features_32bit.ln qui produit un fichier .sift ou sont décrit l'ensemble des points
détectés, et le vecteur de description associé.
2. exemple d'utilisation de extract_features_32bit.ln (copyright Krystian Mikolajczyk)
./extract_features_32bit.ln -harlap -sift -i image.ppm -DC -harThres 5000
-harlapp : utilise le détecteur de Harris pour détecter les points d'intérêt
-sift : donne le descripteur SIFT pour chaque point détecté
-i image en entrée (utiliser du ppm)
-DC permet de sauver une image image.ppm.harlap.sift.png pour visualiser le résultat
-harThres 5000 : permet de fixer un seuil pour le détecteur de Harris (prendre la même seuil pour toutes les images, changer le
http://steep.inrialpes.fr/~Arnaud/indexation/tp.html Page 1 of 4
TD indexation Master MI2PRO 26/03/15 11:01
-harThres 5000 : permet de fixer un seuil pour le détecteur de Harris (prendre la même seuil pour toutes les images, changer le
seuil pour adapter le nombre de points si celui ci est trop grand, par exemple 30000).
En sortie, on obtient un fichier de paramètres (*.params), et un fichier .sift qui contient:
première ligne : taille d'un sift (128),
deuxième ligne : nombre de points détectés,
puis, une ligne par points contenant x, y, 3 parametres, vecteur sift
exemple avec l'image ball1.ppm : ball1.ppm.harlap.sift.png, ball1.ppm.harlap.sift.params, ball1.ppm.harlap.sift
I.2 Création de la matrice de similarité.
L'objectif ici est de calculer la matrice décrivant les similarités 2 à 2 entre les images de la base. Cette matrice sera de dimension NxN (N est le
nombre d'images) et symétrique.
1. La mesure de similarité entre deux images sera calculée en fonction du nombre de points matchés entre les deux images. Ce nombre est
calculé en plusieurs étapes, comme cela est expliqué dans l'exemple suivant.
2. Exemple du calcul de similarité entre une image A décrite par 4 sifts, et une image B décrite par 5 sifts. Attention, il faut travailler
avec les sifts normalisés (les normaliser de telle sorte que la somme d'un vecteur sift soit égale à 1000).
(a) calculer l'ensemble des distances L2 sift à sift dans une matrice 4 x 5.
Puis pour chaque sift de l'image A, repérer le sift de l'image B le plus similaire (celui pour lequel le distance est minimale) -- en
bleu sur la figure. Ici, on a A1 -> B2 ; A2 -> B3 ; A3 -> B2 ; A4 -> B5
(b) faire le même repérage dans l'autre sens : pour chaque sift de l'image B, repérer le sift de l'image A le plus similaire -- en vert
sur la figure. Ici, on a B1 -> A2 ; B2 -> A1 ; B3 -> A3 ; B4 -> A3 ; B5 -> A4
(c) Conserver uniquement les couples réciproques (si Ai -> Bj et Bj -> Ai)
Le nombre de ces couples correspond à la mesure de similarité entre l'image A et l'image B. Ici, 2.
3. écrire la matrice S complète dans un fichier. Cette matrice doit etre symétrique, de taille NxN où N est le nombre d'images traité.
4. La matrice S doit etre normalisée (i.e. Sii = 1). Pour cela, définir une nouvelle matrice P (de taille NxN) qui est la matrice de similarité
normalisée (i.e. Pii = 1) : Pij = Sij / min (Sii ; Sjj)
I.3 Affichez les images les plus similaires d'une image donnée
Affichez les images les plus similaires d'une image donnée, en fonction de la matrice de similarité normalisée : faites comme bon vous semble
....
Deuxieme partie : affichage
http://steep.inrialpes.fr/~Arnaud/indexation/tp.html Page 2 of 4
TD indexation Master MI2PRO 26/03/15 11:01
Deuxieme partie : affichage
II.1 Passage de la matrice de similarité P à une matrice de distance D
Les mesures de similarité doivent etre transformées en mesures de distance. Pour cela :
1. Creer une matrice D, de taille NxN telle que : Dij = - ln Pij.
D est la matrice de distance, qui doit avoir des zeros sur la diagonale.
II.2 Algorithme MDS (Multi-Dimensional Scaling)
Le Multi Dimensional Scaling utilise la décomposition en valeur propre (ou singulière) la dimension des données. Dans notre cas, on passe de
dimension N (N est le nombre d'images) à 2. On obtient alors les coordonnées centrées de chaque image dans un plan 2D.
Pour voir un exemple d'utilisation du MSD, voir p.10 d'une introduction à MDS.
1. soit D, la matrice de distance. Construire D', où chaque élément de D est élevé au carré.
2. Post et Pré-centrer D' :
Soit J, la matrice de centrage de taille NxN. J est remplie de -1/N, avec des 1 - 1/N sur la diagonale
Calculez B = -1/2 * [ J D' J ].
3. Décomposition en valeur singulière de B :
Calculer les valeurs propres l1, l2 ... lm et les vecteurs propres associes e1,... em de B. (en java, utiliser la fonction eig() de la
librairie JAMA ; en C/C++, utiliser les fonctions eigenvalues() et eigenvectors() de la librairie Eigen)
Construire L[2x2] la matrice diagonale contenant les racines des 2 plus grandes valeurs propres positives.
Construire E[Nx2] la matrice contenant les 2 vecteurs propres associés.
4. Retourner X = E L. (X correspond alors aux coordonnées de chaque image dans un plan 2D)
5. Écrire les coordonnées de chaque image dans un fichier.
III.3 Affichage de la base avec et sans chevauchement
Pour générez une image qui affiche les images de la base, avec chevauchement, utilisez les coordonnées précédemment calculées pour placer
les images. Vous avez le choix de la technique à utiliser pour en déduire un affichage sans chevauchement.
http://steep.inrialpes.fr/~Arnaud/indexation/tp.html Page 3 of 4
TD indexation Master MI2PRO 26/03/15 11:01
http://steep.inrialpes.fr/~Arnaud/indexation/tp.html Page 4 of 4
