Titre du sujet: Navigation visuelle dans les bases de données d'images

 

Encadrants: Nicolas Hanusse, Jenny Benois-Pineau

 

Equipe de recherche: Combinatoire et Algorihtme (dans le cadre de

l'ACI "Masse de données")

 

Description détaillée:

 

Les images et les vidéos peuvent être indexés à l'aide de descripteurs (cf. [1]) basés sur la couleur, la structuration spatiale,

la reconnaissance d'objets ou le déplacement de caméra (pour la vidéo).  L'indexation permet de naviguer dans des bases

d'images ou de scènes mais chercher une image au milieu de

plusieurs millions d'images  reste toujours un challenge. 

 

Une approche récente propose de considérer un graphe modélisant toutes les images d'une base à travers leurs

descripteurs. Les sommets représentent les images et la pondération (ou étiquetage) des arêtes mesure la

similarité (ou dissimilarité) entre images.

 

Si on décide d'enlever des arêtes, on obtient un graphe peu dense qui, a-priori,

ne possède pas de propriétés particulières. La recherche d'une image dans ce graphe peut être vu comme une marche dans ce

graphe: l'utilisateur visualise l'image courante ainsi que les images

voisines; décide quelle est l'image la plus proche de celle qu'il recherche et itère ce processus jusqu'a obtenir l'image

recherchée.

 

Cette méthode peut s'avèrer efficace si le graphe sous-jacent possède des bonnes propriétés de petit-monde: petit

diamêtre, nombreux courts chemins, densité locale forte et densité globale faible ... <br>

 

L'objectif de ce mémoire est:

* de construire le graphe sous-jacent sous la forme de spanners

* de transformer le spanner en graphe petit-monde;

* de mettre en place un protocole expérimental pour valider la méthode de recherche d'image;

* d'étudier la pertinence des différents descripteurs lors des expérimentations.   

 

Bibliographie:

 

[1] The MPEG-7 Visual Standard for Content Desciption - An Overview,

Thomas Sikora, IEEE Transactions on circuits and systems for video

technology, vol 11, num 6, 2001

 

[2] Distributed MPEG-7 Image Indexing using small world user agents,

Androutsos and al., 2004

 

[3] Exact and approximate distances in graphs, Zwick, ESA 2001

 

[4] "The small-world phenomenon: An algorithmic perspective", Kleinberg, 2000 

 cf  http://www.cs.cornell.edu/home/kleinber/swn.psKleinberg