– SATTIC

Une approche classique pour la description d'objets complexes consiste à projeter ceux-ci dans un espace d'attributs. La valuation de ces attributs conduit alors à une représentation par vecteurs d'attributs numériques. Pour exploiter un ensemble d'objets décrits par de tels vecteurs, et notamment faire du clustering, de la reconnaissance ou de la recherche d'information, on dispose de mesures de caractérisation statistique à la fois bien définies et facilement calculables. Cependant, de nombreux objets sont mal modélisés avec de tels vecteurs numériques, qui ne permettent pas de rendre compte de la structuration entre attributs. En particulier, nous nous intéressons dans ce projet à la représentation et la manipulation d'images de type vignettes (images de petites tailles) telles que celles retournées par les moteurs de recherche du type Google. Si de nombreux travaux ont été menés sur des images ayant des définitions élevées, aucun à notre connaissance ne concerne le traitement de ces petites images dont la définition est trop basse pour une segmentation en régions et/ou l'utilisation de mesures locales à vastes supports. Une alternative prometteuse consiste à modéliser les images par extraction et structuration de points saillants : les points saillants, correspondant à des zones de l'image à fort contraste, peuvent être facilement identifiés dans des images de faible définition comme les vignettes ; ils peuvent être structurés en chaînes, en arbres ou plus généralement en graphes, pour intégrer des informations sur leur degré de saillance ou leur localisation spatiale. Nous proposons dans ce projet d'étudier les possibilités offertes par cette modélisation par structuration de points saillants pour représenter, manipuler et exploiter des images vignettes. Cet objectif implique de définir un nouveau paradigme pour l'analyse et la caractérisation statistique de données symboliques structurées, en rupture avec les techniques classiques utilisées pour des données numériques. Verrous scientifiques Un premier verrou scientifique est constitué par la difficulté d'évaluer la similarité d'images. Ce point est indissociable de la structuration choisie pour modéliser les images. Dans notre contexte, les points saillants extraits des vignettes peuvent être structurés en chaînes, en arbres, ou plus généralement encore, en graphes. Il s'agit de définir une structuration symbolique pertinente pour modéliser des vignettes et une mesure de distance associée, la pertinence de la modélisation étant évaluée en fonction de sa capacité à refléter la similarité des images modélisées. La difficulté provient ici de la sémantique particulière des structures dans notre application. En particulier, le chaînage des points saillants représente ici un degré de saillance, et non une séquentialité forte comme c'est le cas dans les chaînes manipulées en bioinformatique ou en langue naturelle, ce qui impose de repenser les mesures de distance traditionnellement utilisées pour les chaînes. Un deuxième verrou scientifique provient de la nécessité de disposer d'une caractérisation statistique d'ensembles de structures symboliques (chaines, arbres ou graphes) modélisant des images : pour faire du clustering ou du filtrage, il est nécessaire de disposer de mesures statistiques telles que la moyenne ou la médiane, mais aussi de mesures de dispersion des structures dans l'ensemble, comme par exemple la variance, l'écart-type, ou la densité de probabilité. La difficulté essentielle pour caractériser statistiquement des ensembles de structures discrètes provient du fait que ces ensembles ne sont pas munis d'une relation d'ordre. Un troisième verrou scientifique réside dans la complexité du calcul de ces distances et mesures statistiques. Les ensembles à manipuler contiennent de grandes quantités de structures, chaque structure pouvant comporter plusieurs milliers de symboles, et les opérations à effectuer sur les structures sont généralement intrinsèquement combinatoires. Il s'agira donc de concevoir des algorithmes novateurs permettant un réel passage à l'échelle. Un dernier verrou scientifique provient de la nature très spéciale des données de notre application : la faible définition des vignettes interdit l'utilisation des techniques classiques de la reconnaissance de formes ; l'explosion de leur quantité sur la toile impose le développement d'algorithmes efficaces et novateurs pour leur traitement.