Spécifications, contraintes et preuves
Dans ce thème, nous nous intéressons à la formalisation de la géométrie pour démontrer des théorèmes, construire des figures ou, plus généralement, des scènes géométriques, et certifier des algorithmes en géométrie.
Plus précisément, nous visons la définition formelle d'univers géométriques, la preuve de propriétés, la production automatique d'objets géométriques définis par une spécification exprimée dans et univers géométrique et la dérivation d'algorithmes géométriques certifiés corrects. Nous nous penchons sur des méthodes informatiques permettant d'assister les preuves, de garantir la correction et la faisabilité et, dans la mesure du possible, d'assurer automatiquement certaines tâches notamment à travers l'étude de tactiques Coq ou, dans un autre registre, la résolution de contraintes géométriques. Les retombées attendues concernent des domaines tels que la modélisation géométrique, l'algorithmique géométrique, la géométrie pure, l'enseignement des mathématiques et la planification assistée d'opérations chirurgicales percutanées ou assimilées.
Cela s'est traduit lors de ces dernières années par des activités de recherche dans quatre directions légèrement différentes mais participant du même esprit :
- Formalisation de la géométrie et preuves de théorèmes géométriques (N. Magaud, J. Narboux et P. Schreck) ;
- Spécification et preuves d'algorithmes géométriques en utilisant des cartes combinatoires (C. Brun, J.-F. Dufourd et N. Magaud) ;
- Spécification de figures et résolution de contraintes géométriques (P. Mathis, P. Schreck et S. Thierry) ;
- Formalisation et planification d'opérations percutanées dans le cas de l'ablation de tumeurs hépatiques et d'intervention radiologiques (C. Baegert, C. Essert et P. Schreck) ;
Participants permanents
- Deux professeurs : Jean-François Dufourd et Pascal Schreck
- Quatre maîtres de conférences : Caroline Essert, Nicolas Magaud, Pascal Mathis, Julien Narboux
Autres participants
- 1 Chercheur associé: Gabriel BRAUN (MC UFR LSHA, 09/2009-)
- 1 Maître de conférence en délégation CNRS: Laurent FUCHS (MC Poitiers, 09/2010-09/2011)
- 3 Post-doctorants: Claire BAEGERT (ATER, 01/2010-08/2010), Christophe BRUN (ATER, 01/2011-08/2011), Simon THIERRY (ATER, 10/2010-08/2011)
- 1 Doctorants: Rémi IMBACH (Ministère, 10/2010-)
- 3 Anciens doctorants: Claire BAEGERT (Région Alsace-IRCAD, 10/2005-12/2009), Christophe BRUN (Ministère, 12/2007-12/2010), Simon THIERRY (Ministère, 10/2006-09/2010).
Preuves de théorèmes
géométrie d'incidence et combinatoire
Nous travaillons à la formalisation en Coq des travaux issus de la thèse d'Agathe Chollet sur un modèle discret du continu : la droite d'Hartong-Reeb. Ces travaux en cours pourront donner lieu à une implantation effective du continu sur ordinateur. A plus long terme, nous envisageons de prouver formellement les résultats obtenus sur l'arithmétisation des fonctions et la connectivité des ellipses.
Spécification, preuves d'algorithmes et implantation
Cette recherche reconsidère la modélisation et l'algorithmique géométriques à travers des spécifications formelles et des preuves assistées par ordinateur. Elle s'appuie d'une part sur la modélisation géométrique à base topologique des subdivisions d'espaces par des hypercartes combinatoires, et d'autre part sur le Calcul des constructions inductives et le système Coq de l'INRIA. Cette manière d'aborder les problèmes n'a pas d'équivalent au monde. Ce travail est l'un des volets du projet ANR Blanc GALAPAGOS (2008-2011) sur la preuve assistée en géométrie. Par l'aspect topologie combinatoire, il est étroitement lié au thème "Modélisation et acquisitions" de l'équipe IGG.
Après tout un travail avec des spécifications algébriques, nous avons, depuis la fin des années 90, formalisé les hypercartes et leurs dérivés (cartes et cartes généralisées) et construit une bibliothèque Coq sur ces structures. Des preuves formelles ont été produites pour de grands résultats de topologie combinatoire : théorème de classification des surfaces, théorème du genre, formule d'Euler-Poincaré Duf08a.
Durant le présent contrat quadriennal, nous avons énoncé et prouvé un théorème de Jordan discret, donnant un critère de déconnexion des hypercartes utile pour prouver des algorithmes sur les hypercartes Duf08b Duf09. Nous avons proposé un algorithme fonctionnel de segmentation d'images 2D faisant un pattern-matching sur la structure inductive des cartes combinatoires décrivant les images. Nous en avons prouvé la correction en Coq et avons pu en dériver un programme impératif (en C) efficace, qui a été expérimenté sur des images couleur en vraie grandeur. (Travail de J.-F. Dufourd Duf07).
Nous avons aussi étudié plusieurs problèmes liés à l'algorithmique géométrique. Ainsi, nous avons travaillé sur les algorithmes de construction d'enveloppe convexe. Deux versions en ont été étudiées et prouvées correctes en Coq. La première, qui travaille par induction structurelle, repose sur des idées semblables à la segmentation évoquée précédemment. La seconde, qui repose sur une induction noethérienne, simule un algorithme traditionnel de construction incrémentale. Des programmes en ont été automatiquement extraits en Ocaml, et, de la seconde version a été dérivé un programme en C++, qui a été intégré à la plateforme CGoGn d'IGG. (Travail de thèse de C. Brun, encadré par J.-F. Dufourd et N. Magaud BDM11a BDM11b).
Un gros travail a été effectué sur la formalisation des subdivisions de surfaces, avec les opérations merge et split pour fusionner et éclater des cellules d'hypercartes. Il a été particularisé aux triangulations avec la définition de l'opération classique de rotation (ou flip) d'arêtes. Ceci nous a conduit à la première formalisation et preuve assistée en Coq d'un algorithme de construction d'une triangulation de Delaunay. Celle-ci travaille par une suite de rotations jusqu'à ce que toutes les arêtes soient valides par rapport à un critère de cercle de Delaunay. (Travail de J.-F. Dufourd et Y. Bertot, directeur de l'équipe Marelle de l'INRIA-Sophia DB10).
Spécification et résolution de contraintes
décomposition multi-groupes
Re-paramétrisation de systèmes
systèmes articulés
Utilisation de la géométrie
Formalisation et planification d'opérations percutanées
Dans ce travail nous proposons une approche originale pour l'assistance à la planification avec automatisation du positionnement d'un outil chirurgical. Notre méthode permet d'élaborer une stratégie optimale d'intervention, spécifique au patient et au type d'opération concerné, grâce à un calcul automatique qui se base à la fois sur l'expertise du domaine et sur des données préopératoires.
Dans cet objectif, nous avons mis en œuvre des approches issues de la modélisation déclarative et de la résolution de contraintes géométriques pour calculer automatiquement des trajectoires optimales d'outils chirurgicaux rectilignes rigides. Le calcul de trajectoire se fait en plusieurs étapes. Tout d'abord, l'expertise du praticien sur un type d'intervention donné est retranscrite sous forme d'équations mathématiques (égalités, fonctions de coût). Puis ces équations sont formalisées en contraintes géométriques, écrites sous la forme de termes combinant opérateurs géométriques et arithmétiques, et données issues des images médicales (IRM, CT). Un premier calcul permet de résoudre les contraintes géométriques dites "strictes" (booléennes) pour donner l'espace des solutions. Enfin, un deuxième calcul permet de résoudre les contraintes géométriques dites "souples" (numériques), grâce à une optimisation numérique, pour donner la solution optimale.
Nous avons testé nos approches sur 2 types d'interventions : l'ablation de tumeurs hépatiques par radiofréquence (hyperthermie) en collaboration avec le Pr. Gangi du service de radiologie interventionnelle de l'Hôpital Civil de Strasbourg, et l'implantation d'électrodes de stimulation cérébrale profonde en collaboration avec le Dr. Haegelen du service de neurochirurgie du CHU de Rennes Pontchaillou.
Le travail de thèse de Claire Baegert a porté sur ces travaux Bae09. De nombreuses publications ont porté sur ces thèmes, concernant la radiofréquence EBS09, BES07, BES07, BES07a, BES07b et la stimulation cérébrale profonde EHJ10. Ces travaux ont également donné lieu à une collaboration avec le DKFZ de Heidelberg sur l'accélération des calculs d'obstacles aux trajectoires par GPU ESF10, SES11.
Ces travaux ont donné lieu au projet ANR blanc ACouStiC, qui a démarré en janvier 2011 pour une durée de 4 ans, et dont IGG est partenaire. Ce thème de recherche s'insère également dans le cadre de l'IHU de Strasbourg "Institut de Chirurgie Mini Invasive Guidée par l'Image" ou Mix-Surg.
Perspectives
Spécification, preuves d'algorithmes et implantation :
Le travail sur la formalisation des structures combinatoires topologiques sera consolidé et amplifié. La bibliothèque d'hypercartes sera révisée et étendue en dimension n pour décrire et manipuler des subdivisions d'espace nD. Des liens seront établis avec les algorithmes de calcul des groupes d'homologie des variétés de dimension n.
L'expérimentation en preuves d'algorithmes géométriques sera poursuivie. L'accent sera mis sur les algorithmes de triangulation de Delaunay et de Voronoï en dimension 3, qui sont toujours des challenges, notamment en présence de contraintes. La question des approximations numériques sera également abordée. Jusqu'ici, elle a été évacuée de nos travaux au profit de calculs exacts dans les réels. Cette position devra être révisée, en examinant différentes hypothèses de travail : calcul exacts sur des rationnels, calculs approchés par intervalles, géométrie discrète, etc.
Enfin, le raffinement de nos structures abstraites d'hypercartes en structures concrètes en mémoire, notamment avec des pointeurs, devra être étudié. Le passage de nos algorithmes abstraits en programmes impératifs concrets avec pointeurs sera étudié, avec la preuve de conservation de la correction. Un travail préliminaire sur les structures linéaires et cycliques a déjà permis d'obtenir des résultats prometteurs.
Formalisation et planification d'opérations percutanées :
Concernant la planification d'opérations chirurgicales, dans le cadre entre autres du projet ANR blanc ACouStiC, nous allons entamer une extension du domaine des solutions possibles, en étudiant les trajectoires courbes et/ou multiples, ainsi que les trajectoires volumiques. Cela nous permettra d'étendre le champ des applications à des outils chirurgicaux déformables, insérés dans des tissus également déformables, ou encore à des outils multiples (par exemple la cryoablation de tumeurs du foie), ou enfin à des volumes d'accès par exemple pour la craniotomie dans le cadre d'exérèse de lésions cérébrales. Nous allons également travailler à la navigation contrainte dans l'espace des solutions, afin de restreindre la modification de la trajectoire proposée à un espace des solutions possibles et/ou raisonnables. Pour cela, le lien sera fait avec l'axe "Visualisation et interactions" et notamment le thème de recherche sur les interfaces à retour d'effort.