Méthode des surfaces de niveau

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La méthode des surfaces de niveau est une technique numérique de suivi d'une interface entre un mobile déformable et le milieu dans lequel il se déplace. L'idée consiste à remplacer une courbe plane fermée par une surface fixe dans un espace où le temps représente la troisième dimension. De même, une surface déformable peut être traitée dans un espace à quatre dimensions. Cette modification du point de vue suffit pour esquiver certains problèmes posés dans l'espace physique par les modifications de la topologie, par exemple quand une forme se partage en deux, fait apparaître des trous ou l'inverse.

Historique[modifier | modifier le code]

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.

Description élémentaire[modifier | modifier le code]

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 \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 \varphi tandis que la forme proprement dite est l'ensemble des points pour lesquels \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.

Quelques éléments techniques[modifier | modifier le code]

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

L'interface variable est alors définie par :

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

\varphi est positif à l'intérieur de \Omega, négatif à l'extérieur et nul sur \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é \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 \varphi(\mathbf{x},t) qui représente l'interface comme l'ensemble tel que \varphi(\mathbf{x},t)=0. La fonction \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 \Gamma(t) pour lequel \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 \phi par le champ de vitesse \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 \mathbf{\nabla}\varphi

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

.

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

v_N = \mathbf{v}. \frac {\nabla \varphi} {|\nabla \varphi|}

.

de sorte que l'équation devient

\frac{\partial \varphi} {\partial t} + v_N |\nabla \varphi| = 0

où la fonction module représente la norme euclidienne et 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.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Level set method » (voir la liste des auteurs)

  1. (en) Level Set Methods - An Overview and Some Recent Results, par Stanley Osher (en) et Ronald Fedkiw (en).

Lien externe[modifier | modifier le code]

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