Generalised Hough transform

From Wikipedia, the free encyclopedia
  (Redirected from Generalised Hough Transform)
Jump to: navigation, search

The Generalised Hough Transform or GHT, introduced by Dana H. Ballard in 1981, is the modification of the Hough Transform using the principle of template matching.[1] 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. This maximum can be found by scanning the Hough Space or by solving a relaxed set of equations, each of them corresponding to a black pixel. [2]

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).[3]

References[edit]

  1. ^ D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981
  2. ^ Jaulin, L.; Bazeille, S. (2013). Image Shape Extraction using Interval Methods. In Proceedings of Sysid 2009, Saint-Malo, France. 
  3. ^ A. A. Kassim, T. Tan, K. H. Tan, "A comparative study of efficient generalised Hough transform techniques" Image and Vision Computing, Volume 17, Issue 10, Pages 737-748, August 1999