Méthode des surfaces de niveau

La méthode des surfaces de niveau a été développée dans les années 1980 par les mathématiciens Stanley Osher et James Sethian. Elle s'est répandue dans de nombreuses disciplines, comme les effets spéciaux numériques, le traitement d'images, l'infographie, la géométrie algorithmique, l'optimisation et la mécanique des fluides numérique.

Illustration de la méthode des surfaces de niveau

La méthode des surfaces de niveau est généralement utilisée pour suivre des interfaces à deux dimensions (on peut parler alors de méthode des lignes de niveau) ou trois dimensions.

Une façon efficace bien que très simple de comprendre la méthode dans le cas d'interfaces à deux dimensions consiste à étudier l'illustration ci-contre avant de poursuivre avec une définition un peu plus technique qui sera ainsi d'accès plus facile. La figure de droite illustre plusieurs idées importantes sur la méthode. En haut à gauche nous voyons une courbe, c'est-à-dire une région bornée par une frontière régulière. Au-dessous, la surface rouge représente une fonction ${\displaystyle \varphi }$ qui détermine cette forme, le plan bleu étant le plan (x,y). Le bord de cette forme est alors la courbe de niveau de ${\displaystyle \varphi }$ tandis que la forme proprement dite est l'ensemble des points pour lesquels ${\displaystyle \varphi }$ est positif ou nul.

Dans la rangée supérieure nous voyons la modification de la topologie par une scission. Il serait extrêmement difficile de décrire numériquement cette transformation en paramétrant la frontière et en suivant son évolution. Il faudrait un algorithme capable de détecter le moment de cette scission puis de construire des paramétrisations des deux nouvelles courbes. D'autre part, si nous considérons la rangée inférieure, nous voyons que la fonction de courbe de niveau a simplement été translatée vers le bas. Il apparaît que, plutôt que de travailler directement sur une forme en envisageant toutes ses déformations possibles, il est beaucoup plus facile d'utiliser la fonction de surfaces de niveau correspondante dans un espace muni d'une dimension supplémentaire.

L'idée de base de la méthode des courbes de niveau est simple[1]. Une interface ${\displaystyle \Gamma }$ qui borne une région ouverte ${\displaystyle \Omega }$ peut être définie à l'instant ${\displaystyle t}$ au point ${\displaystyle \mathbf {x} }$ comme le niveau zéro d'une fonction lisse ${\displaystyle \varphi (\mathbf {x} ,t)}$.

L'interface variable est alors définie par :

${\displaystyle \Gamma (t)={\begin{Bmatrix}(\mathbf {x} ,t)\mid \varphi (\mathbf {x} ,t)=0\end{Bmatrix}}}$.

${\displaystyle \varphi }$ est positif à l'intérieur de ${\displaystyle \Omega }$, négatif à l'extérieur et nul sur ${\displaystyle \Gamma (t)}$.

La position initiale de l'interface étant donnée, il s'agit de calculer son mouvement ultérieur dans un champ de vitesses donné ${\displaystyle \mathbf {v} }$. Ces vitesses peuvent être fonction de la position, du temps, de la géométrie de l'interface (par exemple sa normale ou sa courbure moyenne) et de la physique du milieu extérieur.

L'idée consiste simplement à définir une fonction lisse ${\displaystyle \varphi (\mathbf {x} ,t)}$ qui représente l'interface comme l'ensemble tel que ${\displaystyle \varphi (\mathbf {x} ,t)=0}$. La fonction ${\displaystyle \varphi }$ qui s'annule sur l'interface est positive à l'intérieur et négative à l'extérieur. Ainsi l'interface sera capturée à tous les instants ultérieurs en localisant simplement l'ensemble ${\displaystyle \Gamma (t)}$ pour lequel ${\displaystyle \varphi }$ s'annule. Les modifications de la topologie comme une séparation ou un regroupement sont alors bien définies sans ambiguïté.

Le mouvement s'analyse en faisant transporter les valeurs des niveaux ${\displaystyle \varphi }$ par le champ de vitesse ${\displaystyle \mathbf {v} }$. L'équation exprime qu'en chaque point la variation du niveau est portée par la normale à l'interface, c'est-à-dire par le gradient ${\displaystyle \mathbf {\nabla } \varphi }$

${\displaystyle {\frac {\partial \varphi }{\partial t}}+\mathbf {v} .\mathbf {\nabla } \varphi =0}$

.

En réalité, seule la composante normale de ${\displaystyle \mathbf {v} }$ est nécessaire :

${\displaystyle v_{N}=\mathbf {v} .{\frac {\nabla \varphi }{|\nabla \varphi |}}}$

.

de sorte que l'équation devient

${\displaystyle {\frac {\partial \varphi }{\partial t}}+v_{N}|\nabla \varphi |=0}$

où la fonction module représente la norme euclidienne et ${\displaystyle t}$ le temps. C'est une équation aux dérivées partielles, plus particulièrement une équation de Hamilton-Jacobi, qui peut en principe être résolue numériquement.

Néanmoins les méthodes élémentaires de différences finies échouent rapidement. Des techniques d'ordre élevé sont généralement nécessaires.

(en) Moving interfaces and boundaries, par James Sethian (en)