JPH0247786B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Description of the field to which the invention pertains The present invention relates to a feature extraction processing method, and particularly to a feature extraction processing method for extracting features effective for identifying character patterns with complex structures such as kanji. be.

(2) Explanation of conventional technology Optical character readers (OCR) that read handwritten katakana and numbers have been available for some time, but these devices cannot be used to recognize patterns with many character types and complex structures, such as handwritten kanji. This is difficult to apply due to the amount of information contained in the features. In addition, several methods have been proposed that aim to recognize handwritten kanji, but these methods feature information such as the slope of character lines on the pattern, and then superimpose the characterized pattern with a standard pattern to recognize input characters. This method is effective for classifying handwritten kanji, but is insufficient for identification.

(3) Purpose of the Invention The present invention is characterized by using a stroke as a unit of information and accumulating information about the surrounding strokes for each stroke.The purpose of the present invention is to not only classify handwritten kanji but also to identify them. The object of the present invention is to provide a feature extraction device that performs the following. The drawings will be explained in detail below.

(4) Description of structure and operation of the invention FIG. 1 shows an example of the structure of a recognition system including the present invention, in which 1 is a scanning section, 2 is a pattern memory section, 3 is a stroke extraction section, and 4 is a stroke coordinate memory. Part, 5
6 is a feature extraction unit, 6 is an identification unit, and 7 is a control unit.

First, the scanning section 1 scans and photoelectrically converts characters on a document and sends a binary signal to the pattern memory section 2. The pattern memory section 2 is a RAM that temporarily stores the binary signal from the scanning section 1. The stroke extraction unit 3 extracts character line strokes from the binary pattern for one character stored in the pattern memory unit 2, calculates the (x, y) coordinates of both ends for each stroke, and stores them in the stroke coordinate memory unit 4. do. Next, the feature extraction unit 5, which is the object of the present invention, extracts the positions from each stroke in each direction (for simplicity, The inclinations of existing strokes (sometimes abbreviated as "in the direction") are determined in descending order of the inclinations, one or more stroke inclination series are determined, and the obtained stroke inclination series is sent to the identification unit 6. The identification unit 6 determines the category name of the input character based on this and outputs it. All of these processes are controlled by timing signals given by the control section 7.

FIG. 2 shows an embodiment of the feature extracting section 5 shown in FIG. 1, in which 51 is an inclination extraction section, 52 is an inclination table section, 53 is a positional relationship extraction section, 54 is a positional relationship matrix section, and 55 is a stroke inclination. Series extraction part, 5
6 is a stroke table section.

These are controlled and operated by timing signals given from the control section 7. First, the inclination extraction section 51 reads the contents of the stroke coordinate memory section 4, calculates the inclination, and stores it in the inclination table section 52. The strokes treated here are basically straight lines, and when there is a bend, they are divided into straight lines, and for this reason they have a different meaning from the general term stroke (single stroke).

Figure 3 shows an example of a pattern divided into strokes, where 30 marked with "・" is a feature point, 31 to
40 indicates the first to tenth strokes.

FIG. 4 shows an embodiment of the stroke coordinate memory unit 4, where the total number of strokes N appearing at address '0' and address 'a' (a=1, 2,...N).
To do this, match the address to the stroke number,
The coordinates (x ^s _a , y ^s _a ) and (x ^E _a , y ^E _a ) of the starting end and ending end are stored.

As an example of the method for extracting the slope in the slope extracting section 51, a case will be shown in which the slope is converted into eight types of slope codes from 0 to 7 (in 22.5° increments) shown in FIG.

The average slope θ of any stroke (number i) is θ=tan ^-1 (△y/△x); (△x≠0) π/2; (△x=0, △y>0) −π/2 ; (△x=0, △y<0) No value; (△x=△y=0) (However, △x=x ^E _i −x ^S _i , △y=y ^E _i −y ^S _i −π /2
≦θ≦π/2) Therefore, the slope code can be obtained from the values of △x and △y.

FIG. 6 is an embodiment of the tilt table section 52, and shows the contents of the tilt table section obtained from the pattern of FIG. 3. The total number of strokes is stored at address '0', and the slope code corresponding to each stroke number is stored at and after address '1'. For example, the 6th
In the figure, the inclination code "0" of the eighth stroke 38 in FIG. 3 is stored at address '8'.

The positional relationship extraction unit 53 determines the relative positional relationship (vertical relationship, horizontal relationship) between any two strokes based on the coordinates of both ends of each stroke written in the stroke coordinate memory unit 4, and extracts the result. is written in the positional relationship matrix section 54.

An example of a method for checking the vertical relationship between strokes in the process performed by the positional relationship extraction unit 53 is as follows: First, in order for any two strokes to have a vertical relationship, they must have a certain overlap in the left and right direction. is necessary. Figure 7 A to D are any 2
This diagram schematically shows the change in positional relationship when the strokes of a book overlap in the left and right direction.
indicates the i-th stroke, and 532 indicates the j-th stroke. In the cases of C and D in FIG. 7, it can be considered that there is an unconditional overlap, but in the cases of A and B in FIG. 7, the following conditions must be satisfied.

(Condition) △≧α or △≧β・min (l _i , l _j ) However, (α and β are predetermined thresholds △ is the overlapping length of two strokes, l _i and l _j are the strokes i and j, respectively) (means the length in the x direction of .) Next, an example of a method for determining the vertical relationship of a set of strokes that overlap in the horizontal direction will be described. The vertical relationship can be determined by the magnitude of the y-coordinates at both ends of the overlapping portion of the two strokes. FIG. 8 is an explanatory diagram of a method for determining the vertical relationship between a set of strokes that overlap on the left and right, where 531 indicates the i-th stroke and 532 indicates the j-th stroke. In the figure, when the following condition is satisfied, the j-th stroke 532 is determined to be below the i-th stroke 531.

(Condition) (y ^m _i > y ^m _j and y ⁿ _i ≧ y ⁿ _j or y ^m _i = y ^m _j and y ⁿ _i > y ⁿ _j ) Also, when the following condition is satisfied, the jth stroke 532 is determined to be above the i-th stroke 531.

(Condition) (y ^m _i < y ^m _j and y ⁿ _i ≦y ⁿ _j or y ^m _i = y ^m _j and y ⁿ _i < y ⁿ _j ) The vertical relationship between arbitrary two strokes i and j is
Although it can be determined as described above, the left-right relationship can also be determined by replacing the x-direction and the y-direction with respect to the method described above. The vertical and horizontal relationships between arbitrary two strokes i and j obtained in this way are recorded in addresses i and j of the positional relationship matrix section 54. The positional relationship matrix unit 54 is composed of a RAM, and expresses the positional relationship of the stroke j viewed from the stroke i using a four-sided matrix that corresponds to "top", "bottom", "left", and "right". 9 and 10 show examples of matrices corresponding to the "upper" and "lower" portions of the positional relationship matrix section 54 with respect to the pattern shown in FIG. 3. According to this embodiment, FIG.
2 from FIG. 9 upward from the stroke 31 of
The third stroke 32, 33 is downward the tenth stroke.
The figure shows that there are fourth to tenth strokes 34 to 40.

The stroke inclination series extraction section 55 calculates the number series of existing strokes when viewed from each stroke in the upper, lower, left, and right directions based on the contents of the positional relationship matrix section 54, and further extracts the number series of existing strokes from the inclination table section. 52, the number series is converted into a slope series, and the number series is output to the stroke table section 56. Generally, there are a plurality of stroke series seen in each direction from a given stroke. For example, in the pattern example shown in FIG.
Looking down from the top, the fourth stroke 34 is the first
Series, 5th, 6th, 7th strokes 35, 3
6, 37 are the second series, the eighth stroke 38 is the third series, the ninth stroke 39 is the fourth series, the 10th stroke
The stroke 40 is the fifth series, and there are five series.

Next, a method for obtaining these will be explained. Processing is performed in the "up", "down", "left", and "right" directions, but since the processing in each direction is performed using the same procedure, when determining the strokes that exist in the "down" direction, The explanation will be limited to.

First, when an arbitrary stroke i is a stroke of interest, the stroke number below the stroke of interest can be found from the matrix in the "down" direction of the positional relationship matrix section 54. 10th
If the i-th row of the matrix in the "down" direction shown in the figure is expressed as M ^D _i = (K ₁ , K ₂ , ..., K _j , ...), if any stroke j is a stroke If it is below i, then K _j =1. next,
In order for the stroke j to be immediately below the stroke i of interest, it is necessary that no other stroke exists between the stroke i of interest and the stroke j, and therefore the following condition must be satisfied. When the i-th row of the matrix in the upward direction shown in Figure 9 is expressed as M ^U _i = (K ₁ ′, K ₂ ′, ..., K _j ′, ...), the condition M ^D If _i ·D ^U _j =(0, 0, 0, . . . ) is satisfied, stroke j exists immediately below stroke i.

By sequentially replacing the stroke j obtained in this manner with the stroke of interest i, the sequence of strokes can be determined.

This will be explained by taking as an example the case where the first stroke 31 shown in FIG. 3 is the stroke of interest. First, the stroke number j below the first stroke 31 is one line of i= ₁ in ^FIG .
1), j=4, 5, 6, 7, 8, 9, 10. Among these, in the case of j=4, 5, 8, 9, 10, M ^D ₁・M ^U _j =(0, 0, 0, 0, 0, 0, 0, 0,
0, 0), each of which is a stroke immediately below stroke 31.

Next, these strokes (j=4, 5, 8, 9,
10) as the stroke of interest and further examine the existence of strokes below it, M ^D _j = (0, 0, 0, 0, 0, 0, 0, 0, 0, except for the case where j = 5). ,
0), which means there is no further stroke below.

On the other hand, when j=5, M ^D ₅ = (0, 0, 0, 0, 0, 1, 1, 0, 0, 0)≠
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), so there are strokes of j=6 and 7 in this downward direction. Among these, when examining the case of j=6, M ^D ₅ · M ^U ₆ = (0, 0, 0, 0, 0, 0, 0, 0,
0, 0), and it can be seen that stroke 36 (j=6) is immediately below stroke 35 (j=5).

Through the processing described above, the following five stroke number series are obtained in the "downward" direction of the stroke 31.

(Series 1) 1-4 (〃 2) 1-5-6-7 (〃 3) 1-8 (Series 4) 1-9 (〃 5) 1-10 Next, convert these stroke number series into stroke numbers. The method of converting into a slope series will be explained.
The inclination of each stroke is stored in the inclination table section 52 shown in FIG. Therefore, the tilt table section 52 uses each stroke number as an address.
It is sufficient to read out the contents of and write them to the corresponding address in the stroke table section 56.

FIG. 11 schematically shows an embodiment of the stroke table section 56 corresponding to the pattern shown in FIG.
is the slope series of strokes above the stroke of interest, 563 is the slope series of strokes below, 564 is the slope series of strokes to the left,
565 is a slope series of strokes on the right side.

(5) Explanation of effects As explained above, according to this feature extraction processing method, information on the surrounding strokes is accumulated for any given stroke of interest using a stroke as a unit. Since it is possible to obtain multiple inclination series for a stroke in order of proximity to the stroke of interest,
It is possible to describe the complex structure of handwritten kanji, and since relative position information is used, stable characteristics can be obtained even with changes in the position of input characters.

[Brief explanation of the drawing]

Fig. 1 shows an example configuration of a recognition system including the present invention, Fig. 2 shows an example of a feature extraction section, Fig. 3 shows an example of a pattern divided into strokes, and Fig. 4 shows an example of a stroke coordinate memory section. , FIG. 5 is an example of a tilt code, FIG. 6 is an example of a tilt table section, and FIG. 7 is an example of a tilt code.
8 are explanatory diagrams showing the positional relationship between two strokes, FIGS. 9 and 10 are examples of matrices corresponding to "upper" and "lower" of the positional relationship matrix section, and FIG. 11 This is an example of the stroke table section. 1...Scanning section, 2...Pattern memory section, 3...
Stroke extraction unit, 4... Stroke coordinate memory unit, 5... Feature extraction unit, 6... Identification unit, 7... Control unit, 30... Feature points, 31-40... 1st to 1st
10 strokes, 51... slope extraction section, 52...
Tilt table section, 53...Positional relationship extraction section, 54
. . . Positional relationship matrix section, 55 . . . Stroke inclination series extraction section, 56 . . . Stroke table section.

Claims (1)

[Claims] 1. A pattern recognition method that processes a binary character pattern consisting of black and white to extract strokes and identifies a category name to which an input pattern belongs based on stroke information, A means for determining the inclination of a stroke, a means for determining a relative positional relationship between any two strokes from existing position information of the two strokes, and a means for determining the relative positional relationship of any two strokes based on the relative positional relationship, with the arbitrary stroke being the stroke of interest. A means is provided for determining the strokes existing at predetermined directional positions of the stroke of interest in order of proximity to the stroke of interest, and obtaining a slope series of the strokes existing at each directional position, extracting information on the strokes, and determining the stroke of interest. A feature extraction processing method characterized in that the slope series of the strokes for each stroke is accumulated in the stroke of interest. 2. A plurality of inclination series of the strokes are extracted for each predetermined directional position of each stroke of interest.
Feature extraction processing method described in section.