Hough transform

The Hough transform (pronounced /ˈhʌf/, rhymes with tough) is a feature extraction technique used in image analysis, computer vision, and digital image processing.[1] The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in a so-called accumulator space that is explicitly constructed by the algorithm for computing the Hough transform.

The classical Hough transform was concerned with the identification of lines in the image, but later the Hough transform has been extended to identifying positions of arbitrary shapes, most commonly circles or ellipses. The Hough transform as it is universally used today was invented by Richard Duda and Peter Hart in 1972, who called it a "generalized Hough transform"[2] after the related 1962 patent of Paul Hough.[3] The transform was popularized in the computer vision community by Dana H. Ballard through a 1981 journal article titled "Generalizing the Hough transform to detect arbitrary shapes".

Example
Consider three data points, shown here as black dots.
请稍等，图片正在下载中...
* For each data point, a number of lines are plotted going through it, all at different angles. These are shown here as solid lines.
* For each solid line a line is plotted which is perpendicular to it and which intersects the origin. These are shown as dashed lines.
* The length and angle of each dashed line is measured. In the diagram above, the results are shown in tables.
* This is repeated for each data point.
* A graph of length against angle, known as a Hough space graph, is then created.

请稍等，图片正在下载中...

The point where the lines intersect gives a distance and angle. This distance and angle indicate the line which bisects the points being tested. In the graph shown the lines intersect at the purple point; this corresponds to the solid purple line in the diagrams above, which bisects the three points.