STRUCTURES DE TURING

Les structures de Turing
Linéarisation
Application à la généeration de textures

Les structures de Turing

       Alan Turing, mathématicien anglais (1912-1954), s´intéressa à de multiples questions, allant de la théorie des fonctions calculables au décodage, pendant la guerre, des messages secrets allemands, en passant par la construction des premiers ordinateurs et à l´élobaration de ce qui devait devenir l´intelligence artificielle [Lassègue 98]. Il indiqua aussi un lien possible, à partir de la cybernetique, entre physique, biologie et informatique posant ainsi les bases de ce qui devait devenir la vie artificielle.
        S´intéressant à l´hydra, ou hydre d´eau douce, dont la reproduction se fait par division, il décrivit le phénomène de réaction-diffusion, pour expliquer l´apparition de taches d´ou naitront les tentacules.
        Turing considéra un système chimique dont la dynamique est déterminée par deux produits, qu´il appela des morphogènes, diffusant dans le milieu réactionnel. L´un, a, est auto-activateur et l´autre, b, est inhibiteur s´opposant à la production de a mais dont la synthèse est catalysée par a.
        Le système étant dans un état initial stationnaire uniforme, les fluctuations aléatoires des concentrations des deux produits a et b (dues aux mouvements browniens des molécules au sein du mélange) peuvent amener à un excès de a en un point A. La figure ci-dessous montre les variations des concentrations des produits a et b en fonction de la distance (on suppose que l´espace de distribution est linéaire pour simplifier). a étant auto-activateur, sa concentration augmente et, puisqu´il catalyse la synthèse de b, ce dernier va aussi augmenter sa concentration: Un pic de a et de b se forme localement en A. Supposons que l´inhibiteur b diffuse plus rapidement que a, son pic est alors plus étalé. Le niveau de b au centre du pic n´est plus suffisant pour inhiber a dont la concentration croit, par contre, sur les bords du pic, il est suffisant pour inhiber a dont la concentration décroit donnant lieu à deux pics negatifs B1 et B2. À une distance suffisamment grande de A, b a une faible concentration, et d´autres pics de a peuvent apparaitre (en C sur la figure). Si l´on maintient un apport contine des réactifs frais a et b et si l´on élimine les produits en excès, un équilibre dynamique entre réactions chimiques (synthèse-inhibition) et diffusions s´installe, produisant des patterns réguliers de pics de concentration (D) [De Kepper 98].

Variations des concentrations de A et de B en fonction de la distance.

        Ce sont les structures de Turing. Ce processus, appelé réaction-diffusion, a été appliqué au développement des cellules de différents types lors de l´embryogenèse, expliquant ainsi la morphogenèse des organismes.
        Le système d´équations différentielles linéaires suivant permet de modéliser ce phénomène:

        da / dt = F(a,b) + D_a * V²_a
        db / dt = G(a,b) + D_b * V²_b

        da / dt est la vitesse de la variation de la concentration de a.
        F(a,b) est une fonction des concentrations locales de a et b.
        D_a est une constante proportionnelle à la vitesse de diffusion de a.
        Le Laplacien V²_a mesure la concentration de a en un point par rapport à la concentration de a en un voisinage de ce point:
                V²_a = d² a / d x²
        Si V²_a > 0 la diffusion a lieu vers le point,
        Si V²_a < 0 la diffusion a lieu à partir de ce point.

Linéarisation

Espace à une dimension
Espace à deux dimensions

Turing a proposé une approximation linéaire de ces équations pour un espace de cellules discrétisant le milieu homogène du mélange des deux produits a et b, selon la dimension de cet espace (1: linéaire, 2: surfacique, etc ...).

Espace à une dimension

L´espace est une ligne de cellules numerotées de 1 à n, le voisinage de la cellule a_i est le couple:
[a_i-1, a_i+1].

Voisinage de a_i         Variation en x

        L´accroissemnt de concentration de a_i dans le temps est une approximation linéaire de la vitesse de cette variation:
        da_i / dt = a_i - a_i-1

        L´accroissemnt de concentration de a_i sur l´axe x est une approximation linéaire de la vitesse de cette variation:
        da_i / dx = a_i - a_i-1
        De même:
        da_i+1 / dx = a_i+1 - a_i
        L´accroissement de ces vitesses est une approximation lineaire du Laplacien:
        d² a / d x² = (a_i+1 - a_i) - (a_i - a_i-1)
        Soit:
        V²_A = a_i+1 + a_i-1 - 2 * a_i
        Turing a propose les equations suivantes:
        d a_i = s * (16 - a_i * b_i) + D_a * (a_i+1 + a_i-1 - 2 * a_i)
        d b_i = s * (a_i * b_i - b_i - e_i) + D_b * (b_i+1 + b_i-1 - 2 * b_i)
        les e_i sont des irrégularités aléatoires des concentrations chimiques.
        La figure suivante illustre la progression des concentrations du produit b le long d´une ligne de 60 cellules [Turk 91]. Initialement les concentrations en a et b étaient uniformément égales à 4. Les e_i valent 12 avec une variation aléatoire d´amplitude 0.05. On a pris D_a = 0.25, D_b = 0.0625 (a diffuse plus rapidement que b) et s = 0.03125. Après 2000 itérations la concentration de b est distribuée selon un motif presque périodique.

Espace à deux dimensions

Les cellules sont disposées aux sommets d´une grille régulière de dimensions n et m. Un voisinage de la cellule a_ij est:
[a_i+1,j, a_i-1,j, a_i,j+1, a_i,j-1].

Voisinage de a_ij         Variation en x         Variation en y

        Soit a(x,y) la fonction de diffusion du morphogène a.
        On a [Witkin 91]:
        da / dt = dif² * V²_a - diss * a + R.
        da / dt est la vitesse de variation de a.
        dif est le coefficient de diffusion.
        diss est le coefficient de dissipation.
        R est la fonction de réaction contrôlant a.
        Le Laplacien a pour expression:
        V²_a = d² a / d x² + d² a / d y²
        On a les approximations suivantes:
        d² a / d x² = (a_i+1,j + a_i-1,j - 2 * a_i,j) / h² et
        d² a / d y² = (a_i,j+1 + a_i,j-1 - 2 * a_i,j) / h²
        avec h = distance de 2 cellules. Soit:
        V²_a = (a_i+1,j + a_i-1,j + a_i,j+1 + a_i,j-1 - 4 * a_i,j) / h².
        Les équations s´écrivent:
        d a_ij = s * (16 - a_ij * b_ij) + D_a * (a_i+1,j + a_i-1,j + a_i,j+1 + a_i,j-1 - 4 * a_ij)
        d b_ij = s * (a_ij * b_ij - b_ij - e_ij) + D_b * (b_i+1,j + b_i-1,j + b_i,j+1 + b_i,j-1 - 4 * b_ij)
        Remarquons que sur une grille irrégulière il faudrait pondérer les valeurs aux voisins de a en fonction de leurs distances à a.
        La figure de gauche suivante [Turk 91] est le résultat d´une simulation sur une grille de 64 * 64 cellules, les régions sombres correspondant à des pics de a, la taille des taches dépend de la valeur de s, leur régularité dépend des variations aléatoires de e_ij.
        On peut généraliser le principe de la réaction-diffusion à plus de deux réactifs, une simulation est montrée sur la figure de droite:

(s = 0.05 de = 0.1)         (s = 0.2 de = 0.1)
(s = 0.05 de = 3.0)         (s = 0.2 de = 3.0)

Application à la génération de textures

        En remplacant la grille plane régulière du modèle 2D (voir ST-2-2) par l´approximation polyédrique d´une surface paramétrique, il est possible de synthétiser une texture selon le principe de la réaction-diffusion.
        Les avantages de cette méthode sont les suivants:
        1) C´est une méthode procédurale ne nécessitant pas que soient stockées des images de référence.
        2) Il n´y a pas de distorsion comme dans le mapping 2D.
        3) Il n´est pas nécessaire d´assigner des coefficients de texture aux sommets de la grille.
        Turk [Turk 91] décrit un algorithme pour générer une grille régulière à partir d´un modèle géométrique: Une distribution aléatoire de sommets est d´abord réalisée sur le modèle, puis ces sommets sont corrigés de façon a uniformiser leurs distances respectives par une méthode de relaxation (en affectant à chaque sommet une masse et une force inversement proportionnelle aux distances à ses voisins, et en les laissant dynamiquement prendre une position d´équilibre sans quitter la surface).
        Une topologie est ensuite définie sur le nuage de sommets ainsi obtenu en déterminant, pour chaque sommet, sa région de Voronoi: Étant donné un ensemble S de points du plan, la région de Voronoi d´un point P de S est le sous ensemble V de S tel que P est le plus proche de tous les points de V, elle est déterminée par les médiatrices des segments joignant P à ses voisins.
        Le calcul du Laplacien dépend des coefficients de diffusion qui sont les longueurs (normalisées) des côtés de la région de Voronoi:

Région de Voronoi                 d = coefficient de diffusion

        La figure suivante montre [Turk 91]:
        1) Le modèle géométrique polyédrique.
        2) Une distribution aléatoire de sommets sur ce modèle.
        3) La même distribution avec des distances uniformes.
        4) Une topologie obtenue par régions de Voronoi.
        5 et 6) Le rendu d´une texture de réaction-diffusion.

Exemples de textures générées par réaction-diffusion [Turk 91].

Leopard-Cheval Pseudo-Zèbre

Exemples de textures générées par réaction-diffusion [Witkin 91].