| • Science | • People | • Locations | • Timeline |
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.
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.
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.
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.