A ``snake'' [Kass, Witkin and Terzopoulos1987] is a dynamic deformable contour in the x-y
image plane. We define a discrete deformable contour as *n*
equally-spaced nodes indexed by *i*=1, ..., *n*, with time varying
positions . The deformable contour's
dynamic behavior can be influenced interactively by incorporating
user-specified forces (e.g. mouse forces) into its equations of
motion. Such behavior is governed by the system of first-order
ordinary differential equations:

where is a velocity-dependent damping constant, are ``tension'' forces which make the deformable contour act like a series of springs that resist deformation, are ``rigidity'' forces which make the contour act like thin wire that resists bending, and are forces in the image plane plus the simulated mouse forces applied to the contour.

A deformable mesh consists of *m*+*n* contours, *n* of
which run vertically, each with *m* nodes, and *m* of which run
horizontally each with *n* nodes. The crossing points on the
deformable mesh are nodes shared by the intersecting contours.

We express , the tension forces, in terms of the deformation
of the springs connecting node *i* to its two neighboring nodes and
, the rigidity forces, in terms of the second order forward
finite differences as follows:

where *a* and *b* are parameters, is the deformation of the
spring connecting node *i* to node *i*+1 (i.e. its current length
minus its rest length), and is the unit vector from to . Note that and vanish in
the absence of deformation and bending.

To make the outline of the fish in the image stand out, we convert the
original RGB color image into a gray-scale image *I*(*x*,*y*). The gradient
of *I*, call it , forms a potential field whose ``ravines''
coincide with the dark outline of the profile of the fish. The image
force field can then be expressed as the gradient of , i.e.
) such that the ravines act
as attractors to deformable contours. The contours descend and
stabilize at the bottoms of the nearest ravines. In order to let the
ravines attract the deformable contours from some distance away, the
potential function is computed as follows:

where denotes convolution with a 2D Gaussian smoothing filter of width which broadens the ravines of .

Often the user may initialize the border of the deformable mesh too far from the edges of the fish body and hence the deformable contours may become attracted by nearby dark features and fail to localize the correct outline. Should this be the case, the user can apply simulated spring forces by using the mouse to guide a deformable contour towards the ravine of interest [Kass, Witkin and Terzopoulos1987].

Another case frequently encountered is where the profile of the fish is not composed of edges that are consistently dark or consistently white. For example, in the fish image shown in Fig. (a), part of the profile that bounds the tail and the upper body is made of white edges while the lower body is demarcated from the background by dark lines. In this case if is generated such that the deformable contours are attracted to dark edges then most of the profile in Fig. (a) can not be captured properly. It is hence useful to constrain certain nodes of the border contours to selected anchor points in the image (the interface allows the user to interactively place anchor points using the mouse). The constraints prevent the deformable contours from straying far from the anchor points, regardless of the image forces and other mouse forces. This can be achieved by attaching the deformable contour nodes with springs to their corresponding anchor points:

where is the spring constant. Using this mechanism we can also effectively deal with images where the profile of the fish is obscure.

The total external force is therefore obtained by combining the image force , the mouse force and the constraint force . The deformable contour can then be simulated by integrating the system of ordinary differential equations () forward through time using an Euler integration method [Press et al.1986].

Xiaoyuan Tu | January 1996 |