Line detection

Pronounce Hough as “huff” (see discussion).

Line detection consists of detecting alignments of points on an image of contours. The usual method for line detection is the Hough transform [Hough 1962]. Like the Fourier transform, it transposes the image from the spatial domain to another domain, where the information of interest is represented differently. In this case, the lines in the spatial domain are transformed into points in the Hough domain.

The Hough transform is not restricted to lines and can be used to detect any shape with a mathematical parameterization. The working process remains the same as for line detection, so the sequel focuses on line detection only.

First parameterization

In the spatial domain \((x,y)\), a line is parameterized by its coefficients \(a\) and \(b\):

\[ y = a x + b. \]

Thus, any line can be represented by the pair \((a,b)\). This is Hough’s idea: each line of the image can be represented by a point in the Hough domain \((a,b)\). The Hough domain is also called the parameter space.

Fig. 105 The Hough transform transforms a line in the image into a point in the parameter space.

Conversely, a point in the image is represented by a line in the parameter space (which has the equation \(b = \alpha a + \beta\)).

In particular, a constant line \(b=\beta\) in the parameter space corresponds to a point of abscissa \(x=0\) in the image.

Finally, if several points in the image are aligned, their respective lines in the parameter space intersect at a single point, which defines the equation of the line connecting them.

On a computer, the parameter space is finite and discretized (it is called an “accumulator”). Consequently, certain lines of the image cannot be represented there (e.g. a vertical line for which \(a=\infty\)). In consequence, another parameterization of lines needs to be used in practice.

New parameterization

To avoid the aforementioned problem of the parameterization space \((a,b)\), the lines are defined from two other parameters:

• the distance \(d\) of the segment connecting the origin with the point closest to the line (this segment is perpendicular to the line),

• the angle \(\theta\) that this segment makes with the x-axis.

Each line of the image is therefore parameterized by the pair \((\theta,d)\) which corresponds to a point in the parameter space \((\theta,d)\).

Fig. 106 New parameterization of the Hough transform.

We can show that for each point \((x_i,y_i)\) of the image, a sinusoid of equation \(d = x_i \cos(\theta) + y_i \sin(\theta)\) is associated in the space \((\theta,d)\). The sinusoids corresponding to the points of the same line intersect at the point \((\theta^*,d^*)\) parameterizing this line.

The Hough transform algorithm is as follows:

Algorithm: Hough transform

1. Get the result of an edge detection

2. Initialize an accumulator (as the discrete space of the parameters)

3. For each pixel in the edges:

   1. Determine the sinusoid corresponding to the points

   2. Increment the accumulator along this sinusoid

4. Search for the maxima in the accumulator

5. Deduce the line parameters

Fig. 107 gives an example of a Hough transform on an image representing a square.

Fig. 107 Hough transform associated with the image on the left. The sinusoids intersect at four (very bright) points, each one is associated with the line with the same letter.

Fig. 108 gives an example of a Hough transform on an real photograph.

Fig. 108 Hough transform associated with the image on the left.

Besides, it appears that the Hough transform is robust to noise and to occultation (it can detect partially covered objects)

As said above, the Hough transform can be extended to any parameterized object (circles, ellipses, etc.). For example, a circle is parameterized by three parameters (the center coordinates and the radius), then the corresponding Hough space is three-dimensional.

Because, the dimension of the accumulator is equal to the number of parameters, the main drawback of this method is that the computing time and the memory used quickly become significant.