Application de la recherche top-k multicritères au contenu multimédia

Nous proposons une nouvelle méthode de recherche des k-plus proches voisins, utilisant un index facile à construire, à mettre à jour et à exploiter dans un contexte distribué. Cette méthode, appelée MSA (Multicriteria Search Algorithm), est inspirée des algorithmes top-k présentés dans les chapitres précé- dents, et exprime la recherche k-ppv comme un problème de recherche top-k multicritères particulier. Bien que conçue pour une recherche approximative, MSA a l’avantage de pouvoir, si nécessaire, fournir également des résultats exacts. La recherche par similarité du contenu à grande échelle vise à trouver dans une grande collection d’images, le sous-ensemble des images les plus similaires visuellement à une image requête donnée. Les techniques courantes reposent sur l’extraction des descripteurs locaux, typiquement des descripteurs SIFT (Scale-Invariant Feature Transform) [Mikolajczyk et al., 2005]. Ensuite, les descripteurs de la requête sont comparés avec ceux des images de la base, les images avec le plus grand nombre de correspondances sont considérées les plus similaires [Mikolajczyk et al., 2005]. Comme alternative à cette méthode, les des- cripteurs sont combinés en un seul vecteur considéré comme signature de l’image, et la signature de la requête est comparée à celles des images de la base [Sivic and Zisserman, 2003] [Negrel et al., 2012]. Dans les deux cas, l’objectif est d’effectuer le calcul de similarité entre les images le plus rapidement pos- sible. Pour effectuer cette recherche des plus proches voisins, des structures d’index et des algorithmes de recherche ont été proposés, tel que LSH [Indyk and Motwani, 1998], inverted files [Sivic and Zisserman, 2003], NV-tree [Lejsek et al., 2011], etc. Les principaux défis pour toutes ces techniques sont les suivants :

Nous proposons MSA, un nouvel algorithme utilisant une nouvelle structure d’index et s’inspirant des algorithmes top-k multcritères pour effectuer une recherche par similarité de contenu à grande échelle. La méthode MSA exploite la nature multidimensionnelle des signatures des images pour reformuler le problème de la recherche des k-plus proches voisins à grande échelle en tant que problème de recherche top-k multicritères. Cette méthode offre un bon compromis entre la rapidité de la recherche, les besoins de stockage et le coût de la mise à jour. Ces propriétés proviennent d’une structure d’index très simple basée sur des listes triées, faciles à mettre à jour et à distribuer. L’algorithme MSA propose une nouvelle méthode approximative de recherche des k-ppv basée sur les techniques top-k multicritères, avec des garanties sur les faux négatifs, et l’émergence rapide de bonnes approximations, améliorées de façon monotone et conduisant, si nécessaire, à un résultat exact. (q) D le résultat approximatif de la recherche des k plus proches voisins retourné par l’algorithme de recherche.

Intuitivement, la recherche k-ppv -exclusive garantit que même les bons candidats ratés dans le résultat approximatif de la recherche (faux négatifs), ont une faible qualité, car ils se trouvent à une distance d’au moins de la requête q. A noter que la condition -exclusive implique que pour tout point à la solution approximative, alors la qualité du résultat approximatif s’améliore quand la valeur de augmente et celle de diminue. Nous montrons dans la suite que l’algorithme MSA produit une recherche des k plus proches voisins -exclusive, avec une augmentation monotone de et une baisse monotone de .L’algorithme MSA s’inspire des techniques de traitement de requêtes top-k multicritères pour effectuer efficacement une recherche approximative des k-ppv dans une grande base d’images. Il se base sur une structure d’index composée de m listes triées, une liste pour chaque dimension des signatures des images. Pour une image requête donnée, l’algorithme MSA exploite cet index pour générer m processus de re- cherche indépendants, fusionnés à travers une approche top-k multicritères.L’algorithme MSA s’inspire des techniques de traitement de requêtes top-k multicritères pour effectuer efficacement une recherche approximative des k-ppv dans une grande base d’images. Il se base sur une structure d’index composée de m listes triées, une liste pour chaque dimension des signatures des images. Pour une image requête donnée, l’algorithme MSA exploite cet index pour générer m processus de re- cherche indépendants, fusionnés à travers une approche top-k multicritères.La figure 4.2 présente la structure d’index proposée par la méthode MSA. Comme nous l’avons déjà mentionné, nous considérons une base de données D qui contient des signatures d’images (vecteurs de m dimensions). L’index utilisé dans MSA est composé de m listes triées : L.