Last update: August 2, 2004.

BACK

Publications by Prof. James Albert Sethian

• Level Set Methods and Fast Marching Methods, 1999.
• Computing geodesic paths on manifolds, by R.Kimmel & J.A.Sethian, 1998.
• A fast marching level set method for monotonically advancing fronts, by J.A.Sethian, 1996.
• An O(N log N) algorithm for shape modeling, by R. Malladi and J. A. Sethian, 1996.
• Level set methods: Evolving interfaces in geometry, fluid mechanics, computer vision, and materials science, by J.A. Sethian, 1996.

BibTeX references.

Web link:

• http://math.berkeley.edu/~sethian/Publications/publications.html

The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M log M) steps, where M is the total number of grid points. In this paper we extend the Fast Marching Method to triangulated domains with the same computational complexity. As an application, we provide an optimal time algorithm for computing the geodesic distances and thereby extracting shortest paths on triangulated manifolds.

A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.

Advantages fo the Level-set method:

1. Although phi(x,t) remains a function, the level surface phi = 0 corresponding to the propagating hypersurface may change topology, as well as form sharp corners as phi evolves.
2. A discrete grid can be used together with finite differences to devise a numercial scheme to approximate the solution.
3. Intrinsic geometric properties of the front are easily determined from the level set function phi, such as the normal vector to the hypersurface, and the curvature of each level set.
4. Formulation carries along directly to the third dimension.

1. is an advantage with respect to classical Lagrangian methods (particle-based).

2. states that the method easily translates to lattices, since it can be casted as set operations (over finite domains).

3. is not a disadvantage...

A fast marching level set method

The Eikonal equation states that the gradient of arrival time surface is inversely proportional to the speed of the front.

An approximation to the gradient is introduced: finite differences are performed, using an upwind scheme (to follow wavefront motion).

"The key is to select which grid points in the narrow band to update."

"each minimum trial value begins an application of Huygen's principle, and the expanding wave front touches and updates all others."

In 2D, it is proposed to use the 4 direct neighbors to approximate the gradient. In the narrow band, it is implicit that T (or phi) has been pre-computed; that is one need an hypersurface, limited by the domain of the narrow band (and possibly on a domain a bit larger, to avoid re-computations at eact time step), before taking differences. Then, the differences are taken, according to the proposed upwind scheme, using the previously mentioned 4 direct ngbs. This computation, is used in turn to set values of T ahead (at new "alive" points).

It is said that, initially the hypersurface values are computed via a signed distance function. This is done in the domain of the initial narrow band. Hence, it has to be re-computed each time the narrow band changes (is moved together with the front).

Sorting, along the front, is performed with heapsort together wiht pointers to the grid loci. The maintenance of the heapsort queue in the narrow band is of complexity O(log N), where N is the number of discrete cells in the band.

Speed function

Interestingly, the speed function, F, is used to introduce diffusion to the otherwise reactive wave propagation. F can also be made a function of the propagating medium properties (as the classical model of wave propagation suggests).

However, it seems that the diffusion effects, introduced in the numerical approximation of the gradient to the hypersurface (front), are unavoidable, and pure reaction is difficult to model precisely with this technique. Fig.7, where F is supposedly equal to unity (hence modeling a pure reaction propagation) does not produce shar corners immediately, a sign of unwanted diffusion effects.

We present a shape-recovery technique in two dimensions and three dimensions with specific applications in modeling anatomical shapes from medical images. This algorithm models extremely corrugated structures like the brain, is topologically adaptable, and runs in O(N log N) time, where N is the total number of points in the domain. Our technique is based on a level set shape-recovery scheme recently introduced by the authors and the fast marching method for computing solutions to static Hamilton-Jacobi equations.

Keywords: Hamilton-Jacobi equation / Eikonal equation / shape recovery / medical image analysis / level sets.

This book is an introduction to level set methods, which are numerical techniques for analyzing and computing interface motion in a host of settings. The numerical techniques can be used to track three-dimensional complex fronts that can develop sharp corners and change topology as they evolve. The text includes applications from physics, chemistry, fluid mechanics, combustion, image processing, material science, seismology, fabrication of microelectronic components, computer vision and control theory. The book is intended for mathematicians, applied scientists, practicing engineers, computer graphic artists, and anyone interested in the evolution of boundaries and interfaces.

The text is an equal blend of theory, implementations, and applications areas, including detailed descriptions of the appropriate numerical schemes.

Part I: Equations of Motion for Moving Interfaces

1. Stability of Fronts, Total variation, Role of curvature and Entropy conditions
2. The Time-Dependent Level Set formulation
   • Topological Change, Curvature Terms, and Multidimensionality
3. The Stationary Level Set formulation
   • Conversion to Static Hamilton-Jacobi Equation

Part II: Approximation Schemes for Level Set Equations

1. Traditional Techniques:
   • Marker/String Methods
   • Volume-of-Fluid/Cell Methods
2. Hyperbolic Conservation Laws:
   • The Wave Equation, Characteristics, Schocks, and Entropy Conditions
   • Weak Solutions, Flux Conditions, and Riemann Problems
3. Schemes for the Level Set Equation
   • Convex Schemes: First and Second Order
   • Non-Convex Schemes: First and Second Order
   • Boundary Conditions and Initializations
4. A Hierarchy of Fast Level Set Methods
   • Parallel Algorithms
   • Adaptive Mesh Methods
   • Fast Narrow Band Methods
5. Extensions to the Basic Method
   • Masking, Sources, and Sinks
   • Discontinuous Speed Functions and Sub-grid Resolution
   • Multiple Interfaces and Triple Points

Part III: Viscosity Solutions, Hamilton-Jacobi Equations, & Fast Marching Methods

1. Viscosity Solutions of Hamilton-Jacobi Equations
2. Fast Marching Methods
3. How to solve the Eikonal Equation on a 200x200x200 grid in under 30 seconds

Part IV: Applications

1. Motion of Curves and Surfaces under Curvature
2. Sintering of Materials
3. Grid Generation: Two- and Three-Dimensional Body-Fitted Grids
4. Image Enhancement and Noise Removal
5. Combustion: Flame Stability under Exothermic and Vortical Effects
6. Crystal Growth and Dendritic Solidification
7. Two-Fluid Flow, Motions of Thermals, Role of Surface Tension
8. Shape Detection and Recovery in Medical Imaging
9. Shape Recognition: Optical Character Recognition and Neural Nets
10. Shape Offsetting in CAD
11. Shape-from-Shading in Computer Vision
12. Photolithography Development in Semi-Conductor Manufacturing
13. Computing Optimal Paths on Networks
14. Construction of Geodesics on Surfaces
15. Seimsic Travel Times: Computing First Arrival Times
16. Robotic Navigation with Constraints
17. Etching and Deposition in Semi-conductor Manufacturing

Page created & maintained by Frederic Leymarie, 1998-2004.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu