Université Paris-Est Marne-la-Vallée

Master Systèmes d'Information et Applications Web

UE Acquisition et gestion de contenus numériques multimédia

ProjetBases de données image : structuration de l'espace des descripteurs et recherche par similarité

2014-2015

1. Description

1.1. Présentation du sujet

Aujourd’hui, grâce aux nouvelles technologies vidéo et photo, des quantités de plus en plus grandes de données multimédia deviennent disponibles, dans de multiples secteurs : chaînes de télévision qui conservent leurs productions, agences photo, boutiques en ligne, musées, moteurs de recherche sur Internet, collections personnelles, etc. Ce développement crée une demande de plus en plus forte de nouvelles technologies pour organiser ces contenus et pour leur interrogation rapide et fiable.

Dans ce projet, nous allons nous focaliser plus particulièrement sur les bases d’images fixes. Pour ce type de base, les mots-clefs ont été utilisés pendant longtemps comme le seul moyen de recherche, méthode inspirée par la recherche des documents textuels. Pour les bases de petite taille, le coût de l’annotation des images est acceptable, mais pour les bases disponibles aujourd’hui, qui comportent parfois des millions d’images, il est impossible d’appuyer la recherche seulement sur les mots-clefs. La recherche d’images doit employer des moyens supplémentaires, comme la description du contenu visuel, permettant aux utilisateurs de formuler des critères de recherche qui sont parfois difficile sinon impossible à exprimer en utilisant les mots-clés.

Figure 1. Architecture de base d’un système de recherche par contenu visuel.

Le but de ce projet est de mettre en place le prototype d'un système description et de recherche d'images par le contenu (voir Figure 1). Tous les composants d'une machine de recherche d'information seront abordés :

• Description des images (1 séance ; 4 heures ; voir Sec. 2). Parmi les techniques de description existantes nous nous focaliserons sur les descriptions globales qui ont été utilisé avec succès [DAT08] et qui permettent de traiter de grandes bases d'images en temps réel.

1

• Recherche par similarité (1 séance ; 4 heures ; voir Sec. 3). Nous utiliserons la notion de distance sur l'espace de description pour calculer les k plus proches voisins de l'image requête. Nous examinerons aussi les courbes Précision/Rappel et les temps de recherche.

• Structuration des descripteurs (1 séance ; 4 heures ; voir Sec. 4). Structures d'index : il s'agira de mettre en place une structure d'index adaptée à chaque descripteur employé, de manière à accélérer la recherche dans la base d'images.

Moyens techniques conseillés

• Langage JAVA (pour la programmation des différents composants) ;

• Outils graphiques (Gnuplot ou Scilab).

Liens utiles

• http://java.sun.com (Java JDK)

• http://netbeans.org (Java IDE)

• http://www.eclipse.org (Java IDE)

• http://www.scilab.org (Scilab : clone libre de Matlab)

• http://www.gnuplot.info (représentations graphiques des données)

La section 5 contient également des références bibliographiques sur le sujet.

1.2. La base d'images utilisée

La base de données utilisée dans ce projet, appelée Base10000, est constituée de 10000 images au format JPEG. Il s'agit d'une base d'images généraliste, avec beaucoup d'images naturelles sur des sujets variés.

Figure 2. Quelques images de la base utilisée, issues des classes suivantes : (a) montagne désert, (b) chiens, (c) chutes d'eau et (d) route.

Une partie de ces images constitue la vérité terrain, sous forme d'un ensemble de classes prédéfinies. Chaque classe illustre un sujet sémantique, par exemple: Scènes de nuit, Châteaux forts, Chutes d'eau, etc. En total, il y a 30 classes, chacune constituée de 100 images. Ces classes seront utilisées plus tard (voir Sec. 4.2) pour comparer les différents descripteurs et méthodes de recherche. Leur structure est décrite dans les fichiers accompagnant la base :

VT_description.txt : description de chaque classe (en langage naturel), une classe par ligne.VT_files.txt : liste de fichiers par classe (une classe par ligne dans le même ordre que VT_description.txt).Base10000_files.txt : liste avec tous les fichiers de la base (un par ligne).images/ : répertoire avec tous les images.

2

URLs pour récupérer les fichiers :

http://cedric.cnam.fr/~stoiana/files/Base10000.ziphttp://cedric.cnam.fr/~stoiana/files/TP_AGCM.zip

1.3. Description du travail à réaliser

Chacune des sections suivantes contient une sous-section appelée « Travail à réaliser » : suivez les demandes spécifiques de chaque section. En général, dans chaque section il y a trois types de activités :

• Programmation à faire ;

• Parties à préparer et à mettre dans le rapport final ;

• Code fichiers sources java et documentation à préparer avec le rapport.

A la fin du projet, chaque participant doit envoyer par email deux éléments :

1. Un rapport contenant toutes les parties demandées correctement étiquetées avec le numéro et le nom de la section.

2. Les sources des programmes avec leur documentation, là ou ils sont demandés. La documentation doit expliquer comment utiliser les programmes, quelles sont les entrées, les sorties et le format des résultats. Aucun code source ne sera pris en compte sans la documentation qui l'accompagne.

Attention, le travail à réaliser est personnel. Ne copiez pas les résultats de vos collègues.

Date limite : rapport à envoyer par émail à l'adresse andrei.stoian@gmail.com au plus tard Dimanche 14 Décembre 2014 à 23h00. Les rqpports et codes doivent être archivés et le nom du fichier doit contenir vos noms et prénoms. Dans le sujet du mail mettre 'TPMLV'.

2. Description des images (1 séance ; 4 heures)La première partie que nous aborderons est la description du contenu de la base d'images. Cette opération extrait les caractéristiques visuelles principales des images de la base et génère un ensemble de descripteurs, utilisés plus tard, au moment de la requête, par le module de recherche. L’extraction des caractéristiques est faite hors ligne et peut durer aussi longtemps que nécessaire. En revanche, l’interrogation de la base se déroule en ligne et nécessite des temps de réponses les plus faibles possibles (proches du temps réel).

Les systèmes de recherche par contenu visuel (en anglais Content Based Image Retrieval ou CBIR) emploient des descriptions statistiques du contenu visuel qui sont suffisants pour trouver des résultats pertinents dans la majorité des cas. Le premier système CBIR disponible pour le public, QBIC [FLI95], utilisait des descripteurs couleur pour effectuer des recherches d’images et de vidéos. Les systèmes plus récents emploient des descripteurs plus sophistiqués, qui exploitent des caractéristiques visuelles globales plus complexes, comme la forme et la texture, mais aussi des descripteurs locaux qui permettent de faire des recherches par région d'intérêt ou de sélectionner un objet [DAT08].

Le principe est d'associer à chaque image un descripteur (appelé aussi signature d’image) qui se présente sous forme d'un vecteur n-dimensionnel calculé à partir des caractéristiques visuelles les plus importantes de l’image (couleurs, textures, formes, etc.).

Dans ce projet nous utiliserons les descripteurs globaux les plus employés : les histogrammes classiques en niveaux de gris et en couleur, décrits dans la section suivante.

2.1. Histogramme couleur

Un histogramme représente la distribution statistique d'une caractéristique (ou mesure) dans sa plage de valeurs. Dans cette partie nous nous intéresserons à la couleur, une des caractéristiques les plus importantes dans la description du contenu visuel. Employée pour la première fois en CBIR par Swain et Ballard [SWA91], qui introduisent les histogrammes couleur comme signatures d’images, la couleur a fait l’objet d’importantes investigations ces dernières années, en tant que descripteur de contenu. A cause de sa nature statistique, l’histogramme couleur ne peut pas être utilisé directement pour faire des requêtes précises (par exemple pour la

3

recherche par objet), mais reste un outil très puissant, car il combine bons résultats avec temps de calcul raisonnable.

Espace couleur. L’espace couleur employé, ainsi que le niveau de quantification, ont une importance capitale pour la qualité des résultats. Les espaces couleur les plus utilisées sont RVB, HSV et Lab. RVB est l’espace sur lequel sont basés la plupart des capteurs électroniques. C’est un espace non uniforme en termes de perception humaine de la couleur : des couleurs situées à des distances égales par rapport à une couleur de référence peuvent apparaître pour un observateur comme n’étant pas également différentes de la couleur de référence. Cependant, RVB reste l’espace le plus utilisé car il est employé par une grande partie des formats d’image disponibles et il est suffisant pour la plupart des besoins de l’imagerie. L’espace couleur Lab a été introduit pour répondre aux problèmes liés à la perception des couleurs, car il assure une perception uniforme par rapport à la distance euclidienne calculée dans cet espace. L’espace HSV est le plus proche du modèle de perception humaine, qui considère les trois aspects perceptifs de la couleur — teinte, saturation, intensité — de manière indépendante. Une vue d’ensemble des problèmes et des caractéristiques des espaces couleur est présenté dans [GEV06]. Dans ce projet nous utiliserons l'espace couleur RVB.

Dans la représentation RVB, la couleur de chaque pixel est caractérisée par trois composantes : Rouge, Vert et Bleu. Ces trois couleurs sont les couleurs primaires en synthèse additive. Elles correspondent à peu près aux trois longueurs d'ondes auxquelles répondent les trois types de cônes de l'œil humain. L'addition des trois donne du blanc pour l'œil humain. Chaque pixel d'une image est considéré comme étant un mélange de ces trois couleurs.

Figure 3. Le cube RGB. Le Noir (0,0,0) se trouve derrière en bas. Opposé sur la diagonale principale, en face en haut on retrouve le Blanc (1,1,1).

Histogramme en niveaux de gris. Pour préparer la voie pour la présentation de l'histogramme couleur, nous présenterons d'abord le cas (plus simple) de l'histogramme en niveaux de gris. Une image en niveaux de gris est une image où pour chaque pixel (i,j) on donne la valeur de la luminance qui correspond à sa couleur. Le niveau de gris représente donc l'intensité lumineuse d'un pixel, lorsque ses composantes de couleur sont identiques, avec une valeur calculée par

Pour une représentation sur un octet (8 bits), 28 = 256 niveaux de gris différents peuvent être distingués. L'histogramme dans ce cas est donné par la fréquence empirique h de chaque niveau de gris g dans l'image

h( g )=Np( g )

MN

ou Np(g) est le nombre de pixels dans l'image ayant la valeur g, et M et N représentent la longueur et respectivement la hauteur de l'image. L'histogramme est donné par les valeurs h en fonction du niveau de gris g, qui représentent le pourcentage de pixels qui ont la valeur g. Ceci implique la condition de normalisation

∑g

h( g )=1

qui traduit le fait que la somme de tous le pourcentages doit être 100%.

Quand on a besoin de moins de 256 valeurs, l'alternative est de prendre une division en Pss intervalles égaux (appelés bins) de la plage des variation de g, et de calculer la fréquence des valeurs de gris qui tombent dans

4

chaque intervalle (procédure appelé quantification des niveaux de gris). Le résultat est moins précis mais nécessite aussi moins de place pour être stocké.

Figure 4. Une image et son histogramme des niveau de gris.

Histogramme couleur. L'histogramme couleur modélise la distribution statistique des couleurs dans une image. Tout d'abord, la plage des valeurs de chaque composante R, V et B est divisée en un nombre égal d'intervalles, opération appelé aussi quantification (ou discrétisation), car toutes les valeurs des composants dans chaque intervalle sont assimilés à la valeur la plus petite de l'intervalle. Soit P le nombre des couleurs quantifiés sur chaque axe de couleur (R, G et B). La quantification divise le cube RGB en un nombre de P×P×P couleurs quantifiées (ou bins). Chaque bin correspond donc à un cube dans l'espace RGB (voir la Fig. 5). Calculer l'histogramme revient à calculer la fréquence des couleurs dans l'image qui sont quantifiées dans chaque bin.

Figure 5. Quantification de l'espace couleur RVB. La valeur de chaque composante (R, V, ou B) du pixel p(i,j) correspond à un unique intervalle dans la quantification de chaque axe de couleur, ce qui détermine sans

équivoque sa couleur quantifiée : le cube est le produit cartésien de chaque composante quantifiée.

Mathématiquement, l'histogramme approche la densité de probabilité tridimensionnelle des couleurs :

(1)

5

où c est la couleur quantifiée, I(i, j) est la couleur (quantifiée) du pixel (i,j), δ est l'impulsion unitaire de Dirac et M et N représentent les tailles horizontale et verticale de l'image. La condition de normalisation s'écrit

(2)

L'effet de la quantification. Un problème important est celui du nombre de bins (nombre d'intervalles de quantification sur chaque axe de couleur). Si pour chaque composante R, V et B on utilise un octet (8 bits) il est possible de représenter 256 valeurs par composante, on a donc 256×256×256 = 16 777 216 couleurs différentes. Ce nombre et beaucoup trop grand pour fournir un histogramme utile en pratique (en réalité le nombre moyen des couleurs dans une image est beaucoup plus petit). Le rôle de la discrétisation est de réduire le nombre de couleurs et de rendre les histogrammes plus pratiques en tant que descripteur d'image.

Dans la figure suivante on peut voir l'effet de la discrétisation sur la lisibilité de l'image. Naturellement, l'effet dépend de l'observateur et du contenu de l'image.

Image d'origine Quantification 6×6×6

Quantification 4×4×4 Quantification 2×2×2

Figure 6. L'effet de la quantification de la couleur sur les images.

Idéalement, on cherche un nombre de bins le plus petit possible, car celui-ci détermine la taille du descripteur (la dimension). Mais l'effet principal de la discrétisation est de réduire le nombre de couleurs dans une image : plus on réduit, plus l'image résultante se dégrade et la qualité du descripteur baisse. Il faut donc trouver un bon compromis entre nombre des bins et la qualité des résultats qu'on attend de la machine de recherche.

2.2. Travail à réaliser

Exercice

6

Illustration 1: Block

Illustration 2: Checkerboard

Illustration 3: Gradient

Illustration 4: Stripes

Partie 1 :

Les images ci-dessus sont toutes de taille 100x100 pixels. La première, 'block', est divisée en trois bandes, deux blanches de hauteur 25 pixels chacune et une noire de hauteur 50 pixels. La deuxième, 'checkerboard', est divisée en 4 blocs de taille 25x25. La troisième présente un dégradé de noir à blanc contenant toutes les 255 nuances de gris. La dernière contient de rayures de largeur de 2 pixels, noires et blanches.

Calculez, sur papier, leurs histogrammes en niveaux de gris sur 2 bins et sur 8 bins. Donnez vos résultats sous la forme de vecteurs (h1, h2, h3, …, hn) où hi est la valeur du bin d'index i. N'oubliez pas la division par le nombré de pixels dans l'image (voir eq. (1)), l'égalité (2) doit être respectée.

Partie 2 :

Un histogramme couleur peut être vu comme un tableau en 3 dimensions où chaque élément est le nombre de pixels ayant une couleur qui se trouve dans le cube RGB correspondant, comme expliqué ci-dessus. Mais pour sauvegarder ce tableau dans un fichier (comme un simple vecteur de float) il faut parcourir le tableau dans les 3 dimensions. Considérez un histogramme tridimensionnel de 2x2x2 bins – largeur (X) x hauteur (Y) x profondeur (Z) - dont la moitié supérieure, ((X {0,1}, Y=1, Z {0,1}), est remplie de 1 et la moitié inférieure, ((X {0,1},∈ ∈ ∈ Y=0, Z {0,1}) de 0. En parcourant d'abord sur X et puis sur Y et Z, construisez la série de 0 et 1 obtenus (série∈ de longueur 2x2x2 = 8).

Travail de programmation

1. Le fichier (fourni) JPictureMLV.java contient une classe Java qui permet de charger et de sauvegarder une image de type JPG, ainsi qu'un exemple de son utilisation (dans la fonction 'main'). Etudiez-le et familiarisez vous avec l'interface de programmation (API). Testez-vous avec ces trois exercices :

1. Chargez les images fournis 'block.bmp', 'checkerboard.bmp' et 'stripes.bmp' (un constructeur de la classe JPictureMLV est fourni dans ce but).

2. Ecrivez une fonction RGBtoGBR qui intervertit les trois plans de couleur RGB → GBR. L'algorithme pour un pixel de couleur (R,G,B) est le suivant :

temp ← G

G ← B

B ← R

R ← temp

3. Sauvegardez les images obtenues (utilisez la fonction 'writeImageFile') comme 'block_gbr.bmp', 'checkerboard_gbr.bmp' et 'stripes_gbr.bmp'.

2. Complétez la fonction ComputeGrayLevelHistogram(...) qui calcule l'histogramme en niveaux de gris de l'image et qui prend en paramètre le nombre de bins (voir Sec. 2.1). Pour un histogramme une classe Histogram est fournie, utilisez-la. Testez cette fonction sur les images block_gray.bmp, checkerboard_gray.bmp, gradient.bmp et stripes_gray.bmp sur 2 et 8 bins. Comparez avec les résultats obtenus à l’exercice au-dessus.

3. Complétez la fonction ComputeRGBHistogram(...) qui calcule l'histogramme en couleur de l'image et qui prend en paramètre le nombre de niveaux de quantification par axe couleur (voir Sec. 2.1). Testez-la avec 2x2x2 bins sur block.bmp, checkerboard.bmp, et stripes.bmp. Expliquez les résultats en indiquant quels pixels sont affectés à chaque bin.

4. Complétez la fonction IndexImages qui prend en entrée une liste d'images et qui utilise les méthodes définies aux points (2) et (3) pour indexer chaque image de la base et sauvegarder les résultats dans un fichier (le même fichier pour toute la base). Chaque signature (GrayLevelHistogram et RGBHistogram) doit être sauvegardée sur une ligne du fichier de sortie. Testez cette fonction sur la base d'images donnée en passant en paramètre à IndexDatabase le fichier Base10000_files.txt.

5. Indexez la base avec trois histogrammes en niveaux de gris : 256 bins, 64 bins et 16 bins. Appelez les fichiers résultants Base10000.HistGREY_256, Base10000.HistGREY_64 et Base10000.HistGREY_16.

6. Indexez la base avec trois histogrammes RGB : 6×6×6 bins, 4×4×4 bins et 2×2×2 bins. Appelez les fichiers résultants Base10000.HistRGB_6x6x6, Base10000.HistRGB_4x4x4 et Base10000.HistRGB_2x2x2.

7

Remarques : Conservez les résultats obtenus aux parties (5) et (6). Vous utiliserez ces descripteurs plus tard. Employez le type 'float' pour représenter les composants des histogrammes.

7. (Optionnel/Bonus) Ecrivez une fonction QuantizeColors pour quantifier les couleurs d'une image, remplaçant les valeurs de chaque canal avec les valeurs discrétisées sur le nombre de bins passé en paramètres. Essayez sur l'image 'horse.jpg' avec 6, 4 et 2 bins .

Éléments à mettre dans le rapport

1. Les résultats obtenus pour la partie 1 de l’exercice ci-dessus (4 vecteurs de 2, 4 et respectivement 8 bins). Une explication, pour chaque histogramme, des calculs intermédiaires que vous avez faits pour l'obtenir. Qu’observez-vous sur 2 bins pour les 4 images et pour 8 bins pour les images 1, 2 et 4 ? Si on voulait comparer deux images par le biais de leurs histogrammes, quel est l'impact de ces observations ? Discutez-le brièvement.

2. La série de valeurs obtenues pour la partie 2 de l'exercice.

3. Explication de la fonction addToBinRGB, notamment de la ligne :

int bin = binR * m_nBins * m_nBins + binG * m_nBins + binB;

4. Le code des deux fonctions ComputeGrayLevelHistogram et ComputeRGBHistogram avec des commentaires expliquant l'algorithme utilisé. Ne mettez pas toute la classe JPictureMLV dans le rapport, seulement les deux fonctions demandées.

5. (Optionnel) Les images obtenus au point 7 plus haut.

Code à fournir

Le fichier JPictureMLV.java enrichi de vos 3 fonctions ComputeGrayLevelHistogram, ComputeRGBHistogram et IndexDatabase ainsi que la fonction RGBtoGBR. En exécutant le programme compilé, il doit sortir les 8 histogrammes du point 2, les 3 histogrammes du point 3, l’image horse.jpg transformée en GBR, et doit produire les 6 fichiers contenant les histogrammes des images de la base.

3. Recherche par similarité (1 séance ; 4 heures)

3.1. Recherche par exemple

Le scénario d'utilisation est le suivant : étant donnée une image, dite image requête, trouver les éléments (images indexées) de la base qui sont les plus similaires à la requête. C'est le paradigme de recherche le plus utilisé, celui de la recherche par l’exemple (en anglais Query By Example ou QBE). Le module de recherche produit donc une réorganisation de la base en concordance avec la similarité visuelle de chaque image par rapport à l’image requête. La similarité est en général modélisée par l’intermédiaire d’une fonction distance, tel que les objets les plus proches de l’image requête sont les plus similaires. La fonction distance la mieux adaptée dépend du contenu de la base d’images, mais en règle générale la plupart des systèmes utilisent avec succès les distances Lp.

Nous utiliserons une distance de type L2 : étant données deux images X et Y avec les descripteurs ( x1 ,. .. ,xn )

et ( y1 , . .. ,yn ) respectivement, la distance entre les deux images est

d ( X,Y )=(∑i= 1

n

( x i− y i )2)

12

Le résultat d'une recherche consiste donc en un re-ordonnancement de la base en ordre croissant de la distance par rapport à l'image requête, avec les images les plus proches de la requête en premier. Si le nombre d'images de la base est N, le temps d'une recherche linéaire est donc O(N) : pour faire une requête il faut calculer N distances (entre chaque image de la base et l'image requête) et ordonner les résultats en ordre croissant. Pour des raisons pratiques on peut limiter le nombre de résultats affichés à k, ce qui revient alors à calculer les k plus proches voisins de la requête (en anglais K-Nearest Neighbours ou KNN).

8

3.2. Evaluation de la qualité des réponses obtenues : courbes Précision/Rappel

Une étape importante dans le développement d’un système d’indexation et de recherche d’images est son évaluation. Une façon classique d’évaluer la qualité des résultats est le calcul de courbes Précision/Rappel. Cette méthode utilise une vérité terrain vue sous la forme de plusieurs classes d'images définies sur la base. Dans l'idéal, on suppose que tous les éléments d'une classe sont pertinents relativement au sujet sémantique que la classe veut illustrer, c.-à-d. on s'attend qu’une requête faite à partir d'un élément d'une classe produit en premier des résultats de la même classe. Mais en pratique, les systèmes de recherche fournissent des résultats loin de la réponse idéale. On utilise donc des mesures d'efficacité pour quantifier leur succès.

Soit C une classe de la vérité terrain, |C| sa taille, q∈C l'image requête et A l'ensemble des k plus proches voisins de q (résultats fournis par une machine de recherche).

La précision et le rappel sont définis comme suit :

• Précision : mesure la proportion d’images pertinentes retrouvées par le système parmi les images retournées. Une image « pertinente » est une image appartenant à la classe C.

• Rappel : mesure la proportion d’images pertinentes retrouvées parmi toutes les images pertinentes présentes dans la base (il y a |C| images pertinentes dans la base).

Pour une requête q donnée, on considère tous les ensembles de type Ak (k-NN) pour k = 1,2,...N, ou N est la taille de la base, et pour chaque Ak on calcule le couple Précision/Rappel (P, R). La courbe Précision/Rappel est un graphe dans lequel la précision apparaît en ordonnée et le rappel en abscisse, comme l’illustre la Fig. 7.

Figure 7. Exemple de courbe Précision / Rappel.

La courbe Précision/Rappel pour toute la classe C est calculée en moyennant les courbes obtenues en considérant chaque image q de C comme une image requête (pour le même valeur du rappel, on considère la moyenne de l’ensemble des précisions calculées). De la même façon on calcule la courbe Précision/Rappel pour plusieurs classes, en moyennant toutes les précisions obtenues pour une même valeur du rappel.

La courbe associée à un système performant donne de bons taux de précision et de rappel en même temps. Ainsi, un système qui aurait 100% de précision pour toutes les valeurs de rappel trouverait toutes les images pertinentes sans en oublier une seule. Dans la réalité, la précision diminue lorsque le rappel augmente. En effet, plus le système retourne d’images, plus on risque de trouver des réponses non pertinentes. Notons qu’il est facile d'avoir 100% de rappel en retournant toutes les images de la base sur chacune des requêtes et qu’il est également facile d’avoir une bonne précision en ne retournant que très peu d’images sur chacune des requêtes.

3.3. Travail à réaliser

9

Travail de programmation

1. Complétez la fonction queryDb du programme Java QBE.java qui implémente la recherche par exemple (QBE) décrite dans la Section 4.1 ainsi que la fonction distanceL2 de la classe Histogram. Le programme fourni, QBE.java, prend en paramètres (en ligne de commande) la liste des images de la base dans un fichier, le fichier qui contient un des descripteurs calculés précédemment, l'image de la requête et le nombre k de résultats désirés. Il génère en sortie un fichier HTML contenant les k résultats (images) en ordre croissant de la distance par rapport à l'image requête. Pour éviter d'indexer l'image de la requête, on considère que celle-ci appartient à la base (est déjà indexée). Utilisez la sous-classe ImageInfo pour garder en mémoire les informations et scores de chaque image de la base. La fonction queryDb doit retourner une liste triée en ordre croissant de la distance entre l’image et la requête. Ensuite complétez la fonction writeResultsHTML qui écrit les résultats d’une requête ainsi que leur score dans un fichier HTML.

Exemple de ligne de commande pour QBE :

java QBE ..\Base10000\Base10000_files.txt Base10000.HistGREY_64 49000.jpg 30 results_49000.html

2. Un programme Java PrecisionRappel.java se trouve dans l’archive donnée. Ce programme calcule les courbes Précision/Rappel (voir la section 4.2) pour une image appartenant à une classe où pour une classe entière Le programme utilise les fichiers de description de la vérité terrain (VT_files.txt et VT_description.txt), le fichier des descripteurs, et permet de spécifier si on veut calculer les courbes Précision/Rappel pour une classe spécifiée ou pour une image. Le programme écrit les résultats dans un fichier texte de sortie dans le format suivant : un couple "rappel précision" par ligne. Ces fichiers de résultats seront utilisés avec GNUPLOT ou Scilab/Matlab (ou bien Microsoft Excel) pour construire les graphiques des courbes. Dans ce programme il vous reste à implémenter les fonctions computePrecisionRecall (qui calcule la courbe PR pour une seule requête) et getAveragePRforClass (qui calcule la courbe PR moyenne pour toutes les requêtes d’une des classes, qui se trouvent dans le fichier VT_files.txt). Note : comme la requête est sur la première position dans la liste des résultats, la précision doit être 1 pour un rappel de 1/Taille(Classe).

Exemple de ligne de commande pour PrecisionRappel :

java PrecisionRappel ..\Base10000\VT_description.txt ..\Base10000\VT_files.txt class:Fireworks ..\Base10000\Base10000_files.txt ..\Java\Base10000.HistGREY_64 > out.txt

3. Construire les courbes Précision/Rappel par classe (pour Doors_Of_Paris, Cards, Fireworks, Lions et North_American_Deer) pour les cas suivants :

a) Histogrammes en niveaux de gris : 256 bins, 64 bins et 16 bins (les trois sur le même diagramme).

b) Histogrammes couleur : 6×6×6 bins, 4×4×4 bins et 2×2×2 bins.

c) Histogrammes en niveaux de gris 256 bins, histogramme couleur 6×6×6 bins.

Discutez les résultats. Quels descripteurs permettent d'obtenir des meilleurs résultats ? Expliquez.

Des exemples de courbes :

1

4. Une mesure plus concise d’évaluation d’un système de recherche par l’exemple est la Précision Moyenne (‘AP’ de l’anglais Average Precision). Elle est calculée comme l’intégrale de la courbe PR, autrement dit la surface sous la courbe. Une méthode simple de calcul utilise la méthode des trapèzes (voir ci-dessous). Implémentez le calcul de la Précision Moyenne dans la fonction computeAP. En moyennant l’AP de toutes les requêtes de la vérité terrain on obtient la Précision Moyenne Globale (Mean Average Précision – MAP). Calculez la MAP, en modifiant getAveragePRforClass, pour la vérité terrain donnée pour les descripteurs mentionnés au point 3 (pour retourner 2 résultats d’une fonction en Java une astuce est de passer en paramètre un tableau dans lequel la fonction écrit).

Rappel des notions :

Une approximation de l'intégrale d'une fonction sur un intervalle est calculée en discrétisant la fonction et ensuite en assimilant des régions sous la courbe à des trapèzes pour lesquels il est plus simple de calculer l'aire.

Figure 8: Approximation par des trapèzes (source Wikipedia)

∫x0

xn

f ( x )dx∑i=0

n−1 f ( x i+1)− f ( x i )

2( x i+1−x i )

(eq 3)

5. (Optionnel/Bonus) Alors que la MAP est une bonne mesure globale du système de recherche d’information, on veut regarder aussi la courbe PR globale (pour toutes les classes). La difficulté est dans le fait que les valeurs de rappel ne sont pas les mêmes entre les classes car elles ont des tailles différentes. Il faut donc implémenter une fonction d’échantillonnage sur un nombre fixe de pas d’une courbe PR, resamplePRCurve, la précision dans un nouveau point de rappel étant une interpolation linéaire des précisions dans les 2 points de rappel les plus proches. Ensuite, la courbe moyenne sera obtenue comme dans getAveragePRforClass. Note : lorsqu’on veut interpoler la précision entre 2 points de rappel, dans ces deux points il est possible qu’il y ait plusieurs valeurs de la précision. A gauche il faut prendre la précision la plus basse et à droite la plus élevée.

Eléments a mettre dans le rapport

1. Quelques exemples de recherches (copies d'écran des fichiers HTML affichés dans un navigateur Web).

2. Les diagrammes obtenus au point précédent (No. 3) avec la discussion des résultats. Pour chaque classe, pourquoi on obtient des bonnes/mauvaises performances ? Quelles modifications envisagez-vous pour améliorer ces résultats. Prenez des requêtes individuelles de Cards et de Lions, et pour les résultats obtenus motivez vos réponses.

1

3. Les valeurs de la MAP pour toutes les classes pour tous les descripteurs, ainsi que la MAP globale.

4. Si vous avez réussi le point 5, la courbe PR globale pour un pas d’échantillonnage du rappel de 1/100. Calculez l’AP à partir de cette courbe et comparez avec la MAP obtenue au point 3. Est-il préférable de calculer les PR individuelles et moyenner leurs AP ou moyenner les courbes PR et calculer une AP sur celle-ci ?

Code à fournir

1. Le fichier QBE.java qui implémente la recherche par similarité.

2. Le fichier qui PrecisionRappel.java qui implémente la construction des courbes Précision/Rappel.

4. Structuration des descripteurs par un M-tree (1 séance ; 4 heures)

4.1. Arbre métrique (M-tree)

Les structures d'arbre sont utilisées pour faciliter un accès plus rapide dans les grandes bases de données. Pour une recherche séquentielle, le nombre d'items à comparer pour la recherche d'un objet (nombre de distances à calculer) augmente linéairement avec la taille de la base. Les structures d'arbre permettent de faire des recherches beaucoup plus rapidement, en général en temps logarithmique.

Dans cette partie nous allons utiliser une méthode d'indexation fondée sur les arbres métriques (M-tree) [CIA97]. Elle nécessite la définition d’un espace métrique M = (D, d) pour mesurer la similarité entre les descripteurs, où D est le domaine des vecteurs descripteurs et d est la fonction de distance. L’arbre M-tree organise l’espace de vecteurs caractéristiques en un ensemble de régions (ou clusters) imbriquées. Chaque région correspond à un noeud de l’arbre et regroupe un ensemble d'objets similaires (ou très rapprochés). Il est composé de noeuds internes et de noeuds feuilles. Chaque noeud comporte un ensemble de M entrées au maximum (la capacité du noeud). Toute entrée d’un noeud feuille correspond à un objet de la base. L’arbre est construit par insertions successives. Insérer un nouvel objet (une forme) consiste à trouver le noeud feuille le plus convenable pour ajouter cet objet. Ceci entraîne éventuellement la division du noeud feuille s’il est saturé (voir le cours).

Recherche par similarité : pour réduire au minimum le nombre de noeuds consultés et le nombre de distances calculées, toutes les informations concernant ces distances sont stockées dans les noeuds de l’arbre. Dans ce travail, vous devez implémenter une requête par intervalle, dite « Range Query » : soit Q l'objet requête qui appartient à D et r(Q) la distance maximale de recherche, rangeQuery(Q,r(Q)) est une requête qui sélectionne tous les objets indexés Oj tels que d(Oj,Q) ≤ r(Q).

La description détaillé du M-tree (et de la fonction rangeQuery) est donnée dans le cours. Encore plus de détails se trouvent dans la référence [CIA97] (en anglais). Le fichier fourni (MTree.java) inclut le fonctions nécessaires pour définir un arbre vide et ajouter itérativement les éléments de la base. Attention, l'implémentation fournie fonctionne seulement avec un descripteur de type vecteur de nombres de type float, comme ceux que vous avez obtenus à la séance précédente lors de l'indexation de la Base10000. Le but de cette partie du TP est d'écrire la fonction de recherche rangeQuery() en utilisant le pseudo code donné dans le cours et de comparer les résultats obtenus en termes de réduction du nombre d'appels à la fonction distance pour les différents descripteurs d’images implémentes précédemment.

4.2. Travail à réaliser

Travail de programmation

1. Etudiez et familiarisez-vous avec le fonctionnement du M-tree (voir le cours et la référence [CIA97]).

2. Ajoutez une fonction rangeQuery(...) à la classe MTree, fonction qui effectue la recherche par intervalle.

3. Ajoutez une fonction main() pour tester votre implémentation. Celle-ci doit permettre de charger un fichier de descripteurs et de construire le M-tree correspondant ; utilisez une capacité du noeud de 20. Pour une image Q de la base, trouvez par essais le rayon approximatif r(Q) qui permet de récupérer 1/50 des images de la base les plus proches de Q (en utilisant la fonction rangeQuery). Pour cette valeur r(Q) calculez le nombre Nd d'appels à la fonction distance. Finalement, tirez aléatoirement 100 images Q de la base et calculez la moyenne des valeurs Nd résultantes. Cette valeur moyenne donne une mesure du gain obtenu par l'utilisation du M-tree.

Eléments a mettre dans le rapport

1. Le code de la fonction rangeQuery avec l'explication de son fonctionnement.

1

2. Pour les descripteurs image « HistoGray_64bins » et « HistoRGB_4×4×4bins », calculez le nombre moyen d'appels Nd. Faites varier la capacité du noeud ; pour quelles valeurs sont obtenus les meilleurs résultats (Nd moyen petit) ? Expliquez.

Code à fournir

1. Le fichier MTree.java avec vos contributions.

5. Références[CIA97] P. Ciaccia, M. Patella, P. Zelula, M-Tree: An efficient access method for similarity search in metric spaces, Proc. of VLDB, 1997.

[DAT08] R. Datta, D. Joshi, J. Li, and J. Z. Wang, Image Retrieval: Ideas, Influences, and Trends of the New Age , ACM Computing Surveys, vol. 40, no. 2, pp. 5:1-60, 2008.

[FLI95] Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Steele, D. & Yanker, P. , Query by image ans video content: the QBIC system, IEEE Computer, 1995.

[SWA91] M. J. Swain, D. H. Ballard, Color indexing, International Journal of Computer Vision 7(1), 11–13, 1991.

[GEV06] Th. Gevers, Color Feature Detection: An Overview, Color Image Processing: Methods and Applications, editors R. Lukac and K.N. Plataniotis, CRC Press, 2006.

1