Welcome to Sebastian's Snakes Program Page
How to run the Snakes Program(program located below):
1. Ignore all the "User defined Variables". They are set to work in the most common cases. If you understand how the Snakes Program works(See explanations below), you can change these variables for better results.
2. Click on the chess piece that you would like to use.
3. Use your mouse to place Snake Points around to chess piece. Place them not too far away and in a counter clockwise order(See example below). If you would like to remove the last point you clicked, just click on "Undo Last Point".
4. Click on "Start".
5. When the Snakes Program completes you can click on "View Snake Trail" to see how the points moved and click on "Reset" to start over.
[How the Snakes Program works] [Why the Snake Program may not have worked] [Email me]
If the Snake Program executed correctly, the Snake Points should have conformed to the border of the image in a snake like motion. The following briefly describes how the Snakes Program works, so that you can understand the roles that the "User Defined Variables" are performing. One iteration or pass through the program consists of the following steps:
1. Each Snake Point is considered seperately from the others(this is also known as the greedy aproach to the Snakes algorithm). The "Window Size" variable refers to how many pixels to look at around the Snake Point, for example
:
2. Before the actual snaking begins, the picture is convolved with a x and y derivative of a Gaussian(g(x)=-x*x/2*sigma*sigma). A gradient image is generated from the two outputs(Sqrt(x*x + y*y)). The "Sigma Size" variable refers to how large of a Gaussian will be used to convolve the image.
3. The following is calculated for each pixel in the window around the Snake Point:
Alpha * Econtinuity + Beta * Ecurvature + Gamma * Egradient
where Alpha, Beta, and Gamma are merely user defined weights that indicate the strength given to Econtinuity, Ecurvature, and Egradient respectively. (E denotes Energy)
Econtinuity refers to the distance between a pixel and its neighboring Snake Points with respect to all the Snake Points. It is calculated by subtracting the average distance(between all Snake Points) from the distance between the pixel and the previous Snake Point.
Ecurvature refers to the amount curvature between a pixel and the neighboring Snake Points. This can be calculated using the second derivative, which corresponds to: (next Snake Point - pixel) - (pixel - previous Snake Point)
Egradient merely refers to negative the size of the gradient of the pixel.
NOTES:
The values generated need to be normalized. For the continuity and curvature it is enough to divide by the maximum of the window, but the gradient should be normalised using: (Pixel Gradient - Minimum )/(Maximum - Minimum)
The Beta Weight for a pixel should be dropped to ZERO if the gradient and the curvature is above a threshold for that pixel. This will occur when a corner is present. The curvature is not considered in the calculation(i.e. beta = ZERO), so that the corner is preserved.
4. The Snake point is moved to the pixel in its window with the largest overall Energy(E).
5. The porgram terminates when the number of Snake points that move during an iteration is less than the "Minimum Moves" user defined threshold.
NOTES:
The "Maximum Iterations" user defined variable places an upper bound on how many times a Snake Point can move. The reason for this is that situations can occur when one or more Snake Points are moving back and forth without making any progress, and will continue to do so forever. This variable will prevent this rare occurance and guaranttee that the program will teminate.
The view is refreshed every 3 iterations. The see every move that was made, click on the "View Snake Trail" button when the program terminates.
I used Binary Images(Black and white) of the chess pieces because they produce a stronger edge attraction, thus allowing the Snake Points to be placed further away from the chess piece.
Why the Snake Program did not work
Possible reasons why the Snake Points you entered did not conform to the border of the chess piece include:
The points were placed to far away from the chess piece.
The points were not placed in a counter clockwise order around the chess piece(see example above).
Modify the "User Defined Variables", for example: try increasing the maximum number of iterations, and/or decreasing the minimum number of moves.
Sebastian van Delden
Graduate Teaching Assistant
Computer Science Department of UCF
sdelden@cs.ucf.edu
http://www.cs.ucf.edu/~sdelden