Detecting lines and circles with the Hough Transform
21 May 2015 by Adam Allevato
This was a final project for CS384G: Computer Graphics at the University of Texas at Austin, Spring 2015.
This project uses the Hough 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.
More information on the Hough transform is available on Wikipedia and on the University of Edinburgh’s Image Processing website.
Approach
This project roughly implements the procedure described in the Edinburgh reference. The processing pipeline is:
- Gaussian blur the source image to remove high-frequency noise that could cause false positives.
- Sobel edge detection to find actual edges, not just bright spots. This also reduces the processing load by zeroing out most pixels.
- Threshold the edge-detected image, discarding gradients deemed too small to be important.
- Hough transform itself, which varies based on what we’re detecting:
- Lines: A 2D accumulator array is created with r and theta dimensions (polar representation, which handles vertical lines that slope/intercept cannot). For each point of interest, all possible lines through that point are incremented in accumulator space, producing a sinusoid per point.
- Circles: A 3D accumulator array with x, y (center coordinates) and radius dimensions. For each point of interest, a family of circles is drawn in accumulator space, incrementing all circles passing through that point.
- Draw features that accumulated above a threshold percentage of the maximum value.
Results
Line Detection: Straight Lines
One of the simplest cases. The sinusoids and peaks are clearly visible in the accumulator space. Note that quantization error in the accumulator space means detected lines don’t exactly match the originals – increasing accumulator size decreases this error.
Original:
Accumulator space:
Detected lines (yellow):
Line Detection: Broken Lines
This image has incomplete lines but is still detected correctly. The Sobel operator was disabled for this run – the image already has high-intensity information at the correct locations, and because the Sobel operator is not rotationally symmetric, disabling it gives better results here.
Original:
Accumulator space:
Detected lines (yellow):
Line Detection: Stack of Books
A real-world image showing the strength of the pre-Sobel and pre-thresholding steps.
Original:
Accumulator space:
Detected lines (yellow):
Circle Detection: Basic Circle
A simple but noisy circle image showing the accuracy of circle detection. The system is robust to random RGB noise and missing portions of the circle. The Sobel operator was disabled for this image.
Original:
Accumulator at radius=17px:
Detected circle (orange):
Circle Detection: Multiple Circles
The rightmost circle and the outer circle were not detected due to the size of the accumulator array.
Original:
Accumulator at radius=9px:
Detected circles (orange):
Notes
- The accumulator space displays values from 0 to 255*3 by filling the blue, then green, then red components, creating a nice heatmap effect.
- The system detects peak edges well, or ramp edges when the Sobel operator is used. However, the Sobel operator is not rotationally symmetric, as visible in the Multiple Circles results.
- Longer edges are weighted more strongly, so in non-square images the longer dimension is more likely to produce detected edges.
- The system performs best on black-and-white images. For color images, a weighted average or per-channel thresholding would improve results.