Hough Transform Algorithm

The Hough transform is an algorithm for detecting simple geometric shapes, originally straight lines, within a set of points such as the edge pixels produced by an edge detector, even when the points making up a shape are broken up by noise or partly missing. Rather than searching directly among the image pixels, it works in a parameter space that describes every possible instance of the shape being sought; each candidate edge pixel casts a vote for every parameter combination it is consistent with, votes accumulate in this parameter space, and a strong cluster of votes marks the parameters of a shape that is genuinely present in the image. Paul Hough patented the original technique for detecting lines in 1962, and Richard Duda and Peter Hart generalized it in 1972 to detect lines and circles using the now-standard distance-and-angle parameterization, a generalization Dana Ballard extended further to arbitrary shapes in 1981.