JPH0410080A - Target area identification method in image processing - Google Patents

Abstract

PURPOSE:To shorten the time for processing and to identify an area suitable for automatic travel by expressing the relation of linking boundary points in respective areas with a constructed structure according to an attribute described in a list and identifying the boundary of the objective area from this structure. CONSTITUTION:Based on the relation of connecting label values in the respective areas, the attributes of the boundary points along a dividing line in a fixed direction are calculated and described in the list in the fixed direction and based on the relation of connecting the label values in the respective areas, the attributes of the boundary points along the boundary line of the divided area in a certain direction intersecting orthogonally with the fixed direction are calculated and described in the list in the fixed direction. Based on the attributes described in the respective lists, the linked length of the lists in the direction intersecting orthogonally with the fixed direction is calculated, and the sequence of the boundary points corresponding to the list having more than prescribed length is judged as the boundary of the objective area. Then, the boundary of the objective area is identified. In such a manner, the boundary of the objective area is identified from the constructed structure. Thus, the time for processing is shortened and the automatic travel is attained.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a target area identification method for extracting a target area by determining the boundary between a target area and a background area in image processing.

[Conventional technology]

Autonomous driving of automobiles requires technology for determining driving routes using image processing. Conventionally, road edges and driving courses have been determined from image segmentation regions by sequentially tracing the boundaries between the obtained driving course regions and the background region to obtain point sequences corresponding to the boundary lines. In other words, the pixels located at the boundary of the driving road area were sequentially tracked one by one along this boundary, the traces of this tracking were made into a series of points, and the edge of the road was determined based on this series of points. .

[Problem to be solved by the invention]

For this reason, in the conventional method of determining the boundary edge of a travel region, the number of point sequences to be determined increases. Therefore, it is necessary to approximate the boundary of the travel road area with a polygon and thin out unnecessary points, which takes time.

Further, although it is sufficient that the boundaries of the travel path area obtained as a result of image processing are smooth, in reality, the shape of these boundaries becomes complex. Therefore, a large amount of data is obtained by sequentially tracking boundary pixels for a plurality of regions, and as a result, it takes time to process. If the processing time takes such a long time, it will interfere with self-sustaining automatic driving.

[Means to solve the problem]

The present invention has been made to solve this problem, and it divides an image labeled into each divided image area using dividing lines in a certain direction, and creates a list of directions orthogonal to the specified direction using dividing lines. Create a list in a certain direction by scanning the image along the dividing line and identifying the change point of the label value of each area to find the boundary point located at the intersection of the dividing line and the boundary line of each area. is created for each boundary point, the attributes of the boundary points along the dividing line in a certain direction are determined based on the connection relationship of the label values of each area, the attributes are written in a list in a certain direction, and the attributes of the label values of each area are calculated. Based on the connection relationship, find the attributes of the boundary points along the boundary line of the divided area in the direction orthogonal to a certain direction, write the attributes in a list in a certain direction, and then move in a certain direction based on the attributes described in each list. A method that determines the concatenated length of lists in orthogonal directions, determines that the sequence of boundary points corresponding to a list with a length greater than a predetermined length corresponds to the boundary of the target area, and identifies the boundary of the target area. It is.

[Effect]

By the attributes described in the list, the connection relationship between the boundary points of each area is expressed in a structured strafture, and the boundary of the target area is identified from this strafture.

〔Example〕

A case where a target area identification method in a color image processing apparatus according to an embodiment of the present invention is applied to driving control of an autonomous vehicle will be described below. According to the method of this embodiment, the traveling course of the vehicle is automatically recognized, and the vehicle autonomously travels by determining the steering angle, the amount of fuel to be injected into the engine, etc. based on the recognized traveling course.

FIG. 45 is a block diagram showing a schematic configuration of the entire color image processing apparatus according to this embodiment.

The color image processing device includes a color camera 101 that captures road information, and an I/O camera that performs ISH conversion on the captured RGB information.
An SH conversion unit 102, a color processing unit 103 that extracts road candidate areas etc. from the ISH converted image information, a labeling hardware unit 104 that performs labeling processing on the color-processed image, and a merging process on the labeled image areas. It is roughly divided into a CPU processing unit 105 that executes the following operations. The ISH converting unit 102 includes a color camera input board, an ISH converting board, a filter, and the like.

FIG. 2 is a schematic flowchart showing an image processing method in this color image processing apparatus.

A road image 106 is captured by the color camera 101 as RGB information, and the ISH conversion unit 102 converts the brightness (
I), chroma (S), and hue (H) are converted into images (
Step 201). Based on each of these images, the color processing unit 103 extracts a road candidate area that will become the basis of a driving course (step 202). Here, it is determined whether the low brightness threshold existence flag in the status register of the CPU is on (step 203). This flag is a flag indicating whether or not there is a low brightness area such as a shadow or a discolored part in the captured original image. If the flag is on, the low brightness area is extracted in the color processing unit 103 (step 204). The extracted road candidate areas and low-luminance areas are labeled by the labeling hardware unit 104, and the connection relationship between each area is determined. Based on the result of this determination, if the areas are in a relationship that should be merged, the CPU processing unit 105 executes a merge process (step 205).

Next, it is determined whether the high brightness threshold presence flag in the CPU status register is on (step 206). Step 203 (If the low-luminance threshold existence flag is not turned on in Z, the process of step 206 is executed immediately. This high-luminance threshold existence flag is This flag indicates whether there is a high brightness area such as a sunny spot or a discolored area. If the flag is on, the high brightness area is extracted in the color processing unit 103 (step 207).

The extracted road candidate areas and high brightness areas are labeled by the labeling hardware unit 104, and the connection relationship between each area is determined. Based on the result of this determination, if the areas are in a relationship that should be merged, the CPU processing unit 105 executes a merge process (step 208).
).

Based on the road candidate areas merged in this way, the left and right boundary edges of the areas, that is, the road edge boundaries are determined as a dot sequence. Using this point sequence information, the driving course based on the original image taken this time is recognized (step 209).
. Thereafter, the process returns to step 201, and the same process as described above is repeatedly performed on image information that is subsequently obtained as the autonomous vehicle moves, and travel control of the autonomous vehicle is executed.

Next, the above processing will be explained in more detail based on the configuration diagram of the color processing apparatus shown in FIG. 45.

A color camera 101 is fixedly installed on the body of an autonomous vehicle, and the color camera 101 captures a road image 106 located in front of the vehicle as RGB information. The conversion processing unit 107 of the ISH conversion unit 102 has this R
GB information is given. In this conversion processing unit 107, a color image ISH conversion process using a FROM table, which will be described in detail later, is executed, and the RGB road image information is converted into a brightness (1) image 108. It is converted into image information of a saturation (S) image 109 and a hue (H) image 110.

The brightness image 108 is given to the road candidate area extraction means 111, and a road candidate area image 113 based on the brightness image is extracted by a "driving course extraction method by iterative threshold processing using a template image" which will be described in detail later. . Further, the chroma image 109 is provided to the road candidate region extracting means 112, and a road candidate region 114 based on the chroma image is extracted using the same method as described above. The threshold value for region segmentation in this method is determined by "threshold setting means based on the shape of the feature histogram in iterative threshold processing" which will be described in detail later. The obtained road candidate area images 113 and 114 are given to the logical product calculation means 115, and the common part of each road candidate area obtained from the brightness and saturation is extracted, and a new road candidate area image is created based on the color information. It becomes 116.

Furthermore, if a low brightness area is connected to the road candidate area extracted from the brightness image 108, the low brightness threshold presence flag in the status register 117 of the CPU is turned on. When this flag is on, the low brightness area extraction means 118 captures the brightness image 108. Then, the low-luminance area is extracted using a ``extraction means for extracting shadows and high-luminance areas from the driving course that focuses on differences in brightness'', which will be described in detail later. The extracted low brightness area becomes a low brightness image 119. This low brightness area image 119 is processed by a logical product calculation means 120.
In , a logical product is performed with the road candidate region image 114 extracted from the chroma image 109, and a region with a saturation similar to the road candidate region is extracted from among the low luminance regions. The extracted image information of this low brightness area is added to the road candidate area image 116.

Furthermore, if a high brightness area exists in the brightness image 108, the high brightness threshold presence flag in the status register 117 of the color processing section is turned on. When this flag is on, the high brightness area extraction means 121 captures the brightness image 108. Then, the high-brightness area is extracted using a ``extraction means for extracting shadows and high-brightness areas from the driving course that focuses on differences in brightness'', which will be described in detail later. The extracted high brightness area becomes a high brightness area image 122. This high brightness area image 122 is logically ANDed with the road candidate area image 114 extracted from the saturation image 109 in the logical product calculation means 123, and the high brightness area has a saturation similar to that of the road candidate area. A region is extracted.

The extracted image information of this high brightness area is added to the road candidate area image 116.

By each of the above means, the road candidate area image 116 includes a road candidate area image 113 with a pixel value of 1, a low brightness area image 119 with a pixel value of 2, and a high brightness area image 122 with a pixel value of 3.

The road candidate area image 116 is provided to the labeling processing section 124. The labeling processing unit 124 labels each region of the given image and creates a label image 126. At the same time, the labeling processing unit 124 calculates the area, center of gravity, etc. of the same label area. Each of these calculated values is calculated as a calculated value 125 corresponding to the labeling processing unit 124.
become. This labeling process is executed by a "labeling processing device" which will be described in detail later.

The CPU takes the label image 126 into the small area removing means 127. Here, it is assumed that small areas caused by noise or the like and areas whose center of gravity is located above the horizon position do not correspond to road areas, and these areas are removed from each label image. The label image from which the small area has been removed from the road candidate area by the small area removing means 127 becomes a new label image 128 . Furthermore, among the computed values 125 (feature amounts) for each label attached to each region, each region that has not been removed by the small region removal means 127 is described in the feature amount list 1.

Feature amount 129 stored in list 1. Label image 128
．． Based on the road image 116, each label area of the road candidate area image and each label image of the low brightness area image, and each label area of the road candidate area image and each label image of the high brightness area image are in a relationship that should be merged. In this case, the area merging means 130 executes the merging process, and a new label image 131 is stored in the memory 1. The above merging process is executed by a "multiple area merging means" which will be described in detail later.

Road position coordinates 132 of the left and right ends of the road area are calculated based on the label image 131 finally obtained. Based on the road edge position coordinates 132, point sequence data 133 corresponding to the road edge is determined. This process of determining the road edge is a "means for determining a drivable range" which will be described in detail later, as well as a "method for internally expressing travel courses of various shapes" which is a feature of the present invention.
Executed by This point sequence data 133 is sent to a data management unit that performs overall management of image processing data for travel control of the autonomous vehicle, and color image processing is completed.

Next, ISH of a color image using a FROM table that converts the RGB data obtained by imaging with a color camera into 8 envelopes of brightness I and saturation.
The "conversion process" will be explained below using FIG.

First, an original image 301 is input as RGB data from a color camera. Since the original image 301 contains a mixture of RGB data, each component of the RGB data is separated. Then, each separated RGB data is stored in an R image memory 302,
The images are stored separately in each of three image memories, 0 image memory 303 and 8 image memory 304. Each of these R, G,
The B image memories 302 to 304 are composed of a plurality of pixel values having 8-bit gradation, and are subjected to ISH conversion as follows.

First, when reading each 8-bit RGB data, only the upper 6 bits are read and the lower 2 bits are discarded.

That is, by taking the upper 6 bits, a pixel value of 8 gradations is approximated to a pixel value of 6 gradations. The value of the upper 6 bits changes between 00 and 3F (hex) in hexadecimal (00 to FC when the lower 2 bits are rounded down).
(hex)). Also, the values obtained by dividing the value of the upper 6 bits by 40 (heX) are R and G, respectively.

Let it be the B value. These six values of R, G, and B vary in the range of real numbers from 0 to about 1.

If the values obtained by dividing the six values of R, G, and B by (R + G + B) are r, g, and b, respectively, then the conversion from R, G, and B values to I, S, and H values is performed according to the following formula. .

Here, min (r, g, b) indicates the value of the feature amount having the minimum value among the feature amounts r, g, and b.

1- (R+G+B)/3...
・ (1) S-1-(1/3) units min (r
, g, b) H=1/2+ (1/π) ・a
rctan ((3) 1/2(g-b) / (
2r-g-b) 1 This transformation is R
, G, B, and each converted I, S, H
All values are real numbers ranging from 0 to 1. ROM30
5 contains conversion table data from RGB to brightness I, RO
M306 stores conversion table data from RGB to saturation S, and ROM 307 stores conversion table data from RGB to hue H.

Each of these ROMs 305-307 functions as a lookup table. Further, the address at which data is stored in each ROM 305-307 is determined by the upper 6 bits of the 8-bit values of each R, G, and B value before conversion. The storage capacity of each ROM 305 to 307 is 18
bits (-256 bytes).

The feature quantities stored in the ROMs 305 and 306 are immediately read out as brightness data 308 and chroma data 309 in response to an import command from the CPU, and are supplied to necessary image processing in real time. Furthermore, the feature amount of the hue data 310 read out from the ROM 307 is as follows:
Noise is removed and averaged by a 3×3 average value filter 311. Therefore, the hue data 312 used for each image process is smoothed data without noise. Further, each of the read feature data (brightness 308, saturation 3091, hue 310 and 312) is 8-bit approximate data in which the lower 2 bits are 0 and the upper 6 bits are valid.

Next, an example of IH3 conversion processing using this algorithm will be described with reference to FIGS. 4 to 7, while comparing it with an example of IH9 conversion processing that does not use this algorithm.

(a) of each figure is an outline of an original image captured by a color camera. In other words, FIG. 4(a) shows a scene in which a running road curves in the distance, a guardrail is installed on one side of the running road, and trees are growing in the distance from this guardrail. FIG. 5(a) shows a road where the edges of the road are divided by weeds, etc., and there are houses, trees, etc. in the distance. FIG. 6(a) shows a driving route on a highway at night, and the road surface is slightly illuminated by moonlight and lamps. 7th
Figure (a) shows a driving route on a sunny day, and the driving path is shaded by trees inside a block wall.

In addition, (b-1) and (b-1) of each figure from FIG. 4 to FIG.
-2) is a histogram with brightness I as a feature, and (
c-1) and (c-2) are histograms with saturation S as a feature, and (d-1) and (d-2) in each figure are 3×3
Histograms with hue H' as a feature before being applied to the average value filter 311, (e-1) and (e-2) in each figure
is a histogram whose feature is the hue H after being applied to the 3×3 average value filter 311.

The vertical axis of each histogram indicates the number of pixels between each feature, and the maximum is 1/4 of the entire screen. Further, the horizontal axis of each histogram indicates the degree of each feature of lightness, saturation, S1, and hue H'H. The degrees between these features are displayed so that they become stronger as they move away from the origin, and range from 0 to FF (h e x
) The degree between each feature assigned to each numerical value is divided into 64 and displayed. Also, the number of pixels of the original image is 512X
It is slightly smaller than 512. This is because there is a portion in the periphery of the image where all R, G, and B data are O, and each histogram is represented by data values that include this portion.

Also, (b-1), (c-1), (d
-1) and (e-1) are histograms obtained based on the conventional method, in which the CPU directly accesses each image memory and converts R, G, and B data into I, S, and H data according to the conversion formula. This was obtained by In contrast, (b-2) in each figure.

(c-2), (d-2), and (e-2) are histograms obtained based on the algorithm according to the method of this embodiment. This is obtained by storing and reading out a conversion table between each feature.

Each (b-1), (b-2) and each (
As shown in c-1) and (c-2), it can be seen that there is not much difference in brightness I and saturation S between the histogram distribution according to the present method and the histogram distribution according to the conventional method. This shows that the function of converting RGB data into ISH data according to the present method is not inferior to the conversion function according to the conventional method. On the other hand, the histogram distribution of the hue H' between the features before being applied to the 3X3 average value filter 311 shown in (d-1) and (d-2) of each figure is different from the conventional method and the present method. Trends are changing. This means that for images like the one used in this example,
(g-b) in the formula to convert RGB data to hue H
Since the values of (2r-g-b) take only extremely limited values around 0, this is because the information is extremely discretized by compressing data to 6 bits using this method.

However, as shown in (e-1) and (e-2) of each figure, the histogram distribution obtained by applying this hue H' to the 3×3 average value filter 311 is different from the distribution obtained by the conventional method. It is fully compatible. The calculated value of the hue data is an unstable value that easily changes due to small noise in the RGB data, and the hue image has very large noise. For this reason, as in this method,
It is reasonable to perform some kind of smoothing on the calculated value results of hue conversion, and it is understood that the same problem will not occur even if the features are compressed to 6 bits by performing this smoothing. be done. Note that the calculated value of hue is an unstable value that easily changes due to noise, so the hue H′
By passing the data through an average value filter, a distribution similar to the histogram distribution obtained by the conventional method was obtained.

In this way, by using the ROMs 305 to 307 as look-up tables to perform conversion processing between the features of I, S, and f (in advance), the CPU can store each image memory in each image memory each time processing is required, unlike conventional methods. There is no need to access and perform calculations.As a result, the calculation processing speed during data conversion according to this embodiment can be executed at high speed at the video rate, and the processing speed is improved. R,G
, B data to I, S, H data even if the conversion formula changes, it can be handled by the same hardware. In other words, the effect of changing this conversion formula is RO
The only change is the memory contents of M305 to M307. Therefore, the hardware does not change even if the conversion formula is changed. Furthermore, since each R, G, and H pixel value is compressed to 6 bits, the amount of hardware can be reduced.

Furthermore, by passing the hue H through the 3×3 average value filter 311 when reading out the hue H from the lookup table, it is possible to prevent adverse effects caused by compressing the data to 6 bits, such as discretization of the histogram.

Next, "threshold setting means based on the shape of the feature amount histogram in repeated threshold processing" will be explained.

This means is performed as a pre-processing of color image processing for extracting the travel road area.

FIG. 8 is a flowchart showing an outline of this processing process, and shows the processing when the contrast of the original image data obtained from a color camera installed in a running vehicle is low.

First, a histogram representing the frequency with respect to the color feature ff1 (brightness or saturation) is created based on RGB digital image data of the original image obtained from the camera. The horizontal axis of this histogram is set to the color feature amount (lightness or saturation), and the vertical axis is set to the frequency of the feature amount.

This histogram has low contrast in the original image, so
The distribution is biased towards the origin of the histogram.

Furthermore, images with low contrast tend to have a single peak mode, and no clear valleys occur. Therefore, a histogram is created after image enhancement is performed by performing predetermined calculations on each pixel value in the film, but in the case of this method, this histogram is displayed on the histogram data in the Image enhancement is performed by simply stretching the image (step 801).

Then, left end processing (step 802) and right end processing (step 803) of the emphasized histogram are executed. Next, from the frequency distribution state of the histogram, a temporary top (peak) with a high frequency for the feature amount and a temporary trough with a low frequency for the feature amount are set on the peak/trough table (step 804). Evaluation of valleys is performed on this table based on the frequency of temporary valleys obtained (step 8).
05). Furthermore, the valley is evaluated again on the table based on the peaks adjacent to this valley (step 806). Finally, smooth the evaluated peak/valley table,
From the relative relationship between peaks and valleys, valleys that are effective for segmenting the target area of area segmentation and this background area are extracted (step 807
).

On the other hand, in parallel with the above processing, Otsu's discriminant analysis method is applied to the histogram created in step 801, and area segmentation thresholds based on this discriminant analysis method are obtained. and,
The obtained threshold value is compared with the position of the valley extracted in step 807, the frequency of valleys located near the threshold value is taken as the true threshold value, and the threshold value based on Otsu's discriminant analysis method is determined. to correct.

Next, details of each process will be explained below.

Setting of a temporary peak and a temporary valley in step 804 is performed as follows. That is, tentative peaks and valleys are determined based on the distribution of frequencies for the feature amounts. Specifically, depending on the frequency of adjacent points on the left and right of the point of interest on the histogram, the states of peaks and valleys are determined as shown in Figures 9(a) to (f).
) is divided into six states shown in the figure. Here, the point of interest on the histogram is hl (the subscript i means any one point when N points are equally distributed along the horizontal axis of the histogram, and the value is from 0 to N-1). ), focus point h
An adjacent point with a smaller feature amount than j is hl-1, and an adjacent point with a larger feature amount than the point of interest h1 is hiii. In addition, the difference in each frequency between the point of interest h1 and the adjacent point h i-1 is calculated by pitch T
)If (pH-hl-hj-1), adjacent point h i
The difference in each frequency between i1 and the point of interest h+ is expressed as pitch pi2 (p
H2-hDI-hi).

Range from i-1 to N-2 (excluding both end points of the histogram)
, the peak/trough table value pk tj is set as follows. That is, when the sign of pil and p+2 are different, (1) If pH≧0 and p12≦0, table value pktl=1 (2) If p11≦0 and pH2≧0, table value pkti=1 FIG. 9(a) shows that p 11 > 0 and p 12-0
Therefore, the table value is pkti -1. In the same figure (b), the state is pil>O5 and p12<0, so the table value is pkti -1.

In the same figure (c), p Il-0 and p12 < O, and therefore the table value pkti -1. In FIG. 4(d), p ii < o and p 12-0, and therefore the table value pkti=-1. In FIG. 4(e), p if<0 and p12>0, and therefore the table value pkt1=-1. FIG. 2(f) shows a state where p il-0 and p12>0, and therefore the table value pkti −-1.

In this way, from the relationship of relative frequencies of adjacent points, the states of (a), (b), and (c) in the same figure are pkti-1
, and the point of interest h1 is determined to be a temporary peak. Figures (d) and (e).

The state of (f) is calculated to be pktl=-1, and the point of interest h1 is determined to be a temporary valley.

Furthermore, the process of evaluating valleys based on frequency in step 805 is performed as follows. In other words, when the point of interest hi is a temporary peak in i-1 to N-2 (pktl-1)
, (1) If the ratio between the adjacent point hj and the point of interest h+ is smaller than 0.1 (hj /hl <0.1) and the adjacent point hj is on the left side of the point of interest h1, then the table corresponding to the adjacent point hj Set the value pk tj to -1 (pktj = -1)
.

(2) If the ratio between the adjacent point hffl and the point of interest hl is smaller than 0.1 (hm/hl <0.1) and the adjacent point hm is on the right side of the point of interest h1, then the table value corresponding to the adjacent point hm Set pktm to -1 (pkt suri-1).

Furthermore, the valley evaluation process based on adjacent peaks in step 806 is performed as follows.

For i-0 to N-1, (1) When the point of interest hi is a temporary valley (pktl==1), ■ A temporary peak on the left side of the valley (adjacent point hk, table value p
ktk=1) will be called topL.

■Temporary peak on the right side of the valley (adjacent point hj, table value pk
tj=1) will be called topR.

(2) When topL and topR both exist at the point of interest hi, ■Ratio between the point of interest h+ and topL flcΩ−hj/1o
pL) is the ratio r(r-hl/1) between the point of interest h1 and topR
opR) is smaller than (47<r), the table value pk
Add 1 to tj.

■Ratio 1) (hl/1opL) is ratio r (hi/1op
R), if (ρ≧r), table value pk tk
Add 1 to .

(3) TopL and topR both exist at the point of interest hi, and the ratio 1t<0.5, or the ratio r<0.5
If so, 1 is subtracted from the table value pkti corresponding to the point of interest ht.

(4) In cases other than (3) above, the table value p
Rewrite k ti to -4.

(5) When the temporary peak topR exists only on the right side of the valley, if the ratio r<0.5, subtract 1 from the table value pk ti.

(6) When the temporary peak topL exists only on the left side of the valley, if the ratio 1)<0.5, subtract 1 from the table value pk tj corresponding to the adjacent point hj.

Furthermore, in the peak/trough table smoothing process in step 807, that is, in the peak/trough table pkt, if the distances between the determined valleys are sufficiently close, the smoothing process is performed as follows.

In i-1 to N-1, the table value pkti corresponding to the point of interest h1 is -2, the table value pktj of the valley located on the right side of this valley is also -2, and the distance between these valleys ( j−i) is smaller than a predetermined threshold, (1) If the frequency of the point of interest h+ is greater than the frequency of the adjacent point hj (hi > hj), the table value pk
Set ti to 0 (pkti-0).

(2) If the frequency of the point of interest hj is smaller than the frequency of the adjacent point hj (hl ≦hj), the table value pktj of the valley located on the right side is set to 0 (pktj = 0).

Next, a specific example using the above method will be described below.

For example, assume that the feature histogram shown in FIG. 10(a) is obtained. In the figure, the horizontal axis is the color feature amount of brightness or saturation, and the vertical axis is the frequency of the feature amount in the image. When the processing shown in FIG. 8 is performed on this histogram, the table value of the peak/trough table pkt shown in FIG. The transition is as follows along the numbers 8 to 8. As a result of this transition, the numerical values shown in the lower row are determined as the final table values. Note that the positions where each table value in FIG. 11B corresponds to each feature ff1A-L of the histogram in FIG. That is, each described table value corresponds to the feature amount above the described position, as shown by the dotted line.

First, left end processing and right end processing of the feature quantity histogram are performed (steps 802, 803), and subsequently, provisional peaks and provisional valleys are set (step 804). This setting is performed according to the process of step 804 described above, and each table value obtained as a result is shown in the table numbered 1.

Next, evaluation of valleys based on frequency (step 805) and evaluation of valleys based on adjacent peaks (step 806) are performed according to the process described above.

When the feature amount is a valley of A, only topR exists on the right side of the valley, and the ratio r between the frequency in feature i1A and the frequency of the temporary peak on the right side of the valley is less than 0.5 (hi / l
opR<0.5) o Therefore, 1 is subtracted from the table value corresponding to feature ff1A, resulting in the table value being -
2, the table changes to the table indicated by number 2.

In addition, when the feature amount is a valley of D, there are to
Both pL and topR are present. Furthermore, the ratio g between the frequency of this valley and the frequency of the tentative peak on the left side is less than 0.5 (hl/1opL<0.5). Therefore, the feature ff1
Subtract 1 from the table value pk ti corresponding to D, resulting in a table value of -2. Furthermore, the ratio p and the ratio r between the frequency of each tentative peak value on both sides of the valley with the feature amount D and the frequency of the valley are larger (1)<r). Therefore,
By adding 1 to the table value pk tj of the temporary peak (feature ff1E) located on the right side of the valley, the table value becomes 2. As a result, the peak/trough table is numbered 3.
This results in the table shown in .

Furthermore, topL and topR exist on both sides of the valley where the feature amount is F, and either the ratio g or the ratio r is smaller than 0.5 (g, r<Q, 5). Therefore, 1 is subtracted from the table value pk tl corresponding to the feature amount F, and the table value is -
Make it 2. Further, the ratio p is larger than the ratio r (f!≧r).

Therefore, 1 is added to the table value pktk of the temporary peak (feature amount E) located on the left side of the valley, making the table value 3.

As a result, the table transitions to the table indicated by number 4.

In addition, both topL and t are on both sides of the valley where the feature value is H.
opR exists, and either the ratio g or the ratio r is greater than 0.5 (i), r≧0.5). Therefore, the table value pk tl corresponding to the feature amount H is rewritten to -4. Moreover, the ratio p is smaller than the ratio r (g<"). Therefore, the table value pk t corresponding to the temporary peak (feature quantity I) on the right side of the valley
Add 1 to j.

As a result, the table value corresponding to feature jlI becomes 2, and the table transitions to the table indicated by number 5.

Also, on both sides of the valley of the feature J, there are topL and t
opR exists and the ratio r is less than 0.5 (r<0.5
). Therefore, 1 is subtracted from the table value pkt+ corresponding to this valley. Also, the ratio g is larger than the ratio r (1)≧r)
. Therefore, the tentative peak located to the left of the valley (feature ffi
Add 1 to the corresponding table value pk tk to make the table value 3. As a result, the table transitions to the table indicated by number 6.

Further, in the valley of the feature ff1L, only topL exists on the left side of the valley, and the ratio p is smaller than 0.5 (i<0.5). Therefore, 1 is subtracted from the table value pk ti corresponding to this valley. As a result, the table value becomes -2 and the table transitions to the table indicated by number 7.

Next, data is smoothed as described above for the peak/trough table pkt number 7 obtained in this way (step 807). In other words, the distance between the valley h1 of the feature quantity and the valley hj of the feature ff1F located on the right side thereof is smaller than a predetermined threshold, and the table value of each province is -2. Furthermore, the frequency of the valleys of the feature ff1F is thicker than the frequency of the valleys of the feature quantity (hi≦hj). Therefore, the table value pktj corresponding to the valley of the feature amount F is set to 0. As a result, the table finally becomes the table shown at the bottom of FIG. 10(b).

Of this final table, feature quantities A and D.

Each point on the histogram corresponding to H, J, and L is found as a valley, and valleys A are at both ends of the histogram.

L is not a target, and the valley with a table value of -4 (feature ff1H) is also not a target. In other words, the effective valley for dividing the data image into the target area and the background area is
The table value -2 is the valley corresponding to the double-circled features ff1D and J. Of these valleys, Figure 10 (a
), the frequency of valleys near the region segmentation threshold obtained by applying Otsu's discriminant analysis method to the histogram becomes the true region segmentation threshold.

By correcting the ambiguous results of Otsu's discriminant analysis method in this way, it becomes possible to perform highly accurate travel route discrimination with few errors.

Next, a description will be given of a "traveling course extraction method using iterative threshold processing using a template image." In addition,
In the following explanation, it is assumed that the autonomous vehicle travels on a course divided by grass, dirt, etc., and a case will be described in which a traveling road area is extracted.

FIG. 11 is a flowchart showing an overview of the algorithm for recognizing the driving route.

First, using a color CCD camera installed in the vehicle,
The condition of the driving route is imaged (step 1101). Then, the captured RGB color image signals are imported into the color camera input device, and the imported RGB original image data is converted into ISH data as described above (step 1102
). Based on the feature image converted to IsH data, a color image processing device creates a histogram representing the characteristics of each feature and its number of pixels as described above (step 11).
03).

Next, based on the created histogram, threshold processing is repeatedly applied to extract the driving route as a binarized image.

Since the image extracted in this way has noise and finely divided areas, the following processing is performed. That is, each area is labeled by a labeling device which will be described in detail later (step 1104). Then, the area and center of gravity of each labeled area are measured, and areas where the center of gravity is above the horizon position calculated from the camera attachment position and areas with small areas are removed (step 1105).

Next, based on the driving path image that was first extracted by the color image processing device, areas that are darker and brighter than the driving path area are found, these areas are merged, and the relationship between each area is determined. Describe (step 1106)
. The drivable range, that is, the road edge, is detected based on this area merging and the description of the area relationship, and the image capture time is added to this drivable range information. Then, the drivable range information is transmitted to the data management unit that constitutes the image processing device (step 1107). After this, the process returns to step 1102 and repeats the above process.

FIG. 12 is a block diagram showing the details of the process of extracting the travel road area.

First, brightness data I and saturation data S are obtained from the RGB data of the captured original image, and each data is stored as a feature image in an image memory (block 1201). Next, a histogram with brightness as a feature quantity is created based on the brightness data I stored in the image memory (block 12
02). The number of divisions of the feature amount, which is the horizontal axis of this histogram, is 40 points, and this number of points is large enough to extract the driving route from a global perspective. Next, the created histogram is normalized (block 1203).

Then, the well-known Otsu's discriminant analysis method is applied to the normalized histogram to calculate a threshold value for distinguishing the driving road region from the background region (block 1204).

On the other hand, based on the shape of the created histogram, peaks with a large number of feature pixels and valleys with a small number of feature pixels are determined as described above, and a peak/trough table, which is a list of peaks and valleys, is created. (Block 1205). The value of each feature amount at each peak and valley is used as a candidate value for threshold processing.

Since the threshold value determined by Otsu's discriminant analysis method in block 1204 may contain an error, block 1204
The threshold value based on Otsu's discriminant analysis method is corrected using the candidate value for the threshold processing determined in step 05. In other words, the threshold value obtained in block 1204 and the candidate value obtained in block 1205 are compared, and the candidate value in block 1205 that is closest to the threshold value in block 1204 is used for separating the driving road region and the background region. Set as threshold (block 12
06). Next, the brightness image is binarized using this threshold value (block 1207).

The brightness image is composed of 512×512 pixels and is expressed as I (i, j).

Here, i and j are integers that satisfy the conditional expressions 0≦i and j≦511. In addition, the threshold value found in block 1206 is set as XI, the minimum feature value in the feature range to be divided into regions is a threshold value XO1, and the maximum feature value is a threshold value X2. Note that the initial values of the thresholds XO and X2 are O and FF (h e x). Here, if brightness image 1 (i, j) satisfies the following conditional expression,
Write FF (hex) to memory M1 (i, j) (block 1208).

XO:WI (i, j)<Xl In addition, if brightness image 1 (i, j) satisfies the following conditional expression, FF (h e
x) (block 1209).

X1≦I (i, j)<X2 Next, the template image stored in the ROM is read (block 1210). A template area is set within this template image so that the most stable driving route information can be obtained. This area setting is performed based on the angle of depression, 1 angle of view, and focal length of the color camera attached to the autonomous vehicle, and the memory corresponding to the template area is
F(h e x) is stored. Next, the degree of overlap between the read template image and the memories M1 and M2 is calculated (block 1211). That is, the logical product of the template image and the memory M1 and the memory M2 is calculated, and the number of pixels whose logical product is "1" is accumulated for each memory M1 and memory M2.

Next, the ratio of the total number of pixels for each memory to the number of pixels in the template area is determined. It is assumed that the memory information for which this ratio is 50% or more includes the running road area, and further, the memory M1 for which the ratio is 50% or more
Alternatively, the image stored in M2 is repeatedly divided into regions as follows. Further, by selecting a memory based on this ratio, the image is divided into regions by the threshold value X1, and division is also performed on the histogram.

In other words, the memory M1 whose feature value is within the range of XO to X1
This means that the area stored in the memory M2 is divided into the area stored in the memory M2 and the area stored in the memory M2 whose feature amount is within the range of X1 to X2. Further, when the degree of overlap between each memory M1 and M2 and the template image does not exceed 50%, memory M3 in which the sum of memory M1 and memory M2 is stored is selected (block 1212), and based on memory M3, Area segmentation is then performed.

For example, if the degree of overlap between the memory M1 and the template image is high, the area configured by the feature values within X1 from the threshold value XO is set as the road candidate area (block 1
213). Then, this road candidate region is further repeatedly divided into regions. The threshold value X1' for this repeated region division is a value within the range of the threshold values XO to x1 among the valley candidate values determined in block 1205 (block 1214). Furthermore, if there is no valley candidate value within this range, the repeated division process is not performed.

Minimum value XO of the feature range subject to repeated region segmentation
' is the same threshold value XO as the previous area division,
The maximum value X2' becomes the threshold value X1. Regions constituted by feature amounts within this range are binarized again in block 1207, and then the same processing as the previous region division is performed to perform repeated region division.

This repetition is performed until there are no valley candidate values found in block 1205 within the feature amount of the road candidate region to be divided. By repeating the process in this way, the first road image area is finally obtained.

If there is a shadow area that is darker than the brightness of the obtained road image area and a bright high-intensity area, thresholds for determining these areas are set as described below (block 1215). Then, based on this threshold, each region is divided into regions in the same manner as described above to obtain shadow regions and high brightness regions. In addition, if the saturation of the shadow area and the saturation of the road image area are similar based on the processing results based on the saturation images that are performed at the same time, then the logical product of each is taken and the final image is combined into one area. Low brightness area. Similarly, if the calculated saturation of the high brightness area and the saturation of the road image area are similar, the logical product of each is taken and the final high brightness area is determined as one area. Furthermore, the connection relationship between the road image area and the low-luminance area is checked, and if there is a relationship that allows them to be merged, merging processing is performed. Similarly, the connection relationship between the road image area and the high brightness area is investigated.

If there is a relationship that allows merging in this way, merging processing is performed. As a result, if there is a shadow on the driving path, or if your position is in the shadow and there is a high brightness part due to direct sunlight irradiating the driving path far away, by performing this merging process, it will be possible to match the actual driving path. This results in a travel path area having a suitable shape.

Although the above processing was performed on brightness images, similar processing is performed on chroma images as well. However, block 121
Since the process No. 5 is specific to brightness images, this process is not executed. In the processing results using this chroma image, R and G of each area.

In the case of similar colors in which B has similar values, the histogram distribution of each area has a similar shape. This is the above-mentioned conversion formula from RGB data to saturation S data (% formula%) Therefore, in a cloudy sky or on an ordinary paved road where R, G, and B have similar values, the conversion formula based on the saturation is It is difficult to distinguish between each area. However, there are color differences, and R, G,
If the B values are not similar, it is possible to distinguish each region even if there is no difference in brightness between the regions. Therefore, in order to accurately extract the road image area under any scene, two feature quantities, brightness and saturation, are used. Then, by taking the logical product of the two types of road images extracted from the brightness image and the chroma image, highly accurate driving road area information can be obtained.

FIG. 13 shows the process of extracting a road candidate region in the road image region extraction process.

First, a feature histogram 1302 is created from a lightness feature image 1301. The horizontal axis of this histogram 1302 indicates brightness, and this brightness ranges from 0 to FF (h e x
) is expressed as a numerical value.

Further, the vertical axis indicates the number of pixels in the original image at each brightness.

Otsu's discriminant analysis method is applied to this histogram 1302 to find a threshold value C for distinguishing between the road region and the background region. Also, based on the shape of the histogram 1302,
Find the beat and valley of the histogram and create a peak/trough table. Then, the obtained valley is used as a threshold candidate value for the iterative threshold processing. This histogram 1
In 302, the features ff1a+b, d, e, and f are candidate values.

The threshold value C obtained by Otsu's discriminant analysis method is corrected by the candidate value obtained from the peak/trough table. In other words, the candidate value closest to the threshold value C is set as the corrected threshold value. Then, by using this threshold value, the feature amount image 1
301 is binarized.

As a result, the divided image 13 with the feature amount from 00 (hex) to b
03 and divided image 130 with feature amount b-FF (hex)
4 is obtained. At this point, each divided image 130
3. It is not known which image of 1304 includes the driving road area.

For this reason, the template image 130 assuming the road position
5 and each image 1303 and 1304 to calculate the degree of overlap with each image. A trapezoidal template area is set at the bottom of the template image 1305 as shown. As described above, FF (hex) is stored in the memory element corresponding to this template area, and 00 (heX) is stored in the memory element corresponding to the background area of the template area. In the case of this example, the image 1304 has the largest number of overlapping parts with the template image 1305. Therefore, according to the calculation result of the degree of overlap, the image 13 with the feature amount b to FF (hex)
04 is determined to include the driving road area, and a road candidate area image 1306 corresponding to image 1304 is obtained.

Since there are still other candidate values remaining between the feature values of b-FF (hex), next, this road candidate area image 1
Area division is performed for 306.

That is, the road candidate area image 1306 is binarized using the threshold value d. Through this binarization, a divided image 1307 with feature amounts b to d and a divided image 1308 with feature amount d-FF (hex) are obtained. Next, each image 130 obtained
7. The degree of overlap with template image 1305 is calculated for 1308 in the same manner as described above. In this example,
Since the image 1308 has a higher degree of overlap with the template image 1305, the image 13 with the feature amount d-FF (hex)
It is determined that the road area is included in image 1308, and a road candidate area image 1309 corresponding to image 1308 is obtained.

There are still other candidate values e between the features of d-FF (hex).
remains, the road candidate area image 1309 is binarized using this threshold value e. Through this binarization, the feature amount becomes d
-e divided image 1310 and the feature amount is e-FF (hex
) are obtained. Then, the degree of overlap between each image 1310, 1311 and the template image 1305 is calculated in the same manner as described above. In this example, since the image 1310 has a higher degree of overlap with the template image 1305, it is determined that the image 1310 with the feature amount d - e includes the driving road area, and it corresponds to the image 1310. A road candidate area 1312 is obtained.

Since there are no other candidate values remaining between the feature values d - e, this road candidate region 1312 becomes the final binary image of the road region. Although the above processing was performed on the brightness image, similar processing is performed on the chroma image as well. after that,
The final driving path area is obtained by performing a logical product of the driving path area extracted from the brightness image and the driving path area extracted from the saturation image.

A common method is to binarize an image using a threshold and divide the image into regions. However, as in this example, by calculating the degree of overlap with the segmented images using a template image that takes into account the position of the driving route, the threshold value for the next region segmentation performed on the histogram is determined. This process can be performed quickly and simply. As a result, a travel road area matching an actual travel route can be obtained quickly, easily, and at low cost.

Furthermore, the brightness of the scene captured by the camera may change as follows. For example, the brightness may change because the direction of movement of your army changes due to a curve, or the brightness may change because the weather becomes sunny or cloudy. In such a case, the feature value histogram does not always show a constant shape, so region segmentation using a fixed threshold value does not provide a correct driving path region. However, with this method, even if the state of the input image, that is, the brightness, changes from moment to moment, it is possible to always accurately extract the travel road area. This is because the present method finds the feature quantity distribution with the highest degree of overlap with the template image, and sets the optimal threshold value each time according to the feature quantity at that time for images that change moment by moment.

Conventionally, in image processing that performs region division, an original image is divided into a plurality of regions, and identification processing is performed on the divided images to verify the validity of roads.

However, in this method described above, area segmentation is performed using threshold processing in order to extract the target object (road). In this way, in the conventional method, the object was verified from the processing results, but in this method, the processing approach is reversed in that the object is the object from the beginning of the processing. Therefore, it is possible to efficiently extract the road area.

Next, we will explain ``a method for extracting shadows and high-brightness areas from a driving course that focuses on differences in brightness''. This method has already been briefly explained in the explanation of the above-mentioned "method for extracting a driving course by iterative threshold processing using a template image," and this method will be described in detail below.

For the brightness image, by applying the above-mentioned "driving course extraction method using iterative threshold processing using a template image" and "threshold setting method based on the shape of the feature histogram in iterative threshold processing", A histogram showing the distribution of features of the driving course was obtained. This method determines areas darker than the road area and areas lighter than the road area based on this histogram. Further, this method is processed within a color image processing device.

FIG. 14 shows an overview of processing when this method is applied to each case in which various input images are captured. Case 1 is a case where only a driving course with negative road surface conditions is captured as an input image.

In this case, the own vehicle is located in front of a curve on a road that curves to the right. The road candidate area extracted in this case 1 has the same shape as the input image. This is because the input image is only a --like driving course, and therefore low-luminance areas and high-luminance areas are not extracted by this method.

Case 2 is a case where an input image is captured in which there is a partial shadow on the road surface of the driving course and a high brightness part due to reflected light or the like is formed in the far part of the driving course. In this example, the road curves to the right, and before the right curve there is a branch road that curves to the left.

The vehicle is located in front of these curves. The road candidate area extracted in this case 2 has a shape in which dark areas with shadows and bright areas with high brightness are excluded. In addition, shadow parts that appear on the near side of the road can be individually extracted by extracting low-luminance areas using this method. Further, high brightness areas due to reflected light that are formed far away from the road can be individually extracted by extracting the high brightness areas.

Case 3 is a case where an input image in which shadows from trees are formed on the road surface of the driving course is captured during weather with strong sunlight, and the road surface is illuminated by sunlight filtering through the trees. In this example, the own army is located in front of a curve on a road that curves to the left. The road candidate area extracted in this case 3 has the same shape as a shadow created by sunlight filtering through the trees. This is because the shadow overlaps with the template image more often due to strong sunlight.

Therefore, low brightness areas are not extracted by this method. Further, distant road areas and areas where sunlight shines through the trees are extracted as high brightness areas due to strong sunlight.

Case 4 is a case where a band-shaped discolored portion is formed along the side strip of the road, for example, when the road is discolored due to construction of a paved road or the like. In this example, the own car is
It is located in a position where you can see the discolored area on the straight road on your right. The road candidate region extracted in this case 4 has a shape in which this discolored portion is excluded. Furthermore, since this discolored portion has higher brightness than the road area, it is extracted as a high-brightness area by this method. Furthermore, since there are no shadows on the road surface, low-luminance areas are not extracted.

Next, the details of this method will be explained below using Case 2 mentioned above as an example.

FIG. 15 is a histogram created based on the input image captured in case 2.

The feature amount of this histogram is brightness, and this brightness is shown on the horizontal axis. Moreover, the vertical axis is the number of pixels at each brightness.

The feature value range in part A of the figure is the range that includes the driving road area, and the range that includes the pixels most corresponding to the driving course in the aforementioned "driving course extraction method by iterative threshold processing using a template image". This is the part that is said to be. Furthermore, the range A has feature amounts ranging from tl to t2, and is divided into regions using each feature ff1tl and t2 as thresholds. Moreover, the B part located on the left side of the feature Jltl forms one mountain sandwiched between valleys, and has a feature value distribution in a dark range with lower brightness than the A part. The feature range of this portion B is from t3 to tl, and each feature t3 and tl becomes a threshold for region division. Further, the C portion on the right side of the feature amount t2 has a feature amount distribution in a bright range with higher brightness than the A portion, and forms one mountain sandwiched between valleys like the B portion. The feature range of this part C is from t2 to ti, and each feature ff1t
2 and ti become thresholds for region division.

Note that portions B and C shown in the figure form one mountain, but a feature distribution that does not form a single mountain in this way forms a meaningful region for region segmentation on the image. It cannot be recognized as a distribution. Therefore, such a feature quantity distribution is not selected as a region extraction target as it is not a dominant distribution. In the illustrated example, both the B portion and the C portion have a dominant distribution, but the present method is applicable even if only one is a dominant distribution.

The feature quantity distribution of part A corresponds to the road candidate area of case 2 shown in FIG. Further, the feature amount distribution of portion B corresponds to a shadow region having a lower brightness than this road candidate region, and the feature amount distribution of portion C corresponds to a high brightness portion having higher brightness than the road candidate region. This method extracts each area corresponding to each feature value distribution of the B part and C part adjacent to the A part.

First, in order to extract a region corresponding to part B of the histogram, an input image whose feature quantity is brightness is binarized using thresholds t3 and tl. Furthermore, in the above-mentioned [method for extracting a driving course by iterative threshold processing using a template image], a road area image is obtained based on an input image that uses saturation as a feature. This road area image is obtained by first dividing the original image into areas, and is an image in which dark areas such as shadows and high brightness areas are included in the road area. 1 is stored in the memory element corresponding to this road area, and 0 is stored in the memory element corresponding to the other background areas. Further, in the above binarized image, 1 is stored in the memory element corresponding to the pixel area whose brightness is from t3 to tl,
0 is stored in memory elements corresponding to other areas.

Therefore, by performing a logical product of the road area image and the binarized image, only dark areas such as shadow parts on the driving road area are individually extracted.

Furthermore, in order to extract a region corresponding to portion C, the brightness image is binarized using thresholds t2 and ti, similar to the above-mentioned finding of the dark region.

Then, the road area image extracted from the saturation image and these two
High brightness areas are individually extracted by performing a logical product with the valued image in the same manner as in the case of extracting the B portion described above.

Next, a method for determining the threshold values t3 and ti required when dividing portions B and C into regions will be described. Although the peak/trough table shown in FIG. 10(b) was obtained using the above-mentioned "threshold setting means based on the shape of the feature histogram in repeated threshold processing," the histogram shown in FIG. In the same way, a peak/trough table (not shown) is obtained. Each table value in this peak/trough table is expressed as pk ti as in FIG. 10(b).

It is assumed that the subscript i changes sequentially from i-0, 1, 2, . . . N, N-1 corresponding to each table value from the origin of the graph.

In the histogram of FIG. 15, the table value corresponding to the threshold value t1 is assumed to be pk tj. And peak
In the valley table, each table value is looked at from this table value pkti to the left, and it is determined whether there is a table value pktk (pktk<0) that is negative up to pktO. A feature point with a negative table value is a point corresponding to the bottom of a valley. pk becomes negative until pk to
tk, and from the feature points of pktj, pk t
If the distance to k feature points is smaller than the threshold (pk
tj - pk tk <L threshold), and the feature amount corresponding to this table value pk tk is set as a threshold value t3. Furthermore, if there is no pktk that becomes negative by pk tO, or if the distance exceeds the threshold, it is assumed that there is no dominant region that is darker than the road region.

The feature quantity corresponding to the threshold value t4 on the histogram can be obtained in the same manner as the method for obtaining the feature quantity corresponding to the threshold value t3. In other words, if the peak-trough table value corresponding to threshold t2 is pktm, then this pkt
Looking at each table value from m to the right, p k t N
It is determined whether there is a pktn (pktn<0) that becomes negative by -1. There is a pktn that becomes negative up to p k t N-1, and furthermore, from the feature point of pktn, pk
If the distance to the feature point of t+a is smaller than the threshold (
pktn-pktm (threshold value) This table value pk
The feature amount corresponding to tn is set as a threshold value t4.

Furthermore, if there is no pktn that becomes negative by p k t N-1, or if the distance exceeds the threshold value, it is assumed that there is no brighter and superior region than the road region.

As described above, this method is a "threshold setting means based on the shape of the feature histogram in iterative threshold processing"
By using the peak/trough table obtained in , it is possible to individually extract shadows, high-intensity areas, and discolored areas even if the road surface conditions change due to changes in the weather or pavement construction. .

Next, the "labeling device" will be explained in detail below. "
The image extracted by the method for extracting a driving course by repeated threshold processing using a template image has noise and finely divided regions. For this purpose, each region of the extracted image is labeled by a labeling device, and the validity of each labeled region is determined. Based on the results of this labeling process, areas where the center of gravity is above the horizon position and unnecessary small areas caused by noise or the like are removed.

FIG. 16 is a block diagram showing a schematic configuration of this labeling apparatus, and FIG. 17 is a general flowchart showing an outline of this labeling process.

First, an image extracted by the color processing device is loaded into the input memory 1601 via the image bus (NE BUS) (step 1701). This image information is 512X
The information is 512 x 8 bits, and this is used as a multivalued original image input. Next, primary labeling is performed using the run-based temporary labeling method described later (step 1702).
. This primary labeling is performed by a labeling processor (KL).
P) 1602, line buffer memory (LBM) 1
603 and label matching memory (LMM) 160
It is mainly executed in the 4th class.

After this primary labeling, the label matching memory LM
Preprocessing is performed to organize the data arrangement of M1604 (step 1703). After this preprocessing, secondary labeling is performed and at the same time feature quantities such as the area and center of gravity of each region are extracted (step 1704). The processing in steps 1703 and 1704 is mainly executed in the feature extraction processor KLC1605. Through this secondary labeling, a label attached to a pixel located at each address is stored in a label memory (LABELM) 1606. At the same time, the area and centroid of each extracted region are stored in the feature memory 1607.

do. After this, the label image information stored in the LABELM 1606 is output to the NE BUS (step 17
05).

One KLP1602 is used for label generation, and one LBM160 is used as a line register for run processing.
3 is configured using four label memories KLM, which will be described later. Additionally, the maximum number of temporary labels for LMM1604 is 102.
3, it is configured using eight KLMs. When the maximum number of temporary labels is 4095, 32 KLMs are used and LM
Configure M1604.

Conventional labeling was performed only when the input image was a binary image, but labeling using this method
By using 602, it is possible to label multivalued images as well. In other words, it is possible to label several types of images at once. For example, as shown in FIG. 18, assume that three types of binary input images 1801, 1802, and 1803 are input. These binary images are added together to form a 512x512
It is converted into a multivalued image 1804 of x8 bits. This conversion process is performed as pre-processing of the labeling process. A multivalued input image 1804 is labeled under the control of a labeling processor 1807 (KLP1602) using a line register 1805 (LBM1603) and a label matching memory 1806 (LMM1604).

In this labeling, organize the labeling of each area,
Final label image 18 of 512 x 512 x 12 bits
Output as 08. This labeling processor 180
7 (KLP1602) enables labeling processing for multivalued images, reduction of the number of temporary labels using runs, and one-scan labeling.

Each pixel of the multivalued input image is labeled according to each pixel value under the control of the KLP 1602. and,
Region segmentation is performed based on the connection relationship between pixels having the same label value, and a new label is generated based on this connection relationship.

For example, conventionally, when an input image has a region made up of step-like pixels shown in FIG. Label generation was performed by scanning the . As a result, when attaching temporary labels, three types of temporary labels, 1 to 3, are required as shown in the figure.

However, according to the labeling method using runs according to the present method, even if there is an input image shown in FIG. 19(b) consisting of stepped pixels similar to FIG. The number of temporary labels can be reduced. In other words,
As shown in FIG. 3C, each pixel is divided into rows called runs along the rask scan. In the illustrated case, it is divided into two run 1 and run 2. The labeling processor KLP writes a flag in the line buffer memory LBM until the scanning of the run reaches the last pixel, judges the temporary label, and at the last pixel of the row, connects all pixels of the run to the connection relation between each pixel. Write a temporary label that takes into account.

As a result of scanning and performing the above processing on run 1 shown in the same figure (C), the pixels corresponding to run 1 are shown in the same figure (d).
The temporary labeling shown in is performed. This temporary label "1"
' labeling is done simultaneously for each pixel. this is,
This is because the labeling memory KLM, which will be described in detail later, is used as the memory. By subsequently scanning run 2, the provisional labeling shown in FIG. 4(e) is performed. Since run 2 is connected to the temporary label "1" of run 1, when the last pixel of run 2 is scanned, the temporary label "1" is simultaneously written to each pixel of run 2.

By labeling using runs in this way, the same figure (b)
Labeling of the stepped pixels shown in can be performed using one type of label "1", and the number of temporary labels is reduced. In other words, the scale of the labeling circuit can be reduced by grouping pixels into one group called a run and performing processing on a run-by-run basis.

Next, details of the labeling process by the labeling processor NLP will be explained. Labeling is performed by scanning each pixel along each run with the window shown in FIG. By scanning this window along each run, the pixel of interest appears in the T (target) section, the pixel located above the T section appears in the a section, and the pixel on the right side of the T section appears in the b section. Pixels located next to each other appear. Below, T.

Let a and b indicate label values of the input image appearing in each part. Note that when the window is scanning in the middle of a run, the value of the flag is output to the line buffer memory LBM as an output label, and when the window reaches the last pixel of the run, all flagged pixels are Label is written.

The internal structure of KLP is shown in the block diagram of FIG. KLP selector 2101. Temporary label register T
m I 2102. It is composed of a counter Cnt210B, a first comparison circuit 2104, and an i2 comparison circuit 2105. The first comparison circuit 2104 is given label values T, a, and b, and performs a multi-value comparison of input images. The result of this comparison is the select terminal se of the selector 2101.
given to ll. The second comparison circuit 2105 includes a value Mat(a) in the label matching memory LMM of the label value a.
), the value of the temporary label register Tm12102 and the value of the counter Cnt2103 are given, and at the same time, multi-values are applied to the terminals A and B of the selector 2101.

given to C. The value of Tm12102 is determined by the output signal from selector 2101. Also, a line buffer memory LB is connected to the terminal of the selector 2101.
The value of the flag FLAG stored in M is given.

The second comparison circuit 2105 compares these applied multi-values. The connection relationship between each label is determined based on the comparison result, and the comparison result is transmitted to the select terminal 5 of the selector 2101.
Output to elo.

The selector 2101 outputs a matching address MAT ADDR and matching data MAT DATA based on the given multi-value, and changes the storage contents of the label matching memory LMM.

At the same time, the selector 2101 outputs a temporary label value and an output label value (LABEL).

22 to 27 show flowcharts of window processing.

FIG. 22 shows the multi-value T in the first comparison circuit 2104,
A flowchart is shown when performing a comparison judgment process between a and b. First, it is determined whether the label value T of the pixel of interest is equal to 0 (step 2201). If T is 0, processing 1 described later is executed (step 2202). If T is not O, label value T and label value S are compared (step 2203). When label value T and label value S are equal, label value T and label value a are compared (step 2204). If the label value T and the label value a are equal, process 2 is executed (step 2205). In other words, Process 2 is a multi-value T.

This is a process executed when a and b are equal. In this case, if each label value is expressed as O, the window state will be the state drawn adjacent to the illustrated processing box in step 2205.

If label value T and label value a are not equal, process 3
(step 2206). In other words, process 3 is a process that is executed when label value T and label value S are equal and label value T and label value a are different. In this case, if label value T and label value S are expressed as ○, and label value a is expressed as x, the window state will be in the state drawn adjacent to the processing box shown in step 2206. After the processing in step 2205 or step 2206, a flag is set at the position of window T in the line buffer memory LBM 160B (step 2207).

Further, in step 2203, even if label value T and label value a are not equal, label value T and label value a
(step 2208). If the label value T and the label value a are equal, process 4 is executed (step 2209).

In other words, in process 4, label value T and label value a are equal,
This is a process executed when label value T and label value S are different. In this case, if label value T and label value a are expressed as O, and label value S is expressed as X, the window state will be the state drawn adjacent to the processing box shown in step 2209.

If label value T and label value a are not equal, process 5
(step 2210). In other words, in process 5, label value T and label value a are different, and label value T
This is the process that is executed when the label value and the label value are different.

In this case, if label value T is expressed as O and label value a and label value S are expressed as ×, the window state is set to step 2.
It is drawn adjacent to the illustrated processing box 210 . Then, step 2209 or step 221
After processing 0, the temporary label register Tml in KLP is cleared (step 2211). This Tml stores a label for a pixel that was in the T portion immediately before reaching the current window position.

The flowcharts in FIGS. 23 to 27 described below show flowcharts of the comparison judgment processing from processing 1 to processing 5.

FIG. 23 shows a flowchart of the above-mentioned process 1. Process 1 ends without executing anything.

FIG. 24 shows a flowchart of the above-mentioned process 2. First, the label value of the previous pixel stored in the temporary label register Tml is compared with 0 (step 2401). Tml
When the label value of is equal to 0, the value Mat(a) of the label matching memory (LMM) 1604 of the label value a
is written into the temporary label register Tm12102 (step 2402). If the label value of Tml is not equal to 0, the label value of Tml and the counter value of counter Cnt2103 are compared (step 240B). The counter 2103 stores the value of the newest label.

If the label value of the temporary label register Tml and the counter value of the counter Cnt are equal, the value Mat(a) of the label matching memory (LMM) of the label value a is written to Tml (step 2404), and the value of Tml is written. If the value and the value of the counter Cnt are not equal, the value Mat(a) of LMM and the value of Tml are compared (step 24
05). If the value Mat(a) of LMM and the value of Tml are equal, nothing is executed (step 2406);
If the value of LMM Mat(a) and the value of Tml are not equal, the smaller value of the value of Tml and the value of LMM Mat(a) iM i (Tm I, Mat
(a) ) Write l to Tml. Furthermore, the smaller value of both (M in (Tm l, Ma
t (a))] is a label matching memory with a label value equal to the larger value of both [Ma t
(M i n (Tm 1. Mat(a))1
] (step 2407).

FIG. 25 is a diagram showing a flowchart of the above-mentioned process 3. In process 3, first, the value of the temporary label register Tml is compared with 0 (step 2501). Tml value is 0
, the counter value of the counter 2103 is set to T
ml (step 2502), and if the value of Tml is not equal to 0, nothing is done (step 2503).

FIG. 26 is a diagram showing a flowchart of the above-mentioned process 4. First, compare the Tm1O value with 0 (step 26
01). If the value of Tml is equal to 0, the label value a
The LMM value Mat(a) is set as the label value of the target area, and this Mat(a) is written into the T section and all registers with flags set (step 2602). At this time, all LBM flags are cleared. Further, if the value of Tml is not equal to 0 in step 2601,
Compare the value of Tml and the value of Cnt (step 260
3). If the value of Tml and the value of Cnt are equal, the LMM value Mat(a) of label value a is set as the label value of the target area, and this Mat(a) is stored in all registers where the T part and flag are set. (step 260)
4).

At this time, all LBM flags are cleared.

Furthermore, if the value of Tml and the value of Cnt are not equal, the value of Tml and the value of Mat(a) are compared (step 2605). Then, when the value of Tml and the value of Mat(a) are equal, the value of LMM of label value a Mat(
Using a) as the label value of the target area, this Mat(a,) is written to the T section and all registers with flags set (step 2606). At this time, all LBM flags are cleared. Also, the value of Tml and Mat(a
) are not equal, the smaller value of Tml and the LMM value Mat(a) of label value a (M i
n (Tml, Mat (a)) Write l as the label value of the target area to the T section and all registers with flags set. At this time, all LBM flags are cleared. Furthermore, the smaller value IM i n of the value of Tml and the value Mat(a) of LMM
(Tml, Mat (a)) 1 as a label matching memory [MatfMin (Tml, Mat
(a))l] (step 2607).

FIG. 27 is a diagram showing a flowchart of the above-mentioned process 5. First, the value of the temporary label register Tml is compared with 0 (step 2701). If the value of Tml is equal to 0, the value of Cnt is used as the label value of the target area, and this Cnt is written to the T part and all registers flagged.
Write the value of nt. At this time, all LBM flags are cleared. Further, the value of Cnt is written to Mat(Cnt) with a label value equal to the value of Cnt, and the value of Cnt is counted up by one (step 2702).

Also, if the value of Tml is not equal to O, the value of Tml is written to the T part and all registers where the flag is set, using the value of Tml as the label value of the target area (
Step 2703). At this time, all flags of the LBM are cleared. Next, the value of Tml and the value of Cnt are compared (step 2704). If the value of Tml and the value of Cnt are equal, the value of Cnt is written to Mat(Cnt) of the label value equal to the value of Cnt. Furthermore, Cn
Count up the value of t by 1 (step 2705)
. Furthermore, if the value of Tml and the value of Cnt are not equal, nothing is executed (step 2706).

Next, the labeling memory KLM used for the line buffer 7 memory LBM and the label matching memory LMM will be explained. In conventional memories, data could only be written to one internal register with one address specification. However, by using the KLM described below, data can be written to multiple internal registers at once. Therefore, this labeling memory KLM is a line register (LBM) for run processing and a label matching memory (LMM) that does not require label integration.

It can be used as a label image memory (LABELM) for one scan and a label matching memory that can perform label matching.

KLM is composed of multiple registers, but the second
FIG. 8 shows the block configuration of one of these registers. This block is one unit of the KLM structure. Comparators 2802 are connected to each register 2801 in pairs. This comparator 2802 receives output data D from the register 2801.
ATA and the information to be compared with this output data c
.

M is given. Comparator 2802 compares the applied data and outputs the comparison result to AND circuit 2803. In addition to this, the output of an address decoder circuit 2804 is given to the AND circuit 2803. AND circuit 2803 outputs a signal to OR circuit 2805 if either comparator 2802 or decoder circuit 28o4 outputs a signal.

A write signal WR from the CPU is applied to the OR circuit 2805, and an enable signal is applied to the register 2801 in synchronization with the write signal WR. In other words, whether it is selected by the address decoder circuit 28o4 or
If the comparison result in comparator circuit 2802 matches, data is written to register 2801 in synchronization with write signal WR. Addressing to each decoder circuit 28o4 and comparison judgment by each comparator circuit 28o2 are all performed simultaneously. Therefore, it is possible to simultaneously rewrite the contents of a plurality of registers constituting the KLM by one addressing or one data comparison decision.

The temporary labels obtained by the labeling process using the runs described above become discontinuous values when the labels are integrated. The contents of the label matching memory LMM at this time are shown in FIG. 29(a). Labels 1, 3.6 are stored as data corresponding to pixels at addresses 1 to 10. Since this label value is a discontinuous value, the same figure (b)
A feature extraction processor KLC shown in FIG. 1 and described in detail later converts the label into a label having continuous values as shown in FIG. That is, the label values stored in the label matching memory LMM configured by KLM are 1, 2.3.
becomes a continuous value.

More specifically, the labeling processor KLC generates an address for the LMM and takes in the data indicated by the corresponding address. Subsequently, the captured data and address are compared, and if the six values are the same, new data is output to the LMM and the label value is rewritten.

If the six values are different, the next address is output to the LMM and the data is compared with the next address. Thereafter, by repeatedly executing this process, the image shown in FIG. 29 (a
) is converted into a continuous label value shown in (c) of the same figure.

Specifically, since the data (1) at address 1 in FIG.
Rewrite the data at addresses 2, 4, 5°7 with new data 1. In the case shown in the figure, the old data and new data happen to be the same 1, so the figure (a
) and (C) of the same figure, there is no change in the data at the corresponding address.

Next, data (1) of address 2 is compared with the address. Since the address and data are different, the next address 3 is generated. Then, data (3) at address 3 is compared with the address. Since the address and data are the same, 2 is output as new data. LMM is KL
Since the data at address 9 and 10 have the same data (3) as the data at address 3, they are all rewritten to 2 at the same time, as shown in FIG. 3(C). The KLC then generates a new address 4. Since the address and data are different, address 5 is generated next, and thereafter, the same process as above is repeated. As a result,
Discontinuous values are converted to continuous values.

FIG. 30 is a block diagram showing the internal configuration of this feature extraction Bromo-Sosa KLC. By using this KLC, preprocessing of temporary labels generated by primary labeling is performed. In addition, during secondary labeling, at the same time as labeling, calculation of the area of the same label area, calculation of the sum of the X-direction addresses of the same label area, and calculation of the sum of the Y-direction addresses of the same label area are executed by this KLC. .

KLC has a +1 adder 3001 and two adders 300
2.3003, a comparator 3004, and two counters 3005 and 3006. The +1 adder 3001 increments the count by one when there is a pixel input having the same label value, calculates the area of the same label area, and outputs it as 5ize. The adders 3002 and 3003 contain the X direction address value Y.
A direction address value has been entered. Then, when there is a pixel input with the same label value, the address values are added in each direction, and the sum of the address values of the same label area is calculated for each address direction. Each total value is X AD
Output as DR and Y ADDR. By dividing the total value of addresses in each direction by the area of the same label area, the center of gravity in each direction can be determined. Then, the center of gravity of each identically labeled area is determined, and areas whose center of gravity is above the horizon are removed as not being effective for extracting road candidate areas.

The comparator 3004 and counters 3005 and 3006 are
It is used for preprocessing of temporary labels that occur during primary labeling, that is, for converting discontinuous label values into continuous label values. A clock signal CLK is input to counters 3005 and 3006, and the output of counter 3005 becomes a matching address MAT ADDR that is output to label matching memory LMM. This address is also given to comparator 3004 at the same time. Also, counter 30
The output of 06 becomes data MAT DATA that is output to the label matching memory LMM.

Comparator 3004 compares the given address and data as described above, and outputs a signal to counter 3006 if the multi-values of the address and data match. When the counter 3006 receives this signal, the Mat
Outputs the current counter value to DATA and increments the value by one.

The processing time of the labeling process described above required the sum of the rask scanning time of two scans performed along each run and the label integration time. However, the 16th
By configuring the label memory LABELM 1606 shown in the figure using the labeling memory KLM described above, labeling processing can be executed in one scan. That is, as shown in FIG. 31, when a multivalued input image 3101 is captured, the labeling processor KLP 3102 uses the line register 3103 and the label matching memory 31o4 to execute the labeling process in the same manner as described above. . The label value of each pixel obtained by this labeling is written as is into the label image memory 31o5 at the time of scanning the last pixel of each run. Note that since label integration is not performed, the values of each label are stored as discontinuous values.

As mentioned above, in the labeling memory KLM, a comparator is connected to each internal register in pairs, and new data is written to the register whose comparison result by the comparator matches and the register whose address has been selected at - degrees. It is something. With this KLM feature 1
Scan labeling is now possible. Furthermore, the labeling process O-TY+I-KLP is a hardware version of the algorithm of this method, and enables high-speed labeling.

This one-scan labeling method makes it possible to reduce the labeling processing time to less than half of the previous one. For example, if the device is operating with an 8 MHz clock signal, the traditional labeling processing time requires 66 m5 e c for two scans of the window, plus the time required for label integration. And so. but,
According to this one-scan method, 33m5e, which is less than 1/2
Labeling processing can be performed using c.

Further, although normal pixel scanning is performed from the upper left to the lower right of the screen of the input image, in image processing for extracting a road area, the target image is located at the bottom of the image. Therefore, when scanning a target image, there is a possibility that the memory for storing temporary labels will overflow. Therefore, by scanning from the lower right to the upper left of the screen and scanning the target image first, the target image can always be obtained. In other words, if the target image is acquired first, even if a memory overflow occurs, image scanning at the time of overflow will be a scan of unnecessary image parts, and the target image can always be acquired.

Next, a "method for merging multiple regions" obtained by dividing an image will be described.

Road candidate areas are determined by the “driving course extraction method using iterative threshold processing using template images”.
Shadows and high-brightness areas, which are low-brightness areas, were found using ``a method for extracting shadows and high-brightness areas on a driving course that focuses on differences in brightness.'' Using this road candidate area as a reference, low-luminance areas and high-luminance areas that are strongly connected to the road candidate area are merged into the road candidate area, treated as one area, and regarded as a driving course. To do this, the common boundary length adjacent to each region and the perimeter length of each region are determined, and the relationship between the connected regions is described. The merging relationship is expressed by the description of the relationship between each region, and the same result as merging regions can be obtained without changing labels as in the conventional method. Note that the common boundary length is determined based on the length of the side of the pixels adjacent to each region, and the perimeter length is determined based on the length of the side of the outermost pixel of each region.

The algorithm of this method is shown below. There are two methods for this method. Firstly, there is an inverted character mask scanning method in which a mask of inverted characters is scanned. This method is a simple algorithm and is suitable for hardware implementation.

Second, there is a region boundary exploration method that locally searches the boundaries of a region, and since this method searches only the boundaries of a necessary region, it is effective because it can be processed with a small amount of memory.

The first method, the reverse character mask scanning method, is executed by scanning the reverse character mask shown in FIG. 32 from left to right and from top to bottom of the label image. The X pixel appearing in the illustrated mask is the pixel in the row, the a pixel is the pixel located above the pixel of interest X, and the b pixel is the pixel located to the left of the pixel of interest X. For example, assume a pixel area shown in FIG. 33. The mouth shown in the figure represents one pixel, and the numerical value inside the mouth represents the label value of that pixel. In this example, the area with label value 1 and the area with label value 4 are adjacent to each other. Although not shown in the figure, the label value of the background area is 0.

The perimeter ob of each region is determined by scanning the inverted mask along the rows of each region, that is, along the runs. Specifically, the perimeter Ob of the area with the label value 1 is determined as follows. First, the X pixel of the inverted character mask is aligned with the pixel located at the left end of the top run. In this case, since pixel a and pixel b are in the background area and have a label value of 0, it can be seen that the two sides of this pixel are located around the area with the label value of 1. Therefore, 2 is added to the counter that counts the perimeter obl. Next, the reverse character mask is scanned to the right, and the X pixel is aligned with the pixel on the right. In this case, the a pixel is in the background area, and the b pixel is in the main area with a label value of 1, which is the sum of the previous mask. Therefore,
It is found that one side of this pixel is located around the main area with the label value 1, and 1 is added to the counter. By scanning the inverted character mask along the run for the area with the label value 1 in this manner, the perimeter obl becomes 18. Note that the unit of the perimeter Ob is the number of sides of a pixel.

The perimeter obJ of the area with label value 4 is also the perimeter obl above.
It is obtained in the same way as , and the value is 20.

Further, the common boundary tool cb between the area with label value 1 and the area with label value 4 can be found as follows. This common boundary tool cb has a label value of 4 when viewed from an area with a label value of 1.
The common border tool cb14 with the area of is different from the common border tool cb41 with the area of label value 1 viewed from the area of label value 4. In other words, the mask has an inverted shape and only two neighboring pixels of each pixel are considered, which may cause a difference in the common border, or there is no equivalent problem when merging multiple regions. Note that if the mask to be scanned is made into a cross shape that looks at four neighborhoods of the pixel of interest, there will be no difference in common boundary tools.

Common boundary tool c with label value 4 seen from the area of label value 1
b14 is determined by mask scanning when determining the perimeter obl. This common boundary tool cb14 becomes 0. That is, even if the inverted character mask is scanned for each run in the area with the label value 1, the pixels with the label value 4 do not appear in the a and b pixels.

A common boundary tool cb41 between the area of label value 1 and the area of label value 1 viewed from the area of label value 4 can be obtained by mask scanning when obtaining the perimeter ob4. This common boundary tool cb41
becomes 3. In other words, if the mask is located at the first pixel of the second and third runs in the area with label value 4, b
A pixel with a label value of 1 appears in the pixel. Therefore, by mask scanning for the runs up to the third stage, the common boundary tool c
The value of the counter that counts b41 becomes 2.

Further, when the mask is located at the beginning of the fourth run, a pixel with a label value of 1 appears at pixel a of the mask.

Therefore, 1 is added to the counter, the integrated value of the counter becomes 3, and the common boundary tool cb41 becomes 3. Note that the unit of the common boundary tool cb is the number of sides of a pixel.

Next, the values of the common boundary between the regions and the perimeter of each region thus determined are stored in the inter-label boundary length matrix shown in FIG. 34.

The numbers 0, 1.2, etc. attached to each column of the same matrix
j,...kl and numbers 0, 1゜2 attached to each line
..., i, ...g indicate label values. Numerical value mi stored in the location specified by the numerical value in each column and each row
j is a common boundary between the area of label value j and the area of label value j seen from the area of label value i. Further, the numerical value t1 stored in the (k+1)th column is the perimeter of the area of the label value i.

Taking the pixel area shown in FIG. 33 as an example, the label value 1
Common boundary tool cb1 with the area of label value 4 seen from the area of
Since the value of 4 is 0, O is stored in the memory located in the 1st row and 4th column of the same matrix. Further, since the value of the common boundary tool cb41 between the area of label value 1 and the area of label value 1 viewed from the area of label value 4 is 3, 3 is stored in the memory located in the 4th row and 1st column of the same matrix.

After creating a matrix by finding the perimeter of each region and common boundaries between the regions, the degree of connectivity between the regions is calculated.

This degree of connectivity is determined by the following equation based on the common boundary length and perimeter length.

Connectivity - X/min (A, B) where A is the perimeter of the region with label value l, B is the perimeter of the region with label value j, and m1n(A.

B) represents the smaller of A and H. Moreover, X is the average value of the common boundary length between each region expressed by the following formula.

X-(X1+X2)/2 Xl is the common boundary length between the area of label value j and the area of label value j as seen from the area of label value i, and X2 is the common boundary length of the area of label value i as seen from the area of label value j. .

In the above formula for X, both Xl and X2 are not 0 (X
This is valid when i≠O, X2≠O).

When X2 is 0 (X2-0), X is expressed by the following formula.

-X 1 When Xl is 0 (Xi-0), X is represented by the following formula.

-X2 If the calculated degree of connectivity is greater than or equal to a predetermined threshold, the connection between the region with label value i and the region with label value j is strong, and the regions are in a relationship that should be merged. Furthermore, if the degree of connectivity is below a predetermined threshold, the connection between the region with label value i and the region with label value j is weak, and the regions are not in a relationship that should be merged. This merging relationship is described in the connection label column of the feature list shown in FIG. 35.

The label No. of the same list is a label value, and the area double center of gravity is the area and center of gravity of the region of that label value. This area and center of gravity are obtained during the labeling process described above.

A circumscribing rectangle is a rectangle that encloses all pixels within the region of the label value.

A circumscribed rectangle has four vertices that are intersections between sides,
It is specified by the coordinates tL (x, y) of the top left vertex and the coordinates bR (x, y) of the bottom right vertex. Each coordinate is determined during the boundary exploration process described above. Further, the label No. written in the connection label column indicates the label value of the area that should be merged with the area of that label value. If there is an area to be merged with the area described in this column, connection labels are further connected by a pointer as shown in the figure.

Further, each feature amount described in the same list is for each area shown in FIG. 36. Each area has a label value β1~g
4 is attached, and 61 to G4 indicate the center of gravity of each region. Also, a circumscribed rectangle is drawn in each area. The point of contact between the upper side of this rectangle and the area is the coordinate st (
x, y) and is determined by horizontal operation from the area starting point tL (x, y). The coordinate st is used in the method described later.

Since the area with the label value g1 and the area with the label value p2 are in a relationship that should be merged, the label No., l!
Label value g2 is written in the connection label field of row 1.

Furthermore, since the area with the label value All is in a relationship to be merged with the area with the label value g3 and the area with the label value g4, the connection labels of the label values p3 and p4 are connected by a pointer. Furthermore, the connection relationships between the areas are described in the same way in the connection label columns of the rows of labels No., j)2 to Ω4.

Next, the area boundary exploration method will be explained.

First, draw a rectangle that circumscribes the target area, and the coordinates 5t (x) where this circumscribed rectangle and the area touch.

Find the search start pixel located at y). Then, eight pixels located in the vicinity of this search start pixel are investigated.

8. Each reference pixel located in the vicinity is given a position number as shown in FIG. That is, the number located above the pixel of interest is set to 0, and the numbers are assigned in clockwise order. The coordinates of the pixel to be searched next to the search start pixel are shown in Figure 38 (a
), (b) using the pixel reference table.

The table shown in (a) of the same figure is a table that is referred to when performing a pixel search clockwise (clockwise).
The table shown in FIG. 4B is a table that is referred to when performing a pixel search counterclockwise (counterclockwise). The numbers 0 to 7 in parentheses () in the table are the third
This corresponds to the position No. of the reference pixel in FIG.

The next pixel to be searched is the reference pixel position No. corresponding to the current pixel position relative to the previous pixel position.

Find the row number of the table that matches this position number,
It is determined by referring to the column No. A method for determining search pixels using a pixel reference table will be specifically described below. Assume that the boundary of the pixel area is formed as shown in FIG. 39. The hatched areas in the figure indicate pixels whose label values are not 0. The previously searched pixel is indicated by the symbol Δ, the currently searched pixel is indicated by the symbol 0, and the next pixel to be searched is indicated by the symbol ◎.

The current pixel position O with respect to the previous pixel position Δ is the 37th pixel position O.
The reference pixel position No. in the figure corresponds to 1.

If pixels near the boundary of the area are searched clockwise, the pixel reference table will refer to the table in FIG. 38(a). Reference pixel position No.

is 1, so the column number where the row number is 1, (7°0
．． See 1, 2.3, 4, 5.61. In addition, line No.
, the top row is 0, and the rows are 1 to 7 in order.

In addition, column No. indicates all the numbers of the pixels to be referenced, and by referring to the eight neighboring pixels of the pixel in this order, it is possible to avoid modulo calculations in address calculations for day-to-day children.

In other words, since the column number starts from 7, the next pixel to be searched is the pixel located diagonally to the upper left of the current position ◎
become. Since the pixel ◎ is in the background area and the label value is 0, the next pixel is searched according to the column number. In other words,
Next reference pixel position N.

Since is O, the pixel located above the current position ○ is searched. Since this pixel is also in the background area, the column No.
, a pixel whose reference pixel position No. is 1 is searched for.

Since this pixel has a label value and is not 0, the reference for the next pixel to be searched is set to the pixel at this position No. 1, and the eight neighboring pixels are searched in the same manner as above. and,
Perform the above processing for each pixel along the region boundary,
Similar processing is repeated for each pixel until returning to the search start pixel.

In addition, in this search process, by performing processing according to the following rules, the perimeter o of the own area of label value i
common boundary length c between bi and adjacent areas of label value j
blj can be found.

In other words, if the label value j exists in four adjacent areas on the upper, lower, left, and right sides of the current position, 1 is added to a counter that counts the common boundary length cbij.

At the same time, 1 is added to a counter that counts its own perimeter obi. Furthermore, if there is no pixel with the same label value as its own label value i in the four vicinity of the current position, 1 is added to its own perimeter counter.

Next, based on the obtained perimeter length and common boundary length, the degree of connectivity between each region is obtained in the same way as calculation in the inverted mask operation method. At the same time, a feature list is created in the same manner as described above. The connection label of this feature list describes the connection relationship between each area, and the merging relationship of multiple areas is determined.

In other words, even with this method, the merging relationship of each area can be determined without changing the label of each area. Although the above boundary search was performed clockwise, if the boundary search is to be performed counterclockwise, it can be performed clockwise or counterclockwise by using the counterclockwise pixel reference table shown in FIG. 38(b). Processing can be performed in a similar manner.

Using a pixel lookup table in this way allows for fast boundary exploration. In other words, it is not necessary to investigate all eight pixels in the vicinity of the pixel serving as the search reference. Further, it is only necessary to search for pixels near the boundary of the area, and there is no need to search for all pixels within the area. Therefore, processing time is reduced.

According to each of the methods described above, it is possible to determine the merging relationship between the divided regions without changing the labeling and scanning as in the conventional method. In other words, the road candidate areas obtained by the ``driving course extraction method using iterative threshold processing using template images'' and the ``extraction method of shadows and high-brightness parts on the driving course that focuses on differences in brightness'' are used. The obtained low-luminance and high-luminance areas are combined to obtain a realistic driving course area.

Next, the "means for determining the travelable range" will be explained. This method consists of ``a driving course extraction method using iterative threshold processing using a template image,'' ``a threshold setting method based on the shape of the feature histogram in iterative threshold processing,'' and ``a method that focuses on differences in brightness. The final drivable range, that is, the road edge seat is determined from the driving course image obtained by the ``extraction means for extracting shadows and high-luminance portions on the driving course''.

FIG. 40 is a flowchart showing the overall processing flow of the driving course recognition system according to the present method.

First, image information of the driving course is captured using a color camera input device, and the captured R, G, and 8 images are adjusted as described above to determine the brightness. , to each image with saturation S. Based on each converted image, a histogram having lightness I as a feature and a histogram having saturation S as a feature are created in the color processing device as described above (step 400
1). Next, based on each of the created histograms, road candidate regions are extracted using a "driving course extraction method based on iterative threshold processing using a template image" and small regions are removed (step 4002).

Next, using this method, the point sequence of the road edge of the extracted road candidate area is evaluated (step 4003).

Then, based on the evaluation result of the four rows of road edge points, it is determined whether the extracted road candidate area is a monotonous road or not (step 4004). In the case of a monotonous road similar to a road, the relationships between the obtained multiple point sequences are further compared and evaluated (
Step 4005). Then, this evaluation result is finally output (step 4006). After this, it is assumed that the point sequence for the currently input image has been obtained, and processing is executed for the next image.

Furthermore, if the judgment result in step 4004 is that the road-likeness is low and the road is not monotonous, the "extraction means for extracting shadows and high-luminance parts on the driving course that focuses on differences in brightness" is used to
If there is a low brightness area, it is extracted (step 4007
). Then, the obtained low-luminance area and the road candidate area are merged, and the road edge point sequence is evaluated using this method (step 4).
008).

Based on the evaluation result of this road edge point sequence, it is determined whether the extracted road candidate area is a monotonous road or not (step 4009).
. If the path is monotonous, the process from step 4005 onwards is executed, and the process moves on to the next image.

In addition, if the road is not monotonous, next, if there is a high brightness area, it is extracted using "a means for extracting shadows and high brightness parts on the driving course that focuses on differences in brightness" (step 4).
010). Then, the obtained high-luminance region and the road candidate region are merged, and the road edge point sequence is evaluated using this method (step 4011). Based on the evaluation result of this road edge point sequence, it is determined whether the extracted road candidate area is a monotonous road (step 4012). If the road is monotonous, step 4
The processes after 005 are executed, and the process moves on to the next image. If the road is not monotonous, the low-luminance area and the high-luminance area are merged into the road candidate area, and the road edge point sequence obtained from the merged area of the three areas is evaluated (step 401
3).

Thereafter, the process of moving to step 4005 is executed, and the process moves to the next image.

Next, a method for obtaining the point sequence coordinates of the road edge in the road candidate area will be described below.

For example, assume that the image area shown in FIG. 41 is obtained. The upper left of the figure is the origin, the X coordinate is positive in the horizontal direction toward the right, and the X coordinate is positive in the vertical direction toward the bottom. There are notches in the road area shown in this image, and there are scattered locations where image information could not be obtained due to noise or the like. It is assumed that labeling processing is performed on each pixel of the image shown in the same figure, and the resulting pixel area is shown as shown in FIG. 42 as a result of this processing. The shaded area in the figure is a pixel whose label value is not 0 but has a certain label value. Note that pixels without diagonal lines are pixels located in a background area with a label value of O. Also, a frame 4 surrounding 3x3 pixels
201 is a window W, and the number of diagonally lined pixels (pixels having non-zero pixel values) existing in the window W becomes the value of the histogram. The value of the histogram by window W in the case shown is 5. Also, although the illustrated window W is a 3×3 window, the 5×
It may be a window of other size, such as 5 or the like.

First, the window W is scanned horizontally from the center of the image toward the left. Note that the window W is scanned from the center of the image only at the start of the process. The histogram value of the window W at each position is determined while moving. If the window W is moved while monitoring this histogram value, and histogram values below a predetermined threshold are continuously obtained, that is, the density of diagonally lined pixels in the window W becomes low. , it is determined that the window W is outside the road area. Then, the position of the first window W whose histogram value becomes less than or equal to a predetermined threshold value is set as the point sequence coordinate XL of the left road edge.

Next, the window W is horizontally scanned toward the right side, and when the histogram values within the window W are continuously below a predetermined threshold, the position of the window W where the histogram value first changes is set to the right side. Let the point sequence coordinates of the road edge be XR.

Next, the Y coordinate at which the window W is located is decreased by one, and the window W is moved above the image to shift the horizontal scanning position. Then, from the road edge coordinates XL and XR obtained by the above first horizontal scan, the center position of the road area is calculated using the formula (XR-
It is obtained by calculating XL)/2. This center position is set as the scanning start position of the window W, and the window W is scanned left and right. In this scanning as well, the histogram value within the window W is monitored in the same manner as above, and the position where the histogram value changes is taken as the coordinates of the road edge.

Thereafter, by repeating the same process until the Y coordinate of the horizontal scanning position reaches the horizon position, a series of point sequence coordinates of the left and right road edges can be obtained.

In addition, in scanning this window W, the histogram value obtained from the window W at the scanning start position is below a predetermined threshold from the beginning, and moreover, the histogram values obtained by scanning the window W to the left are consecutive. If it is below a predetermined threshold, the center position becomes the road edge coordinate. However, in this case, the scanning direction of the window W is changed to the right side. Then, when histogram values greater than or equal to a predetermined threshold are obtained consecutively, the position of the window W where a histogram value greater than or equal to the predetermined threshold is first obtained is set as the coordinates of the left road edge. . The coordinates of the right road edge can be found by scanning the window W further to the right and finding the position where the histogram value changes.

Next, since the point sequence coordinates of the road edge obtained in this way exist near the boundary of the area, the boundary line obtained by connecting each point is not uniformly smooth. For this reason, a certain 1
The angle formed by each point located before and after the point and this one point is calculated for all points in the point sequence, and this variance value is used as a standard for smoothness. Also, if the obtained angle is an acute angle, that point is removed from the calculation. After smoothing the point sequence coordinates of the left and right road edges in this manner, these point sequence coordinates are projectively transformed into real space. This projective transformation is performed based on the depression angle, height, and focal length of a color camera attached to the autonomous vehicle.

Furthermore, in the point sequence after projective transformation, the distance between the left and right point sequences, that is, the road width, is determined by setting the left and right point sequences as a set. Then, the number of points where this road width is narrower than the vehicle body width of the traveling vehicle is counted, and the number of points of this narrow width relative to the total number of points in the point sequence is calculated. If the ratio of the narrow width points to the total number of points is small, the narrow width points are not suitable as road edge points, so these points are removed.

In addition, when evaluating this road edge point sequence, the left and right pairs that have a small difference from the road width determined by the initially determined pair of left and right edges are counted. When the ratio of left and right sets with little difference to the total number of sets is large, that is, when the left and right road edge rows are parallel to some extent, the evaluation as road-likeness is highest, and the road is judged as a monotonous road. be done. If it is determined that the path is monotonous in this way, steps 4003, 4008, 40 in the flowchart shown in FIG.
It is possible to obtain the road edge without performing the processing in 1].

Next, a description will be given of means for correcting the point sequence at the left and right edges of the road when the autonomous vehicle approaches the road edge too much. FIGS. 43(a) to 43(d) show the process in which the autonomous vehicle approaches the edge of the road. Figure (a) shows a case where the autonomous vehicle is located in front of a curve with a sharp curvature. In this case, the left road edge and the right road edge R are captured within the field of view of the color camera attached to the autonomous vehicle. When the curvature of the road curve is sharp, the autonomous vehicle located at (a) in the figure moves to the position shown in (b) in the figure. In this case, the right road edge R disappears from the field of view of the camera.

Further, the autonomous vehicle moves to the position shown in FIG. 2(c), and the ratio of the off-road area to the template gradually increases. The illustrated shaded area indicates the area outside the road. Furthermore, the autonomous vehicle moves to the position shown in FIG.

In this case, the left road edge and the left boundary of the off-road area are captured in the field of view of the camera. Moreover, the ratio of the area outside the road to the template image becomes high, and the area outside the road is mistakenly recognized as the driving course. As a result,
The left road edge is mistakenly recognized as the right road edge R, and the left boundary of the off-road area is mistakenly recognized as the left road edge.

However, in the point sequence of the road edge obtained from sequentially captured image information, the point sequence on the right side in the previous image does not become the point sequence located extremely on the left side in the current image. Also,
Conversely, the point sequence on the left side in the previous image will not become the point sequence located extremely on the right side in the current image. Therefore,
The point sequence information obtained from the image information one processing cycle ago is stored and retained, and the distance between the point sequence obtained from the current image information and the point sequence obtained from the previous image information is calculated as described later. . For example, the distance between the point sequence of the right road edge found last time and the point sequence of the right road end found this time is far apart,
If the previous right side point sequence is close to the current left side point sequence, it is determined that the positions of the left and right road edges have been reversed. Then, swap the right and left sides of the road edge obtained this time.

This will be explained using the image shown in FIG. The image shown in FIG. 4C is the image obtained last time, and the point sequence at the left road edge is expressed as L i-1. The image in (d) of the same figure is the image obtained this time, and the point sequence of the misidentified left road edge is L.
l. The misidentified right-side road edge point sequence is expressed as R1. To determine whether the dot sequences on the left and right road edges are reversed,
This is performed by determining which of the current point sequence Li and Rj the previous point sequence Li-1 is closer to. Previous point sequence L
If i-1 is close to the current point sequence R1, it is determined that the point sequences at the left and right road edges are reversed.

- The proximity of this point sequence within the film is determined as follows. In other words, the left-hand point sequence obtained from this image is one group, the right-hand point sequence is another group, and it is determined which of these groups the previous left-hand or right-hand point sequence is closer to. Do by doing. The determination of which group it is closer to is determined by the Mahalanobis general distance described in detail below. FIG. 44 is a diagram for explaining the Mahalanobis general distance.

The point of the left point sequence Ll-1 (or right point sequence R1-1) according to the previous image information is (x, y), the point of the left point sequence Ll according to the current image information is (x lj, y lj), this time The points of the right-hand point sequence Ri based on the image information of (x 2j.

Y2j). To determine which point (x, y) in the previous point sequence is closer to the current point sequence L1 or Ri, use the Mahalanobis general distance to point sequence Li-1 (or point sequence R1-1).
Calculate as follows for all points in , and choose the one closest to the point sequence to which the most points with short distances belong. Furthermore, when the point sequence determined from the current image is a straight line, the distance to this straight line is calculated.

First, for each point on the point sequence Ll, the average value μm1 of the X direction component. Average value of the y-direction component μm2. Variance value σ11 of the X direction component. Variance value σ12 of the y-direction component. x.

A covariance value σ112 and a correlation coefficient ρ1 in each y direction are determined. Here, ni is the number of points located on the point sequence Ll. Note that each point on the point sequence Ri can also be determined using a formula similar to the following formula.

μll−Σxlj/nl, μl2−Σy lj
/ n 1σ112-Σ(xlj-R11) 2/ (
nl -1) σ122 - Σ (7 questions - μm2) 2/ (
nl −1) σ112−Σ(xlj−μll) (y
lj-μl2) /(nl-1) ρ1-σ112 /σIIX σ12 Based on these values, the point (x.

y) and the point (x lj, y lj) of the current point sequence Ll
The Mahalanobis general distance Di between can be calculated using the following equation.

Di 2- + [(x-μll) / (711] 2
+ [CY-μ 12)/σ 12ko 2 ρ
l [(x −μ ll) /σ 11 comments,
[(y − μ 12) / σ 11 co) / (1
−ρ l) 2 Similarly, find the Mahalanobis general distance D2 between the point (x, y) of the previous point sequence and the point (x 2j, y 2j) of the current point sequence Ri using the following formula. I can do it.

D22- ([(x-μ21) /cy21] 2+
[(Y-μ22)/σ22]2ρ2 [(X-μ21
)/σ 21]X'[(y − μ 22) / σ
22 Co) C 1- ρ 2) 2 As a result of calculating each general distance based on each formula above, if Di2>D22 holds, then the previous point (x, y) is the current road edge on the right side. This is close to the point sequence R1. Also, Dl > D22
If this does not hold true, on the contrary, the previous point (x, y) will be close to the current point sequence L+ of the left road edge.

Even if the road candidate area obtained as a result of the image segmentation process is an area with an unclear outline due to noise, etc., the edge points of the road can be determined based on the changes in the histogram values of the window using this method. You can definitely get it.

This is because the present method searches for the end points based on the region, and according to the present method, the left and right ends of the region can be clearly distinguished.

In addition, low-luminance areas found using the "extraction method for shadows and high-luminance areas on a driving course that focuses on differences in brightness" may be located outside the road if the driving course is dark overall. be. In such a case, the low-luminance area outside the road and the road area may be merged, and the shape of the outline of the road candidate area becomes complicated. However, by smoothing the obtained road edge point sequence data using this method, regions with complex contours can be evaluated in a global manner, and low-luminance regions such as those mentioned above are ignored. It is possible to obtain road edge information without any problems.

In addition, according to the ``driving course extraction method using iterative threshold processing using template images,'' when an autonomous vehicle approaches the left or right side of a road with a sharp curvature, the template may veer off the road. In some cases, the road may be considered a road.

In this case, the left and right sides of the road edge will be incorrectly recognized.

However, according to this method described above, even if the left and right edge data of the road is incorrectly recognized, this recognition is immediately corrected, and highly reliable road edge information can always be obtained.

Next, a description will be given of the "method for internally representing driving courses of various shapes," which is a feature of the present invention, that is, the method for structuring and representing the various point sequences of obtained road edges.

This method uses an image of a driving course obtained by ``a means of extracting a driving course by iterative threshold processing using a template image'' and ``extracting shadows and high-brightness parts from the driving course by focusing on differences in brightness.'' Based on the image obtained by the "method for merging multiple regions" and the list of features obtained by the "method for merging multiple regions," a strafture of region boundary points is created while detecting the label displacement location of the image, and links in the forward and backward directions are created. The driving course is expressed inside the computer by adding boundary attributes and determining a valid point sequence for driving. By using the inter-feature list that represents the description of regions and regions created in "Means for merging multiple regions", the end points of regions can be obtained quickly, and road edges, road shoulders, 1 branching roads, and merging roads. is represented by a structured list inside the computer.

FIG. 1 is a flowchart showing an outline of road structuring processing.

First, when initializing each piece of hardware such as a color camera input device, a list of region boundary point struc- tures in the X direction is created (step 4501).

Next, a change point in the X direction of the label value attached to each area is detected, a list in the X direction is created, and a link is made in the X direction of each boundary point (step 4502). Then, considering the connection label of the inter-feature list of each region, attributes are given to the left and right ends of the region, and the left and right ends of each region are divided (step 4503). Next, while adding attributes such as holes, which will be described later, to each boundary point,
, and link each boundary point in the X direction (step 4504). In addition, there are cases where road areas diverge or merge, and in each of these cases, the continuity of the boundaries of each area is determined, and the attributes assigned to each boundary point are changed (step 4505). . Thereafter, the starting position of the point sequence of the boundary points of each area is selected, and a valid point sequence is detected (step 4506).

Each of the above processes will be explained in detail below.

The process of step 4501 will be explained with reference to FIG. 46.

FIG. 5A is a diagram showing the principle of projective transformation of a road surface (assumed to be a horizontal surface) in real space onto an image. The road surface 4601 is divided into equal intervals (11), and the road area and each division line on the road are divided into the image 4 toward one point in the distance.
602 to obtain the viewport of the color camera. FIG. 4B is a diagram showing details of the image obtained in this manner. There is a boundary line 460 of the road area on the image.
3 and the dividing line 4604 have been projectively transformed. In real space, the lane markings were equally spaced at intervals of ρ, but in the image, the intervals become closer as you get farther from the road area. The y-coordinates at which each division line 4604 is located are determined, and an area boundary point structure 4605 in the X direction shown in FIG. 4(c) is created.

The six frames of this area boundary point struc- ture 4605 are the leftmost boundary line and the dividing line 46 of the road area boundary lines 4603.
This corresponds to each boundary point located at the intersection with 04. The mutual connection relationship of the six frames is expressed by pointers indicated by arrows in the figure.

In each of these frames, the characteristics of each boundary point are described as a list 4606 shown in FIG. 4(d).

First, the six values of the determined y coordinate are written in a list 4606, and a list in the X direction is created. In addition to the above y-coordinate, this list 4606 describes each feature that each boundary point has, which will be described later.

In other words, attribute 1 representing the X coordinate 1 point sequence starting point iD, attribute 21 representing the distance between adjacent points in real space, pointer to the right neighbor representing the connection relationship between the boundary point of interest and the boundary point to the right, pointer to the left neighbor A pointer to the left that represents the connection relationship with the boundary point, a pointer to the front that represents the connection relationship with the boundary point in front of the screen in the A pointer is written.

Next, the process of step 4502 will be explained with reference to FIG. 47.

An image 4701 shown in FIG. 4A is an image obtained by performing labeling processing on a captured image. Through this labeling process, each region constituting the road region is assigned a label value. Among the intersections between each division line and the area boundary, the intersection marked with a circle is a label displacement location where the label value changes. First, step 4501
The image is scanned in the horizontal direction, that is, in the X direction at each y-coordinate position of the list obtained by the process. In this scan, if you move from a background area whose label value is O to a road area whose label value is not 0, or if you move from a road area whose label value is not 0 to a background area whose label value is 0, Create a new region boundary point structure.

This region boundary point struc- ture is shown in FIG. 4(b).

As shown in the figure, a new frame is provided in the X direction corresponding to each boundary point located at the intersection of the boundary of each area and the division line. These six new frames are connected to the six frames of the area boundary point structure in the X direction that has already been created in the previous step.

This connection relationship is expressed by a pointer represented by an arrow in the figure, and the six frames are linked in the horizontal direction by this pointer.

Next, the process of step 4503 will be explained with reference to FIG.

It is determined whether each set of points in the horizontal direction of the area boundary point structure created in step 4502 exists in the same area. The determination as to whether the regions are the same or not is made based on the feature list obtained in the above-mentioned "method for merging multiple regions."

When adjacent points exist in the same area, the boundary point located on the left side is treated as a left edge, and the boundary point located on the right side is treated as a right edge, and this attribute is described in each list. This attribute allows the left and right ends of the area to be distinguished. Furthermore, the distance in real space from this left edge to the right edge is calculated and similarly written in each list. This distance calculation involves performing inverse projective transformation processing, which is the inverse of the projective transformation described above.
It is necessary to find the actual road area from the image.

The edge identification method for the image shown in FIG. 48(a) will be specifically explained. The road area 4801 is expressed by merging three areas A, B, and C. Here, the connection labels of the above-mentioned feature amount list are shown as shown in FIG. 2(b). In other words, the connection label column for area A contains area C.
is written, nothing is written in the connection label column of area B, and area A is written in the connection label column of area C. Therefore, it is determined that area A and area C are the same area that should be merged, and area B is
It is determined that this is a different area from the area formed by and area B.

Therefore, when the image is scanned horizontally along the dividing line 4802, the marked boundary points a, b, c,
d is determined as the label displacement location.

Therefore, boundary point a and boundary point S exist as points on the same area, boundary point a is given the attribute of left edge, boundary point A is given the attribute of right edge, and is described in the list of area boundary point structure. Ru. In addition, boundary point C and boundary point d exist in the same area because their label values are the same, and boundary point C is given the attribute of left edge, boundary point d is given the right edge, and the area boundary point struc- ture is described in the list.

Next, the process of step 4504 will be explained with reference to FIGS. 49 and 50.

In the image shown in FIG. 49(a), each boundary point located at the intersection of the left boundary line and each division line is at, ai+
t, and the boundary points located at the intersections of the right boundary line and each division line are bl and bl+1. Here, it is determined whether or not the first and i+1st boundary points in the y direction of the area boundary point structure exist in the same area, and if they are in the same area, they are linked before and after. That is, it is determined whether the boundary points a1 and a i+1 are in the same area, and whether the boundary points b1 and b I+1 are in the same area. In the case shown,
Since each boundary point is in the same area, in the area boundary point structure shown in FIG. 3B, each boundary point located before and after the screen is linked by a pointer indicated by a thick line.

Furthermore, if there is an internal point existing between the left edge and the right edge, the boundary of the area is traced as shown in FIG. The figure (a) shows a road area 50 to be processed.
This is an image in which a white line 5002, which is a lane marking, is drawn in the center of 01.

The label value of this white line 5002 is O. Here, when scanning the image horizontally along each dividing line, the white line 500
In the second part, the internal point E shown in FIG. 11(b) 11.
E 1i+l, E 2L E 2i+1 are obtained.

Therefore, the boundaries of the region are tracked to explore the relationship between each internal point. If this boundary is traced from the interior point Elf along the boundary line of the white line 5002, the interior point EII+1 is reached. Also, when tracing the boundary from the interior point E21, the interior point E2i+
Reach 1. In this way, adjacent internal points E11.
E 21 is the next internal point E on the division line located higher
1i+l, E2i+1, the internal point Eli located on the left side is given the attribute of internal point left edge, and the internal point E2+ located on the right side is given the attribute of internal point right edge.

Further, when tracing the boundary and reaching an adjacent internal point without being continuous with an internal point on the upper division line, each adjacent internal point is given the attribute of hole. In other words, the interior point E
Tracing the boundary from li+I, the adjacent interior point E
It reaches 2i+1. In this case, each internal point E IDI,
Give E 2i+1 the attribute of hole.

The above processing is performed along each y-coordinate in the list until this y-coordinate reaches the horizon position 5003. At this time, the distance in real space from the left edge of the interior point to the right edge of the interior point is calculated. This calculation is obtained by subtracting the X-coordinate value of the left edge point in real space from the X-coordinate value of the right edge point in real space.

Next, the process of step 4505 will be explained with reference to FIG. 51.

In the method of assigning attributes by processing each step above,
If a road branches into a Y-shape or merges, correct attributes will not be assigned. In other words, the association of each boundary point in the front-back direction may not be performed correctly. For this reason,
In such a case, in this step, the boundary is tracked and the boundary evaluation is corrected.

For example, suppose that the image shown in FIG. 51(a) is obtained through the processing of each step up to this point.

A road area 5101 in this image branches into a Y-shape, and is divided into a main road 5102 and a branch road 5103. Each dividing line (i, i+1
．． i+2. ) is image scanned, and the image is scanned from the left side of the screen to the right side at each dividing line. Through this scanning, the boundary point located at the intersection of the leftmost boundary line and each division line is given the symbol a, and the boundary point located at the intersection of the boundary line located one place to the right of the leftmost boundary line and the division line is assigned the symbol a. The boundary point located at the intersection of the boundary line two positions to the right of the leftmost boundary line and the division line is labeled C. As a result, the region boundary point struc- ture shown in FIG. 2(b) is obtained.

As can be seen from the diagram, the association of each boundary point by this region boundary point struc- ture does not match the actual road boundary, and each boundary point is not given a correct attribute.

Therefore, the boundary of the area is traced from the internal point, and if there is a boundary point where the next point is at the left or right edge of the area, this internal point and the next point are determined to be connected, The links at each of these points will be changed. In the case of the figure, the boundary of the area is traced from the internal point c i+4. When traced, the next point is a i+5, and since this point is the edge of the left area, the link attachment is changed. In other words, the attributes attached to each boundary point after a1+5 are the same as the internal point C++4.
be the attribute of By this process of changing the link attachment, the region boundary point struc- ture shown in FIG. 13(c) is obtained.

This strafture matches the boundaries of the actual road.

Figures (d) and (e) are diagrams showing the state of the area boundary before and after the link replacement process using vector representations. In other words, FIG. 4(d) shows the vector state before the links are changed, and represents the connection relationship of each boundary line by a vector based on the area boundary point structure shown in FIG. 4(b). The vectors to which attribute a is attached and the vectors to which attribute C is attached do not correspond to actual road boundaries. Figure (e) shows the vector state after the link replacement process is performed, and the connection relationship between each boundary line is expressed by a vector based on the corrected region boundary point structure in Figure (c). It is. The terminal portion of the vector to which the attribute a has been attached is modified as described above, and the attribute C has been assigned. Therefore, the boundaries of the road area represented by the vectors a, b, and c have shapes that match reality.

Figures (f) and (g) are diagrams in which the state of area boundaries when roads merge are expressed by vectors in the same way as above. FIG. 3(f) is a vector representation of the area boundary before the link is added. The vector with the attribute d blocks the entrance of the confluence path formed by the vectors with the attributes e and f. Same figure (g)
is a vector representation of the area boundary after the same linking and replacing process as described above. The starting end portion of the vector to which the attribute d has been attached is modified to the attribute f by the link reassignment processing, and the area boundary matches the actual confluence route.

Next, the process of step 4506 will be explained with reference to FIG. 52.

For example, assume the road image shown in FIG. This road image includes a road area 5201 and a road area 52.
On the left side of 01 is a road shoulder 5203 separated by a white line 5202.
There is. Boundary points are attached to the intersections between the boundary lines of each region of this road image and the lane markings, and the point sequence of the road edge and road shoulder edge shown in FIG. 4(b) is obtained. Note that points that overlap the edges of the image are excluded from the point sequence. The links of the region boundary point struc- tures in the y direction obtained by the operations in each step above are traced from the part corresponding to the bottom of the image to the top. If there are more than a predetermined number of links of the area boundary point struc- ture, an attribute of a starting point of a point sequence is attached to a location corresponding to the lower part of the image of the links of this area boundary point struc- ture. The starting point of the illustrated sequence of points is indicated by a Δ symbol.

Among the struttles with the attribute of starting point, a set of struttles whose distance in real space from the left edge to the right edge of the area boundary is equal to or greater than the vehicle width of the traveling vehicle is defined as a road edge. In the case of the same figure (b), point sequence 5204 and point sequence 5
The struture set corresponding to 205 becomes the road edge. In addition, there is a set of straftures next to the road edge, and the distance between this strafture group and the road edge is narrower than the width of the straffure group representing the road edge, and the distance between the straffure group and the other road edge is is wider than the vehicle width, and when the actual distance between struture groups is approximately 20 cm and continuous, this struture group is assumed to form a white line. The area between the strafture group and one road edge is considered to be a shoulder separated by a white line.

In the sequence of points in FIG. 5B, a white line is formed by a set of strutures corresponding to the sequence of points 5206 and 5207, and the area between this white line and the road edge 5204 is considered to be the shoulder.

By the way, the above-mentioned "means for determining the drivable range" recognizes the driving course based on the area, and is based on the premise that the road area obtained as a result of image processing is one area. According to this means, it is possible to identify the road edge of a monotonous road or a branch road. However, when an area is divided by a white line, especially into a road and a road shoulder, it is difficult to distinguish between them. This is because the means scans the window from inside the area to search for area boundaries, and therefore cannot identify the edge of the road and the edge of the road at the same time.

However, as described above, it is possible to know the boundaries of an area by scanning the label image horizontally from the bottom to the top of the image, tracking the boundaries of local areas, and finding the displacement location of the label value of each area. I can do it.

At the same time, the relationship between regions is updated in the strafture, and the boundary points of the regions are structured, so that the road region is represented in a structured manner inside the computer.

Therefore, according to this "internal representation method for driving courses with various shapes", the boundary edge coordinates of multiple areas such as road shoulders and driving lanes can be obtained, and the area boundaries can be easily detected.
The target area is not limited to a single area as in the case of ``Means for Determining Drivable Range''. Furthermore, it is also possible to identify road shoulders divided by the above-mentioned white lines.

In addition, it requires less memory capacity than conventional domain boundary methods, and evaluates the possible travel range of a driving course that is sufficient for an autonomous vehicle to drive automatically by performing sequential boundary exploration and polygon approximation. This can be obtained without any processing. Furthermore, even if the driving course is not a monotonous road, and the roads are branching or merging, the shapes of these branching roads and merging roads can be expressed uniformly, and the boundaries of the driving course can be accurately determined. It is possible to identify

As explained above, according to the "internal representation method for travel courses with various shapes", the connection relationships between the boundary points of each area are expressed in a structured strafcha using the attributes described in the list, and from this strafcha. The boundaries of the region of interest are identified. Therefore, since the number of point sequences that can be determined is large as in the conventional method, the process of approximating the boundary of the target area with a polygon and thinning out unnecessary points is no longer necessary. Further, it is no longer necessary to sequentially track all the boundary pixels of each area one by one as in the conventional method, and the target area is identified by processing only predetermined boundary pixels. Therefore, the processing time is shortened, and an area identification method suitable for autonomous driving of autonomous vehicles is provided.

〔Effect of the invention〕

As described above, according to the present invention, the connection relationship between the boundary points of each area is expressed in a structured strafture using the attributes described in the list, and the boundary of the target area is identified from this strafture. Therefore, since the number of point sequences that can be determined is large as in the conventional method, the process of approximating the boundary of the target area with a polygon and thinning out unnecessary points is no longer necessary. Also,
It is no longer necessary to sequentially track all the boundary pixels of each area one by one as in the past, and the target area is identified by processing only predetermined boundary pixels. Therefore, the processing time is shortened, and an area identification method suitable for autonomous driving of autonomous vehicles is provided.

[Brief explanation of drawings]

FIG. 1 is a flowchart showing an outline of road region structuring processing in the "internal representation method for driving courses of various shapes" according to an embodiment of the present invention, and FIG. A flowchart showing the general flow,
Figure 3 shows ISH of a color image using FROM table.
The block diagrams illustrating the algorithm of the ISH conversion process in ``conversion process'', FIGS. 4 and 5, and FIGS. 6 and 7 respectively explain processing examples of this ISH conversion process in comparison with conventional processing examples. Figure 8 is a flowchart showing the outline of color image preprocessing in [threshold setting means based on the shape of feature histogram in iterative threshold processing], and Figure 9 shows peaks and valleys in this preprocessing. FIG. 10 is a diagram for explaining the transition of table values in this preprocessing.
FIG. 11 is a flowchart showing an overview of the driving route recognition process, FIG. 12 is a flowchart showing details of the driving route extraction process in "driving course extraction means by iterative threshold processing using a template image", and FIG. The figure is a diagram for explaining each process in this road candidate region extraction process, and Figure 14 is a diagram for explaining various steps in the extraction process of road candidate regions. A diagram for explaining the outline of the processing, Figure 15 is a graph showing an example of a brightness histogram for explaining shadows and high brightness areas in this method, and Figure 16 is a configuration diagram of the labeling board of the "labeling processing device". , 17th
The figure is a general flowchart of the labeling process, No. 18.
The figure is a diagram for explaining the multivalued manual labeling method.
Figure 9 is a diagram for explaining the labeling method using runs, Figure 20 is a diagram showing a window used in image scanning for labeling processing, and Figure 21 is a diagram showing the labeling processor K.
The block diagram of the LP, FIGS. 22, 23, 24, 25, 26, and 27 are flowcharts showing window processing performed during image scanning in labeling processing, and FIG. 28 is a flowchart for labeling. A configuration diagram of the memory KLM, FIG. 29 is a diagram for explaining the process of matching the label values finally assigned, FIG. 30 is a configuration diagram of the feature extraction processor KLC, and FIG. 31 shows the one-scan labeling method. Figure 32 is an explanatory diagram showing an inverted mask used to search the label area in the ``means for merging multiple areas'';
A diagram showing an example of divided regions used to explain region boundary exploration using the inverted mask shown in the figure, FIG. 34 is a label region boundary exploration field determined by the inverted mask scanning method FIG. 35 is a diagram showing an inter-label boundary length madrisk in which the perimeter length of a long region is stored; FIG. 35 is a diagram showing a feature quantity list in which the connection relationship between each region and the feature quantities of each label region are described; FIG. 36 is an example of a label area having each feature quantity described in the feature quantity list shown in Fig. 35, and Fig. 37 shows the reference pixel position number attached near the pixel of interest in the boundary search method. Figure 38 is a diagram showing a pixel reference table used in the boundary search method, and Figure 39 is an example of a pixel area used to explain how to use the pixel reference table shown in Figure 38. FIG. 40 is a flowchart showing the processing flow of the driving course recognition system in the "means for determining the drivable range", and FIG. 41 shows the movement of the window in the captured image used in the explanation of this means. Figure, No. 42
The figure is a diagram for explaining the window and histogram values in the target area, and Figure 43 is a diagram for explaining the reversal of road edge identification that occurs when the vehicle approaches the road edge too much on a curve with a tight curvature. , FIG. 44 is a diagram for explaining a method of correcting the relationship of the point sequence group obtained in order to prevent the reversal of road edge recognition shown in FIG. 43 using Mahalanobis' general distance. 46 is a block diagram showing a schematic configuration of the entire color image processing device; FIG. 46 is a diagram for explaining the y-direction list and area boundary point struc- ture in the "method for internally representing travel courses of various shapes"; and FIG. The figure is a diagram for explaining the label displacement location and the region boundary point structure, FIG. 48 is a diagram for explaining the attributes of the region boundary, and FIG. 49 is a diagram for explaining the linking process of the region boundary point in the front and back direction. , FIG. 50 is a diagram for explaining the attributes of internal point edges and holes, FIG. 51 is a diagram for explaining the process of replacing attributes once assigned, and FIG.
FIG. 2 is a diagram for explaining detection of road edges and road shoulder edges. 101... Color camera, 102... ISH conversion unit, 103... Color processing unit, 104... Labeling hardware, 105... CPU processing unit, 148... Label image, 149... Features Weighing list 1.150...Road position coordinates, 151...Point sequence image, 4603...Boundary line of road area, 4604...Dividing line, 4605...
・Area boundary point struc- ture in the y direction,

Claims (1)

[Scope of Claims] 1. Divide the image into which each region of the image is divided and labeled by a dividing line in a certain direction, create a list of directions perpendicular to the certain direction for each dividing line, By scanning the image along the line and identifying points of change in the label values of each area, a boundary point located at the intersection of the dividing line and the boundary line of each area is found, and the list in the certain direction is divided. Create each boundary point, find the attribute of the boundary point along the dividing line in the certain direction based on the connection relationship of the label values of each area, and write the attribute in the list of the certain direction, and each area Find the attribute of the boundary point along the boundary line of the divided area in the direction orthogonal to the certain direction based on the connection relationship of the label values, write the attribute in the list in the certain direction, and write the attribute in each list in the certain direction. The concatenated length of the list in the direction orthogonal to the certain direction is determined based on the described attribute, and the point sequence of the boundary points corresponding to the list whose length is greater than or equal to a predetermined length corresponds to the boundary of the target area. A method for identifying a target area in image processing, characterized by determining that a target area is a target area and identifying a boundary of the target area. 2. If an internal point exists between the boundary edges of the target area, trace the boundary of the divided area from the internal point along a direction orthogonal to the certain direction, and determine whether the next boundary point that appears is another internal point. If the other internal point is connected to another adjacent internal point on the dividing line, it is recognized that another area is formed in the target area by each of these internal points. 2. The target area identification method according to claim 1. 3. If an internal point exists between the boundary edges of the target area, trace the boundary of the divided area from this internal point along the direction perpendicular to the certain direction, and the next boundary point that appears is the boundary edge of the target area. If it is a boundary point located in ,
3. The target area identification method according to claim 1, wherein the boundary of the determined target area is modified by connecting the boundary point and the internal point.