COS 496 - Computer Vision

Spring 2003

Assignment 2

I. Active Contours (80%)

Implement a system for evolving active contours. The system should be based on the "greedy" algorithm described by Williams and Shah. Compared to the original Kass, Witkin, and Terzopoulos paper, this method simply performs a local search on the position of each vertex, and greedily moves the vertex to the position that locally minimizes energy.

The system should do the following:

1. Read an image from disk.
2. Compute the smoothed gradient of the image, and find the magnitude of the gradient at each pixel.
3. Obtain the initial position of a contour via user input. Use matlab's getline function for this (if your version of matlab doesn't have getline, you'll need getline.m and getcurpt.m). You'll also need to round the positions returned from getline to integers.
4. If the distance between points in the curve is large, interpolate to add extra points. You should probably aim for about 5 pixels between points.
5. While a fraction greater than f of points move in an iteration:
   1. Compute the average distance between points along the snake
   2. For each point p:
      1. Define an n by n neighborhood around p.
      2. Compute the energy functional E (see below) at each point in the neighborhood.
      3. Move p to the point with the minimum energy.
      4. If p moved away from its original position, update the count of pixels that moved on this iteration.

The energy functional you use should be a combination of three terms:

E = alpha * Econt + beta * Ecurv + gamma * Eedge

• Econt is analogous to the first-derivative term in the Kass-Witkin-Terzopoulos formulation, but should seek to keep points spaced equally along the curve. Thus,

  Econt = square( d_avg - distance(p[i], p[i-1]) )

  where d_avg is the average distance between points in the curve.
• Ecurv is analogous to a second-derivative term, which seeks to minimize curvature. The finite-difference approximation to the second derivative is

  Ecurv = square( magnitude(p[i-1] - 2*p[i] + p[i+1]) )

• Eedge is a term that tries to draw the snake towards edges, based on gradient magnitude. Thus,

  Eedge = - magnitude( gradient(I(x,y)) )

You should normalize the contributions of each term. That is, divide each of Econt, Ecurv, and Eedge by the largest value of that term within the neighborhood over which you are searching.

II. Evaluating your Implementation (20%)

The algorithm described above contains several different parameters:

• The amount of smoothing (i.e., the width of the Gaussian used in the smoothed gradient computation)
• The size of the neighborhood searched
• The relative contributions of the different terms (alpha, beta, gamma)
• The fraction of points that move at which to stop iterating

Begin your experiments (with an image of your choosing) with the values:

• Gaussian of width 3 pixels
• Searching a 3x3 neighborhood (i.e., the current position of the point plus its immediate horizontal, vertical, and diagonal neighbors).
• alpha = beta = gamma = 1
• Stop when 10% of the points move

Moving Images

Grab the "pond" image sequence from here. Run the active contour on the first image of the sequence (with manual initialization), then run your code on each subsequent image, starting with the position of the curve from the previous image. You will have to extend your code to do something sensible when the contour runs into the edge of the image.

III. Extra Credit

1. Gradually reduce the amount of blurring in the edge functional at later iterations. Comment on the effects.
2. Implement the "termination functional" described in the Kass, Witkin, and Terzopoulos paper. Alternatively, implement some other energy term that looks for corners in the image. Show the results.
3. Implement the logic in the Williams and Shah paper that looks for local maxima in the curvature and sets beta to zero at those points. This has the effect of allowing certain points along the curve to become sharp corners.

Submitting

This assignment is due Wednesday, March 5, 2002 at 11:59 PM Eastern Standard Time. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.

Please submit:

• Your code (as one or more .m files, or source code if you are not working in Matlab).
• The results of your code, including the initial and final positions of the active contour, on some sample images (using the best parameters you were able to find).
• A README or README.html file containing comments on your experiments with different parameters, and any relevant implementation notes.