Background in Deformable Models

In some sense, deformable models used in segmentation and shape recovery applications can be classified into two groups: free form and shape models [53].

In shape models prior knowledge of the global structure is included using a parameterized template of a specific structure. Free form deformable templates, like snakes, have no explicit global structures as the prior knowledge includes basically local continuity and smoothness constraints.

Considering as a functional energy minimization process, the snake model consists of an initial model which is carried to the desired object boundary by forces described by the Euler-Lagrange equations. In a different way, the snake evolution can be formulated by local deformations to reshape dynamically the initial model in a process which do not apply minimization techniques explicitly. The former is the formulation used by Kass et al. [42] in the original snake model. It will be described next.

7.2.1 Original Model

Geometrically, a snake is a parametric contour c, here assumed to be closed, embedded in a domain D c m2:

c : [0, 1] ^ D c m2, c (s) = (x (s), y (s)) . (7.1)

We can define a deformable model as a space of admissible deformations (contours) Ad and a functional E to be minimized [18]. This functional represents the energy of the model and has the form:

E1 = j (W1|| c'(s) ||2 + w21| c"(s) ||2) ds, (7.3)

Jn are the internal and external energy terms, respectively. In the internal energy expression, the parameter w1 (tension) gives the snake the behavior of resisting the stretch and w2 (rigidity) makes the snake less flexible and smoother. These parameters can be constants or dependent on s [44]. Each prime denotes a degree of differentiation with respect to the parameter s.

In the external energy E2, P is a potential related with the features we seek. For edge detection in a grayscale image a possible definition is [6]:

where I is the image intensity.

The process of minimizing the functional given in (7.2) can be viewed from a dynamic point of view by using the Lagrangian mechanics. This leads to dynamic deformable models that unify the description of shape and motion. In these models the deformable contour is viewed as a time-varying curve:

with a mass density ¡x and a damping density y.

In this formulation, the Lagrange equations of motion for a snake with potential energy given by expression (7.2) have the form [44,50]:

x VP + yM + Wic'(s)) + (w2c"(s)) + VP(c(s)) = 0, (7.7)

where the first two terms represent the inertial and damping forces while the third and fourth terms give the forces related to the internal energy (Eq. (7.2)). The last term in Eq. (7.7) is the external force due to the external potential P in expression (7.5). Equilibrium is achieved when the internal and external forces balance and the contour comes to rest; which implies that:

In general, Eq. (7.7) does not have analytical solutions. Thus, numerical methods must be considered. Henceforth, in order to solve this equation, for an initial closed contour, we have to discretize the snake in space and time by using finite differences or finite elements methods, each of them with trade-offs between performance and numerical efficiency [19,44]. We also have to use a termination condition, based on Eq. (7.8), to stop the numerical interactions [44].

It is important to observe that the space Ad in expression (7.2) does not include contours with more than one connected component. So the classical snake model does not incorporate topological changes of the contour c during its evolution given by Eq. (7.7). Besides, the contraction force generated by the third and fourth terms in this equation is shape dependent and makes the stabilization of the snake too dependent on the parameters w1 and w2. While in theory it is possible to compute a pair of proper weights of the internal energy for each point, it is very difficult in practice [79].

For boundary extraction and segmentation tasks, in general we use a simplified version of Eq. (7.7) in which we take ¡x = 0. Hence, the model has no inertial forces, which avoids oscillations near the equilibrium point [31].

Snake models can be extended to 3D, generating deformable surface models. The traditional mathematical description for these models is given next.

7.2.2 Deformable Surfaces

Let us consider the following balloon-like model for closed surfaces [19]:

v : ft+ x [0, 1] x [0, 1] ^ ft3, v(t, r, s) = (v1(t, r, s), v2 (t, r, s), v3(t, r, s)),

Initial estimation : v(0, r, s) = v0(r, s), where n(v) is the normal (unitary) field over the surface v, F is the image force field (may be normalized), and k is a force scale factor. The parameters rnij control the smoothing and flexibility of the model.

By using the internal pressure force (kn(v)), the model behaves like a balloon, which is inflated, passing over regions in which the external force is too weak. Consequently, the model becomes less sensitive to initialization, which is an advantage over more traditional active models [6, 18].

If finite differences is used to numerically solve Eq. (7.9), the continuous surface v(r, s) is discretized, generating a polygonal mesh. During the mesh evolution, self-intersections must be avoided.

This problem has been efficiently addressed in the context of discrete de-formable models. Differently from the above formulation, in which the mesh arises due to a discretization of the continuous model (defined by Eq. (7.9)), discrete surface models start from a two-dimensional mesh. The mesh nodes are updated by a system of forces that resembles a discrete dynamical system. The T-surfaces model is such a system, which is fundamental for our work. It is summarized next.

dv d2v d2 v

7.2.3 T-Surfaces

The T-surfaces approach is composed of three components [49]: (1) atetrahedral decomposition (CF-triangulation) of the image domain D c ft3; (2) a particle model of the deformable surface; and (3) a characteristic function x defined on the grid nodes which distinguishes the interior (Int(S)) from the exterior (Ext(S)) of a surface S:

where x (p) = 1 if p e Int(S) and x (p) = 0, otherwise p is a node of the grid.

Following the classical nomenclature [1], a tetrahedron (also called a simplex) a is a transverse one if the characteristic function x in Eq. (7.10) changes its value in a. Analogously, this follows for an edge.

In the framework composed of both the simplicial decomposition and the characteristic function, the reparameterization of a surface is done by [49]: (1) computing the intersection points of the surface with the grid; (2) finding the set of transverse tetrahedra (combinatorial manifold); (3) choosing an intersection point, for each transverse edge; and (4) connecting the selected points.

In this reparameterization process, the transverse simplices play a central role. Given such a simplex, we choose in each transverse edge an intersection point to generate the new surface patch. In general, we will obtain three or four transverse edges in each transverse tetrahedron (Fig. 7.1). The former gives a triangular patch and the latter defines two triangles. So, at the end of step (4), a triangular mesh is obtained. Each triangle is called a triangular element [49].

Taking a 2D example, let us consider the characteristic functions (x1 and x2) relative to the two contours pictured in Fig. 7.2. The functions are defined on the vertices of a CF-triangulation of the plane. The vertices marked are those where max{xi, x2} = 1. Observe that they are enclosed by a merge of the contours. This merge can be approximated by a curve belonging to the region obtained by tracing the transverse triangles. The same would be true for more than two contours (and obviously for only one).

After the reparameterization process, a suitable evolution scheme must be applied. Dynamically, a T-surfaces can be seen as a closed elastic mesh [49].

Case 0 Case 1 Case 2

Figure 7.1: Basic types of intersections between a plane and a simplex in 3D.

Figure 7.1: Basic types of intersections between a plane and a simplex in 3D.

Figure 7.2: Two snakes colliding with the inside grid nodes and snaxels marked.

Each mesh node is called a node element and each pair of connected nodes Vj_, Vj is called a model element.

The node elements are linked by springs, whose natural length we set to zero. Hence, a tensile force can be defined by: