Soutenance mémoire
Protocole expérimental
Aucun consensus n’est actuellement adopté par la communauté sur un protocole expérimental standard permettant d’évaluer les méthodes d’indexation en grande dimension. Le choix de la base de données, des requêtes et de la vérité terrain est toujours difficile. Bien que des chercheurs aient proposé d’utiliser des données synthétiques, suivant une distribution aléatoire uniforme, il est maintenant accepté que ce contexte d’évaluation est peu réaliste. En règle générale, les travaux récents évaluent leur méthode sur des données réelles. Nous évaluons les performances de notre méthode avec la base de vidéos TrecVid (cf. Annexe A.1). Chaque keyframe est représentée par un vecteur de 128 dimensions obtenu en concaténant deux histogrammes, un histogramme de 64 chrominances de l’espace CIE Lab et un second de 64 textures issues des filtres de Gabor. Pour évaluer l’influence de la taille de la base de données, nous avons considéré 3 ensembles, le premier, de 43 616 images correspondant à la base de données Trecvid 2007 (cf. Annexe A.1), appelé DB1, le second, de 86 077 images obtenu en y ajoutant la base Trecvid 2008, appelé DB2 et la troisième, de 158 763 images, obtenu en ajoutant la base Trecvid 2009, appelé DB3. Pour chaque base de données, nous avons créé un banc de test en prenant aléatoirement 25 000 images requêtes. Pour chaque image requête, la vérité terrain est construite en effectuant une recherche KNN exhaustive (image requête exclue) basée sur la distance χ2. La vérité terrain permet, d’une part, d’obtenir le temps de recherche de référence et ainsi d’évaluer le facteur de rapidité de χ2-LSH. Elle permet, d’autre part, de construire l’ensemble des k images à retrouver afin d’évaluer la précision de la recherche approximée. Pour mesurer la précision nous utilisons la méthode d’estimation classique qui consiste à calculer la fraction d’images pertinentes retrouvées. La rapidité est mesurée par le facteur de gain en temps de recherche défini comme le ratio entre le temps de recherche de la méthode exacte et le temps de la recherche approximée. Cette mesure a l’avantage de ne dépendre ni de la machine ni du système d’exploitation utilisé. Le nombre d’images recherchées k peut varier suivant l’application visée, la base considérée, voire les besoins de l’utilisateur. N’ayant aucune information pour choisir k, il nous faut choisir une valeur arbitraire. Dans [GIM99], les évaluations ont été réalisée avec k = 1 et k = 10. Nous avons préféré fixer k = 20 qui a été utilisée dans [LJW+07], [VCPF07].
Efficacité de la recherche approximée : recherche exacte vs χ2-LSH
L’efficacité de χ2-LSH est évaluée avec deux jeux d’expérimentations qui permettent de mesurer l’influence des paramètres LSH ainsi que celle de la taille du jeu de données. Les trois paramètres de l’algorithme LSH sont : le nombre de tables de hachage (L), le nombre de projections par fonction de hachage (M) et la largeur de la fenêtre de recherche (W). Le premier jeu d’expérimentations permet d’étudier l’influence des paramètres M et W. Nous utilisons le paramètre L pour contrôler le compromis entre précision et rapidité. Pour étudier l’influence de W, nous fixons M à 26 et nous faisons varier W et L. La Figure III.2 montre l’influence des deux paramètres W et L pour la base DB3. Nous faisons varier W dans l’intervalle [125,160] et L dans l’intervalle [25,150]. Pour chaque paire de paramètres testée, la précision et la rapidité sont reportées. On observe que pour une même valeur de L, augmenter la valeur de W augmente les temps de recherche. En effet, plus on augmente la valeur de W, plus le découpage de l’espace opéré par les fonctions hi est grossier. Par conséquent, le nombre de buckets diminue et le nombre de points par bucket augmente. De plus, plus W est grand, plus la distance moyenne entre les points d’un même bucket augmente. Il en résulte que, lors d’une recherche, le nombre de faux points positifs augmente. Le nombre de candidats à examiner lors de l’étape de vérification des collisions est plus important ce qui accroît les temps de recherche. Cependant, augmenter W a également comme conséquence d’augmenter la précision. Comme le nombre de points par bucket augmente, la probabilité que les « bons » points (les ppv du point requête) se trouvent dans le bucket requête est donc plus importante. Le nombre de faux négatifs diminue. Un compromis entre la diminution des faux positifs et la diminution des faux négatifs doit donc être trouvé. Comme le montre la Figure III.2, le meilleur compromis est obtenu pour W = 140. En effet, pour toutes les valeurs de L testées, la courbe correspondant à W = 140 (en orange sur la figure) offre, pour une précision donnée, un gain en temps de calcul supérieur aux autres valeurs de W. Cependant, elle ne permet pas d’atteindre une précision supérieur à 90% pour un nombre de tables limité à 150. Etant donnée qu’il devient difficile d’envisager d’utiliser plus de 150 tables de hachage (pour des raisons de ressources mémoires : 150 × taille de la base × taille d’un pointeur vers un point) si une précision supérieure est nécessaire, il devient préférable de diminuer la valeur de W.
Ressources mémoires : recherche exacte vs χ2-MPLSH
Dans cette partie, nous évaluons l’amélioration de χ2-MPLSH sur χ2-LSH en termes de ressources mémoires. Avant de mesurer la diminution d’occupation mémoire, nous vérifions que l’algorithme de recherche χ2-MPLSH permet d’obtenir la même efficacité que χ2-LSH. L’ensemble des tests sont réalisés sur la base DB3. Les premiers tests ont pour but de vérifier que χ2-MPLSH est capable d’atteindre une précision de recherche similaire à χ2 -LSH tout en utilisant très peu de tables de hachage et donc beaucoup moins de ressources mémoires. Figure III.5, nous mesurons la précision en fonction de la rapidité de recherche de χ 2-MPLSH avec les paramètres par défaut de χ2-LSH : W = 140 et M = 26 pour 2, 4 et 6 tables de hachage. χ2-MPLSH requiert le réglage d’un paramètre supplémentaire, le nombre de probes T (nombre de buckets visités par table de hachage). Nous avons fait varier T entre 25 et 150. Ces valeurs peuvent paraître importantes mais elles sont à rapprocher du nombres de tables de hachage utilisées habituellement avec l’algorithme χ2-LSH. Il peut être noté que ces valeurs sont similaires à celles testées dans [LJW+07]. Comme montré sur la Figure III.5, pour atteindre une précision entre 0,8 et 0,9, seules 6 tables sont nécessaire pour χ2-MPLSH contre entre 75 et 150 pour χ2-LSH (voir Fig. III.3). De plus, seules 4 tables de hachage suffisent pour atteindre une précision entre 0,6 et 0,8.
Noyau sur sacs (BoF) vs Dictionnaire (BoW)
Dans ce paragraphe, nous mettons en évidence l’intérêt de l’approche noyau en comparant le noyau Kpower5 avec une implémentation classique de l’approche dictionnaire. Pour l’approche dictionnaire, toute image de la base ainsi que l’image requête est représentée par un seul vecteur. Ce vecteur est un histogramme d’occurrences des mots visuels du dictionnaire dans l’image. Les mots visuels sont obtenus par un clustering de type K-means des SIFT de la base. Nous avons utilisé les mêmes descripteurs locaux que ceux utilisés pour l’approche noyau. Nous avons testé les performances de la méthode pour différentes tailles de dictionnaire. Chaque valeur de l’histogramme est ensuite pondérée par le schéma classique tf-idf [PCI+07], qui diminue le poids des mots souvent présents dans la base et donc moins discriminants. Communément, la distance entre deux vecteurs ainsi construits est mesurée avec une distance l2. La recherche par similarité revient donc à effectuer une recherche des plus proches voisins au sens de la distance l2 entre l’image requête et les images de la base. Ne cherchant pas à comparer les temps de recherche entre les deux méthodes, nous n’avons pas utilisé de structure d’index, nous nous sommes donc contentés d’une recherche linéaire. On rappelle que les vecteurs de données étant creux (la majorité des composantes sont de valeurs nulles),la structure d’index souvent privilégiée dans ce contexte est les fichiers inversés. Les résultats sont rassemblés dans le Tableau V.6 pour des dictionnaires entre 100 et 1 000 mots.
Ressources mémoires
Les noyaux sur sac permettent d’atteindre une meilleure qualité de recherche que les approches classiques de types BoW pour les tâches de recherche par similarité. Cependant, la représentation BoW a l’avantage d’être plus rapide et de nécessiter moins de ressources mémoires (pour des dictionnaires de taille raisonnable). En effet, contrairement à la représentation BoF qui nécessite de stocker en mémoire primaire l’ensemble des descripteurs locaux pour chaque image, la représentation BoW nécessite juste de stocker une entrée pour chaque mot visuel du dictionnaire. La concision de cette représentation est rendue possible grâce à une quantification des descripteurs locaux qui entraîne une perte d’information et donc une diminution de la qualité de la recherche. Plus on garde d’information, plus on est précis mais moins on est efficace (aussi bien en terme de rapidité que d’occupation mémoire). Le choix de la méthode dépend donc du compromis entre précision et efficacité.Quand une précision importante est demandée, l’approche noyau sera alors préférée. Dans ce cas, l’occupation mémoire pourra tout de même être optimisée sans trop de perte de précision. Plusieurs travaux ont déjà proposé des solutions qui permettent de réduire les ressources mémoires. Dans [FS07], les auteurs ont réduit le nombre de descripteurs locaux par image et donc l’occupation mémoire d’un facteur 10 pour une qualité de recherche presque similaire. Dans [KS04], les auteurs utilisent une ACP qui permet de réduire la dimension des SIFT de 128 à 20 entraînant une réduction mémoire d’un facteur 6. Prenons le descripteur SIFT de 128 dimensions encodées en char. Stocker tous les descripteurs locaux de la base en mémoire vive nécessite : |B| × n × d octets de RAM, avec |B|, le nombre de descripteurs locaux par image, n, la taille de la base et d, la dimension d’un descripteur local. Pour une machine disposant de 32Go de RAM, avec 200 descripteurs locaux par image (en utilisant [FS07]), le système est capable de travailler avec les bases contenant jusqu’à 1,3M d’images.Pour de très grandes bases (plus de 10M d’images), le nombre de descripteurs locaux à stocker devient alors prohibitif et seules les approches vectorielles (BoW, GIST [TFW08]) sont capables de traiter une aussi grande quantité de données si l’on souhaite travailler en mémoire primaire.
|
Table des matières
I Introduction générale
1 Contexte
1.1 Techniques de recherche
1.1.1 Approche textuelle vs approche numérique
1.1.2 Le fossé sémantique/numérique
1.2 Explosion de la quantité d’information à traiter
2 Architecture des systèmes de recherche par le contenu
2.1 Indexation
2.1.1 Calcul d’index
2.1.2 Fonction de similarité
2.2 Moteurs de recherche
2.2.1 Système de détection de copies
2.2.2 Similarité sémantique et recherche interactive
3 Passage à l’échelle
3.1 Complexité de la recherche par similarité
3.2 Complexité de la recherche interactive
3.3 Accélération de la recherche
4 Evaluation des systèmes de recherche
4.1 Protocoles expérimentaux
4.2 Bases d’évaluation
5 Contributions et plan de la thèse
5.1 Passage à l’échelle de la recherche par similarité basées signature globale
5.2 Passage à l’échelle de la recherche par similarité basée signature locale
5.3 Passage à l’échelle de la recherche interactive par bouclage de pertinence
I Signature globale et recherche rapide dans les grandes bases d’images
II LSH, une structure d’index pour accélérer la recherche par similarité
1 Structures d’index pour CBIR
2 Table de hachage
2.1 Adressage direct
2.2 Hachage
2.3 Collisions
3 Locality-Sensitive Hashing : adaptation du hachage à la recherche des plus proches voisins
3.1 Fonction Locality-Sensitive
3.2 Concaténation de M fonctions : diminution de la fausse détection
3.3 Utilisation de L tables de hachage : augmentation de la bonne détection
4 Algorithmes de recherche
4.1 Hachage de la base
4.2 Etape de recherche
4.2.1 Problème (R, c)NN
4.2.2 Problème (R,1−δ)NN
4.2.3 Problème KNN
4.3 Implémentation
5 Principales fonctions de hachage
5.1 Hachage pour la distance de Hamming
5.2 Hachage pour la similarité du cosinus
5.3 Généralisation du hachage pour la similarité du cosinus aux similarités noyaux
5.4 Hachage pour la distance l1 et l2
5.5 Diminution des ressources mémoires : Multi-Probe
5.6 Amélioration du l2
III χ2-LSH : Schéma LSH optimisé pour les signatures globales 45
1 Construction de la clé χ2-LSH
1.1 Partitionnement de l’espace au sens de la distance χ2
1.2 Construction de la clé
1.3 χ2-LSH : une fonction Locality-Sensitive
2 Extension du Multi-Probe : χ2-MPLSH
3 Evaluation
3.1 Efficacité du hachage χ2
3.1.1 Protocole expérimental
3.1.2 Efficacité de la recherche approximée : recherche exacte vs χ2LSH
3.1.3 Ressources mémoires : recherche exacte vs χ2-MPLSH
3.2 Comparaison de la qualité de recherche entre χ2-MPLSH et E2-MPLSH
3.2.1 Protocole expérimental
3.2.2 Evaluation
4 Conclusion
II Signature locale et recherche rapide dans les grandes bases d’images
IV Similarité entre sacs de caractéristiques locales
1 Formalisme
2 Approches dictionnaires
3 Vector of locally aggregated descriptors (VLAD)
4 Stratégie par vote
5 Approches noyaux
6 Optimisation des fonctions noyaux
6.1 Kselect
6.2 Ultra fast
6.2.1 Principe
6.2.2 Algorithme
6.2.3 Propriétés de UFast
7 Conclusion
V Evaluation et discussion
1 Validation sur VOC06
1.1 Protocole expérimental
1.2 UFastK vs KSelect
1.3 Evaluation de UFastK pour Kpower
1.4 Evaluation de UFastK pour Kmatch
1.5 UFastK vs Vote
1.6 Noyau sur sacs (BoF) vs Dictionnaire (BoW)
2 Comparaison en utilisant la base INRIA Holidays
2.1 Protocol expérimental
2.2 Evaluation de la qualité de recherche de UFastK
2.3 Compromis qualité / temps de recherche de UFastK
3 Evaluation de différents détecteurs et descripteurs BoF sur VOC06
4 Discussions
4.1 Ressources mémoires
4.2 Intérêt du formalisme : BoW et noyau explicite
III Recherche interactive rapide dans les grandes bases d’images
VI Méthodes d’apprentissage interactif rapides
1 Recherche rapide du cœur de classe
1.1 Fonctions de similarité basiques
1.2 Recherche par sous échantillonnage
1.3 Recherche hiérarchique
1.4 K-VA files
1.5 Kernel Indexer : KDX
1.6 Recherche dans l’espace des caractéristiques
1.7 Synthèse
2 Recherche des images les plus proches de la frontière
2.1 Extension des méthodes de recherche du cœur de classe
2.2 M-Tree
2.3 Synthèse
3 Stratégie d’apprentissage interactif sous-lineaire basée sur la recherche ppv approximée
3.1 Justification de la construction du pool d’images
3.2 Sélection rapide d’un sous-ensemble d’images pertinentes
3.3 Stratégie active
3.4 Système
3.5 Algorithme et complexité
VII Evaluation de SALSAS
1 Plan expérimental
1.1 Bases
1.2 Critères d’évaluation
1.3 Paramétrage
1.3.1 Sessions de recherche
1.3.2 Paramètres internes des méthodes
1.3.3 Paramètres propres à SALSAS
1.3.4 Paramètres de la recherche KNN
1.4 Notations
2 Performances de SALSAS
2.1 SALSAS vs LIN_CHI2
2.2 Intérêt de χ2-LSH : Optimisation de la structure d’index
2.3 Analyse détaillée des résultats
3 Performance du système avec d’autres paramètres
3.1 Multi-requête
3.2 Système avec un noyau l2-RBF
3.3 Intérêt du χ2: comparaison des méthodes LIN_L2 et LIN_CHI2
4 Conclusion
VIII Conclusion générale et perspectives
1 Bilan
2 Perspectives
IX Annexes
A.1 Bases d’évaluation
A.2 Mesure de performances
A.3 Exemple de session de recherche interactive
Publications de l’auteur
Références bibliographiques
Télécharger le rapport complet
