Modèles de Structures Aléatoires de Type Réaction-Diffusion - Thèse de Morphologie Mathématique - Luc Decker, Ecole des Mines de Paris (1999)

1.4 Modèle de diffusion par différences finies

Il s'agit d'intégrer l'équation de la diffusion en tout point d'un domaine en deux ou trois dimensions. Ce domaine est discrétisé sous la forme d'un réseau régulier de sites en trame carrée ou cubique, donc avec des relations de voisinage en connexité 4 ou 8 en 2D, 6 ou 26 en 3D. A tout site, on associe une concentration locale C(x,y,z,t), représentée sous la forme d'un nombre flottant. L'équation de la diffusion est ré-écrite sous la forme d'une différence finie. Nous commencerons par en rappeler les principes à une dimension :

$\displaystyle C(x,t+1)\ -\ C(x,t) \ = \ D_{x}\ ( \frac{1}{2}\ (C(x+1,t)\ +\ C(x-1,t))\ - \ C(x,t))$ (II.-4)

L'expression du membre de droite correspond à la discrétisation de l'opérateur Laplacien. On exprime alors directement $ C(x,t+1)$ en fonction de $ C(x,t)$:

$\displaystyle C(x,t+1)\ = (1 - D_{x})\ C(x,t)\ +\ \frac{D_{x}}{2}\ (C(x+1,t)\ +\ C(x-1,t))$ (II.-5)

En un procédé itératif, on définit ainsi l'évolution élémentaire et simultanée en tout site du domaine. Dans l'évolution de la concentration au point $ x$, on distingue un premier terme qui correspond à sa diminution par la perte d'une partie de la matière ( $ D_{x} \ C(x,t)$) qui se trouvait en $ x$, alors qu'un deuxième terme représente les apports de matière en provenance du voisinage du point $ x$. Un équilibre tend à s'instaurer de sorte que $ C(x,t+1) = C(x,t)$ lorsqu'il y a égalité des concentrations $ C(x,t) = C(x-1,t) = C(x+1,t)$. La validité de cet opérateur de diffusion a été vérifiée par l'étude de profils gaussiens résultants de l'amortissement (et de la dispersion) progressif d'une impulsion locale. Par ailleurs, il s'agit d'un opérateur linéaire, que l'on peut implanter sous la forme d'une convolution spatiale par un masque centré en $ x$ et couvrant le voisinage de $ x$ ($ x+1$, $ x-1$ à une dimension).

Pour des raison de stabilité numérique du modèle, il est impératif que $ 1 - D_{x} \geq 0$ : la dimution de la concentration au point $ x$ ne doit pas dépasser sa valeur initiale. Dans le cas contraire, des oscillations (ou erreurs) numériques se trouvent amplifiées. En conséquence, les coefficients de diffusion applicables varient entre 0 et $ 1$. Il s'agit de coefficients relatifs, propres au modèle; il peuvent être exprimés en $ {pixels}^2 {[T]}^{-1}$ ou $ {voxels}^2 {[T]}^{-1}$.

Par ailleurs, un phénomène de parité peut apparaître lorsque $ D = 1$; dans ce cas, $ C(x,t+1)$ dépend uniquement des concentrations voisines $ C(x+1,t)$ et $ C(x-1,t)$ ($ C(x,t+1)$ est indépendant de $ C(x,t)$). Il en résulte une décomposition du domaine en sous-domaines indépendants et entrecroisés qui évoluent sans aucun échange d'information. Au temps temps $ t$ pair, l'un des sous-domaines sera décrit par $ C(2n,t)$ avec $ n$ entier; au temps $ t+1$ impair, il se trouvera en $ C(2n+1,t+1)$. Ce phénomène peut être affecté par les conditions aux limites du domaine. En cas de limites périodiques, il y a couplage entre les sous-domaines lorsque le nombre de sites est impair.

Ces principes restent valables dans des dimensions supérieures; le phénomène de parité se traduit par des effets de "damiers" en 4-connexité (ou 6-connexité en 3D). Cependant, ce problème peut à présent être contourné en intégrant les seconds voisins dans le voisinage d'un site - soit des relations de 8-connexité (en 2D) ou de 26-connexité (en 3D). Dans ce cas, les concentrations diffusent à travers un domaine unique, même lorsque $ D = 1$. On utilisera ainsi un noyau de convolution $ 3 \times 3$ en 2D (ou en 3D, $ 3 \times 3 \times 3$). En trois dimensions, si $ N_{26}$ représente l'ensemble des translations $ h(h_{x},h_{y},h_{z})$ décrivant le voisinage 26-connexe d'un site, l'équation II-5 devient:

$\displaystyle C(x,y,z,t+1)\ = (1 - D)\ C(x,y,z,t)\ +\ \frac{D}{26}\ (\sum_{h \in N_{26}} C(x+h_{x},y+h_{y},z+h_{z},t))$ (II.-6)

lorsque la diffusion est isotrope, avec un unique coefficient de diffusion $ D$. Une variante possible consiste à attribuer des pondérations différentes en fonction du niveau de voisinage (6 "premiers" voisins, 12 "seconds" voisins et 8 "troisièmes" voisins).


Optimisations
Nous traiterons ici le cas de l'opérateur de diffusion en trois dimensions; les principes restent semblables en deux dimensions. Le noyau de convolution utilisé pour l'opérateur de diffusion ne contient que deux pondérations différentes ($ 1-D$ au centre, et $ D/26$ pour le voisinage). Cette opération peut donc être optimisée par une méthode classique, dite de la fenêtre glissante. On remarque en effet que $ C(x,y,z,t)$ dépend en partie de $ C(x-1,y,z,t)$. La convolution est réalisée en balayant l'image par un masque cubique $ 3 \times 3 \times 3$, dans l'ordre des directions croissantes $ (x,y,z)$. Lorsque le masque se déplace d'un site dans la direction $ x$, seuls $ 9$ nouveaux points sont couverts par le masque, et $ 9$ points en sortent - la valeur de ces points ayant été conservée. Il en résulte qu'il n'est pas nécessaire de parcourir $ 26$ voisins en chaque site. Par ailleurs, l'opération de convolution pourrait aussi être décomposée selon les trois directions de l'espace, en raison de la forme gaussienne du noyau de convolution. Cependant, il serait alors nécessaire de balayer trois fois l'image par un masque à une dimension, orienté successivement dans les directions $ x$, $ y$ et $ z$. Sur le plan pratique, il semble que la multiplication des accès aux données ne soit pas avantageuse, en particulier en trois dimensions, en raison du mode de gestion de la mémoire vive dans les architectures matérielles usuelles. Enfin, la convolution est effectuée "en place", sans recourir à un autre domaine pour y enregistrer son résultat; il est cependant nécessaire d'utiliser une image temporaire bidimensionnelle pour y placer les valeurs du plan $ z$ en cours de traitement, avant qu'elles ne soient mises à jour. Cette image est alors utilisée lorsque le plan $ z+1$ vient à être balayé.

Decker, Luc. "Modèles de structures aléatoires de type réaction-diffusion". PhD diss. (191 p.), Paris, ENSMP-CMM, 1999.
Luc Decker   luc@texrd.com   www.texrd.com  -  Mars 1999