JPH0245232B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Technical Field of the Invention The present invention relates to a character recognition device, and particularly to a character recognition device, which extracts many types of features for characters that have many deformations, such as handwritten kanji, and have many types of characters to read. The present invention relates to a character recognition device that accurately and efficiently recognizes input characters.

(2) Prior art and problems Conventional character recognition devices use a two-dimensional correlation method for printed characters and a structural analysis method for handwritten characters, but the former has the disadvantage of being susceptible to deformation of handwritten characters. However, the latter had the disadvantage that it took time to create templates.

(3) Purpose of the Invention The present invention aims to solve the above-mentioned problems, and uses a two-dimensional correlation method to easily create templates when there are many types of characters to be read, and also uses a two-dimensional correlation method to easily create templates when there are many types of characters to be read. The purpose of this invention is to provide a character recognition device that extracts many types of features and matches each feature with multiple templates in order to deal with such deformations, and also performs matching hierarchically to improve recognition speed. It is said that

(4) Structure of the invention In order to achieve the above object, the present invention utilizes the fact that the weaknesses of individual features are compensated for by using multiple types of features simultaneously, and realizes stable recognition performance.
Furthermore, by matching multiple templates and features, it is possible to absorb handwritten deformations. Additionally, to improve processing speed, the first stage of matching narrows down the candidate categories using a small number of features, and the second stage of matching uses all features to perform detailed classification. be. That is, the character recognition device of the present invention is a character recognition device that observes a given character and recognizes the character, and includes a plurality of feature extraction means for respectively extracting different types of features of the observed character, and a character recognition device that recognizes the character type to be read. A recognition dictionary that has a plurality of standard templates per category and stores a plurality of standard features that are made to correspond to the different types of features for each of the standard templates, and separates categories among the different types of features of the observed characters. a first distance calculation means that calculates the minimum value of the distance from a corresponding standard feature for each category stored in the recognition dictionary for some of the features with a large force and adds the distance for each category; A candidate selection means that narrows down the candidate categories based on the output result of the distance calculation means, and a minimum value of the distance between the corresponding standard feature for each candidate category stored in the recognition dictionary for all the different types of features. a second distance calculating means for calculating and adding for each candidate category; and a category determining means for performing detailed classification based on the output result of the second distance calculating means; It is characterized by using as recognition candidates. Embodiments will be described below with reference to the drawings.

(5) Embodiment of the invention FIG. 1 shows a schematic block diagram of an embodiment of the invention.

In the figure, 1 is an observation unit that photoelectrically converts characters written on paper, and 2, 3, and 4 are feature extraction units that extract features from input characters. There are three types: a feature extractor, a feature extractor, and a feature extractor. In addition, 5 is a first matching unit that selects candidate categories using some features, 6 is a second matching unit that performs detailed classification using all features, and 7 is a matching unit that selects candidate categories using some of the features. On the other hand, a recognition dictionary in which a plurality of standard templates are stored (in this case, one standard template is associated with three types of features), and 8 represents an output section for the recognition results.

The features extracted by each feature extraction unit 2, 3, and 4 are:
It is sent to the matching section 5. The matching unit 5 matches the template of the recognition dictionary 7 with predetermined features, and determines the top n categories with the smallest distance. The matching unit 6 matches all features with the templates of the recognition dictionary 7 for the n categories determined by the matching unit 5, and sends the top m features with the smallest distance value to the output unit 8. The output unit 8 displays the sent candidate categories on a display or stores them in an external storage device.

Next, parts related to the present invention will be explained in detail.

First, there is a feature extraction section.As an example, we will introduce three features: line density feature, line direction feature, and line area feature.
Explain the types.

The line density feature is a feature that expresses the complexity of characters.
The line direction feature is a feature that expresses the direction of each character line that makes up a character, and the interline area feature is a feature that expresses the state of the character line and the area surrounded by the character line.
These three types of characteristics are considered to be complementary to each other.

FIG. 2 is a diagram illustrating linear density characteristics. In the figure, 11 is a recognized character pattern, 14 is a projection origin,
15 to 18 are projection axes, 15 is the horizontal direction, 16 is the vertical direction, 17 is the right diagonal direction, and 18 is the left diagonal direction, and 15-1 and 15-2 are the first and Projection patterns 16-1 and 1 with respect to the projection axis 15 in the second projection pattern
6-2 are third and fourth projection patterns relative to the projection axis 16; 17-1 and 17-2 are fifth and sixth projection patterns relative to the projection axis 17; 18- 1
and 18-2 are seventh and eighth projection patterns, which represent the projection patterns with respect to the projection axis 18, respectively.

In other words, in Fig. 2, the projection origin 1 is placed at an arbitrary position.
For example, four projection axes 15 to 18 that intersect with each other at the projection origin 14 are set, and first projection patterns 15-1 to eighth projection patterns of the recognized character pattern are set for the projection axes 15 to 18. An example in which 18-2 is generated is shown.

The extraction of the first and second projection patterns 15-1 and 15-2 with respect to the projection axis 15 is carried out in the direction perpendicular to the projection axis 15.
The first projection pattern 15-1 is extracted by scanning and counting the points of change from the background portion (for example, white) to the character portion (for example, black). Further, since there is no character line portion on the right side of the projection axis 15, the second projection pattern 15-2 does not appear. Similarly, third projection patterns 16-1 to eighth projection patterns 18-2 for projection axes 16 to 18 are extracted.

Figure 3 is a block diagram of the linear density feature extraction section, and Figure 4.
Figures A and B are diagrams for explaining this block diagram. 19 and 2 in Figures 3 and 4
0 is a shift register, 21 is a one-row delay circuit, 2
2-1 to 22-4 are not circuits, 23-1 to 23-4 are OR circuits, 24-1 to 24-
4 is an AND circuit, 25-1 to 25-4 are one-shot multi, and the inputs are from "1" to "0".
26-1 to 26-4 are note circuits, 27
-1 to 27-8 are AND circuits, 28-1 to 28-8 are first to eighth projection pattern counter groups, and the first projection pattern counter group 28-1 is the first projection pattern counter group in FIG. Projection pattern 15-
This is a group of counters corresponding to 1. 29 is an address generator, 30 is a row address counter that counts row addresses (for example, address j in FIG. 4A), and 31 is a row origin address register that counts the row address of the projection origin (for example, 4
32 is a column address counter for counting column addresses (for example, column address i in FIG. 4A); 33 is a column origin address register; , which stores the column address of the projection origin (for example, the column address a of the projection origin 14 in FIG. 4A);
34 and 35 are arithmetic units, and the arithmetic unit 34 performs the operation of adding (-1) the content i of the column address counter 32 and the content j of the row address counter 30, that is, (i+j-1). , and the arithmetic unit 35 is the column address counter 32
36 and 37 are registers, and 36 and 37 are registers. are the column address a and row address b of the projection origin
The added value (a+b-1) of and (-1) is set. The register 37 is set to a value (ab+J) obtained by subtracting the row address b from the column address a of the projection origin and adding the maximum value J of the row address. 38
41 are comparators, which output "1" until the comparison contents match, and "0" after the match;
42 is a feature register that stores extracted features. 45 represents a character area, and 46 represents a scanning mask.

In FIG. 3, an image signal is input to the shift register 19. The image signal is generated by horizontally scanning the input characters and assigning "0" to the background part and "1" to the character line part.
It is sent as. The image signal input to the shift register 19 is sent to the shift register 20 via the one-row delay circuit 21.
From the output terminal of the register 19 and the output terminal of the shift register 20, an image signal similar to that scanned by the scanning mask 46 at arrow B in FIG. 4A, that is, the scanning mask 46 in FIG. 4B is output. Ru. Note that the numbers written in the mask 46 correspond to the output terminals.

First, in the AND circuit 24-1, the image signal in the window 1 of the mask 46 in FIG.
2-1 and the inverted signal of the image signal in window 2 of the mask 46 sent via the OR circuit 23-1. Therefore, the reason why the output of the AND circuit 24-1 is "1" is because of the mask 46.
If "1" is detected in window 1 and "0" is detected in window 2, that is, a change from "0" to "1" in the direction matching the scanning direction of the character area 45 is detected and the above AND circuit is executed. 24-
1 outputs "1". The output of the AND circuit 24-1 is sent to the AND circuits 27-1 and 27-2.
In the AND circuit 27-2, the output signal of the comparator circuit 38 is ANDed with the output signal of the comparator circuit 38. The output of the AND circuit 27-1 is then output to the first projection pattern counter group 28-1.
The output of the AND circuit 27-2 is counted by the counters of the second projection pattern counter group 28-2 whose addresses correspond to the contents of the row address counters 30, respectively. In this way, the first projection pattern/counter group has character area 4 in FIG.
The number of strokes that exist in the left side of the projection axis 15 in 5 in the horizontal direction corresponding to the row address j is set. Further, the number of strokes on the right side of the projection axis 15 is set in the second projection pattern counter group.

Thereafter, the contents of the third to eighth projection pattern counter groups 28-3 to 28-8 are also set in the same manner as described above.

The feature pattern obtained in this way is stored in the feature register 42.

FIGS. 5 to 8 are diagrams for explaining line direction characteristics. FIG. 5 is a diagram explaining the addition of direction codes to characters, FIG. 6 is a diagram showing horizontal projection by direction code, and FIG. 7 is a diagram explaining various projection directions.
FIG. 8 is a diagram showing various projections for each direction code. FIG. 5 is a diagram illustrating the direction code added to the character "tree". Direction codes such as horizontal H, vertical V, diagonally downward left L, and diagonally downward right R are added to each grid point of the character "tree". Figure 6 shows the characters in Figure 5 being horizontally scanned, and for each horizontal scan, the number of grid points to which direction code H is added, the number of grid points to which direction code V is added, the number of grid points to which direction code L is added, and the direction code. It shows the results obtained by counting the number of lattice points to which R is added. Figure 7 shows the scanning direction when creating a projection.
indicates the vertical scanning direction, indicates the horizontal scanning direction, indicates the diagonally downward scanning direction to the right, and indicates the diagonally downward scanning direction to the left. Figure 8 A shows the projection for each direction code obtained by vertical scanning, B shows the oblique shadow for each direction code obtained by diagonally downward scanning to the right, and C shows the projection for each direction code obtained by diagonally downward scanning to the left. Shows projection by direction code.

FIG. 9 shows a block diagram of the line direction feature extraction section. In FIG. 9, 51 is a video memory, 52
-1 to 52-3 are one-row delay circuits, 53 is
PROM, 54-1 to 54-4 are AND circuits,
55-1 is an H component counter, 55-2 is a V component counter, 55-3 is an L component counter, 55-4 is an R component counter, and 56 is a row address counter. Input video is stored in video memory 51. The video memory 51 is scanned horizontally, vertically, diagonally downward to the right, and diagonally downward to the left. The grid point information read out from the video memory 51 is input to the one-row delay circuits 52-1 to 52-3.
The input lattice point matrix from PROM53
is input. PROM53 is input 3×
Output terminals P1 and P for the grid point pattern of 3
One logic "1" signal is output to any one of P2, P3, and P4. For example, PROM53 is 3×3
When the pattern of lattice points is as shown in FIG. 10 (b), a logic "1" is output to the output terminal P2, and when the pattern is as shown in FIG. 10 (c), a logic "1" is output to the output terminal P4, In the case shown in Figure 10 D, the output terminal P
Outputs logic "1" to 1. Outputs from the output terminals P1 to P4 are input to AND circuits 54-1 to 54-4, respectively, and information about the grid point at the center of the 3×3 matrix is input to other input terminals of the AND circuits 54-1 to 54-4. be done. AND circuit 5
The pulse output from 4-1 is the H component counter 55-
1, the pulse output from the AND circuit 54-2 is counted by the V component counter 55-2, the pulse output from the AND circuit 54-3 is counted by the L component counter 55-3, and the pulse output from the AND circuit 54-4 is counted by the L component counter 55-3. The pulse output from the R component counter 55
-4 counts. The values of counters 55-1 through 55-4 are updated in feature pattern register 5 when the contents of row address counter 56 are updated.
It is set to 7.

FIG. 11 is a block diagram of the interline region feature extraction section.
FIGS. 12 and 13 are diagrams for explaining this operation. In FIG. 11, 62 is a memory, 63
is a vertical scanning address counter, 64 is a horizontal scanning address counter, 65 is a horizontal start point detection unit, 6
6 is a horizontal end point detection section, 67 is a vertical start point detection section, 6
8 is a vertical end point detection unit, 69 and 70 are flip-flops, 71 is a horizontal surface feature memory, 72 is a vertical surface feature memory, 73 to 75 are AND circuits,
Reference numeral 76 indicates a double-sided enclosing feature counting section, 77 a horizontal enclosing feature counting section, 78 a vertical enclosing feature counting section, and 79 a feature pattern register. The image signal is stored in memory 62. Vertical scan address counter 63 is for scanning memory 62 in the vertical direction, and horizontal scan address counter 64 is for scanning memory 62 in the horizontal direction. The horizontal start point detection section 65 detects the point of change from black to white in horizontal scanning, the horizontal end point detection section 66 detects the point of change from white to black in horizontal scanning, and the vertical start point detection section 65 detects the point of change from black to white in horizontal scanning. Reference numeral 67 detects a point of change from black to white in vertical scanning, and a vertical end point detection section 68 detects a point of change from white to black in vertical scanning. The flip-flop 69 is set when the horizontal start point detection section 65 detects a change point from black to white, and is reset when the horizontal end point detection section 66 detects a change point from white to black. The flip-flop 70 is set when the vertical start point detection section 67 detects a change point from black to white, and is reset when the vertical end point detection section 68 detects a change point from white to black. The horizontal plane feature memory 71 includes a flip-flop 69
The lattice points during the period in which . Similarly, vertical surface feature memory 7
2 stores the back surface portion sandwiched between strokes when vertical scanning is performed. The double-sided enclosing feature counting unit 76 counts the horizontal or vertical projections of the double-sided parts, the horizontal enclosing feature counting unit 77 counts the horizontal or vertical projections of the horizontal plane part, and the vertical enclosing feature counting unit 78 counts the horizontal or vertical projections of the horizontal plane parts. Count horizontal or vertical projections of vertical plane parts. The count values of the double-sided enclosing feature counting section 76, the horizontal enclosing feature counting section 77, and the vertical enclosing feature counting section 78 are stored in the feature pattern register 79.

FIG. 12 and FIG. 13 explain the operation of the above-mentioned line area feature extraction section. FIG. 12 shows input characters. When horizontal scanning is performed, the first
The back side of the horizontal hatch in Figure 3 A is taken out and the 13th
3 is stored in the horizontal plane feature memory 71. When vertical scanning is performed, the back surface of the vertical hatch shown in FIG. Double-sided box feature count section 7
6 counts the projections of the figure as shown in FIG.
It calculates the projection of a figure as shown in FIG. 1st
Figure 3 H shows the horizontal and vertical projections of Figure 13 E.

Next, the matching section will be explained. The matching unit is composed of a matching unit 5 shown in FIG. 1, a matching unit 6, a recognition dictionary 7, etc., and these are illustrated in detail as shown in FIG. 14, for example. In the figure, numerals 5, 6, and 7 correspond to those in FIG. 103 is a readout control circuit for reading out patterns from the feature pattern register 101 and the dictionary 7 and inputting them to the matching section; 200 is a readout control circuit for reading patterns stored in the dictionary 7 and inputting them to the matching section; 104 is a NOT circuit, 105 is an adder,
106 is an EOR circuit, 107 is an adder, 108 is a register, 109 is a register, 110 is a comparator,
111 is an adder, and 112 is a register. 20
1 is a candidate selection circuit that selects a plurality of candidate categories for the input character by comparing the magnitude of the distance output from the distance calculation circuit 200;
is a register, and 114 is a comparator. 202 is a distance calculation circuit that calculates the distance between the pattern stored in the dictionary 7 and the feature pattern; 115 is a NOT circuit; 116 is an adder; 117 is an EOR circuit;
8 is an adder, 119 is a register, 120 is a register, 121 is a comparator, 122 is an adder, and 123 is a register. 203 is a determination circuit that determines the category corresponding to the input character by comparing the magnitude of the distance output from the distance calculation circuit 202; 124 is a register; and 125 is a comparator.

FIG. 15 shows an explanatory diagram of the operation of the matching section shown in FIG. 14.

The operation of the matching section will be explained using FIG. 14 and FIG. 15.

Now, suppose that the characteristic pattern of the input character is 〓, and the template of category C is 〓 _i (i=1 to P).
(Category C is composed of P templates.) Assume that the feature pattern is composed of N types of different features. = = ( = (1), = (2), ..., = (N)) It is expressed as 〓i=(〓 _i (1), 〓 _i (2), ..., 〓 _i (N)). Here, if we focus on one feature, 〓(n) = (f _o1 , f _o2 , ..., f _o M) 〓 _i(o) = (t _io1 , t _io2 , ..., t _ioM ) . Let d represent the distance between 〓 _(o) and 〓 _i(o) , and let d (〓 _(o) , 〓 _i(o) )= _M 〓 ^m=1 ｜f _on −t _ion ｜. Input character = Distance D between a certain category C
is defined as D(〓, C)= _N〓n ⁼¹ [min ^i=1~P {d(〓 _(o) , _〓i(o) )}]. At this time, D(〓, C) for input〓
The category C for which is the minimum is determined to be the input category.

The features extracted from the feature extractor are stored in the feature pattern register 101. The read control circuit 102 sequentially reads pre-designated features among the features stored in the feature pattern register 101 and the corresponding features of the templates of each category stored in the dictionary 7, and inputs them to the distance calculation circuit 200. do. The NOT circuit 104 is for adding a negative sign to the feature read from the feature pattern register 101, and the output of the adder 105 is _tion -f _on . EOR circuit 106 is adder 10
By taking the EOR of the addition output t _ion −f _on of 5 and Carry, |t _ion −f _on | is output. Adder 10
7 and register 108 are distance d with respect to feature n.
Calculate (〓 _(o) , 〓 _i(o) )= _M 〓 ^m=1 ｜f _on −t _ion ｜. Register 109 and comparator 110 are circuits for finding the minimum value. Comparator 110 compares the input and output of register 109, and if the output is larger, the input is set in register 109. Therefore min ^i=1〜P {d
(〓 _(o) , 〓 _i(o) )} is found. The adder 111 and the register 112 add min ^{i=1 to P} {d(〓 _(o) ,〓i _(o) )} for all the features specified in advance. In other words, the distance between a certain category C and the input
D'(〓, C)= _N〓n ⁼¹ [min ^i=1~P {d(〓 _(o) , _〓i(o) )}] is calculated. The candidate selection circuit 201 selects the one smaller than a predetermined value from among D'(〓, C). A distance reference value is set in advance in the register 113, and the comparator 114 sends the control circuit to the read control circuit 103 only when the output of the register 112 is smaller than this value.

Read control circuit 103 sequentially reads features from feature pattern register 101 and dictionary 7.
The category read from the dictionary 7 at this time is the category selected by the candidate selection circuit 201. Similarly to the distance calculation circuit 200, the distance calculation circuit 202 calculates the distance D(〓,
C)= _N 〓 ⁿ⁼¹ [min ^i=1~P {d(〓 _(o) , 〓 _i(o) )}] is calculated.
Processing of distance calculation circuit 200 and distance calculation circuit 202
The difference with the processing is that the processing of the distance calculation circuit 200 uses some features to calculate the distance for all categories, whereas the processing of the distance calculation circuit 202 uses all the features to calculate the distance. The purpose is to calculate the distance for the categories of the parts. The determination circuit 203 determines the minimum value of the distance output from the register 123 and outputs the corresponding category to the register. Register 124 and comparator 125
is a circuit for finding the minimum value, and the comparator 125 outputs a control signal when the input of the register 124 is smaller than the output. This control signal causes register 1 to
Since the category corresponding to No. 26 is set, the category of the determination result is stored in the register 126 when distance calculations for all candidate categories are completed.

In Figure 15, the first feature (1) and the third feature have the greatest ability to separate categories.
(3) Select and input character characteristics for each separately〓 ₁
We are looking for the minimum distance between and 〓 ₃ . Then, by comparing the sum of these minimum values with an appropriate reference value, the candidate selection circuit 201 narrows down the 2000 character categories to candidates such as 100 character types or 50 character types. There is.

For the category selected by the candidate selection circuit 201, the minimum distance and their sum are calculated for each of all features (1) to (N),
The determination circuit 203 determines the minimum sum of the minimum distances for each category. In this case, even if the standard template 〓 has only P types for one category, if there are N types of features, simply P
We don't just choose the best one from a variety of options.
Since the minimum distance is found for each feature, it can be considered that the optimal one is selected from among P ^N types. Note that the number of candidates can be easily adjusted by changing which features and how many are selected in the first step and by setting the standard value for comparison in the candidate selection circuit 201. .

(6) Effects of the Invention As explained above, according to the present invention, by using multiple types of features at the same time, the weaknesses of individual features are compensated for and stable recognition performance is achieved. Since it performs matching, it is less affected by the deformation of handwritten characters. Furthermore, by performing hierarchical matching using the same features, processing speed can be improved without increasing dictionary capacity.

[Brief explanation of the drawing]

Fig. 1 is a schematic block diagram of an embodiment of the present invention, Fig. 2 is an explanatory diagram of the linear density feature, Fig. 3 is a block diagram of the linear density feature extracting section, and Fig. 4 is a block diagram illustrating the diagram in Fig. 3. 5 to 8 are explanatory diagrams of the line direction feature, FIG. 9 is a block diagram of the line direction feature extraction section, and FIG. 10 is a diagram for explaining the block diagram shown in FIG. 9. Figure 11 is a block diagram of the line feature extraction section, and Figures 12 and 13 are the block diagram of the line feature extraction section.
FIG. 14 is a block diagram of the matching section, and FIG. 15 is a diagram explaining the block diagram shown in FIG. 14. In the figure, 1 is an observation unit, 2 to 4 are feature extraction units,
5 and 6 are matching units, 7 is a recognition dictionary, 200 is a distance calculation circuit, 201 is a candidate selection circuit, 202 is a distance calculation circuit, and 203 is a determination circuit.

Claims (1)

[Claims] 1. A character recognition device that observes a given character and recognizes the character, which has a plurality of feature extraction means for extracting different types of features of the observed character, and a plurality of standard templates for each category of characters to be read. A recognition dictionary that stores a plurality of standard features that are made to correspond to the different types of features for each of the standard templates, and a recognition dictionary that stores a plurality of standard features that are made to correspond to the different types of features for each of the standard templates; Based on the output result of the first distance calculation means, which calculates the minimum value of the distance from the corresponding standard feature for each category stored in the recognition dictionary and adds it for each category; A candidate selection means for narrowing down the candidate categories and the minimum distance between the corresponding standard feature for each of the candidate categories stored in the recognition dictionary for all of the different types of features are determined and added for each of the candidate categories. It is characterized by comprising a second distance calculating means and a category determining means for performing detailed classification based on the output result of the second distance calculating means, and the category determined by the category determining means is set as a recognition candidate. character recognition device.