next up previous
Next: Background Up: No Title Previous: No Title

Introduction

Snakes [1], or active contours, are curves defined within an image domain, which can move under the influence of internal forces within the curve itself and external forces derived from the image data. The internal and external forces are defined so that the snake will conform to an object boundary or other desired features within an image. Snakes are widely used in many applications, including edge detection [1], shape modeling [2,3,4], segmentation [5,6,7], and motion tracking [5,8].

There are two general types of active contour models in the literature today: parametric active contours and geometric active contours. Parametric active contours were originally developed by Kass, Witkin, and Terzopoulos [1]. In their formulation, the image data are used to define potential functions over the image domain. Usually, these potential functions have local minima at the image intensity edges that occur at object boundaries. Parametric curves are then synthesized within the image domain, and are forced to move toward the potential function minima. The forces that move the curve are formed in part by the negative of the gradient of the potential function itself; we will call these forces potential forces. Additional forces, such as pressure forces, together with the potential forces comprise all the external forces. In addition, there are internal forces designed to hold the curve together (elasticity forces) and to keep it from bending too much (bending forces).

More recently, geometric active contour models were proposed by Caselles et al. [9] and Malladi et al. [10]. Based on the theory of curve evolution and geometric flows [11,12,13,14], these models define a geometric active contour as a level-set of an evolving scalar function defined on a spatial domain. The computations causing the scalar function to change are based on a numerical algorithm proposed by Osher and Sethian [15].

Caselles [16] has shown that parametric active contours and geometric contours are basically equivalent, and that one formulation can be derived from the other. One basic difference, however, is in the handling of what is sometimes called ``the topology problem''. In particular, when there are several objects in the scene, the topology of the final curve is object-dependent, and the algorithm must adjust. In the geometric active contour formulation, this is handled automatically, since the parameterization of the level-set is calculated only after convergence [16]. In the parametric active contour formulation, more extensive measures need to be taken to split active contours into two or more pieces [7,17] or to instantiate separate active contours at different locations [18,19]. Except for topological differences, however, the behavior of both active contour models is fundamentally characterized by the external and internal forces of the formulation. We focus our discussion in this paper on the parametric active contour viewpoint.

There are three key difficulties with active contour algorithms. First, it is well known that the initial contour, in general, must be placed close to the boundary or else it will likely converge to the wrong result. Several methods have been proposed to address this problem including scale-space methods [1] and pressure forces [20]. The basic idea is to increase the ``capture range'' of the external fields and to guide the contour toward the desired boundary. The second problem is that active contours are known to have difficulties progressing into concave boundary regions, often leaving the contour split across the concave region [21]. There is no satisfactory solution to this problem, although pressure forces [20], control points [21], adding nodes [22], and using solenoidal external fields [23] have been proposed. The third problem stems from the fact that that most algorithms use potential forces derived from a low-pass filtered image in order to increase the capture range. Unfortunately, this filtering also blurs the boundary detail, leaving the snake to converge to a blurry boundary. While multi-resolution approaches have addressed this problem [24], determining the required resolution for a given snake position is difficult to determine, and leads to ad-hoc methods.

In this paper, we present a new class of external forces for active contour models which addresses all three problems listed above. These fields, which we call gradient vector flow (GVF) fields, are dense vector fields derived from images by minimizing a certain energy functional in a variational framework. The minimization is achieved by solving a pair of decoupled linear partial differential equations which diffuses the gradient vectors of an edge map computed from the image. The GVF field assigns to every point in the image a vector that would move a particle placed at that point toward a nearby edge in the image. We will call the active contour that uses the GVF field as its external force a GVF snake. Particular advantages of the GVF snake over a traditional snake are its insensitivity to initialization and ability to move into concave boundary regions. Unlike the pressure forces associated with balloon snakes, the GVF snake does not need to ``know'' whether to shrink or grow towards the boundary. We will also show how the GVF field itself has some interesting properties related to the medial axis analysis of shape.

This paper is organized as follows. In Section 2, we give a brief introduction to parametric snakes. In Section 3, we describe the GVF field and GVF snake, and in Section 4 we give several examples of GVF fields and GVF snakes applied to simple shapes. Section 5 demonstrates GVF on two noisy gray-level images and on a simple shape in three dimensions. In Section 6, we describe an interesting connection between the GVF field and medial axis properties of shapes. Finally, in Section 7, we summarize our results and discuss possible future research directions.


next up previous
Next: Background Up: No Title Previous: No Title
Chenyang Xu
1999-11-06