JPS6015994B2 - Pattern feature extraction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a feature extraction method for an optical character recognition device (hereinafter referred to as OCR), and particularly to a method for extracting a feature that distinguishes between roundness and refraction of a loop portion of a pattern.

When recognizing characters written on paper, it is generally scanned optically and quantized into a binary pattern such that the character part is "1" and the white part of the paper is "0", and separated into individual characters. After that, it undergoes preprocessing such as noise removal and thinning, and then passes through a feature extraction section and a determination section.

The feature extraction section usually extracts line end points, branch points, bending points, depressions, convexities, etc. as features, and the judgment section judges input characters based on the presence or absence or quantity of these features. There is. Regarding this feature extraction, various feature extraction methods have been proposed and put into practical use.

However, when the range of characters to be read is expanded to include alphabets, katakana, symbols, etc. in addition to numbers, the number of similar patterns in different categories further increases. In order to distinguish patterns that are similar to each other, it becomes necessary to extract special features for distinguishing only between these similar patterns. To do this, we first extract relatively effective features (referred to as basic features in the following text) for identifying the entire character to be discussed, and then determine candidate categories based on these extracted basic features. Next, only for this candidate category, according to a list of multiple features described for each category (hereinafter referred to as a feature list), features are extracted from the basic features or input patterns to create one candidate category that satisfies the feature list. A method called nimaru came to be adopted. An example of the distinction between ○, D, and V is difficult to distinguish without using such means. In order to read the alphabet D as shown in FIG. 1, it is a prerequisite that three patterns as shown in FIG. 2 can be distinguished. Fig. 2 1 shows a handwritten 0 (zero) pattern with a protruding stroke in the upper left, and Fig. 2 2 shows a handwritten D (day) pattern with no protruding stroke in the lower left.
FIG. 2 and 3 show a case where there is no protrusion of the upper right stroke in a handwritten V. In OCR, which only reads numbers, there was no problem even if these three types were recognized as the number 0, but in OCR, which reads letters and numbers, it is necessary to accurately distinguish between them. Once it becomes possible to distinguish between these patterns, the input pattern shown in Figure 1 has the basic characteristics of a downward shortening and stroke from the end point to the branch point in the upper left corner, so it becomes 3 as shown in Figure 2. Candidate categories ○, D, and V are determined.
Once the input pattern has been classified into these three candidate categories, the lack of roundness on the left side of the input pattern indicates that it is not the character shape shown in Figure 2, 1, and the presence of roundness on the right side indicates that it is not the character shape of Figure 2, Figure 3. I understand that. Therefore, the pattern in FIG. 1 can be seen as a letter D in FIG. 2. However, detecting whether there is a rounded refraction in the loop portion of a subordinate character pattern was more difficult than expected, and there was no stable method for determining this. SUMMARY OF THE INVENTION An object of the present invention is to provide a method for extracting features that are effective for distinguishing character patterns whose differences are the roundness and refraction of loops.

The present invention provides a pattern memory that stores a binary pattern for one character, and a basic feature that extracts basic features such as special points such as stroke end points and denominator points, and stroke direction from the binary pattern of this pattern memory. an extraction means, a basic feature register for storing the basic features extracted by the basic feature extraction means, a candidate determination dictionary for storing a large number of standard patterns having a similar format to the basic features, and a combination of the basic features and the basic feature register. Candidate determining means for extracting a character name of a matching standard pattern as a candidate character name by comparing it with the basic characteristics of a stored input character, and a candidate character for sequentially storing the candidate character names obtained by the candidate determining means. name register, a judgment dictionary that stores one or more feature lists necessary for recognizing each character; a feature list for the candidate character name stored in the candidate character name register is extracted from the judgment dictionary; from the input pattern of the pattern memory or the basic features stored in the basic feature register, and when all the features in the feature list are extracted, the candidate character name is extracted from the determining means for determining the candidate character name as a character of the input pattern. The determination means, which is the last component of the OCR, determines whether one feature in the feature list extracted from the determination dictionary has a roundness or corner in a designated direction from a designated branch point. , the pattern memory is scanned in the first direction from the row coordinate value of the designated branch point, and second and third patterns are scanned in a direction orthogonal to the first direction and in mutually different directions. The scanning lines that do not intersect with the input pattern are read out in the respective directions, and the scanning lines before scanning are detected as the first line coordinate values and the second line coordinate values in the second and third directions. means, scanning the interval indicated by the detected first row coordinate value and second row coordinate value from the end of the column of the pattern memory in the second direction or the third direction; detecting a coordinate value of a scanning line that intersects the discussion input pattern only once for the first time in a specified direction of the direction of , or a direction opposite to the first direction; A first feature value extracting means for detecting a row coordinate value at an end of the input pattern by scanning in the third direction from the position of the first row coordinate value or from the position of the second row coordinate value according to designation. and, by designation, the value of the difference between the row coordinate value of the branch point and the first row coordinate value or the second row coordinate value, the row coordinate value obtained by the first feature value extraction means, and the first row coordinate value. As one feature extraction means, a means for verifying whether the value of the ratio between the row coordinate value of It was designed to include. According to the present invention, when there is a line descending to the right from the end point T to the branch point B in the input pattern as shown in FIG. 1, after three candidate characters are determined as shown in FIG. assigned to one of the

Figure 2 shows branch point B, and branch B from the lower end of the lower loop.
It is assigned when the ratio b/a of the height b from the bottom end of the loop to the bottom end of the pattern in the technique left column of the loop is 1/3 or more, and The b/a on the right side is assigned when it is below 2/tsuchi, and in FIG. 2, the b/a on the right side is assigned when it is 4'5 or more.

FIG. 3 is a block diagram showing one embodiment of the present invention.

Reference numeral 10 denotes a pattern memory for storing a pattern for one character, in which pattern information that has been subjected to processing such as OCR light crab conversion and cutting is stored.

Basic feature extraction means 1 1 extracts basic features such as total points, branching points, inflection points, stroke direction, etc. from the character pattern stored in the pattern memory 10, and basic feature register 1
Store in 2. Regarding the method of feature extraction, for example, see Section 4.
From the character pattern shown in Figure 1, the stroke directions (indicated by arrows) indicated by numbers such as total point T, branching point B, bending point K, 2, 5, 5, etc. are shown in Figure 4 and 2. They are detected and made into a symbol string such as sign spots IB in the order of detection.

Figure 4 3 shows the direction of the stroke and the numbers 0, 1, 2...
... shows the correspondence of 7. Since this basic feature is a feature that can be applied to all characters, there is almost no need for it in subsequent processing. Therefore, the basic feature extraction means 11 extracts uniform features for all input characters. When the basic features are extracted, the control is passed to the candidate determining means 14 to extract the basic features stored in the basic feature register 12 and the candidate determining dictionary 13.
The pattern is compared with the standard pattern stored in the . This standard pattern has the form, for example, A: 12 rounds (4 songs) 4 spots 2 $ (01K) 01B. In this format, the first A indicates the letter name of this standard pattern, K, B, numbers (0-7
) indicates an inflection point, a branch point, and the direction of a stroke in the same way as in Fig. It shows.

Also, the part inside parentheses indicates a good stroke whether or not it is present. Since a standard pattern of this format includes the basic feature 2K5B3BIB as shown in FIG. 4, the character name A of this standard pattern becomes a candidate character.

The candidate determination dictionary 13 includes one or more standard patterns for each character to be recognized. The candidate determining means 14 performs a comparison with the standard pattern in the candidate determining dictionary 13, and the character names of the standard pattern containing the basic features in the register 12 are stored in the candidate character name register 15. One or more candidate characters may be set in this register 15, or there may be none at all. Once the candidate character name based on the basic characteristics is determined, control is passed to the determining means 17.

If there is no candidate character name stored in the candidate character register 15, the determining means 17 outputs a signal indicating that it cannot be taken down to the output register 19, but if there is one or more candidate characters, the character name is output to the output register 19. The contents of the key determination dictionary 18 are indexed, the necessary pattern memory 10 and the basic feature register 12 are extracted according to the feature list read therefrom, and character names that satisfy the feature list are output as input character names to the register. Output to 19. Each entry in the judgment dictionary 18 expresses the type and parameter of sub-features, and when all of a plurality of features need to be satisfied, they are listed together.

For example, in the feature list for the katakana character "a" as shown in FIG. 4, the features x, 8, T3, and 3 necessary for distinguishing the character from "ma" are specified.

This is an example using the feature X, and shows that if the x coordinate of the branch point B is 3 bits or more to the right of the x coordinate of the total point t, one feature for A is satisfied. One or more such features are prepared for each character in a feature list, and if there is only one feature, it can be judged if it is satisfied, but if there are multiple features, the feature list is prepared. This means that all characteristics are satisfied. In this case, the relationship between the X coordinates between the basic features is used as the feature 0, but a feature extraction method is required that re-extracts features that are not extracted as the basic features from the input pattern.

One of them is the present application. FIG. 5 is a block diagram showing a specific embodiment of the present application.

The determination means 17 includes several feature extraction means 40, 50, and 60 under the control of the determination control circuit 20, and the present application refers to one means 40 among these plurality of feature extraction means. It shows. Note that some parts common to FIG. 3 are omitted from illustration. When the feature list corresponding to the candidate character set in the candidate character register 15 is decoded by the determination control circuit 201, and as a result, the feature R, that is, R, B, d, t'r is selected as one of the feature lists. , the coordinate value of the branch point & as a parameter is stored in the register 21, the parameter value d indicating whether the branch point is to the right or left is stored in the register 28, and the threshold parameter value t for comparison with the ratio detected from the input pattern is stored in the register 21. In register 32,
Furthermore, a parameter value r indicating the magnitude relationship is set in the register 33.

The coordinate values of branch points are stored in the section for storing branch points of the basic feature register 2 in the order in which they are detected by the basic feature extraction means 11, and when a branch point number is given, the coordinate values of the specified branch point are stored. The coordinate values are read and the X and Y coordinate values are set in registers 27 and 22, respectively. The upward detection means 23 is the Y of the branch point set in the register 22.
After the rows of the pattern located above the coordinate values are sequentially retrieved from the pattern memory 10, the row coordinate value of one row before the row that does not intersect with the input pattern is detected as the upper row, and its coordinate value Yp is set in the register 24.

The descending line detection means 25 takes out from the pattern memory 10 the line of the pattern located below the Y coordinate value set in the register 22, and first detects the line coordinate value of the previous line of the line that does not intersect with "1" of the input pattern. It is detected as a lower row and the row coordinate value Yq of the lower row is set in the register 26. The cross-column detection means 29 stores the pattern memory 10 between the upper row coordinate value set in the register 24 of the input pattern and the lower row coordinate value set in the register 26, and detects a branch point, which is a basic feature set in the register 27. While descending from the X coordinate value in the vertical direction, the proposal is advanced in the direction specified by the direction parameter binary value a set in the register 28, and the first value that intersects "1" in the input pattern only once is determined. is detected, and the coordinate value Yc in the vertical direction intersecting the input pattern at the position of the detected columnar value is detected and set in the register 30. Verification means 31, register 24, register 26
and the Y coordinates Yp, Y set in each of the registers 30
Using q and Yc, to -hC-Yp! a・Nq-Yp
l is calculated, and this b/a is the value t set in register 32.
If the condition of the magnitude-related parameter value r set in the register 33 is satisfied, set it to "1"; otherwise, set it to ``0''.
” is output to the judgment control circuit 20.

In addition, in FIG. 5, the x coordinate is set in register 22, and register 2
While vertically scanning the means 23 to the left of the X coordinate of the register 22 so as to set the Y coordinate in 7 and the upward or downward direction in the register 28, first set the column coordinate value of the column one column before the column that does not intersect with the input pattern. The means 24 is changed to a means for detecting as the left column Xp, and the means 24 is changed to a means for vertically scanning to the right from the X coordinate of the register 22 and detecting as the coordinate value Xq of the column one column before the column that does not intersect with the input pattern first, Furthermore, while horizontally scanning the means 29 in the direction (up or down) set in the register 28 within the area narrowed by the left column Xp and the right milk yield q, the row coordinate value that first intersects the input pattern once is detected. Then, at the position of the detected row coordinate value, the coordinate Xc in the horizontal direction intersecting the input pattern is detected and set in the register 30'. By changing in this way, the verification means 31 calculates b/a=IXc-Xpl/IXq-Xp
The function is changed to calculate l and verify whether this value satisfies the conditions of the value t set in the register 32 and the parameter value Y set in the register 33 in a magnitude relationship.

That is, by making this change, it is possible to provide a function for detecting the roundness or corner of the upper end, which is effective in distinguishing between numbers 9 and 4 as shown in FIG.

Furthermore, in the above description, the input pattern is a scanned binary pattern, but it is of great significance to replace it with a thinned pattern in order to eliminate the influence of thickness.

[Brief explanation of drawings]

FIG. 1 shows one of the recognized input characters, FIGS. 2 and 6 show examples of patterns that can be distinguished by applying the present invention, and FIGS. 3 and 5 show examples of patterns that can be distinguished by applying the present invention. FIG. 4, a block diagram showing the embodiment, is a diagram explaining the basic features. In the figure, 10 is a pattern memory, 11 is a basic feature extraction means, 12 is a basic feature register, 13 is a dictionary for candidate determination, 14 is a candidate determination means, 15 is a candidate character register, 17
is a judgment means, 18 is a judgment dictionary, 19 is an output register,
A two-way determination control circuit, 23 and 25 are upper row and lower row detection means, 29 is a cross column detection means, and 31 is a verification means. O figure O 2 figure O 3 figure O 4 figure O 5 figure Juice 6 figure

Claims (1)

[Claims] 1 Basic features such as end points, branching points, and stroke direction are extracted from the input pattern for one character, and the conditions are described as the conditions that candidate character names should have by comparing them with multiple standard patterns using the basic features. In a character recognition device that extracts a plurality of features from basic features and an input pattern and determines a candidate character name that satisfies the conditions of the plurality of features as an input character name, While scanning the memory in the first direction from the row coordinate value of the designated branch point, the memory is read in second and third row directions that are perpendicular to the first direction and different from each other, and for the first time, the input pattern is read out. Detecting the row coordinate values one scan before the non-intersecting scanning rows as the first row coordinate values and the second row coordinate values in the second direction and the third direction, and detecting the two detected rows. Scanning the interval indicated by the coordinate values from the end of the column of the memory in the row direction in the second direction or the third direction; Detects the column coordinate value of a scanning line that intersects the input pattern once for the first time in the specified column direction, and scans in the same direction as the second or third direction specified on the column coordinate value. The value of the difference between the row coordinate value of the first detected input pattern and the detected first and second row coordinate values corresponding to the specified second and third directions, and the row of the branch point. A value that is a ratio of the difference value between the coordinate value and the first and second row coordinate values corresponding to the same second and third directions as specified above is detected as a recognition feature of the input pattern. A feature extraction method for patterns characterized by