• Contribute
• What's New
• Submit News

A Hough Transform is a clever algorithm that can find geometric shapes, such as circles, or lines within an image. Hough Transforms work on the basis of parametric equations, so before delving into the specifics of the algorithm itself, let us quickly review the mathematics behind this.

Parametric Equations

A parametric equation is a way of defining an equation using arbitrary values (parameters) that then provide the values for the dependent variables. For an example, let us look at an example - on the left, is an equation for a simple parabola. On the right, is the parametric equivalent.

Notice how the two are equivalent. Now let us look at something a little more complicated — the equation for a straight line.

The two equations don't immediately look equivalent, also note that the two parametric equations have been combined into one. The parametric equation doesn't use the slope and y-axis intersect, but instead uses the angle from the x-axis and distance from the origin. The graph to the right should help visualize this.

Hough Transform

The Hough Transform works by analyzing how each coordinate in the image contributes to the line being detected. To do this, we must first run an edge detector and thresholding on the input image, so that we have a black and white image of all distinct edges. Next, the Hough algorithm iterates through the edge image and each time a point is found an accumulator is updated. It is updated by incrementing every point at the it's distance r for every theta.

This sounds a little confusing, so think of it like this: for every edge point within the input image, that point could be part of any line passing through it at any angle. This is why we update the accumulator for all angles. The end result of this is after the entire image has been processed, the accumulator will look something similar to the image on the right. The accumulator is plotted with r on the y-axis and theta across the x-axis. Notice how the lines in the accumulator curve - the strongest physical lines within the input image correspond to the darkest areas on the accumulator.

At this juncture, it might be a little easier at this point to actually look at the Hough Transform code used with the Generation5 JDK.

This code snippet is taken from the run method:

// Now find edge points and update hough array
for (int i = 0; i < width; i++) {
   for (int j = 0; j < height; j++) {
       src_rgb = source.getSample(i, j, 0);
       if (src_rgb != 0) {
           // Edge pixel found
           for (int k = 0; k < h_w; k++) {
               //Work out the r values for each theta step
               tmp = (int) (((i - centre_x) * Math.cos(k * thetaStep)) +
                       ((j - centre_y) * Math.sin(k * thetaStep)));

               tmp = tmp + h_h;
               if (tmp < 0 || tmp >= 2 * h_h)
                   continue;

               //Increment hough array
               houghAccumulator[k][tmp]++;
           }
       }
   }
}

Look at the screenshot below, the top-left image is the input run through a Sobel edge detector, the middle shot is the image thresholded and the final image is the Hough transform results superimposed on the input image.

To see the Hough in action interactively, click on the demonstration link below:

Hough Transform Demonstration (added 3/12/2004) Demonstrates how Hough Transforms work. Using a colour image as input requires a 5-stage filter: input, greyscale, Sobel edge detection, thresholding, Hough transform and finally interpreting the Hough results. This applet allows you to view each stage, as well as manipulate 3 key parameters.

If you are interested in exploring the Hough transform further, look at implementing algorithms that will detect other shapes (such as circles).

References

R. Fisher, S. Perkins, A. Walker and E. Wolfart. HIPR2: Image Processing Learning Resources. Online at http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm: 2003.