JPH0624015B2 - Hough transform method in image processing apparatus - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of application] The present invention relates to an image pickup means for picking up an image of the front of a moving body, and a linearization process for Hough transforming image information obtained by the image pickup means to perform linearization processing. A plurality of candidate point pixels corresponding to the candidate point among a plurality of pixels positioned so as to be aligned in the X-axis direction and the Y-axis direction in the XY coordinate system of the image information. The present invention relates to a Hough transform method in an image processing device that detects a passing straight line.

[Conventional technology]

The above Hough conversion method of this kind, for example, as an example of a mobile body, a working vehicle such as a lawnmower working vehicle is automatically traveled using a boundary between an unprocessed work site and a processed work site as a travel guide, Alternatively, in order to automatically move a moving body or the like for transporting various articles in a factory or the like along a predetermined traveling guide, an image obtained by capturing the front side of the traveling route of the moving body in a two-dimensional direction Corresponding to the guide for traveling by extracting the pixels corresponding to the candidate points based on the brightness of each pixel from the information and obtaining the straight line with the maximum frequency among the straight lines passing through the extracted candidate point pixels. It will be used when obtaining information.

If an explanation is added using an example in which the work vehicle is automatically driven using the boundary between the unprocessed work site as a traveling guide, the boundary (L) between the unprocessed work site (B) and the processed work site (C) is Image information of the work area within a predetermined range including the two-dimensional direction (second
Figure (b)) is binarized based on the difference in brightness between the unprocessed work site (B) and the processed work site (C), and
By extracting a plurality of candidate point pixels corresponding to (L) and finding the maximum frequency among the straight lines passing through the plurality of candidate point pixels as the straight line corresponding to the boundary (L) (See Figure 2 (b)).

By the way, in the Hough transform, a straight line passing through candidate point pixels extracted as pixels lined up in the X-axis direction and the Y-axis direction in the XY coordinate system is tilted with respect to the reference line in the polar coordinate system (see θ) and the distance (ρ) from the origin (see FIG. 3).

ρ = X · cos θ + y · sin θ where x and y are the coordinate values of the candidate point pixel in the XY coordinate system.

Further, as the inclination (θ), a value set in advance in a plurality of stages in the range of 0 degree to 180 degrees is sequentially substituted.

Then, the combination of the inclination (θ) set in multiple steps and the value of the distance (ρ) obtained corresponding to it is taken as a histogram using a two-dimensional array, and the inclination (θ) and the corresponding value are obtained. The distance having the maximum distance (ρ) is obtained as a straight line corresponding to the boundary.

By the way, the value of the obtained distance (ρ) may be a decimal value, as is clear from the above equation, but the combination of the inclination (θ) with respect to the reference line and the distance (ρ) from the origin is a histogram. In this case, when the size of the two-dimensional array increases, the amount of information increases and high-speed processing becomes difficult.Therefore, in order to reduce the amount of information, the value of the distance (ρ) is converted to an integer, It is desired to determine the position of the two-dimensional array used as the histogram based on the integerized value.

However, when performing image processing on the imaging information, generally, X-
In the Y coordinate system, so-called square pixels are quantized so that the distances per pixel in the X-axis direction and the Y-axis direction are equal.

However, the integer conversion as described above has the following disadvantages.

That is, as shown in FIG. 2C, among the straight lines obtained for each candidate pixel, the X-axis or the Y-axis in the XY coordinate system is used.
In the case of straight lines that are parallel to the axis (refer to the straight lines indicated by L ₀ and L ₁ in the figure), even if the distance (ρ) from the origin is rounded down to an integer, The resolution with respect to such a straight line is essentially the resolution of one pixel in the XY coordinate system, and therefore, no disadvantage occurs due to integer conversion. However, when the straight line obtained with respect to the X-axis and the Y-axis is inclined (see the straight lines indicated by L ₂ and L ₃ in the figure), the integral part of the distance (ρ) from the origin in the polar coordinate system For example, since the values pass through adjacent candidate point pixels in the X-axis direction and have the same value on the straight lines (L ₂ ) and (L ₃ ) having the same slope, the adjacent straight lines (L ₂ ) and (L ₃ ) Cannot be distinguished, and the resolution of a straight line inclined to the X-axis and the Y-axis becomes lower than the required resolution of the straight line due to the integerization.

Therefore, conventionally, the distance from the origin in the Hough transform
The minimum resolution of the above distance (ρ) can be obtained by subdividing the two-dimensional array used as a histogram so that the values below the decimal point of (ρ) can be distinguished, or by making the pixels to be processed highly precise. By increasing the distance, it is possible to discriminate small distance changes and suppress a decrease in detection accuracy.

[Problems to be solved by the invention]

However, if the minimum resolution of the distance is increased or the pixel to be quantized is made high-definition so that the value after the decimal point of the distance from the origin in the polar coordinate system can be distinguished, the pixel information is two-dimensional information. However, the amount of information to be processed by the Hough transform increases, and the processing time required to obtain the straight line with the maximum frequency increases. For example, a straight line can be obtained at a speed corresponding to the traveling speed of the work vehicle. Disadvantages will occur.

The present invention has been made in view of the above circumstances, and an object thereof is to prevent the accuracy of detection from decreasing without increasing the amount of processing information in Hough transform.

[Means for solving problems]

In the characteristic configuration of the Hough transform method in the image processing apparatus according to the present invention, the reference line is the X axis or the Y axis in the XY coordinate system.
In the polar coordinate system determined as a line parallel to the axis, for each of the candidate point pixels, a plurality of straight lines passing through the pixel are set to a plurality of stages in the range of 0 to 180 degrees, and the reference line is set. And the distance from the origin, and in the range where the inclination is 0 degree or more and less than 45 degrees,
In the range of the cosine of the inclination, and the inclination is 45 degrees or more and less than 90 degrees, the cosine of the value obtained by subtracting the inclination from 90 degrees, and in the range of the inclination of 90 degrees or more and less than 135 degrees, , The cosine of the value obtained by subtracting 90 degrees from the inclination, and in the range where the inclination is 135 degrees or more and 180 degrees or less,
With the cosine of the value obtained by subtracting the inclination from 180 degrees, the distance obtained in the polar coordinate system is divided, the value obtained by the division is converted into an integer, and for each of the pixels, the inclination and the integer. The maximum frequency of the straight lines obtained as a combination with the converted value is extracted, and the action and effect thereof are as follows.

[Work]

That is, for each candidate point pixel, a plurality of straight lines passing through the pixel are obtained as the inclination with respect to the reference line set in a plurality of stages in the range of 0 to 180 degrees and the distance from the origin, and The maximum frequency of the combination of the slope and the value obtained by integerizing the distance from the origin is calculated to reduce the amount of information required for the processing in the Hough transform, and the calculated value of the distance is calculated according to the slope. Tilt 45
It is corrected so that the change in the value of the distance is enlarged as it approaches, and the corrected value is converted into an integer,
This suppresses a decrease in detection accuracy.

〔The invention's effect〕

Therefore, in order to increase the detection processing speed, it has become possible to reduce the amount of information to be processed, but to prevent the accuracy of the obtained straight line from decreasing.

〔Example〕

An embodiment in which the present invention is applied to a means for detecting a boundary between an unprocessed work site and a processed work site will be described below with reference to the drawings.

As shown in Fig. 5, the boundary between uncut land (B) and already cut land (C)
Work vehicle that automatically travels along (L) (V) (Example of moving body)
The image sensor (S) [an example of an image pickup means] for picking up an image of the work site on the front side of traveling in the two-dimensional direction is
It is provided so as to image a predetermined range of the work site on the front side with respect to (V) in a state of being viewed obliquely from above.

If the image sensor visual field of the image sensor (S) is further described, the work vehicle (V) follows the proper condition with respect to the boundary (L) between the uncut land (B) and the already cut land (C). In this state, the boundary (L) is located at the center of the visual field of the image sensor (S) in the lateral width direction.

That is, the work vehicle (V), the portion from one side of the square uncut land (B) surrounded by the already cut land (C) to the opposite side, as one work stroke, the work vehicle ( The image of the image sensor (S) is taken so that V) automatically travels along the boundary (L) between the uncut land (B) and the already cut land (C) on the side along the length direction of the work process. The boundary detected from the information using the Hough transform
(L) is provided with an image processing apparatus having a linearization processing means for performing linearization processing corresponding to (L), and the steering control is performed based on the information of the obtained straight line, and
By reaching the end side of one work stroke, that is, the opposite side of the uncut land (B), by automatically turning toward the start end of the next work stroke adjacent to that work stroke, In the so-called reciprocating mowing method, the lawn mowing work within a predetermined range is automatically performed.

Next, the image processing for detecting the straight line corresponding to the boundary (L) will be described based on the control flowchart of the straightening processing means shown in FIG.

That is, every time the work vehicle (V) travels a set distance, the process for boundary detection is started, and the image pickup information by the image sensor (S) has a preset pixel density (32 × The brightness level is set to 32 pixels), and the brightness level of Y corresponds to the vehicle body traveling direction per pixel.
The distance in the axial direction and the distance in the X-axis direction corresponding to the lateral direction of the vehicle body are quantized into square pixels in the XY coordinate system where they are equidistant (see FIGS. 2A to 2C).

However, as will be described later in detail, for the convenience of processing, the center of the screen is set as the reference point of the XY coordinates in order to match the origin in the polar coordinate system with the reference point of the XY coordinates.

Next, as shown in FIG. 4, the pixel (e) to be processed
The absolute value of the differential value of the brightness in the X-axis direction on the image of the pixel (e) to be processed and the Y-axis direction based on the values of 8 pixels (a to d, f to i) adjacent to The process of obtaining the differential value (IP) obtained by adding the absolute value of the differential value of the brightness in (1) using the following formula (i) is performed for each pixel arranged in the two-dimensional direction.

IP (x, y) = | (c + 2f + i) − (a + 2d + g) | + | (a + 2b + c) − (g + 2h + i) | ... (i) and the above By binarizing so that only the pixels whose differential value (IP) value is greater than the preset threshold value are extracted, the pixels at the location where the brightness change is large are candidate points to be Hough transformed. It is extracted as a pixel (see FIG. 2B).

However, the pixel located at the outermost part of the screen cannot be differentiated because there is no pixel information adjacent to it, so it is excluded from the processing target.

Therefore, the pixel range to be actually processed is a range obtained by subtracting one pixel located at both ends in the X-axis direction and the Y-axis direction from the quantized pixel range.

Next, set the pixel coordinate values (x, y) to the minimum values (X = -14, y = -1).
After initializing to 4) and determining whether or not the binarized value of the pixel is “1”, it is determined whether or not the pixel is a candidate point pixel, and then the Hough transform is used. Then, a plurality of straight lines passing through the pixel are obtained.

However, a large number of straight lines passing through the extracted candidate point pixels can be distinguished from each other in the range of 0 to 180 degrees with respect to the X-axis so as to distinguish the line connecting the screen center and each pixel located at the screen edge. In addition, for each inclination (θ) preset in a plurality of stages corresponding to the pixel quantization accuracy in the XY coordinate system, the value is
Until reaching 180 degrees, based on the following equation (ii), the inclination (θ) with respect to the X axis as the reference line in the polar coordinate system,
Calculated as the distance (ρ) from the origin, that is, the center of the screen (3rd
See figure).

ρ = x · cos θ + y · sin θ (ii) If the description of the value of the inclination (θ) set in multiple steps in the range of 0 ° to 180 ° with respect to the X-axis, for example, a screen as an origin A pixel located in the center,
The inclination of the straight line connecting the pixels arranged on the outermost side on the screen is set so as to be distinguishable with the resolution of one pixel.

By the way, as shown in FIG. 2C, each pixel is
Since it is quantized into square pixels so that the distances per pixel in the X-axis direction and the Y-axis direction are equal,
The difference in the distance (ρ) from the origin of the two straight lines (L ₀ ) and (L ₁ ) having a difference in distance of one pixel from each other in the direction parallel to the Y-axis is expressed by an integer. An error does not occur in accordance with the difference in the distance of one pixel in the XY coordinate system, but there is an inclination of 45 degrees with respect to the X axis or the Y axis, and the distance from the origin in the polar coordinate system ( Since the integer part of each distance (ρ) of the _two straight lines (L ₂ ) and (L ₃ ) whose ρ) differ by one step has the same value, it becomes indistinguishable when converted to an integer.

When the distance (ρ) from the origin is converted into an integer, generally, the value below the decimal point is truncated.

Therefore, the value of the distance (ρ) from the origin in the polar coordinate system, based on the following formula (iii), the change in the value of the distance (ρ) increases as the value of the inclination (θ) approaches 45 degrees. Then, the minimum resolution of the value obtained by converting the distance (ρ) into an integer corresponds to the resolution of one pixel in the XY coordinate system.

However, in the range of 0 ≦ θ <45, ψ = θ in the range of 45 ≦ θ <90 ψ = 90−θ in the range of 90 ≦ θ <135 ψ = θ−90 in the range of 135 ≦ θ ≦ 180 ψ = 180 −θ.

Next, the decimal point of the distance (ρ) is rounded down to be an integer, and a preset two-dimensional array is used corresponding to the integerized value and the inclinations (θ) set in the plurality of steps. And add the histograms.

Then, for one candidate point pixel, after repeating the process of adding the histogram until the value of the inclination (θ) set in the plurality of steps reaches 180 degrees, the coordinate value (x, y) of the pixel is maximum. For each extracted candidate point pixel, the slope (θ) corresponding to the straight line passing through the pixel and the distance from the origin are updated until the value (x = 15, y = 15) is reached. The process of adding the histograms of the combination of (ρ) is repeated to obtain the straight line passing through all the candidate point pixels.

After completing the process of finding the straight line that passes through all candidate point pixels,
From the value added to the histogram, obtain the combination of the slope (θ) and the distance from the origin (ρ) that is the maximum frequency,
One straight line having the maximum frequency among straight lines passing through each candidate point pixel is determined, and the straight line is obtained as a straight line corresponding to the boundary (L).

Then, the deviation of the work vehicle (V) with respect to the boundary (L) is calculated from the obtained values (ρ) and (θ) to the actual ground coordinate system, that is, the resolution of the quantized pixel. Corresponding to X-
By mapping to the Y coordinate system, the actual position of the work vehicle (V) with respect to the boundary (L) will be calculated.

[Another embodiment]

As a method of converting the distance (ρ) into an integer, various methods such as rounding up or rounding off can be used.

It should be noted that reference numerals are added to the claims for convenience of comparison with the drawings, but the present invention is not limited to the structures of the accompanying drawings by the entry.

[Brief description of drawings]

The drawings show an embodiment of a Hough transform method in an image processing apparatus according to the present invention, and FIG. 1 is a flowchart of image processing,
2 (a), (b), and (c) are explanatory diagrams of images, FIG. 3 is an explanatory diagram of Hough transform, FIG. 4 is an explanatory diagram of differential processing, and FIG. 5 is an explanatory diagram of a work site. is there. (X, y) …… Pixel, (θ) …… Slope with respect to the reference line, (ρ)
...... Distance from the origin, (S) …… Image pickup means, (V) …… Moving body.

Claims (1)

[Claims] 1. An imaging means (S) for photographing the front of a moving body (V)
And linearization processing means for Hough-converting and linearizing the image information obtained by the image pickup means (S), and in the XY coordinate system of the image information, in the X-axis direction and the Y-axis direction. A Hough transform method in an image processing apparatus for detecting a straight line passing through a plurality of candidate point pixels corresponding to a candidate point among a plurality of pixels (x, y) positioned so as to be arranged side by side. In a polar coordinate system determined as a line parallel to the X-axis or Y-axis in the XY coordinate system, a plurality of straight lines passing through the image for each candidate point pixel are set to 0.
The inclination (θ) with respect to the reference line set in a plurality of stages in the range of degrees to 180 degrees and the distance (ρ) from the origin are obtained. In the range where the inclination (θ) is 0 degree or more and less than 45 degrees, The cosine of the slope (θ), and in the range where the slope (θ) is 45 degrees or more and less than 90 degrees, the cosine of the value obtained by subtracting the slope (θ) from 90, and the slope (θ) Is 90 degrees or more and less than 135 degrees, it is the cosine of the value obtained by subtracting 90 degrees from the inclination (θ), and when the inclination (θ) is 135 degrees or more and 180 degrees or less, With the cosine of the value obtained by subtracting the slope (θ), the distance (ρ) obtained in the polar coordinate system is divided, the value obtained by the division is converted into an integer, and each pixel (x, y) is divided into On the other hand, of the straight lines obtained as a combination of the slope (θ) and the integerized value, the image with the highest frequency is extracted. Hough transform method in the processing apparatus.