Ce sujet de thèse se place dans le contexte d'une application de classification d'images vignettes, dont la faible définition ne permet pas une modélisation par vecteurs numériques. On propose de modéliser ces vignettes par extraction et structuration symbolique de points saillants : les points saillants peuvent être facilement identifiés dans des images de faible définition comme les vignettes ; nous proposons de les structurer 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. Cependant, pour exploiter des ensembles de structures symboliques (chaînes, arbres ou graphes), il est nécessaire de disposer d'une mesure de distance entre structures, ainsi que de mesures pour caractériser statistiquement ces ensembles, comme par exemple la moyenne, la variance, ou la densité de probabilité.
L'objectif de cette thèse est de permettre le calcul de telles mesures : les ensembles à manipuler contiennent de grandes quantités de structures, souvent composées d'un grand nombre de symboles, et les opérations à effectuer sur les structures symboliques sont généralement intrinsèquement combinatoires. Il s'agira donc de concevoir des algorithmes novateurs permettant un réel passage à l'échelle. Cet objectif sera poursuivi en étudiant par exemple les deux pistes suivantes : l'optimisation par colonies de fourmis et la réduction de données.
La méta-heuristique d'optimisation par colonies de fourmis, introduite par M. Dorigo en 1992, s'inspire du comportement collectif des colonies de fourmis pour résoudre des problèmes d'optimisation combinatoire, et s'est montrée particulièrement performante pour la résolution de différents problèmes d'optimisation difficiles, comme par exemple le problème du voyageur de commerce. Il s'agira d'étudier dans le cadre de cette thèse les possibilités offertes par cette méta-heuristique pour
calculer efficacement différentes mesures entre structures symboliques.
Afin de réduire le nombre de mesures à calculer, une seconde piste à explorer consiste à réduire le nombre d'images contenues dans la base d'apprentissage, les images étant représentées par des structures symboliques. Il s'agit, pour chaque classe, de sélectionner un sous-ensemble optimal de structures symboliques ne remettant pas en cause la densité de probabilité de l'ensemble initial. On s'inspirera pour cela des travaux menés sur la réduction de données par la théorie
du boosting, qui ont donné d'excellents résultats sur des représentations numériques.