The Level Set Formulation: An Initial Value PDE

The central idea in what has become known as level set methods is take the previous work on curvature flow, links between evolving interfaces and hyperbolic conservation laws, and the use of numerical shock schemes to track interfaces which remain a graph, and use an implicit description of interface to extend these ideas to evolving fronts which do not remain graphs. This lies at the core of the Osher-Sethian level set approach: it casts the problem in one higher dimension. That is, a curve propagating in the plane is replaced by the problem of a two-dimensional surface evolving in three dimensions. More precisely, given a curve gamma(t) propagating in its normal direction with speed F, a level set function phi(x,y,t) is introduced such that the zero level set phi =0 is identified at any time t with the evolving curve gamma(t). The equation of motion for the evolving level set function then becomes

phi_t + F | nabla phi | = 0

You are currently in the topic outlined in red.

Click on navigable flow chart to go to new topic

click on any text to go to a new topic.

Annotated References:

By relying on this embedding, discussed and exploited in Ref. 1 below, topological changes in the evolving front are handled naturally. In addition, it allows one to calculate geometric quantities such as the normal direction and the curvature by capitalizing on the smoothness of the level set function in a neighborhood of th zero level set of interest. Explicit first and second order schemes for advancing this implicit representation of evolving interfaces are described in Ref. 1, and results are given of using this embedding on several examples, including those involving curvature flow and three dimensions. Ref. 2 discusses how the various aspects come together, and applies the results to problems in geometry and singularity development.

Because the problem has been moved to one higher dimension, it becomes computational expensive. This limitation is removed by the development of the Narrow Band Methods , which focus computational labor on a thin region around the level set representing the interface itself; this is the efficient way to implement level set methods. In the special case where the speed F of the evolving front is always of the same sign, a far faster technique based on a stationary formulation, is possible, known as Fast Marching Methods .

New Book and Resource on Level Set and Fast Marching Methods



References:

1. Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton--Jacobi Formulations : Osher, S., and Sethian, J.A. Journal of Computational Physics, 79, pp. 12-49, 1988.

   Abstract

   We devise new numerical algorithms, called PSC algorithms, for following fronts propagating with curvature-dependent speed. The speed may be an arbitrary function of curvature, and the front can also be passively advected by an underlying flow. These algorithms approximate the equations of motion, which resemble Hamilton-Jacobi equations with parabolic right-hand-sides, by using techniques from the hyperbolic conservation laws. Non-oscillatory schemes of various orders of accuracy are used to solve the equations, providing methods that accurately capture the formation of sharp gradients and cusps in the moving fronts. The algorithms handle topological merging and breaking naturally, work in any number of space dimensions, and do not require that the moving surface be written as a function. The methods can be also used for more general Hamilton-Jacobi-type problems. We demonstrate our algorithms by computing the solution to a variety of surface motion problems.

   Download publications

   Recent Numerical Algorithms for Hypersurfaces Moving with Curvature-dependent Speed: Hamilton-Jacobi Equations and Conservation Laws : Sethian, J.A., Journal of Differential Geometry, 31, pp. 131--161, 1990.

   Abstract

   In many physical problems, interfaces move with a speed that depends on the local curvature. Some common examples are flame propagation, crystal growth, and oil-water boundaries. We idealize the front as a closed, non-intersecting, initial hypersurface flowing along its gradient field with a speed that depends on the curvature. Because explicit solutions seldom exist, numerical approximations are often used. In this paper, we review some recent work on algorithms for attacking these problems. We show that algorithms based on direct parameterizations of the moving front face considerable difficulties. This is because such algorithms adhere to local properties of the solution, rather than the global structure. Conversely, the global properties of the motion can be captured by embedding the surface in a higher-dimensional function. In this setting, the equations of motion can be solved using numerical techniques borrowed from hyperbolic conservation laws. We apply the algorithms to a variety of complicated shapes, showing corner formation and breaking and merging, and conclude with a study of a dumbbell in #R sup 3# moving under its mean curvature. We follow the collapsing dumbbell as the handle pinches off, a singularity develops, and the front breaks into two separate surfaces.

   Download publications