Hough Transform Visualizer

Hough Transform Visualizer

CS384G: Computer Graphics
University of Texas at Austin
Spring 2015

Introduction

This project uses the Hough (pronounced “Huff”) transform to detect linear and circular features in an image. The Hough transform converts image features into parameter space, then uses a “voting” system to determine values of the parameters that best fit the data.

The Hough Transform

The Hough transform is a generic algorithm for converting objects into a parametric representation. First, an “accumulator array” is created. This accumulator has a number of dimensions equal to the number of parameters required to represent the feature in question. For lines, this is 2 parameters: slope and intercept, or the more robust r/theta polar representation. For more complex features, a higher-dimension accumulator array is required. The accumulator array represents the full range of parameters that can create every detectable feature in the image.

For each feature point of interest in the source image, the algorithm increments the values of each cell in the accumulator array that corresponds to the parameters that create the feature in question. The maximum

More generic information on the Hough transform is available on Wikipedia [1] and on the University of Edinburgh’s Image Processing website [2].

Approach

This project roughly implements the procedure described in [2]. The first step in image processing is to perform a lowpass (i.e. Gaussian blur) filter on the source image. The blurring helps remove high-frequency noise that could result in false positives when detecting features. The second step is to run the Sobel edge detector on the blurred image. This ensures that the Hough transform will find actual edges in the scene, not just bright spots. It also reduces the processing load by making many of the pixels in the scene black or near-black. The next step is to threshold the edge-detected image, throwing out any gradients that are deemed too small to be important. This leaves only “meaningful” edge pixels. Step 4 is performing the actual Hough transform itself, and the technique varies based on whether the system is detecting lines or circles:

  • If the system is detecting lines, a 2D accumulator array is created. The two dimensions are the r and theta parameters of the polar representation of a line. The polar representation is used instead of the slope/intercept version because the slope/intercept parametric equation is unable to accurately represent a vertical line (the slope would be infinite). For each point of interest in the processed source image, all possible lines that pass through that point are incremented in the accumulator space. This results in a sinusoid for every point of interest, and a family of sinusoids for a line (see results images, below).
  • If the system is detecting circles, a 3D accumulator array is created. The three dimensions are the x/y coordinates of the circle’s center and the radius of the circle. For each point of interest in the processed source, a family of circles is drawn around the corresponding point in accumulator space. In this way, we increment all points in the 3D accumulator that represent circles passing through the point of interest.

While the accumulator is being populated, the program records the maximum accumulated value. The final step is to draw all features that have accumulated above a certain percentage of the maximum value, which represent the most prominent features in the original scene.

Configuration

The dialog displays the original image and the accumulator space. Features are drawn directly on the output image. The user can navigate “up” or “down” through a 3D accumulator space by using the View menu, or the keyboard shortcuts Alt-U and Alt-J. Finally, the user can save the detected version of the image, or the accumulator space image itself. The user has the ability to modify the following parameters of the program:

  • Switch between detecting lines and detecting circles
  • Toggle the Gaussian blur, Sobel operator, and thresholding step
  • Change the Gaussian blur size
  • Change the initial threshold cutoff
  • Change the accumulator size, thus affecting the numeric accuracy of the results
  • Change the significance threshold, or how prominent a detected feature has to be before it will be drawn
  • Change the maximum number of features to be drawn. The list of features is sorted so that the most prominent features will be drawn first.

Results

The final program is quite robust to various types of image noise, as will be demonstrated in 5 images below.

Line Detection: Straight Lines

This is one of the simplest possible cases, and the sinusoids and peaks are clearly visible in the accumulator space plot. Note that because of quantization error in the accumulator space, the detected lines do not exactly match that in the image. This is true for all the results from this program. Increasing the accumulator size decreases this quantization error.

Original Image:

Accumulator:

Detected lines in yellow:

Line Detection: Broken Straight Lines

This image has incomplete lines, but is still detected correctly by the program. Note that for this run, the Sobel operator was disable. This image already has high-intensity information at the correct locations, and because the Sobel operator is not rotationally symmetric [1], disabling the Sobel step gives better results.

Original Image:

Accumulator:

Detected lines in yellow:

Line Detection: Stack of Books

This real-world image shows the strength of using a pre-Sobel operator and the pre-thresholding step.

Original Image:

Accumulator:

Detected lines in yellow:

Circle Detection: Basic Circle

This simple, but noisy, circle image shows the accuracy of circle detection. The system is quite robust with respect to random RGB noise and missing portions of the circle. The Sobel operator was disabled for this image.

Original Image:

Accumulator at radius=17px:

Detected circles in orange:

Circle Detection: Multiple Circles

Another display of the circle detection effect. The rightmost circle and the outer circle were not detected because of the size of the accumulator array.

Original Image:

Accumulator at radius=9px:

Detected circles in orange:

Additional Images

Many other images are packaged with the source code, and they display other features of the program, such as picking out linear features from non-linear images.

Notes

  • The accumulator space displays values from 0 to 255*3 by first filling the blue, then green, then red components of the GL image. This results in a nice-looking and easy-to-understand “heatmap” of value.
  • The system is good at detecting peak edges, or ramp edges if the Sobel operator is used. But note again that the Sobel operator is not rotationally symmetric, as can be clearly seen in the Multiple Circles image above.
  • Mathematically, longer edges are weighted more strongly. This means that in non-square images, the longer dimension of the image is more likely to have detected edges than the short dimension. This may or may not be the desired behavior, depending on the end use of the algorithm.
  • This system performs best on black-and-white pictures, specifically with regards to the thresholding. The program averages the red, green, and blue values before thresholding. In a real-world scenario, a weighted average could be used, the R/G/B components could be thresholded separately, or the entire image could first be converted to greyscale before thresholding the image.

References

[1] http://en.wikipedia.org/wiki/Hough_transform
[2] http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm