Le titre de la thèse est "Mesure de similarité pour cartes généralisées"

 

Le jury est composé de :

M. Christophe, Fiorio, Polytech’Montpellier, LIRMM, Rapporteur

M. Pascal Lienhardt, Professeur, Univ. Poitier, XLIM-SIC, Rapporteur

M. Luc Brun, Professeur, ENSICAEN, GREYC, Examinateur

Mme. Raphaëlle Chaine,Maître de conférences, Univ. Lyon 1, LIRIS, Examinatrice

Mme. Christine Solnon, Professeure, INSA Lyon, LIRIS, Directrice de thèse

M. Guillaume Damiand, Chargé de Recherches HDR, CNRS, LIRIS, Co-Directeur de thèse

 

Résumé de la Thèse :

 

Une carte généralisée est un modèle topologique permettant de représenter implicitement un ensemble de cellules (sommets, arêtes, faces , volumes, : : :) ainsi que l’ensemble de leurs relations d’incidence et d’adjacence au moyen de brins et d’involutions. Les cartes généralisées sont notamment utilisées pour modéliser des images et objets 3D. Á ce jour il existe peu d’outils permettant l’analyse et la comparaison de cartes généralisées. Notre objectif est de définir un ensemble d’outils permettant la comparaison de cartes généralisées. Nous définissons tout d’abord une mesure de similarité basée sur la taille de la partie commune entre deux cartes généralisées, appelée plus grande sous-carte commune. Nous définissons deux types de sous-cartes, partielles et induites, la sous-carte induite doit conserver toutes les involutions tandis que la sous-carte partielle autorise certaines involutions à ne pas être conservées. La sous-carte partielle autorise que les involutions ne soient pas toutes conservées en analogie au sous-graphe partiel pour lequel les arêtes peuvent ne pas être toutes présentes. Ensuite nous définissons un ensemble d’opérations de modification de brins et de coutures pour les cartes généralisées ainsi qu’une distance d’édition. La distance d’édition est égale au coût minimal engendré par toutes les successions d’opérations transformant une carte généralisée en une autre carte généralisée. Cette distance permet la prise en compte d’étiquettes, grâce à l’opération de substitution. Les étiquettes sont posées sur les brins et permettent d’ajouter de l’information aux cartes généralisées. Nous montrons ensuite, que pour certains coûts notre distance d’édition peut être calculée directement à partir de la plus grande sous-carte commune.

Le calcul de la distance d’édition est un problème NP-difficile. Nous proposons un algorithme glouton permettant de calculer en temps polynomial une approximation de notre distance d’édition de cartes. Nous proposons un ensemble d’heuristiques basées sur des descripteurs du voisinage des brins de la carte généralisée permettant de guider l’algorithme glouton, et nous évaluons ces heuristiques sur des jeux de test générés aléatoirement, pour lesquels nous connaissons une borne de la distance. Nous proposons des pistes d’utilisation de nos mesures de similarités dans le domaine de l’analyse d’image et de maillages. Nous comparons notre distance d’édition de cartes généralisées avec la distance d’édition de graphes, souvent utilisée en reconnaissance de formes structurelles. Nous définissons également un ensemble d’heuristiques prenant en compte les étiquettes de cartes généralisées modélisant des images et des maillages. Nous mettons en évidence l’aspect qualitatif de notre appariement, permettant de mettre en correspondance des zones de l’image et des points du maillages.