Géométrie discrète

D'un point de vue arithmétique, une droite discrète du plan est l'ensemble des points de coordonnées (x,y) de Z² vérifiant une double inégalité de la forme m <= ax + by < m + w, avec a, b, m, w entiers. Les propriétés des droites discrètes définies de la sorte sont en relation étroite avec les propriétés des nombres entiers et offrent des rapprochements avec la combinatoire des mots. Les plans discrets sont définis de manière analogue. Ces définitions analytiques procurent une représentation compacte des objets discrets. Il est alors possible d'étudier des objets intrinsèquement discrets (pas uniquement des approximations d'objets continus), et de définir des objets discrets infinis.

Notre approche vise à résoudre proprement des problèmes pratiques posés par la non-validité de la plupart des théorèmes euclidiens dans un espace discret, par exemple l'intersection de deux droites discrètes. Elle permet également d'éviter les erreurs engendrées par l'utilisation de nombres réels codés en virgule flottante ; les conséquences pour les calculs géométriques et graphiques sont très importantes en particulier lorsqu'une décision de nature topologique dépend du résultat numérique (par exemple l'appartenance d'un voxel à l'intérieur d'un polyèdre). Cette approche arithmétique se différencie de la topologie discrète qui considère l'objet discret sous un angle topologique plutôt que par ses propriétés combinatoires.

Nos travaux portent essentiellement sur :
- la définition et l'étude de nouvelles classes d'objets discrets,
- la reconnaissance analytique permettant, non seulement de dire si une suite de points est ou non un objet discret donné (segment de droite, morceau de plan, cercle, ...), mais aussi de fournir les coefficients des inéquations analytiques correspondantes,
- la reconstruction analytique visant à passer d'une représentation en compréhension du discret à une représentation en compréhension du continu.
L'application première de ces algorithmes se trouve en informatique géométrique et graphique, en particulier en synthèse d'image, traitement d'image, analyse de documents et imagerie médicale. Elle a aussi trouvé des applications dans des domaines où la géométrie intervient moins directement, comme la cristallographie.

Un des thèmes développés est l'étude des courbes et surfaces discrètes bruitées. Notre objectif est d'élaborer, dans le cadre de la géométrie discrète, un formalisme adapté à ces objets tenant compte du bruit inhérent aux outils et méthodes d'acquisition. L'analyse des propriétés arithmétiques, géométriques et combinatoires de ces courbes et surfaces discrètes bruitées s'appuie sur une définition analytique des objets discrets, par exemple en généralisant les notions de segments de droites discrètes et de morceaux de plans discrets. Ce travail vise l'élaboration d'algorithmes performants de reconnaissance, de parcours, et d'extraction de paramètres géométriques tels que le périmètre, la courbure, la normale, etc..., et à terme, la reconstruction d'objets continus correspondant aux structures discrètes étudiées.

Reconnaissance de structures discrètes

L'idée générale est de travailler à partir de données discrètes puis, grâce à des définitions analytiques d'objets discrets, d'identifier si les données initiales correspondent à des objets discrets connus, c'est ce que nous appelons la reconnaissance.

Droites discrètes 2D et 3D -- Suite à un travail sur la reconnaissance exacte de droites discrètes, nous avons défini la notion de segment flou 2D, en relation avec la définition arithmétique des droites discrètes où l'épaisseur est paramétrable. Un segment flou est une suite 8-connexe de points qui appartiennent à une droite discrète dont l'épaisseur est donnée. Un paramètre, l'ordre du segment flou, contrôle l'amplitude du bruit autorisé en fixant l'épaisseur de la droite englobant le segment flou. Nous avons élaboré un algorithme incrémental et très efficace de reconnaissance de ces structures discrètes à partir duquel un algorithme de découpage de courbes discrètes en segments flous d'ordre fixé a été déduit.
Une collaboration avec Fabien Feschet (LLAIC, Clermont-Ferrand) a abouti à une optimisation de cette notion de segment flou et de l'algorithme de segmentation associé.
L'application de cet algorithme à l'analyse de documents a fait l'objet d'une collaboration avec l'équipe QGAR du LORIA.
Nous avons aussi développé un détecteur efficace de segments droits épais dans des images en niveau de gris, s'appuyant sur la reconnaissance de segments flous.
Récemment, nous avons étendu la définition de segments flous à la dimension 3 pour développer un algorithme similaire de reconnaissance de segments flous 3D.

Plans discrets -- Un plan discret naïf est défini comme le sous-ensemble de points (x,y,z) de Z³ vérifiant la double inégalité h <= ax + by + cz < h + max (|a|,|b|,|c|), avec (a,b,c,h) dans Z⁴. Etant donné un sous-ensemble fini de Z³, le problème est de déterminer s'il existe ou non un plan discret naïf le contenant. En collaboration avec Yan Gérard (LLAIC, Clermont-Ferrand) et Paul Zimmermann (équipe SPACES du LORIA), nous avons proposé un algorithme qui utilise une stratégie d'optimisation dans un ensemble de facettes triangulaires ainsi que la notion d'ensemble de cordes.
Nous nous intéressons maintenant à la reconnaissance de plans discrets bruités en combinant des techniques de géométrie algorithmique et de géométrie discrète. En effet, des algorithmes de construction d'enveloppes convexes ou des algorithmes géométriques de programmation linéaire apparaissent naturellement comme des solutions possibles à ce problème. Cependant, la spécificité des structures discrètes et les propriétés arithmétiques sous-jacentes impliquent des adaptions et des simplifications de ces algorithmes pour résoudre le problème de la reconnaissance de morceaux de plans bruités.

Extraction de paramètres géométriques

Nous travaillons sur deux approches pour extraire des paramètres géométriques tels que longueur, courbure, normale, tangente, aire, ...
- caractériser les données par des objets discrets représentés par des définitions analytiques, puis extraire les paramètres à partir de leurs propriétés géométriques,
- estimer la surface euclidienne s'appuyant au mieux sur les données discrètes, puis calculer les paramètres.

Longueur d'une courbe discrète 3D -- En collaboration avec David Coeurjolly (LIRIS, Lyon) et Olivier Teytaud (LRI, Paris XI), nous avons proposé un nouvel algorithme de calcul de la longueur de courbes discrètes 3D. La courbe 3D est découpée en segments de droites de longueurs maximales et la longueur de la courbe est calculée en fonction de la longueur de la ligne polygonale obtenue. La convergence de cette technique d'estimation de longueur a été prouvée.

Courbure discrète -- Dans le cadre de notre travail sur les courbes bruitées, nous avons proposé une nouvelle notion de tangente discrète, reposant sur la définition des segments flous et adaptée aux courbes discrètes bruitées. Un algorithme fournit les paramètres de la tangente en chaque point d'une courbe discrète. Il est alors possible d'extraire d'autres paramètres comme le vecteur normal ou la courbure en tout point de la courbe considérée. En collaboration avec F. Feschet (LLAIC, Clermont-Ferrand) et M. Tajine (LSIIT, Strasbourg), nous étudions les performances de cet estimateur de courbure discrète.
Nous avons adapté ces algorithmes au calcul de la courbure de l'ADN. Par ailleurs, une version 2D est utilisée pour une application de reconnaissance de cercles et d'arcs de cercles dans des documents techniques.

Lissage de surfaces discrètes -- Nous avons introduit une méthode réversible de lissage de surfaces discrètes. Cette méthode se base sur l'estimation statistique du plan discret pour pouvoir transformer la surface discrète en une surface euclidienne. La nouvelle représentation de la surface permet d'extraire directement les paramètres géométriques tels que l'aire, le volume ou les normales de la surface. Il est aussi possible d'obtenir des profils 2D de l'objet discret pour en extraire d'autres mesures associées telles que par exemple le périmètre des différentes coupes.

Reconstruction

A partir de données discrètes, nous utilisons des objets discrets et leurs propriétés pour reconstruire des objets du monde continu correspondant aux données initiales.

Décomposition polygonale de courbes discrètes en parties convexes et concaves} -- L'étude de la convexité d'une région discrète du plan se ramenant à celle de figures particulières appelées polyominos hv-convexes, nous avons développé un algorithme incrémental et linéaire de détection de la convexité de tels polyominos. Un travail avec Hélène Dörksen-Reiter (équipe du Professeur Eckhardt, Université d'Hambourg) a aboutit à un algorithme linéaire de décomposition polygonale du bord d'un objet discret en parties convexes et concaves reposant sur certaines propriétés que nous avons pu établir par le passé. Cette décomposition est très utile pour décrire un objet discret.
Nous poursuivons ce travail en étudiant les propriétés des algorithmes de décomposition polygonale du bord d'objets discrets.

Polyédrisation -- A partir des algorithmes de reconnaissance de plans bruités que nous avons développés, nous étudions la polyédrisation d'objets discrets bruités tridimensionnels en contrôlant l'approximation effectuée. Notre objectif est d'obtenir des algorithmes performants en combinant les approches de géométrie discrète et de géométrie algorithmique. Cette représentation paramétrique pourra être utilisée pour extraire rapidement des propriétés géométriques des surfaces discrètes ou encore pour lisser sous contrôle la surface des objets discrets bruités et ensuite la transformer en surface euclidienne permettant ainsi l'utilisation de calculs rapides de la géométrie euclidienne sur celle-ci (transformations géométriques, tests de visibilité, d'intersection, ...).

Reconstruction de surfaces à partir d'images -- Dans ses travaux de thèse menés au LaBRI (Bordeaux), Bertrand Kerautret a proposé une méthode discrète de reconstruction de surfaces de type lambertien. Elle s'appuie sur l'estimation discrète de la normale sur le bord d'une région de la surface. La reconstruction s'effectue à partir de contraintes géométriques et de l'information photométrique contenues dans une ou plusieurs images. L'approche adoptée permet d'exprimer des contraintes explicites pour lever l'ambiguïté concave/convexe liée à l'utilisation d'une seule source lumineuse frontale.
Cette méthode a montré une grande robustesse par rapport au bruit des images et par rapport au modèle de réflectance pouvant prendre en compte une composante spéculaire. Nous travaillons actuellement sur l'intégration d'une source lumineuse ponctuelle non distante dans le modèle. Cette extension vise une meilleure reconstruction, en particulier dans le cas d'objets de grande taille pour lesquels il est expérimentalement très difficile de satisfaire l'hypothèse d'une source lumineuse directionnelle sans matériel spécifique. En effet les méthodes développées jusqu'à maintenant montrent une grande complexité de calcul. Par ailleurs la résolution des images utilisées pour la reconstruction reste très faible, de l'ordre de 64x64 pixels.

Génération de structures discrètes à partir de contraintes

Jusqu'à présent, nous nous sommes principalement intéressés à une définition analytique des objets discrets par des équations ou inéquations sur les coordonnées des points qui composent l'objet. Si une telle définition fournit un moyen rapide de tester l'appartenance d'un point à l'objet discret considéré, en revanche elle ne permet en général pas directement d'engendrer efficacement les points de l'objet. Notre objectif est de développer des techniques de génération d'objets discrets à partir de leurs propriétés.

Extension du formalisme -- En plus de ne pas fournir de méthode de génération des objets, le formalisme utilisé s'avère parfois insuffisant pour exprimer certaines propriétés. On ne peut par exemple pas définir les pentominos avec une équation analytique ou encore définir la connexité d'un objet. Nous proposons une autre démarche permettant de considérer des problèmes où les objets ne s'adaptent pas au formalisme proposé précédemment : une information plus globale est donnée sur l'objet avec pour objectif de reconstruire géométriquement un ou plusieurs objets solutions. Cette démarche ne remplace pas la précédente mais l'enrichit de manière à pouvoir considérer un éventail plus large de propriétés des objets dont nous traitons.
En particulier, nous nous intéressons au formalisme qui consiste à définir un objet par sa fonction caractéristique, c'est à dire une fonction qui en chaque point vaut 1 ou 0 selon que le point appartient ou n'appartient pas à l'objet. Ce type de définition permet d'exprimer d'autres propriétés d'un objet à travers des propriétés de sa fonction caractéristique. Par exemple, pour un pentomino, la somme de la fonction caractéristique vaut cinq. Ces propriétés peuvent être plus complexes et s'exprimer sur des transformées de la fonction caractéristique telles que la transformée de Fourier.

Génération d'objets discrets -- En termes de problématiques, nous nous sommes jusqu'à présent intéressés à la recherche d'une définition en compréhension adaptée à la manipulation des objets discrets ou au raisonnement sur ceux-ci. A l'inverse, dans certaines situations, on dispose d'une telle définition ou plus généralement de certaines propriétés de l'objet, et on s'intéresse à sa génération pour le visualiser ou travailler sur sa représentation géométrique. Dans ce cas, on souhaite obtenir des algorithmes efficaces en particulier dans des domaines critiques comme la visualisation en temps réel où encore dans les cas où un grand nombre de solutions doivent être engendrées.
Bien que l'objectif soit toujours d'aboutir à des algorithmes efficaces, les techniques de résolution peuvent être très variées. Ainsi, dans le cas de la droite discrète définie par une double inégalité sur les coordonnées, des adaptations de l'algorithme de Bresenham fournissent des méthodes très performantes permettant une génération directe des points de la droite. A l'inverse, dans le cadre d'une application de cristallographie moléculaire, nous avons identifié un objet discret par la solution d'un problème de minimisation de la valeur d'une fonction, dite fonction objectif, mettant en œuvre la transformée de Fourier de la fonction caractéristique. On fait alors appel à des techniques d'optimisation par recherche locale afin de converger progressivement vers l'objet recherché. A mi-chemin de ces extrêmes, on trouve par exemple des structures telles que les courbes algébriques discrètes décrites par des équations algébriques pour lesquelles une solution ne peut pas toujours être obtenue facilement ou encore des polyèdres définis par un ensemble d'inégalités. Dans ce dernier cas, la génération passe par une recherche des points extrêmes par des techniques d'optimisation comme la méthode du simplexe, suivie d'une génération de morceaux de plans discrets pour les facettes.
Nous envisageons de développer des techniques hybrides de génération d'objets discrets en combinant selon la nature et la complexité des problèmes posés des techniques issues de l'arithmétique, de l'algèbre et de l'optimisation discrète.