Dans
[1], nous avons proposé une
généralisation de la
méthode Fast Marching (FMM) introduite par Sethian [2] en
1996.
Cette méthode est un algorithme très rapide qui
permet de
faire avancer un front évoluant avec une vitesse normale
prescrite c=c(x)>0.
Le
problème qui nous intéresse est plus
général dans le sens où la vitesse que
l'on
considère dépend du temps et
peut changer de signe en espace-temps. L'exemple typique est le suivant:
Dans
la zone rouge, la vitesse est négative et le front
à
tendance à disparaître alors que dans la zone bleu
la
vitesse est positive et le front à tendance à
s'étendre. Notre méthode est une extension de la
FMM
classique que nous allons maintenant rappelé.
Méthode Fast Marching
On suppose que la vitesse c=c(x)>0. L'idée de la FMM est de voir le problème d'évolution comme un problème stationnaire et plus précisemment comme un problème de temps minimal. De manière plus concrète, le front va être représenté, dans une approche Level Sets, par la ligne de niveau zéro d'une fonction régulière u. On peut alors voir facilement (au moins formellement) que l'équation vérifiée par u est:
ut=c(x)|Du|.
Méthode Fast Marching Généralisée
La généralisation que nous avons proposée permet de traiter le cas de vitesses générales c(x,t) sans aucune restriction de signe. La difficulté principale vient du fait que l'on ne peut plus utiliser l'approche stationnaire. Nous allons utiliser la notion de solution discontinue pour représenter le front. De manière très simple, le front sera représenté par la discontinuité d'une fonction θ qui prendra les valeurs 1 et -1. La fonction est alors solution de l'équation (au sens de viscosité):
Méthode Fast Marching
On suppose que la vitesse c=c(x)>0. L'idée de la FMM est de voir le problème d'évolution comme un problème stationnaire et plus précisemment comme un problème de temps minimal. De manière plus concrète, le front va être représenté, dans une approche Level Sets, par la ligne de niveau zéro d'une fonction régulière u. On peut alors voir facilement (au moins formellement) que l'équation vérifiée par u est:
ut=c(x)|Du|.
Dans le cas où la
vitesse est positive, on peut alors chercher des solutions
stationnaires sous la forme u(x,t)=t-T(x).
La fonction T
représente alors le temps auquel le front passe au point x. Il est
également facile de voir que la fonction T est solution de
Une fois que l'on a construit la fonction T, on peut alors retrouver le front à l'instant t comme la ligne de niveau t de la fonction T. Comme exemple, prenons le cas d'un cercle (en bleu sur la figure suivante) qui se propage avec une vitesse normale c=1. La fonction T est alors un cône, comme représenté sur la figure de droite:
|DT|=1/c(x).
Une fois que l'on a construit la fonction T, on peut alors retrouver le front à l'instant t comme la ligne de niveau t de la fonction T. Comme exemple, prenons le cas d'un cercle (en bleu sur la figure suivante) qui se propage avec une vitesse normale c=1. La fonction T est alors un cône, comme représenté sur la figure de droite:
Sur cette image, on voit
qu'à chaque hauteur t,
la surface donne l'ensemble des points atteints par le front au temps t.
L'idée de la méthode Fast Marching est alors de résoudre directement (et de manière très rapide) l'équation sur T. On va alors utiliser une discrétisation du gradient, donnée par le schéma de Rouy, Tourin. Pour la valeur de TI au point I, on va utilisé les valeurs de TH, TB, TG et TD au points H, B, G et D :
Le schéma est alors donné par :
Au lieu d'utiliser un schéma itératif, Sethian a montré que l'on pouvait résoudre cette équation en une seule itération à condition de calculer la valeur des noeuds dans le bon ordre. En fait, l'ordre des noeuds est donné par les valeurs croissantes de T. Pour ce faire, l'idée est de trier les noeuds en trois catégories:
L'idée de la méthode Fast Marching est alors de résoudre directement (et de manière très rapide) l'équation sur T. On va alors utiliser une discrétisation du gradient, donnée par le schéma de Rouy, Tourin. Pour la valeur de TI au point I, on va utilisé les valeurs de TH, TB, TG et TD au points H, B, G et D :
Le schéma est alors donné par :
| max(TI − TG, TI − TD, 0)² | |
| + | = (Δx/c(xI))² (1) |
| max(TI − TH, TI − TB, 0)² |
Au lieu d'utiliser un schéma itératif, Sethian a montré que l'on pouvait résoudre cette équation en une seule itération à condition de calculer la valeur des noeuds dans le bon ordre. En fait, l'ordre des noeuds est donné par les valeurs croissantes de T. Pour ce faire, l'idée est de trier les noeuds en trois catégories:
- Les points Frozen (ou acceptés) : c'est l'ensemble des points où le front est déjà passé et pour lesquels on connait le temps T.
- La Narrow Band : c'est l'ensemble des points qui peuvent être potentiellement atteint par le front. Ce sont sur ces que l'on va effectué des calculs.
- Les points Far : ce sont les autres points qui ne peuvent pas être atteint par le front dans l'immédiat.
- Calcul des temps candidats : pour tous les points I de la Narrow Band, on calcul la valeur TI en résolvant le schéma (1). Pour ce faire, on utilise la valeur des points voisins uniquement si ceux-ci ont déjà été accepté.
- Calcul du minimum : on appelle tn le temps minimal TI pour I dans la Narrow Band et on accepte au temps tn tous les points qui réalisent le minimum.
- Mise a jour
de la Narrow Band : on redéfinit la Narrow Band comme le
bord de la nouvelle région acceptée.
Méthode Fast Marching Généralisée
La généralisation que nous avons proposée permet de traiter le cas de vitesses générales c(x,t) sans aucune restriction de signe. La difficulté principale vient du fait que l'on ne peut plus utiliser l'approche stationnaire. Nous allons utiliser la notion de solution discontinue pour représenter le front. De manière très simple, le front sera représenté par la discontinuité d'une fonction θ qui prendra les valeurs 1 et -1. La fonction est alors solution de l'équation (au sens de viscosité):
θt=c(x,t)|Dθ|
L'idée de base est
assez simple. Il s'agit en fait,
à chaque étape, de considérer deux
zones : une où la vitesse est négative et l'autre
où elle est positive. Ensuite, il suffit de faire
évoluer en utilisant deux Fast Marching (une dans chaque
zone). Le schéma suivant explique cette idée:Le front est
représenté par la ligne violette (la ligne de
discontinuité de la fonction θ).
Dans la zone de gauche, où la vitesse est positive, c'est l'ensemble θ=1 qui va grossir, alors que dans la zone de droite, c'est la zone θ=-1
qui va grossir. De plus, pour bien séparer ces deux zones, nous
imposons numériquement une bande où la vitesse est nulle.
Comme dans la méthode Fast Marching classique, on peut alors
définir les points de la Narrow Band (les ronds rouges sur la
figures) et les points utiles (les carrées bleus, qui joueront
le rôle des points frozen). L'algorithme est alors
essentiellement le même que dans le cas classique: on calcul les
temps candidats sur la Narrow Band, on cherche le minimum, puis on
itère.
Il y a cependant plusieurs suptilités dans cette nouvelle version. Tout d'abord, pour résoudre l'équation (1), nous avons maintenant besoin de connaître le temps courant (à utiliser dans la vitesse). En fait le temps est directement donné par l'algorithme comme le minimum des temps candidats. Nous renvoyons à [1] pour une description détaillée de l'algorithme
Il y a cependant plusieurs suptilités dans cette nouvelle version. Tout d'abord, pour résoudre l'équation (1), nous avons maintenant besoin de connaître le temps courant (à utiliser dans la vitesse). En fait le temps est directement donné par l'algorithme comme le minimum des temps candidats. Nous renvoyons à [1] pour une description détaillée de l'algorithme