Level set methods and Fast Marching Methods have been used in a variety of aspects of imaging and medical imaging. The basic idea is as follows; starting with a raw image, obtained from a scanning device, how does one segment a shape, which is the process of detecting, extracting, and representing a desired shape inside the image.

The central perspective of appling level set methods to image segmentation comes from the approach of adopting the methodology of snakes to grow an interface from a seed point onto the selected boundary. This strategy was proposed by Malladi, Sethian, and Vemuri (Ref. 1 below) and Caselles, Catte, Coll, and Dibos in (Ref. 2). Malladi makes his approach fast by coupling it to Narrow Band Methods in Ref. 5, and couples the approach to Fast Marching Methods in Ref. 8. In more detail, using a level set method, Ref. 1 synthesizes a speed function F from the image gradient in order to extract the underlying boundary and realized that a speed F of the form

F = 1./(1 + | nabla I | )
where I is the image gradient, would slow down and stop where the image gradient was large, indicating that boundary was reached. The interested reader is referred to a large amount of movies, interactive java applets, and details of interface-based medical image segmentation, showing how these techniques work.

A particular fast version of these techniques, given in the references below, uses the Fast Marching Method to perform an initial segmentation which produces a result close to the desired answer; further refinement then comes from resorting to the original algorithm.

Once these segmentation problems have been addressed, an additional issue is to perform some preprocessing image analysis which can enhance and denoise the image, creating an image which is more amenable to the above segmentation algorithm. Here again, considerable work has been done using partial differential equations based techniques. Some work which couples this level set enhancement/denoising ideas may be found in the references below.



Annotated References:

• Ref. 1 is the Malladi, Sethian, and Vemuri reference coupling level set methods to shape segmentation.
• Ref. 2 are the Caselles, Catte, Coll and Dibos references.
• Ref. 3 and 4 expand on the Malladi approach.
• Ref. 5 couples the Narrow Band level set method to the underlying partial differential equation.
• Ref. 6 introduces the min/max flow, which is a highly efficient technique for image denoising. It has the virtue that is a geometrical hierarchically-based scheme, requires only one parameter, and automatically stops.
• Ref. 7 shows how to use the Fast Marching Method to perform highly efficient shape segmentation.
• Ref. 8 combines the various techniques.
• Ref. 9 shows how all the elements may be assembled to provide a unified approach to enhancement and segmentation.
• Ref. 10 and 11 gives further application of the Min/Max flow.
• Ref. 12 is a review of the previous material.
• Ref. 13 applies these techniques to cytology.
• Refs. 14 and 15 extend some of the geometric-based image processing ideas to color and multichannel images.
• Refs. 16, 17, and 18 continue the work, with applications to medical imaging.

Example: Segmentation of arterial structure using interface technique. (See Reference 1 below).

Movies, interactive java applets, and details of medical image segmentation.

Movies, interactive java applets, and details of image denoising.


New Book and Resource on Level Set and Fast Marching Methods

References:

1. A Topology Independent Shape Modeling Scheme : Malladi, R., Sethian, J.A., and Vemuri, B.C., Proceedings of SPIE Conference on Geometric Methods in Computer Vision II, Vol. 2031, San Diego, California, pp. 246--258, July 1993.

   Abstract

   Developing shape models is an important aspect of computer vision research. Geometric and differential properties of the surface can be computed from shape models. They also aid the tasks of object representation and recognition.In this paper, we present an innovative new approach fpr shape modeling which, while retaining important features of the existing methods, overcomes most of their limitations. Our technique can be applied to model arbitrarily complex shapes with protrusions, and to siutations where no a priori assumption about the object's topology can be made. A single instance of our model, when presented with an image having more one object of interest, has the ability to split freely to represent each object. Our method is based on the level set ideas developed by Osher and Sethian to follow propagating solid/liquid interfaces with curvature-dependent speeds. The interface is a closed, nonintersecting hypersurface flowing along its gradient fields with constant speed or a speed that depends on curvature. We move the interface by solving a "Hamilton-Jacobi" type equation written for a function in which the interface is particular level set. A speed function synthesized from the image is used to stop the interface in the vicinity of the object boundaries. The resulting equations of motion are solved by numerical techniques borrowed from the technology of hyperbolic conservation laws. An added advantage of this scheme is that can easily be extended to any number of space dimensions. The efficacy of the scheme is demonstrated with numerical experiements on synthesized images and noisy medical images.

   Download publications



2. A Geometric Model for Active Contours in Image Processing Recovery Caselles, V., Catte, F., Coll, T., and Dibos, F., Numer. Math., 66, 1993. and Automatic contours detection in image processing, F. Dibos, V. Caselles, T. Coll, and F. Catte, Proceedings of the 1992 First World Congress of Nonlinear Analysts, Tampa, V. Lakshmikantham, Verlag Walter de Gruyter GmbH & Co., 1995.



3. Evolutionary Fronts for Topology-Independent Shape Modeling Recovery Malladi, R., Sethian, J.A., and Vemuri, B.C., in Proceedings of the Third European Conference on Computer Vision, LNCS Vol. 800, pp. 3--13, Stockholm, Sweden, May 1994.

   Abstract

   This paper presents a novel framework for shape modeling and shape recovery based on ideas developed by Osher \& Sethian for interface motion. In this framework, shapes are represented by propagating fronts, whose motiois governed by a ``Hamilton-Jacobi'' type equation. This equation is written for a function in which the interface is a particular level set. Unknown shapes are modeled by making the front adhere to the object boundary of interest under the influence of a synthesized halting criterion. The resulting equation of motion is solved using a narrow-band algorithm designed for rapid front advancement. Our techniques can be applied to model arbitrarily complex shapes, which include shapes with significant protrusions, and to situations where no {\it a priori} assumptioabout the object's topology can be made. We demonstrate the scheme via examples of shape recovery in 2D and 3D from synthetic and low contrast medical image data.

   Download publications

   
   

4. Shape Modeling with Front Propagation: A Level Set Approach : Malladi, R., Sethian, J.A., and Vemuri, B.C., IEEE Trans. on Pattern Analysis and Machine Intelligence, 17, 2, pp. 158-175, 1995

   Abstract

   Shape modeling is an important constituent of computer vision as well as computer graphics research. Shape models aid the tasks of object representation and recognition. This paper presents a new approach to shape modeling which retains some of the attractive features of existing methods, and overcomes some of their limitations. Our technique can be applied to model arbitrarily complex shapes, which include shapes with significant protrusions, and to situations where no {\it a priori} assumption about the object's topology is made. A single instance of our model, when presented with an image having more than one object of interest, has the ability to split freely to represent each object. This method is based on the ideas developed by Osher and Sethian to model propagating solid/liquid interfaces with curvature-dependent speeds. The interface (front) is a closed, nonintersecting, hypersurface flowing along its gradient field with constant speed or a speed that depends on the curvature. It is moved by solving a ``Hamilton-Jacobi'' type equation written for a function in which the interface is a particular level set. A speed term synthesized from the image is used to stop the interface in the vicinity of object boundaries. The resulting equation of motion is solved by employing entropy-satisfying upwind finite difference schemes. We present a variety of ways of computing evolving front, including narrow bands, reinitializations, and different stopping criteria. The efficacy of the scheme is demonstrated with numerical experiments on low contrast medical images.

   Download publications

   
   
5. A Fast Level Set based Algorithm for Topology-Independent Shape Modeling : Malladi, R., Sethian, J.A., and Vemuri, B.C., Journal Mathematical Imaging and Vision, 6, 2/3, pp. 269--290, 1996.

   Abstract

   Shape modeling is an important constituent of computer vision as well as computer graphics research. Shape models aid the tasks of object representation and recognition. This paper presents a new approach to shape modeling which retains some of the attractive features of existing methods, and overcomes some of their limitations. Our technique can be applied to model arbitrarily complex shapes, which include shapes with significant protrusions, and to situations where no {\it a priori} assumption about the object's topology is made. A single instance of our model, when presented with an image having more than one object of interest, has the ability to split freely to represent each object. This method is based on the ideas developed by Osher and Sethian to model propagating solid/liquid interfaces with curvature-dependent speeds. The interface (front) is a closed, nonintersecting, hypersurface flowing along its gradient field with constant speed or a speed that depends on the curvature. It is moved by solving a ``Hamilton-Jacobi'' type equation written for a function in which the interface is a particular level set. A speed term synthesized from the image is used to stop the interface in the vicinity of object boundaries. The resulting equation of motion is solved by employing entropy-satisfying upwind finite difference schemes. We also introduce a new algorithm for rapid advancement of the front using what we call a narrow-band update scheme. The efficacy of the scheme is demonstrated with numerical experiments on low contrast medical images.

   Download publications

   
   
6. Image Processing via Level Set Curvature Flow : Malladi, R., and Sethian, J.A., Proc. Natl. Acad. of Sci., 92, 15, pp. 7046--7050, 1995.

   Abstract

   In this note, we present an image smoothing and enhancement method which is based on the curvature flow interpretation of the geometric heat equation. It can be termed as a ``controlled-diffusion'' scheme for images. The model has just one (enhancement) parameter and achieves very good results by expending significantly less computational labor compared to the other schemes.

   Download publications

   
   
7. An O(N \log N) algorithm for shape modeling : Malladi, R., and Sethian, J.A., Proceedings of the National Academy of Sciences, Vol. 93, pp. 9389-9392, September 1996.

   Abstract

   We present a shape recovery technique in $2D$ and $3D$ 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 the level set shape recovery scheme introduced by Malladi, Sethian, and Vemuri} and the fast marching method for computing solutions to static Hamilton-Jacobi equations.

   Download publications

   
   
8. Level Set Methods for Curvature Flow, Image Enchancement, and Shape Recovery in Medical Images : Malladi, R., and Sethian, J.A., H.C. Hege, K. Polthier (eds), Visualization and Mathematics, Springer, Berlin, Heidelberg, New York, pp. 329--345, 1997.

   Abstract

   Level set methods are powerful numerical techniques for tracking the evolution of interfaces moving under a variety of complex motions. They are based on computing viscosity solutions to the appropriate equations of motion, using techniques borrowed from hyperbolic conservation laws. In this paper, we review some of the applications of this work to curvature motion, the construction of minimal surfaces, image enhancement, and shape recovery. We introduce new schemes for denoising three-dimensional shapes and images, as well as a fast shape recovery techniques for three-dimensional images.

   Download publications

   
   
9. Unified Approach to Noise Removal, Image Enhancement, and Shape Recovery : Malladi, R., and Sethian, J.A., IEEE Trans. on Image Processing, 5, 11, pp. 1554-68, 1996.

   Abstract

   We present a unified approach to noise removal, image enhancement, and shape recovery in images. The underlying approach relies on the level set formulation of curve and surface motion, which leads to a class of PDE-based algorithms. Beginning with an image, the first stage of this approach removes noise and enchances the image by evolving the image under flow controlled by min/max curvature flow and by the mean curvature. This stage is applicable to both salt-and-pepper grey-scale noise and full-image continuous noise present in black and white images, grey-scale images, texture images and color images. The noise removal/enhancement schemes applied in this stage contains only one enhancement parameter, which in most cases is automatically chosen, and stop automatically at some optimal point. Continued application of the scheme produces no further change. The second stage of our approach is the shape recovery of a desired object; we again exploit the level set approach to evolve an initial curve/surface towards the desired boundary, driven by an image-dependent speed function which automatically stops at the desired boundary.

   Download publications

   
   
10. Image Processing: Flows under Min/Max Curvature and Mean Curvature : Malladi, R., and Sethian, J.A., Graphical Models and Image Processing, 58,2, pp. 127--141, 1996.

    Download publications

    
    
11. Flows under Min/Max Curvature and Mean Curvature: Applications in Image Processing : Malladi, R., and Sethian, J.A., Proceedings of the Fourth European Conference on Computer Vision, LNCS Vol. 1064, pp. 251-261, University of Cambridge, Cambridge, England, April 1996.

    Download publications

    
    
12. Level Set and Fast Marching Methods in Image Processing and Computer Vision : Malladi, R., and Sethian, J.A., Proceedings of IEEE International Conference on Image Processing, Lausanne, Switzerland, Sept. 16-19, 1996.

    Abstract

    In recent years, level set methods have been used in a variety of settings for problems in computer vision and image processing. A related numerical methodology, known as "fast marching methods", has been recently developed to solve static Hamilton-Jacobi equations extremely quickly; the techniques rely on conversion to a static problem, and are based on a marriage between narrow band techniques for level set methods and fast sorting algorithms. We show the application of these techniques to a collection of problems, including image denoising and enhancement schemes based on curvature-controlled diffusion with automatic stopping and hierarchical scales, extremely fast shape-from-shading schemes, and shape recovery in medical imaging.

    Download publications

    
    
13. Level Set Methods for Curvature Flow, Image Enhancement, and Shape Recovery in Medical Images : Malladi, R., and Sethian, J.A., Proc. of Conf. on Visualization and Mathematics, June, 1995, Berlin, Germany, Springer-Verlag, Heidelberg, Germany, pp. 329--345, 1997.

    Download publications

    
    
14. A Unified Geometric Model for 3D Confocal Image Analysis in Cytology : Sarti, A., Ortiz, C., Lockett, S., and Malladi, R., LBL Report, Lawrence Berkeley National Laboratory, University of California, May, 1998, SIBGRAPI 98 proceedings, Rio de Janeiro, 1998, submitted to IEEE Trans. on Biomedical Engineering.

    Download publications

    
    
15. A Real-Time Algorithm for Medical Shape Recovery : Malladi, R., and Sethian, J.A., Proceedings of ICCV '98, Bombay India, pp. 304-310, 1998.

    Download publications

    
    
16. Images as Embedded Maps and Minimal Surfaces: Movies, Color, Texture, and Medical Images : Kimmel, R., Malladi, R., and Sochen, N., to appear, International Journal of Computer Vision, 1999.

    Download publications

    
    
17. A General Framework for Low Level Vision : Sochen, N., Kimmel, R., and Malladi, R., IEEE Trans. Image Proc., 7,3, pp. 310-318, 1998.

    Download publications

    
    
18. A General Framework for Low Level Vision Fast Methods for Shape Extraction in Medical and Biomedical Imaging : Malladi, R., and Sethian, J.A., in Geometric Methods in Biomedical Image Analysis, Ed. R. Malladi, pp. 1--13, Springer Verlag, 2002.

    Download publications