Linear pattern recognizing method

• US 5,181,258 A
• Filed: 03/14/1990
• Issued: 01/19/1993
• Est. Priority Date: 10/02/1987
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Komatsu Seisakusho
• Original Assignee: Kabushika Kaisha Komatsu Seisakusho
• Inventors: Nagao, Makoto, Terada, Keiji
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): Tung, Yon
• Application Number:
  US07/465,232
• Time in Patent Office: 1,042 Days
• Field of Search: 382/1, 382/8, 382/44, 382/45, 382/46, 382/48, 382/50, 382/51, 382/24, 382/29, 382/28, 382/53, 358/106, 358/107
• US Class Current: 382/206
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20068 Projection on vertical or horizontal image axis
• CPC Class Codes: G06T 2207/30256 Lane; Road marking
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

Disclosed is a linear pattern recognizing method of recognizing a linear pattern included in the image data stored in an original image memory. The memory region of the original image memory is divided into a plurality of smaller regions, and the image data of the smaller regions are utilized to obtain projection waveforms at a plurality of projection angles for each smaller region. The projection waveforms thus obtained are analyzed to detect the presence or absence, line direction (θ), smaller region. According to the results of detection, a linear segment corresponding to the linear pattern is extracted for each smaller region.

Claims

1. A linear pattern recognizing method comprising:

a first step in which the memory region of an original image memory in which image data have been stored is divided into a plurality of overlapping smaller subregions, and according to the image data in said plurality of smaller subregions, projection waveforms at a plurality of different projection angles are obtained for each of said smaller subregions;

a second step of obtaining, according to said projection waveforms obtained in said first step, the line direction of a linear pattern existing in the image data of each of said smaller subregions;

a third step of determining, according to said projection waveforms obtained for said smaller subregions in said first step, whether or not a linear pattern exist in the image data of each of said smaller subregions;

a fourth step of obtaining, according to said projection waveforms obtained for said smaller subregions in said first step, the line width of a linear pattern existing in the image data of each of said smaller subregions;

a fifth step of obtaining, according to said projection waveforms obtained for said smaller subregions in said first step, the line length of a linear of a pattern existing in the image data of each of said smaller subregions;

a sixth step of obtaining, according to said projection waveforms obtained for said smaller subregions in said second through fifth steps, extracting a linear segment corresponding to a linear pattern existing in the image data of each of said smaller subregions; and

a seventh step of combining said linear segments in said smaller subregions which have been extracted in said sixth step, to extract said linear pattern included in said image data.

2. A linear pattern recognizing method as claimed in claim 1, in said first step of which an n ×

m matrix slit is used to divide said memory region of said original image memory into a plurality of square regions.

3. A linear pattern recognizing method as claimed in claim 1, in said first step of which each projection waveform is obtained with the average value of the densities of a plurality of picture elements existing in a projection direction in each of said smaller regions as a waveform value.

4. A linear pattern recognizing method as claimed in claim 3, in said step second of which, of the projection waveforms obtained in said first step, one which has a projection angle with which a projection waveform is made maximum in peak value is selected, and the projection angle of said projection waveform thus selected is determined as the line direction of said linear pattern.

5. A linear pattern recognizing method as claimed in claim 4, in said third step of which the maximum peak value of said projection waveform in said line direction obtained in said second step is compared with a predetermined threshold value, to determine whether or not a linear pattern exists in said smaller region.

6. A linear pattern recognizing method as claimed in claim 5, in said third step of which said threshold value for determining the presence or absence of a linear pattern is set using the average density of all the image data in said original image memory.

7. A linear pattern recognizing method as claimed in claim 4, in said fourth step of which said projection waveform having the maximum peak value obtained in said second step is cut with a cutting line of a predetermined threshold value, and the distance between the two intersections of said cutting line and said projection waveform is determined as the line width of said linear pattern.

8. A linear pattern recognizingt method as claimed in claim 7, in said fifth step of which, from said image data corresponding to said projection angle providing a maximum peak value which is obtained in said second step, a part is extracted which is between two straight lines which are extended from said two intersections of said cutting line and said projection waveform which are obtained in said fourth step, with respect to said image data thus extracted a projection waveform is obtained in a direction perpendicular to said line direction, and compared with a predetermined threshold value, and the length of the part of said projection waveform which is larger than said threshold value is determined as the line length of said linear pattern.

9. A linear pattern recognizing method as claimed in claim 4, in said fourth step of which said projection waveform having a maximum peak value which is obtained in said second step is processed with a plurality of first threshold values, standard deviation are obtained for a plurality of combination waveforms which are combination of projection waveforms smaller than said first threshold values and straight lines corresponding to said first threshold values and compared with a second threshold value, so that, of said combination waveforms with which said standard deviations are smaller than said second threshold value, one whose first threshold value is largest is selected, and the distance between the two intersections of a straight line corresponding to said first threshold value of said combination waveform and said projection waveform is determined as the line width of said linear pattern.

10. A linear pattern recognizing method as claimed in claim 9, in said fourth step of which a plurality of values which are provided by repeatedly subtracting a predetermined value from the peak value of said projection waveform are employed sa said first threshold values.

11. A linear pattern recognizing method as claimed in claim 4, in said fourth step of which said projection waveform having a maximum peak value which is obtained in said second step is processed with a plurality of first threshold values, average values are obtained for a plurality of combination waveforms which are combination of projection waveforms smaller than said first threshold values and straight lines corresponding to said first threshold values and compared with a second threshold value, so that, of said combination waveforms with which said average values are smaller than said second threshold value, one whose first threshold value is largest is selected, and the distance between the two intersections of a straight line corresponding to said first threshold value of said combination waveform and said projection waveform is determined as the line width of said linear pattern.

12. A linear pattern recognizing method as claimed in claim 11, in said fourth step of which a plurality of values which are provided by repeatedly subtracting a predetermined value from the peak value of said projection waveform are employed as said first threshold values.

13. A linear pattern recognizing method as claimed in claim 1, which said linear segments extracted in said sixth step are rectangular.

14. A linear pattern recognizing method as claimed in claim 1, in which said linear segments extracted in said sixth step are linear.

15. A linear pattern recognizing method comprising:

a first step in which the memory region of an original image memory in which image data have been stored is divided into a plurality of smaller regions, and according to the image data in said plurality of regions, projection waveforms at a plurality of different projection angles and standard deviations for said projection waveforms are obtained for each of said smaller regions;

a second step of obtaining, according to said standard deviations of said projection waveforms obtained in said first step, the line direction of a linear pattern existing in the image data of each of said smaller regions;

a third step of determining, according to said standard deviations of said projection waveforms obtained in said first step, whether or not a linear pattern exists in the image data of each of said smaller regions;

a fourth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line width of a linear pattern existing in the image data of each of said smaller regions;

a fifth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line length of a linear pattern existing in the image data of each of said smaller regions; and

a sixth step of extracting, according to the results of operations in said second through fifth steps, extracting a linear segment corresponding to a linear pattern existing in the image data of each of said smaller regions.

16. A linear pattern recognizing method as claimed in claim 15, in said second step of which said plurality of standard deviations at said plurality of projection angles which are obtained in said first step are subjected to comparison, and the projection angle providing the largest said standard deviation is determined as the line direction of said linear pattern.

17. A linear pattern recognizing method as claimed in claim 16, in said third step of which the standard deviation of said projection waveform having maximum in standard deviation which is obtained in said second step is compared with a predetermined threshold value to determine whether or not a linear pattern exists in said smaller region.

18. A linear pattern recognizing method as claimed in claim 17, in said third step of which said threshold value for determining the presence or absence of a linear pattern is set using the average value of said standard deviations of said projection waveforms which are obtained for all the smaller regions in said original image memory.

19. A linear pattern recognizing method as claimed in claim 15, in which said second step comprises:

a first process of obtaining, according to the standard deviations of projection waveforms in two-dimensional directions provided when one of said projection angles obtained in said first step in zero, an average value of standard deviations in two-dimensional directions in said original image memory;

a second process in which said average value of said standard deviations in two-dimensional directions which is obtained in said first process is distributed in proportion to said projection angles;

a third process in which said standard deviations of said projection waveforms at said projection angles which are obtained in said first step are normalized with the values calculated in said second process; and

a fourth process in which said standard deviations at said projection angles which have been normalized in said third process are subjected to comparison, so that, of said projection angles, one which provides a maximum normalization is determined as the line direction of said linear pattern.

20. A linear pattern recognizing method as claimed in claim 19, in said third step of which said normalization obtained in said third process is compared with a predetermined value to determined whether or not a linear pattern exists therein.

21. A linear pattern recognizing method comprising:

a first step in which the memory region of an original image memory in which image data have been stored is divided into a plurality of smaller regions, and according to the image data in said plurality of regions, projection waveforms at a plurality of different projection angles are obtained for each of said smaller regions;

a second step of obtaining, according to said projection waveforms obtained in said first step, the line direction of a linear pattern existing in the image data of each of said smaller regions;

a third step of determining, according to said projection waveforms obtained for said smaller regions in said first step, whether or not a linear pattern exist in the image data of each of said smaller regions;

a fourth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line width of a linear pattern existing in the image data of each of said smaller regions;

a fifth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line length of a linear pattern existing in the image data of each of said smaller regions;

a sixth step of extracting, according to the results of operations in said second through fifth steps, extracting a linear segment corresponding to a linear pattern existing in the image data of each of said smaller regions;

a seventh step of determining, according to the result of operation in said third step, the positional relationship of said smaller region having a linear pattern, and determining, according to said positional relationship thus determined, an interpolation position on said original image memory for reprojection;

an eighth step of obtaining projection waveforms at a plurality of different projection angles again at each interpolation position on said original image memory which is determined in said seventh step;

a ninth step of operating, according to said projection waveforms obtained in said eighth step, the presence or absence, line direction, line width and line length of a linear pattern in said interpolation region; and

a tenth step of extracting, according to the results of operation in said ninth step, a linear segment corresponding to a linear pattern which exists in each interpolation region, and combining said linear segment thus extracted with said line segment obtained in said sixth step.

22. A linear pattern recognizing method comprising:

a first step in which the memory region of an original image memory in which image data have been stored is divided into a plurality of smaller regions, and according to the image data in said plurality of regions, projection waveforms at a plurality of different projection angles are obtained for each of said smaller regions;

a second step of obtaining, according to said projection waveforms obtained in said first step, the line direction of a linear pattern existing in the image data of each of said smaller regions;

a third step of determining, according to said projection waveforms obtained for said smaller regions in said first step, whether or not a linear pattern exist in the image data of each of said smaller regions;

a fourth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line width of a linear pattern existing in the image data of each of said smaller regions;

a fifth step of obtaining, according to said projection waveforms obtained for said smaller regions in said first step, the line length of a linear pattern existing in the image data of each of said smaller regions;

a sixth step of extracting, according to the results of operations in said second through fifth steps, extracting a linear segment corresponding to a linear pattern existing in the image data of each of said smaller regions;

a seventh step of obtaining for each smaller region the standard deviations of said projection waveforms in said line direction obtained in said second step and in a direction perpendicular to said line direction, and determining from said standard deviations whether or not a branch exists in each smaller region;

an eighth step of further dividing each of the smaller regions which are determined to have branches in said seventh step into a plurality of much smaller regions, and obtaining projection waveforms at a plurality of different projection angles again for each of said much smaller regions;

a ninth step of determining, according to said projection waveforms obtained for said much smaller regions in said eight step, the presence or absence, line direction, line width and line length of a linear pattern; and

a tenth step of extracting, according to the results of operation in said ninth step, linear segments corresponding to branches existing in said regions.

23. A linear pattern recognizing method as claimed in claim 22, in said seventh step of which, when the larger of said standard deviations in said two directions is larger in value, and the ratio of said standard deviations in said two directions is substantially equal to one, the existence of a branch in said smaller region is determined.

24. A linear pattern recognizing method as claimed in claim 22, in said eighth step of which each smaller region is divided into said plurality of much smaller overlapping subregions.