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.

Circle Extraction
The more intuitive of the methods is circle extraction. It is more intuitive to me because the matrix representing the parameter space has the same dimensions as the original, and the method involves projecting circles using cartesian coordinates. Simply stated, each pixel in the edge-detected image serves as the centerpoint for a circle of a given radius. Circles are projected around the centerpoint, and for each point on the circle, the corresponding cell in the accumulator array is incremented by one.

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.

Line Extraction
Line extraction operates in a similar vein, but is somewhat more abstract, in other words, you can view the accumulator matrix (parameter space) from circle extraction, and see pretty clearly how the process works, including being able to see vestiges of the original image. With line extraction, there is no such correlation: parameter space inhabits a different-sized matrix for one, and the axes represent minimum distance from the origin for a given line on the one hand, and angle of the line on the other.

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 the following: 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.

The resulting matrix: The x-axis of parameter space ranges from 1 to the square root of the sum of the squares of rows and columns from feature space. (This number corresponds to the furthest possible minimum distance from the origin to a line passing through the image. The y-axis represents the angle of the line. Obviously the axes could be switched...

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.

Conclusion
Although my implementation could certainly use some polishing, and hough transforms are certainly a clever idea, no doubt with many interesting applications, for non-artificial scene analysis and feature extraction, it appears to be somewhat too rigid (only near-perfect circles are found) and computationally somewhat complex. For curve fitting or feature extraction other than lines or circles, the approach is so limited as to be only marginally useful.