The Hough Algorithm

The Hough algorithm is used to locate the unique $(r,\theta )$-coordinate of a straight line. Each step of the Hough algorithm is outlined below.

1.

Quantize parameter space appropriately according to the image size in (x,y)-space.
For Example, consider a straight line $\ell$ in a 100 by 100 pixel image. This line $\ell$ can be represented by the equation,

$$r=x cos\theta+y sin\theta .$$

The values of r that $\ell$ can take lie in the range $0\le r \le d$, where $d=\sqrt{100^{2}+100^{2}}$ is the length of the diagonal across the image. Thus the r values in parameter space are restricted by the image size in (x,y)-space. The values of $\theta$ that $\ell$ can take lie in the range $0 \le \theta \le 360^{o}$.

2.

Construct an accumulator array $A(r,\theta)$ (i.e. an array with dimensions $r \times \theta$) with all elements initially set to zero.

3.

Examine the input image for feature points. This may involve a gradient exceeding some threshold. This step however is optional. If it is not known what defines a feature point, then it is reasonable to include every point in the Hough transform. If it is the randomized Hough transform that is being implemented, then a number of random points in the image will be chosen for examination.

4.

For each (x_i,y_i) point examined, evaluate the corresponding r_i and $\theta_{i}$ values that the point may take. For each r_i and $\theta_{i}$ value obtained, add one to the $A( r_{i} ,\theta_{i})$ position in the accumulator array,

$$A( r_{i} ,\theta_{i})=A( r_{i} ,\theta_{i})+1.$$

This constitutes a "vote" for this $(r_{i},\theta_{i})$ value.

5.

Examine the accumulator array for global and local maxima (i.e. $(r,\theta )$ values that obtained significantly more votes). These maxima correspond to collinear points.
The longest line $\ell$ in the input image will have the maximum value in the accumulator array, and this maximum value provides a measure of how many points lie on the line. The position in the array $A(r_{m},\theta_{m})$ where this maximum value occurs corresponds to the r and $\theta$ values that represent $\ell$. Hence, $\ell$ can be reconstructed by the equation,

$$r_{m}=x cos\theta_{m}+y sin\theta_{m} .$$