Hough Transform

In this assignment you will be implementing some basic image processing algorithms and putting them

together to build a Hough Transform based line detector. Your code will be able to find the start and end

points of straight line segments in images. We have included a number of images for you to test your line

detector code on. Like most vision algorithms, the Hough Transform uses a number of parameters whose

optimal values are (unfortunately) data dependent (i.e., a set of parameter values that works really well on

one image might not be best for another image). By running your code on the test images you will learn

about what these parameters do and how changing their values effects performance.

Many of the algorithms you will be implementing as part of this assignment are functions in different

Python image processing and computer vision toolbox.

You are not allowed to use such functions in this assignment. You may however compare your output to

the output generated by the pre-existing functions to make sure you are on the right track.

1 Instructions

1. Integrity and collaboration: Students are encouraged to work in groups but each student must submit their own work. If you work as a group, include the names of your collaborators in your write

up. Code should NOT be shared or copied. Please DO NOT use external code unless permitted.

Plagiarism is strongly prohibited and may lead to failure of this course.

2. Start early! Especially for those not familiar with Python. For each assignments you may need to

install a couple of python libraries, so if you are not familiar with installing different libraries make

sure to start early. We use Python 3.x (not python 2.x). For this assignment you need to have numpy,

opencv, and glob libraries installed. We use opencv version 3.4.1 or higher. See appendix if you dont

have python installed on your system.

3. If you have any question, please look at Piazza first. Other students may have encountered the same

problem, and it may be solved already. If not, post your question in the specified folder. TAs will

respond as soon as possible.

4. Write-up: Your write-up should mainly consist of three parts, your answers to theory questions, the

resulting images of each step (for example, the output of houghScript.py), and the discussions for

experiments. Please note that we DO NOT accept handwritten scans for your write-up in this assignment. Please type your answers to theory questions and discussions for experiments electronically.

5. Instructions for gradescope Log onto http://gradescope.com with your Andrew ID and you

should be registered for the course. Submit the assignment by the specified due date. Each answer

in the write-up should be on a different page. In gradescope, you need to mark the pages in the PDF

which correspond to each question.

6. Submission: Your submission for this assignment should be a zip file, <andrew-id.zip>, composed of your write-up (pdf), your python implementations (including helper functions), and your

implementations and results for extra credit (optional). Please make sure to remove the data/,

result/ folders, and any other temporary files that you’ve generated.

Your final upload should have files arranged in this layout:

1

• <AndrewID>

– <AndrewID>.pdf

– python

∗ houghScript.py

∗ myImageFilter.py

∗ myImageFileterX.py

∗ myEdgeFilter.py

∗ myHoughTransform.py

∗ myHoughLines.py

∗ myHoughLinePrune.py

∗ yourHelperFunction1.py(optional)

∗ yourHelperFunction2.py(optional)

Assignments that do not follow this submission rule will be penalized 10% of the total score.

7. Please make sure that the file paths that you use are relative and not absolute. That is, it shouldn’t be

imread(‘/name/Documents/subdirectory/hw1/data/abc.jpg’) but

imread(‘../data/abc.jpg’).

2 Theory Questions (25 points)

Type down your answers for the following questions in your write-up. Each question should only take a

couple of lines. In particular, the “proofs” do not require any lengthy calculations. If you are lost in many

lines of complicated algebra you are doing something much too complicated (or perhaps wrong). Each

question from Q2.1 to Q2.5 are worth 5 points each.

Q2.1 Show that if you use the line equation xcosθ + ysinθ − ρ = 0, each image point (x, y) results in a

sinusoid in (ρ, θ) Hough space. Relate the amplitude and phase of the sinusoid to the point (x, y).

Q2.2 Why do we parameterize the line in terms of ρ, θ instead of slope and intercept (m, c)? Express the

slope and intercept in terms of ρ and θ.

Q2.3 Assuming that the image points (x, y) are in an image of width W and height H (i.e., x ∈ [1, W], y ∈

[1, H]), what is the maximum absolute value of ρ and what is the range of θ?

Q2.4 For points (10, 10), (15, 15) and (30, 30) in the image, plot the corresponding sinusoid waves in Hough

space (ρ, θ) and visualize how their intersection point defines the line (what is (m, c) for this line?).

Please use Python to plot the curves and report the result in your write-up.

Q2.5 How does the dimension of parameter space affects Hough Transform method? What would you do

when the parameter space is high , i.e., 3D or 4D instead of 2D? Briefly explain your method in the

write-up.

3 Implementation (75 points)

We have included a wrapper script named houghScript.py that takes care of reading in images from a

directory, making function calls to the various steps of the Hough transform (the functions that you will

be implementing) and generates images showing the output and some of the intermediate steps. You are

free to modify the script as you want, but note that TAs will run the original houghScript.py while

grading. Please make sure your code runs correctly with the original script and generates the required

output images..

Every script/function you write in this section should be included in the python/ directory. As for the

resulting images, please include them in your write-up

2

3.1 Convolution (10 points)

Write a function that convolves an image with a given convolution filter

def myImageFilter(img_gray, h):

return Img1

As input, the function takes a greyscale image (imggray) and a convolution filter stored in matrix h. The

output of the function should be an image Im1 of the same size as imggray which results from convolving

imggray with h. You can assume that the filter h is odd sized along both dimensions. You will need to

handle boundary cases on the edges of the image. For example, when you place a convolution mask on

the top left corner of the image, most of the filter mask will lie outside the image. One possible solution is

to pad the image such that pixels lying outside the image boundary have the same intensity value as the

nearest pixel that lies inside the image.

Your code cannot use pre-exising convolution functions in python such as

numpy.convolve, scipy.signal.convolve2d, imfilter, conv2, convn, filter2, etc, or

other similar functions. You need to write your functions from scratch. You may compare your output to

these functions for comparison and debugging.

3.2 Convolution with One for Loop (10 points)

Write a function that does convolution with only one for loop. (If you already do so in Q3.1, good job,

just copy it.) Also, briefly describe how you implement it in your write-up. Illustrations helpful for understanding is highly encouraged.

def myImageFilterX(img_gray, h):

return Im1

Vectorization is an important, must-learn technique while writing python. Comparing to for loop, vectorization dramatically increases the speed, especially when dealing with big data. Therefore, it would be a

good habit to avoid loops and use vectorization as much as possible. In Q3.1, it’s straightforward to implement the convolution with two for loops. However, through vectorization, it is possible to use only one for

loop. This may be quite difficult, especially for those who just start learning python, but we still encourage

you to give it a try.

3.3 Edge Detection (10 points)

Write a function that finds edge intensity and orientation in an image. Include the output of your function

for one of the given images in your writeup.

def myEdgeFilter(img_gray, sigma):

return ImEdge,Io,Ix,Iy

The function will input a greyscale image (imggray) and sigma (scalar). sigma is the standard deviation

of the Gaussian smoothing kernel to be used before edge detection. The function will output ImEdge, the

edge magnitude image; Io the edge orientation image and Ix and Iy which are the edge filter responses

in the x and y directions respectively.

First, use your convolution function to smooth out the image with the specified Gaussian kernel. This

helps reduce noise and spurious fine edges in the image. You may use Gauss2D.py to get the Gaussian

filter. The size of the Gaussian filter should depend on sigma (e.g., hsize=2*ceil(3*sigma)+1). To

find the image gradient in the x direction Ix, convolve the smoothed image with the x oriented Sobel filter.

Similarly, find Iy by convolving the smoothed image with the y oriented Sobel filter.

3

Figure 1: Example of edge intensity image

The edge magnitude image Im and the edge orientation image Io can be calculated from Ix and Iy.

In many cases, the high gradient magnitude region along an edge will be quite thick. For finding lines

its best to have edges that are a single pixel wide. Towards this end, make your edge filter implement non

maximal suppression, that is for each pixel look at the two neighboring pixels along the gradient direction

and if either of those pixels has a larger gradient magnitude then set the edge magnitude at the center pixel

to zero. Map the gradient angle to the closest of 4 cases, where the line is sloped at almost 0◦

, 45◦

, 90◦

, 135◦

.

For eg, 20◦ would map to 0◦ and 30◦ would map to 45◦

.

For more details on non-maximum suppression, please refer to section 4 of this handout. Your code cannot

call pre-existing edge functions from python libraries. An example of edge intensity image can be seen in

Figure 1.

We encourage writing vectorized code for efficiency.

3.4 Hough Transform (15 points)

Write a function that applies the Hough Transform to an edge magnitude image.

def myHoughTransform(ThrImEdge, threshold, rhoRes, thetaRes):

return H, rhoScale, thetaScale

ThrImEdge is the binary image resulted from the edge magnitude image via threshold (scalar). ThrImEdge

pixels with value lower than the threshold are zero and the remaining are one. rhoRes (scalar) and

thetaRes (scalar) are the resolution of the Hough transform accumulator along the ρ and θ axes respectively. For example, if thetaRes = 5◦ and θ ∈ [0, 360◦

], then number of bins along θ axis is 360/5 = 72. H

is the Hough transform accumulator that contains the number of ‘votes’ for all the possible lines passing

through the image. rhoScale and thetaScale are the arrays of ρ and θ values over which myHoughTransform

generates the Hough transform matrix H. For example, if rhoScale(i) = ρi and thetaScale(j) = θj ,

then H(i,j) contains the votes for ρ = ρi and θ = θj .

4

First, threshold the edge image to get ThrImEdge. Each pixel (x, y) above the threshold is a possible

point on a line and votes in the Hough transform for all the lines it could be a part of. Parametrize lines in

terms of θ and ρ such that ρ = xcosθ + ysinθ. Range of ρ and θ should be such that each line in the image

corresponds to a unique pair (ρ, θ).

The accumulator resolution needs to be selected carefully. If the resolution is set too low, the estimated

line parameters might be inaccurate. If resolution is too high, run time will increase and votes for one line

might get split into multiple cells in the array.

Your code cannot call pre-existing python functions for hough transform.

3.5 Finding Lines (15 points)

def myHoughLines(H, nLines):

return peakRho, peakTheta

H is the Hough transform accumulator and nLines is the number of lines to return. Outputs contain the

indicies of the accumulator array H that correspond to a local maxima. peakRho and peakTheta are both

1d vectors that contain the parameters (ρ and θ respectively) of the lines found in an image.

Figure 2: Hough transform result.

Ideally, you would want this function to return the ρ and θ values for the nLines highest scoring cells

in the Hough accumulator. But for every cell in the accumulator corresponding to a real line (likely to be a

locally maximal value), there will probably be a number of cells in the neighborhood that also scored highly

but shouldn’t be selected. These non maximal neighbors can be removed using non maximal suppression.

Note that this non maximal suppression step is different to the one performed earlier. Here you will consider all neighbors of a pixel, not just the pixels lying along the gradient direction. Implement your own

non maximal suppression. Once you have suppressed the non maximal cells in the Hough accumulator,

return the line parameters corresponding to the strongest peaks in the accumulator. If you find a suitable

function on the Internet (you must acknowledge/cite the source in your write-up as well as hand in the

source in your python/ directory).

5

3.6 Fitting Line Segments for Visualization (15 points)

def myHoughLineSegments(img_rgb,ThrImEdge,peakRho,peakThetas,rhoScale,thetaScale):

return OutputImage

Now you have the parameters ρ and θ for each line in an image. However, this is not enough for visualization. We still need to prune the detected lines into line segments that do not extend beyond the objects they

belong to. Here you need to write your myHoughLineSegments, this function get imgrgb, ThrImEdge,

peakRho, peakThetas, rhoScale, thetaScale and return OutputImage. OutputImage demonstrate the input image and the hough transform results (see Figure 3). In myHoughLineSegments you

need to prune the detected lines into line segments that do not extend beyond the objects they belong to.

Then, you need to draw them on the imgrgb and return the results.

As shown in Fig. 3, the result is not perfect, so don’t worry if the performance of your implementation is

not that great.

Run the houghScript.py file and include the aforementioned visual results (Im1, ImEdge, ThrImEdge,

H, OutputImage) in your write-up.

Figure 3: Line segments result

4 Experiments (10 points)

Did your code work well on all the image with a single set of parameters? How did the optimal set of

parameters vary with images? Which step of the algorithm causes the most problems? Did you find any

changes you could make to your code or algorithm that improved performance?

Tabulate the different experiments that you have performed with their results in your write-up. Also describe how well your code worked on different images, what effect the parameters had on any improvements that you made to your code to make it work better. If you made changes to your code that required

changes to the results generation script, include your updated version in your submission.

6

Appendix

Installing Python 3

If you don’t have python installed the easiest way is use Anaconda (https://docs.anaconda.com/anaconda/install/)

to install python. Anaconda also let you install other packages and libraries easily.

Non-maximum Suppression

Non-maximum suppression (NMS) is an algorithm used to find local maxima using the property that the

value of a local maximum is greater than its neighbors (see Figure 4). To implement the NMS in 2D image,

one can move a 3 × 3 (or 7 × 7) filter over the image. At every pixel, it suppresses the value of the center

pixel (by setting its value to 0) if its value is not greater than the value of the neighbours. To use NMS for

edge thinning, one should compare the gradient magnitude of the center pixel with the neighbors along

the gradient direction instead of all the neighbors. To simplify the implementation, one can quantize the

gradient direction into 8 groups and compare the center pixel with two of the 8 neighbors in the 3 × 3

window according to the gradient direction. For example, if the gradient angle of a pixel is 30 degrees, we

compare its gradient magnitude with the north east and south west neighbors and suppress its magnitude

if it’s not greater than the two neighbors.

Figure 4: NMS for 2D

7

Sale!