Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science (2nd edition)

Citation

Andrew, A.M. (2000), "Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science (2nd edition)", Kybernetes, Vol. 29 No. 2, pp. 239-248. https://doi.org/10.1108/k.2000.29.2.239.3

The two rather enigmatic terms appearing in the main title refer to computational techniques for modelling phenomena at interfaces, such as waves on water. The author of this work is ideally qualified to deal with the topic, since Level Set Methods were introduced in a paper in 1988, of which he was a joint author, and Fast Marching Methods were his own innovation in 1996. In the book he develops the topic from first principles, and his expository style is admirable (not, I have to admit, that I have worked through it). The development of the theory is interspersed with helpful comments about the wider significance, and with references to publications dealing with the latest developments.

Of the two techniques, it appears that fast marching methods often allow, as might be expected, solutions that are less time‐consuming, but they do not entirely supersede level set methods which have wider applicability. It is acknowledged that there are other methods besides these that can be considered for problems of the kind and, while the author is careful not to be dogmatic about the superiority of his favoured techniques, he makes it pretty clear that one of them will almost always be the method of choice. Older methods operate by placing a series of markers along the evolving boundary (if in two dimensions) or over the boundary surface (in three dimensions), and then letting these markers advance as the simulation runs.

The trouble with such methods is summed up in the author’s Web site (see below) as follows: “Such schemes usually go unstable and blow up as the curvature builds around a cusp, since small errors in the position produce large errors in the determination of the curvature.” The methods described in this book use a different approach that bypasses the difficulty and gives robust and accurate and efficient operation. The methods handle problems in which the separating interfaces develop sharp corners and cusps, and become very intricate. The methods are even applicable to situations in which physical events on each side of the interface both drive its variations and are themselves affected by its proximity and properties. Such situations include combustion and flame propagation, crystal growth and dendritic solidification, among others.

Impressive though all this is (and one of the attractive features of the author’s style is his infectious enthusiasm) there is much more to come since the techniques find important applications in apparently unrelated fields. One of these, likely to be useful as a part of other kinds of numerical simulation, is to the forming of rectangular grids of points around complex body shapes. Associated with this is the means of drawing geodesics, or shortest paths, on arbitrary three‐dimensional surfaces, and of planning robot movements through a maze.

The methods also find application in a remarkable number of areas related to image processing, including the extraction of 3D shape from shading, and the extraction of images from noise. These have been applied in medical imaging. The cleaning‐up of noisy images is illustrated in its application to character recognition, where the new methods allow noise reduction with much less loss of definition than in older methods performing neighbourhood operations on pixels. Essentially, the picture is treated as a 3D shape with height corresponding to blackness, and then the shape is made to evolve like a fluid with surface tension, whereupon character images coalesce into sharply defined smooth versions.

The relevance to character recognition is not restricted to this cleaning‐up process. Another application is illustrated by reference to the classical task of recognition of sloppy hand‐blocked characters. The new techniques can be used as an adjunct to a recognition scheme, so that when submitted images are rejected as unrecognisable, one of them is applied to modify the image in ways that often allow it to be correctly classified when resubmitted.

An application to aircraft navigation is also described, having a bearing on the optimal course for an aircraft finding itself uncomfortably close to another, given that the action that will be taken by the other craft is not precisely known. Another application is to the interpretation of seismic data in geophysics.

Apart from these wide‐ranging areas of application, the methods have also proved their worth in what may be considered closer to their home ground, namely the development of microelectronic components. The various processes of deposition and etching are all subject to uncertainty as to just what is etched or exactly where the deposits form. At least, that has been so in the past, so that development has involved numerous trials of actual fabrication. The new computing methods now allow the processes to be modelled in computer simulations, and the last chapter of the book treats this valuable area of application.

The author very generously gives his e‐mail address and invites correspondence. He also gives the address of his Web site as: <http://math.berkeley.edu/∼sethian/level_set.html> The Web site is a magnificent piece of work, and really puts the user in an interactive learning environment. For example, the user is invited to download pieces of movie animation that illustrate aspects of the theory. The movies can be made to run through from start to finish, or can be taken back or forward to any point in their run‐time by a slider that can be dragged by the mouse pointer. There are also “Java applets” that run as interactive programs and that, for example, allow the user to set up an arbitrary shape to be operated on by the simulation method, or to create his own images to be cleaned‐up of noise.

The Web site also gives a reference, and abstract, to a popular account of the techniques in the American Scientist for May‐June 1997, Vol. 85 No. 3, as well as many other references, some of them to papers that can be downloaded in full. The Web site gives a valuable and delightful introduction and a feeling for the capabilities, but of course the book has to be consulted in order to follow the mathematics in detail and to implement the methods, as specialists in quite a number of areas will want to do.