Hough transform

From Free net encyclopedia

The Hough transform (pronounced Template:IPA) 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. 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".

Contents

[edit]

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.

[edit]

Implementation

The input to a Hough transform is usually a raw image to which an edge detection operator is usually applied. Thus, the set of points to be transformed are not likely to all likely to be 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.

[edit]

Example

Consider three data points, shown here as black dots.

Image:Hough transform diagram.png

  • 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 bisects 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.

Image:Hough space plot example.png

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.

[edit]

Variations and extensions

[edit]

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 center 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.

[edit]

Using weighted features

One common variation 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.

[edit]

External links

[edit]

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

es:Transformada de Hough fr:Transformée de Hough

Retrieved from "http://www.netipedia.com/index.php/Hough_transform"