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, ...)
• LIRIS (D. Coeurjolly, ...)
• LIGM (H. Talbot, ...)
• LJK (E. Oudet ?, ...)
• Chercheurs associés
  • 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.
• rapprochements récents avec les FEM (introduction de cellules de toutes dimensions)

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.

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