Image Processing Reference
In-Depth Information
that the snake aims to attain evenly spaced contour points. Low values for β imply that
curvature is not minimised and the contour can form corners in its perimeter whereas high
values predispose the snake to smooth contours. These are the properties of the contour
itself, which is just part of a snake's compromise between its own properties and measured
features in an image.
The image energy attracts the snake to low-level features, such as brightness or edge
data. The original formulation suggested that lines, edges and terminations could contribute
to the energy function. Their energy is denoted
E
line
,
E
edge
and
E
term
, respectively, and are
controlled by weighting coefficients
w
line
,
w
edge
and
w
term
, respectively. The image energy
is then:
E
image
=
w
line
E
line
+
w
edge
E
edge
+
w
term
E
term
(6.10)
The
line
energy can be set to the image intensity at a particular point. If black has a lower
value than white, then the snake will be extracted to dark features. Altering the sign of
w
line
will attract the snake to brighter features. The
edge
energy can be that computed by
application of an edge detection operator, the magnitude, say, of the output of the Sobel
edge detection operator. The
termination
energy,
E
term
as measured by Equation 4.52, can
include the curvature of level image contours (as opposed to the curvature of the snake,
controlled by β (
s
)), but this is rarely used. It is most common to use the edge energy,
though the line energy can find application.
6.3.2
The Greedy algorithm for snakes
The implementation of a snake, to evolve a set of points to minimise Equation 6.7, can use
finite elements, or finite differences, which is complicated and follows later. It is easier to
start with the
Greedy algorithm
(Williams, 1992) which implements the energy minimisation
process as a purely discrete algorithm, illustrated in Figure
6.4
. The process starts by
specifying an initial contour. Earlier, Figure
6.3
(a) used a circle of 16 points along the
perimeter of a circle. Alternatively, these can be specified manually. The Greedy algorithm
then evolves the snake in an iterative manner by local neighbourhood search around contour
points to select new ones which have lower snake energy. The process is called Greedy by
virtue of the way the search propagates around the contour. At each iteration, all contour
points are evolved and the process is actually repeated for the first contour point. The index
to snake points is computed modulo
S
(the number of snake points).
For a set of snake points
v
s
,
s
0,
S
- 1, the energy functional minimised for each
snake point is:
E
snake
(
s
) =
E
int
(
v
s
) +
E
image
(
v
s
)
(6.11)
This is expressed as
2
2
2
d
ds
v
d
ds
v
s
s
Es
() =
()
s
+
()
s
+
()
sE
(6.12)
snake
edge
2
where the first-order and second-order differentials are approximated for each point searched
in the local neighbourhood of the currently selected contour point. The weighting parameters,
α , β and γ , are all functions of the contour. Accordingly, each contour point has associated
values for α , β and γ . An implementation of the specification of an initial contour by a
function
point
is given in Code
6.1
. In this implementation, the contour is stored as a
