Recherche:Outlook

Modélisation géométrique et topologique

La modélisation géométrique constitue le cœur de métier de l’équipe IGG depuis plus de 20 ans. Durant ce quadriennal, nous avons relancé ces activités avec succès et nous souhaiterions donc les intensifier durant le prochain quadriennal en travaillant les aspects fondamentaux et les applications.

En ce qui concerne les aspects fondamentaux, nous souhaitons continuer nos travaux en modélisation géométrique à base topologique, notamment en ce qui concerne les modèles non-variétés, les modèles multi-résolutions, multi-échelles, adaptatifs et hiérarchiques. L'originalité de notre approche consiste à nous appuyer sur la topologie pour formaliser ces modèles et mettre en évidence leurs propriétés combinatoires.

Nous cherchons à définir et à développer des modèles topologiques multi-résolutions devant permettre une représentation plus efficace des structures hiérarchiques classiques utilisées dans le cadre de la simplification de surfaces (décimation d'arêtes, fusion de sommets). Il s'agira ensuite de proposer diverses extensions de ces modèles pour généraliser les algorithmes de simplification à des objets 2D non variétés ou plus généralement à des complexes simpliciaux. Basile Sauvage, MCF recruté en 2006, étudiera spécifiquement la simplification de maillages surfaciques de très grande taille pour la visualisation en rapport avec l’opération 4. En effet, les maillages obtenus par reconstruction d'objets scannés sont aujourd'hui de taille considérable. Afin les visualiser, nous souhaitons donc travailler sur la simplification et la hiérarchisation de ces maillages. En particulier, il nous semble opportun de combiner différents critères (géométrie, topologie, texture, etc.) pour la mesure d'approximation et pour la hiérarchisation.

Dans le cadre des maillages volumiques multi-résolutions, nous voulons, d'une part, généraliser les représentations topologiques par cartes combinatoires que nous avons mises au point en dimension 2. D'autre part, il s'agira de développer les modèles mathématiques sous-jacents et les plongements associés. Pour cela nous souhaitons profiter de l'intégration dans IGG de Basile Sauvage (MCF), et de ses compétences en modèles multi-résolutions en bases d'ondelettes. Une application directe serait la simplification et l'approximation de maillages tétraédriques pour la visualisation de données scientifiques.

Dans le domaine de la détection de collision et de la simulation, beaucoup de structures de données spatiales et hiérarchiques sont utilisées pour accélérer les traitements (octrees, kd-trees, hiérarchie de boîtes englobantes ou de sphères). Nous souhaitons explorer l'utilisation de nos modèles hiérarchiques pour proposer de nouvelles structures accélératrices ou de nouveaux algorithmes.

Plate-forme de modélisation géométrique

Nous proposons de mettre nos principaux résultats à disposition de la communauté, notamment sous la forme d'une plate-forme logicielle autour de la modélisation géométrique.

En plus des modèles topologiques classiques (Cartes, G-Cartes, Hyper-Cartes), nous souhaiterions ajouter à la plate-forme tous les nouveaux modèles développés dans l'équipe comme les NM-Maps (cartes pour les non-variétés) et les cartes multi-résolutions.

Il est aussi prévu de développer de nouveaux modèles de plongement associés. En effet l'architecture de la plate-forme permet l'utilisation de plongements quelconques, et donc spécifiques à différentes applications (propriétés de matériaux pour la visualisation et la simulation, équations pour la modélisation sous contrainte, etc.). De plus certaines structures topologiques comme les non-variétés peuvent nécessiter des types de plongements spécifiques.

Un autre axe de développement est la création de ponts vers d'autres librairies plus matures (GTS, CGAL). Ceci nous permettra d'utiliser de nombreux algorithmes sans avoir à les re-coder. Nous devrons aussi développer les fonctions d'import/export du plus grand nombre possible de formats de fichiers.

Une dernière voie de développement à explorer est la création d'une couche d'abstraction qui devra permettre à des développeurs n'ayant pas de connaissances particulières des modèles topologiques sous-jacents d'utiliser notre plate-forme.

Applications médicales de la modélisation géométrique et topologique

Le foisonnement hétéroclite de modèles de représentation des objets virtuels provenant de sources variées de données réelles (images voxels provenant de l'imagerie médicale ou nuages de points provenant des scanners) et des nombreuses utilisations de ces modèles (visualisation ou simulation entre autres) pose des problèmes notamment de compatibilité ou d'utilisation conjointe. Nous souhaitons intensifier notre problématique actuelle autour de la conversion entre différentes représentations sans perte d'informations ou encore de la généricité de modèles à différentes échelles en liaison avec les applications.

Concernant les applications, celles-ci seront principalement centrées sur le domaine médical et thérapeutique, avec en particulier notre participation au programme multi-laboratoires IRMC (Imagerie et Robotique Médicale et Chirurgicale) sur des thèmes du Pôle de Compétitivité à vocation mondiale «Innovations Thérapeutiques» d'Alsace. Dans le cadre du projet ANR VORTISS, nous étudierons les apports possibles de la modélisation à base topologique, pour le développement d'une plate-forme de simulation d'opérations chirurgicales. Les différentes applications visées seront :

• La définition de modèles topologiques adaptés à la modélisation d'organes : modèles volumiques, multi-résolutions, prenant en compte les propriétés physiologiques, les tissus inter-organes et adaptés au couplage avec des moteurs de simulation physique.

• La reconstruction des organes du corps humain à partir d'images IRM en étant aussi fidèle que possible à la réalité anatomique humaine. Dans le processus de reconstruction (passage de données voxels à un maillage surfacique et volumique multi-résolutions), nous prendrons en compte les relations topologiques comme les inclusions, intersections et adjacences entre les structures anatomiques.

• La reconstruction de structures arborescentes comme les vaisseaux sanguins. Nous tenterons de résoudre le problème lié à la modélisation des embranchements en s'appuyant sur leur modélisation topologique et nos travaux sur les surfaces de subdivisions.

• S’agissant de la navigation virtuelle dans les organes et vaisseaux sanguins, nous voulons utiliser nos travaux sur les structures accélératrices, pour permettre une navigation temps réel dans les organes reconstruits, puis pour simuler les interactions avec des outils de chirurgie mini-invasives.

• Pour la planification d'opérations chirurgicales, nous allons travailler à la description d'un langage utilisateur de haut niveau permettant de décrire les règles de l'art et l'expertise du praticien.

Le recrutement en 2007 de Rémi Allègre, spécialiste de géométrie algorithmique et de reconstruction, permettra de poursuivre le renforcement de l’équipe autour de la thématique de la modélisation géométrique et de ses applications notamment médicales.

Résolution de contraintes géométriques

Nous suivrons deux directions de recherche :

• La généralisation de notre approche en tirant parti de l'invariance par certains groupes de transformations géométriques à des groupes à action locale en développant une algèbre des groupes de transformation élémentaires.

• La reparamétrisation, en étudiant notamment des méthodes numériques adaptées au problème et les liens entre la reparamétrisation et la décomposition de systèmes de contraintes tirant parti de l'invariance.

Formalisation de la géométrie

De nombreuses questions de base concernant la géométrie, et plus particulièrement la preuve en géométrie, sont sous-jacentes à la résolution des contraintes géométriques. Nous nous sommes intéressés d'un point de vue assez pragmatique à la preuve d'incidences forcées dans des configurations de systèmes de contraintes à travers l'utilisation du théorème de Pascal ou de calcul de rang de matroïdes (voir [2-MS06]). Nous comptons continuer dans cette direction en ré-étudiant les bases de la géométrie d'incidence via le prouveur Coq. Les objectifs à terme sont multiples, nous voulons

• Développer des algorithmes efficaces et certifiés pour faire des preuves d'incidences forcées ;
• Faire des constructions utilisant uniquement des contraintes d'incidence (pour pouvoir notamment construire des "témoins" selon la terminologie de D. Michelucci) ;
• Etendre le cadre géométrique de l'incidence pour pouvoir garantir la robustesse des méthodes de résolution géométriques formelles.

Le recrutement de Julien Narboux en 2007 qui a associé preuves en coq et constructions géométriques devrait permettre de renforcer ce thème.

Spécifications et preuves en géométrie

Les expériences précédentes sont les prémices d'une entreprise originale de grande envergure que nous entendons mener au LSIIT. Nous formons en effet aujourd'hui un groupe cohérent autour de Coq pour attaquer la géométrie, après les recrutements de Nicolas Magaud et de Julien Narboux, spécialistes de preuves assistées, ayant tous deux une expérience de spécification et de résolution de problèmes. Nicolas Magaud a travaillé sur l'arithmétique et les changements de représentation, domaines utiles pour la modélisation géométrique et l'approximation en algorithmique géométrie (INRIA-Sophia, équipe de Yves Bertot). Julien Narboux a formalisé l'axiomatique de la géométrie de Tarski, la méthode des aires de Gao et Chou, et la méthode de preuve de Wu, et a conçu et réalisé un système complet d'aide à la construction géométrique et à la preuve interactive pour l'enseignement (LIX, équipe de Hugo Herbelin, 2006, TU de Munich, équipe de Tobias Nipkow, 2007). Nous sommes également en possession de toutes les bases topologiques permettant de modéliser et de prouver les propriétés des subdivisions de surfaces.

Notre travail va se développer dans plusieurs directions mêlant spécification, conception, preuve et certification d'algorithmes :

Topologie combinatoire : approfondissement de certaines propriétés et preuves d'autres grands résultats. Le prototype en est le théorème de Jordan discret, que nous sommes en train de réexplorer de manière plus réaliste que dans la thèse de Puitg, sans faire intervenir de point de vue observationnel, et en découpant bien une hypercarte donnée selon un anneau de brins. Nous en aurons même une extension avec un algorithme permettant de dire combien de nouvelles composantes connexes sont engendrées par cette découpe. Modélisation géométrique : passage en 3D, et même en nD, avec des hypercartes de dimension n, permettant de subdiviser des espaces de dimension n. Nous explorerons aussi d'autres modèles de nature combinatoire. Ainsi, les ensembles ou complexes simpliciaux sont de bons candidats puisqu'une première spécification fonctionnelle en avait été réalisée lors du DEA de Jean-Baptiste Surgant en 2002. Nous pensons aussi attaquer la spécification des subdivisions adaptatives, qui fait l'objet d'études dans l'opération 1.

Algorithmique géométrique : Nous poursuivrons nos travaux sur la révision des notions et algorithmes de base, notamment ceux mettant en jeu des subdivisions. Après notre algorithme incrémental d'enveloppe convexe avec des cartes et Coq, nous tenterons de formaliser et de certifier les algorithmes de Jarvis et de Graham, pour étendre les résultats de Bertot-Pichardie et Fleuriot-Meckle. Parmi les problèmes classiques du plan que nous avons en ligne de mire figurent l'appariement de droites, proche du co-raffinement de cartes, pour lequel une preuve de correction reste à produire. Toujours avec nos techniques, nous visons bien sûr tout particulièrement la construction des diagrammes de Delaunay et de Voronoï, et leurs innombrables variantes. Les questions inhérentes aux approximations numériques ne seront pas traitées de front, mais contournées, en utilisant des prédicats décidables comme les tests d'orientation de Knuth, basés sur des triplets de points.

Géométrie classique et enseignement des mathématiques : axiomatisation de géométries classiques en Coq, dans la lignée du travail déjà effectué ici sur la géométrie de Hilbert (DEA de Christophe Dehlinger), ou du travail du LIX sur la géométrie de Tarski (thèse de Julien Narboux). L'objectif est de fournir des outils d'élaboration et de certification de programmes de constructions géométriques, avec des boîtes à outils variées. Le prototype en est la problématique de la construction à la règle et au compas. Sur ce thème, nous serons très proches de certains travaux de l'opération 2.

Acquisition, analyse, synthèse et représentation de textures

Nous souhaitons poursuivre nos actions concernant les textures, notamment avec la thèse de L. Amman. En effet, la numérisation de l'apparence, et plus généralement d'un certain matériau, engendre des manipulations fastidieuses et nécessite un contrôle très précis des conditions d'éclairage. Le nombre d'images qui doivent être capturées est extrêmement élevé. Outre ces manipulations importantes et ces contraintes fortes, la masse de données engendrée dépasse souvent très largement les capacités des cartes graphiques. Il n'existe pas à ce jour de technique satisfaisante d'acquisition d'un matériau qui soit à la fois simple du point de vue de la manipulation (peu de prises de vue avec un éclairage non totalement maîtrisé), compacte et correcte du point de vue de l'erreur commise lors de la restitution sur écran. Le recrutement de Rémi Allègre en 2007 confortera également cette thématique.

Visualisation de données volumiques scientifiques et couplage

Concernant la simulation et la visualisation de données scientifiques, nous souhaitons élargir notre activité aux simulations médicales, notamment concernant la modélisation de l'ablation des tumeurs par radiofréquence. Nous souhaitons mettre à profit une collaboration l'équipe Equations aux Dérivées Partielles et Théorie du Contrôle (EDPTC) de l'IRMA, pour modéliser des échanges de chaleur dans les tissus de façon précise et rapide, avec un objectif à moyen terme de processus en temps interactif. Ces thématiques seront également abordées au sein du projet ARA Masse de Données VORTISS. Par ailleurs, nous souhaitons profiter de l'intégration dans IGG de M. Torregrossa (MCF associée) et de ses compétences en physique optique et photonique pour développer la simulation de la propagation d'un rayonnement électromagnétique dans un tissu biologique comme par exemple le cerveau humain [5-MCT05]. L'objectif principal sera de réaliser un simulateur de propagation de la lumière en 3 dimensions, pour les milieux respectant l'équation de diffusion, c'est à dire, les milieux diffusants.

Interagir avec les objets

Nous allons poursuivre nos travaux sur l'interaction 3D en liaison avec la modélisation géométrique et les applications médicales. Notre approche consistera à proposer des solutions multimodales pour enrichir et faciliter l'interaction avec l'environnement virtuel en couplant informations visuelles et informations haptiques notamment par l'introduction du retour d'effort et de l'interaction bimanuelle. Voici quelques perspectives déjà engagées autour des déformations en modélisation géométrique.

Nouvelles modalité d'exploration.

L’ajout de nouvelles modalités d’exploration de l’environnement sera également étudié. Ainsi, la «métaphore du potier» permettra d’évaluer rapidement et sans effort les résultats des déformations réalisées en tournant autour de l'objet par simple mouvement de la main sur l'écran horizontal du workbench.

Modes de visualisation augmentés.

La perception du positionnement relatif des formes géométriques dans l'environnement peut parfois s'avérer problématique, en raison des techniques de visualisation employées, et de la difficulté posée par le simple changement de point de vue de l'utilisateur par rapport à l'application. L’utilisation de modes de visualisation «augmentés» (par exemple, les ombres portés des objets) permettra d'apporter à l'utilisateur des indices visuels importants pour la perception des informations de profondeur, par exemple. D'autres modes de visualisation, comme la coloration surfacique de la zone contrainte par une déformation réalisée, permettront de donner à l’utilisateur un feed-back en temps réel sur l’état de l’interaction.

Techniques d'assistance aux gestes.

Le manque de précision des périphériques utilisés (notamment les gants de données) sera compensé par une technique d’assistance pour la sélection du point d’application de la contrainte initiale et le contrôle du geste de déformation. Il s'agira, par exemple, d’aider l’utilisateur à «saisir» des maxima locaux par l’implémentation d’une métaphore de type «puits de potentiel». Le geste de déformation pouvant s’avérer imprécis, la correction des erreurs de manipulation grâce à des algorithmes de lissage des mouvements parasites et/ou de correction de la trajectoire en fonction des caractéristiques de la contrainte de déformation sont en cours d'étude.

Matérialisation de propriétés par le retour haptique.

Nous étudierons la matérialisation de propriétés quelconques sous forme tactile dans un but de réduction de la surcharge visuelle. Nous améliorerons le contrôle gestuel avec introduction du retour d’effort en particulier dans les applications de déformations géométriques et de simulation des gestes chirurgicaux.

Plate-forme de réalité virtuelle

Nous proposons de mettre nos principaux résultats à disposition de la communauté, notamment sous la forme d'une plate-forme logicielle autour d'une boîte à outils virtuels d'interaction en lien avec la plate-forme IRMC. Nous mettrons également nos forces en commun avec la plate-forme de réalité virtuelle mise en place par la région Alsace en 2007 (Iconoval et Holo3). L'ingénieur de recherche CNRS que nous recruterons en 2007 portera ce projet en collaboration, d'une part avec le responsable de la plate-forme de réalité virtuelle de la Région Alsace, Silvère Besse, et d'autre part en cohérence avec la plate-forme IRMC dans le cadre du pôle de compétitivité à vocation mondiale "Innovations Thérapeutiques".

Nous intégrerons dans cette plate-forme de réalité virtuelle des techniques d'interaction permettant la sélection, la manipulation et l'édition de grands ensembles d'objets dans des scènes 3D complexes. Ce travail sera appliqué à la modélisation et l'édition de détails dans les scènes naturelles, et au traitement et à la visualisation interactive de données complexes de grande taille issues de la simulation numérique (ANR Masse de données DNA et MASSIM).

Applications médicales et réalité virtuelle

Concernant les applications, celles-ci seront principalement centrées sur le domaine médical et thérapeutique, avec en particulier notre participation au programme multi-laboratoires IRMC (Imagerie et Robotique Médicale et Chirurgicale) sur des thèmes du Pôle de Compétitivité à vocation mondiale «Innovations Thérapeutiques» d'Alsace.

Manipulation, visualisation et navigation virtuelles dans le corps humain.

Une première application médicale aura pour objectif l'élaboration de méthodes et d'outils spécifiques et ergonomiques pour la simulation réaliste du geste chirurgical. Ainsi, nous développerons des techniques de navigation et de manipulation virtuelles dans un modèle du corps humain (abdomen) avec palpation et planter d’aiguilles pour la radiofréquence et endoscopie virtuelle dans les vaisseaux.

Traitement des troubles psychiatriques par réalité virtuelle.

Une seconde application médicale visera à étudier l’impact de la réalité virtuelle sur les traitements psychiatriques des phobies ou des troubles obsessionnels compulsifs (TOC) par des thérapies comportementales et cognitives (TCC). L'immersion d'un malade dans un environnement virtuel permettra de le mettre en situation de manière graduelle et d'explorer l'effet de la variation de nouveaux paramètres sur l'appréhension du malade. L'interaction avec l'environnement virtuel offrira une simulation immersive réaliste d'une situation réelle anxiogène. Les troubles alimentaires seront étudiés en collaboration avec le LINK (Céline Clément) et un psychiatre (Marc Villard). La schizophrénie pourrait également se prêter à une étude en collaboration avec le professeur Danion des Hôpitaux Universitaires de Strasbourg.