Snakes, or active contours as they are sometimes called, provide a convenient way to optimize the location of a boundary according to some quality function Q (or energy function E). The boundary is specified via a series of control points connected by straight line segments. The value of the quality (energy) function can be calculated given the control point positions.
Given an initial set of control points, the snake position evolves over time by hill-climbing toward configurations with higher quality. (Because hill-climbing will tend to arrive at the nearest local maximum, the initialization of the control points will determine to some extent the final solution that is reached.) Efficient hill-climbing can be implemented via a dynamic programming approach that can identify the best configuration within a move of one pixel for each control point. You will investigate one implementation of such a system.
The Energy Function
The choice of energy function will partly determine how a snake evolves, since the new position maximizes the chosen function within a local neighborhood at each step. Many different energy functions are possible, but some are more complicated to implement than others. For our basic snake, we will use two terms: one term measuring the strength of the gradient at each control point, and another measuring how much the distance between each pair of consecutive points differs from some chosen amount. (The latter term will provide either an "inflationary" or "deflationary" pressure to our snake, depending on how the current size compares to the target size. If the target size is zero, then the snake will tend to shrink down to nothingness unless the gradient term prevents it. This can be useful in some cases; if you initialize the snake surrounding some feature of interest, deflation can be used to "shrink-wrap" the feature boundary.)
The lambda coefficients will allow you to play with the balance between these two terms. Setting either term to zero will allow you to see how the other tends to influence the snake's behavior by itself.
Notice that we did not include a straightness term, or require that the gradient direction be perpendicular to the snake contour. These are useful energy terms, but including them requires consideration of three control points at a time rather than two, which considerably complicates the dynamic programming. Another term that can be included if three points are considered it the difference in length between consecutive segments. This provides a way to encourage uniform segment lengths without introducing extra inflationary or deflationary pressures.
As an initial exercise, you may wish to try a snake whose points merely move towards a higher gradient. With a gradient-seeking snake, one would expect the points to move to a local maximum of the gradient. Try your program on the original image and a significantly smoothed image, and see if you can explain any differences in behavior. (Note: the dynamic-programming snake can simulate the gradient-seeking snake if the second lambda term is zero.)
To Do
You will be using the Matlab function snakeSol.m. This code takes three arguments: an image, a number of control points to be entered, and a value for lambda (the parameter controlling the balance between data and likelihood terms). When run, it first allows the user to input a set of initial control points (usually 20-50 for this lab, depending on the size of the object). It then updates the control point positions using dynamic programming, displaying the results as it goes, and returns the final set of points when the snake position becomes frozen at a local minimum of the energy function. You will examine the effects of different parameter settings and initialization choices on the results.
To work properly, this simple snake needs a fairly strong gradient around the object to be segmented. Try two different images: coins.jpg and wrenches.jpg. Now answer these questions: Can you get a segment around each of the coins in the first image? Do the same lambda values work in each case? What happens when lambda is too high? Too low? Can you explain why this happens? Can you segment an individual wrench? What is different about the wrench segmentations compared to the coins?
Further Exploration
The Matlab function activecontour implements a segmentation that is based on concepts similar to those explored here. Do you find it easier or harder to use than snakeSol.m?