4 Deformable Models and Level Sets in Image Segmentation

65

Fig. 4.3 Additional force provided by Gradient Vector Flow for synthetic image segmentation; (a) Initial contour defined as a circle in the image; (b) Vector flow visualization derived from the image; (c) Segmentation result using Gradient Vector Flow: the snake captures the desired object; (d) Segmentation result without additional force

4.2.1.2 Snake Optimization Method

Image segmentation using an active contour is formulated as a process of energy minimization that evolves the contour. This minimization controls the model deformation to reach the desired segmentation result. The term “snake” comes from the “slip and slide” movement of the contour during this minimization process.

66	A. Alfiansyah

Fig. 4.4 Local neighborhood in optimization using a greedy algorithm. The energy function is evaluated at vti−1 and each of the neighbors, using vti−1 and vti−+11 to compute the internal energy terms. The location with lowest energy is chosen as the new position vti

Greedy Algorithm

Using greedy algorithms optimization finds the solution incrementally by choosing at each step the direction which is locally the most promising for the final result, i.e. which provides larger energy decrease.

Figure 4.4 illustrates the optimization procedure using a greedy algorithm. The energy function at the current point νit−1 and each of its neighbors is computed under consideration of adjacent contour points νit−1 and νit+−11. The location with the smallest energy value is chosen as the new position of νit . The previous point νit−1 has already been updated to the new position in the current iteration over the contour, while νit+−11 will be updated next.

At the first stage of the algorithm, all contour points are sequentially updated within one iteration. At the second stage, the forming of corners is determined by recalculating the rigidity energy terms with the updated points, and also by adjusting the weighting rigidity parameter w2 for each contour point accordingly.

Dynamic Programming

Dynamic programming minimization was presented by Amini [20] to solve the variational problem in energy minimization of active contour models. Dynamic programming is different from variational optimizations in the sense that it ensures a globally optimal solution with respect to the search space and numerical stability by moving the contour points on a discrete grid without any derivative numerical approximations. The optimization process can be viewed as a discrete multi-stage decision process and is solved by a time-delayed discrete dynamic programming algorithm. Dynamic programming bypasses local minima as it embeds the minimization problem in a neighborhood-related problem. This is achieved by replacing

4 Deformable Models and Level Sets in Image Segmentation

67

the minimization of the total energy measurement by the minimization of a function of the form:

E(ν0, ν1, ν2 . . . νn−1) = E1(ν0, ν1, ν2) + E2(ν1, ν2, ν3)

+E3(ν1, ν2, ν3) + ···+ En−2(νn−1, νn−2, νn−1).

(4.9)

S(ν

, ν ) = min ν

i−1

S

i−1

(νi, ν

i−1

) + E

elast

(ν

i−1

, νi) + E

rigid

(ν

i−1

, νi, ν

i+1

)

i+1

1

ν1

+Eext(νi).

(4.10)

Apart from the energy matrix corresponding to the optimal value function Si, a position matrix is also needed so the value of νi minimizing equation (4.10) can be stored. The optimal contour of minimum energy Emin(s) can be then found by back-tracking from the end position represented in the matrix.

This process is iterated until the active contour finds an energy that does not change significantly. It consists of a forward pass to determine the minimum energy values for each νi and a backward pass to find the minimum energy path in the position matrix.

Similar to minimization using the greedy algorithm, dynamic programming allows hard constraints (e.g. minimum distance between snaxels) on the behavior of the global minimum solution directly and naturally. The other advantage of this method comes from the execution time and the required memory. The complexity of this method is O(mn) with O(mn2) memory required, where n is the number of points on the contour and m is the number of potential locations in the search space to which every point is allowed to move during one optimization step.

Variational Method

This approach is based on the Euler–Lagrange condition in order to derive a differential equation that can be solved to minimize the snake energy. For each iteration, an implicit Euler forward step is performed with respect to the internal energy, and an explicit Euler step with respect to the external image and constraints energy terms.

The basic deformable model (in (4.2)) can be rewritten as:

E(C(s)) =	1	w	(s) C (s)		2 + w	(s) C (s) 2		ds +	E		(C(s))ds. (4.11)
Ω	2	1	|	|	2	|	|		Ω	ext

Representing the integrand by E(s,C ,C ), the necessary condition for the variation to locally minimize E(C(s)) must satisfy the following Euler–Lagrange equation:

− (w1(s)C ) + (w2(s)C ) + Eext(C(s)) = 0.

(4.12)