Orientation cristalline par transport optimal§
Expérimentations
authors: | David Coeurjolly et Isabelle Sivignon |
---|
Expérimentations
authors: | David Coeurjolly et Isabelle Sivignon |
---|
Retrouver l'orientation cristalline des grains dans les images tomographiques
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)
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
Application de Gauss
Gauss -> Mesures de probabilité
Application de Gauss d'un objet \(X\) \(\implies\) mesure à densité \(\mu\) sur \(S^2\) (source)
\[\mu(B) = \int_B \rho(x)dx\]
Prisme \(\implies\) mesure discrète \(\nu\) sur \(S^2\) avec 8 Diracs (target)
\[\nu = \sum_{p\in S} \lambda_p\delta_p\]
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)
\(\pi: \mathbb{R}^d\leftarrow \mathbb{R}^d\) (ici de \(S^2\) sur l'ensemble des Diracs)
\(\pi_\mu(B)\) ~ \(\mu(\pi^{-1}(B))\) est le pushforward de \(\mu\) par \(\pi\)
\(\pi\) est un plan de transport si le pushforward de \(\mu\) par \(\pi\) est \(\nu\)
Le coût d'un plan de transport d'ordre \(r\) est
\[c(\pi) = \int_{\mathbb{R}^d} \|x - \pi(x) \|^r d\mu(x) = \int_{\mathbb{R}^d} \|x - \pi(x) \|^r \rho(x)dx\]
Transport optimal = plan de transport valide de coût minimal
\(Wasserstein_r(\mu,\nu)\) distance définie comme étant la puissance \(1/r\) du coût du transport optimal entre \(\mu\) et \(\nu\)
Données
\(\mu = \sum_{1}^N \lambda_i \delta_{x_i}\), \(\nu = \sum_{1}^N \lambda'_i \delta_{y_i}\)
avec \(X=\{x_i\},Y=\{y_i\}\subset\mathbb{R}^d\) et \(\{\lambda_i\},\{\lambda'_i\}\in\mathbb{R}^+\) et \(\sum \lambda_i = \sum \lambda'_i = 1\)
Soit \(c(x_i,y_i): \mathbb{R}^{2d}\rightarrow \mathbb{R}^+\) une fonction de coût (distance \(l_r\) par ex)
\(\pi: X\times Y\rightarrow \mathbb{R^+}\) est un plan de transport discret
Le transport \(\pi\) est valide ssi
\[\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\]
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) ...
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...
...mais...
Dans notre cas, on cherche en fait le transport optimal de \(\mu\) vers \(R\nu\) pour toutes les rotations \(R\) de la mesure cible
\[c(\pi,R) = \int_{\mathbb{R}^d} \|x - R(\pi(x)) \|^r \rho(x)dx\]
C'est plus convexe !
(qq travaux ad-hocs sur le cerlce)
...et pire...
Comme la cible est très petite (8 diracs), on va pour l'instant faire un calcul complet
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\)
Transport Optimal 2 options
\(\implies\) approche lagrangienne
Bah pourquoi ?
Principe
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
\(\implies\) "local derivative-free optimization" : Bound Optimization by Quadratic Approximation
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
Sur un prisme digital bruité sans occlusion
Sur un prisme digital bruité avec occlusion
Pour des élongations différentes
Reste à faire
Expérimental
Théorie