[Activity] 3 : Hough Transform

Activity 3 : Hough Transform

In this activity, we are to explore the method behind the Hough Transform and why the method can accurately detect lines in an image. The input image is this activity is shown below:

Input image

Since Matlab already has a built-in function for Hough Transform, we only need to specify the parameters that in the function. The built-in Matlab function hough outputs a transform matrix, an array for the angle and another array for the distance from the origin. These output data is then subsequently used in other Matlab functions such houghlines and houghpeaks.

The houghpeaks functions extracts the "peaks" in the transform matrix generated by the hough function while the houghlines function extracts the lines in the logical image of the input image based on the angle and distance information together with the transform matrix. The output of the program is shown below.

Output image

Hough Transform

Hough Transform works by converting an image (which is transformed into a binary image and is edge-detected) from its rectangular, coordinate space into the normal or parametric space. Using the input image as the example, the following is the image turned into BW and was edge-detected.

Edge-detected input image.

Each of the remaining pixels in the image has a coordinate (x,y). For each point, we would try to identify all lines that pass through it (which is, infinite). By making the angle of these lines discrete (let's say, at 2, 5, or 10 degree intervals), we would have a list of lines for each point. Since an equation of the line is defined by

y = mx + b,

we could define this lines passing through each point with respect to the (m,b) parameters. However, this would be problematic as the 'm' parameter would yield infinite values for perpendicular lines. Fortunately, we could still represent the lines by writing them in terms of the normal or parametric form. The normal or parametric representation has the form

xcos(θ) + ysin(θ) = ρ.

Since we have already discretized the θ, given a pixel with (x, y) coordinate, we would have respective discrete values of ρ then. The θ and ρ represent the angle line perpendicular to the line containing the point (x,y) with respect to the positive x (+x) axis and the the distance of the line from the origin, respectively. We do this step for all the pixels and listing the resulting theta and rho values

When tabulated, this rho and theta values form an image similar to the one below. The image below is the logical image above represented in the parametric space with theta and rho as the coordinates.

Edge detected image in normal or parametric space.

Each sinusoid represents the rho values for varying theta values. Each (x,y) pixel will have a correspondingly unique (θ, ρ) value. The image above is actually a tabulation of theta and rho values extracted from the logical of the input image. The brighter the pixels in the image above, the more likelihood that lines are present in the image since the curves intersect at the (θ, ρ), indicating collinear points in the (x,y) space.

This is how the Hough Transform can detect lines in the image, by utilizing this tabulating method. The table as a result of this process is called the Hough Transform matrix. By selecting a threshold value, we could eliminate most pixels and choose the brightest ones. The brightest ones would generally mean that it it a candidate point where lines pass through it in the (x,y) space. This process of extracting lines from the parametric space and laying them back to the cartesian space is commonly called as de-houghing.

Code Listing:

function [H, theta, rho, peaks] = hough_act(image)

I = imread(image);

BW = edge(I, 'canny');

[H, theta, rho] = hough(BW);

peaks = houghpeaks(H, 20);

figure, imagesc(H)

figure, imshow(BW)

lines = houghlines(BW, theta, rho, peaks);

figure, imshow(I)

hold on

for k = 1:numel(lines)

x1 = lines(k).point1(1);

y1 = lines(k).point1(2);

x2 = lines(k).point2(1);

y2 = lines(k).point2(2);

line([x1 x2],[y1 y2],'Color','g')

end

hold off

I would like to give myself a grade 0f 10 for this activity for successfully implementing the Hough Transform in Matlab and was able to understand the theory behind it.

References:

[1] Hough Transform Activity Sheet, Dr. Maricor Soriano.

[2] "Hough Transform", PlanetMath.org website, http://planetmath.org/encyclopedia/HoughTransform.html

[3] "Hough Transform", http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm