We now describe a novel approach to make the geometric snake much more tolerant toward weak edges and image noise. It comprises the integration of gradient flow forces with diffused region forces in the image, resulting in the region-aided geometric snake:

• The gradient flow forces supplant the snake with local object boundary information. They play a main role in all active contours4.

• The region forces are based on the global image features and supplant the snake with global image information.

We show that this combination of forces not only improves the performance of the geometric snake toward weak edges, but also makes it more immune to noise. The PDE thus obtained evolves an initial contour toward final convergence under the influence of both internal forces and boundary-regional image forces, and is implemented via level sets.

The proposed region force can be generated from any image segmentation technique. This means that while RAGS is independent of any particular segmentation technique, it is dependent on the quality of the regions produced. However, we show a good degree of tolerance to (reasonable) segmentation quality, and that our snake indeed acts as a refinement of the results of the initial region segmentation. Later in Section 10.7, we introduce the mean shift segmentation technique presented by Comaniciu et al. in [12,13] which is a very elegant method to generate region maps for this work. Results will be presented based on region maps obtained from both the under-segmentation and over-segmentation options of the software from Comaniciu and Meer's study.

4There are notable exceptions to this, e.g. [11].

10.4.1 Gradient Flow Force: A Summary

As mentioned earlier, the gradient flows impose local constraints while the region force contributes global constraints. Within a homogeneous region of an image, measured by region segmentation, the snake evolves mainly according to gradient flows. The first gradient flow is the weighted length gradient flow, which is given by (10.7). It is composed of two terms. The first is the weighted curvature term, g(\VI\)kJv, which smooths the active contour and also shrinks it. The second term, (Vg(\VI\) ■ Jv)Jv, is on the normal factor of the gradient of the weighting function. Unlike the curvature, the vector field Vg(\VI\) is static. The direction and strength of this field depend on position only, and is independent of time and contour.

The second gradient flow, g(\VI\)cJJf, is introduced by constant motion which locally minimizes area (see [14] for proof). It helps the snake shrink or expand toward object boundaries and accelerates its convergence speed.

For all these forces, the weighting function g can be defined as any decreasing function of the image I edge map f such that g ^ 0 as f ^to. When dealing with gray level images, the solution (as used in this work) is straightforward:

This monotonically decreasing nature is illustrated in Fig. 10.2. As for color images, the edge function f becomes a little more intricate (an example function will be presented in Section 10.6). However, the derivation of the decreasing function g can remain the same.

The aim of generating a region force is to empower the snake with a global view of image features. A typical region segmentation method splits an image into several regions, giving the segmentation map S. From this, the region map R is generated by computing the gradient of S. The gradient computation is the same as the edge computation stage for generating gradient forces. Then, we compute the gradient V R of this region map, resulting in region constraints in the vicinity of the region boundaries. Having slithered across a homogeneous region reliant on the gradient flow forces, if the snake tries to step from one region into another, it must concur with the region force in VR since it breaks the region criteria, which probably indicates a leakage. The force field VR has vectors pointing toward the center of the region boundaries. The capture area of this pure region force is quite small: only immediate areas close to region boundaries. The vectors need to be diffused further away from the region boundaries to create a larger capture field. To achieve this, we can diffuse VR resulting in region forces with a larger capture area along the region boundaries. Hence, the region force vector field [R(z) = (u(z), v(z)), z = (x, y)] is obtained by solving the following equations:

j p(|VR|)V2u — q(|VR|)(u —VRu) = 0 [ p(|VR|)V2v — q(|VR|)(v — VRv) = 0 ' .

where V2 is the Laplacian operator with dimensions u and v, p( ) and q ( ) are weighting functions that control the amount of diffusion, and VRu and VRv are the components of vector field VR along the u and v directions5. The weighting functions are selected such that p( ) gets smaller as q ( ) becomes larger with the desirable result that in the proximity of large gradients, there will be very little smoothing and the vector field will be nearly equal to the gradient of the region map. We use the following functions for diffusing the region gradient vectors:

where K is a constant and acts as a trade-off between field smoothness and gradient conformity. The solution of (10.10) is the equilibrium state of the following partial differential equations:

where u and v are treated as functions of time. These partial differential equations can be implemented using an explicit finite difference scheme. An iterative process can be set up and guaranteed to converge with the following constraint

4 pmax

5 Theoretically, VR can be diffused in any two orthogonal directions, u and v, within the image domain. However, practically we will only choose x and y directions corresponding to image plane coordinates. Thus VRu and VRv are equal to ^ and ^ respectively.

Figure 10.12: Region force diffusion—top row: A synthetic image with additive Gaussian noise, region segmentation map, region boundary map R, and gradient of the region map R (and a small selected area)—bottom row: diffused region vector field, and close-up views in the small selected area of the vectors in the gradient of region map and the diffused region vector field respectively.

Figure 10.12: Region force diffusion—top row: A synthetic image with additive Gaussian noise, region segmentation map, region boundary map R, and gradient of the region map R (and a small selected area)—bottom row: diffused region vector field, and close-up views in the small selected area of the vectors in the gradient of region map and the diffused region vector field respectively.

where Ax and Ay are the spatial sample intervals, pmax is the maximum of p( ), and At is time step, the interval between time tn and time tn+1 when iteratively solving (10.12).

From (10.11) and (10.12) we note that within ahomogeneous region, based on the criteria of region segmentation, p( ) equals 1 while q ( ) equals 0. Thus (10.12) is only left with the first term (as the second term vanishes). This effectively smooths the vector field. However, at the region boundaries, p() ^ 0and q () ^ 1. The smoothing term imposes less and the region vectors are close to the gradient of the region map R. Thus the diffused region vector field provides the evolving snake with an attracting force in a sufficiently large range near the region boundaries, and also allows the snake to evolve solely under other gradient forces.

Figure 10.12 illustrates an example of region force diffusion, including close-up views of pre- and post-diffusion vector field.

Next, we can derive the region-aided geometric snake formulation. The standard geometric snake is given by (10.8). In the traditional sense, the snake forces fall into two types, internal forces and external forces. The internal forces impose regularity on the curve and control the elasticity and rigidity of the snake. The external forces pull the snake toward salient image features such as object boundaries. Thus, the internal and external forces in (10.8) can be written as

where g() is the stopping function as before. The first term of the external forces is a constant shrink or expand force in the normal direction of the snake. It can be separated from other external forces in the sense that it is not spatially static in the image domain as other external forces and needs different numerical schemes. However, considering the previous definition of snake forces and that the constant force alone can push the snake toward boundaries, we keep it in the external term.

The diffused region force is a feature driven force and spatially static. So we can add the diffused region force to the external term:

where RR is the region force vector field obtained in (10.10) and a is anew constant incorporating c. Constants a and 0 act as a trade-off between gradient forces and region forces. In practice, 0 is a constant from 0 to 1 for most nonhighly textured images. If good segmentation results are available, 0 should be set close to 1.

The snake evolves under all the internal and external forces. However, only the forces in the normal direction of the evolving contours can change the geometry. The forces tangential to the contours can only change the parameterization of the contours. Thus, a geometric snake evolving under internal and external forces can be interpolated as

Finally, by substituting (10.15) into (10.16), the region-aided geometric snake formulation becomes

Ct = [g(|V I |)(K + a) — Vg(|V 11) ■ jj + 0 R ■ N]N.

10.4.4 Level Set Representation

In this section, we outline the level set representation for the region-aided geometric snake. Level sets describe a moving front in an implicit function and are the basis for the numerical algorithm for curve evolution according to functions of curvature, introduced by Osher et al. [15,16]. In the application to active contours, the evolving contour is embedded into a higher dimensional surface as a zero level set. The entire surface, the level sets, is an implicit representation of the embedded contour. As shown in Fig. 10.13, the snake is initially built in a three-dimensional surface, which later evolves according to underlying forces. Finally, the converged snake is extracted from the level sets by cutting it at zero height.

Let C be a level set of a function of fa : [0, a] x [0, b] ^ That is, C is embedded into the zero level set with fa being an implicit representation of the curve C. This representation is parameter free and intrinsic. Given a planar curve that evolves according to Ct = FN for a given function F, the embedding function should deform according to fat = F|Vfa|, where F is computed on the level sets. By embedding the evolution of C in that of fa, topological changes

of C are handled automatically and accuracy and stability are achieved using numerically stable computations.

The internal curvature and external pressure terms of the RAGS formulation in (10.17) can be easily transferred to a level set representation:

j Ct = g(|VI|)k J ^ & = g(|VI|)k|V&| (10 18)

[Ct = g(|V I DaJJT^ & = g(|V I |)a|V & |' .

The other external forces in (10.17) are static vector fields derived from image data which do not change as the active contour deforms. Static force fields are defined on the spatial positions rather than the active contour itself. Since JJ is the inward normal, the level set representation of the inward unit normal is given by

Then, we have

Combining (10.18) with (10.20) where F takes on the static force fields, the level set representation of RAGS is given by

& = g(|VI|)(k + a)|V&| + Vg(|V11) -V& - 3R ■ V& (10.21)

where g( ) is the stopping function as before. The expression for the curvature of the zero level set assigned to the interface itself is given by

.. / V& \ &xx&y - 2&y&x&xy + &yy&x K = div - = -----T-7--Z--(10.22)

Was this article helpful?

## Post a comment