Projet CoMeDiC

Titres possibles

• Convergent metrics for digital calculus
• Métriques convergentes pour le calcul discret

Idées générales

• structures discrètes (Z^n) + calcul discret + estimateurs géométriques convergents
• métriques adaptés au calcul discret sur des parties de Z^n
• projet centré fondements, avec des applications potentielles (analyse d'image, geometry processing, optimisation de formes)

Partenaires

• LAMA (J.-O. Lachaud, D. Bucur, M. Foare, ...)
• LIRIS (D. Coeurjolly, T. Roussillon, N. Bonneel, ...)
• LIGM (H. Talbot, P. Romon, L. Najman, ...)
• LJK (E. Oudet, B. Thibert ?, ...)
• Chercheurs associés
  • P. Gueth
  • C. Mercat (?)
  • M. Desbrun (?)

Objets géométriques considérés

• objets digitaux dans Z^d
• surfaces digitales dans Z^d
• objets tubulaires, complexes cellulaires
• structures d-2 dans objets d-1
• bruits / perturbations
• multirésolution (top->down)
• cellules adaptatives: quadtree/octree, grilles isothétiques

Contexte

Plusieurs calculs discrets

• Desbrun, Seok, etc: la géométrie de la maille modifie les opérateurs
• Grady, Polimini: opérateurs et métriques sont séparés, et remis ensemble lors de leur composition
• Polthier: ?
• Mercat: une bonne normale définit un digital Hodge star.

Points communs et différences du Calcul Discret (CD) avec le Calcul Scientifique (CS) usuel

• le CD cherche à rendre exact le calcul intégral (théorème de Stokes exact). Le CD n'a pas nécessairement besoin d'une géométrie (plongement) pour être consistant. La notion de différentielle est plus topologique.
• le CD peut être paramétré par une géométrie/métrique.
• le CS, avec les schémas numériques usuels (différences finies, éléments finis) cherche à approcher numériquement les intégrales, les dérivées, définis sur des domaines géométriques. Il n'y a pas en général de satisfaction exacte du théorème de Stokes (généralisation du théorème fondamental du calcul différentiel et intégral).
• le CS doit souvent faire attention à bien choisir le schéma numérique pour que le calcul numérique corresponde au calcul continu.
• Liens forts entre calcul différentiel discret et éléments finis (méthode de Galerkin, piecewise linear basis)
  • on retrouve le même opérateur Laplacien (formule des cotangentes)
  • introduction de cellules de toutes dimensions (bases choisies introduisent ces cellules)
• Limites du DEC et schémas classiques dans le cadre de la géométrie digitale (formulations spatiales, mais aussi lorsque le domaine de calcul nécessite une surface ou une courbe (de dimension inférieure au domaine)
  • problème central : quand est-ce que les opérateurs discrets approchent (convergent) vers leur sens usuel au sens du calcul différentiel ?
  • réponse "Grady" c'est de ne pas chercher à se rapprocher d'un modèle continu : très raisonnable quand on travaille sur un problème type graphe sans plongement géométrique pertinent
  • réponse "DEC caltech" double : 1) métrique induite par la géométrie d'une surface triangulée, 2) "convergence" dans certains cas mais avec une surface triangulée qui est une bonne approximation d'une surface idéale sous-jacente.
  • ces techniques, appliquées directement aux courbes et surfaces discrètes (ou à des problèmes de domaine mais avec bord ou discontinuités), ne peuvent converger vers le même problème continu (variationnel ou edp).

Estimateurs discrets

• Il s'agit donc de définir des métriques adaptées aux objets géométriques considérés
• estimateurs discrets convergents (MST, II, VCM, normales sans paramètres, courbures)
• intéressants pour fournir des métriques sur des objets digitaux de dimension inférieure

Convergence des CD

• approche calcul extérieur discret sur les mailles triangulées. Formules particulières sur le Hodge star et sur musical operators. Semble ~ok si la maille tend vers la surface idéale (preuves ?). Approche Polthier avec la formule des cotangentes.
• approche Boykov sur graphe: ajout d'arêtes pondérées reliant des points plus distants. Formule de Cauchy-Crofton montrant que le périmètre peut être approché (sans vitesse de convergence).
• approche Mercat sur surface discrète: un bon champ de normales donne un bon résultat (vitesse de convergence ?)

• (où le classer ?) approche Gamma-convergence et méthode phase-field: la métrique paramétrée par epsilon induit une convergence du périmètre entre deux phases.

Objectifs

Equations

• Transport optimal: diffusion, transport de mesure
• Applications conformes: minimisation de la distorsion angulaire
• reconstruction avec discontinuité (Mumford-Shah, Ambrioso Tortorelli)

Convergence

• quelles métriques discrètes pour quelles équations et quelles données discrètes
• Montrer énergies discrètes tendent vers énergies continues
• Comment montrer que les solutions sont proches ?
• quelles métriques sur les algos de partitions (graph cut, opt combinatoire)
• la convergence est-elle le bon critère pour le CD ? On pourrait regarder d'autres propriétés comme la "convexité" (comme le MLP).

Applications

• analyse d'image: clustering, segmentation, restauration, reconstruction lisse par morceaux
• reconstruction de graphes (diffusion électrique, propriétés graphes)
• reconstruction de surfaces (avec discontinuités)
• géodésiques, texture mapping, feature mapping
• optimisation de formes (surfaces minimales, Willmore, Minkowski, conditions de Robin, problème de Steiner).

Calcul discret

• structures de données
• définition des métriques (évolutives ou non)
• problèmes linéaires / algèbre linéaire
• optimisation combinatoire
• descente en gradient et Gamma-convergence

Scale-space

• estimateurs géométriques paramétrés (lambda) => calcul discret paramétré (lambda)
• propriétés du calcul discret paramétré
• comparer longue diffusion en temps avec Laplacien bête versus courte diffusion avec Laplacien induit par un estimateur géométrique discret.

Autres retombées

• meilleur compréhension des possibilités et des limitations du calcul discret (contraintes sur les domaines, contraintes sur les opérateurs et les quantités géométriques manipulées (longueur, courbures, etc).

Références

• http://math.univ-lyon1.fr/homes-www/mercat/articles/MeshParamGenDiscConfMaps.pdf
• http://en.wikipedia.org/wiki/Cahn%E2%80%93Hilliard_equation
• http://page.mi.fu-berlin.de/polthier/articles/diri/diri_jem.pdf

Projet ANR

Programmation ANR

• ouverture site de soumission: 10 septembre 2014
• soumission des prépropositions: *16 octobre 2014*, 13h
• résultats 1ère phase : mi-janvier 2015
• ouverture soumission 2e phase: début février 2015
• deadline soumission 2e phase: fin mars 2015
• résultats 2ème phase : début juillet 2015

Type de projet ANR

• projet PRC (Projet de Recherche Collaborative)
• classements possibles:
  1. Défi 10 Défi de tous les savoirs (DEFSAV)
  2. Défi 7 Société de l'Information et de la Communication
     1. Axe 4 : Fondements du numérique
     2. Axe 7 : Interactions humain-machine, objets connectés, contenus numériques, données massives et connaissance

Questions et remarques diverses

• Liens et différences avec d'autres projets ANR
• Impact éventuel du projet pour l'enseignement supérieur (nouveaux cours sur digital calculus)
• taux de précarité doit être inférieur à 30%