## Snakes

The second class of algorithms presented intends to overcome some of the limitations of the graph-based approaches. The former allows the segmentation line, respectively surface, to have individual properties that are not related to the image, but rather to physical properties of some material. The segmentation process is no longer solely based on the image, but regularized by the constraineds imposed by the physical model. This model introduces some generic knowledge of general organ's shape encoded in the elasticity of the material. The algorithms of this section belong to the field of physically based deformable models. In this section, the basics of Snakes are first depicted, followed by the presentation of two extensions that have been proposed during the last few years.

Traditional Snakes used for image segmentation are polygonal curves to which an objective function is associated. This function combines an "image term," which measures either edge strength or edge proximity, and a regular-ization term, which accounts for tension and curvature. The curve is deformed in order to optimize a score and, as a result, to match the image edges. The optimization typically is global, i.e., it takes edge information into account along the whole curve simultaneously, but only considers local image information, i.e. image intensities close to the curve.

Snakes were originally introduced by Kass et al. [44] and are modeled as time-dependent 2-D curves defined parametrically as v(s, t) = (x(s, t), y(s, t))o <s<1> (14.5)

where s is proportional to the arc length, t the current time, and x and y the curve's image coordinates. The Snake deforms itself as time progresses so as to minimize an energy term that combines image, internal, and external energies:

These energies are derived by integration along the curve. The forces resulting from the minimization of the image energy E¡mage guide the Snake to match the desired image features. This image energy is derived by integrating over a potential P(v(s, t)) from an image feature map, i.e.

A typical choice is to take P(v(s, t)) to be equal to the magnitude of the image gradient, that is

where I is either the image itself or the image convolved by a Gaussian kernel. As for the Live-Wire cost function, many different feature maps have been suggested in the past [45-47], yet the results are comparable.

The internal energy term Eint models the physical behavior of the material describing the Snake. Using the elastic rod model, E¡nt is taken to be

d s2

The parameters a(s) and ( (s) are arbitrary functions that regulate the curve's tension and rigidity and are commonly supplied by the user. It has been shown that they can be chosen in a fairly image-independent way [46]. Generally a(s) and ((s) are defined as constant along the curve, i.e. a(s) = a and ((s) = (. Other authors have proposed to dynamically adjust the values of a and ( along the curve by a feed-back strategy [48].

The segmentation process performed with Snakes is governed by the minimization of the term f E(v) dt. This amounts to using Hamilton's principle in variational calculus to derive the Euler-Lagrange equations of motion. The resulting equation of motion for the basic Snake described here can be written as a vss + P v ssss — Pv,

using subscripts to denote derivatives. For computational purposes the equation has to be discretized. The model v is taken to be a polygonal curve defined by a set of vertices v[i] = (xj^, y/i])o<i<n-1. It is customary to use central differences, yielding the discrete counterpart to Eq. (14.10)

-a (wJ-1 - 2uf] + + p (v[-2 - 4v[-1 + 6uf] - 4vi+1 + = -P„|^

which has to be solved for every single vertex uf1 simultaneously. Using matrix notation, the linear system of equations can be written as

where v stands for either (x0,..., xn-{) or (y0,..., yn-i). The stiffness matrix K is pentadiagonal and singular, thus Eq. (14.12) cannot be solved by direct inversion of K. To be able to solve the Snake Eq. (14.10), two different methods will be described. First an iterative solution is presented, which stems from the original Snakes framework. Ziplock Snakes, which will be introduced in section 14.5.1.1, incorporate boundary conditions into Eq. (14.12), so that the equation can be solved by inversion of K. In the original approach, additional terms are incorporated into Eq. (14.10) that introduce a temporal development of the Snake.

### 14.4.2.1 Dynamic Terms

Dynamic terms have been introduced to account for kinetic energy and velocity-dependent friction, leading to a more physically reasonable movement of the Snake [49]. The kinetic energy term EK(v) is set to

where n(s) represents the mass of the Snake.

14.4.2.2 Energy Dissipation

The physical system described so far is energy conserving. The introduction of energy dissipation results in a more realistic physical behavior and can be modeled using a Rayleigh dissipation functional

Y (s) being the damping coefficient.

The segmentation process is now determined by the minimization of the term f E(v) + EK(v) + D(vt) dt. Using the Hamiltonian principle the following Euler-Lagrange differential equation results l^vtt + Y vt - avss + P Vssss = -Pv, (14.15)

where i(s) and y (s) are considered constants along the curve. Forward differences are used to approximate the time derivatives, resulting in a linear system of equations which can be formulated in matrix notation as

((l + y)I + K) ■ v[t] = -Pv\vI_1] + (2| + y) v[t-1] - i v[t-2]. (14.16)

The role of the damping becomes evident, as the condition of the stiffness matrix K is improved through the damping term (i + y)I. This term has to be selected in a reasonable manner to prevent the Snake to be "glued," which would be the case for |(| + y)I| ^ |K|. With appropriate selections for i and y, a well-conditioned linear system results, so that the term (i + y )I + K can be inverted and Eq. (14.16) solved for v[t] yielding an iterative algorithm to solve the Snake equation of motion.

The Lagrangian formalism allows to unify forces from very different type of sources. The target function is extended to incorporate more energy terms so that the final energy to be minimized is of the form Etot = i Ei. Some basic extensions that have been presented are summarized.

### 14.4.2.3 External Forces

User interaction is introduced through external forces, so that the Snake can be modified manually [49]. Two type of forces are commonly used to attract or repulse the Snake from the current mouse position. Attraction can be modeled by introducing a virtual spring connecting the mouse position m with a point p on the Snake, that adds a term k(p - m)2 to the external energy Eext, where the spring constant k is a parameter. To push the Snake away from an undesired local energy minimum, a "volcano" is introduced by adding an energy function proportional to 1 to the external energy, where r is the distance of a point from the volcano center. Obviously, special care is required to avoid instabilities near r = 0.

### 14.4.2.4 Balloon Forces

Traditional Snakes exhibit a tendency to shrink, as they reach an absolute minimum when contracted into a single point under a flat potential field, i.e., a homogeneous image. While the correction of the energy term Ejnt to enforce parameterization according to the arc-length can prevent this behavior, the resulting governing equations are highly nonlinear. Instead, an inflating force can be introduced, which expands a closed Snake like a balloon [50]. Denoting the unit vector normal to the curve at point v(s) with n(s), the additional energy term becomes

14.4.2.5 Gravitational Forces

Similar to the balloon forces, a gravitational force can be defined [51]. Interpreting the image intensity as the 2-dimension, the energy term is defined as

where g(s) is the gravitation vector (0, 0, —g). The Snake is then accelerated in negative 2-direction, so that the model seems to "falls" on an object.

## Post a comment