Active Contours, Deformable Models, and Gradient Vector Flow

[Brain Mapping] [Cardiac Motion Estimation][Image Processing and Analysis]

Chenyang Xu and Jerry L. Prince

Overview

Active contours, or snakes, are computer-generated curves that move within images to find object boundaries. Its 3D version is often known as deformable models or active surfaces in literature. We have developed a new kind of snake that permits the snake to start far from the object, and yet still draws it towards the object, and forces it into boundary concavities. The new snake is based on a new type of external force field, called gradient vector flow, or GVF. This field is computed as a spatial diffusion of the gradient of an edge map derived from the image. This computation causes diffuse forces to exist far from the object, and crisp force vectors near the edges. Combining these forces with the usual internal forces yields a powerful computational object: the GVF snake (2D), or the GVF deformable model (N-D). We have experimented with GVF on line drawings and grayscale images, including images of the heart and brain. Several examples are shown below and both publications and software are also available online.

Introduction

Active contours, or snakes, are computer-generated curves that move within images to find object boundaries (note that the 3D version is often known as deformable models or active surfaces in the literature). They are often used in computer vision and image analysis to detect and locate objects, and to describe their shape. For example, a snake might be used to automatically find a manufactured part on an assembly line; one might be used to find the outline of an organ in a medical image; or one might be used to automatically identify characters on a postal letter. We have developed a new kind of snake here at the Image Analysis and Communications Laboratory. Our snake solves two key problems that have plagued the computer vision community since the introduction of snakes in 1988. These problems are that snakes cannot move toward objects that are too far away and that snakes cannot move into boundary concavities or indentations (such as the top of the character U). Previous efforts to solve these problems have not been completely successful, and have often created new problems along with the proposed solutions.

Method

Our snake, which we call the gradient vector flow (GVF) snake, begins with the calculation of a field of forces, called the GVF forces, over the image domain. The GVF forces are used to drive the snake, modeled as a physical object having a resistance to both stretching and bending, towards the boundaries of the object. The GVF forces are calculated by applying generalized diffusion equations to both components of the gradient of an image edge map.

The GVF external forces are what makes our snake inherently different from previous snakes. Because the GVF forces are derived from a diffusion operation, they tend to extend very far away from the object. This extends the "capture range" so that snakes can find objects that are quite far away from the snake's initial position. This same diffusion creates forces which can pull active contours into concave regions. A fundamental difference between this formulation and the traditional formulation is that GVF forces are not purely irrotational (curl-free) forces. In fact, they typically comprise both irrotational and solenoidal (divergence-free) fields. Because of this property, they cannot be derived from the energy minimization framework of traditional snakes.

This is a gradient vector flow (GVF) field for a U-shaped object. These vectors will pull an active contour towards the object boundary.

Results

We have tested our GVF snake on many types of objects, from simple shapes to magnetic resonance images of the heart and brain. We have also extended GVF to three dimensions, where deformable surfaces, or balloons, are defined. Our ultimate research goal is to use a three-dimensional GVF balloon to find the entire human brain cortex from volumetric magnetic resonance images. The following examples demonstrate some of the properties of the GVF snake.

A. Capture range and boundary concavities

(Click on image to see movie in animated GIF format.)	Initial Curve	Final Curve
A traditional snake must start close to the boundary and still cannot converge to boundary concavities.
A GVF snake can start far from the boundary and will converge to boundary concavities.
A GVF snake can even be initialized across the boundaries, a situation that often confounds traditional snakes and balloons.

B. Subjective Contours and Grayscale Images

(Click on image to see movie in animated GIF format.)	Initial Curve	Final Curve
GVF snakes converge to subjective contours -- contours that are not really there. This is also true for traditional snakes but not true for balloons.
GVF snakes are defined for grayscale images as well as binary images. Here the GVF snake finds the heart wall on a magnetic resonance image.

C. Three-Dimensional GVF: Deformable Surface

(Click on image to see movie.)	Initial Surface	Final Surface
GVF deformable surfaces are analogous to GVF snakes. They are driven by GVF forces to conform to object boundaries.

Conclusion

The GVF snake is a new approach to active contours and surfaces. It focuses on the design of the external force first, and the implementation of the snake second. The computations are straightforward, i.e., the diffusion equations are simple to calculate (see publications and software below), and the result is always better than the traditional snake. As outlined in our publications, the GVF usually offers advantages over balloons and distance-based snakes as well. We anticipate and encourage widespread use of the GVF snake and the easily implemented GVF active surface as well. This new approach offers new areas for further improvement as well. For example, we have recently implemented a more general version of GVF, generalized GVF, which offers advantages when the boundary concavity is very thin.

Acknowledgment

This research was supported by National Science Foundation grant MIP93-50336, CISE Directorate, Division of Microelectronic Information Processing Systems, Signal Processing Systems Program.

Publications

C. Xu and J.L. Prince, ``Gradient Vector Flow: A New External Force for Snakes,'' Proc. IEEE Conf. on Comp. Vis. Patt. Recog. (CVPR), Los Alamitos: Comp. Soc. Press, pp. 66-71, June 1997. [.pdf (2.5MB), .ps (2.0MB), .ps.gz (370KB), or request hard copy]
C. Xu and J. L. Prince, ``Snakes, Shapes, and Gradient Vector Flow,'' IEEE Transactions on Image Processing, 7(3), pp. 359-369, March 1998. [.pdf (0.4MB), .ps (4.1MB), .ps.gz (0.9MB), or request hard copy].
By March 2005, this paper has over 140 citations in archival journals and conference proceedings listed in Science Citation Index (SCI) and is ranked #7 among more than 1,200 SCI papers citing the original active contour paper by Kass, Witkin, and Terzopolous. Also as of April 2007, it receives 752 citations as listed by Google Scholar, and is ranked #9 among more than 4633 publications citing the original active contour paper by Kass et al.
C. Xu and J. L. Prince, "Generalized Gradient Vector Flow External Forces for Active Contours," Signal Processing --- An International Journal, 71(2), pp. 131-139, December 1998. [.pdf (0.5MB), or request hard copy].
C. Xu and J. L. Prince, "Global Optimality of Gradient Vector Flow", Proc. of 34th Annual Conference on Information Sciences and Systems (CISS'00), Princeton University, March 2000. [.pdf (0.7MB), .ps (0.6MB), .ps.gz (0.1MB)].
C. Xu, D. L. Pham, and J. L. Prince, "Medical Image Segmentation Using Deformable Models," SPIE Handbook on Medical Imaging -- Volume III: Medical Image Analysis, edited by J.M. Fitzpatrick and M. Sonka, May 2000. [.pdf (5.6MB), .ps.gz (1.9MB), book info]. (new)
C. Xu and J. L. Prince, "Gradient Vector Flow Deformable Models", Handbook of Medical Imaging, edited by Isaac Bankman, Academic Press, September, 2000. [.pdf (1.7MB)], [book info]. (new)
C. Xu, D. L. Pham, M. E. Rettmann, D. N. Yu, and J. L. Prince, "Reconstruction of the Human Cerebral Cortex from Magnetic Resonance Images," IEEE Transactions on Medical Imaging, 18(6), pp. 467-480, June, 1999. [.pdf (0.9MB)]. ( new) Note: this is an application of using GGVF deformable surface for 3D brain segmentation. See all the journal papers that cited this paper compiled from Science Citation Index.
C. Xu, A. Yezzi, Jr., and J. L. Prince, "On the Relationship between Parametric and Geometric Active Contours", in Proc. of 34th Asilomar Conference on Signals, Systems, and Computers, pp. 483 -489, October 2000. [.pdf (0.2MB)], Note: contains level set active contours using GVF.
C. Xu, A. Yezzi, Jr., and J. L. Prince, "A Summary of Geometric Level-Set Analogues for a General Class of Parametric Active Contour and Surface Models", in Proc. of 2001 IEEE Workshop on Variational and Level Set Methods in Computer Vision (VLSM 2001), pp. 104-111, July 2001. [.pdf (0.3MB)], Note: contains level set deformable surfaces using GVF.
C. Xu, Deformable Models with Application to Human Cerebral Cortex Reconstruction from Magnetic Resonance Images, PhD Dissertation, Department of Electrical and Computer Engineering, Johns Hopkins University, Baltiomre, MD, 21218, USA. [.pdf (20MB), .ps.gz (6.6MB)].
X. Han, C. Xu, and J. L. Prince, "A Topology Preserving Level Set Method for Gemetric Deformable Models," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 25, No 6, pp. 755-768, June 2003. [.pdf (1.8MB)]

GVF FAQ (Frequently Asked Questions)

The authors get frequent emails that ask various questions regarding GVF, from general questions regarding the theory of GVF to specific questions of asking help for debugging code!. In the past, we have tried to do our best to give response to every email we receive. However, recently, both authors are occupied completely by the work and finding harder to respond to every email we receive (which is getting more and more every day). As a result, we compiled a GVF FAQ to help answer some common questions regarding the use of GVF. Therefore, we kindly ask those who send us emails read both the FAQ and GVF papers carefully before asking question in email.

GVF Software

Matlab (2D Version)

We have put together a collection of matlab *.m files that will compute GVF and run a GVF snake (and several traditional snakes) on 2-D images. These files are not guaranteed to work on your machine and are not supported; however, they may be instructive and fun to play with. You can draw your own contour and watch it deform to its final configuration. The 2-D demonstrations above were generated using this software.

GVF for Unix, tested with Matlab version 4.2c (updated version, 9/29/99)

GVF for Windows 95/NT, tested with Matlab version 5 (updated version, 9/29/99)

Graphical GVF Snake Demo for Windows 95/98/NT, tested with Matlab version 5.

C version of GVF code for Matlab (CMEX) replaces GVF.m and is significantly faster. (new)

NOTE: for those who downloaded GVF software before 9/29/99, you can update the previous GVF software by downloading the MATLAB routines below and placing them under the "snake" directory of the GVF software: GVF.m, uppertri.m, BoundMirrorExpand.m, BoundMirrorEnsure.m, and BoundMirrorShrink.m.

MIPAV (3D Version)

A 3D implementation of the Generalized Gradient Vector Flow Algorithm is also available as a MIPAV plugin. This work was supported by NIH Grant 1 R01 NS054255-01.