## Description

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, that is, 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 the

Matlab image processing toolbox. You are not allowed to use calls to functions in this assignment.

You may however compare your output to the output generated by the image processing toolboxes

to make sure you are on the right track.

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 those not familiar with Matlab.

3. Write-up: Your write-up should mainly consist of three parts, your answers to theory questions, the resulting images of each step, that is, the output of houghScript.m, 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.

4. Submission: Your submission for this assignment should be a zip file, —tt ¡ust login id.zip¿,

composed of your write-up, your Matlab implementations (including any helper functions),

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

the data/ and result/ folders, the houghScript.m and drawLine.m scripts, and any other

temporary files you generated.

Your final upload should have the files arranged in this layout:

•

–

– matlab

∗ myImageFilter.m

∗ myEdgeFilter.m

∗ myHoughTransform.m

∗ myHoughLines.m

1

∗ any helper functions you need

– ec

∗ myHoughLineSegments.m

∗ ec.m

∗ your own images

∗ your own results

5. File paths: Please make sure that any file paths that you use are relative and not absolute.

Not imread(’/name/Documents/subdirectory/hw1/data/xyz.jpg’)

but imread(’../data/xyz.jpg’).

1 Theory questions

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 wrong).

Q1.1 Hough Transform Line Parametrization (20 points)

1. Show that if you use the line equation ρ = x cos θ + y sin θ 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).

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

Express the slope and intercept in terms of (ρ, θ).

3. Assuming that the image points (x, y) are in an image of width W and height H, that is,

x ∈ [1, W], y ∈ [1, H], what is the maximum absolute value of ρ, and what is the range for θ?

4. For point (10, 10) and points (20, 20) 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 Matlab to plot the curves and report the result in your

write-up.

2 Implementation

We have included a main script named houghScript.m 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.m while grading. Please make sure your code runs correctly with the original script

and generates the required output images.

Every script and function you write in this section should be included in the matlab/

directory. Please include resulting images in your write-up.

Q2.1 Convolution (20 points)

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

function [img1] = myImageFilter(img0, h)

2

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

The output of the function should be an image img1 of the same size as img0 which results from

convolving img0 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 solution is to output a zero value at all these locations, the better thing to do 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.

You can call Matlab’s function to pad array. However, your code cannot call on Matlab’s

imfilter, conv2, convn, filter2 functions, or any other similar functions. You may compare

your output to these functions for comparison and debugging. This function should be vectorized.

Examples and meaning of vectorization can be found here. Specifically, try to reduce the number

of for loops that you use in the function as much as possible.

Q2.2 Edge detection (20 points)

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

your function for one of the given images in the handout.

function [img1] = myEdgeFilter(img0, sigma)

The function will input a greyscale image (img0) and scalar (sigma). sigma is the standard deviation of the Gaussian smoothing kernel to be used before edge detection. The function will output

img1, the edge magnitude image.

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. Use fspecial to get the kernel for

the Gaussian filter. The size of the Gaussian filter should depend on sigma (e.g., hsize = 2 *

ceil(3 * sigma) + 1).

The edge magnitude image img1 can be calculated from image gradients in the x direction and

y direction. To find the image gradient imgx in the x direction, convolve the smoothed image with

the x-oriented Sobel filter. Similarly, find image gradient imgy in the y direction by convolving the

smoothed image with the y-oriented Sobel filter. You can also output imgx and imgy if needed.

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-maximum 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◦

, and 135◦

. For example, 30◦ would map to 45◦

.

For more details about non-maximum suppression, please refer to the last page of this handout.

Your code cannot call on Matlab’s edge function, or any other similar functions. You may use

edge for comparison and debugging. A sample result is shown in Figure 1.

Q2.3 The Hough transform (20 points)

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

output for one of the images in the write-up.

function [H, rhoScale, thetaScale] = myHoughTransform(Im, threshold,

rhoRes,thetaRes)

Im is the edge magnitude image, threshold (scalar) is a edge strength threshold used to ignore

pixels with a low edge filter response. rhoRes (scalar) and thetaRes (scalar) are the resolution of

3

Figure 1: Edge detection result.

the Hough transform accumulator along the ρ and θ axes respectively. 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) = θi

, then

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

.

First, threshold the edge image. 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 ρ = x cos θ + y sin θ, θ ∈ [0, 2π] and ρ ∈ [0, M]. M should be large

enough to accommodate all lines that could lie in an image. Each line in the image corresponds

to a unique pair (ρ, θ) in this range. Therefore, θ values corresponding to negative ρ values are

invalid, and you should not count those votes.

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 Matlab’s hough function, or any other similar functions. You may use

hough for comparison and debugging. A sample visualization of H is shown in Figure 2.

Figure 2: Hough transform result.

4

Q2.4 Finding lines (15 points)

Write a function that uses the Hough transform output to detect lines,

function [rhos, thetas] = myHoughLines(H, nLines)

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

rhos and thetas are both nLines ×1 vectors that contain the row and column coordinates of peaks

in H, that is, the lines found in the image.

Ideally, you would want this function to return the ρ and θ coordinates 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 high but should not be selected. These non maximal neighbors

can be removed using non maximal suppression. Note that this non maximal suppression step is

different from the one performed earlier. Here you will consider all neighbors of a pixel, not just

the pixels lying along the gradient direction. You can either implement your own non maximal

suppression code or find a suitable function on the Internet (you must acknowledge and cite the

source in your write- up, as well as hand in the source in your matlab/ directory). Another option

is to use Matlab function imdilate.

Once you have suppressed the non maximal cells in the Hough accumulator, return the coordinates corresponding to the strongest peaks in the accumulator.

Your code cannot call on Matlab’s houghpeaks function or other similar functions. You may

use houghpeaks for comparison and debugging.

Q2.5 Fitting line segments for visualization (5 points)

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. This is done by houghlines and drawLines.m. See the script

houghScript.m for more details. You can modify the parameters of houghlines and see how

the visualizations change. As shown in Figure 3, the result is not perfect, so do not worry if the

performance of your implementation is not good. You can still get full credit as long as your

implementation makes sense.

Figure 3: Line segment result.

Q2.5x Implement houghlines yourself (extra: 10 points)

In Q2.5, we used the Matlab built-in function houghlines to prune the detected lines into line

segments that do not extend beyond the objects they belong to. Now, its our turn to implement

one ourselves! Please write a function named myHoughLineSegments and then compare your results

with the Matlab built-in function in your write-up. Show at least one image for each and briefly

describe the differences.

5

function [lines] = myHoughLineSegments(lineRho, lineTheta, Im)

Your function should output lines as a Matlab array of structures containing the pixel locations

of the start and end points of each line segment in the image. The start location of the i

th line

segment should be stored as a 2 × 1 vector lines(i).start and the end location as a 2 × 1 vector

in lines(i).stop. Remember to save your implementation in the ec/ directory.

Your code cannot call on Matlab’s houghlines function, or any other similar functions. You may

use houghlines for comparison and debugging.

3 Experiments

Q3.1 (15 points)

Use the script included to run your Hough detector on the image set and generate intermediate

output images. Include the set of intermediate outputs for one image in your write-up. 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? In your

write-up, you should describe how well your code worked on different images, what effect do the

parameters have and any improvements you made to your code to make it work better.

4 Try your own images!

Q4.1x Implement houghlines yourself (extra: 10 points)

Take five pictures, either with a camera of your own, or from the Internet. Write a script ec.m

to take care of reading in your images (use a relative path here, not absolute), making function

calls to the various steps of the Hough transform, and generating images showing the output and

some of the intermediate steps (like houghScript.m). Submit your own images and ec.m in ec/.

Please include resulting images in your write-up.

5 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. To implement the

NMS in 2D image, you can move a 3 × 3 (or 7 × 7, etc.) filter over the image. At every pixel,

the filter suppresses the value of the center pixel (by setting its value to 0) if its value is not greater

than the value of the neighbors. To use NMS for edge thinning, you 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, you 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◦

, we compare its gradient

magnitude with the north-east and south-west neighbors and suppress its magnitude if it is not

greater than these two neighbors.

6