CSE 455: Computer Vision
Autumn 2010
|
Homework 2
Finding Callouts in Parts Diagrams
Assigned October 11, 2010; Due October 18, 2010 11:59pm
Materials
Download the software and test image you need.
Windows rar file;
Windows zip file;
Linux rar file;
Linux zip file.
Contents
The goal of this assignment is to find and mark the circles
in the diagram, 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
The skeleton code sets up the accumulators (feel free to change if
you wish), reads in the image, and leaves a space for you to write
the code for finding the circles. It also provides the code for
method drawcenters for marking the centers of the circles you have found.
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. Alfred suggests trying a range of radii from 11 to 12.2, so
11.6 would be the middle one.
The program should use the methodology described in class and in Chapter
10 (10.3.4) of the text to find the circles. Thus you will perform the
following steps:
- Compute gradient values Gx and Gy at each pixel. The Sobel operator
should be sufficient.
- 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.)
- Use the angle you obtain and the given radius to estimate the
center of the circle.
- Use the accumulator array to accumulate votes for centers of
circles.
- Once the votes are all accumulated, the bins that have high
counts represent the centers of the circles.
- 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:
- your code for finding circles, inserted into the skeleton code
and, as before, well commented and in a text file, so that
the grader can compile them to working binaries.
- your report including:
Very brief description of the problem being solved
Details of your solution, including the Hough Transform, the
data structure used, and, in particular, how you did the center
clustering
Results shown on the image and discussed in words. What went
right, what went wrong, etc.
Instructions on how to run the program.
This part can be either in MS Word, pdf, or html (web page) format.
If you use a web page, send the URL by email, not the files and images,
and make sure the web page
is viewable by the deadline. Any modification made after the deadline will
not be counted for your grade.
Please email your homework to Alfred (alfredg@cs.washington.edu).
Homework is due on October 18 (Monday) by 11:59 PM. Please plan your
work early.
This is a one-person assignment. You may discuss it, but please turn in your own individual work.