📄 report.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD> <TITLE>CS 7322 Winter 1997 -- Mid Term Solutions by Roman Khramets</TITLE> <META NAME="GENERATOR" CONTENT="Mozilla/3.01Gold (X11; I; SunOS 4.1.3 sun4m) [Netscape]"></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 closerto me and you'll find out who I really am...</I></P></DIV><DIV ALIGN=right><P>Boris Grebenschikov, "Aquarium" (Russianrock group)</P></DIV><P><HR></P><H4><A NAME="Index"></A><B><FONT SIZE=+2>Index</FONT></B></H4><P><A HREF="#solution">How I solved it</A></P><P><A HREF="#assumptions">Assumptions and Weaknesses</A></P><P><A HREF="#improvements">How it can be improved</A></P><P><A HREF="#answers">Answers to the Questions</A></P><P><A HREF="#results">Results</A></P><P><A HREF="#code">Code</A></P><P><HR></P><H4><A NAME="solution"></A>How I solved it</H4><P>Fisrt, I looked at the paper <I>"The Computation of Visible-SurfaceRepresentations"</I> by Terzopoulos. After I read other papers, classnotes, etc. the first 3 chapters made much more sense. Even the "computationalmolecules" 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 theproject. My first choice was to write everything in C++ from the scratch.ideally, it would be a program for Windows 95 (I somewhat familiar withthe Windows API), that would mimic the functionality of the demo code providedfor this assignment. However, after I failed to find a quick and easy wayof reading and displaying gifs, jpegs, etc. in Windows, I decided to workwith matlab.</P><P>I made the following changes to the code provided:</P><UL><LI>I modified the <A HREF="snake_demo.m">snake_demo.m</A>, so that itis possible to load multiple files into the demo</LI><LI>I totally replaced the contents of <A HREF="snake.m">snake.m</A> withmy implementation of the snakes algorithm</LI></UL><P>I decided to implement the greedy algorithm described in the paper <I>"AFast Algorithm for Active Contours"</I> by Donna J. Williams and MubarakShah. The algorithm is the easiest one to implement because it is basedon a very simple greedy principle of minimization of each control point'senergy 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 snakecontrol point, for each point in its neighborhood defined by the "XRange" and "Y Range" parameters, choose a new location forthe current control point that has the minimum energy according to theformula:</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> likea membrane - discontinuities are penalized),<BR> curvatureEstimate- the curvature (second derivative) energy term (makes the snake act<BR> likea thin plate - high curvature is penalized),<BR> imageForces- the energy term for the image forces (image gradient) - attracts thesnake<BR> tothe 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 controlpoint under exploration is calculated as a sum of gradient values overhorisontal and vertical "axis" defined by the position of theneighborhood point. It is done to make the estimation more robust (lesssensitive to noise) since it is based on several, and not just onegradient values and to extend the radius of sensitivity of the snake tothe large values of the image gradient. The extent of those axis is definedby the parameters <I>radius_x </I>and <I>radius_y</I> passed to the <I>imageForces</I>function (see <A HREF="imageForces.m">imageForces.m</A>).</P><P>Tracking a moving object through several frames, provided changes fromframe to frame are on the order of +-(10 + "X Range") pixelsin 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 explorationduring the search for an optimal (new) position for a particular controlpoint 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 thatway.</P><P><A HREF="#Index">to TOP</A></P><P><HR></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><LI>the snake is not self intersecting - unpredictable behavior is exhibitedif it is</LI><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><LI>non-adaptive neighborhood size for calculating the image force</LI><LI>not very good handling of boundary control points - the first and thelast one</LI><LI>the snake cannot adapt to very sharp edges (where the 1st derivativeis discontinuous)</LI><LI>the snake doe not "snap to" the areas of large curvaturevery well</LI><LI>points bunch up due to a not very good continuity energy estimationfunction</LI><LI><I>total</I> energy of the snake is not calculated</LI><LI>snakes do not stretch along the edges</LI></OL><H4><A HREF="#Index">to TOP</A></H4><P><HR></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><LI>make X and Y ranges and neighborhood size for calculating the imageforce adaptive so that initially their values are relatively large andthey gradually decrease as the snake becomes icreasingly more stable (indicatedby the derivative of the total snake energy getting marginally small orby not too many points moving at each iteration) - I think that some sortof simulated annealing method applied to this would be good</LI><LI>implement the stretching-along-the-edge force</LI><LI>improve handling the boundary point</LI><LI>allow for discontinuities by breaking snakes up</LI></UL><P>Future work:</P><UL><LI>implement a "colony" of "intelligent" snakes foredge processing:</LI>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -