Hough Transformation

• Motivation
• Algorithm
• Do it yourself
• Hints

The Hough Transformation (HT) was invented in 1962 by P.V.C.Hough, and plays an important role in computerized image processing. In principle it can detect arbitrary shapes in images, given a parametrized description of the shape in question. A specialized form of the HT is part of the ring detection algorithm for evaluating SNCFD scans.

For the sake of simplicity this page concentrates on using the HT to detect lines in images. This case is especially interesting as it can easily be compared to other commonly used methods of fitting lines to image data, e.g. the least squared error method used to fit lines to experimental data.

A line in image space with coordinates x and y can be witten as:

y = y₀ + m*x       ...(1)

The Hough method transforms this line into the parameter space generated by m and y₀.
For each pixel (x,y) in the original image there is obviously a corresponding "line" in parameter space:

y₀ = y - x*m         ...(2)

The HT creates a discrete parameter space, called accumulator, initialized with zeros, and transforms every pixel in the original image according to (2). All accumulator cells found are incremented. In the end the highest valued accumulator cell is sought, its parameters represent the most probable line in the original image.

The Java applet below implements the line HT as described.
To use it,

1. paint something in the left panel,
2. press "Transform" to do the HT,
3. press "Clear" and try it again.

You should see a Java applet here...

This applet needs a Java VM capable of interpreting JDK1.1 code, e.g. InternetExplorer 4.

There are some special cases to consider:

Single Point

For a single point in the image you should see how it transforms into a line in parameter space. All accumulator cells on this line will have the same value. No global maximum can be found, consequently there is no valid solution (you will see a bogus line, though).

Two Points

Two points define a line, so there should be a solution now. Again you will see that each point creates a line in parameter space. These lines should cross each other in parameter space, the intersection defines the line in image space.

You might also see the problem with using the HT here. There are easier ways to find the line between two points. The line found via HT might even be slightly off the "real" solution because the accumulator is discrete, so the parameters found are always rounded.

No-line Features

This example shows the real strength of the Hough Method:
It is highly sensitive only to the shape it was implemented to detect.

The long line in the image to the right is found even in the presence of several shorter lines and non-line features as text and, well, sort of circles. A least squared error fit in contrast would fail, because all the pixels would be regarded as points of the line sought.

You get another example if you paint a short line running parallel to a longer line. While the HT detects the longer line, other fit methods might give you a line between the parallels as a solution.

These examples show why the HT is known to be the most robust method for shape detection because it tends to disregard noise and non-sought shapes.