ACM Algorithm

In our deliberations over the implementation of the snakes, we considered 3 possible implementations of the general algorithm – the Kass approach [1], the William and Shah approach [2] and the Gradient Vector Flow (GVF) model by Xu and Prince [3].


Comparisons of various techniques
Based on literature review, we decided to approach the implementation of the snakes algorithm by William and Shah’s approach. We discarded the GVF approach first, considering that the improvement it offered was not of significance in our motion tracking problem. Furthermore, such an improvement was at a cost of lengthy and computation-intensive calculations, which inherently would not make sense in a motion tracking application.

While deliberating between Kass and William and Shah’s approaches, we opted for the simpler algorithm in the latter, and also since William and Shah’s method made it easier to determine weight values at a slight cost in terms of computation (Kass approach was O(n) whereas William and Shah’s approach was O(nm^2)).


Our Program
We decided to implement William and Shah's approach to ACM, but modify it slightly for image sequences. Below is a summary of how our program works:

FOR each frame in the image sequence, iterate through the control points that determine the location of the snake

FOR each iteration,

(1) Obtain mean edge length,d from the vector of control points, by calculating the Euclidean distance between neighboring points. Do note that we have to perform a wrap around for the first control point.

FOR each control point,

(2)Find maximum and minimum image gradient values based on the pixels within the neighborhood of the control point. We decided on a neighborhood size of 3 x 3, and also decided on a preset image gradient value threshold as described above, to be 5.0.

(3)Calculate the relevant energy terms E_elastic, E_stiffness and E_external for each pixel in the neighborhood. In particular, to approximate the derivatives, we use the forward difference approximation method.

(4)Normalize the internal energy values and compute the total energy at the pixel.

(5)Update the control point to the pixel where the total energy is a neighborhood minima.

END

(6)Check for number of points updated. When number of points updated falls below a certain threshold (we determined to be 0.2 x total number of points), then the iterations stopped and we take the points as our final points.

END

(7) With the control points obtained, use it as the starting location for the snake in the next frame. This continues until we have iterated through all the frames

END OF PROGRAM