ABSTRACT

Image segmentation is an important research area in Computer Vision and the GVF-snake is an effective segmentation algorithm presented in recent years. Traditional GVF-snake algorithm has a large capture range and can deal with boundary concavities. However, when interesting object has deep concavities, traditional GVF-snake algorithm can’t converge to true boundaries exactly. In this paper, a novel improved scheme was proposed based on the GVF-snake. The central idea is introduce dynamic balloon force and tangential force to strengthen the static GVF force. Experimental results of synthetic image and real image all demonstrated that the improved algorithm can capture boundary concavities better and detect complex edges more accurately.

1. Introduction

Active contours model, a tracking method using active curves or surfaces, has been proposed in recent years. It can integrate edge and region information and has been widely used in image segmentation field. The most widely used active contours model include snakes and level set [1]. Snakes were firstly introduced by Kass and its basic idea is to make the initial closed curve (i.e. a sequence of discrete points) converge to the desired edge by minimizing the energy functional [2]. However, the classical snakes have three main disadvantages. The first is topological structure of the curves can’t change flexibly. Secondly, the initial curve only converges steadily when it lies close to the desired edge. Thirdly, it is not easy to handle boundary concavities. To solve the first problem, McInerney et al. proposed T-snake which not only maintains strong interactivity of the classical snakes but also improves the changing ability of topological structure [3]. Sun et al. introduced adaptive filters to T-snake so that it can deal with several interlaced objects [4]. Zagorchev et al. proposed R-snake based on rotating Gaussian curve [5]. R-snake is capable of changing the curve’s rigidityso object’s shape could be reconstructed smoothly. To the second problem, Cohen et al. has proposed the balloon snake [6] and the distance snake [7]. Both of them increase the capture range of external force field and make the placing of initial curve easy. To the third problem, Xu et al. has introduced the GVF-snake which not only enlarges capture range but also can deal with boundary concavities [8]. Luo et al. presented an additional balloon force to the GVF-snake to prevent the active curve from trapping into local minima [9]. Zhu proposed a nonlinear filtering on GVF force field to further enlarge capture range [10]. Although the GVF-snake has large capture range and considerable ability to handle boundary concavities, it is difficult to realize accurate segmentation when detecting complex shape object with deep concavities. Accordingly, we introduce dynamic balloon force and tangential force to strengthen the static GVF force, and it is found that the capability of capturing concave edges enhanced effectively.

2. Principles and Methods

2.1. The GVF-Snake

Let, represents a curve in image, s is the regularized arc length. The energy function of the snake is as follows:

(1)

where and denote the first and second derivatives of X(s) with respect to s, α and β are weighting parameters that control smoothness and tautness of the snake respectively. External energy is used for moving the snake towards edges or other interesting features. To minimize the energy function, the energy Equation (1) can deduce to the force-balance equation using the calculus of variations, i.e. the Euler equation is as follows:

(2)

The former two terms represent the internal force F_int and the negative gradient of a potential function represents the external force F_ext. When the internal force and the external force reach their balance, the energy functional converges to its minima.

The main difference between the GVF-snake and the classical snake model lies on the different external forces. For the GVF-snake, the external force F_ext is replaced by the gradient vector flow, where is achieved by minimizing the following energy function:

(3)

where, denotes the gradient of edge map and μ is a weighting parameter. μ should choose a large value when the image is noisy. When is small, the energy is dominated by the first partial derivatives, so it is a slowly-varying field. When is large, the second term dominates the energy and energy minima can be achieved by setting.

In order to minimize the energy of Equation (3), it must satisfy the following Euler equation:

(4)

(5)

where is the Laplacian operator. In homogeneous regions, both f_x and f_y are zero. In this case, u and v are dominated by Laplacian equation. Within the boundary regions, the snake mainly performs a “filling in” property. We can get from Equation (3) and set X as function of time X(s,t), the dynamic equation is obtained as follows:

(6)

where V represents static GVF force, is a weighting parameter. When is equal to zero, stable solution of the GVF-snake is achieved.

2.2. The Improved GVF-Snake

The GVF-snake can’t converge to deep boundary concavities accurately, so we propose to design dynamic balloon force and tangential force to strengthen the GVF force to improve the capture ability of desired edges. To demonstrate the effect of the additional forces, Figure 1 shows external forces field of the traditional snake, the GVF-snake and the improved GVF-snake, respectively.

In Figure 1, the circle denotes the desired edge and the arrow denotes the force direction. The curve denotes the active contour and the point on the curve denotes control point. It can be seen that force field of the traditional snake is narrow and very close to the desired edge.

The force field of the GVF-snake showed in Figure 1(b) can effectively enlarge capture range throughout the whole image. Therefore, the GVF-snake can overcome the initialization problem related to the traditional snake. The improved GVF-snake is considered to combine the static GVF force field and two kinds of dynamic forces which are showed in Figure 1(c). The balloon force is used to increase capture range and converging speed of snake, and the tangential force is used to make the snake converge to boundary concavities better.

It is noted that the proposed balloon force and tangential force can change their affect area adaptively. The value of each control point is replaced by the average value of its nine surrounding pixels. It indicates that the control point denoted by squared point is far away from the desired edge when the averaged value is smaller than the given threshold T. In this case, the balloon force pulls snake towards the edge. When the averaged value is bigger than T, it means this control point is close to the edges. In this case, the tangential force is used to approach the edge. At the same time, it can prevent the snake from breaking through weak edges.

If T is choose too large, the balloon force is still affecting nearby the desired edge while the capture range of the tangential force becomes smaller, and it is difficult to avoid boundary leakage. If T is too small, only the tangential force is affected near to the edges, and the snake is hard to converge to deep concave boundary. So the value of threshold T is advised to 0.2 ~ 0.5.

The force balance equation of the improved GVFsnake can be expressed as follows:

(7)

where F_int represents the internal force, represents the GVF force, represents the balloon force, represents the tangential force. They are defined respectively as follows:

(8)

where, and are weighting parameters of the GVF force, the balloon force and the tangential force respectively. N(x,y) represents outward unit normal vector. When the active contour lies inward the desired edge, sign(n) > 0 and the active contour inflates. When the active contour lies outward the desired edge, sign(n) < 0 and the active contour deflates. represents the unit tangential force. Sign(q) is obtained by computing the inner product of and:

(9)

where θ is the angle between and. If θ lies in, and it indicates the two vectors are inconsistent. It is necessary to negate the tangential vector to ensure the snake converging normally. If θ lies in or,. It indicates that the two vectors are consistent and the direction of tangential vector needn’t change. Accordingly, can be expressed as follows:

(10)

then, Equation (7) can be expressed as follows:

(11)

Therefore, the improved GVF-snake is expressed as follows:

(12)

Equation (12) can be quantized and expressed using matrix formation as follows:

(13)

where γ is temporal step-size.

3. Experiments and Results

Experiments were designed to compare segmentation performance of the GVF-snake and the improved GVFsnake. All computation is done under the environment of computer X42J (ASUS Inc.). CPU is 2.00 GHz and RAM is 2 GB. Operation system is Windows XP-SP3 and the programming tool is MATLAB 7.0.

Figure 2 shows a U-shape test image U64.pgm along with an initial circle curve. Image size is 64 × 64. Figure 3(a) shows segmentation procedure of the GVF-snake with maximum iteration number set as 80. Figure 3(b) shows similar segmentation procedure of the improved GVF-snake with same computing parameters as in Figure 3(a) i.e. α = 0.05, β = 0, γ = 1, μ = 0.2, κ₁ = 0.6, κ₂ = −0.15, κ₃ = 0.2, T = 0.3. It can be seen that the improved GVF-snake converge towards the boundary concavities faster than the GVF-snake with 80 iterations. The reason is that the GVF-snake is driven only by the GVF force, while the improved GVF-snake is driven by a combination of balloon force, tangential force and GVF force. Figures 3(c) and (d) show the segmentation results of the GVF-snake and the improved GVF-snake at 125 iterations respectively. For convenient comparison, the boundary concavities section denoted by the rectangle in Figures 3(c) and (d) are zoomed in as shown in Figures 3(e) and (f). It can be seen clearly that the former snake can’t converge to the deep boundary concavity well, while the latter snake converges to the deep boundary concavity more exactly. So, the improved GVF-snake proposed in this paper not only converges to boundary concavity faster than the GVF-snake but also its capture capacity of deep concave edges is also better than the classical GVF-snake.

Figure 4 shows a left clavicle image clavicle.bmp along with an initial manual curve. Image size is 269 × 210. Figures 5(a) and (b) show the results of 200 iterations of the GVF-snake and the improved GVF-snake respectively. The computing parameters are same i.e. α = 0.05, β = 0, γ = 1, μ = 0.2, κ₁ = 0.6, κ₂ = 0.25, κ₃ = 0.5, T = 0.3. It can be seen from Figure 5(a) that the GVF-snake didn’t converge to the thin concave boundary exactly at