Orientation cristalline par transport optimal§

Expérimentations

authors:David Coeurjolly et Isabelle Sivignon

Préliminaires...§

Problématique§

Retrouver l'orientation cristalline des grains dans les images tomographiques

_images/snow_original.png _images/snow_segmentation.png _images/orientation.png

Processus idéal

Image tomgraphique \(\rightarrow\) segmentation en grains par des critères géométriques \(\rightarrow\) pour chaque grain, orientation cristalline

Pourquoi ?

Paramètres anisotropiques importants dans la modélisation des "croissances de facettes" (Clausius-Clapeyron)

Problématique (bis)§

Approche

Bad news

\(\implies\) problèmes de matching géométrique:

Étant donnée un grain, trouver la transformation affine minimisant une certaine distance entre le grain et un prisme hexagonal idéal

Approche : Application de Gauss et Transport Optimal§

Application de Gauss

http://upload.wikimedia.org/wikipedia/commons/thumb/8/8e/Gauss_map.svg/1000px-Gauss_map.svg.png

Gauss -> Mesures de probabilité

Transport Optimal§

Problème

Distance lors du matching géométrique \(\Leftrightarrow\) distance entre distributions sur \(S^2\)

\(\implies\) transport optimal et distance de Wasserstein

Plan de transport de mesure (Monge/Kantorovich)

Transport Optimal discret§

Données

Problème discret

\[min_{\pi} \sum_{x_i\in X} \sum_{y_j\in Y} c(x_i,x_j)\pi(x_i,y_j)\]

\(\implies\) Problème d'assignation, min cost flow dans un graphe bi-partie, ....

\(\implies\) Bcp cas particuliers, par ex \(d=1\) (distance entre histogrammes), \(c=l_p\), intégration sur histogrammes cumulés (Earth Mover Distance) ...

Continu, cas particulier pour \(Wass_2\)§

Outils clé: Diagramme de Puissance et relaxation

\(\pi_{(S,\omega,\mu)}\) est un plan de transport optimal de \(\mu\) sur son pushforward par \(\pi_{(S,\omega,\mu)}\)

Par def,

\[Wass_2(\mu,\pi_{(S,\omega,\mu)}) = \left( \sum_{p\in S} \int_{Vor^\omega_S(p)} \| x-p\|^2\rho(x)dx\right)^{\frac{1}{2}}\]

Pour \(\nu\) mesure discrète quelconque, le transport optimal s'obtient itérativement

\(\implies\) formulation énergétique convexe, approche hiérarchique...

Bilan§

...mais...

...et pire...

Comme la cible est très petite (8 diracs), on va pour l'instant faire un calcul complet

En pratique...§

Etape 1 : calcul des mesures (1/2)§

Il nous faut : des positions \(X=\{x_i\},Y=\{y_i\}\subset\mathbb{R}^d\) et des poids associés \(\{\lambda_i\},\{\lambda'_i\}\in\mathbb{R}^+\) et \(\sum \lambda_i = \sum \lambda'_i = 1\)

Mesure à densité source

Estimation des normales

Positions : on construit une distribution empirique par accumulateur sphérique

Poids uniformes : \(\lambda_i = \frac{N_i}{N} \ \forall i\) avec \(N =\) nombre de surfels et \(N_i =\) nombre de points dans la cellule \(i\) de l'accumulateur

Mesure cible

Positions : on construit les diracs du prisme pour une certaine rotation \((\rho,\theta,\phi)\)

Poids uniformes : \(\lambda'_i = \tfrac{1}{8} \ \forall i\)

Etape 1 :calcul des mesures (2/2)§

_images/GaussMap-DigitalPrism-noAcc.png _images/GaussMap-DigitalPrism.png

Etape 2 : calcul de la distance de Wassertein (1/3)§

Transport Optimal 2 options

\(\implies\) approche lagrangienne

Bah pourquoi ?

Etape 2 : calcul de la distance de Wassertein (2/3)§

Principe

_images/bonneel.png

Etape 2 : calcul de la distance de Wassertein (3/3)§

Rappel du problème discret

\[min_{\pi} \sum_{x_i\in X} \sum_{y_j\in Y} c(x_i,x_j)\pi(x_i,y_j)\]

sous contraintes

\[\begin{split}\forall x_i\in X,\, \sum_{y_j\in Y} \pi(x_i,y_j) = \lambda_i,\\ \forall y_i\in Y,\, \sum_{x_j\in X} \pi(x_j,y_i) = \lambda'_i\end{split}\]

Trois versions de l'algo de minimisation

Etape 3 : Optimisation dans l'espace des rotations§

\(\implies\) "local derivative-free optimization" : Bound Optimization by Quadratic Approximation

Paramètres de tests§

Occlusion suppression d'une partie de la sphère de Gauss

Bruit génération de prismes discrets bruités

Nbre de 'bins' de l'accumulateur sphérique

Espace de recherche pour les angles \(\rho\) = phase, \(\phi, \theta\) = latitude, longitude de l'axe du prisme

Algorithme utilisé pour le calcul de la distance de Wassertein

Visualisation de l'espace de recherche§

_images/EspaceRechercheGlobal1.png _images/EspaceRechercheGlobal2.png
_images/EspaceRechercheGlobalLatCst.png _images/EspaceRechercheGlobalAngleCst.png

Résultats d'alignement§

Sur un prisme digital bruité sans occlusion

_images/resPrism.png
bruit = 0.2, algo contraint
_images/resPrism2.png
bruit = 0.4, algo contraint

Sur un prisme digital bruité avec occlusion

_images/resPrism3.png
bruit = 0.4, facette basale, algo contraint
_images/resPrism4.png
bruit = 0.4, facette latérale, algo contraint

Résultats d'alignement§

Pour des élongations différentes

_images/resPrism5.png
bruit = 0.4, algo contraint
_images/resPrism6.png
bruit = 0.4, algo non contraint

Analyse de l'erreur comise§

Analyse de l'erreur comise§

_images/resOptimPasBruitPasOcc.png
bruit = 0, pas d'occlusion

Analyse de l'erreur comise§

_images/resOptimBruitPasOcc.png
bruit = 0.2, pas d'occlusion

Analyse de l'erreur comise§

_images/resOptimBruitOcc.png
bruit = 0.2, occlusion d'une face latérale

Résultat sur la bulle d'air§

_images/bulle1.png

Conclusion§

Reste à faire

Expérimental

Théorie