Time-Dependent Level Set Methods
Tracking a moving boundary
-
Suppose you are given an interface separating one region from
another, and a speed F that tells you how to move each point of the
interface. In the figure below, a black curve separates a dark blue
inside from a light blue outside, and at each point of the
black curve the speed F is given. This speed can depend on a variety
of physical effects. For example
- Imagine that the dark blue
is ice and the light blue is water. Then the boundary can melt
as the ice shrinks, or grow as the ice freezes; the speed
then depends on the temperature jump between the two.
- Imagine that the dark blue is honey and the light blue is tea. Then the boundary moves as the heavy fluid falls into to the light one, and the speed depends on gravity, the ratio of the fluid densities, and the surface tension between the two.
Most numerical techniques rely on markers, which try to track the motion of the boundary by breaking it up into buoys that are connected by pieces of rope. The idea is to move each buoy under the speed F, and rely on the connecting ropes to keep things straight. The hope is that more buoys will make the answer more accurate.
Unfortunately, things get pretty dicey if the buoys try to cross over themselves, or if the shape tries to break into two; in these cases, it is very hard to keep the connecting ropes organized. In three dimensions, following a surface like a breaking ocean wave is particular tough. - Imagine that the dark blue
is ice and the light blue is water. Then the boundary can melt
as the ice shrinks, or grow as the ice freezes; the speed
then depends on the temperature jump between the two.
The level set approach
-
Rather than follow the interface itself, the level set approach
instead takes the original curve (the red one on the left below),
and builds it into a surface. That cone-shaped surface, which is
shown in blue-green on the right below, has a great property; it intersects the
xy plane exactly where the curve sits.
The blue-green surface on the right below is called the
level set function, because it accepts as input any point in the
plane and hands back its height as output.
The red front is called the zero level set, because
it is the collection of all points that are at height zero.
The original front The level set function Front lies in xy plane Front is intersection of Surface and xy plane
Another way to see why this is called a "level set surface" is to imagine a saw that can cut a slice of the surface and then drop it onto the xy plane. However, the slice has to be perfectly level.- If the saw cuts the blue-green level set surface at height zero above the xy plane, the ring that will drop to the xy plane will be the original red front.
- If the saw cuts at some other height, a different ring will drop down, producing one of the blue-green curves instead.
How do you move the front?
-
The idea is that instead of moving the red front, which
can do all sorts of weird things, one might try and instead move the
surface on the right. In other words, the level set function
expands, rises, falls, and does all the work. To
find out where the front is, get out the saw and cut the surface
at zero height.
(290K)
Red curve is zero level set
Why is this a good idea?
-
So far, it might seem crazy to take the problem of a moving
curve and trade it in for a moving surface.
The reason this is a good idea lies in taking a good look at the
surface on the right. It will always be "nice"; the red
front can get wildly contorted, but our blue level set function
is well-behaved. All the complicated problems of breaking
and merging are easily handled. Better yet,
everything works for three dimensional surfaces
with no change..
(260K)
Initial front is two curves that join together as they grow
An equally important advantage is that it is easy to build accurate numerical schemes to approximate the equations of motion. That's because rather than track buoys around, which might end up colliding, one can instead stand on the xy plane and compute the answer. Using terminology from a completely different language, marker particle methods are man-to-man coverage, while level set methods are a zone defense. All together, the trick of embedding the front in a higher dimensional function is well worth the added cost (in fact, with some work, that cost be made the same as that of marker techniques).
Narrow Band Methods: Computational Adaptivity
- As described above, the level method requires one to track all the level set sets, not just the zero level set corresponding to the interface. A computationally adaptive version, narrow band method . may be easily built. Rather than track all the level sets, we focus only on those grid points which are located in a narrow band around the zero level set. The value of the level set function is updated only at these grid points, thus reducing the computational labor to the dimension of the interface times a constant corresponding to the width of the narrow band. Thus, the narrow band level set method has the same computational complexity as string and cell methods, while maintaining of the singular advantages of topological changes, correct weak solutions as corners and cusps, high accuracy, and straightforward extension to three dimensions.
Fast Marching Methods
-
The above technique can handle almost anything; fronts that move
forwards and backwards, sensitively depend on curvature, etc.
In the special case of a front that always moves in one
direction; a extremely fast version known as the
fast marching method is possible. Here's a sketch of
how it works:
The stationary level set formulation
-
In the general level set technique above, we build an initial surface
that intersects the xy plane where the front is located, and
then move the surface itself. If we want to find the front, we just
get out our saw and cut along the xy plane.
Suppose we could miraculously build an initial surface with the property that if you cut it at a height T, then you get the position of the front at time T?. If we could do this, then we wouldn't have to move this surface at all!. All we would have to do is slice it at the level set T to get the position at time T. We call this a stationary level set method because we don't have to move the level set function once we build it.
Original Green front at T=0 The stationary level set function Front moves outwards Slicing surface at time T gives solution at time T
The fast marching method
-
How can this stationary surface be constructed?
As a motivation, imagine scaffolding being erected around a
house! One stands on one of the boards, puts a board above the head,
and then moves to another board at the same level and put a board
one level up. Once all the boards are placed at a given level, one then
climbs up to the next level set repeat the process.
The thing to remember is that the scaffolding is built from the ground up;
each level must be completed before the next is begun.
The fast marching method imitates this process. Given the initial curve (shown in red), stand on the lowest spot (which would be any point on the curve), and build a little bit of the surface that corresponds to the front moving with the speed F. Repeat the process over and over, always standing on the lowest spot of the scaffold, and building that little bit of the surface. When this process ends, the entire surface has been built.
(354K)
Construction of stationary level set solution Green squares show next level to be built
The speed from this method comes from figuring out in what order to build the scaffolding; fortunately, there are lots of fast sorting algorithms that can do this job quickly.
Details
Level set methods
- The level method tracks the motion of an interface by embedding the interface as the zero level set of the signed distance function. The motion of the interface is matched with the zero level set of the level set function, and the resulting initial value partial differential equation for the evolution of the level set function resembles a Hamilton-Jacobi equation. In this setting, curvatures and normals may be easily evaluated, topological changes occur in a natural manner, and the technique extends trivially to three dimensions. This equation is solved using entropy-satisfying schemes borrowed from the numerical solution of hyperbolic conservation laws which produce the correct viscosity solution. For details, see the Osher-Sethian paper listed below.
Fast marching level set methods
- The fast marching level set method solves the general static Hamilton-Jacobi equation, which applies in the case of a convex, non-negative speed function. Starting with an initial position for the front, the method systematically marches the front outwards one grid point at a time, relying on entropy-satisfying schemes to produce the correct viscosity solution. The main idea is exploit a fast heapsort technique to systematically locate the proper grid point to update, so that one need never backtrack over previously evaluated grid points. The resulting technique sweeps through a grid of N total points in N log N steps to obtain the evolving time position of the front as it propagates through the grid. For details, see the paper listed below.
References
For Fast Marching Methods: Sethian, J.A., A Marching Level Set Method for Monotonically Advancing Fronts, Proc. Nat. Acad. Sci., 93, 4, 1996.
J.A. Sethian
sethian@math.berkeley.edu You are visitor number to this page.