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 :(