Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Mesures de similarité pour cartes généralisées [PDF]
Camille Combier [LIRIS]
11/2012
Établissement : Université Claud Bernard Lyon 1
Soutenue le Nov 28, 2012
Jury
Pr Fiorio Christophe, LIRMM, Montpellier Rapporteur
Pr Lienhardt Pascal, XLIM-SIC, Poitiers Rapporteur
Pr Brun Luc, GREYC, Caen Président
Mme Chaine Raphaëlle, LIRIS, Lyon Examinateur
Pr Solnon Christine, LIRIS, Lyon Directeur
M. Damiand Guillaume, LIRIS, Lyon Co-directeur
Contact : c.combier@gmail.com

TEL : tel-00995382

Résumé

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 objets3D. Á 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 maillage.

BibTex

Download

@PhDThesis{Liris-5884,
  title         = {{Mesures de similarité pour cartes généralisées}},
  author        = {Camille {Combier}},
  year          = {2012},
  month         = nov,
  school        = {Université Claud Bernard Lyon 1},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=5884}
}