La problématique centrale de nos travaux est la représentation et la manipulation d’objets géométriques. Cette problématique se pose dans de très nombreux domaines, comme en modélisation géométrique, en traitement d’images, en rendu réaliste, en simulation d’écoulement de fluides…Dans chacun de ces cas, il est nécessaire d’avoir une structure de données décrivant les objets à manipuler et contenant suffisamment d’information pour les algorithmes utilisés. Cependant, ces informations ne doivent pas être en nombre trop important afin d’être capable de traiter un grand nombre d’objets. Le problème peut donc se résumer, comme souvent en informatique, à trouver le meilleur compromis entre espace mémoire et temps d’exécution des opérations. Mais un troisième problème important se pose dans notre cadre, qui est le pouvoir de modélisation de la structure de données. Ce problème est lié aux informations contenues dans celle-ci. En effet, il faut préciser ce qui est sous-entendu par représenter les objets et les informations, car de nombreuses solutions existent. Les questions auxquelles il va falloir répondre portent sur le type d’objets à représenter et le type de relations entre ces objets. Le choix de la «meilleure» structure de données va en effet dépendre de la dimension, de l’éventuelle régularité des objets, des possibilités pour les objets de se superposer, se toucher par un sommet ou une face…Selon les réponses à ces questions, le choix de la structure de données ne sera pas la même. Enfin, ce choix doit être également guidé par les algorithmes qui vont être utilisés par la suite. Si ces objets doivent uniquement être visualisés, et si nous disposons d’une carte graphique capable d’afficher uniquement des triangles, la meilleure structure de données sera sûrement une simple liste de triangles.
Il existe toute une gamme de structures de données qui ont été définies pour représenter des objets triangulés (triangles en 2D, tétraèdres en 3D, appelés simplexes en nD). Ces éléments de base sont mis en relations par des opérateurs qui vont décrire les relations d’adjacence et d’incidence. Ce type de structure a pour avantage principal d’être simple à mettre en œuvre, de pouvoir être défini en dimension quelconque, et enfin d’être directement utilisable dans des algorithmes de visualisation rapides. En effet, la plupart des moteurs de rendu actuels utilisent des triangles comme primitives de base. De plus, ce type de structure de données peut être mis en relation avec les objets simpliciaux définis en topologie algébrique, et il est alors possible de faire un lien direct entre la structure de données et une partie d’un espace topologique. L’inconvénient principal de ce type de structure se pose lors d’opérations de modification. En effet, certaines opérations produisent des objets non triangulés. Un autre inconvénient est qu’il faut un nombre important de simplexes pour décrire les objets.
Afin de résoudre ces problèmes, plusieurs structures de données ont été définies afin de pouvoir représenter les objets comme assemblage de n’importe quel type de cellules (et pas seulement des triangles). Parmi ces structures, les seules à avoir été formellement définies en dimension quelconque sont des structures proche de la notion de cartes. Ces structures de données ont plusieurs avantages qui justifient leur étude et leur utilisation. Elles sont définies en dimension quelconque à partir d’un seul élément de base. Le fait de ne pas avoir plusieurs structures de données liées entre elles simplifie les algorithmes, les mises à jour, et les développements informatiques. Une carte représente des objets subdivisés en cellules, et décrit toutes les relations d’adjacence et d’incidence entre ces cellules. De ce fait, il est très simple d’associer des informations à n’importe quelle cellule de la subdivision. De plus, l’accès aux différentes relations d’incidence et d’adjacence entre les cellules se fait en temps polynomial en le nombre de cellules dans le voisinage, ce qui donne des algorithmes efficaces. Enfin, le domaine des cartes est clairement défini et le lien formel entre les cartes et les modèles simpliciaux autorise le transfert aux cartes des nombreux travaux existant en topologie algébrique. Pour cette raison, les cartes ne sont pas seulement une structure de données mais bien un modèle mathématique de représentation des objets. De plus, des contraintes de cohérence précises existent et permettent de tester simplement la validité d’une carte.
Ces modèles sont relativement jeunes puisqu’ils ont pris leur essor au début des années 1990, et ils souffrent de ce fait d’un manque de reconnaissance et d’utilisation. De plus, les papiers de références sont très complets, mais du coup également peu abordables pour une personne non initiée, ce qui est une deuxième cause limitant leur utilisation.
Dans ce cadre, nos travaux ont débuté en 1998 tout d’abord dans l’optique d’utiliser les cartes combinatoires afin de décrire les partitions d’images 3D. Nous nous sommes très vite rendu compte qu’il existait un fossé entre les travaux menés en traitement et analyse d’images, et ceux menés en modélisation géométrique. Ce fossé s’expliquait par la manière dont les deux communautés s’étaient intéressées aux cartes : en modélisation, l’objectif est de manipuler et représenter des objets, principalement en 3D, et de définir des opérations de transformation ; en imagerie, les cartes étaient principalement vues comme une extension des graphes planaires représentant l’ordre des arêtes autour des sommets. De ce fait, les habitudes étaient de transposer les algorithmes sur les graphes en algorithmes sur les cartes, ce qui fonctionnait très bien en 2D, mais rendait difficile le passage en dimension supérieure. Après nous être rendu compte de ce problème, nous avons depuis lors essayé de mener de front des activités de modélisation géométrique et de traitement d’images afin que chaque domaine profite des résultats de l’autre, mais également pour que les deux domaines contribuent à de nouvelles avancées autour des cartes.
C’est ce type de réflexion qui nous pousse encore aujourd’hui à réfléchir aux opérations en termes les plus génériques possibles, en dimension quelconque, et sans fixer de contraintes liées à un cadre d’application. C’est dans ce cadre que nous avons défini des opérations de base qui sont les suppressions, contractions, insertions et éclatements. Nous montrons dans ce mémoire que ces opérations peuvent être vues comme une généralisation des opérateurs d’Euler.
Ces opérations sont au cœur de nos travaux et sont le fil conducteur de ce mémoire. En effet, nous avons eu très tôt l’idée de simplifier progressivement un objet à partir d’une carte de base, et d’une application d’une suite de simplifications, en les contrôlant afin de préserver certaines propriétés. Nous avons utilisé ce principe de simplification dans plusieurs problématiques très différentes abordées dans ce mémoire, qui vont de la définition des cartes topologiques, au calcul des groupes d’homologie, en passant par la segmentation d’images ou par des algorithmes de reconstruction de contour discrets.
Mais il n’est pas toujours possible de définir les modèles et opérations de manière générique en nD. En effet, il peut exister des contraintes d’efficacité et nous avons alors besoin d’optimiser un cas particulier par exemple pour des raisons d’espace mémoire. Il existe également des spécificités selon les dimensions. Par exemple en 2D, il est possible d’utiliser le théorème de classification des surfaces afin de définir un algorithme de caractérisation, alors que ce type de théorème n’existe pas en dimension supérieure. Une dernière raison pouvant limiter une définition générique peut tout simplement être la difficulté du passage en dimension supérieure qui fait que nous commençons par étudier les choses en 2D, puis 3D avant d’essayer de généraliser en dimension n.
C’est dans ce cadre que nous avons défini la carte topologique 3D, qui était le sujet initial de notre thèse [Dam01]. Afin d’arriver à cette définition, nous sommes reparti de la dimension 2, en nous reposant les questions de base sur les raisons d’être des modèles existants. Ce type de questionnement nous a amené à proposer la notion de niveau de simplification, qui utilise les opérations de suppression, et c’est cette notion qui nous a permis ensuite de définir de manière relativement simple les cartes topologiques en 3D alors que cela était beaucoup plus difficile de manière directe. Nous avons depuis beaucoup travaillé autour de ces cartes topologiques, en 2D et 3D, afin de définir des opérations de manipulation, comme la fusion ou la découpe de régions, qui nous ont servi ensuite à définir des opérations de segmentation d’images.
Nous avons également étudié différents liens entre les cartes et les invariants topologiques. En effet, il existait très peu de travaux sur le calcul d’invariants topologiques pour les cartes, et aucun ne permettant la mise à jour de ces invariants dans le cadre des opérations de simplification. Nous avons tout d’abord proposé une méthode de calcul de la caractéristique d’Euler-Poincaré, en nous appuyant à nouveau sur l’étude des opérations de base et sur leur impact sur l’évolution des nombres de cellules. Nous avons alors ensuite cherché à calculer d’autres invariants topologiques plus puissants. Cela nous a amené à étudier le calcul des nombres de Betti, puis des groupes d’homologie, pour le moment uniquement en 2D et 3D. Nous avons pu alors utiliser nos algorithmes de calcul des nombres de Betti au sein d’un critère de segmentation d’images 3D, ce qui nous a permis de définir une méthode de segmentation d’images avec contrôle topologique.
Au final, tout ces travaux vont dans la même direction : la définition d’outils performants, génériques, et topologiques de manipulation d’objets 2D, 3D ou nD. Ils ont été en partie réalisés au cours des thèses de Carine Simon, Sébastien Horna, Alexandre Dupas et Romain Goffe, que nous avons co-encadrés. D’autre par, ils ont été réalisés en collaboration avec d’autres chercheurs français: Olivier Alata, Sylvie Alayrangues, Eric Andres, Denis Arrivault, Mehdi Baba-ali, Fabien Baldacci, Yves Bertrand, Camille Bihoreau, Pascal Bourdon, Achille Braquelaire, Luc Brun, David Coeurjolly, Martine Dexet-Guiard, Jean-Philippe Domenger, Christophe Fiorio, Laurent Fuchs, Colin De La Higuera, Jean-Christophe Janodet, Jacques-Olivier Lachaud, Pascal Lienhardt, David Marcheix, Daniel Meneveaux, Christian Olivier, Samuel Peltier, Patrick Resch, Emilie Samuel, Xavier Skapin, Christine Solnon, Frédéric Vidil ; et étrangers : Yll Haxhimusa, Adian Ion, Walter G. Kropatsch. Enfin, une partie de ces problématiques ont été étudiées dans le cadre du projet ANR Fogrimmi de Janvier 2007 à Décembre 2010, dans lequel nous avons été porteur pour le laboratoire XLIM-SIC. Ces différents travaux montrent chacun, à différents niveaux, l’intérêt d’utiliser des cartes dans différentes problématiques, et nous espérons qu’ils participeront à promouvoir leur diffusion. Nous espérons également que ce mémoire œuvrera dans ce sens en regroupant en un même endroit les notions principales autour des cartes.
Le plan de ce mémoire est le suivant. Tout d’abord nous présentons au chapitre 2 les notions de base de la topologique algébrique, les modèles existants, puis nous présentons en détails les cartes combinatoires et les cartes généralisées. Ce chapitre est l’occasion d’éclaircir certains points, et de compléter des notions qui manquaient jusqu’alors. Le chapitre 3 présente les quatre opérations de base que nous avons définies en dimension quelconque dans le cadre des cartes généralisées : la suppression, son opération duale qui est la contraction, et les opérations inverses qui sont l’insertion et l’éclatement. Nous présentons également l’opération de décalage d’arête. Le chapitre 4 présente la carte topologique en 2 et 3 dimensions. C’est un modèle décrivant la partition d’une image en régions et qui est basé sur les cartes combinatoires. Sa définition utilise les opérations de base, qui sont contrôlées afin de garantir l’absence de perte d’information. Le chapitre 5 introduit les pyramides généralisées qui sont une extension hiérarchique des cartes généralisées, et donne les principales définitions utiles afin de retrouver les informations au sein de ce type de pyramide. Nous présentons au chapitre 6 des algorithmes de calcul d’invariants topologiques utilisant les cartes. Nous nous sommes intéressés à la caractéristique d’Euler-Poincaré, aux nombres de Betti, et aux groupes d’homologie. Le chapitre 7 illustre l’application de ces différents travaux dans quelques utilisations que nous avons pu faire. Pour le moment, nous avons principalement appliqué nos méthodes dans un projet de reconstruction de complexes architecturaux, et dans des algorithmes de segmentation d’images autorisant un contrôle topologique. Enfin, le chapitre 8 conclut ce mémoire et présente mon programme de recherche pour les années à venir.