Reducing the control by curvature can clearly be desirable for features that have high localized
curvature. This illustrates the mutual dependence between and , since low values of can
accompany low values of in regions of high localized curvature. Setting to zero would
force the snake to ignore image data and evolve under its own forces. This would be rather
farcical. The influence of is reduced in applications where the image data used is known to
be noisy. Note that one fundamental problem with a discrete version is that the final solution
can oscillate when it swaps between two sets of points which both have equally low energy.
This can be prevented by detecting the occurrence of oscillation. A further difficulty is that as
the contour becomes smaller, the number of contour points constrains the result as they cannot
be compressed into too small a space. The only solution to this is to resample the contour.
6.3.3 Complete (Kass) snake implementation
The greedy method iterates around the snake to find local minimum energy at snake points.
This is an approximation, since it does not necessarily determine the ‘best’ local minimum
in the region of the snake points, by virtue of iteration. A complete snake implementation,or
Kass snake, solves for all snake points in one step to ensure that the snake moves to the best
local energy minimum. We seek to choose snake points vs =xs ys in such a manner
that the energy is minimized (Equation 6.8). Calculus of variations shows how the solution to
Equation 6.7 reduces to a pair of differential equations that can be solved by finite difference
analysis (Waite and Welsh, 1990). This results in a set of equations that iteratively provide new
sets of contour points. By calculus of variation, we shall consider an admissible solution
ˆ
vs
perturbed by a small amount, v
s
, which achieves minimum energy, as:
dE
snake
ˆ
vs +vs
d
=0 (6.15)
where the perturbation is spatial, affecting the x and y coordinates of a snake point:
vs = 
x
s
y
s (6.16)
This gives the perturbed snake solution as
ˆ
vs +vs =
ˆxs +
x
s ˆys +
y
s
(6.17)
where ˆxs and ˆys are the x and y coordinates, respectively, of the snake points at the
solution
ˆ
vs =
ˆxs ˆys
. By setting the constraint energy E
con
to zero, the snake energy
(Equation 6.7) becomes:
E
snake
vs =
1
s=0
E
int
vs +E
image
vs
ds (6.18)
Edge magnitude information is often used (so that snakes are attracted to edges found by an
edge detection operator), so we shall replace E
image
by E
edge
. By substitution for the perturbed
snake points, we obtain
E
snake
ˆ
vs +vs =
1
s=0
E
int
ˆ
vs +vs
+E
edge
ˆ
vs +vs
ds (6.19)
252 Feature Extraction and Image Processing
By substitution from Equation 6.9, we obtain
E
snake
ˆ
vs +vs =
s=1
s=0
s
d
ˆ
vs +vs
ds
2
+s
d
2
ˆ
vs +vs
ds
2
2
+E
edge
ˆ
vs +vs
ds
(6.20)
By substitution from Equation 6.17,
E
snake
ˆ
v
s
+v
s

=
s=1
s=0
s
dˆx
s
ds
2
+2
dˆx
s
ds
d
x
s
ds
+
d
x
s
ds
2
+
dˆy
s
ds
2
+2
dˆy
s
ds
d
y
s
ds
+
d
y
s
ds
2
+
s
d
2
ˆx
s
ds
2
2
+2
d
2
ˆx
s
ds
2
d
2
x
s
ds
2
+
d
2
x
s
ds
2
2
+
d
2
ˆy
s
ds
2
2
+2
d
2
ˆy
s
ds
2
d
2
y
s
ds
2
+
d
2
y
s
ds
2
2
+E
edge
ˆ
v
s
+v
s

ds
(6.21)
By expanding E
edge
at the perturbed solution by Taylor series, we obtain
E
edge
ˆ
vs +vs
=E
edge
ˆxs +
x
s ˆys +
y
s
=E
edge
ˆxs ˆys
+
x
s
E
edge
x
ˆxˆy
+
y
s
E
edge
y
ˆxˆy
+O
2
(6.22)
This implies that the image information must be twice differentiable, which holds for edge
information, but not for some other forms of image energy. Ignoring higher order terms in
(since is small), by reformulation Equation 6.21 becomes
E
snake
ˆ
vs +vs
=E
snake
ˆ
vs
+2
s=1
s=0
s
dˆxs
ds
d
x
s
ds
+s
d
2
ˆxs
ds
2
d
2
x
s
ds
2
+
x
s
2
E
edge
x
ˆxˆy
ds
+2
s=1
s=0
s
dˆys
ds
d
y
s
ds
+s
d
2
ˆys
ds
2
d
2
y
s
ds
2
+
y
s
2
E
edge
y
ˆxˆy
ds (6.23)
Flexible shape extraction (snakes and other techniques) 253
Since the perturbed solution is at a minimum, the integration terms in Equation 6.23 must be
identically zero:
s=1
s=0
s
dˆxs
ds
d
x
s
ds
+s
d
2
ˆxs
ds
2
d
2
x
s
ds
2
+
x
s
2
E
edge
x
ˆxˆy
ds = 0 (6.24)
s=1
s=0
s
dˆys
ds
d
y
s
ds
+s
d
2
ˆys
ds
2
d
2
y
s
ds
2
+
y
s
2
E
edge
y
ˆxˆy
ds = 0 (6.25)
By integration we obtain
s
dˆxs
ds
x
s
1
s=0
s=1
s=0
d
ds
s
dˆxs
ds
x
sds
s
d
2
ˆxs
ds
2
d
x
s
ds
1
s=0
d
ds
s
d
2
ˆxs
ds
2
x
s
1
s=0
+
s=1
s=0
d
2
ds
2
s
d
2
ˆxs
ds
2
x
sds +
1
2
1
s=0
E
edge
x
ˆxˆy
x
sds = 0 (6.26)
As the first, third and fourth terms are zero (since for a closed contour,
x
1
x
0 = 0 and
y
1
y
0 = 0), this reduces to
s=1
s=0
d
ds
s
dˆxs
ds
+
d
2
ds
2
s
d
2
ˆxs
ds
2
+
1
2
E
edge
x
ˆxˆy
x
sds = 0 (6.27)
Since this equation holds for all
x
s,
d
ds
s
dˆxs
ds
+
d
2
ds
2
s
d
2
ˆxs
ds
2
+
1
2
E
edge
x
ˆxˆy
=0 (6.28)
By a similar development of Equation 6.25 we obtain
d
ds
s
dˆys
ds
+
d
2
ds
2
s
d
2
ˆys
ds
2
+
1
2
E
edge
y
ˆxˆy
=0 (6.29)
This has reformulated the original energy minimization framework (Equation 6.7) into a pair of
differential equations. To implement a complete snake, we seek the solution to Equations 6.28
and 6.29. By the method of finite differences, we substitute for dxs/ds x
s+1
x
s
, the
first order difference, and the second order difference is d
2
xs/ds
2
x
s+1
2x
s
+x
s1
(as in
Equation 6.12), which by substitution into Equation 6.28, for a contour discretized into S points
254 Feature Extraction and Image Processing

Get Feature Extraction & Image Processing, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.