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,

image

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

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

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

    • roman10 on said:

      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.

  3. arc detection using hough transform

  4. khadijeh on said:

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Set your Twitter account name in your settings to use the TwitterBar Section.