1.5 Aspects numériques I : consistance et précision
21
1.5.1 Redistanciation de ϕ
La première méthode consiste à redresser une fonction Level Set donnée
ϕ 0 en une fonction distance signée à chaque pas de temps. Cette idée est
apparue très vite en méthodes Level Set [136, 135] et a connu de nombreux
développements (on pourra par exemple consulter [121, 31, 109]). On se
bornera ici à donner les grandes lignes de la méthode.
La redistanciation de la fonction Level Set peut être faite par exemple en
résolvant l’équation d’Hamilton-Jacobi suivante :
∂ τ ϕ + sgn(ϕ 0 )(|∇ϕ| − 1) = 0.
(1.35)
avec ϕ 0 comme condition initiale, équation dont on cherche un état stationnaire. En pratique, du fait de l’hyperbolicité de cette équation, le redressement
de ϕ est propagé à partir de {ϕ = 0} si bien qu’il suffit de quelques itérations
pour avoir |∇ϕ| ≈ 1 au voisinage de {ϕ = 0}. En effet, l’équation ci-dessus
peut être écrite comme une équation de transport avec second membre :
∂ τ ϕ + sgn(ϕ 0 )
∇ϕ
|∇ϕ|
· ∇ϕ = −sgn(ϕ 0 ).
(1.36)
Les caractéristiques sont donc issues de {ϕ 0 = 0} et perpendiculaires à cette
interface. On peut effectivement montrer que cette équation ne modifie pas la
ligne de niveau zéro de la fonction initiale (i.e. {ϕ(·,t) = 0} = {ϕ 0 = 0} pour
tout t > 0). L’inconvénient de cette approche est d’une part qu’il faut résoudre
cette équation supplémentaire et que, d’autre part, sa discrétisation numérique
entraine en pratique un déplacement de l’interface. C’est un inconvénient que
plusieurs contributions se sont attelé à réduire au détriment de la simplicité
de la méthode [135, 121, 31, 109, 56]. Une difficulté tient notamment à
l’approximation numérique de la fonction signe.
D’autres méthodes consistent à résoudre directement l’équation eikonale.
Etant donnée une interface {ϕ 0 = 0}, où ϕ 0 n’est pas une fonction distance,
on cherche ϕ satisfaisant
|∇ϕ| = 1 dans Ω
ϕ = 0
sur {ϕ 0 = 0}
(1.37)
Parmi ces méthodes, qui ont débuté historiquement par le Fast Marching de J.
Sethian [123, 124, 94], on retrouve le Fast Sweeping [144, 117] et la méthode
de Dapogny et Frey [41].
Une autre approche consiste à transporter ϕ en dehors de l’interface
de manière à ce que l’on ait toujours |∇ϕ| = 1. Une méthode, introduite
initialement par Osher et ses co-auteurs [146] d’aprés une idée d’Evans et
Spruck [59], puis reprise par Gomes et Faugeras [78] et, dans le cadre de
l’optimisation de formes, par Delfour et Zolésio [47], consiste à déterminer ϕ
21
1.5.1 Redistanciation de ϕ
La première méthode consiste à redresser une fonction Level Set donnée
ϕ 0 en une fonction distance signée à chaque pas de temps. Cette idée est
apparue très vite en méthodes Level Set [136, 135] et a connu de nombreux
développements (on pourra par exemple consulter [121, 31, 109]). On se
bornera ici à donner les grandes lignes de la méthode.
La redistanciation de la fonction Level Set peut être faite par exemple en
résolvant l’équation d’Hamilton-Jacobi suivante :
∂ τ ϕ + sgn(ϕ 0 )(|∇ϕ| − 1) = 0.
(1.35)
avec ϕ 0 comme condition initiale, équation dont on cherche un état stationnaire. En pratique, du fait de l’hyperbolicité de cette équation, le redressement
de ϕ est propagé à partir de {ϕ = 0} si bien qu’il suffit de quelques itérations
pour avoir |∇ϕ| ≈ 1 au voisinage de {ϕ = 0}. En effet, l’équation ci-dessus
peut être écrite comme une équation de transport avec second membre :
∂ τ ϕ + sgn(ϕ 0 )
∇ϕ
|∇ϕ|
· ∇ϕ = −sgn(ϕ 0 ).
(1.36)
Les caractéristiques sont donc issues de {ϕ 0 = 0} et perpendiculaires à cette
interface. On peut effectivement montrer que cette équation ne modifie pas la
ligne de niveau zéro de la fonction initiale (i.e. {ϕ(·,t) = 0} = {ϕ 0 = 0} pour
tout t > 0). L’inconvénient de cette approche est d’une part qu’il faut résoudre
cette équation supplémentaire et que, d’autre part, sa discrétisation numérique
entraine en pratique un déplacement de l’interface. C’est un inconvénient que
plusieurs contributions se sont attelé à réduire au détriment de la simplicité
de la méthode [135, 121, 31, 109, 56]. Une difficulté tient notamment à
l’approximation numérique de la fonction signe.
D’autres méthodes consistent à résoudre directement l’équation eikonale.
Etant donnée une interface {ϕ 0 = 0}, où ϕ 0 n’est pas une fonction distance,
on cherche ϕ satisfaisant
|∇ϕ| = 1 dans Ω
ϕ = 0
sur {ϕ 0 = 0}
(1.37)
Parmi ces méthodes, qui ont débuté historiquement par le Fast Marching de J.
Sethian [123, 124, 94], on retrouve le Fast Sweeping [144, 117] et la méthode
de Dapogny et Frey [41].
Une autre approche consiste à transporter ϕ en dehors de l’interface
de manière à ce que l’on ait toujours |∇ϕ| = 1. Une méthode, introduite
initialement par Osher et ses co-auteurs [146] d’aprés une idée d’Evans et
Spruck [59], puis reprise par Gomes et Faugeras [78] et, dans le cadre de
l’optimisation de formes, par Delfour et Zolésio [47], consiste à déterminer ϕ