# Hough Transform for Line Detection –An Intro and Sample Code

*By roman10 On August 9, 2011 · 5 Comments*

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

## 5 comments on “Hough Transform for Line Detection –An Intro and Sample Code”

### Leave a Reply Cancel reply

### Categories

- Android Apps (19)
- Android Audio Editor (1)
- OneClick Movie Maker (1)
- TS 2 (3)
- Video Converter Android (8)
- Video2Gif (1)

- Android Tutorial (31)
- Android Dev Tools (1)
- API illustrated (8)
- Multimedia API (3)

- ffmpeg on Android (5)
- NDK (7)
- UI (9)
- Animation (2)

- Code Snippet (2)
- Coding Beyond Technique (18)
- a word, a world (4)
- Bug Rectified (4)
- Programming Habit (1)
- Software as a Career (1)
- Software as User Experience (1)

- Compilers and Related (2)
- ELF (2)

- Computer Languages (31)
- C/C++ (13)
- Java (9)
- JavaScript (2)
- PHP (1)
- Python (8)

- Data Structure & Algorithms (29)
- Bits (1)
- Data Structure (5)
- Integers (10)
- BigInteger (1)
- Prime (4)

- Search (3)
- Sorting (5)
- Strings (5)

- Database (1)
- SQLite (1)

- Digital Signal Processing (33)
- Distributed Systems (17)
- Apache Cassandra (6)
- Apache Hadoop (8)
- Apache Avro (3)

- Apache Nutch (3)
- Apache Solr (1)

- Linux Study Notes (40)
- crontab (1)
- Linux Kernel Programming (8)
- Linux Programming (12)
- IPC (2)
- Linux Network Programming (5)
- Linux Signals (2)

- Linux Shell Scripting (1)
- ssh (3)

- Machinery (30)
- misc (1)
- My Ideas (1)
- My Project (3)
- Mobile Caching (1)
- Selective Decoding (2)

- My Publication (1)
- My Readings (1)
- Networking (15)
- Program for Performance (8)
- Uncategorized (1)
- Virtual Machine (2)
- Web Dev (8)
- web components (3)

- Android Apps (19)
### Recent Comments

- fangliang on How to Build ffmpeg with NDK r9
- fangliang on How to Build ffmpeg with NDK r9
- Alex on How to Build Android Applications Based on FFmpeg by An Example
- wnc on How to Build ffmpeg with NDK r9
- siddharth on Modification of RED AQM in NS2

### Archives

- October 2013 (1)
- August 2013 (4)
- May 2013 (2)
- April 2013 (1)
- March 2013 (4)
- December 2012 (2)
- November 2012 (6)
- October 2012 (6)
- September 2012 (3)
- August 2012 (13)
- July 2012 (15)
- June 2012 (3)
- May 2012 (8)
- April 2012 (4)
- March 2012 (13)
- February 2012 (19)
- January 2012 (9)
- December 2011 (11)
- November 2011 (12)
- October 2011 (4)
- September 2011 (12)
- August 2011 (16)
- July 2011 (15)
- June 2011 (6)
- May 2011 (10)
- April 2011 (13)
- March 2011 (20)
- February 2011 (4)
- November 2010 (2)
- May 2010 (1)
- April 2010 (1)
- February 2010 (1)

hi there, wonderful article, and a good understand! definitely one for my bookmarking.

Hi,I test it but I don’t understand what it is show at last,please help me,dose it have any output?

I wrote the program to show the algorithm. You’ll need to read through the code in order to understand it. It has no output. But you can change it to suit your needs. For example, decide whether an image contains a lot of straight lines or not.

arc detection using hough transform

hi,i am need to program that to detect barcode of image with hogh transform,please help me.please you send matlab code.