# Hough algorithm for detecting arbitrary curves in images

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

The Hough transform algorithm uses a battery array, the dimension of which corresponds to the number of unknown parameters in the equation of the family of desired curves. For example, when detecting lines described by the equation y = m * x + b, for each line it is necessary to calculate the values ​​of two parameters m and b. At the same time, values ​​indicating the probability of the presence of a straight line y = m * x + b in the image are accumulated in the elements A [M, 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 in the image and its surroundings. Determines whether a distinct edge is present in a given pixel. If present, then the parameters of the desired curve passing through the given pixel are calculated. After evaluating the parameters of the line in this 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, magnification is performed by one, in others by the amount of edge power in the processed pixel. After processing all the pixels, a search is made for local maxima in the battery array. The points of local maxima correspond to the parameters of the most probable lines in the image.

The battery array allows you to determine the parameters of infinitely long straight lines or curves, but with its help it is impossible to determine where the segments of these lines begin and end. You can create another PTLIST data structure to get this information. The PTLIST [M, B] element contains a list of coordinates of all the pixels that contributed to the value of the battery array A [M, B]. By the content of these lists, you can find the segments or segments of curves present in the image.

Now we have examined the general principles of the Hough method, but we have not considered some important details that you need to know in software implementation.

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

The indices of the battery array A correspond to discrete values ​​of d and f. In a series of experiments in 1976, O'Gorman and Clovs sampled d values ​​in increments of 3 and f values ​​in increments of 10. Below the accumulate_lines procedure is the O'Gorman and Clovs algorithm for populating battery array A and array of PTLIST lists. To detect circles, we have to add another dimension to array A, because The standard circle description 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 in the form f (x, a) = 0, where x is the image point, and a is the vector of parameters. The search procedure for such curves consists of three steps:
1. Initialization of the array A with zero values.
2. For each edge pixel x, a vector a is determined 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 f curves 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 highlighting various lines in images. If the topic is interesting, then I can talk about them. Thanks for attention.