Level-Set-Methode


Level-Set-Methode

Die Level-Set-Methode oder Niveaumengenmethode ist ein numerisches Verfahren, um geometrische Objekte und deren Bewegung approximativ zu verfolgen.

Der Vorteil der Level-Set-Methode liegt darin, dass man Kurven und Oberflächen auf einem räumlich festen (Eulerschen) Koordinatensystem berechnen kann, ohne Parametrisierungen dieser Objekte verwenden zu müssen. Insbesondere muss bei der Level-Set-Methode die Topologie (zum Beispiel die Anzahl der zusammenhängenden Gebiete) nicht bekannt sein, und sie kann sich während der Berechnung ändern. Dies erlaubt die einfache Verfolgung der Ränder beweglicher Objekte, beispielsweise eines Airbags oder eines Tropfens Öl, der in Wasser schwimmt.

Bei der Level-Set-Methode wird im n-dimensionalen Raum ein (n − 1)-dimensionaler Rand Γ (etwa eine Kurve für n = 2) als Nullstellenmenge ("level-set") einer n-dimensionalen Hilfsfunktion  \phi(\vec{x}) beschrieben:

 \Gamma(\vec{x})  = \{\vec{x} | \phi(\vec{x}) = 0 \}.

Die Hilfsfunktion wird auf dem ganzen betrachteten Gebiet definiert, und zwar mit positiven Werten auf der einen und negativen Werten auf der anderen Seite von Γ. Bei einem zeitlich veränderlichen Rand kann analog eine zeitabhängige Hilfsfunktion  \phi(\vec{x}, t) definiert werden. Bewegt sich solch ein Rand entlang seiner Normalenrichtung mit einer Geschwindigkeit \vec{v}(\vec{x}, t) in Richtung positiver \phi(\vec{x}, t), kann man diese Bewegung mittels einer sogenannten Hamilton-Jacobi-Gleichung für die Hilfsfunktion darstellen:

 \partial\,\phi / \partial t = -\vec{v} \cdot |\nabla \phi|.

Diese partielle Differentialgleichung kann mit Hilfe von numerischen Näherungsmethoden (Finiten Differenzen) auf einem numerischen Gitter berechnet werden. Um die Kurve Γ zu verschiedenen Zeitpunkten der Bewegung darzustellen, muss nun die Nullstellenmenge der Funktion φ verfolgt werden.

Häufig wird \phi(\vec{x}, t) zusätzlich die Eigenschaft einer vorzeichenbehafteten Abstandsfunktion aufgeprägt ( |\nabla \phi|=1). Dadurch wird die numerische Verfolgung der Nullstellenmenge erleichtert. Die numerische Herstellung dieser Eigenschaft wird Reinitialisierung genannt. Häufig ist \vec{v} nur für \phi(\vec{x}, t) = 0 physikalisch sinnvoll definiert (bspw. Ausbreitungsgeschwindigkeiten bei der Simulation von Vormischflammen), so dass abseits von Γ eine künstliche Geschwindigkeit vorgegeben werden muss. Soll die Eigenschaft |\nabla \phi|=1 erhalten bleiben, ist dort \nabla \phi \cdot \nabla |\vec{v}|=0 sicherzustellen. Neben der expliziten Sicherstellung von  |\nabla \phi|=1 durch Reinitialisierung existieren Ansätze der impliziten Einbettung in die Formulierung von \phi(\vec{x}, t). So können (beispielsweise durch Einführung eines Regularisierungsterms) solche Bewegungen bevorzugt werden, die in einer approximativ vorzeichenbehafteten Abstandsfunktion resultieren. [1]

Entwickelt wird die Level-Set Methode als numerisches Verfahren seit den 1980er Jahren vor allem von den amerikanischen Mathematikern Stanley Osher und James Sethian. Sie wird seitdem in vielen Bereichen (numerische Strömungsmechanik, Computergrafik) erfolgreich eingesetzt.

Literatur

  • James Albert Sethian: Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge University Press 1996, ISBN 0-5215-720-29
  • James Albert Sethian: Level Set Methods and Fast Marching Methods, Cambridge University Press 1999, ISBN 0-5216-455-73
  • S. J. Osher, R. Fedkiw: Level Set Methods and Dynamic Implicit Surfaces, Springer 2002, ISBN 0-3879-548-21
  1. Li, C. & Xu, C. & Gui, C. & Fox, M.D.: Distance Regularized Level Set Evolution and its Application to Image Segmentation. IEEE Trans. Image Processing (19), 2010. pp. 3243–3254.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Level Set Methode — Die Level Set Methode oder Niveaumengenmethode ist ein mathematisches Verfahren um geometrische Objekte und deren Bewegung numerisch zu berechnen. Der Vorteil der Level Set Methode liegt darin, dass man Kurven und Oberflächen auf einem räumlich… …   Deutsch Wikipedia

  • Méthode des surfaces de niveau — 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ù… …   Wikipédia en Français

  • Méthode de Viola et Jones — Un exemple de détection de visage par la méthode de Viola et Jones. La méthode de Viola et Jones est une méthode de détection d objet dans une image numérique, proposée par les chercheurs Paul Viola et …   Wikipédia en Français

  • Méthode composite de chimie quantique — Les méthodes composites de chimie quantique sont des méthodes de chimie numérique dont le but est d obtenir une grande précision par combinaison des résultats de plusieurs calculs. Cette combinaison est constituée à partir de méthodes d un haut… …   Wikipédia en Français

  • High-level data link control — Pile de protocoles 7 • Application 6 • Présentation 5 • Session 4 • …   Wikipédia en Français

  • High Level Data Link Control — Pile de protocoles 7 • Application 6 • Présentation 5 • Session 4 • …   Wikipédia en Français

  • High level data link control — Pile de protocoles 7 • Application 6 • Présentation 5 • Session 4 • …   Wikipédia en Français

  • Sound level meter — Type 1 Sound Level Meter (Shown: Svantek 979) Sound level meters measure sound pressure level and are commonly used in noise pollution studies for the quantification of almost any noise, but especially for industrial, environmental and aircraft… …   Wikipedia

  • High-Level Data Link Control — Pile de protocoles 7.  Application 6.  Présentation 5.  Session 4.  Tr …   Wikipédia en Français

  • Niveaumengenmethode — Die Level Set Methode oder Niveaumengenmethode ist ein mathematisches Verfahren um geometrische Objekte und deren Bewegung numerisch zu berechnen. Der Vorteil der Level Set Methode liegt darin, dass man Kurven und Oberflächen auf einem räumlich… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.