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,
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,
You can also find another implementation at reference 4.
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