|Feature extraction with Hough Transform implemented in matlab
Hough transform is used to automatically detect simple features from an image that has had an edge detection algorithm applied.
I implemented two types of feature extraction: lines and circles, both of which involve transforming an image from "feature space" into "parameter space". The methods for extracting line and circle features are different enough to warrant separate explanations.
The result of projecting these circles of fixed radius in the hough parameter space is that the centerpoints of circles in feature space is revealed: in parameter space those centerpoints will accumulate relatively large values, since the centerpoint will appear on the edge of all of the circles formed in parameter space by the edges of the actual circle in feature space.
The drawback of this technique is that it is computationally complex, and requires separate passes for any give radius. It's also rigid, and only reveals nearly perfect circles.
So the first thing to understand (and roughly the last thing I did fully understand) about parameter space for line extraction is that there is no one-to-one relationship between pixels in the image and cells in the parameter space matrix. Rather, each cell in parameter space represents a line that spans across the entire image.
The transformation between feature space and parameter space is
1) Project a line through each edge pixel at every possible angle
(you can also increment the angles at steps).
2) For each line,
calculate the minimum distance between the line and the origin.
3) Increment the appropriate parameter space accumulator by one.
Similarly to the process of circle extraction, the larger the number in any given cell of the accumulator matrix, the larger the likelihood that a line exists at that angle and distance from the origin.
Transforming from parameter space back to feature space is slightly more trouble for lines than circles -- the method I employ involves the risk of divide-by-zero for one. Also, each line pixel is checked to see if there is a pixel in edge space, and marked accordingly.
An extra step which I didn't employ would be to add a step of hysterisis to attempt to discover the line segments more definitively.
By far the main trouble with both methods was finding an appropriate threshhold for determining what constitutes a feature. The image processing toolkit apparently has a local maximum detector, which would have been very helpful. I relied on a more blunt measure, which was a threshold as a percentage of the maximum accumulator value. The non-artificial example below demonstrates how unsatisfactory this method is -- lines that are picked up are either non-representative, or saturate the image.
|Simple quadrilateral, pretty good results.||Original edge image||Parameter space representation of lines|
|Slightly more involved image, with obscured circles. Beginnings of line threshold problems -- circle tangents are showing up, while horizontal lines aren't.||Original edge image||Parameter space representation of circles||Parameter space representation of lines|
|Non-artificial scene. Some lines not detected, threshold problem.||Same scene with lower threshold, obviously too low.||Original canny results||Parameter space representation of circles||Parameter space representation of lines|