Hough's algorithm for detecting arbitrary curves in images

Hough Transformation is a method for detecting straight and curved lines on halftone or color images. The method allows you to specify the parameters of the family of curves and provides a search on the image of the set of curves of a given family. We will consider its use for searching on the image of rectilinear segments and arcs of circles.

The Hough transform algorithm uses a battery array whose dimension corresponds to the number of unknown parameters in the equation of the family of the desired curves. For example, when detecting the straight lines described by the equation y = m * x + b, for each straight line it is necessary to calculate the values ​​of the two parameters m and b. At the same time in the array in the elements A [M, B] accumulate values ​​indicating the probability of the presence on the image of a straight line y = m * x + b, where M and B correspond to discrete values ​​of m and b.

Array A is used in the Huff algorithm to check each pixel of the image and its neighborhood. Determines whether a pronounced edge is present in this pixel. If present, the parameters of the desired curve passing through the given pixel are calculated. After evaluating the parameters of a straight line in a given pixel, they are sampled to obtain the corresponding values ​​of M and B, and the value of the array A [M, B] increases. In some implementations, the increase is performed by one, in others by the amount of edge power in the processed pixel. After processing all the pixels, a search for local maxima in the battery array is performed. The local maximum points correspond to the parameters of the most probable lines in the image.
')
The battery array allows you to determine the parameters of infinitely extended straight lines or curves, but with its help it is impossible to determine exactly where the segments of these lines begin and end. To obtain this information, you can create another data structure PTLIST. The PTLIST [M, B] element contains the list of coordinates of all pixels that contributed to the value of the battery array A [M, B]. The content of these lists can be found present in the image segments or segments of the curves.

We have now considered the general principles of the Hough method, but we have not considered some important details that need to be known when implementing the software.

The equation of the line y = m * x + b is not suitable for representing vertical lines. It is more convenient to represent straight lines in the form d = x * cos (f) + y * sin (f), where d is the length of the perpendicular to the straight line, and f is the angle between the perpendicular and the horizontal axis. In the image coordinate system, axes are directed along the rows and columns of the image. Since the coordinate c corresponds to x, and the coordinate r to the coordinate (-y), then the equation of the line takes the form: d = c * cos (f) -r * sin (f).

Battery array indices A correspond to discrete values ​​of d and f. In a series of experiments in 1976, O'Gorman and Klovs sampled d values ​​in increments of 3 and f values ​​in increments of 10. Below, the accumulate_lines procedure shows the O'Gorman and Klovs algorithm for filling the battery array A and the PTLIST array. To detect circles, we’ll have to add another dimension to array A, since The standard description of the circle contains three parameters:
r = r0 + d * sin (f)
c = c0-d * cos (f)
where d is the radius of the circle, and r and c are the vertical and horizontal coordinates of the center of the circle.

In fact, the Hough method can be used to detect any curves described analytically. Let the curve be represented as f (x, a) = 0, where x is the image point and a is the parameter vector. The procedure for finding such curves consists of three steps:
1. Initialization of array A with zero values.
2. For each border pixel x, the vector a is defined, such that f (x, a) = 0 and the value of the corresponding element of the array A [a]: = A [a] +1 is increased.
3. Local maxima in the battery array A correspond to the probable curves f in the image.

If the vector a contains m parameters and each of these parameters takes M discrete values, then the time complexity of the algorithm is O (M ^ (m-2)).

In fact, there are many methods for isolating various lines in images. If the topic is interesting, then I can talk about them. Thanks for attention.

Source: https://habr.com/ru/post/102948/

All Articles