next up previous
Next: Extended Gaussian Images Up: Object Recognition Previous: Pattern Recognition

Hough Transforms

The Hough transform can be regarded as a generalised template matching method.

The Hough transform is typically used to extract out edges or curves from an image. In this case it can be regarded as an edge linker since it groups edge pixels together and describes by a higher order entity such as a line equation.

However the Hough transform can be used to extract circles and even generalised (perhaps non-symmetrical) shapes (See Exercises). In this case it is more like a pattern matcher. Note that the Hough transform is invariant to rotation and translation.

The input to a Hough transform is normally an image that has been edge detected -- with a Robert, Sobel or Canny edge detector, for instance.

Let us suppose that we are looking for straight lines in an image.

If we take a point (x',y') in the image, all lines which pass through that pixel have the form
equation3168
for varying values of m and c. See Fig. 47.

 

Fig. 47 Lines through a point

However, this equation can also be written as
equation3173
where we now consider x' and y' to be constants, and m and c as varying.

This is a straight line on a graph of c against m as shown in Fig. 48.

Each different line through the point (x',y') corresponds to one of the points on the line in (m,c) space.

 

Fig. 48 Lines though a point in terms of m and c

Now consider two pixels p and q in (x,y) space which lie on the same line.

 

Fig. 49 Points on the same line

Taking this one step further,

To detect straight lines in an image, we do:

  1. Quantise (m,c) space into a two-dimensional array A for appropriate steps of m and c.
  2. Initialise all elements of A(m,c) to zero.
  3. For each pixel (x',y') which lies on some edge in the image, we add 1 to all elements of A(m,c) whose indices m and c satisfy y'=mx'+c.
  4. Search for elements of A(m,c) which have large values -- Each one found corresponds to a line in the original image.

One useful property of the Hough transform is that the pixels which lie on the line need not all be contiguous.

For example, all of the pixels lying on the two dotted lines in Fig. 50 will be recognised as lying on the same straight line. This can be very useful when trying to detect lines with short breaks in them due to noise, or when objects are partially occluded as shown.

 

Fig. 50 Non-contiguous pixels on the same line

On the other hand, it can also give misleading results when objects happen to be aligned by chance, as shown by the two dotted lines in Fig. 51.

 

Fig. 51 Aligned objects

Indeed, this clearly shows that one disadvantage of the Hough transform method is that it gives an infinite line as expressed by the pair of m and c values, rather than a finite line segment with two well-defined endpoints.

One practical detail is that the y=mx+c form for representing a straight line breaks down for vertical lines, when m becomes infinite.

To avoid this problem, it is better to use the alternative formulation (Fig 52),
equation3199
as a means of describing straight lines.

 

Fig. 52 Line Representations Note, however, that a point in (x,y) space is now represented by a curve in tex2html_wrap_inline8717 space rather than a straight line.

Otherwise, the method is unchanged.

As we have already mentioned, the Hough transform can be used to detect other shapes in an image as well as straight lines.

For example, if we wish to find circles, with equation
 equation3203
Now:

In practice, the technique takes rapidly increasing amounts of time for more complicated curves as the number of variables (and hence the number of dimensions of A) increases (See Exercises and Further Reading).

So the method is really only of use for simple curves.


next up previous
Next: Extended Gaussian Images Up: Object Recognition Previous: Pattern Recognition

dave@cs.cf.ac.uk