Hough transformation

The Hough transformation (speaking [ hʌf ]) is a robust global method for recognizing straight lines , circles or any other parameterizable geometric figures in a binary gradient image , ie a black-and-white image , after edge recognition . The process was patented in 1962 by Paul VC Hough under the name "Method and Means for Recognizing Complex Patterns" .

To recognize geometric objects, a dual space is created (especially: parameter space, Hough space) in which all possible parameters of the figure to be found in the dual space are entered for each point in the image that lies on an edge. Each point in the dual space thus corresponds to a geometric object in the image space. In the straight line, this can be, for. B. be the slope and the y-axis section, the center and radius for a circle . Then you evaluate the dual space by looking for clusters that then correspond to the figure you are looking for.

Line recognition using Hough transformation

Representation of a Hough transformation of a pixel image with two lines to a space of angle and distance to the center of the image. The two bright points are accumulation points in the result space, they correspond to the two input lines.

When recognizing a straight line using the Hough transformation, one must first find suitable parameters for a straight line. The slope and y-axis section are only suitable to a limited extent, since straight lines parallel to the y-axis have an infinite slope and can therefore no longer be mapped in the (inevitably for the calculation) finite parameter space. This problem can be avoided by performing a second Hough transformation on the image space rotated by 90 °, which is, however, quite cumbersome. In the more recent literature, the approach to represent straight lines by their Hessian normal form prevails . The parameters chosen are the angle and the (Euclidean) distance d, where the angle between the normal of the straight line (= perpendicular) and the x-axis denotes the distance from the origin to the base of the perpendicular on the straight line. ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha}$ ${\ displaystyle d}$

This results in the parametric equation with which the corresponding curve in the dual space is drawn for all points on edges in the image. And denote the variables, while x and y have now been converted into parameters. x and y are the coordinates of the previously detected edge points. The output image is first subjected to an edge detection algorithm (e.g. Canny or Sobel filter) and the point space to be examined is thus restricted to possible edges. ${\ displaystyle d = x \ cdot \ cos (\ alpha) + y \ cdot \ sin (\ alpha)}$ ${\ displaystyle \ alpha}$ ${\ displaystyle d}$

The dual space is now spanned by and . For each calculated value , the value is now increased by 1 in the dual space (represented as a matrix ) at the point , ie, quasi “voted” for the straight line represented by it. That is why the matrix is often called the “voting matrix”. ${\ displaystyle \ alpha}$ ${\ displaystyle d}$ ${\ displaystyle d}$ ${\ displaystyle (\ alpha | d)}$

The next step is the analysis of the dual space, in which one looks for accumulation points in the voting matrix. These accumulation points in the dual space represent possible straight lines in the image space, since they are obviously represented at the same angle with the same distance from the origin. ${\ displaystyle \ alpha}$ ${\ displaystyle d}$

Due to the independence of the individual cells of the parameter space from one another when calculating the accumulation points, the Hough transformation can easily be parallelized .

Simple algorithm

A simple algorithm to do a Hough accumulation might look something like this:

max_d := sqrt((bildhöhe)^2 + (bildbreite)^2)
min_d := max_d * -1
houghRaum[0 $\ldots \pi$ ][min_d $\ldots$ max_d] := 0
foreach pixel != 0 do
   for  $\alpha$  := 0 to  $\pi$  do
      d := pixel_x * cos( $\alpha$ ) + pixel_y * sin( $\alpha$ )
      houghRaum[ $\alpha$ ][d]++
   end
end

The result of the accumulation is a two-dimensional array that contains the frequency of occurrence for each combination of and . Because the straight lines are not directed, only the range from 0 to has to be evaluated, as the straight lines then coincide with those already calculated. In practice, the center of the image is often used as the origin of coordinates. ${\ displaystyle \ alpha}$ ${\ displaystyle d}$ ${\ displaystyle \ pi}$

Hough transform for circles and generalized Hough transform

As mentioned above, the Hough transformation can - in a modified manner - not only be used for the detection of straight lines, but also e.g. B. can also be used by circles. Based on the edge image, each edge pixel is viewed as being generated by circles of a certain radius. The transformation into Hough space works in such a way that one enters all circle centers in the accumulator which could lead to this edge pixel (increase each accumulator center pixel by 1). If the points in the edge image now represent a circle, a particularly high value is entered in the accumulator matrix at the corresponding point of the circle center point, since a large number of edge pixels of the circle have matched the center point there. The maxima in Hough space thus represent the center of the circle.

In this case, the first two dimensions of the Hough space correspond to those of the image space, since the (x, y) coordinates describe the position of the center of the circle in both cases. In addition, according to the circular equation, the radius r is the third parameter that must be taken into account. With circles one speaks of a 3-dimensional Hough space (xc, yc, r). The value limits for the radius must be firmly specified (e.g. using a priori knowledge). ${\ displaystyle x ^ {2} + y ^ {2} = r ^ {2}}$

This method can also be used for ellipses and any other shape that can be represented by a parametric equation. 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 structure that cannot be represented by parametric representation. This process is called Generalized Hough Transform (GHT). Any shape can be found in an image. The principle here is that a shape-dependent lookup table is calculated. In this, the possible vectors for a reference point are assigned to the different gradient directions. By reshaping the table, you can also find rotated or scaled versions of the shapes you are looking for, which leads to a high level of robustness. The lookup table can now be used to transfer the edge image into the Hough space; Maxima represent the reference points found.

Disadvantages of the Hough Transform

The Hough transformation is a kind of " brute force approach" and is therefore very computationally intensive.
In its original form, the Hough transform is therefore even in a parallel computer z. B. not suitable for the analysis of video sequences in real time, as is necessary for the detection of lane markings in autonomous driving. However, there is a barely manageable number of further developments of the Hough transform, often called "Fast Hough Transform", which address this problem.

The memory requirement of the classic approach is very large. This property has also been improved in various scientific publications.

With the Hough transformation, instead of the desired straight lines, many straight lines of the same type are often recognized. This phenomenon is due to the discrete image space in which many possible straight lines share the same pixels - which means that in the parameter space no accumulation points are formed , but rather accumulation plateaus (in the 2D case when straight lines are recognized). An acceptable result is therefore only obtained if these accumulation plateaus are reduced to one point before being converted into a straight line list. This can be achieved by a local operator using window technology.

As its name suggests, the Hough transformation for straight lines delivers straight lines - i.e. infinitely long lines without a start or end point. In a real edge image, however, the recognition of the start and end point of an edge is usually of decisive importance, so post-processing of the line list is still required. One possible approach is the so-called tracking : Here a window of the length is pushed over the recognized straight line and the middle pixel within this window is only included in the result set if more than pixels were set in the edge image.

{\ displaystyle l}

{\ displaystyle {\ tfrac {l} {2}}}

software

In free software - libraries for image processing as Scikit-image , Dlib and OpenCV is the Hough transform.

literature

Thomas Bräunl, Stefan Feyrer, Wolfgang Rapf, Michael Reinhardt: Parallel image processing. Addison-Wesley, Bonn 1995, ISBN 3-89319-951-9 , p. 99ff.
Rafael C. Gonzales, Richard E. Woods: Digital Image Processing. Prentice Hall, New Jersey 2002, ISBN 0-201-18075-8 , pp. 587ff.
Bernd Jähne : Digital image processing. 5th revised and expanded edition. Springer, Berlin 2002, ISBN 3-540-41260-3 , pp. 459ff.

Web links

Commons : Hough Transformation - Collection of Images, Videos and Audio Files

Peter E. Hart: How the Hough transform was invented. IEEE Signal Processing Magazine, November 2009, pp. 18-22 (PDF; 268 kB).

Applets for visualizing the Hough transformation:

Individual evidence

^ Straight line Hough transform. In: scikit-image - docs. Retrieved December 12, 2018 .
↑ dlib C ++ Library - hough_transform_ex.cpp. Retrieved January 8, 2019 .
^ Hough Circle Transform. In: OpenCV documentation. Retrieved December 12, 2018 .

[1] Straight line Hough transform. In: scikit-image - docs. Retrieved December 12, 2018 .

[2] dlib C ++ Library - hough_transform_ex.cpp. Retrieved January 8, 2019 .

[3] Hough Circle Transform. In: OpenCV documentation. Retrieved December 12, 2018 .