![](https://csdnimg.cn/release/download_crawler_static/15168927/bg3.jpg)
QIN et al.: GENERALIZED GRADIENT VECTOR FLOW FOR SNAKES 885
robustness to noise, which is defined as the equilibrium
solution of the following partial differential equation:
v
t
(x, y, t)=g(|∇f |)∇
2
v(x, y, t) − h(|∇f |)[v(x, y, t) −∇f ]
(10)
where
g(
|
∇f
|
)=exp(−
|
∇f
|
k) (11)
h(
|
∇f
|
)=1− exp(−
|
∇f
|
k). (12)
The parameter k regulates to some extent the tradeoff between
the first term (known as smoothing term) and the second term
(known as data term) in the right-hand side of (10) and it
should be set according to the amount of noise in the image
(larger k for higher noise levels).
2) Numerical Implementation: As in [26], the partial
differential equation (10) specifying the GGVF field can be
implemented using an explicit finite difference scheme. In
(10), |∇f | can be calculated using any digital image gradient
operator, e.g., simple central differences employed in this
paper. Since the data term in (10) is defined to encourage the
GGVF field to be close to the edge map gradient computed
from the image, its weighting coefficient h(|∇f |) must be
greater than or equal to 0. According to (12), the parameter k
must be greater than 0.
To set up the iterative solution, let the spatial sample
intervals be x and y and the time step for each iteration be
t. The partial derivative v
t
(x, y, t) can then be approximated
as [v(x, y, t + t) − v(x, y, t)]/t. On a discrete grid, the
Laplacian term can be approximated by
∇
2
v
(
x, y, t
)
=
1
xy
A ∗ v
(
x, y, t
)
(13)
where A =
010
1 −41
010
is the Laplacian matrix.
Substituting the above approximations into (10) gives an
iterative solution to the GGVF field as follows:
v(x, y, t + t)= v(x, y, t)+
t
xy
g(|∇f |) A ∗ v(x, y, t)
−th(|∇f |)[v(x, y, t) −∇f ]. (14)
According to the GGVF stability constraint t
(
xy
)
≤
1
4 [26], t must be not larger than 1
4 by making x =
y = 1. To obtain the maximum smoothness of the GGVF
field, we set t =1
4. Accordingly, (14) can be rewritten as
v(x, y, t + t)= v(x, y, t)+
1
4
g(|∇f |) A ∗ v(x, y, t)
−
1
4
h(|∇f |)[v(x, y, t) −∇f ]. (15)
The desired external force field v(x, y, t) is iteratively calcu-
lated from the initial vector field v(x, y, 0) = ∇f , i.e., the
gradient of the edge map. Typically, the iteration number
(denoted as n) required to calculate the GGVF field or the
above GVF field for an n
1
×n
2
-pixel image is
√
n
1
× n
2
[15].
After the iterative process, external forces in actual imple-
mentations are normalized to unit vectors to make the snake
evolve at a constant speed. Typically, the initial GGVF vectors
v(x, y)=[u(x, y),v(x, y)] are normalized with respect to their
magnitudes using
v
vn−ggvf
(x, y)=
v(x, y)/|v(x, y)|, |v(x, y)| =0
[
0, 0
]
, |v(x, y)| =0
(16)
which is referred to as vector-based normalization.
Fig. 1. Performance of GVF and GGVF snakes in detecting an odd-width
LTI. The initial and resulting snakes are indicated by cyan dashed and solid
lines, respectively. The external force fields in the top and bottom rows are
properly and over smoothed, respectively. First column: GVF snakes. Second
column: GVF fields within the LTI. Third column: GGVF snakes. Fourth
column: GGVF fields within the LTI. (a) GVF snake. (b) Properly smoothed.
(c) GGVF snake. (d) Properly smoothed. (e) GVF snake. (f) Over-smoothed.
(g) GGVF snake. (h) Over-smoothed.
D. New Observations on GVF and GGVF Snakes
It was reported in [26] that GGVF snakes outperform GVF
snakes in the convergence to LTIs. GVF’s difficulty of forcing
a snake into an LTI is caused by excessive smoothing of
the field near the LTI boundary, governed by the smoothing
coefficient μ in (9). When a much smaller μ is used, the GVF
snake can also achieve a good convergence to the LTI similar
to that of GGVF, but at the expense of an order of magnitude
higher computational complexity than that of GGVF [26].
However, to our observation, GVF and GGVF snakes yield
almost the same performance in convergence to LTIs. Specifi-
cally, when the LTI width is of an odd number of pixels, both
snakes can converge completely to the LTI if their external
force fields are appropriately smoothed
1
, as reported in [26],
whereas the computational cost required for the GVF field is
almost the same as that for the GGVF field, which is opposed
to the opinion in [26]. However, if their vector fields are over-
smoothed
2
, not only the GVF snake but also the GGVF snake
fails to capture the LTI. On the other hand, when the LTI width
is an even number of pixels, in general, neither the GVF snake
nor the GGVF snake is able to detect the LTI no matter how
their external force fields are smoothed. The following will
further elaborate our observations.
Fig. 1 shows the performance of the GVF and GGVF snakes
in capturing an odd-width LTI. The original image in Fig. 1
is a line-drawing of a square-shaped object (shown in black)
with the odd-width LTI. All resulting snakes indicated by cyan
solid lines are derived from a same initialization indicated by
a cyan dashed line. All fields within the LTI are sampled by
a factor of 3 in the y direction. We find that at almost the
same computational cost, both the GVF snake in Fig. 1(a)
1
The vector field is considered to be appropriately smoothed when k in (10)
is less than a selected value to be discussed in Section IV-B.
2
The vector field is considered to be over-smoothed when k is greater than
the selected value.