Did you know that in 2008 a mathematician won an Academy Award? Do you know how to model realistic hair for animation movies or a bomb deflagrating for an action movie? Or you simply need some effective active contour segmentation method? All these questions have in common an effective, yet intuitive, mathematical framework: level set methods. I came to know them through my own X-ray tomography research project, which gives you a hint of how wide and inclusive such methods are. Yesterday I gave an introductory and informal talk at the Students' Seminar about them. This post comes as an integration to the slides that you may download from this page.
Let's start from defining what an interface is. I could not find a rigorous definition, but the concept is very intuitive. It is a "boundary" which clearly splits the space in two subsets ("inside" and "outside"). You can imagine a closed (even self-intersecting) curve on the plane, for instance. Or the surface of a ball or a torus in 
. From now on, let's work with planar interfaces, for better visual intuition. However, everything I will discuss here can be extended to any 
. Now, imagine we are working with a dynamic interface, meaning that our closed curve, for instance, changes in time.
Rigorously speaking, we are given an initial curve, 
and a velocity field 
which we assume is normal to the curve at any instant 
. We would like to determine and parametrise the evolution of the curve, that is 
. One intuitive idea is the following: let's choose some ordered points on our curve 
(Fig. A), let's follow their evolution (
will tell us where they are going) and let's complete the curve between any subsequent points 
and 
by interpolation. However, it may happen that our curve will split under the action of and Fig. B shows how our method would fail, because we told our algorithm to connect 
with 
and with .
How could we explain to our algorithms when the curve splits or merges? It's hard, especially since we are searching for a general method. This is where level set methods come to the rescue.
The idea is very intuitive: what if we would add one extra-dimension (time) and "record" the evolution with a surface? For instance, if our curve is a disc expanding, one candidate surface could be a truncated cone. If our disc would evolve in a "8-shape" and then split, one candidate surface would be some sort of 3-dimensional "Y". In other words, we are looking for a function 
such that:
Here I denote the "inside" region at the time by 
. At any time, the zero level set of 
will detect the interface. In addition, its sign will detect the inside and outside regions. Now, observe that from the previous equation:
By applying the chain rule, we get 
. We assumed that our velocity field was orthogonal to the interface at any instant. In other words,
.
Hence, we can write the following evolution equation:
.
This, in addition to the given initial condition , will define and consequently the interface at any time. Suddenly we are in front of a PDE problem, for which there are many well-developed theoretical and numerical tools. Also, this approach handles perfectly topological changes, such as splitting and merging. Plus, it makes it really easy to compute geometric quantities as the curvature of the interface (simply differentiate ).
This new framework was introduced in 1987 by Stanley Osher and James Sethian. Since then, it has been a thriving topic of research: just know that their seminal paper to date has been cited more than 11 500 times! Level set methods have been applied to an incredible variety of problems and settings: medical imaging, computer vision, image denoising, active contour segmentation, scattering, obstacle detection, and more. It has been widely explored both theoretically and numerically. One its richest areas of application is computer graphics. One of Osher's students, Ron Fedkiw, now full professor at Stanford, won an Academy Scientific and Technical Award in 2008. Fedkiw is a consultant for Industrial Light and Magic, a big name in the special effects industry. He worked on blockbusters as Terminator III, Star Wars Episode III, the Pirates of the Caribbean's saga and some Harry Potter movies. Level set methods are widely used in fluid, fire, hair simulations in animation movies. Think of water, with all his splashes (=topological changes): this framework works very well. One drawback is that this approach does not conserve some physical quantities as the volume. However, there are nowadays many tricks to work around this. For instance, there are hybrid methods that mix level set and volume tracking methods or sometime rendering techniques that fill up for the missing physical properties. You can see many animations at the PhysBAM project page.
If you got curios, I include a selection of references:
Osher – Paragios, “Geometric Level Set Methods in Imaging, Vision and Graphics”, Springer 2003.
Osher – Fedkiw, “Level Set Methods and Dynamic Implicit Surfaces”, Springer 2003.
Links:
http://step.polymtl.ca/~rv101/levelset/ explanations
http://www.ams.org/notices/201005/rtx100500614p.pdf
http://physbam.stanford.edu/~fedkiw/papers/stanford2003-04.pdf
