COS 496 - Computer Vision Assignment #2

Spring, 2002

Due Tues. Mar. 5

I. Questions (20%)

1. When we were discussing the Hough transform for lines, we saw that parameterizing lines by slope and intercept led to a less uniform parameterization than angle and distance from center. To analyse this nonuniformity, assume that you are given 1000 lines (of random orientations) and you must assign them to 5 buckets based on orientation.
   1. How many lines fall in each bucket if the buckets are assigned uniformly based on angle?
   2. How many lines fall in each bucket if the buckets are assigned uniformly based on slope? For concreteness, assume that the slopes of the buckets are -2, -1, 0, 1, 2 and that each line is assigned to the bucket that is nearest to its slope.
2. The finite size of an image implies that, on average, the length in pixels of the visible portions of lines close to the image center C is greater than that of lines distant from C. How does this bias the Hough transform? How could you counter this bias?

II. Implementing Active Contours (60%)

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.

III. 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

Choose one of our image sequences, 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.

IV. 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 us your 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 Tuesday, 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), the results of your code on some sample images (using the best parameters you were able to find), and a README or README.html file containing the answers to the questions in part I, some comments on your experiments with different parameters, and any implementation notes you would like us to know about. If you find it more convenient to hand in the written portion of the assignment on paper, that will be accepted as well.