Hough transform
|
|
The Hough transform is a feature extraction technique used in digital image processing. The classical transform identifies lines in the image, but it has been extended to identifying positions of arbitrary shapes. The transform universally used today was invented by Richard Duda and Peter Hart in 1972, who called it a "generalized Hough transform" after the related 1962 patent of Paul Hough.
| Contents |
Theory
The underlying principle of the Hough transform is that there are an infinite number of potential lines that pass through any point, each at a different orientation. The purpose of the transform is to determine which of these theoretical lines pass through most features in an image - that is, which lines fit most closely to the data in the image.
In order to determine that two points lie on the same potential line, it is necessary to create a representation of a line that allows meaningful comparison in this context. In the standard Hough transform, each line is represented by two parameters, commonly called r and θ (theta), which represent the length and angle from the origin of a normal to the line in question (see Coordinates (elementary mathematics)). In other words, a line is described as being at an angle 90° from θ, and being r units away from the origin at its closest point.
By transforming all the possible lines through a point into this coordinate system - i.e. calculating the value of r for every possible value of θ - a sinusoidal curve is created which is unique to that point. This representation of the two parameters is sometimes referred to as Hough space . If the curves corresponding to two points are superimposed, the location(s) (in Hough space) where they cross correspond to lines (in the original image space) which pass through both points. More generally, a set of points which form a straight line will produce Hough transforms which cross at the parameters for that line.
Implementation
Rather than a raw image, the input to a Hough transform is usually one to which some kind of edge detection has been applied. Thus the points to be transformed are those likely to lie on an 'edge' in the image. The transform itself is quantised into an arbitrary number of bins, each representing an approximate definition of a possible line. Each salient point (or feature) in the edge detected image is said to vote for a set of bins corresponding to the lines that pass through it. By simply incrementing the value stored in each bin for every feature lying on that line, an array is built up which shows which lines fit most closely to the data in the image.
By finding the bins with the highest value, the most likely lines can be extracted, and their (approximate) geometric definitions read off. The simplest way of finding these peaks is by applying some form of threshold, but different techniques may yield better results in different circumstances - determining which lines are found as well as how many. Since the lines returned do not contain any length information, it is often next necessary to find which parts of the image match up with which lines.
Variations and extensions
Hough transform of curves, and Generalised Hough transform
Although the version of the transform described above applies only to finding straight lines, a similar transform can be used for finding any shape which can be represented by a set of parameters. A circle, for instance, can be transformed into a set of three parameters, representing its centre and radius, so that the Hough space becomes three dimensional. Arbitrary ellipses and curves can also be found this way, as can any shape easily expressed as a set of parameters. For more complicated shapes, the Generalised Hough transform is used, which allows a feature to vote for a particular position, orientation and/or scaling of the shape using a predefined look-up table.
Using weighted features
One common variation of the Hough transform takes account of uncertainty in the underlying detection of edges by allowing features to vote with varying weight. Most edge detection algorithms produce as output a likelihood that an edge exists, which is then thresholded to determine a set of features. If the thresholding is omitted (or limited to removing those features with the lowest probability), this likelihood value can be used directly in the Hough transform. In this way, the degree of certainty that something is an edge is translated directly into the degree of certainty that it constitutes part of a line. The detected orientation of an edge could also be used to weight features, but this information is rarely reliable due to the presence of noise.
Hierarchical Hough transform
A final enhancement that is sometimes effective is to perform a hierarchical set of Hough transforms on the same image, using progressively smaller bins. If the image is first analysed using a small number of bins, each representing a large range of potential lines, the most likely of these can then be analysed in more detail. That is, finding the bins with the highest count in one stage can be used to constrain the range of values searched in the next.
History
Initially it was primarily used in machine analysis of bubble chamber photographs.
The Hough transform was patented as Template:US patent in 1962 with the name "Method and Means for Recognizing Complex Patterns". This patent teaches a slope-intercept parametrization for straight lines, which awkwardly leads to an unbounded transform space since the slope can go to infinity.
The rho-theta parametrization universally used today was first described in
- Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972).de:Hough-Transformation