report.html

Tracking a moving object through several frames, provided changes from frame to frame are on the ord

<UL>
<LI>edges are identified via the image gradient and labeling</LI>

<LI>snakes start moving in random directions</LI>

<LI>once a snake attaches itself to an edge, it tags the edge as belonging
to it - no other snake can attach after that</LI>

<LI>all edges get themselves one snake</LI>

<LI>if there are &quot;unemployed&quot; snakes, delete them</LI>

<LI>if there are edges left with no snakes attached to them, put more snakes
in the colony let them attach to edges left</LI>

<LI>after that each snakes proceeds &quot;snapping&quot; itself onto the
edge more and more, possibly breaking up at discontinuities and stretching</LI>

<LI>if no snakes change significanty, we are done and have an edge map,
mapped with snakes</LI>
</UL>
</UL>

<H4><A HREF="#Index">to TOP</A></H4>

<P>
<HR></P>

<H4><A NAME="answers"></A>Answers to the Questions</H4>

<P>1. What algorithm did the snake demo use? Explain it? What are its limitations?</P>

<UL>
<P>The given snake algorithm implemented a dynamic programming snake optimization
strategy (for details see the paper <I>&quot;Using Dynamic Programming
for Minimizing the Energy of Active Contours in the Presense of Hard Constraints&quot;</I>
by Amir A. Amini, Saed Tehrani, and Terry E. Weymouth). The difference
from my implemetation of the greedy strategy was that the image force was
calculated at just one point (and there was a possibility to switch from
the image force based on the gradient and the image itself), not over a
neighborhood and that iterations of control point movement (adjustment)
and optimization was done over the whole span of control points simultaneously.</P>

<P>Limitations of the algorithm include:</P>

<UL>
<LI>an inability to deal with discintinuities in the edge the snake is
attracted to (the snake should be split in two at the point of discontinuity)</LI>

<LI>inability to &quot;snap to&quot; a very high curvature objects (e.g.,
circle)</LI>

<LI>points &quot;bunching up&quot; on a high curvature edge</LI>

<LI>very limited &quot;radius&quot; of sensitivity to the large values
of the image gradient</LI>
</UL>
</UL>

<P>2. What does your method do that is different then the give one? Explain
it? What are the limitations?</P>

<UL>
<P>See <A HREF="#solution">How I solved it</A>, <A HREF="#assumptions">Assumptions
and Weaknesses</A>, and the answer to the previous question for a detailed
discussion.</P>
</UL>

<P>3. How sensitive are the algorithms to setting the parameters alpha
and beta? Why?</P>

<UL>
<P>The algorithms are quite sensitive to the values of those parameters.
For example, setting alpha to a large value makes the snake control points
&quot;bunch up&quot; on the areas of high curvature and ultimately converge
to a single point because alpha affects the weight that the algorithm assigns
to the energy measure based on, effectively, the distance between the points.
Large values of alpha also cause the snake to be resistant to the abrupt
changes in the first derivative. Hence, no sharp edges are detected when
large values of alpha are used. I kept alpha very small, mainly to prevent
points from &quot;bunching up.&quot;</P>

<P>Large values of beta force the snake to become a straight line - the
curvature is minimized in this case. However, I kept the value of beta
relatively large but less than gamma (image force coefficient ), so that
if one control point is strongly attracted to an edge, it stays there since
image forces are strong and at the same time forces the nearest control
point unaffected (yet) by the image force to minimize the curvature due
to a large beta. When that control point moves quite close to the edge
(and control point on the edge) so that image forces become strong, it
&quot;snaps&quot; to the edge, now regardless of the beta since image forces
are stronger. This chain continues until all the control points are forced
onto the edge.</P>

<P>Small values of beta make the snake less &quot;energetic&quot; to minimize
its curvature.</P>

<P>I always kept values of gamma quite large since image force is by far
the most important element of the energy estimate - it forces the snake
onto the edge which is what we ultimately want.</P>
</UL>

<P>4. How stable are the algorithms with respect to initial placement of
the snake in the image? Why?</P>

<UL>
<P>The stability of my implementation is much better due to a relatively
large area of exploration for moving a control point to a new location.
Placing just one control point on the edge forces the whole snake to &quot;snap&quot;
to the edge due to the reasons described in the answer to the previous
question.</P>
</UL>

<P>5. How stable are the algorithms with respect to the time step? Why?</P>

<UL>
<P>Time step bears no relevance to the stability of the algorithms working
on single still images. However, if we have to track an object/edge through
different frames of a motion sequence, then we have to worry about the
time step - the smaller it is, the better. If we have a very small time
step we can track objects moving even at very large speeds since object
displacement from frame to frame is going to be relatively small and my
implementation of the algorithm will track the edge very well, because,
as I already mentioned, the &quot;exploration area&quot; is relatively
large. The stability of the given algorithm with respect to the time step
was worse.</P>
</UL>

<P>
<HR></P>

<H4><A NAME="results"></A>Results</H4>

<P>1. Image 1.</P>

<P>Initial snake placement</P>

<P><IMG SRC="img1.jpg" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex1.gif" HEIGHT=410 WIDTH=519></P>

<P>Snake after 40 iterations of the algorithm (note the slow convergence
due to the small X and Y ranges)</P>

<P><IMG SRC="img1_1.jpg" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex1.gif" HEIGHT=410 WIDTH=519>
</P>

<P>2. Image 2.</P>

<P>Initial snake placement</P>

<P><IMG SRC="img2.jpg" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif" HEIGHT=410 WIDTH=519></P>

<P>Snake after 5 iterations of the algorithm (fast convergence - due to
large values of X and Y ranges and small time step)</P>

<P><IMG SRC="img2_1.jpg" ALT="Image 2" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif" HEIGHT=410 WIDTH=518></P>

<P>3. Image 3 (next frame of the previous image)</P>

<P>Snake after 3 iterations of the algorithm (fast convergence - due to
large values of X and Y ranges and small time step)</P>

<P><IMG SRC="img3_1.jpg" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif" HEIGHT=410 WIDTH=519></P>

<P>4. Image 4 (next frame of the previous image)</P>

<P>Snake after 3 iterations of the algorithm (fast convergence - due to
large values of X and Y ranges and small time step)</P>

<P><IMG SRC="img4_1.jpg" SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif" HEIGHT=410 WIDTH=519></P>

<H4><A HREF="#Index">to TOP</A></H4>

<P>
<HR></P>

<H4><A NAME="code"></A>Source Code</H4>

<UL>
<LI><A HREF="./snake_demo.m"><TT>snake_demo.m</TT> </A>: the main module</LI>

<LI><TT><A HREF="./snake.m">snake.m</A></TT>: the implementation of the
greedy snake optimization algorithm (one pass)</LI>

<LI><TT><A HREF="./clipValue.m">clipValue.m</A>:</TT> make a value passed
to it as a parameter to lie within a range specified</LI>

<LI><TT><A HREF="./continuityEstimate.m">continuityEstimate.m</A>:</TT>
calculates an estimate of the snake's continuity</LI>

<LI><TT><A HREF="./curvatureEstimate.m">curvatureEstimate.m</A>:</TT> calculates
an estimate of the snake's curvature</LI>

<LI><TT><A HREF="./imageForces.m">imageForces.m</A>:</TT> calculates an
estimate of the image forces applied to the snake's control point in the
neighborhood defined by the parameters passed to the function</LI>
</UL>

<P>
<HR></P>

<ADDRESS>Roman Khramets, <I><A HREF="mailto:[e-mail]">[e-mail]</A></I></ADDRESS>

</BODY>
</HTML>