The Generalised Hough Transform is a "classic" algorithm used in computer pattern recognition and computer vision. It is used to locate examples of a known object (or pattern) within a search space. Usually it is applied in image processing. The advantage it offers over the normal Hough Transform is that a parametric description of the pattern is not required. The main disadvantages are computational and memory expense and the inability to deal with slight variations in the pattern. It is suited to tasks like automatic industrial inspection.

Here's how it works for 2D images. The pattern is represented as a set of vectors that describe the location of feature points in the pattern with respect to a fixed reference point. Feature points are often edge or corner points (identified by preprocessing) and the reference point is often the centroid of the pattern.

To locate the pattern in an image, the set of all feature points in the image is considered. Each point in the set is treated as though it was each of the feature points in the pattern and the corresponding location of the reference point is calculated. An entry in an accumulator array is incremented, keeping track of the total number of times each possible reference point location is encountered.

After this process is complete 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 final stage is to locate peaks in the accumulator array. If you can find several peaks, then several instances of the pattern have been detected in the scene, all in one pass.

The method can be enhanced by considering rotated and scaled 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 and memory requirements are increased by two orders of magnitude :(

Log in or register to write something here or to contact authors.