Literature Review:
After understaing the basic functioning of snakes we decided to study different implementations of them, and their applications and weaknesses. Towards this end we reviewed a number of papers by different authors suggesting various methodologies and algorithms. We finally decided to concentrate on three papers.
- A paper by Kass et all, for understanding the basics of snakes
- A paper by Williams and Shah, which we intended to implement in Vision X
- A paper by Chenyang Xu for comparison against the performance of our snake.
Reviews of these papers follow:
Kass algorithm
To understand the basic principles behind snakes, we first
reviewed the Kass paper. The Kass paper is the foundation for active contour models, and
outlines the underlying equation of all snakes. From
this paper, the following characteristics and properties for implementation of snakes were
found:
Let a closed contour, C be represented by its pair of coordinate
functions {x(s), y(s)}, where s is the normalized arc length along C. Then the desired
contour is given by minimizing a function.
where,
Eint = internal energy of the spline due to bending
Eimage= image forces
Econ= external constraint forces
1. Internal Energy:
The internal spline energy can be written as
The spline energy is composed of a first order term controlled by
a(s), which makes the snake act
like a membrane and a second order term b (s),
which makes the snake, act like a thin plate. Adjusting the weights of these terms allows
the snake to make corners and straight lines.
2. Image Forces:
For a snake to align itself with the regions of interest, it is
necessary that be attracted by the same. A number of functions are defined that cause the
snake to be attracted to the feature. Three important ones are the line, edge and
termination functions. The total image energy can be expressed as a weighted combination
of the three energy functions.
Eimage = wline Eline + wedge
Eedge + wterm Eterm
The simplest useful image functional is the image intensity e.g.:
if we set
Eline = I(x,y)
then depending on the sign of wline the snake is
attracted to dark or light lines. Subject to the other constraints the snake will then try
to align itself with the lightest or darkest nearby contour.
The edge functional can be obtained by setting
In this case the snake is attracted to image regions with large
gradients.
The termination functional can be obtained by a function checking
the curvature of level lines in a slightly smoothed image.
By combining the various terms and choosing the parameters of the
snake accurately, the snake can be used to bend to and encompass regions of interest with
high accuracy.
William and Shah algorithm
After this we looked at newer and more efficient implementations
of snakes and came across the William and Shah paper.
This paper suggests a faster implementation of Kass’s model of
representing contours. However Kass’s
algorithms was computationally slow. What Williams and Shah suggest is a greedy
algorithm that runs at O(nm), whereas Kass’s algorithms run at O(nm3). We want to examine the quality of this
computationally efficient method
The greedy algorithm is implemented by minimizing the following
equation:
This is similar to the Kass Model, but it only deals with three
energy functions total. a(s)
and b(s) are user selected scalars that weight the first and second
order continuity constraints, whereas g(s)
scales the edge strength. The first two
parameters correspond to Eint(v(s)),
and g(s)
corresponds to the Eim(v(s)) in the
Kass equation. What we have is a simplified
form of the Kass Active Contour Model.
First, let us define vi as the set of points (xi, yi).
We start at the first point in the snake, and evaluate the minimal E values
of the next point. To do this, we examine
the next point in the snake over a predefined “neighborhood” value, and see
which of those points minimizes the E function. That
point is then changed to the minimizing value.
To calculate Econt,
we use the equation:
Econt = d - | vi
– vi-1 |
where d = the average distance between two points. This implements first order continuity, without
causing the distance between points to become extremely small at edges and large otherwise
(it helps to regulate a common distance between points).
To calculate Ecurv, we use the
equation:
Ecurv = | vi-1 – 2vi + vi+1 | 2
This is just a less calculation intensive implementation of
second derivative.
And for our Eimage,
we use the gradient equation:
Eimage = (min – mag) / (max – min)
Where mag is the
gradient magnitude of the current pixel, min and
max are the minimum and maximum gradient
values in each neighborhood.
Gradient Vector Flow
algorithm
The gradient vector flow (GVF) was
originally introduced by Xu and Prince in [10] in order to improve some poor properties of
the force field generated by the gradient operator:
- The gradient of an edge map
has
vectors pointing toward the edges, which are normal to the edges at their location. - These vectors generally have large
magnitude only in the immediate vicinity of the edges.
- In homogeneous regions where the image
is nearly constant,
is nearly
zero.
Although the first property is highly
desirable, the last two properties are not. The second one induces a very small capture
range and because of the third one, homogeneous regions induce forces that are near to
zero. The overall approach is to use the force balance equation and introduce a new
external force field 
,
which is called gradient vector flow (GVF). The idea is based on the Helmholtz theorem
which states that the most general static field can be decomposed into two components: an
irrotational (curl-free) component and a solenoidal (divergence-free) component. In the
classic case the static field is irrotational, since it is the gradient of a potential
function. A more general static field can be obtained by allowing the possibility that it
comprises both an irrotational and a solenoidal component. The GVF is defined so that 
minimizes the
energy functional
with
'This variational formulation follows a
standard principle, that of making the result smooth when there is no data. In particular,
we see the when 
is
small, the energy is dominated by sum of the squares of the partial derivatives of the
vector field, yielding a slowly varying field. On the other hand, when 
is large, the
second term dominates the integrand, and is minimized by setting 
.This
produces the desired effect of keeping v nearly equal to the gradient of the edge map when
it is large, but forcing the field to be slowly-varying in homogeneous regions. The
parameter 
is
a regularization parameter governing the tradeoff between the first and second term in the
integrand. (...) Using the calculus of variations, it can be shown that the GVF field can
be found by solving the following Euler equations
where 
is the
Laplacian operator. These equations provide further intuition behind the GVF formulation.
We note that in a homogeneous, the second term in each equation is zero. Therefore, within
such a region u and v are each determined by Laplace's equation, and the resulting GVF
field is interpolated from the region boundary, reflecting a kind of competition among the
vectors. This explain why GVF yields vectors that point into the concavities.
The introduction of the GVF instead of
the gradient force provides two great advantages. The first advantage is the convergence
of the snake into concavities and the second one, a less sensibility to the initial. The
introduction of the GVF strongly improves the convergence of the classic snake towards the
desired solution, but it also deteriorates the performances at corners. Although the
classic snake is not designed for corner matching because of its intrinsic smoothness, the
results can be quite satisfying if the snake resolution is sufficient. The snake behavior
at corners in presence of the GVF is poorer than with the classic snake because of the
diffusion effects explained in the previous paragraph. The GVF turns out to be very
powerful, but it proves some lack of performance in the presence of corners.