JPS6022792B2 - 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 features that distinguish between roundness and linearity of a pattern.

When recognizing characters written on paper, it is generally optically scanned and quantized into a binary pattern such that the text part is "1" and the white part of the paper is "0", and then separated into individual characters. After that, it goes through pre-processing such as noise removal and thinning, and then passes through a feature extraction section and a determination section. The feature extraction section extracts end points, branching points, bending points, depressions, convexities, etc. of normal lines as features, and the judgment section judges input characters based on the presence or absence or quantity of these features. . 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 these similar patterns. To do this, we first extract relatively effective features (hereinafter referred to as basic features) for grasping the entire character to be discussed, determine candidate characters based on the extracted basic features, and then select only the candidate characters for this candidate character. A method is adopted in which features are extracted from basic features or input patterns according to a list of multiple features described for each character (hereinafter referred to as feature list), and candidate characters that satisfy the feature list are grouped into one. It started to be done. Examples of cases where it is difficult to distinguish without using such means include ○, D, and B.

In order to read the alphabetic character D (D) as shown in FIG. 1, it is a prerequisite that three patterns as shown in FIG. 2 can be distinguished. Figure 2 1 is the number 0 (zero), 2 is the alphabetic character D (di), and 3 is the katakana o. With OCR that only reads numbers, there is no problem in recognizing the number 0 in any of these three forms, but with OCR that reads numbers, alphabets, and katakana, it is necessary to accurately distinguish between these. Once it becomes possible to distinguish between these patterns, the input pattern shown in Figure 1 is considered to be one of the three patterns shown in Figure 2, since the basic feature is that there are no branch points or endpoints, and the input pattern shown in Figure 1 is considered to be one of the three patterns shown in Figure 2. letter,
0, D, and B are determined. After determining these three candidate characters, we can see that the input pattern does not have the shape shown in Figure 2-1 because there is no roundness on the left side, and that it does not have the character shape shown in Figure 2-3 because there is a roundness on the right side. I understand. Therefore, the pattern in FIG. 1 can be seen as a letter D in FIG. 2. However, conventionally it has been difficult to detect whether a character pattern is rounded or not, and there has been no stable method for determining this. An object of the present invention is to provide a method for extracting features that are effective for distinguishing character patterns whose difference is whether they are rounded or not, or whether they are straight.

The present invention provides a pattern memory that stores a binary pattern for one character, coordinate values of feature points of stroke end points, branch points, and bending points from the binary pattern of this pattern memory, and a plurality of direction values for approximating the stroke with a polygonal line. basic feature extraction means for extracting basic features such as; basic feature extraction means for storing coordinate values and direction values obtained by the basic feature extraction means; a dictionary for candidate determination that stores standard patterns expressed by the basic features of each category; Candidate determination means that compares the basic features from the input pattern with the basic features of each standard pattern in the dictionary for candidate determination and sets character names of matching standard patterns as candidate character names, and candidate character name storage that stores candidate character names. means, a judgment dictionary that stores one or more feature lists necessary for judging each character, extracts a feature list of candidate character names from the judgment dictionary, and extracts the features of the feature list from the input pattern or basic features. When all the features in the feature list have been extracted, the final component of OCR, which consists of a judgment means that judges the candidate character name as the character name of the input pattern, is used to extract the character name from the feature list extracted from the judgment dictionary. One of the features is an intersection detection unit that sequentially reads out the pattern memory according to the direction value specified from the coordinate value of the edge of the pattern memory and obtains the coordinate value of the first detected pattern position, and the pattern memory is divided into two points. An arrival detection section that reads out the coordinates of the midpoint from the coordinates in sequence according to the specified direction value and calculates the distance value to the coordinates of the first detected pattern position, and the distance value obtained by the arrival detection section. and a verification unit that compares with specified threshold values, and converts the coordinates of the feature points that are basic features or the coordinates obtained by the intersection detection unit to the coordinates of the two points of the arrival detection unit according to the specification in the feature list. The distance value obtained as the input pattern is detected as the determination feature of the input pattern.

Next, the present invention will be explained with reference to the drawings.

FIG. 3 1 shows scanning directions dl to d8 for performing diagonal scanning.
FIG. 3 shows the order of scanning lines when performing diagonal scanning in the direction dl, which is the order of SI and S2.

In the other directions (d2 to d8), the order of the scanning lines is the same toward the center of the pattern memory. Perform diagonal scanning in directions dl to d8 and PI the intersection that intersects the input pattern for the first time.
~P8. Direction dl as illustrated in FIG.
2 obtained by diagonal scanning of and d7 (or directions d2 and d8)
The distance to reach the input pattern by horizontally scanning the midpoint of the two intersections P1, P7 (or P2, P8) to the left is obtained by diagonally scanning in directions d3 and d5 (or directions d4 and d6). Two intersections P3, P5 (or P4, P6)
The distance to reach the input pattern by horizontally scanning the midpoint in the right direction is b, directions dl and d7 (or directions d2 and d8).
) horizontally scan the midpoint of the two intersections P1, P7 (or P2, P8) obtained by diagonal scanning in the left and right directions, and calculate the shorter distance until reaching the input pattern in the direction c and Horizontally scan the midpoint of the two intersections P & P5 (or P4, P6) obtained by diagonal scanning of d3 and d5 (or directions d4 and d6) to the left and right to reach the input pattern, whichever is shorter. If the distance is e, then in FIG.
In FIG. 2, c is assigned when the threshold value tsa is below and b is greater than or equal to the threshold value tl, and in FIG. 2, c and e are assigned when the threshold value is below ta. Here, it is assumed that tl>t2.
FIG. 4 is a block diagram showing an embodiment for realizing the pattern feature extraction method of the present invention. Reference numeral 10 denotes a pattern memory for storing a pattern for one character, in which pattern information that has undergone processing such as OCR photoelectric conversion and cutting is stored.

Basic feature extraction means 11 extracts basic features such as coordinate values of end points, branch points, and inflection points and direction values that approximate a stroke to a polygonal line from the character pattern stored in pattern memory 10, and stores them in basic feature register 12. Regarding the method of feature extraction, for example, from a character pattern as shown in FIG. 71, as shown in FIG.
Stroke direction values (indicated by arrows) indicated by numbers such as 3, 5, etc. are detected and set as a symbol string such as Fox Yuhimo IB in the order of detection. Figure 7 3 shows the stroke direction value and the number 0
, 1, 2, . . . 7. Since these basic features can be used in common for all characters, there is almost no need for them in later processing. Therefore, in the basic feature extraction means 11,
Uniform features are extracted for all input characters. Once the basic features are extracted, control passes to the candidate character determining means 14, where the basic features stored in the basic feature register 12 are compared with standard patterns stored in the candidate determining dictionary 13. This standard pattern is for example:
It has a shape like 12 Zu (4 songs) 4 $ 2 $ (01 K) 01 B, and in this format, the first A indicates the letter name of this standard pattern, and the K, B, and numbers (0 to 7) are Figure 7 2
Similarly, it shows the inflection point, branch point name, and direction value of the stroke. In particular, the number 123 in 12 shoes indicates one of the direction values 1, 2, or 3, and the K after it indicates that there is an inflection point. .

Also, the part inside parentheses ( ) may or may not be present and indicates a stroke. Since a standard pattern such as this format includes the basic feature 2K porridge box IB as shown in FIG. 72, the character name A of this standard pattern becomes a candidate character.

Note that the candidate determination dictionary 13 contains one character per character to be recognized.
Contains one or more standard patterns. The candidate determining means 14 performs a comparison with the standard pattern in the candidate determining dictionary 13, and the standard /g0 turn character name containing the basic feature in the register 12 is stored in the candidate character name register 5. In this register 15, one or more candidate characters may be set, or there may be none at all. Once the candidate character name is determined based on the basic characteristics, control is transferred to the determining means 17. In the determination means 17, if there is no candidate character name stored in the candidate character name register 5, a signal indicating unreadability is output to the output register 19, but if there is one or more candidate characters, the signal is output to the output register 19. The content of the judgment dictionary 18 is indexed using the character name as a key, the necessary features are extracted from the pattern memory 0 and the basic feature register 12 according to the feature list read therefrom, and the character name that satisfies the feature list is entered as an input character. It is output to output register 9 as the name. Each item in the judgment dictionary 18 expresses the type and parameter of a feature, 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.

This is an example using the feature x, and shows that if the x coordinate of the branch point BI is 5 bits or more to the right of the x coordinate of the end point T3, one feature for becoming A is satisfied. One or more of these features are grouped together as a feature list for each character, and if there is only one feature, the judgment can be made if it is satisfied, but if there are multiple features, all the features on the list are It means being satisfied. In this case, the relationship between the X coordinates of the basic features is used as a feature, but a feature extraction method is also required to extract features that are not extracted using the basic features from the input pattern. One of them is the present invention. FIG. 5 is a block diagram showing a specific embodiment of the determining means 17 in the pattern feature extraction method of the present invention. The determination means 17 includes several feature extraction means 40, 50, . It shows that there are two means 40. Note that some parts common to FIG. 4 are omitted from illustration. The feature list corresponding to the obtained complementary character set in the candidate character name register 15 is decoded by the determination control circuit 20', and the feature R, that is, R, m, n, c, t, r [however, m=Pi (i=1-8)
．． n = Pj (i = 1 to 8) or m, n are branch points, end points]
is selected, if m=Pi, n=Pi, i is stored in register 21 as a parameter that determines the direction of diagonal scanning, and i is stored in register 2 as a parameter that determines the direction of diagonal scanning.
2, c is stored in the register 31 as a parameter that determines the scanning direction from the midpoint of the two designated points, and is used to compare with the value of the distance from the coordinates of the midpoint to the input pattern. A function value parameter t is set in register 3, and a parameter r indicating a magnitude relationship is set in register 32.

The intersection detection means 23 and 24 scan the pattern memory 0 according to the parameters that determine the diagonal scanning direction set in the registers 21 and 22, first detect a point that intersects with the input pattern, and store the coordinate value in the register 25. 2
Set to 6.

The arrival detection means 27 obtains the coordinate value of the midpoint from the values of the registers 25 and 26 in which the coordinate value of the designated point is set, and scans the pattern memory 10 in the direction set in the register 31 to reach the input pattern. The value of the distance from the midpoint until the end is set in the register 28. Verification means 29
If the value set in the register 28 satisfies the threshold value t set in the register 30 and the magnitude relationship r set in the register 32, the control circuit 2 determines "1", otherwise it determines "0". Output this. If the parameter of feature R is c = 1, scan left, c; 2, scan right, if c = 3, scan left and right, c
=4 means upper scan, c=5 means lower scan, c=6 means upper and lower scans, r=1 means more than that, and r:2 means less than that. 1, 0:R, P1, P7, 1, tl, I R, P3, P5, 2, tl, 1 or 0: R, P2. P& 1, tl, I R, P4, P6 2, tl, 1 D for Figure 2 2: R, P1, P7, 3, t2, 2 R, P3, P5, 2, tl, 1 or D :R, P2, P8, 3, [2,2 R, P4, P0 2, tl, 1 0 For Figure 2 3: R, PI, P7, 3, t2, 2 R, P3, P5 , 3, t2, 2 or B: R, P2, P& 3, t2, 2 Ta R, P4, P6, 3, t2, 2.

Here, each feature list is described by two features, and when both features are satisfied, the category name attached to the feature list is given as an input character name. 0 In Fig. 5, if an end point or a branch point is specified for m or n, the coordinate value of the end point or branch point can be directly set in the register 25 or 26 without using diagonal scanning to provide the same function as above. You can also do it.

For example, in the pattern of FIG. 6, horizontal scanning is performed in the right direction from the coordinate value of the midpoint between point P3 obtained by diagonal scanning with direction value d3 and branch point BI, and if distance b is greater than or equal to function value t3, the 6th In FIG. 2, if it is below the cutoff value, it can be determined as FIG. 61. The feature R for determination in FIG. 6 is as follows. 0 1:R, P3 B1, 2, t4, 22: R,
P3, B1, 2, t3, 1 In the above explanation, the input pattern was a scanned binary pattern, but it is of great significance to replace it with a thinned pattern in order to eliminate the influence of the thickness. .

[Brief explanation of drawings]

FIG. 1 is a diagram showing one of the recognized input characters, FIGS. 2 and 6 are diagrams showing examples of patterns that can be distinguished by applying the present invention, and FIG. 3 is a diagram related to diagonal zero scanning. Fourth
5 is a block diagram showing an embodiment of the pattern feature extraction method of the present invention, FIG. 5 is a block diagram showing an embodiment of the determination means 17, FIG. 7 is a diagram explaining basic features, FIG. 8 is a diagram illustrating the midpoint of two intersections obtained by diagonal scanning and horizontal scanning. In the figure, 1 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 name register,
17 is a determination means, 18 is a dictionary for determination, 19 is an output register, 20 is a determination control circuit, 23 and 24 are intersection detection means, 27 is an arrival detection means, and 29 is a verification means. Figure O Figure O 2 Figure Age 3 Figure O 4 Figure O 6 Figure O 5 Figure O 7 Figure O 8

Claims (1)

[Claims] 1. A pattern storage means for storing an input pattern, a basic feature extraction means for obtaining coordinate values of a plurality of types of feature points of a pattern from the pattern storage means and a plurality of direction values for approximating a stroke with a polygonal line, and a basic feature extraction means. basic feature storage means for storing coordinate values and direction values obtained by the basic feature storage means; a dictionary for candidate determination storing standard patterns expressed by the basic features of each category; Candidate determining means that compares the features with the basic features of each standard pattern of the candidate determining dictionary and sets character names of compatible standard patterns as candidate character names; Candidate character name storage means that stores candidate character names; a determination dictionary that stores one or more feature lists necessary for determining each character; and determination means that determines character names of the input pattern from the candidate character name storage means based on the feature list of the determination dictionary; an output storage means for storing character names of the input pattern determined by the determination means, and the characteristics specified in the feature list are extracted from the basic features and the input pattern, An intersection detecting section reads the pattern storage means sequentially from the coordinate values of the edges of the pattern storage area according to the direction values specified in the feature list and calculates the coordinate values of the first detected pattern position; an arrival detection section that reads out the coordinate values of the midpoint obtained from the coordinate values in sequence according to specified direction values and calculates the distance value to the coordinate values of the first detected pattern position; and the distance obtained by the arrival detection section. and a verification unit that compares the value of A pattern feature extraction method in which a distance value obtained as the coordinate values of two points is detected as a determination feature of an input pattern.