Hough transform was originally proposed to detect lines in images. It is then generalized to detect arbitrary shapes that can be represented by a set of parameters. This blog only covers Standard Hough Transform for line detection.

**The Basic Idea**

The basic idea of Standard Hough Transform can be divided into three phrases.

1. Represent each point of image boundary in some parameter space.

2. a voting procedure is carried out in the parameter space.

3. compare the local maxima found in the voting against certain thresholds to decide whether an instance of the search object exists.

Take the line detection as an example. A straight line can be represented as,

ρ=xcosθ+ysinθ (1)

where ρ is the distance between the line and origin, θ is the angle of the vector from origin to the nearest point of the line. (To indicate θ and ρ are constants, we mark them as θ0 and ρ0) As you see in hte left part of Figure 1 below,

*Figure 1. A Straight Line in Image Domain and Hough Domain*

For formula (1) above, if we view x, y as constant, and ρ, θ as parameters, then we have the right part of Figure 1. Furthermore, when ρ, θ changes and x, y being constant (let’s say x = x0, y = y0), the sinusoidal curve in the right part actually represent all the possible lines that passing through point (x0, y0) in the image domain.

**Thus, for each point in image domain, there’s a corresponding curve in hough domain. **

If there’s a line in the image domain, which consists of many points, then there’ll be an intersection for all the curves of those points in hough domain. (The intersected point will be (θ0, ρ0) as mentioned before)** In other words, a line in image domain is essentially a point in hough domain. **Therefore, the problem of detecting lines is equivalent to find an intersection in hough space.

In voting stage, an accumulator is established with a discrete set of (θ, ρ) values. For each point in the image, we calculate the value of ρ for a sampled set of θ, and the number of votes in the corresponding accumulator cell is incremented by 1.

At the end of voting, the maxima are retrieved and if the voting count is more than a threshold, we consider there’s a high possibility a line exists with the corresponding (θ, ρ) value.

**A Sample Implementation**

The hough transform line detection algorithm is implemented as below in Matlab,

function [ O ] = hough_transform( fPath )

% fPath: the path to the image

% this program implements the Standard Hough Transform

% to detect lines

rhoStep=1;

thetaStep=1;

rhoDiffThresholdForLine=rhoStep/8;

I=imread(fPath, 'gif');

%find the edge of the image

BW=edge(I,'canny');

%imshow(BW);

%hough transform

%define the accumulator range

rho=1:rhoStep:sqrt((size(BW,1))^2 + (size(BW,2))^2);

theta=0:thetaStep:180-thetaStep;

accu=zeros(length(rho), length(theta));

%get the pixel indices that contains a point

[rowInd, colInd]=find(BW);

%for each point, plot all the lines (sampled) pass through it

%at theta-rho plane

for li=1:1:length(rowInd)

for lk=1:1:length(theta)

` ltheta=theta(lk)*pi/180;`

lrho=colInd(li)*cos(ltheta) + rowInd(li)*sin(ltheta);

%binning the lrho value

diffs=abs(lrho-rho);

%we only increase the count of most similar ones

%introducing a threshold instead choosing the

%min

minDiff=min(diffs);

` if (minDiff<rhoDiffThresholdForLine)`

minDiffInd=find(diffs==minDiff);

for lm=1:1:length(minDiffInd)

accu(minDiffInd(lm),lk) = accu(minDiffInd(lm),lk) + 1;

end

end

end

end

%find local maxima

accuBMax=imregionalmax(accu);

[rho_candi, theta_candi]=find(accuBMax==1);

%find the points in theta-rho plane that has count more than

%threshold

linePoints=0;

%get a list of lines detected with their rho and theta values

rhoLines=[];

thetaLines=[];

for li=1:1:length(rho_candi)

l_accu=accu(rho_candi(li), theta_candi(li));

` if (l_accu<=0)`

%do nothing

` elseif (l_accu > 25)`

linePoints=linePoints+1;

rhoLines=[rhoLines;rho(rho_candi(li))];

thetaLines=[thetaLines;theta(theta_candi(li))];

end

end

end

You can also find another implementation at reference 4.

**References:**

1. http://en.wikipedia.org/wiki/Hough_transform

2. Hough Transform: http://www.cs.jhu.edu/~misha/Fall04/GHT1.pdf

3. IDL Reference Guide. Available at http://idlastro.gsfc.nasa.gov/idl_html_help/HOUGH.html

4. Matlab code: Line Detection via Standard Hough Transform

http://www.mathworks.com/matlabcentral/fileexchange/4983-line-detection-via-standard-hough-transform