Keywords

1 Introduction

Medical imaging nowadays is part of the routine in hospitals. The acquired images get better in quality and improvements are made to reduce the exposure of patients to radiation. Modern techniques allow to capture small details and to differentiate between kinds of soft tissue. But with the increased number of images and their higher resolution, interpretation has become a more complex task. Nonetheless, medical image segmentation is required for applications like radiotherapy, preoperative planning and postoperative evaluation. Medical image segmentation, as described by Elnakib et al. [1] in a survey, is the process of identifying regions of interest in images. Approaches range from simple ones that only exploit intensity values or region information to model-based ones that include a priori knowledge. The images often suffer from noise, aliasing and anomalies or may contain gaps in boundaries, providing challenges that are hard to handle with non model-based approaches.

Deformable models have been first proposed by Terzopoulos et al. in 1987 [2]. They provide a robust segmentation approach that uses bottom-up image-based constraints and top-down constraints from prior knowledge. Deformable models can be curves or surfaces (or of higher dimension, e.g. for temporal segmentation). They evolve under the influence of internal and external energies. The internal energy controls the curves smoothness and the external energy aims to attract the model towards boundaries in the image domain. Deformable models are an interesting approach as they combine geometry (to describe the shape), physics (to simulate the behavior) and approximation theory (for model fitting).

Deformable models have a broad range of possible applications. They have been used in computer graphics [3], to calculate the deformation of clothes [4] and in image composition [5]. Other uses include optical flow analysis for facial animation [6] and the determination of vehicle types [7].

Due to their power and robustness, deformable models are often used in medical applications. For example, Deserno et al. [8] presented an application for segment-ing the bony orbit while Heimann et al. [9] proposed a grand challenge for knee segmentation. Schmid [10] presented the segmentation of the hip bone, Snel et al. [11] used a deformable model for wrist segmentation and Rafai et al. [12] proposed a method for skull segmentation. Another medical use is surgery simulation which has been reviewed by Meyer et al. [13]. Medical simulation approaches that use deformable models to describe the mechanical behavior need proper evaluation. Marchal et al. [14] proposed a new and open framework to combine several metrics and models to compare different algorithms.

Several surveys on deformable models have been published, e.g. by McInerney et al. [15] in 1996, Montagnat et al. [16] in 2001 and Hegadi et al. [17] in 2010. Moore et al. [18] provided a general survey on deformable models while Jain et al. [19] have reviewed deformable template models, which are used for segmentation, image retrieval and video tracking.

Deformable models can be divided into discrete and continuous representations [16]. The discrete models can be split into particle systems and meshes. Continuous representations can have either an explicit (snakes) or implicit (level sets) description of their surface. These different classes of deformable models will be surveyed in this overview. First we will introduce active contour models, also known as snakes (Sect. 4.2). Next, several approaches to the level sets method will be discussed (Sect. 4.3), followed by a description of discrete deformable models (Sect. 4.4). We take a look at knowledge-based deformable models (Sect. 4.5) that are a specialization and at some alternative approaches (Sect. 4.6). An overview of external forces (Sect. 4.7) and approaches for segmentation initialization will also be given (Sect. 4.8). In the conclusion, the most important aspects are summarized and future prospects are briefly discussed.

2 Snakes

Active contour models, usually called snakes, are a class of deformable models with a continuous representation based on an explicit surface description. They have been originally proposed by Kass et al. [20] in 1988 and have been applied as a method for edge detection [21], motion tracking [22], stereo matching [23] and interactive image interpretation [20]. Other applications are shape modeling [24, 25] and segmentation [21, 26].

The main concept is to use an energy-minimizing parametric curve or a spline, reducing the problem to a minimization problem. Snakes need to be initialized closely to the final shape to ensure that they are attracted to the correct features.

The energy of a snake \(\alpha (s)\) can be written as

$$\begin{aligned} E_{\mathrm {snake}}(\alpha (s)) = E_{\mathrm {ext}}(\alpha (s)) + E_{\mathrm {int}}(\alpha (s)). \end{aligned}$$
(4.1)

The external energy \(E_{\mathrm {ext}}\) represents external constraints and image influence to get the contour pulled towards desired image features.

$$\begin{aligned} E_{\mathrm {ext}}(\alpha (s)) = \int {-\omega _1|\nabla \alpha (s)| ds} \end{aligned}$$
(4.2)

The internal energy expresses smoothness and tension constraints:

$$\begin{aligned} E_{\mathrm {int}}(\alpha (s)) = \frac{1}{2}\left( \int {\omega _2\left| \frac{\partial \alpha (s)}{\partial s}\right| ^2} + \int {\omega _3\left| \frac{\partial ^2\alpha (s)}{\partial s^2}\right| ^2} \right) \end{aligned}$$
(4.3)

where \(\omega _2\) is the weight for the influence of stretching on the contour and \(\omega _3\) weighs the bending.

Xu et al. [27] have proposed the gradient vector flow (GVF, see Sect. 4.7.2.5) as a new external image force to improve segmentation results. This concept has been extended by Cheng et al. [28] to a directional GVF. In 1993 Ivbins and Porril [29] have shown a region growing segmentation that exploits a snake with pressure force and statistical characteristics of the image. Mitrea et al. [30] have reviewed snakes and proposed an iterative method for snake calculation. Wang et al. [31] showed a method for muscle extraction from the leg using snakes. Kauffmann et al. [32] proposed a snake-based method to quantify cartilage thickness and volume in MR images.

Ip and Shen [33] proposed affine invariant active contour models (AI snakes) in 1998. AI snakes are an efficient method of establishing correspondence between model and data. The basis for their energy function is formed by local and global affine-invariant features.

In 1999, Vemuri and Guo [34] presented hybrid geometric active models. They introduced a hybrid geometric snake to allow for topology changes. Their model allows for the representation of global shapes with local details.

Another approach to topology adaptive snakes has been proposed by McInerney and Terzepoulos in 2000 [35]. Their T-Snakes offer topological flexibility and significantly extend conventional snakes. This approach has been extended further by others [36, 37].

3 Level Sets

Level sets have been introduced in 1988 by Osher and Sethian  [38] to overcome the difficulties that snakes have with changes in topologies. Their work has proven to be a powerful tool in segmentation. The ability of level sets to perform automatic topology changes can be useful in many cases, especially for the segmentation of objects with high shape variations. Implementations can be found in tools like ITK-SNAP [39] and YaDiV [40] or libraries like LSMLib.Footnote 1

Like snakes, level sets can be regarded as continuous deformable models. To overcome the drawbacks of snakes and to allow topology changes, level sets make use of an implicit representation. A deformable surface \(S\) is implicitly represented as an iso-surface of a time-varying scalar function, embedded in 3D.

Let \(\varPhi {:} \varOmega \times \mathbb {R}\rightarrow \mathbb {R}, \varOmega \in \mathbb {R}^{3}\). A level set \(S\) can be defined as an iso-hypersurface on \(\varPhi \) as follows:

$$\begin{aligned} S = \left\{ x \in \varOmega | \varPhi (x) = 0 \right\} \end{aligned}$$
(4.4)

We assume \(\varPhi \) to be a distance map that is negative inside the level set and positive outside. To integrate a temporal evolution we iteratively modify \(\varPhi \) and get

$$\begin{aligned} \frac{\partial \varPhi }{\partial t} + F \left| \nabla _{\varPhi } \right| = 0 \end{aligned}$$
(4.5)

with \(F\) as speed function. The speed function controls the image influence on the evolution of the level set surface. This formulation leads to the need to solve partial differential equations (PDE). To define the speed function we use the surfaces normal \(N\) and curvature \(k\), defined as:

$$\begin{aligned} N = \frac{\nabla \varPhi }{\left| \nabla \varPhi \right| }, \quad k = div\left( \frac{\nabla \varPhi }{\left| \nabla \varPhi \right| }\right) . \end{aligned}$$
(4.6)

Common approaches for speed functions are edge stopping and energy minimization, which we will present in the following sections.

3.1 Edge Stopping Level Sets

Osher and Sethian [38] proposed a level set approach that exploits edges. To slow down the expansion of the model, image gradients are used. The speed function is defined as the sum of a curvature force and an expansion force. This force is scaled by a stopping function that makes use of the image gradient at this point. The following equation is an example of a stopping function:

$$\begin{aligned} g (x) = \frac{1}{\left( 1 + \sqrt{|\nabla x|}\right) ^{p}} \end{aligned}$$

Using these speed values, the new distance map can be updated. The resulting con-tour is the input for the next iteration step. This approach does not stop the contour at high gradient completely but only slows it down. Therefore it is possible that after a large number of steps, the contour could overcome high gradients. This is a behavior that should always be considered. Figure 4.1 shows an example of patella segmentation using an edge stopping level set approach.

Fig. 4.1
figure 1

Example of an edge stopping level set for segmentation of the patella after a 10, b 20, c 30, d 40, e 60 and f 80 steps

Full size image

3.2 Energy Minimizing Level Sets

Instead of a gradient stopping function, an alternative approach defines an energy potential that is consequently minimized. The foundational work on this approach has been done by Mumford and Shah in 1989 [41]. The area and volume covered by the level set \(S\) are important in this approach and can be determined using the Heaviside function, which needs to be smoothed as described by Zhao et al. in [42]. The calculation is performed in three steps. First the average image intensity for voxels inside and outside the segment is calculated. The next step is to compute the energy of each voxel using the weighted area, volume and image intensities inside and outside the region of interest. Finally the distances are being updated using these energies.

3.3 Extensions

Over the years several extensions to level sets have been proposed. Sethian [43] developed an extension for fast marching, allowing the contour to move more than one voxel per iteration step. This was previously prevented by numerical instabilities. In 2001 Chan and Vese [44] have presented an approach to level sets that is not based on an edge-function and can operate on very noise, unsmoothed images. Zhang et al. [45] showed a hybrid approach that uses both boundary and region information to get accurate results by reducing leaking problems. Yeo et al. [46] have proposed a new external force in 2009. Their geometric potential force is based on hypothesized interaction between relative geometry and image gradients. Caselles et al. [47] have proposed geodesic active contours as a connection between snakes and geometric curves. Unger et al. [48] have extended this approach with GPU usage to improve performance.

Other extensions focus on performance optimizations. In 1999, Adalsteinsson and Sethian [49] have proposed to only calculate the speed function for a narrow band around the current contour. Whitaker [50] showed a computational method (sparse-field algorithm) that combines the level sets approach with the efficiency and accuracy of parametric representation. A solution to use level sets without the need of solving PDEs has been proposed by Shi and Karl in 2005 [51]. Meziou et al. [52] have presented an approach that uses fractional entropy applicable for cell nuclei segmentation.

4 Discrete Deformable Models

Unlike snakes and level sets, discrete deformable models do not use a continuous representation of their surface. Instead, they are modeled using particles or meshes (see Sect. 4.4.2). In a discrete deformable model, forces are calculated in an iterative process and applied to the particles or vertices in the mesh. Several physical and numerical schemes can be used for this purpose, while an abort criterion terminates the segmentation. When dealing with meshes, special attention has to be paid to local resampling, topology adaptation and the avoidance of (self-) intersections and collisions. Kainmueller et al. [53] proposed coupled deformable models. They exploited redundant structures that appear when segmenting multiple connected objects in parallel. They demonstrated a model for femur and ilium that reduces the need for expensive self-intersection testing. In their approach, the logical relationship can be retained using combined intensity profiles.

Fig. 4.2
figure 2

Process of the iterative deformation of a surface using forces

Full size image

Bredno et al. [54] gave a description of the components needed for a discrete deformable model. It consists of a surface, forces, a surface resolution adjustment approach and an abort criterion. In an iterative process, forces are calculated and applied. Afterwards the surface is adjusted. The iteration end is defined by the abort criterion. This process is illustrated in Fig. 4.2. The calculation of forces, e.g. the ones described in Sect. 4.7, is the first step. If a force is calculated for an edge or a triangle, it has to be distributed to the corresponding vertices. The next step is the movement of the vertices. The translation of each vertex is determined according to the selected numerical implementation. If the volume or shape of the models changes significantly, resampling processes are often needed. They adjust the mesh to ensure the geometrical quality of the triangles and modify the mesh in a way that triangles are small enough to fit through the desired structures. For example, the segmentation of a small vein needs a constant refinement as the model grows along the tubular structure. In a final step, a check is performed to see if the iteration process should be terminated. This can be triggered for example after a certain number of steps or once the vertices have reached equilibrium.

4.1 Implementation

There are several possibilities to implement the physical properties of a discrete deformable model. The forces may be modeled directly or as hookean spring forces, as presented by Gilles and Magnenat-Thalmann [55] and Schmid [10]. In their formulation, a translation from the point \(x_i\) to \(x_j\) is weighted by a factor \(\alpha _h\):

$$\begin{aligned} F_\mathrm {h} = \alpha _\mathrm {h} (x_j - x_i) \end{aligned}$$
(4.7)

A common approach to describe the forces is by applying Newtonian physics, but a popular alternative is to use Lagrangian dynamics [11]. Other approaches include the Finite Difference Methods (FDM) [2] and Finite Element Methods (FEM) [25, 56–58].

4.2 Mesh Types

Simple segmentation algorithms often create point clouds as a result. To initialize a deformable model, an initial shape has to be provided, which can be derived from point clouds. The conversion from a point cloud can be done using the marching cube algorithm as proposed by Lorensen and Cline [59] in 1987. The resulting mesh will be closed but also will contain a high number of faces, higher than needed in most cases. In this case, reduction techniques can be applied, but they will have an impact on the mesh quality. Miller et al. [60] have proposed another approach, the Geometrically Deformable Model (GDM) in which the mesh of a deformable model is grown into the point cloud. This results in a lower number of triangles while preserving the topology and details. Most discrete deformable models use traditional triangle meshes. Delingette [61, 62] proposed to use a simplex representation to store the model geometry. A n-simplex mesh contains vertices that all have n+1 distinct neighbors. Using 2-simplex meshes (each vertex has exactly 3 neighbors), arbitrary topologies can be represented. Faces can have an arbitrary number of vertices and can be non-planar. A comparison between simplex and triangle meshes is shown in Fig. 4.3. Simplex meshes have been used for example in the segmentation of cardiac structures by Montagnat et al. [63] and for musculoskeletal structures in the lower limb by Gilles [64].

Fig. 4.3
figure 3

Triangle (a) and simplex (b) meshes

Full size image

To improve iteration performance, Lachaud and Montanvert [65] proposed a coarse to fine model while Snel et al. [11] have demonstrated a multi-resolution scheme. Pons et al. [66] demonstrated an implicit triangular mesh that performs a delauney triangulation on-the-fly when needed. A permanent connection through tessellation has been presented by Gilles et al. [67].

4.3 Particle Systems

A different approach to discrete deformable models are particle systems which operate mesh-less. A collection of independent particles get assigned physical properties, such as mass, position, speed and acceleration and evolve according to classical Newtonian mechanics.

Particle system can represent arbitrary topologies but pose a great challenge when it comes to visualization and the definition of surfaces. Szeliski and Tonnensen [68] have proposed to use oriented particles to represent surfaces. They use several techniques to derive a surface from the particles. This approach has been extended by Lombardo [69] to define curvature and to get an implicit surface description.

5 Knowledge-Based Deformable Models

Deformable models require initial shape information to achieve better results. Knowledge-based deformable models are a group of approaches that aim to invoke more prior knowledge through additional features. This increases the flexibility in poor images and the robustness against inaccurate initializations. A comprehensive overview of knowledge-based deformable models has been given by Schmid [10] in 2011. A simple approach would be assigning labels with an associated behavior to the model. Other models use the statistical or probabilistic variation of selected features. In this section, possibilities for feature selection are discussed, followed by the alignment process and construction of the statistical model. We conclude with the description of the two main approaches: active shape models and active appearance models.

5.1 Feature Selection

Features select the property of the models that will be exploited. They can be summed up in three categories: shape-, appearance- and transformation-based features.

5.1.1 Shape-Based Features

Cootes et al. [70, 71] have proposed shape-based features in 1994. They use prior shape information to improve results and limit shape variability to the shape variations from training data. A set of points, called landmarks, represents image features. They have to be (usually manually) selected from a large number of training data. Another approach for these point distribution models (PDM) can be used to replace landmarks with parameters of a medial axis [72].

5.1.2 Appearance-Based Features

To exploit image properties, appearance-based features can be intensity, gradient, texture, momentum, etc. Intensity profiles (IP, see Sect. 4.7.2.1) are very important and commonly used. In 3D, appearance-based features suffer from an increased complexity (highly increased memory consumption and computational effort).

5.1.3 Transformation-Based Features

A third group of not very common approaches are transformation-based features. They exploit transformation parameters that can be used for the statistical deformation model. They have been extended to also support non-rigid transformations.

5.2 Construction

The creation process of statistical or probabilistic models of feature variation can be divided into two parts. Initially, the training models have to be aligned before the construction can be performed.

The alignment process aims at eliminating pose changes that are not feature related. To do this, commonly the iterative generalized Procrustes approach [73] is applied.

$$\begin{aligned} T^* = {\underset{T}{\text{ argmin }}}\,\,\sum \limits _i \,\, \left| \left| y_i - T(x) \right| \right| ^2 \end{aligned}$$
(4.8)

The transformation \(T^*\) is obtained by finding a transformation that minimizes the distance between a model \(x\) and all other models \(y_i\). The resulting transformation \(T^*\) is combination of a translation, a rotation and scaling. Once this transformation is applied, all models are in a common coordinate frame: the model space of the point distribution model. Although aligned, these models still have a substantial amount of shape variability.

The actual construction process uses the corresponding and aligned features and performs a principal component analysis (PCA). PCA has been introduced by Pearson [74] in 1901. This technique has been used for the point distribution model (PDM) by Cootes and Taylor [70]. Given \(n\) shapes \(Y_1\),\(Y_2\),..., \(Y_n\), the mean shape can be defined as

$$\begin{aligned} \overline{Y} = \frac{1}{n} \sum \limits ^n_{i=1}Y_i. \end{aligned}$$
(4.9)

The covariance matrix is defined as

$$\begin{aligned} S = \frac{1}{n-1} \sum ^n_{i=1}(Y_i-Y)(Y_i-Y)^T \end{aligned}$$
(4.10)

and its eigenvectors correspond to the largest eigenvalues of \(S\). The eigenvectors describe the most significant variation modes from which a subset (much smaller than the number of points) is used.

This approach needs a sufficiently high number of training models. Otherwise a poor generality is given, leading to poor adaptation to new data and enforcement of an over-constrained behavior. Approaches to solve this problem include Bayesian inference [75], synthetic shape variations [76] or the derivation of new artificial shapes from existing training shapes [77].

5.3 Active Shape Models (ASM) and Active Appearance Models (AAM)

Active Shape Models use a statistical model of shape feature variations. To implement them, a model fitting process constrains movement to the modes defined by the trained models. In each iteration step of this process, the closest parametric model to the model \(X\) with the deformation \(dX\) is searched for and forces are applied to deform the model towards this shape. Given the model shape \(Y\), the model \(X\) can be represented as follows:

$$\begin{aligned} X = MY + X_c \end{aligned}$$
(4.11)

with \(M\) being the matrix for scaling and rotation and \(X_c\) the translation vector of the center of \(X\). The estimation of the pose adjustment can be done efficiently using a standard least-squares approach as described in [71]. An example for the segmentation of lung and cerebellum using ASMs is given by Ginneken et al. [78]. Lamecker et al. [79] presented an approach to use ASMs for the segmentation of the bony orbit.

Active Appearance Models have been proposed by Cootes et al. [80] in 1998. They combine a statistical model of the shape and the gray-level appearance. This extends the models for shape \(X_s\) with another one for the image texture \(X_t\), assuming that all textures have been warped to the mean shape. Olabarriaga et al. [81] have presented the use of AAMs for thrombus segmentation; Shen et al. [82] have extended the approach to active volume models.

6 Other Deformable Models

In this section we will give a short overview of other types of deformable models that fall outside the classification described so far. We will discuss deformable Fourier models, the modal analysis, deformable superquadrics and graph-cut approaches.

6.1 Deformable Fourier Models

In 1992 Staib and Duncan [83] have proposed to use a Fourier representation for deformable contours and surfaces. In the following we will take a look at a closed Fourier contour, described as:

$$\begin{aligned} X(s) = \left[ \begin{array}[]{c}X(s)\\ Y(s)\end{array}\right] = \left[ \begin{array}[]{c}a_0\\ c_0\end{array}\right] + \sum \limits _{k=1}^{\infty }\left[ \begin{array}[]{cc}a_k &{} b_k\\ c_k &{} d_k\end{array}\right] \left[ \begin{array}[]{c}\cos 2 \pi k s\\ \sin 2 \pi k s\end{array}\right] \end{aligned}$$
(4.12)

with the Fourier coefficients \(a_0,c_0,a_k,b_k,c_k,d_k\). They are defined as

$$\begin{aligned} \nonumber a_0 = \frac{1}{2\pi }\int \limits _0^1{X(s) \, ds}, \quad&a_k = \frac{1}{\pi }\int \limits _0^1{X(s)\cos 2\pi k s \, ds},\\&b_k = \frac{1}{\pi }\int \limits _0^1{X(s)\sin 2\pi k s \, ds} \end{aligned}$$
(4.13)

A smooth representation can be obtained by truncating the series. The shape translation is defined by the coefficients \(a_0\) and \(c_0\). The subsequent terms follow the parametric form of an ellipse and can be mapped to the standard properties of an ellipse [84]. The parameters follow scale ordering, with low indices for global properties and high indices describing local deformations.

To incorporate prior knowledge, Staib and Duncan [83] use a Bayesian approach. A prior probability approach is defined by manual delineation and the consequent parameterization of Fourier coefficients using a converted ellipse parameter set. In this way, a mean and variance can be calculated for each parameter.

6.2 Deformable Models Using Modal Analysis

Modal analysis has been introduced by Pentland and Horowitz [85]. Deformable models using it are similar to deformable Fourier models but their basis functions and nominal values are derived from templates. The objects consist of finite elements, stacked in the vector \(X\). Displacements are stored in \(U\), so that the new state after a deformation step is given by \(X+U\). They are constrained using the following differential equation

$$\begin{aligned} M\frac{d^2U}{dt^2} + C \frac{dU}{dt} + KU = f \end{aligned}$$
(4.14)

with \(M\) as mass, \(C\) as damping and \(K\) as stiffness matrix. The vector \(f\) contains the external forces and \(f\) and \(U\) are defined as functions of time.

6.3 Deformable Superquadrics

To incorporate local and global shape features, Terzopoulos and Metaxas [58] have proposed deformable superquadrics. These deformable models use a superquadric surface. While global deformations have a large influence on the global shape characteristics, local deformations capture the details. Local and global deformations are being performed in parallel. The closed surface \(x(u)\) in parametric coordinates \(u = [v,w]\) is expressed as:

$$\begin{aligned} x(u) = c + Rp(u) \end{aligned}$$
(4.15)

with \(c\) a translation vector and \(R\) a rotation matrix. The model shape is expressed by \(p(u)\) and is the sum of the reference shape \(s(u)\) and the local deformations \(d(u)\). Superquadrics are a popular extension to quadrics and can model many shapes with few parameters. Examples for superquadrics are superellipsoids, which are described in Ref. [86].

6.4 Graph-Cut-Based Approaches

Graph cuts are used to efficiently solve computer vision problems through global optimization. A formulation as energy minimizing approach (e.g. in level sets) can be reduced to the maximum-flow problem. Ababneh et al. [87] have presented an application of this approach for the segmentation of the knee bones in MR images. Zhou et al. [88] have presented a graph-cut-based method for industrial image segmentation. Zhu-Jacquot et al. [89] have proposed a method to combine graph-cuts with statistical shape priors. A similar approach has been presented by El-Zehiry et al. [90]. Chen et al. [91] have demonstrated a combination of graph-cuts and active appearance models to get more accurate segmentation results.

Vineet and Narayanan [92] demonstrated how to calculate graph cuts on the GPU. Their approach achieves a better performance as it exploits the highly parallel structure of GPUs for concurrent calculation. Another optimization has been proposed by Delong and Boykov in 2008 [93]. Their approach reduces the memory requirements for large data sets and achieves a near linear increase in computational speed with respect to number of processors in multi-core systems. Lee et al. [94] have proposed Branch-and-MinCut in 2010. This approach combines graph cuts and other techniques like branch-and-bound to allow a global optimization for a wide class of energies. This can be used to include shape- or color-distribution priors.

7 External Forces

The deformation of the model is determined by forces. They bridge the gap between the model with its internal forces and the image domain. Over the years these external forces have evolved from intensity or gradient based image forces to complex approaches using statistics or vector flow techniques. In this section we will present some basic forces that are commonly used in deformable models. Advanced forces follow as an extension. We conclude with the description of interactive forces. All following forces will be calculated for a vertex \(x\) with the normal \(n_x\) and will be scaled by a factor \(\alpha \).

7.1 Basic Forces

7.1.1 Pressure Force

In areas with low image information, the model tends to stay at its current position as there are no image features to attract it. To overcome this issue and to reduce the need for very close initialization, Cohen et al. [95] have proposed a balloon or pressure force.

$$\begin{aligned} F_{\mathrm {pressure}}(x) = \alpha _{\mathrm {p}} n_x \end{aligned}$$
(4.16)

It evolves the model along its surface normals and depending on the sign of \(\alpha _{{\mathrm{p}}}\) the model can either shrink or expand.

7.1.2 Laplacian Smoothing Force

Image noise or artifacts may stop small parts of the model. To prevent this from happening, model smoothing can be applied. An example for a common approach is the Laplacian smoothing:

$$\begin{aligned} F_{\mathrm {smooth}}(x) = \alpha _{\mathrm {s}} \frac{1}{|U_x(\varDelta )|}\sum \limits _{y \in U_x(\varDelta )} y-x \end{aligned}$$
(4.17)

It calculates the centroid of the neighboring vertices and defines a force towards that point. Improvements have been proposed by Shen et al. [96]. Figure 4.4 shows an example for smoothing (transformation from cube to sphere) and pressure force (growing).

Fig. 4.4
figure 4

The combination of pressure force and smoothing transforms a cube into a sphere

Full size image

7.1.3 Simple Image Force

A simple approach to include image features is the use of normalized intensity gradients that, for example, can be calculated using central differences. Along the vertex normal, several gradients are being calculated and the force will be directed towards the higher gradients:

$$\begin{aligned} F_{\mathrm {image}}(x) = - \alpha _\mathrm {i} n_x \sum \limits ^{\delta _{max}}_{\delta _{min}} k(\delta ) * \varPhi ( x + \delta \cdot n_x) \end{aligned}$$
(4.18)

where \(k(\delta )\) is a weighting factor with respect to the distance \(\delta \) and \(*\) is the convolution operator. An image interpretation factor \(\varPhi \) can be calculated, in this case the gradient.

7.2 Advanced Forces

The basic forces can be extended by more advanced approaches to improve results and runtime.

7.2.1 Image Intensity Profiles

Instead of simply using the image gradient, intensity profiles can be used to compare the intensity curve along the normals. By doing so, the desired structure can be described more powerful and it allows a distinction between noise-induced gradients and targeted edges. This approach is commonly used [70, 97, 98]. To reduce the complexity of the high number of intensity profiles, clustering has been proposed. For instance, Chung and Delingette [99] have proposed an Expectation-Maximization-based algorithm for clustering and classification. An example of image intensity profiles in a magnetic resonance (MR) image of the femur is shown in Fig. 4.5.

7.2.2 Multiscale Gaussian Potential Force

The Gaussian Potential Force is designed to attract a model towards image features and is defined as

$$\begin{aligned} F_\mathrm {g}(x) = \alpha _\mathrm {g} |\nabla [G_{\sigma }(x) * I(x)]|^2 \end{aligned}$$
(4.19)

with I(x) the intensity image, \(G_{\sigma }(x)\) a Gaussian function, \(\alpha _g\) a weight and \(*\) the convolution operator. This force has been extended by Terzopoulos et al. [100] to a multi-scale scheme. To overcome the need of an initialization close to the final contour, they propose to use a large initial value of s to broaden the search space. Once equilibrium has been reached, \(\sigma \) could be decreased to maintain the accuracy of the original approach. Until now, no criterion has been established to determine when to reduce \(\sigma \), limiting the utility of the multi-scale gaussian potential force.

Fig. 4.5
figure 5

Example of intensity profiles sampled in an MR image of the femur

Full size image

7.2.3 Distance Potential Force

To extend the attraction range, Cohen and Cohen [57] have proposed to use a dis-tance map in 1993. The values in this map are obtained by using either the Euclidian distance [101] or Chamfer distance [102] to calculate the distance between a voxel and the closest boundary point.

7.2.4 Dynamic Distance Force

This force extends the distance potential force to include a larger spatial area around the surface [103, 104]. The dynamic distance has improved handling of boundary concavities. It is calculated by examining the image for features or gradients along the surfaces normal. The maximal search distance is limited by a threshold \(D_{\mathrm {max}}\).

$$\begin{aligned} F_{\mathrm {dynamic}}(x) = \alpha _\mathrm {d} \frac{D(x)}{D_{max}} n(x) \end{aligned}$$
(4.20)

The resulting force can pull the model towards distant image features. Nonetheless, the search is very time consuming and has to be repeated in every step. Lowering the threshold can shorten the runtime but also reduces the attraction range for image features.

7.2.5 Gradient Vector Flow

In 1998, Xu and Prince [27] have proposed a new external force model. Their Gradient Vector Flow (GVF) field is calculated as the diffusion of an intensity image. It allows a more flexible initialization and supports a more efficient convergence to concavities.

Ng et al. [105] present a medical image segmentation that uses a feature-based GVF snake. The iteration is stopped once the accuracy is sufficient by exploiting image features. Zhao et al. [106] have improved the dynamic GVF force field and introduced a strategy of deformable contour knots for a B-spline based model.

7.2.6 Omnidirectional Displacements

When working with deformable surfaces, forces are commonly directed along a line, usually the surfaces local normal. Kainmueller et al. [107] have proposed omnidirectional displacements for deformable surfaces (ODDS) that consider a sphere around each vertex. By doing so, a global optimization can be performed. This technique has been proven to be useful in regions of high curvature, e.g. tips. They have also proposed a hybrid approach, fast ODDS to overcome the high memory and runtime requirements.

7.3 Interactive Forces

Image artifacts, different protocols and implants can cause problems in automated segmentation of medical images. In a clinical environment, operators can provide guidance to the deformable model to overcome these problems. The so called interactive forces provide a link between real-time user input and model iteration.

Kass et al. [20] have proposed two interactive forces. Spring forces are designed to pull the model in the direction of a point \(p\). Their strength is proportional to the distance from \(p\):

$$\begin{aligned} F_{\mathrm {spring}}(x) = \alpha _{\mathrm {s}}(p-x) \end{aligned}$$
(4.21)

The opposite effect can be achieved using volcano forces. They push a model away from a point \(p\):

$$\begin{aligned} F_{\mathrm {volcano}}(x) = \alpha _\mathrm {v} \frac{r}{|r|^3} \end{aligned}$$
(4.22)

with \(r = x-p\). Interaction forces often are only computed for a small neighborhood to reduce computational costs. When using all points the complexity is of order \(O(n^2 )\), while a small neighborhood m with \(m \ll n\) can reduce the complexity to order \(O(n \cdot m)\).

8 Initialization

All the previously presented approaches for segmentation require the placement of an initial model in the proximity of the desired boundaries. In this section we will present several possible approaches: manual and landmark-based initialization as well as automatic methods using the general Hough transform and atlas registration.

8.1 Manual Initialization

A simple approach to initialization is to ask the user to place the model manually. This can be done by using several interaction tools such as the mouse, keyboard or haptic devices. The manual placement is a time-consuming process and requires an experienced user, depending on the quality of the images. Nonetheless, this approach is not usable for large-scale applications. It also reduces the reproducibility, as the results often depend on the initial model and expertise of the user.

8.2 Landmarks

The use of landmarks is an extension of the manual approach. Instead of translating and scaling the whole model, the user selects a set of strong landmarks in the image and the initial model is automatically adjusted to obtain the best fit. In this way, the user input and hence the margin of error can be significantly reduced. Landmarks should be positioned at significant areas that can be easily detected in the image. Examples would be areas of high curvature, e.g. a fissure in a bone, or a measurable location, e.g. the middle of the femural shaft. An initialization of a model using seeds has been proposed by Neuenschwander et al. [108]. The correct scaling and positioning of the model has to be determined from the seeds. This warping can be done using the Thin Plate Spine (TPS) transform. If the number of landmarks is very small and not sufficient for a confident pose estimation, different positions can be evaluated using a cost function that incorporates a penalty based on image properties. An example for that can be found in Ref. [10].

Using landmarks at key anatomical positions allows the invocation of prior knowledge. Other approaches extend landmarks with inclusion of spatial knowledge. For example, Fripp et al. [109] proposed a cartilage initialization system that exploits prior knowledge of the bone location.

8.3 General Hough Transform

In 1962, Hough [110] was granted a patent for Method and Means for Recognizing Complex Patterns. His approach uses templates and a voting space. For each identified image feature all templates create votes for possible poses. The highest vote represents a set of parameters of the best corresponding template. An example with original image and voting space is shown in Fig. 4.6. Illingworth and Kittler [111] have presented a review of the Hough transform and Khoshelham [112] has demonstrated an extension to 3D object detection.

Fig. 4.6
figure 6

Example of the Hough Transform for lines. Original image (left) and voting space (right)

Full size image

The general Hough transform can be used for the initialization of deformable models. Van der Glas et al. [113] have demonstrated a method to detect ball joints. Seim et al. have proposed approaches for the hip [114] and the knee [115]. In 2010, Ruppertshofen et al. [116] have proposed a discriminative approach for lower extremities, which has been extended to a multi-level scheme [117].

8.4 Atlas Registration

Rather than using a reference model, a reference image (called atlas) can be used. The atlas contains a specific initialization. A registration step tries to find the transform \(T\), that matches the reference image to the actual image. \(T\) can then be used to transform the initialization to the actual image.

Atlas-based initialization requires a registration process, e.g. using ElastiX [118]. Another requirement is the subjects pose, which has to be same in each image to get satisfactory results. Examples for atlas registration based initialization have been proposed by Fripp et al. [119, 120].

9 Conclusion

We have presented an overview of the current state of deformable models in medical image segmentation. They are a powerful tool for the given image conditions and therefore play an important role. We have surveyed current snakes and level sets methods that are examples for continues shape representation. These usually two-dimensionally used approaches achieve good results with high computational costs. However, they are highly dependent on a good initialization. Contrary to snakes, level sets are able to adapt to different topology automatically. Discrete deformable models are three-dimensional approaches, which can be represented as particle systems or through different mesh types. They can also be based on several physical foundations. They provide great flexibility and haven proven useful in many cases. Depending on the structure of interest, deformable models have to be carefully configured and parameterized. An extension to deformable models is the incorporation of prior knowledge to make them more robust in complex image conditions. These knowledge-based deformable models exploit prior knowledge on shape and appearance. They need a large training base and complex training but are very robust. We have presented several forces that cover the tools needed for creating deformable models. We have also extended the view by presenting other deformable model approaches. Lastly we have presented the main approaches to the important initialization problem.

A challenge for future research is the development of more general approaches. Although very sophisticated and robust, deformable model applications are tuned to specific organs and well-defined image conditions. Knowledge-based models for example have to be trained with a large database of examples and image forces like the intensity profiles have to be recreated if imaging sequences are modified. Depending on the chosen approach, the initialization can be a critical task. Speed and robustness still can be improved.