Parametric Snake Model

In the original snake formulation of Kass et al. [1], the best snake position was defined as the solution of a variational problem requiring the minimization of the sum of internal and external energies integrated along the length of the snake. The corresponding Euler equations, which give the necessary conditions for this minimizer, comprise a force balance equation. By introducing a temporal parameter t, the force balance equation can be made dynamic. When the dynamic equation reaches its steady state, a solution to the static problem is found. We now give a brief summary of these steps.

A snake is a curve ${\bf x}(s) = [x(s),y(s)]$, $s\in[0,1]$, that moves through the spatial domain of an image to minimize the energy functional

$$E = \int^1_0 \frac12(\alpha\vert{\bf x}'(s)\vert^2+\beta\vert{\bf x}''(s)\vert^2) + E_{\rm ext}({\bf x}(s)) ds$$ (1)

where $\alpha$ and $\beta$ are weighting parameters that control the snake's tension and rigidity, respectively. ${\bf x}'(s)$and ${\bf x}''(s)$ denote the first and second derivatives of ${\bf x}(s)$with respect to s. The external energy function $E_{\rm ext}$ 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 energies designed to lead an active contour toward step edges are [1]:

$$E_{\rm ext}^1(x,y) -\vert\nabla I(x,y)\vert^2$$ = (2)

$$E_{\rm ext}^2(x,y) -\vert\nabla(G_\sigma(x,y)*I(x,y))\vert^2$$ = (3)

where $G_\sigma(x,y)$ is a two-dimensional Gaussian function with standard deviation $\sigma$ and $\nabla$ is the gradient operator. If the image is a line drawing (black on white), then appropriate external energies include [20]:

$$E_{\rm ext}^3(x,y)$$ = I(x,y) (4)

$$E_{\rm ext}^4(x,y) G_\sigma(x,y)*I(x,y)$$ = (5)

It is easy to see from these definitions that larger $\sigma$'s will cause the boundaries to become blurry. Such large $\sigma$'s are often necessary, however, in order to make the effect of the boundary ``felt'' at some distance from the boundary -- i.e., to increase the capture range of the active contour.

A snake that minimizes E must satisfy the Euler equation

$$\alpha {\bf x}''(s) - \beta {\bf x}''''(s) - \nabla E _{\rm ext} = 0$$ (6)

This can be viewed as a force balance equation

$${\bf F}_{\rm int} + {\bf F}^1_{\rm ext} = 0$$

where ${\bf F}_{\rm int} = \alpha {\bf x}''(s) - \beta {\bf x}''''(s)$ and ${\bf F}^1_{\rm ext} = - \nabla E _{\rm ext}$. The internal force ${\bf F}_{\rm int}$ discourages stretching and bending while the external force ${\bf F}^1_{\rm ext}$pulls the snake towards the desired image contour.

To find a solution to (6), the snake is made dynamic by treating ${\bf x}$ as function of time t as well as s -- i.e., ${\bf x}(s,t)$. Then, the partial derivative of ${\bf x}$ with respect to t is then set equal to the left hand side of (6) as follows

$${\bf x}_t(s,t) = \alpha {\bf x}''(s,t) - \beta {\bf x}''''(s,t) - \nabla E _{\rm ext}$$ (7)

When the solution ${\bf x}(s,t)$ stabilizes, the term ${\bf x}_t(s,t)$ vanishes and we achieve a solution of (6). This dynamic equation can also be viewed as a gradient descent algorithm [25] designed to solve (1). A solution to (7) can be found by discretizing the equation and solving the discrete system iteratively (cf. [1]).