Métriques convergentes pour le calcul digital – CoMeDiC

L’idée générale est de définir des métriques adaptées pour le calcul discret qui le font converger vers les valeurs continues attendues. Cette approche est maintenant envisageable grâce aux avancées récentes en géométrie digitale sur la mise au point d’estimateurs géométriques locaux convergents. Ce nouveau calcul «digital« permet d’attaquer des problèmes variationnels impliquant des domaines discrétisés comme des surfaces, courbes, ou graphes, vivant dans un espace ambiant de dimension supérieure, de même que des problèmes avec discontinuités, de bord libre, ou avec des conditions aux bords subtiles.
Ce projet s’attaque à la fois aux problèmes théoriques liés à la mise au point d’un calcul digital, du choix des bons estimateurs pour les métriques, de l’établissement de ses propriétés de convergence, ainsi qu’à sa résolution numérique efficace. Le projet étudie aussi tout particulièrement les problèmes variationnels difficiles pour les méthodes numériques standards, comme les problèmes à discontinuitées ou à frontières libres, les problèmes impliquant des domaines de codimension supérieure ou à égale à un comme les surfaces ou les courbes. Enfin, le projet CoMeDiC vise trois domaines d’applications naturels du calcul digital — l’analyse d’image, le traitement de données géométriques, et l’optimisation de formes — à la fois pour guider et nourrir les développements théoriques et pour servir de banc d’essai pour le calcul digital.

L'équipe rassemble des mathématiciens et des informaticiens, avec des expertises en problèmes variationnels, calcul discret, géométrie discrète, optimisation de formes, théorie géométrique de la mesure, analyse d'image et geometry processing.

1 Digital Calculus : convergence, variational models, computation issues

1.1 Metric definitions and convergence of digital operators

- Opérateur de Laplace-Beltrami convergent sur des surfaces digitales [CCLR16, CCLR17]
- Calcul du vecteur normal d'un plan discret par marche locale [LPR17]
- Discrétisation de Gauss et intégration sur des surfaces digitales [LT16]
- Estimateurs de normales et courbures convergents par invariants intégraux [LCL17]

1.2 Adaptation of variational problems to digital calculus

- Discrétisation de la fonctionnelle d'Ambrosio-Tortorelli par calcul discret [FLT16a, CFGL16]
- Identification de formes optimales pour des problèmes spectraux en dimension 4 [AO17]
- Partitions optimales pour la longueur des variétés par méthode champ de phase [BO16]
- Optimisation d'objets géométriques sous forme variationnelle, régularité et géométrie [DPMSV16,MTV17,MPLPV] et incertitude [BV].

1.3 Performance issues in digital calculus

- package Discrete Exterior Calculus dans la bibliothèque DGtal (dgtal.org)
- outil de restauration d'image basé calcul discret labellisé recherche reproductible [FLT16b]

2 Applications of digital calculus to various variational problems

2.1 Digital calculus for image analysis

- Régularisation lisse par morceaux pour restauration d'image par fonctionnelle AT [FLT16\
a]
- Filtres morphologiques et géodésiques préservant les contours [DCDSN17]

2.2 Digital calculus for geometry processing

- Biclustering pour appariement de formes non isométriques [GSTOG16]
- Régularisation anistrope de champ de normales sur surface discrète par fonctionnelle AT\
[CFGL16]
- Carte de confiance discrète pour reconstruction d'objets tubulaires [KKDR16a,KKDR16b]

2.3 Digital calculus for shape optimisation

- Discrétisation du problème euclidien de l'arbre de Steiner [BOO16]
- Calibration numérique d'arbre de Steiner optimaux[MOV17]
- Construction de réflecteurs sous contraintes par transport optimal [dCMT16]

Faits marquants:

La plateforme de géométrie discrète DGtal (http://dgtal.org) a reçu le « software award » à la conférence Symposium on Geometry Processing 2016 (20-24 juin à Berlin). Ce prix récompense un logiciel ou une bibliothèque open-source de haute qualité autour de la thématique du traitement géométrique de formes. Issue d’une collaboration entre le LIRIS et le LAMA (Université de Savoie Mont-Blanc), le projet collaboratif DGtal autour de la géométrie discrète est devenue incontournable dans la communauté internationale avec des contributions des principaux laboratoires sur ce thème.

Perspectives:

Nous travaillons à la fois sur les aspects fondamentaux du calcul discret et sur ses champs d'application possibles. Par exemple, nous étudions différentes formes de convergence, certaines basées sur les courants normaux et donc sur la convergence des formes, d'autres basées sur la convergence d'opérateurs ou de problèmes variationnels spécifiques. Les questions numériques sont aussi étudiées, par exemple par des approches multi-échelles.

Sur les applications, nous étudions comment utiliser le calcul discret pour régulariser les objets discrets et avoir des reconstructions linéaires par morceaux proches en positions et en normales des objets continus sous-jacents. De même, nous étudions comment injecter les longueurs et les courbures dans les problèmes variationnels en imagerie 2D et 3D, en essayant de limiter l'explosion combinatoire des approches existantes. Enfin, nous regardons comment discrétiser des problèmes classiques d'optimisation de formes de l'espace Euclidien, notamment la conjecture du nid d'abeille en 3D.

Sur la période T0-T18 (10/2015 - 4/2017):
- 3 articles pluri-partenaires dans des journaux internationaux
- 10 articles mono-partenaires dans des journaux internationaux
- 1 chapitre d'ouvrage pluri-partenaire
- 3 communications pluri-partenaires à des conférences internationales
- 5 communications mono-partenaires à des conférences internationales
- 2 articles déposés sur HAL

Le calcul extérieur discret s'est imposé dans les dix dernières années comme un outil puissant pour résoudre des problèmes variationnels en traitement et analyse d'image et de données géométriques. Il simplifie à la fois la formulation des problèmes et leur résolution numérique, et rend souvent possible l'extraction d'optimum globaux. Cependant, le calcul discret souffre d'un défaut important. Rien ne garantit que ce calcul discret converge vers le résultat attendu du calcul vectoriel standard lorsque l'on affine le domaine discret, notamment sur des données numériques comme des images 2D ou 3D, des surfaces ou courbes digitales.

Le projet CoMeDiC vise à combler cet écart entre calcul discret et calcul vectoriel pour les ensembles de l'espace digital Z^n. L'idée générale est de définir des métriques adaptées pour le calcul discret qui le font converger vers les valeurs continues attendues. Cette approche est maintenant envisageable grâce aux avancées récentes en géométrie numérique --- digital geometry en anglais --- sur la mise au point d'estimateurs géométriques locaux convergents. Ce nouveau calcul, appelé calcul digital, permet d'attaquer des problèmes variationnels impliquant des domaines discrétisés comme des surfaces, courbes, ou graphes, vivant dans un espace ambient de dimension supérieure, de même que des problèmes avec discontinuités, de bord libre, ou avec des conditions aux bords subtiles.

Ce projet s'attaque à la fois aux problèmes théoriques liés à la mise au point d'un calcul digital, du choix des bons estimateurs pour les métriques, de l'établissement de ses propriétés de convergence, ainsi qu'à sa résolution numérique efficace. Le projet étudie aussi tout particulièrement les problèmes variationnels difficiles pour les méthodes numériques standards, comme les problèmes à discontinuitées ou à frontières libres, les problèmes impliquant des domaines de codimension supérieure ou à égale à un comme les surfaces ou les courbes. Enfin, ce projet vise trois domaines naturels d'applications du calcul digital --- l'analyse d'image, le traitement de données géométriques numériques, et l'optimisation de formes --- à la fois pour guider et nourrir les développements théoriques et pour servir de banc d'essai pour le calcul digital.