## Background

2.1 2D Parametric Deformable Models

A traditional 2D parametric deformable model or deformable contour is a curve x(s) = [x(s), y(5)], 5e [0,1], that moves through the spatial domain of an image to minimize the energy functional

E = jO1! H*'(5)|2 + ^|x"(5)|2) + Eext(x(5))d5 (1)

where a and ft are weighting parameters that control the deformable contour's tension and rigidity, respectively, and x'(5) and x"(5) denote the first and second derivatives of x(5) with respect to 5. The external potential function Eext is derived from the image so that it takes on its smaller values at the features of interest, such as boundaries. Given a gray-level image I(x, y) viewed as a function of continuous position variables (x,y), typical external potential functions designed to lead a deformable contour toward step edges are 

where Gff(x, y) is a two-dimensional Gaussian function with standard deviation a and V is the gradient operator. If the image is a line drawing (black on white), then appropriate external energies include 

It is easy to see from these definitions that larger a's will cause the boundaries to become blurry. Such large a's are often necessary, however, in order to increase the capture range of the deformable contour.

A deformable contour that minimizes E must satisfy the Euler equation 

This can be viewed as a force balance equation

where Fint = ax"(5)- ^""(5) and F^xt = — VEext. The internal force Fint discourages stretching and bending while the external potential force F^t pulls the deformable contour toward the desired image edges.

To find a solution to (6), the deformable contour is made dynamic by treating x as function of time t as well as 5 —i.e., x(5, t). Then, the partial derivative of x with respect to t is then set equal to the left-hand side of (6) as follows:

Xt(5, t) = ax"(5, t) - 0x""(5, t) - VEext. (8)

When the solution x(5, t) stabilizes, the term xt (5, t) vanishes and we achieve a solution of (6). A numerical solution to (8) can be found by discretizing the equation and solving the discrete system iteratively (cf. ). We note that most deformable contour implementations use either a parameter that multiplies xt in order to control the temporal step size, or a parameter that multiplies VEext, which permits separate control of the external force strength. In this chapter, we normalize the external forces so that the maximum magnitude is equal to 1, and use a unit temporal step size for all the experiments.

### 2.2 Behavior of Traditional Deformable Contours

An example of the behavior of a traditional deformable contour is shown in Fig. 1. Figure la shows a 64 x 64-pixel line-drawing of a U-shaped object (shown in gray) having a boundary concavity at the top. It also shows a sequence of curves (in black) depicting the iterative progression of a traditional deformable contour (a = 0.6, ¿6 = 0.0) initialized outside the object but within the capture range of the potential force field. The potential force field F^t = —VE^4 where a = 1.0 pixel is shown in Fig. lb. We note that the final solution in Fig. la solves the Euler equations of the deformable contour formulation, but remains split across the concave region.

The reason for the poor convergence of this deformable contour is revealed in Fig. lc, where a close-up of the external force field within the boundary concavity is shown. Although the external forces correctly point toward the object boundary, within the boundary concavity the forces point horizontally in opposite directions. Therefore, the deformable contour is pulled apart toward each of the "fingers" of the U-shape, but not made to progress downward into the concavity. There is no choice of a and 6 that will correct this problem.

Another key problem with traditional deformable contour formulations, the problem of limited capture range, can be understood by examining Fig. lb. In this figure, we see that the magnitude of the external forces die out quite rapidly away from the object boundary. Increasing a in (5) will increase this range, but the boundary localization will become less accurate and distinct, ultimately obliterating the concavity itself when a becomes too large.

Cohen and Cohen  proposed an external force model that significantly increases the capture range of a traditional deformable model. These external forces are the negative gradient of a potential function that is computed using a Euclidean (or chamfer) distance map. We refer to these forces as distance potential forces to distinguish them from the traditional potential forces defined in Section 2.1. Figure 2 shows the performance of a deformable contour using distance potential forces. Figure 2a shows both the U-shaped object (in gray) and a sequence of contours (in black) depicting the progression of the deformable contour from its initialization far from the object to its final configuration. The distance potential forces shown in Fig. 2b have vectors with large magnitudes far away from the object, explaining why the capture range is large for this external force model.

As shown in Fig. 2a, this deformable contour also fails to converge to the boundary concavity. This can be explained by inspecting the magnified portion of the distance potential forces shown in Fig. 2c. We see that, like traditional potential forces, these forces also point horizontally in opposite directions, which pulls the deformable contour apart but not downward into the boundary concavity. We note that Cohen and Cohen's modification to the basic distance potential forces, which applies a nonlinear transformation to the distance map , does not change the direction of the forces, only their magnitudes. Therefore, the problem of convergence to boundary concavities is not solved by distance potential forces.