The Generalised Hough Transform

The generalised Hough transform is a method for locating instances of a known pattern in an image. The search pattern is parameterised as a set of vectors from feature points in the pattern to a fixed reference point. The feature points are usually edge features and the reference point is often the centroid of the search pattern

To locate the pattern in an image the set of feature points in the image is considered. Each image feature is considered to be each of the pattern features in turn and the corresponding locations of the reference point are calculated. An accumulator array keeps track of the frequency with which each possible reference point location is encountered.

After all the image feature have been processed the accumulator array will contain high values (peaks) for locations where many image features coincided with many pattern features. High peaks (relative to the number of features in the pattern) correspond to reference point locations where instances of the pattern occur in the image.

The Hough transform can detect multiple similar objects in one pass. It can be enhanced by considering rotated and shortened or lengthened versions of the vectors to locate instances of the pattern at different orientations and scales. In this case, a four dimensional accumulator array is required and the computation is increased by two orders of magnitude.

Text and images by Mark Dobie, back to Mark's home page