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.
The algorithm works in a two-dimensional coordinate space. The row_gradient and column_gradiet functions process pixel neighborhoods to evaluate gradient components in the row and column directions. The gradient function combines the two components together to get the magnitude of the gradient. The atan2 function returns the angle in the corresponding quadrant by the given gradient components. The accumulate_lines procedure is a version of the Hough transform. The original Hough method does not provide for a standard method for extracting straight line segments. Therefore, the find_lines procedure was developed. The pick_greatest_bin function returns the maximum value from the battery array, assigning the corresponding discrete values of d and f to the DQ and THETAQ parameters. The reader function orders the list of points in an array element by the column coordinate at f <45 or f> 135 and by the row coordinate at 45 <= f <= 135. It is assumed that the arrays D and THETA for pixels contain discrete values. Similarly, the GRADIENT array should contain the calculated values of the gradient value. The merge procedure combines a list of points of a neighboring pixel with a list of points for a given pixel. This preserves the spatial ordering of points. The set_to_zero procedure resets the battery cell element so that it is not found again. Finally, the create_segments procedure scans the final ordered list of points and searches for gaps longer than one pixel. It is important to understand that the Hough transform can be detected by extraneous discontinuous or fictitious lines, such as those formed by a shadow.
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.
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.
The algorithm works in a two-dimensional coordinate space. The row_gradient and column_gradiet functions process pixel neighborhoods to evaluate gradient components in the row and column directions. The gradient function combines the two components together to get the magnitude of the gradient. The atan2 function returns the angle in the corresponding quadrant by the given gradient components. The accumulate_lines procedure is a version of the Hough transform. The original Hough method does not provide for a standard method for extracting straight line segments. Therefore, the find_lines procedure was developed. The pick_greatest_bin function returns the maximum value from the battery array, assigning the corresponding discrete values of d and f to the DQ and THETAQ parameters. The reader function orders the list of points in an array element by the column coordinate at f <45 or f> 135 and by the row coordinate at 45 <= f <= 135. It is assumed that the arrays D and THETA for pixels contain discrete values. Similarly, the GRADIENT array should contain the calculated values of the gradient value. The merge procedure combines a list of points of a neighboring pixel with a list of points for a given pixel. This preserves the spatial ordering of points. The set_to_zero procedure resets the battery cell element so that it is not found again. Finally, the create_segments procedure scans the final ordered list of points and searches for gaps longer than one pixel. It is important to understand that the Hough transform can be detected by extraneous discontinuous or fictitious lines, such as those formed by a shadow.
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