Dans ce mémoire nous avons résumé nos principales contributions autour des cartes combinatoires et cartes généralisées qui sont : la définition générique des quatre opérations de base, la définition des cartes topologiques 2D et 3D, la définition des pyramides généralisées, le calcul d’invariants topologiques, et l’utilisation de ces résultats dans différentes applications.
Nous avons tout d’abord défini les quatre opérations de base, génériques et en dimension quelconque qui sont la suppression, la contraction, l’insertion et l’éclatement. Ces opérations peuvent être considérées comme la généralisation des opérateurs d’Euler, tout en jouant un rôle de factorisation puisque ces quatre opérations de base recouvrent et généralisent les nombreux opérateurs d’Euler 2D existants. Nous avons également défini l’opération de décalage d’arête, mais pour le moment uniquement en 2D et 3D. Ces opérations, et principalement l’opération de suppression, sont au cœur de nos travaux et servent dans différentes utilisations très diverses, allant de la segmentation d’images avec contraintes topologiques au calcul des générateurs des groupes d’homologie.
Nous avons ensuite défini les cartes topologiques en 2D et 3D, qui généralisent et étendent les travaux précédents autour de la définition de modèles topologiques de représentation de partitions d’images. Les définitions utilisent les opérations de base, et l’introduction du concept de niveau de simplification facilite l’étude de ces modèles en découpant les problèmes. Nous avons montré que ces cartes topologiques sont un bon outil pour manipuler les partitions d’images et pour définir ensuite des opérations de plus haut niveau.
Nous nous sommes également intéressés aux pyramides généralisées qui sont une extension hiérarchique permettant de manipuler au sein d’une même structure différentes résolutions d’une même carte. Nous avons défini cette structure à nouveau de manière générique en dimension quelconque, sans contrainte additionnelle sur les opérations utilisés pour la construction. Cela autorise différentes utilisations possibles, en ajoutant si besoin des contraintes supplémentaires. Nous avons ensuite étudié comment les informations pouvaient être retrouvées à travers les différents niveaux de la pyramide. Nous avons pour cela introduit la notion d’orbite généralisée, et montré que sous certaines conditions nous avions des propriétés intéressantes sur les cellules généralisées qui sont associées aux cellules.
Nous avons également étudié différentes méthodes de calcul d’invariants topologiques permettant de calculer la caractéristique d’Euler-Poincaré, les nombres de Betti, et les groupes d’homologie. Pour ces deux derniers invariants, nous avons pour le moment uniquement des résultats en 2D et 3D, et l’extension en dimension supérieure est une de nos perspectives de recherche. Pour ces algorithmes, nous avons proposé lorsque c’est possible une version permettant de calculer localement la mise à jour de ces invariants lors des opérations de simplification. Cela nous a permis de proposer une méthode de contrôle topologique des opérations de fusion que nous avons utilisée ensuite afin de contrôler l’évolution des nombres de Betti des régions obtenues au cours de l’application d’un algorithme de segmentation d’images 3D.
Enfin nous avons présenté différentes utilisations de nos travaux, principalement un projet de reconstruction de complexes architecturaux à partir de plans numériques, et des méthodes de segmentation d’images 2D et 3D. Ces différentes utilisations illustrent différentes possibilités applicatives, tout en montrant également l’intérêt d’avoir des opérations de base génériques puisqu’elles servent ensuite dans des cadres très différents.
Notre programme de recherche consiste à continuer d’enrichir les modèles à base de cartes de nouvelles opérations, en nous concentrant sur l’étude et le contrôle des propriétés topologiques, et à utiliser ces résultats théoriques au sein d’applications de traitement d’images et de modélisation géométrique. De plus, ces travaux peuvent être à chaque fois menés dans le cadre mono-échelle et multi-échelle. À long terme, notre objectif est de définir un cadre complet permettant la mise en place rapide de nouvelles méthodes, tant du point de vue théorique en s’appuyant sur des opérations de base génériques, prouvées, et autorisant un contrôle précis, que pratique, en utilisant des bibliothèques existantes et leurs fonctionalités.
Pour atteindre cet objectif, il reste à étendre plusieurs travaux présentés dans ce mémoire afin de les généraliser en dimension quelconque. C’est le cas de la définition de la carte topologique pour laquelle le principe des niveaux de simplification est déjà valide en dimension quelconque, mais pour laquelle il reste à étudier la définition de cellules fictives et leur décalage. En effet ces opérations existent pour le moment seulement pour les arêtes, et posent encore des problèmes dans le cas général.
C’est le cas également pour le calcul des nombres de Betti et des groupes d’homologie qui sont pour le moment uniquement définis en 2D et 3D. Pour atteindre cet objectif, nous avons déjà défini un opérateur de bord sur les G-cartes en dimension quelconque, et avons des premiers résultats non encore publiés mais très prometteurs sur son utilisation permettant de calculer les matrices d’incidences des cellules de la carte. De plus, nos premières expérimentations montrent un fort intérêt à coupler ces méthodes avec une passe de simplification utilisant les opérations de suppression pour diminuer à la fois les temps de calcul, et l’espace mémoire occupé par les matrices. Mais pour cela, nous devons étudier le lien entre les opérations de réduction sur les ensembles simpliciaux, et les opérations de suppression et contraction. En effet, il a été prouvé que ces opérations de réductions préservent l’homologie, et ce lien nous permettrait de prouver la propriété équivalente pour nos opérations.
Nous souhaitons également étudier plus précisément la notion de schéma polyédrique pour voir s’il est possible d’étendre nos méthodes de calcul de schéma polygonal en dimension supérieure. Cela rejoint une autre problématique théorique qui est sous-jacente à de nombreuses parties de nos travaux et qui est la caractérisation combinatoire des boules. En effet, différents algorithmes fonctionnent uniquement si les cellules de la subdivision sont des boules. Nous savons garantir cette contrainte si les objets sont orientables et de dimension 3, et lorsque la subdivision initiale vérifie cette contrainte, ce qui est le cas dans le cas des subdivisions cubiques des images 3D. Mais il serait très intéressant d’être capable de caractériser cette propriété pour vérifier si une carte donnée la respecte ou non. Cela semble un sujet ouvert très difficile, mais les pistes évoquées lors de la présentation de la caractéristique cellulaire d’Euler-Poincaré dans le cadre des G-cartes doivent être creusées.
Nous allons également étudier la possibilité d’étendre les opérations de base en relâchant les contraintes de cellules disjointes. Notre objectif est ici de pouvoir simplifier plus rapidement une carte. Cela fournirait une optimisation en temps de calcul puisque plusieurs passes pourraient alors être regroupées en une seule. Mais cela fournirait surtout une optimisation en espace mémoire dans le cadre des pyramides de cartes, en diminuant le nombre de niveaux nécessaires puisque plusieurs niveaux seraient regroupés en un seul. Ce dernier point est crucial pour que les pyramides puissent être utilisées dans des applications 3D réelles. La problématique est ici de garantir qu’il n’y a pas de perte d’information, c’est-à-dire qu’il est possible après l’opération de retrouver correctement les chemins de connexion entre les brins survivants, ainsi que les notions d’orbites généralisées.
Dans le cadre des cartes topologiques, nous devons maintenant valider nos méthodes au sein d’applications réelles de traitement d’images. Il faudra pour cela travailler en collaboration avec des spécialistes de traitement d’images pour résoudre des problèmes spécifiques et précis. Cela nous permettra de paramétrer nos algorithmes dans ces objectifs, en utilisant le contrôle topologique, et d’éventuelles opérations semi-automatiques. Nous attendons également de ce travail un retour nous permettant de mieux cerner les besoins en applications réelles, tant au niveau de nouvelles opérations, qu’au niveau des temps de calcul ou pour le contrôle topologique.
Toujours dans ce cadre, nous souhaitons étudier les opérations de bas niveaux travaillant sur les pixels/voxels de l’image, en commençant par la modification de la région d’un pixel/voxel. Ce type d’opération n’est pas simple à intégrer car la carte topologique représente les régions, donc les ensembles de pixels/voxels, mais l’accès et la modification des pixels/voxels n’est pas immédiat. Il est important de fournir également ce type d’opérations pour qu’un utilisateur puisse modifier directement les images en fonction de ses besoins. À partir de ces opérations, nous pouvons ensuite étudier différentes opérations qui s’appuient sur ces opérations de base comme par exemple des opérations de morphologie mathématique, de squelettisation ou encore des calculs de distances. Pour ces opérations, il peut être intéressant d’étudier l’apport d’un modèle global de représentation qui va permettre de calculer des informations rapidement sur la surface des objets. Dans ce cadre nous avons commencé à travailler sur un modèle déformable discret multi-étiquette [DDL09, DDL10] qui permet de modifier localement la géométrie d’une partition tout en préservant sa topologie. Enfin, à l’autre bout de la chaîne, nous devons poursuivre le développement d’opérations de haut niveau de traitement d’images, en profitant des spécificités de nos modèles pour guider les opérations et de les contrôler.
Un autre point de recherche, qui est totalement nouveau, concerne l’étude d’outils de comparaison de cartes. En effet, la seule opération qui existait jusqu’à présent pour comparer deux cartes était le test d’isomorphisme, ce qui est très limitant. Notre objectif est ici de proposer des outils permettant de comparer des cartes, par exemple pour savoir si deux cartes sont similaires ou au contraire totalement différentes. Nous avons donc débuté récemment des travaux autour de la définition ce type d’outils. Nous avons tout d’abord défini un algorithme de détection de sous-isomorphisme entre cartes [DdlHJ+09b, DdlHJ+09a] qui est polynomial. Nous avons également proposé une signature de cartes combinatoires qui permet une recherche polynomiale d’une carte dans une base de cartes [GDS09]. Nous poursuivons maintenant ces travaux autour de deux axes, dans le cadre de deux thèses co-encadrées avec Christine Solnon. Le premier axe, dans le cadre de la thèse de Stéphane Gosselin, concerne la fouille de données dans une base de cartes, où l’objectif est de rechercher la présence de motifs fréquents dans la base (un motif fréquent est une sous-carte apparaissant dans un suffisamment grand nombres de cartes de la base). Le second axe, dans le cadre de la thèse de Camille Combier, concerne la définition de mesure de similarité entre cartes. Cette mesure peut être vue comme une distance permettant de quantifier la similarité des cartes. Nous souhaitons ensuite utiliser cette mesure pour définir une distance d’édition calculant le nombre minimal d’opérations de base pouvant transformer une carte dans une autre. Ces travaux débutent juste mais nos premiers résultats sont très encourageants et montrent que la structure combinatoire et ordonnée des cartes nous permet de définir des algorithmes gloutons, là où il faut des recherches plus complexes avec des graphes étant donné que les arêtes ne sont pas ordonnées autour des sommets. Ces travaux doivent être réalisés de manière théorique et générique en dimension quelconque, puis de manière appliquée en s’attaquant à la résolution d’une problématique précise en utilisant ces nouveaux outils.
Enfin, les deux dernières perspectives de recherche sont très vastes, et pas du tout abordées pour le moment. La première perspective concerne l’étude de cartes permettant de représenter des partitions pouvant se chevaucher. Ce type de carte pourrait être intéressant, par exemple pour représenter des zones de flou au bord des régions, ou encore pour assigner plusieurs labels apportant des informations différentes à une même région. La problématique est ici complexe car le modèle même des cartes est très lié à la représentation des subdivisions. La seconde perspective concerne l’utilisation des cartes topologiques dans des images animées 2D ou 3D plus temps. En théorie, comme les cartes combinatoires sont définies en dimension quelconque, la représentation de ce type d’objet doit pouvoir de faire sans problème. En pratique, nous devons étudier l’impact de la non homogénéité dans les dimensions sur les opérations et sur les calculs des caractéristiques. Ce type de modèle ouvre des perspectives très intéressantes. Nous envisageons par exemple de faire du suivi d’objet, où une occlusion à un certain moment qui s’arrête plus tard pourrait correspondre à un tunnel ayant un générateur temporel.
Pour pouvoir aboutir, ces travaux doivent être menés en collaboration avec d’autres chercheurs, et dans le cadre de différents projets. Nous souhaitons pour cela poursuivre les collaborations existantes, mais également créer des nouveaux liens avec des spécialistes de traitement d’images concernant nos travaux autour de l’imagerie, ou de topologie algébrique pour les aspects liés aux invariants topologiques. Dans cet objectif, nous envisageons le dépôt d’un projet européen «Homology-based Discrete Image Processing» en collaboration avec le laboratoire XLIM-SIC de Limoges, le laboratoire CATAM de Séville, en Espagne, et le laboratoire PRIP de Vienne, en Autriche. Nous avons également participé au montage du projet «DigitalSnow: Géométrie discrète et mathématiques appliquées pour la métamorphose de neige», en collaboration avec le LAMA de Chambéry et le CEN de Grenoble, soumis à l’appel 2010 des programmes blanc de l’ANR. Enfin, nous sommes également impliqué dans le projet de David Coeurjolly «GigaSpel: Digital Geometry for High Performance n-D Image Analysis» soumis à l’ERC Starting Grant 2010. Ces trois projets tournent autour des problématiques liées à la représentation efficace d’objets 3D, 4D ou nD, à la définition d’opérations de manipulation, au calcul d’invariants topologiques, et à l’utilisation de tous ces outils dans la résolution de problématiques spécifiques. Ils illustrent bien la richesse de nos travaux, et les différentes possibilités de recherche tant au niveau théorique que pratique.
En effet, l’étude de toutes ces perspectives de recherches doit être menée conjointement de manière théorique et générique, de manière spécialisée afin de proposer des méthodes efficaces et éventuellement spécialisées, mais s’appuyant sur les bases fondamentales, et de manière pratique en implémentant et testant nos méthodes au sein de différents logiciels.