Level set method

Level set method

The level set method (sometimes abbreviated as LSM) is a numerical technique for tracking interfaces and shapes. The advantage of the level set method is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects (this is called the "Eulerian approach"). Also, the level set method makes it very easy to follow shapes that change topology, for example when a shape splits in two, develops holes, or the reverse of these operations. All these make the level set method a great tool for modeling time-varying objects, like inflation of an airbag, or a drop of oil floating in water.

Level set function

In two dimensions, the level set method amounts to representing a closed curve Gamma in the plane as the zero level set of a two-dimensional auxiliary function varphi, :Gamma = {(x, y)|, varphi(x, y) = 0 }, ,and then manipulating Gamma "implicitly", through the function varphi. This function is called a "level set function". varphi is assumed to take positive values inside the region delimited by the curve Gamma and negative values outside.

The picture above illustrates several important ideas about the level set method. In the upper-left corner we see a shape, that is, a bounded region with a well-behaved boundary. Below it, the red surface is the graph of a level set function varphi determining this shape, and the flat blue region represents the x-y plane. The boundary of the shape is then the zero level set of varphi, while the shape itself is the set of points in the plane for which varphi is positive or zero.

In the top row we see a shape changing topology by splitting in two. It would be quite hard to describe this transformation numerically by parameterizing the boundary of the shape and following its evolution. One would need an algorithm able to detect the moment the shape splits in two, and then construct parameterizations for the two newly obtained curves. On the other hand, if we look at the bottom row, we see that the level set function merely got translated downward. We see that it is much easier to work with a shape through its level set function than with the shape directly, when we need to watch out for all the possible deformations the shape might undergo.

The level set equation

If the zero level set moves in the normal direction to itself with a speed "v", this movement can be represented by means of a so-called "Hamilton-Jacobi equation" for the level set function: :varphi_t = v| abla varphi|.This is a partial differential equation, and can be solved numerically, for example by using finite differences on a Cartesian grid.

History

The level set method was developed in the 1980s by the American mathematicians Stanley Osher and James Sethian. It has become popular in many disciplines, such as image processing, computer graphics, computational geometry, optimization, and computational fluid dynamics.

A number of level set data structures have been developed to facilitate the use of the level set method in computer applications.

References


* Osher, S. & Sethian, J. A. (1988) "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations". Journal of Computation Physics, vol. 79, pages 12–49.
* Osher, Stanley J. & Fedkiw, Ronald P. (2002) "Level Set Methods and Dynamic Implicit Surfaces". Springer-Verlag. ISBN 0-387-95482-1.
* Sethian, James A. (1999) "Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science" (2nd ed.). Cambridge University Press. ISBN 0-521-64557-3.

External links

* See Ronald Fedkiw's [http://graphics.stanford.edu/~fedkiw/ academic web page] for many stunning pictures and animations showing how the level set method can be used to model real life phenomena, like fire, water, cloth, fracturing materials, etc.
* [http://vivienmallet.net/fronts/ Multivac] is a C++ library for front tracking in 2D with level set methods.
* James Sethian's [http://math.berkeley.edu/~sethian/ web page] on level set method.
* Stanley Osher's [http://www.math.ucla.edu/~sjo/ homepage] .


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Level set (data structures) — In computer science a level set data structure is designed to represent discretely sampled dynamic level sets functions.A common use of this form of data structure is in efficient image rendering.Chronological developmentsThe powerful level set… …   Wikipedia

  • Level set — In mathematics, a level set of a real valued function f of n variables is a set of the form: { ( x 1,..., x n ) | f ( x 1,..., x n ) = c }where c is a constant. That is, it is the set where the function takes on a given constant value. For… …   Wikipedia

  • Method of lines — The method of lines (MOL, NMOL, NUMOL) (Schiesser, 1991; Hamdi, et al., 2007; Schiesser, 2009 ) is a technique for solving partial differential equations (PDEs) in which all but one dimension is discretized. MOL allows standard, general purpose… …   Wikipedia

  • Multigrid method — Multigrid (MG) methods in numerical analysis are a group of algorithms for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in (but not… …   Wikipedia

  • Spectral method — Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain Dynamical Systems, often involving the use of the Fast Fourier Transform. Where applicable, spectral methods have… …   Wikipedia

  • Crank–Nicolson method — In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations.[1] It is a second order method in time, implicit in time, and is numerically …   Wikipedia

  • Collocation method — In mathematics, a collocation method is a method for the numerical solution of ordinary differential equations, partial differential equations and integral equations. The idea is to choose a finite dimensional space of candidate solutions… …   Wikipedia

  • Discontinuous Galerkin method — Discontinuous Galerkin methods (DG methods) in mathematics form a class of numerical methods for solving partial differential equations. They combine features of the finite element and the finite volume framework and have been successfully… …   Wikipedia

  • Schwarz alternating method — In mathematics, the Schwarz alternating method, named after Hermann Schwarz, is an iterative method to find the solution of a partial differential equations on a domain which is the union of two overlapping subdomains, by solving the equation on… …   Wikipedia

  • Neumann–Dirichlet method — In mathematics, the Neumann–Dirichlet method is a domain decomposition preconditioner which involves solving Neumann boundary value problem on one subdomain and Dirichlet boundary value problem on another, adjacent across the interface between… …   Wikipedia

Share the article and excerpts

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