Soutenance HDR de Guillaume Damiand

13 Septembre 2010

---

Catégorie : Soutenance HdR

---

Composition du Jury:
M. Jean-Marc Chassery, Directeur de Recherches, CNRS, GIPSA-Lab, Rapporteur
M. Pedro Real, Professeur, Univ. de Seville, Dpt. Math. Appli., Rapporteur
Mme Monique Teillaud, Chargé de Recherches, INRIA, Sophia-Antipolis, Rapporteur
M. Luc Brun, Professeur, ENSICAEN, GREYC, Examinateur
M. Jean-Michel Jolion, Professeur, INSA de Lyon, LIRIS, Examinateur
M. Pascal Lienhardt, Professeur, Univ. Poitiers, XLIM-SIC, Examinateur
M. Bernard Péroche, Professeur, Univ. Lyon 1, LIRIS, Examinateur

Résumé:
Ce mémoire résume nos principales contributions aux cartes
combinatoires et cartes généralisées, deux modèles combinatoires
représentant des subdivisions d'objets en cellules (sommets, arêtes,
faces, volumes, ...). Ces modèles possèdent plusieurs avantages
qui justifient leurs utilisations dans plusieurs domaines comme la
modélisation géométrique et l'analyse d'images : ils sont définis en
dimension quelconque à partir d'un seul type d'élément ; ils
décrivent les cellules de la subdivision ainsi que toutes les
relations d'adjacence et d'incidence entre ces cellules ; des
contraintes de cohérence permettent de tester la validité des objets
manipulés ; ils autorisent la mise en oeuvre d'algorithmes
locaux, qui sont simples et efficaces en complexité.

Nos travaux portent sur l'étude de ces modèles, et sur la définition
d'algorithmes.  Nous avons tout d'abord défini quatre opérations de
base : la suppression, la contraction, l'insertion et
l'éclatement. Ces opérations sont les briques de base permettant de
modifier un objet, et peuvent être vues comme une généralisation des
opérateurs d'Euler. Elles sont définies de manière générale en
dimension quelconque. Il est ensuite possible d'ajouter des
contraintes supplémentaires selon les applications, et selon les
propriétés spécifiques à conserver.

Ces opérations sont au coeur de nos travaux. Nous les avons
utilisées pour définir la carte topologique 2D et 3D, un modèle
décrivant la partition d'une image en régions, puis pour définir des
opérations de fusion et de découpe sur les cartes topologiques. Nous
avons également défini les pyramides généralisées qui peuvent être
vues comme des piles de cartes, chacune étant obtenue par
simplification de la carte précédente. Enfin, nous avons proposé des
algorithmes de calcul d'invariants topologiques : la caractéristique
d'Euler-Poincaré, le schéma polygonal canonique, les nombres de
Betti, et les groupes d'homologies. Dans ces quatre cas, nous avons
à nouveau utilisé les opérations de base afin de proposer des
méthodes de mise à jour locales, ou pour simplifier la carte dans
l'objectif d'accélérer les calculs du fait de la diminution du
nombre de cellules.

Nous avons utilisés ces travaux théoriques dans différentes
applications. En modélisation géométrique, nous présentons le
modeleur Moka qui est un modeleur géométrique à base
topologique. Différentes applications se sont basées sur ce modeleur
et nous présentons plus en détail une méthode de reconstruction
automatique de bâtiments 3D à partir de plans numériques 2D. En
traitement d'images, nous avons utilisé les cartes topologiques afin
de proposer des algorithmes de segmentation d'images 2D et 3D
pouvant intégrer un contrôle topologique.