next up previous contents
suivant: Estimateur de qualité des monter: Modélisation et résolution du précédent: Régularisation   Table des matières

Approche multi-grille et optimisation

La minimisation de $ J$ est réalisée sur une suite de sous-espaces emboités:

$\displaystyle \mathcal{C}_{16}\subset\mathcal{C}_{8}\subset\mathcal{C}_{4}\subset\mathcal{C}_2\subset\mathcal{C}_1,$ (4.11)

où $ \mathcal{C}_q$ est l'ensemble des champs de déplacement admissibles à l'échelle $ q$ , c'est-à-dire affines par morceaux par rapport à chaque variable d'espace sur des carrés de $ q\times q$ pixels.

La différence principale avec les approches relevant du flot optique (voir par exemple [85,93]) est que nous considérons la minimisation de la fonctionnelle non linéaire $ J$ , ce qui permet notamment d'identifier des champs de déplacement arbitrairement grands, contrairement aux approches où la fonction coût est linéarisée.

Une fois la minimisation réalisée, par exemple sur l'espace $ \mathcal{C}_{16}$ (ce qui rend l'optimisation particulièrement rapide, compte tenu de la réduction de la dimension du problème), le champ optimal est utilisé comme point de départ pour la minimisation sur l'espace $ \mathcal{C}_8$ , et ainsi de suite jusqu'à obtenir un minimum sur l'espace complet $ \mathcal{C}_1$ , et donc une solution totalement raffinée.

Les différentes optimisations sont faites avec un algorithme de Gauss-Newton. Ainsi, en initialisant la minimisation avec un champ $ (u^0,v^0)$ donné (en pratique, un champ nul), cela revient à chercher une mise à jour sous la forme

$\displaystyle (u^{k},v^{k}):=(u^{k-1},v^{k-1})+(du^{k},dv^{k}),$ (4.12)

où $ (du^k,dv^k)$ est solution de

$\displaystyle (DF^TDF+\alpha S^TS)(du,dv)=-DF^TF-\alpha S^TS(u,v),$ (4.13)

où $ F=F(I_0,I_1;u^{k-1},v^{k-1})$ est l'erreur, $ DF=DF(I_0,I_1;u^{k-1},v^{k-1})$ est la matrice jacobienne de l'erreur, et $ S$ est l'opérateur linéaire de régularisation.

Une autre nouveauté de notre approche réside dans l'assemblage de la matrice $ DF^T DF$ , nécessaire à la résolution de l'équation (4.13).

Soit $ V$ un champ de vecteurs de $ \mathcal{C}_q$ , i.e. défini sur la grille constituée de carrés de $ q\times q$ pixels. Soit $ ({\bf e}_i)$ la base canonique orthonormée de $ \mathcal{C}_q$ , qui contient donc des vecteurs nuls sauf sur une maille où le champ contient des vecteurs unitaires parallèles à l'un des deux axes de $ \mathbb{R}^2$ . Le c\oefficient $ (k,l)$ de la matrice $ DF^T DF$ est alors égal à

$\displaystyle (DF^TDF)_{k,l} = (DF^TDF {\bf e}_k\vert{\bf e}_l) = (DF {\bf e}_k\vert DF {\bf e}_l)_{L^2(\Omega)}.$ (4.14)

Comme les déplacements élémentaires $ {\bf e}_k$ sont nuls sauf sur une maille, la matrice $ DF^T DF$ est donc creuse. En utilisant la formulation suivante de la jacobienne:

$\displaystyle DF(u,v).d(x,y) = \nabla I_1(x+u(x,y),y+v(x,y)).d(x,y),$ (4.15)

la matrice $ DF^T DF$ peut être assemblée de la façon suivante:
$\displaystyle DF^TDF$ $\displaystyle =$ $\displaystyle \sum_{k,l}(DF^TDF)_{k,l} {\bf e}_k\otimes {\bf e}_l$  
  $\displaystyle =$ $\displaystyle \sum_{k,l}\int_\Omega(\nabla I_1(x') \vert {\bf e}_k(x)) (\nabla I_1(x') \vert {\bf e}_l(x)) {\bf e}_k\otimes {\bf e}_l dx$  
  $\displaystyle =$ $\displaystyle \sum_{k,l}\sum_{R\in\mathcal{R}_q}\int_R(\nabla I_1(x') \vert {... ...e}_k(x)) (\nabla I_1(x') \vert {\bf e}_l(x)) {\bf e}_k\otimes {\bf e}_l dx$  
  $\displaystyle =$ $\displaystyle \sum_{R\in\mathcal{R}_q}\sum_{k,l}\int_R(\nabla I_1(x') \vert {... ...}_k(x)) (\nabla I_1(x') \vert {\bf e}_l(x)) {\bf e}_k\otimes {\bf e}_l dx,$ (4.16)

avec la notation $ x'=x+V(x)$ , et en notant $ \mathcal{R}_q$ l'ensemble des carrés $ q\times q$ de la grille. Le nombre de produits scalaires de la forme $ (\nabla I_1(x+V(x))\vert{\bf e}_k(x))$ à calculer est de $ 8$ pour chaque élément de $ \mathcal{R}_q$ . Il suffit donc de lire une seule fois les données contenues dans l'image $ I_1$ pour remplir la matrice $ DF^T DF$ . De même, les termes $ DF^T F$ et $ S^T S$ sont assemblés rapidement avec une technique similaire.

Finalement, l'équation (4.13) est résolue avec une méthode de gradient conjugué sans préconditionnement.

next up previous contents
suivant: Estimateur de qualité des monter: Modélisation et résolution du précédent: Régularisation   Table des matières
Retour à la page principale