Harvey Mudd College
Computer Science 153
Problem Set 4
Due Friday, November 11, 11:59pm
Section 1: The Hough Transform for Lines
In this section you will implement the Hough transform for lines
and use it to identify the lines in the sketches that you drew in
class. These sketches can be found in:
/cs/cs153/ImagesF05/PS4/Ink/
They are simply grayscale images. In this next section we will work
with the same images represented as stroke data, but for now there's
no new image representation. I recommend starting with the simple
shapes and then moving on to the complete trees as the trees may take
a long time to run.
Part 1: Implementing the Hough Transform
Your only task in this section of the assignment is to implement the
Hough transform for lines as we descibed it in class using the line
representation x*cos(theta) + y*sin(theta) + d = 0. Implementing this
algorithm will
involve addressing the following issues:
- Finding Feature Points.
Because our images are sketches, they
are relatively clean, however, to apply the Hough transform we need a
specific set of feature points. Finding these points will not be
hard, but you may want to consider dropping some of the "lighter"
points which may correspond to edges of lines and may not be necesary
to use. Or you might want to weight a points votes by how "dark" it is.
- Choosing Parameter Bins. How will you discretize theta
and d? Be sure to consider the problems we talked about that arise if
the bins are too big or too small. You may need to play around with
several bin sizes.
- Determining the Number of Lines. Because you are not told
beforehand how many lines you have, your best bet is probably to find
the maxima in your accumulator array. The matlab built-in fuctions
max and findmax may be useful here. Alternatively, one you have a
ballpark idea of how many lines you have, you may decide to refine
your fit by
applying k-means clustering for different values of k near the proposed
number of lines to see if you can get a better fit.
Note that I do not see any clear way to use matrix manipulation to
analyze all the points in parallel, so this implementation will
involve some loops (which is partly why it will be so slow).
If you find you are unhappy with your fit, here are some more things
to consider (as suggested by Z. Dodds):
- To gain additional accuracy in your localization of lines,
consider backprojecting the hypothesized line and then "tweaking" it
a bit by fitting it to the edge pixels. That would mean assigning each
pixel to a line returned by the Hough transform, and then, using the
points assigned to each line, finding a new least-squares line to fit
those points.
- Because of error introduced by discretizing parameter space, it
often helps to blur the values that are being accumulated there. This,
in effect, lets an edge feature contribute evidence not only for
lines going directly though that point, but also for lines
passing nearby. This can be done either as evidence is being accrued
(by adding to neighboring bins) or afterward, by smoothing accumulator
space. The latter might be done by convolving with a Gaussian or
another smoothing mask. Matlab's function conv2 does arbitrary 2d
convolution. Matlab's fspecial function can create Gaussian masks of
any size and any standard deviation.
- The distribution of "votes" in parameter space can be complex
enough that multiple responses can arise from a single image
curve. There are a couple of methods to handle this that you may want
to try:
- Backmapping refers to performing the Hough transform
twice. First, a parameter space is filled with evidence, as usual,
with each edge pixel (or feature) contributing votes along some curve
in parameter space. The second transform uses a new parameter
space. This time each edge pixel (or feature) only contributes votes
to one bin, rather than to all of the bins along some line in
parameter space. What happens is that the bins along that line are
searched in the first parameter space and in order to find the bin
with the maximum evidence. In the new parameter space, that bin
receives all of the votes of the edge pixel under consideration.
- Alternatively, the Hough transform can be performed once. When the
global maximum is found in parameter space, that line is
backprojected into the original image. Then, all of the edge responses
on or near (within some threshold) of that line remove their votes
from parameter space. This can be done by recomputing where they would
vote and subtracting, rather than adding. This is faster (at the
expense of more memory) if each pixel keeps a record of how it
distributed its votes; then, the subtraction is immediate.
Both of these techniques lead to sharper peaks in the accumulator, and
thus easier and more robust contour-finding.
To display your results, overlay the lines found by your Hough
transform on top of the original image. You can plot a line by first
generating a number of x and y values that fall on your line and then
plotting those values using the
"plot" command. For example, to plot the line x*cos(20) + y*sin(20) +
2 = 0 on x ranging from 0 to 5:
x = [0 5];
y = (cosd(20).*x + 2) / sind(20);
plot(x,y);
When you are satisfied with your Hough transform, run it on several of
the simple shape images, and a few of the family trees (these could
take a LONG time). Show the resulting accumulator array (visualize it
as a 2D image by treating bin values as image intensities (you may
have to scale them)) and the lines found overlaid on the original
image. Also include a brief (2-3 paragraph) writeup about your
experience with the hough transform. What worked and what didn't and
what did you finally settle on?
Results:
Possible Extensions
Remember that you need to pursue only one extension in one part of the
assignment, and it can be anything you'd like to investigate. These
are only suggestions.
- Try implementing a Hough transform algorithm for overlapping
circles. There are examples of images with circles in them in
/cs/cs153/Images/a4/synthetic,
/cs/cs153/Images/a4/cds,
and
/cs/cs153/Images/a4/change
Note that you will have to first apply an edge detector (There are
some built in to matlab. The function is called "edge". Use help for
more info). Test out your algorithm on the syntetic circles and the
CDs and if you get really ambitious, try finding (and identifying!) change.
- Generalized Hough transform
The Hough transform requires that the curves being sought have a known
parameterization. However, it is possible to use it for consistent 2d
shapes even if their parameterization is unknown, by constructing an
implicit representation through its boundary points.
This is known as the generalizes Hough transform. Basically, given
a 2d shape that you are seeking in images, choose any arbitrary
reference point on that shape. Find the vector to that reference point
from each point on the boundary of the shape and store all of those
vectors in a table, called an R table.
Then, assuming translation but no scaling and no rotation, an edge
pixel contributes a vote to each parameter space bin that is a
displacement of that pixel by some vector in the R table. If scaling
and rotation are allowed, the R-table vectors contribute votes for
each orientation and scale considered. With a shape of your own
choosing, implement the generalized Hough transform (at least for
translation-only) -- for example, this would be an alternative method
for finding the "squiggle" shapes in the game of Set.
- The Hough transform -- in action As always, I'm interested
in display tools for showing the process behind visual algorithms, for
example in a tool that shows the sequential changes to parameter space
-- say, as the pixels in the edge image changed color to indicate that
they have been used.