Level-Set-Methode

Die Level-Set-Methode (LSM) 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 ${\displaystyle n}$-dimensionalen Raum ein ${\displaystyle (n-1)}$-dimensionaler Rand ${\displaystyle \Gamma }$ (etwa eine Kurve für ${\displaystyle n=2}$) als Nullstellenmenge („level-set“) einer ${\displaystyle n}$-dimensionalen Hilfsfunktion ${\displaystyle \phi ({\vec {x}})}$ beschrieben:

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

${\displaystyle \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 ${\displaystyle \Gamma }$ zu verschiedenen Zeitpunkten der Bewegung darzustellen, muss nun die Nullstellenmenge der Funktion ${\displaystyle \phi }$ verfolgt werden.

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

• James Albert Sethian: Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge University Press 1996, ISBN 0-521-57202-9
• James Albert Sethian: Level Set Methods and Fast Marching Methods, Cambridge University Press 1999, ISBN 0-521-64557-3
• S. J. Osher, R. Fedkiw: Level Set Methods and Dynamic Implicit Surfaces, Springer 2002, ISBN 0-387-95482-1

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.