Generalised Hough transform
Encyclopedia
The Generalised Hough Transform or GHT, introduced by D.H. Ballard in 1981, is the modification of the Hough Transform
using the principle of template matching
. This modification enables the Hough Transform
to be used for not only the detection of an object described with an analytic equation (e.g. line
, circle
, etc.). Instead, it can also be used to detect an arbitrary object described with its model.
The problem of finding the object (described with a model) in an image can be solved by finding the model's position in the image. With the Generalised Hough Transform, the problem of finding the model's position is transformed to a problem of finding the transformation's parameter that maps the model into the image. As long as we know the value of the transformation's parameter, the position of the model in the image can be determined.
The original implementation of the GHT uses edge information to define a mapping from orientation of an edge point to a reference point of the shape. In the case of a binary image where pixels can be either black or white, every black pixel of the image can be a black pixel of the desired pattern thus creating a locus of reference points in the Hough Space. Every pixel of the image votes for its corresponding reference points. The maximum points of the Hough Space indicate possible reference points of the pattern in the image.
The main drawbacks of the GHT are its substantial computational and storage requirements that become acute when object orientation and scale have to be considered.
Ballard suggested using orientation information of the edge decreasing the cost of the computation. Many efficient GHT techiques have been suggested such as the SC-GHT (Using slope and curvature as local properties).
Hough transform
The Hough transform is a feature extraction technique used in image analysis, computer vision, and digital image processing. The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure...
using the principle of template matching
Template matching
Template matching is a technique in digital image processing for finding small parts of an image which match a template image. It can be used in manufacturing as a part of quality control, a way to navigate a mobile robot, or as a way to detect edges in images....
. This modification enables the Hough Transform
Hough transform
The Hough transform is a feature extraction technique used in image analysis, computer vision, and digital image processing. The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure...
to be used for not only the detection of an object described with an analytic equation (e.g. line
Line (geometry)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...
, circle
Circle
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....
, etc.). Instead, it can also be used to detect an arbitrary object described with its model.
The problem of finding the object (described with a model) in an image can be solved by finding the model's position in the image. With the Generalised Hough Transform, the problem of finding the model's position is transformed to a problem of finding the transformation's parameter that maps the model into the image. As long as we know the value of the transformation's parameter, the position of the model in the image can be determined.
The original implementation of the GHT uses edge information to define a mapping from orientation of an edge point to a reference point of the shape. In the case of a binary image where pixels can be either black or white, every black pixel of the image can be a black pixel of the desired pattern thus creating a locus of reference points in the Hough Space. Every pixel of the image votes for its corresponding reference points. The maximum points of the Hough Space indicate possible reference points of the pattern in the image.
The main drawbacks of the GHT are its substantial computational and storage requirements that become acute when object orientation and scale have to be considered.
Ballard suggested using orientation information of the edge decreasing the cost of the computation. Many efficient GHT techiques have been suggested such as the SC-GHT (Using slope and curvature as local properties).