Level-Set-Methode - LinkFang.de





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 [math]n[/math]-dimensionalen Raum ein [math](n-1)[/math]-dimensionaler Rand [math] \Gamma [/math] (etwa eine Kurve für [math]n=2[/math]) als Nullstellenmenge ("level-set") einer [math]n[/math]-dimensionalen Hilfsfunktion [math] \phi(\vec{x}) [/math] beschrieben:

[math] \Gamma = \{\vec{x} | \phi(\vec{x}) = 0 \}.[/math]

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 [math] \Gamma [/math]. Bei einem zeitlich veränderlichen Rand kann analog eine zeitabhängige Hilfsfunktion [math] \phi(\vec{x}, t)[/math] definiert werden. Bewegt sich solch ein Rand entlang seiner Normalenrichtung mit einer Geschwindigkeit [math]\vec{v}(\vec{x}, t)[/math] in Richtung positiver [math]\phi(\vec{x}, t)[/math], kann man diese Bewegung mittels einer sogenannten Hamilton-Jacobi-Gleichung für die Hilfsfunktion darstellen:

[math] \partial\,\phi / \partial t = -\vec{v} \cdot \nabla \phi.[/math]

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

Häufig wird [math]\phi(\vec{x}, t)[/math] zusätzlich die Eigenschaft einer vorzeichenbehafteten Abstandsfunktion aufgeprägt ([math] |\nabla \phi|=1[/math]). Dadurch wird die numerische Verfolgung der Nullstellenmenge erleichtert. Die numerische Herstellung dieser Eigenschaft wird Reinitialisierung genannt. Häufig ist [math]\vec{v}[/math] nur für [math]\phi(\vec{x}, t) = 0 [/math] physikalisch sinnvoll definiert (bspw. Ausbreitungsgeschwindigkeiten bei der Simulation von Vormischflammen), so dass abseits von [math] \Gamma [/math] eine künstliche Geschwindigkeit vorgegeben werden muss. Soll die Eigenschaft [math]|\nabla \phi|=1[/math] erhalten bleiben, ist dort [math]\nabla \phi \cdot \nabla |\vec{v}|=0[/math] sicherzustellen. Neben der expliziten Sicherstellung von [math] |\nabla \phi|=1[/math] durch Reinitialisierung existieren Ansätze der impliziten Einbettung in die Formulierung von [math]\phi(\vec{x}, t)[/math]. 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.

Kategorien: Numerische Mathematik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Level-Set-Methode (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.