📄 cs 7322 winter 1997 -- mid term solutions by roman khramets.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0091)http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html -->
<HTML><HEAD><TITLE>CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META content="MSHTML 6.00.2900.2523" name=GENERATOR></HEAD>
<BODY>
<P><!-- SGI_COMMENT COSMOCREATE --><!-- SGI_COMMENT VERSION NUMBER="1.0.1" --></P>
<H2>CS 7322 Spring 1997 -- MidTerm </H2>
<H3>Solutions by Roman Khramets</H3>
<DIV align=right>
<P><I>I am a snake, and I guard the tranquility. Sit closer to me and you'll
find out who I really am...</I></P></DIV>
<DIV align=right>
<P>Boris Grebenschikov, "Aquarium" (Russian rock group)</P></DIV>
<P>
<HR>
<P></P>
<H4><A name=Index></A><B><FONT size=+2>Index</FONT></B></H4>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#solution">How
I solved it</A></P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#assumptions">Assumptions
and Weaknesses</A></P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#improvements">How
it can be improved</A></P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#answers">Answers
to the Questions</A></P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#results">Results</A></P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#code">Code</A></P>
<P>
<HR>
<P></P>
<H4><A name=solution></A>How I solved it</H4>
<P>Fisrt, I looked at the paper <I>"The Computation of Visible-Surface
Representations"</I> by Terzopoulos. After I read other papers, class notes,
etc. the first 3 chapters made much more sense. Even the "computational
molecules" part seemed less obscure than before. As I like to say, I do not
understand that paper a little less than before ;-).</P>
<P>Then, I had to make a choice of the development environment for the project.
My first choice was to write everything in C++ from the scratch. ideally, it
would be a program for Windows 95 (I somewhat familiar with the Windows API),
that would mimic the functionality of the demo code provided for this
assignment. However, after I failed to find a quick and easy way of reading and
displaying gifs, jpegs, etc. in Windows, I decided to work with matlab.</P>
<P>I made the following changes to the code provided:</P>
<UL>
<LI>I modified the <A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/snake_demo.m">snake_demo.m</A>,
so that it is possible to load multiple files into the demo
<LI>I totally replaced the contents of <A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/snake.m">snake.m</A>
with my implementation of the snakes algorithm </LI></UL>
<P>I decided to implement the greedy algorithm described in the paper <I>"A Fast
Algorithm for Active Contours"</I> by Donna J. Williams and Mubarak Shah. The
algorithm is the easiest one to implement because it is based on a very simple
greedy principle of minimization of each control point's energy as a part of
minimization of the total energy of the snake.</P>
<P>The algorithm can be described in the following way. For each snake control
point, for each point in its neighborhood defined by the "X Range" and "Y Range"
parameters, choose a new location for the current control point that has the
minimum energy according to the formula:</P>
<P> E(n)
= aplha(n)*continuityEstimate(control_points(n))
+<BR> beta(n)*curvatureEstimate(control_points(n))
+<BR> gamma(n)*imageForces(control_points(n))</P>
<P>where n - current control point
index,<BR> alpha(n),
beta(n), gamma(n) - weights of the energy terms for the control
point,<BR> control_points
- array of control
points,<BR> continuityEstimate
- the continuity (first derivative) energy term (makes the snake
act<BR> like
a membrane - discontinuities are
penalized),<BR> curvatureEstimate
- the curvature (second derivative) energy term (makes the snake
act<BR> like
a thin plate - high curvature is
penalized),<BR> imageForces
- the energy term for the image forces (image gradient) - attracts the
snake<BR> to
the edges in the image</P>
<P>continuityEstimate = (|control_points(n) - control_points(n - 1)| ^
2)/2;<BR>curvatureEstimate = (|control_points(n - 1) - 2*control_points(n) +
control_points(n)| ^ 2)/2;<BR> imageForces =
SUM( image_gradient(control_points(n)(2),<BR> neighborhood_left:neighborhood_right) )
+<BR> SUM( image_gradient(neighborhood_top:neighborhood_bottom,<BR> control_points(n)(1)) ).</P>
<P>Image gradient force for any particular neighborhood point of the control
point under exploration is calculated as a sum of gradient values over
horisontal and vertical "axis" defined by the position of the neighborhood
point. It is done to make the estimation more robust (less sensitive to
noise) since it is based on several, and not just one gradient values and
to extend the radius of sensitivity of the snake to the large values of the
image gradient. The extent of those axis is defined by the parameters
<I>radius_x </I>and <I>radius_y</I> passed to the <I>imageForces</I> function
(see <A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/imageForces.m">imageForces.m</A>).</P>
<P>Tracking a moving object through several frames, provided changes from frame
to frame are on the order of +-(10 + "X Range") pixels in the <I>X</I> direction
and +-(10 + "Y Range") in the <I>Y</I> direction is done automatically because
of a relatively large area of exploration during the search for an optimal (new)
position for a particular control point and a very strong force exerted by large
values of the image gradient. I just realized that optical flow estimation of
certain "interest" areas of the image (the areas snake(s) sticks(stick) to) can
be done that way.</P>
<P><A
href="http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Khramets/midterm/report.html#Index">to
TOP</A></P>
<P>
<HR>
<P></P>
<H4><A name=assumptions></A>Assumptions and Weaknesses</H4>
<P>I made the following assumptions</P>
<OL>
<LI>all the input images are in gif format
<LI>the snake is not self intersecting - unpredictable behavior is exhibited
if it is
<LI>there are at least 2 control points in the snake </LI></OL>
<P>I think the major weakness of my solutions are:</P>
<OL>
<LI>non-adaptive X and Y range values
<LI>non-adaptive neighborhood size for calculating the image force
<LI>not very good handling of boundary control points - the first and the last
one
<LI>the snake cannot adapt to very sharp edges (where the 1st derivative is
discontinuous)
<LI>the snake doe not "snap to" the areas of large curvature very well
<LI>points bunch up due to a not very good continuity energy estimation
function
<LI><I>total</I> energy of the snake is not calculated
<LI>snakes do not stretch along the edges </LI></OL>
<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=improvements></A>Improvements and Possible Future Work</H4>
<P>I think that this can be improved by doing the following</P>
<UL>
<LI>calculate the <I>total</I> energy of the snake
<LI>make X and Y ranges and neighborhood size for calculating the image force
adaptive so that initially their values are relatively large and they
gradually decrease as the snake becomes icreasingly more stable (indicated by
the derivative of the total snake energy getting marginally small or by not
too many points moving at each iteration) - I think that some sort of
simulated annealing method applied to this would be good
<LI>implement the stretching-along-the-edge force
<LI>improve handling the boundary point
<LI>allow for discontinuities by breaking snakes up </LI></UL>
<P>Future work:</P>
<UL>
<LI>implement a "colony" of "intelligent" snakes for edge processing:
<UL>
<LI>edges are identified via the image gradient and labeling
<LI>snakes start moving in random directions
<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>all edges get themselves one snake
<LI>if there are "unemployed" snakes, delete them
<LI>if there are edges left with no snakes attached to them, put more snakes
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -