cs 7322 winter 1997 -- mid term solutions by roman khramets.htm

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

    in the colony let them attach to edges left 
    <LI>after that each snakes proceeds "snapping" itself onto the edge more and 
    more, possibly breaking up at discontinuities and stretching 
    <LI>if no snakes change significanty, we are done and have an edge map, 
    mapped with snakes </LI></UL></LI></UL>
<H4><A 
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#Index">to 
TOP</A></H4>
<P>
<HR>

<P></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>"Using Dynamic Programming 
  for Minimizing the Energy of Active Contours in the Presense of Hard 
  Constraints"</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>inability to "snap to" a very high curvature objects (e.g., circle) 
    <LI>points "bunching up" on a high curvature edge 
    <LI>very limited "radius" 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="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#solution">How 
  I solved it</A>, <A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#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 "bunch 
  up" 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 
  "bunching up."</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 "snaps" 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 "energetic" 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 "snap" 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 
  "exploration area" is relatively large. The stability of the given algorithm 
  with respect to the time step was worse.</P></UL>
<P>
<HR>

<P></P>
<H4><A name=results></A>Results</H4>
<P>1. Image 1.</P>
<P>Initial snake placement</P>
<P><IMG height=410 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img1.jpg" 
width=519 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex1.gif"></P>
<P>Snake after 40 iterations of the algorithm (note the slow convergence due to 
the small X and Y ranges)</P>
<P><IMG height=410 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img1_1.jpg" 
width=519 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex1.gif"> 
</P>
<P>2. Image 2.</P>
<P>Initial snake placement</P>
<P><IMG height=410 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img2.jpg" 
width=519 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif"></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 height=410 alt="Image 2" 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img2_1.jpg" 
width=518 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif"></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 height=410 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img3_1.jpg" 
width=519 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif"></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 height=410 
src="CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets.files/img4_1.jpg" 
width=519 
SGI_SRC="/tmp_mnt/net/ac89/www-db3/classes/cs7322_97_spring/participants/template/midterm/ex2.gif"></P>
<H4><A 
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#Index">to 
TOP</A></H4>
<P>
<HR>

<P></P>
<H4><A name=code></A>Source Code</H4>
<UL>
  <LI><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/snake_demo.m"><TT>snake_demo.m</TT> 
  </A>: the main module 
  <LI><TT><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/snake.m">snake.m</A></TT>: 
  the implementation of the greedy snake optimization algorithm (one pass) 
  <LI><TT><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/clipValue.m">clipValue.m</A>:</TT> 
  make a value passed to it as a parameter to lie within a range specified 
  <LI><TT><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/continuityEstimate.m">continuityEstimate.m</A>:</TT> 
  calculates an estimate of the snake's continuity 
  <LI><TT><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/curvatureEstimate.m">curvatureEstimate.m</A>:</TT> 
  calculates an estimate of the snake's curvature 
  <LI><TT><A 
  href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/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></P>
<ADDRESS>Roman Khramets, <I><A 
href="mailto:[e-mail]">[e-mail]</A></I></ADDRESS></BODY></HTML>