Level set method

The level set method ( LSM ) or level set method is a numerical method for approximating geometric objects and their movement.

The advantage of the level set method is that curves and surfaces can be calculated on a spatially fixed (Euler) coordinate system without having to use parameterizations of these objects. In particular, with the level set method, the topology (for example the number of contiguous areas) does not have to be known and it can change during the calculation. This allows easy tracking of the edges of moving objects, such as an airbag or a drop of oil floating in water .

In the level-set method, a -dimensional boundary (e.g. a curve for ) is described as a set of zeros ("level-set") of a -dimensional auxiliary function : ${\ displaystyle n}$ ${\ displaystyle (n-1)}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle n = 2}$ ${\ displaystyle n}$ ${\ displaystyle \ phi ({\ vec {x}})}$

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

The auxiliary function is defined over the entire area under consideration, with positive values on one side and negative values on the other . If the margin changes over time, a time-dependent auxiliary function can be defined analogously . If such an edge moves along its normal direction with a speed in the direction more positive , this movement can be represented by a so-called Hamilton-Jacobi equation for the auxiliary function: ${\ displaystyle \ Gamma}$ ${\ displaystyle \ phi ({\ vec {x}}, t)}$ ${\ displaystyle {\ vec {v}} ({\ vec {x}}, t)}$ ${\ displaystyle \ phi ({\ vec {x}}, t)}$

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

This partial differential equation can be calculated using numerical approximation methods ( finite differences ) on a numerical grid. In order to display the curve at different points in time of the movement, the set of zeros of the function must now be followed. ${\ displaystyle \ Gamma}$ ${\ displaystyle \ phi}$

Often the property of a signed distance function is also impressed ( ). This makes it easier to track the number of zeros numerically. The numerical production of this property is called reinitialization . Often it is only defined in a physically meaningful way (e.g. propagation speeds when simulating premixed flames ), so that apart from an artificial speed must be specified. If the property is to be retained, it must be ensured there. In addition to the explicit safeguarding of through reinitialization, there are approaches of implicit embedding in the formulation of . For example, by introducing a regularization term, preference can be given to movements that result in an approximately signed distance function. ${\ displaystyle \ phi ({\ vec {x}}, t)}$ ${\ displaystyle | \ nabla \ phi | = 1}$ ${\ displaystyle {\ vec {v}}}$ ${\ displaystyle \ phi ({\ vec {x}}, t) = 0}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle | \ nabla \ phi | = 1}$ ${\ displaystyle \ nabla \ phi \ cdot \ nabla | {\ vec {v}} | = 0}$ ${\ displaystyle | \ nabla \ phi | = 1}$ ${\ displaystyle \ phi ({\ vec {x}}, t)}$

The level set method has been developed as a numerical method since the 1980s, primarily by the American mathematicians Stanley Osher and James Sethian . Since then it has been used successfully in many areas ( numerical fluid mechanics , computer graphics ).

literature

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
SJ Osher, R. Fedkiw: Level Set Methods and Dynamic Implicit Surfaces , Springer 2002, ISBN 0-3879-548-21

^ Li, C. & Xu, C. & Gui, C. & Fox, MD: Distance Regularized Level Set Evolution and its Application to Image Segmentation . IEEE Trans. Image Processing (19), 2010. pp. 3243-3254.

[1] Li, C. & Xu, C. & Gui, C. & Fox, MD: Distance Regularized Level Set Evolution and its Application to Image Segmentation . IEEE Trans. Image Processing (19), 2010. pp. 3243-3254.