The Hough transform is a robust global technique to detect lines in a binary image formed of edges as they emerge after edge detection. It is named after Paul Hough, who patented it in 1962. It has been popularized by the paper “Use of the Hough Transformation to Detect Lines and Curves in Pictures” written by Duda and Hart.

The Hough transform establishes a relation between the Cartesian (x, y) space and a polar (d, φ) space using the point-line duality of these two spaces. A line in (x, y) space corresponds to a point in (d, φ) space. The following equations explain the mathematics behind the transformation. The equation of a line is

y = ax + b

If you substitute the parameters a and b with

$$a=-\frac{cos \varphi}{sin \varphi}$$

and

$$b=\frac{d}{sin \varphi}$$

and rearrange, you end up with the following equation of a line:

x ⋅ cosϕ + y ⋅ sinφ = d

If you remember linear algebra, this is just the equation of a line in normal form,

r ⋅ n − d = 0

where r is the position vector of a point $\begin{pmatrix} x & y \end{pmatrix}^T$ on the line and n is a normal vector perpendicular to the line. It so happens that the normal vector $\begin{pmatrix} cos \varphi & sin \varphi \end{pmatrix}^T$  is of length 1, and thus d is the distance of the line to the origin.

The figure explains the geometric significance of this normal equation of a line:

All points (infinitely many) on a line are characterized by a single pair of (d, ϕ) values. Likewise, if you take a single point in Cartesian (x, y) space, this single point is part of all possible lines (infinitely many) through this point.

For practicality, both the original (x, y) space and the (d, ϕ) space are discrete spaces. By convention and with no loss to generality, the origin of the (x, y) space is considered to be in the middle of the image. Then, the maximum value of d can be calculated with the formula

$$d_{max}=\frac{1}{2}\sqrt{width^2+height^2}$$

Thus, the range of parameters d and ϕ is given by

d in left [ -d_{max}, d_{max} right ] textrm{ if } phi in left [ 0, pi right ]

or

d in left [ 0, d_{max} right ] textrm{ if } phi in left [ 0, 2pi right ]

I mentioned that infinitely many lines pass through a single point. Of course the code cannot handle infinity, but it has to take into account every line passing through the point given the chosen discrete (d, ϕ) space. This is done by treating the image in (d, ϕ) Hough space as an accumulator. Every point which is set in (x, y) space casts votes for all of the possible lines in (d, ϕ) space. The following little code snippet shows how this could be done.

for (y=-height/2; y<height/2; ++y)
{
  for(x=-width/2; x<width/2; ++x)
  {
    if (source[x][y]))
    {
      for (theta=0; theta <180; ++ theta)
      {
         d = x\*cos(theta) + y\*sin(theta);
         accumulator[theta][d]++;
      }
    }
  }
}

A set of collinear points will spread votes among many accumulator cells, but some of them will fall into the same accumulator cells in |image32| space. Ultimately, accumulator cells which correspond to lines in the original image will get most votes and stand out in the accumulator image.

The original image that corresponds to the above transformation to Hough space has two squares in it. The maxima in the Hough space have been detected and the corresponding lines have been overlaid on top of the image.

The hough_transform sample shows how to use the functions for the Hough transform.