Materials

Download the software and images you need: zip file. The code we give is in C/C++. You can work on any platform using any compiler. We provide CMake file to build your project. Ask Ezgi (ezgi@cs.washington.edu) any questions about the code or how to use CMake.

Contents

The goal of this assignment is to find and mark the circles in the diagrams, using the Hough transform for circles to find them and drawcenters to mark them in red as shown below. (Note: the circles with the numbers are all marked, but some of them are not showing up well in the reduced-size jpg image.

document image with marked circles

We provide you with the original document image and skeleton code, including the code to put red marks on the image, after you have found the circles.

What To Do

NOTE: The equations in the text (10.18, 10.19) are correct, but the algorithm that follows them has the +/- and sin/cos reversed. To avoid confusion, here are the correct formulas for the program you are writing, assuming that i is the row index (ie. vertical axis) and j is the column index (ie. horizontal axis).

r0 = i - R * sin(angle);
c0 = j + R * cos(angle);

This makes sense because the sin should be associated with vertical and cos with horizontal.

The radius R of the circles we are looking for is an argument to the program, but digital images are never exact, so you should actually look for circles whose radii are in a small range about the radius you give it. The radius of the "callout" circles in the sample input image is approximately 11.6. Though it seems strange to make it floating point, recall that the algorithm uses sin and cosine, so floating point actually makes sense. We suggest trying a range of radii from 11 to 12.2 for the first image , so 11.6 would be the middle one. You can figure out the range for the other images.

The program should use the methodology described in class and in Chapter 10 (10.3.4) of the text to find the circles in each image. Thus you will perform the following steps:

1. Compute gradient values Gx and Gy at each pixel. The Sobel operator should be sufficient.
2. Compute the gradient magnitude M. If it is bigger than a threshold (ie. edge pixel), then also compute the gradient angle A.
Use atan2(Gy, Gx) to compute the angle, being sure to handle the special cases that can occur. (ie. Don't let it blow up, and any combination of Gx and Gy should produce a valid angle.)
3. Use the angle you obtain and the radius you are trying to estimate the center of the circle.
4. Use the accumulator array to accumulate votes for centers of circles.
5. Once the votes are all accumulated, the bins that have high counts represent the centers of the circles. Since each image has a different size and contains a different number of circles, you need to have a different threshold to pick high counts for different images. You need to use the third parameter (center threshold) for this.
6. However, there will be some bins that are adjacent and actually represent the same circle, because of digitizing effects. So include a postprocessing step that combines adjacent bins with significant counts in order to get just one center for each circle.

Evaluation

• Working Program: 4 points
• Circle Finding Quality: 3 points
• Center Clustering: 2 points
• Report: 1 point

Turnin

You must turn in:

1. your code for finding circles, inserted into the skeleton code and, as before, well commented so that the grader can compile them to working binaries.
2. your report including:
   1. Very brief description of the problem being solved
   2. Details of your solution, including the Hough Transform, the data structure used, and, in particular, how you did the center clustering
   3. Results shown on the image and discussed in words. What went right, what went wrong, etc.
   4. Instructions on how to run the program.
   This part can be either in MS Word or PDF format.

Dropbox

Upload your report and code to the homework dropbox HERE. Any modification made after the deadline will not be counted for your grade.

Homework is due on October 14 (Tuesday) by 11:59 PM. Please plan your work early. You can submit until October 16 but you will lose 10% of your grade for every late day.

This is a one-person assignment. You may discuss it, but please turn in your own individual work.