Hough transform

The Hough transform ( speech [ hʌf ] ) is a robust global methods for the detection of straight lines, circles, or any other parameterized geometric figures in a binary gradient image, so a black and white image, after edge detection. The process was patented in 1962 by Paul VC Hough under the name "Method and Means for Recognizing Complex Patterns".

For the detection of geometric objects, a dual space is created ( specifically: the parameter space, Hough space ), all possible parameters of to-find figure to be entered in the dual space in the for each point in the image that lies on an edge. Each point in the dual space corresponds to a geometric object in the image space. Wherein the line can be the slope and the Y -axis section, for example, the circle, the center and radius. After that evaluates the dual space, by looking for clusters, which then correspond to the desired figure.

Just recognition using Hough transform

Especially in the detection by means of the Hough transform, one must first find appropriate parameters for a straight line. Slope and y- axis intercept are only conditionally, since the y-axis parallel lines have an infinite slope, and therefore ( for the calculation necessarily ) finite parameter space can not be mapped. This problem can be avoided if one performs a second Hough transform on the 90 ° rotated image space, but this is quite cumbersome. In the recent literature therefore outweighs the approach to represent lines through its HNF. As a parameter to choose the angle and the ( Euclidean ) distance d, wherein the angle between the normal to the straight line ( = Lot) and the x- axis, and the distance from the origin to the nadir point to the straight line referred to.

Thus we have the equation parameters with which we draw the corresponding curve in the dual space for all points on edges in the image. This call and the variables, while x and y were now converted into parameters. x and y are the coordinates of the previously detected edge points. The output image to an edge detector algorithm subjected (for example, Canny or Sobel filter ), and thereby the space to be tested point is first limited to possible edge.

The dual space is now spanned by and so. For each calculated value is now in dual space (represented as a matrix ) is increased at the location of the value by 1, so to speak, for the straight line represented by " voted ". Therefore they are called the matrix often "voting matrix ".

The next step in the analysis of the dual- chamber, in which one looks for cumulative points in the voting array. This accumulation points in the dual space represent potential lines in the image space, since they are obviously represents at the same angle with the same distance from the origin.

Due to the independence of the individual cells of the parameter space to each other in the calculation of accumulation points, the Hough transform is easily parallelizable.

Simple algorithm

Could perform a simple algorithm to a Hough accumulation look like this:

Max_d: = sqrt ( (1/ 2 * image height ) ^ 2 (1 /2 * image width) ^ 2) min_d: = -1 * max_d Hough space [0 ..] [ min_d ... max_d ]: = 0 foreach pixel! = 0 do     for: = 0 to do        d: = Pixelx * cos () pixely * sin ()        Hough space [ ] [ d ]     end end The result of the accumulation is a two-dimensional array containing the number of occurrences for each combination of and. Because the lines are addressed, only the range from 0 to evaluated needs to be, because then cover the straight line with the already computed. In practice, the center of the image is frequently used as a coordinate origin.

Hough transform for circles and generalized Hough transform

As mentioned above, the Hough transform - in modified form - not only for the detection of straight lines, but also eg of circles are used. Starting from the edge image of each edge pixel is considered as generated by circles of a given radius. The transformation in the Hough space works is that one registers all circle centers in the accumulator, which could lead to this edge pixel ( each Akkumulatormittelpunktpixel increase by 1 ). If now represent the points in the edge image a circle, a particularly high value of the corresponding point of the circle center is entered, as there have voted for the center of a lot of edge pixels of the circle in the Akkumulatormatrix. The maxima in the Hough space thus represent the circle centers.

The first two dimensions of the Hough space in this case correspond to those of the image space, as the (x, y) coordinates describe the position of the circle center point in both cases. According to the equation of a circle In addition, the radius r of the third parameter, which must be respected. One speaks in circles, therefore, of a 3-dimensional Hough space (xc, yc, r). The value limits for the radius must be specified ( eg by means of a priori knowledge ).

For ellipses, and any other group represented by a parametric equation form, this method can also be used. However, the dimension of the Hough space increases with the number of variables ( for ellipses: 5), which significantly increases the computational effort.

It is also possible to find a non-displayable by parametric representation structure. This method is called generalized Hough transform (GHT ). So any shapes can be found in an image. The principle is that it calculates a form -based lookup table. In that the possible vectors to a reference point associated with different gradient directions. Through some transformations in the table can be found also rotated and scaled versions of the desired shapes, which leads to a high durability. By means of the lookup table, you can now convert the edge image in the Hough space; Maxima represent the reference points found

Disadvantages of the Hough transform

• The Hough transform is a kind of " brute force " approach and thus computationally very intensive.

In its original form, the Hough transform itself in a parallel processor is therefore not suitable for example for the analysis of video sequences, in real time, as is necessary for the recognition of lane markings in the autonomous driving. However, there are a hardly manageable number of further developments of the Hough transform, often called "Fast Hough Transform", which this problem on a ( see, eg, Fast Hough Transform).

• The memory requirement of the classical approach is very large. Also this property has been improved in various scientific publications.
• In the Hough transform many of the same straight line are detected instead of the desired straight line often. This phenomenon is due, in which many possible lines share the same pixel in the discrete image space - resulting in that form in the parameter space no accumulation points, but ( in the 2D case of the detection of straight lines ) accumulation plateaus. An acceptable result is obtained, therefore, only if you contract this accumulation plateau prior to the transfer in a straight line to a point list. This can be achieved by a local operator in windowing.
• The Hough transform for line supplies, as their name implies, straight - so infinitely long lines without starting and ending point. In a real edge image, however, the detection of the start and end point of an edge is usually crucial, so it's still a post-processing of the line list required. One possible approach is the so-called Tracking: In this case a window of length is the perceived Just pushed and only included the center pixel within the window in the result set if more than pixels were set in the edge image.