JPS59116885A - Character recognition system - Google Patents

Abstract

PURPOSE:To perform character recognition wherein two-dimensional expansion and contraction are matched by normalizing expansion and contraction horizontally in one direction with regard to projection information on the horizontal axis of a pattern, and using pieces of position information on partial patterns for the vertical expansion and contraction matching of every partial pattern. CONSTITUTION:An input character pattern is read out of an input character pattern storage part 2 as a signal 101 and a projection information histogram on the horizontal axis is found and sent to a mapping relation generating circuit 3. This circuit 3 obtains the mapping function between standard projection information stored in a standard projection information storage part 4 and a projection information signal 102 and supplies it to a two-dimensional expansion and contraction matching circuit 5. This circuit 5 reads the signal 101 to perform unidirectional expansion and contraction normalization by using a signal 103, and then performs unidirectional expansion and contraction normalization by using the mapping function stored in a standard character pattern storage part 6. Then, the vertical expansion and contraction matching of every partial pattern is performed by utilizing the position information from the storage part to find the degree of difference and then the degree of difference of each partial pattern is found and outputted.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method for recognizing characters composed of many strokes, such as kanji, hiragana, gatagana, alphanumeric characters, etc.

The development of optical character recognition technology has been remarkable in recent years, and products that recognize alphanumeric characters, both handwritten and printed characters, have been commercialized and put into practical use. Also kanji,
For those that recognize Japanese characters including hiragana,
As far as single fonts for printed characters are concerned, the development of prototype machines has already been announced.

However, in order to recognize handwritten characters such as kanji, hiragana, katakana, alphanumeric characters, etc., it is necessary to extend the handwritten alphanumeric recognition method to recognize even kanji, or to take an approach from printed kanji recognition. However, no effect has been obtained yet. One reason for this is that kanji have more complex shapes than alphanumeric characters, making it difficult to select characteristic information.
Another reason is that it is difficult to obtain stable feature information due to the large number of deformations.

On the other hand, although experiments have been attempted on a small number of data by combining the brush effect and the template matching method, at present no good results have been obtained.

Now, the first possible causes of fluctuations in handwritten characters are (1) positional deviation (stretching M), and (2) rotation, and each stroke that makes up the handwritten character is independent of (1) and ( Because of the variation 2), distortion occurs in the entire character stamp.

Regarding positional deviation (1), the basic problem is that positional deviation occurs in two directions because it is a character stamp or two-dimensional information. To solve this problem, we perform nonlinear stretching processing in one direction, for example in the horizontal direction, column by column, and then in the other direction,
For example, attempts have been made to recognize printed Chinese characters using a character sensitivity system that absorbs two-dimensional expansion/contraction fluctuations by performing nonlinear expansion/contraction processing on a line-by-line basis in the vertical direction. (Nakano, et al., “
“Improvement of Kanji Recognition Using Marginal Distribution and Its Spectrum” Transactions of the Institute of Electronics and Communication Engineers, VOI 57 =D, AI PP
, 15-22) However, unlike in printed kanji recognition, handwritten kanji recognition involves independent deformation for each partial stroke, such as lateral and lateral, so non-linear expansion/contraction processing is performed simply on a column-by-column and row-by-row basis, as described above. Even if this is done, it is not possible to absorb the positional shift for each partial slam.

31 The purpose of the present invention is to achieve pseudo expansion/contraction matching in two different directions on a two-dimensional plane for each part of a kanji character.
- Provides a highly accurate character opening method that absorbs two-dimensional positional deviations.

A detailed explanation will be given below with reference to the drawings, taking as an example the horizontal direction and the vertical direction as two different directions.

The reason for this is that it is easy to understand when explaining, and it is often used when dealing with two-dimensional batons.
The same effect can be obtained by using two different directions.

Figures 1 (a), (b), (0), and (1) are diagrams for intuitively explaining two-dimensional expansion/contraction matching; (a) is the standard character BATA, (t)) Fi human power character slam, (C)
normalizes and stretches the input character button in the horizontal direction so that the projection information of the input character button (b) on the horizontal axis 2 and the projection information of the standard character button (a) on the horizontal axis are optimally expanded and contracted. The one-way normalized character button (C) and the standard character button 0 are vertically expanded and contracted in order to optimize the vertical expansion/contraction alignment between the one-way normalized character button (C) and the standard character button 0 (d). 4- shows a two-way normalized character button, and when the present invention matches the standard character button (a) and the input character button (b), the standard character button (a) and the two-way normalized character button (b) are matched. This realizes alignment with the stroke (d), and as a result, it is possible to absorb the two-dimensional positional deviation of the strokes and recognize the characters.

Figures 2 (-) to (1) are diagrams for explaining means for realizing two-dimensional expansion/contraction matching and their effects;
is the standard character bang, 伽), 22 is the input character bang, (C
23 in ) is the standard projection information on the horizontal axis of the standard character button 21, 24 in (d) is the input projection information on the horizontal axis of the input character pattern 22, and (.) is the standard projection information 2.
3 and the input projection information 24 in the horizontal direction to obtain the mapping function 25f, (f
) is a diagram showing that a one-way stretch normalization button 26 in the horizontal direction of the input character pattern 22 is obtained using the mapping relationship 25, and (g) is a diagram showing that the one-way stretch normalization button 26 and the one-way stretch normalization button 26 of the input character pattern 22 are obtained. This is the next diagram showing that vertical expansion/contraction matching with the standard character button 21 is performed and the mapping function at that time is 27.

In the above explanation, the character pattern used in stretch matching consists of a matrix of MXN, where M is the number of pixels in the horizontal direction and N is the number of pixels in the vertical direction. It is assumed that the projection information on the horizontal axis is described as a one-dimensional vector, that is, a series of M scalar quantities. The horizontal one-way expansion/contraction normalization process of the input character pattern 22 indicated by fC,(r) sequentially expands/contracts and normalizes each of the N M-dimensional vectors.

On the other hand, Figure 2 (+1) is a diagram to show the effect of the horizontal one-way stretching/contraction normalization process. The blank areas indicate areas that are not aligned even if expanded or contracted in the vertical direction. By comparing FIG. 2 (11) and the above-mentioned FIG. 2 (g), it is found that unidirectional horizontal expansion/contraction normalization processing is performed on the input character pattern 22 before vertical expansion/contraction matching processing. The effect is shown.

Figure 2 (1) is a diagram for explaining the case where two-dimensional baton information itself is used instead of projection information for horizontal unidirectional stretching/contraction normalization processing, and the black parts 21 and 22 in the figure are horizontal This is the part that was aligned by expanding and contracting in the direction, and the white blank part shows the part that is difficult to align even if it is expanded and contracted in the horizontal direction, but the alignment is very unstable due to the positional shift of the stroke. I understand that. This one-way horizontal stretching/contraction normalization process greatly affects the accuracy of the next vertical stretching/contraction matching process, and stable matching is required to obtain the mapping function, and for this purpose, information as a character stamp is required. Even if there is a lack of stroke position, it is necessary to use projection information sound that absorbs the positional deviation of the stroke.

FIGS. 3(a) to (=1) are diagrams for explaining an example of the DP matching method used as a one-way expansion/contraction matching process.

Standard pattern AO is M-dimensional vector AO1AO1...
It consists of a series of AO, and the input button A is an M-dimensional vector A.
, f, . . . , 1. Furthermore, if we take continuous matching between an arbitrary vector d of standard methane and an arbitrary vector size of the input capacity (r) as distance f a (t, j), we can find that the degree of difference between the human capacity pattern and the standard pattern AO is D( ASAn) is determined by the following formula, for example.

D (A% An ) = 21 a (1, j) This formula associates ^ and Aol on the mapping function +-1 of the 31st?4 ra) and calculates the degree of dissimilarity between the two patterns. , on the mapping function j-φ(1) in the same figure, if it is possible to make t+-' correspond to 18, then to find the degree of difference between the two patterns,
The input button A can be partially expanded/contracted to match the standard pattern AO.

Does the DP matching method match the input button by partially expanding or contracting it? ) This is a refined method. For example, in Figure 3(b), g(N, N) is calculated from the w-period value and recurrence formula below. By 1:, on the mapping function j = (i) Matching can be achieved by making λ and B completely correspond.

g(1,1)-d C1,1) y(1,j)=a(
t, j) + mtn(g(1-1, j), g(1-1, j
-1), g(1-1, j-2) ] However, a(i, j
)-no (1≦0 or j≦o) T,! , le.

FIG. 3 (0) t:I is a diagram for explaining an example of the DP matching method for obtaining the above recurrence formula, and the input capacitance is 58.
− one-dimensional vectors, i.e. a sequence of 7 colors (1,
2, 4, 5, 5), and the standard pattern is also 5 series CI, 2.3.4.5), and (1, j) is (1,
1), (2,2), (3,4), (4,5), (5,5
) is performed on the mapping function.

Figure 3(d) shows that the recurrence formula calculation is performed within the range of 1-△≦j≦1+Δ in order to reduce the calculation result of the above recurrence formula calculation, and in general, in the DP matching method, ,
This range is called the matching window, and is actually used to improve the efficiency of calculations. The above recurrence formula is only for calculating the degree of dissimilarity, but mtn(gD-1, j), g(1-1, j
-1), g(1-1, j-2)) = g(1-1, j
)(i-1) (where j 1 is j, j-1, or j-2) Cr-1) Then, as h(z, j)=, +・゛, the function h
(1, j)(+-4), h(
i, j) sequentially from b (NXN) 1 turtle (1, 1
)′! ! The mapping function can be found by finding.

For example, in Figure 3 (in the example (1), h(5,5) h(5
,5)=5,h(4,5)=4,h(3,4)=2,h
Since (2, 2) = 1, the mapping function (1, j) is (1
,1),(2,2),(3,4),(4,5),(5,
5) and request 1Z).

Figure 4 is a diagram for showing an example of a1 standardization processing, where X(,1) (1≦1≦16) Fi person kabatan Y
(j) (1≦j≦16) is expansion/contraction II] normalization bang,
j=φ(1) is a mapping function for expansion/contraction normalization. In this example, Y (j) is >i2 according to the following rule.

(1) j=16(1)>ψ(1-1) and p<IKψ
When (1-1-1), Y(j)=X(1)(2) j=
'p(1)""φ(1-1)+217) when Y(,+
-t) -X(on(3)j-φ(1)=φ(1-IK
4) When (1-1-1) Y(+)=E1) Figure 5 (
-), (b), (0), (d) 2 for every 1i partial bang
FIG. 6 is a diagram showing the effect of performing direction expansion/contraction matching. Fifth
Figure (IL) Fi standard character button (b) is an input button that has been subjected to non-linear expansion/contraction processing in the horizontal direction based on projection information on the horizontal axis. Since the relative positional relationship between the ``day'' and the ``side group'' is different between (a) and color), if you perform expansion/contraction matching in the vertical direction in units of horizontal rows, the input button will be, for example, (d ), but in this case, (6) and (d
) is the part that was not aligned even if you performed stretch alignment because the relative positional relationship between the bias and the side is different? Showing 1
There are 7. However, it is clear from the previous explanation that if the ranges AB and BC in the figure are expanded and contracted independently in the direction l/r,,% perpendicular to each other, the relative position will match with the yield of 1-metal. It is.

FIGS. 5(e), (f), and (g) (colors) are diagrams of another example for illustrating the effect of performing two-way expansion/contraction matching for each partial button. (e) is a standard character batan, and (f) is a large kabatan that has been subjected to nonlinear expansion/contraction matching processing in the vertical direction based on projection information on the vertical axis. In (e) and (f), the relative positions of ``tate'' and ``日'' are different, so if you perform expansion/contraction alignment in the horizontal direction in units of vertical columns, the input button will be However, in this case, the blank areas in (g) and color) indicate areas that were not aligned. However, if the range AB and the range BC in the figure are independently expanded and contracted in the horizontal direction, the relative positional deviation can be absorbed and the alignment can be achieved.

FIG. 6 is a block diagram showing an example of the configuration of the present invention. Reference numeral 100 is an input character slam signal, and 1 is an input character 12-bang storage section that stores the input character bang. Reference numeral 2 denotes a projection information extraction means, which receives input character slams from the input character button storage unit 2 as a signal 101.
The projection information histogram on the horizontal axis is obtained and output as a projection information signal 102. This is a 3-digit mapping relationship generating means, which outputs the projection information signal 102 and the projection information signal -Ii! to the standard projection information storage section 4. A mapping function between the standard projection information signal 104 and the standard projection information signal 104 for each character type to be read stored in the same format as 102 is determined and output as a mapping function signal 103. A 5-digit two-dimensional expansion/contraction matching means reads the input character bang signal 101, performs one-way expansion/contraction normalization processing using the mapping function for each read JIV character type read as the signal 103, and stores the standard character bang. The position information of the standard character button and partial button of the type of bubble characters to be read corresponding to the mapping relationship stored in the section 6 is read as a signal 106, and the vertical direction is determined for each partial pattern using the position information. Performs expansion/contraction matching to obtain the total degree of dissimilarity, softens the degree of dissimilarity of each partial pattern as the degree of dissimilarity between the human input character BUTTON and the read character type, and outputs it as a total dissimilarity signal 105 between the input character BUTTON and each read character type. do. The identification means 7 reads the degree of difference from each character type to be read as a signal 1°5, and for example, simply outputs the character type with the smallest degree of difference, or *:
Or, when the difference between the smallest dissimilarity and the second smallest dissimilarity is greater than a certain value, the character type with the smallest dissimilarity is used as the output result, and in other cases, it is output? The recognition result is output as a signal 107 using a normal method for character recognition, such as outputting the result.
Output as .

In the above description, the input button storage section 1 and the projection information extraction means 2 may be a book generally used in the button processing.

FIG. 7 is a block diagram showing an example of the configuration of the mapping function generating means 3. The process here is to calculate g(1, j) of the recurrence formula in the explanation of the DP matching method above, and find the trajectory h(i, j) obtained as a result of the recurrence formula calculation.
j) to find the mapping function. 102 is the projection information signal, which is a series of scalar quantities A , A , . . .
1, and 104 is the standard projection information signal, which is a scalar quantity NOR array A+11, A&, . . . for each character type to be read.
・,A+l''K Corresponding C, 31 C Distance tTtf Calculate d(1,j) using human power in the distance tTtf calculating section 1-
1 signal 311. 32 is a recurrence formula calculation unit that calculates the recurrence formula %(1 j-1), g(i I, j-2)) written in #, and a(Z, j) is sent to the signal 311, win( g(1
-1, j), g(1-1sj-1), g(t-t, j-
2)) Input as 1ft signal 341 and calculate g(
1, j) is output to the cumulative value storage section 33 as a signal 321. 34 is a minimum value selection section which selects g(1-1,j), g(l-1,j-1) and g(
i I, j-2) as signal 331, signal 332 and signal 333, m1n(g(1-1, j), g
(1-11, +-t), gc i-t, j-z)
) as the signal 341, and h(', j)? It is output to the mapping locus storage section 35 as a signal 342. When the adaptation formula calculation is completed, the mapping function is sent to the signal 103 from the mapping locus storage section 35.
Output as .

FIG. 8 is a block diagram showing an example of the configuration of the two-dimensional expansion/contraction matching module 5. As shown in FIG. Reference numeral 51 denotes a one-way expansion/contraction normalization means, which extracts all the one-way expansion/contraction normalization means 510 bang signals corresponding to each character type to be read from the input character bang signal 101 and the mapping function signal 103 corresponding to each character type to be read. Output. Reference numeral 52 denotes a character slam expansion/contraction matching means, which corresponds to each of the nine character types to be read from the one-way expansion/contraction normalized character bang signal 511 and the position information signal 106 of the standard character pattern and partial button corresponding to each character type to be read. The degree of difference obtained is output as a signal 105.

The expansion/contraction normalization means 51 reads the input character button 101 as a series of vectors ^, X, . . .
According to the rules explained in the figure, the vectors i, ^,...
The XN series is output as a signal 510, which is a unidirectionally expanded/contracted normalized character pattern. This one-way expansion/contraction normalized character stamp is obtained for each type of character to be read. That is, a unidirectionally expanded/contracted normalized character pattern is outputted as a signal 510 in the 111th order for the mapping function corresponding to each character type to be read.

FIG. 9 is a pull diagram showing an example of the configuration of the character baton wire drawing matching means 52. The 521-digit matching 15 partial button selection section reads the stretchable normalized character button 510, the standard character pattern, and the partial button position information signal 106, and uses the partial button position information to select the corresponding portions of the stretchable normalized character button and the standard character button. Signal pair of patterns 52
11, the output is performed sequentially.

Reference numeral 522 denotes a partial button expansion/contraction matching means, which determines the degree of difference in expansion/contraction matching between the corresponding partial pattern of the standard character pattern and the expansion/contraction normalized character button inputted as a signal 5211, and outputs the degree of difference as a signal 5221.

Reference numeral 523 denotes a difference m'' adding means which sequentially reads the difference degree of each partial pattern as a signal 5221 and outputs the difference degree obtained as the summation as a signal 105.

FIG. 10 is a pull diagram showing an example of the configuration of the partial flap expansion/contraction matching means 522. As shown in FIG. 524 is a vector distance operation part 111, and signals 5211/:
Then, the distance calculation of d(1, j) using the DP matching method is performed, and the result is output as a signal 5241. In the 525-digit acclimation expression performance section, the recurrence expression calculation section 32 of the mapping function generation means 3
and 1+y4-, and 16- recurrence formula g(i, j)=d(i, j)+min(g(i-
1, j), g (1-t, j-1), g (1-1, 3-2
)), where a(t, j) is the signal 5241, and min (g(i-1, j), g(1-1
, j-1), g(1-11,+-2)) as the signal 5271
g(i, j) is output as a signal 5251 to the difference cumulative value storage unit 526. Reference numeral 527 denotes a minimum dissimilarity value selection unit, which selects g(1-1
, j ), g(' 1, j-1) and g(il, j
-2) as signal 5261, signal 5262, and signal 52
63, min(g(1-1,j), g(
1-1, j-1), g(1-1, j-2)) as the signal 52
Output as 71. When the recurrence formula operation is completed, the cumulative dissimilarity value storage unit 526 stores the dissimilarity g(N, N
) is output as a signal 105. Through the above processing, the degree of difference between the partial patterns for each character type to be read is determined by the signal 10.
5 and output sequentially.

FIG. 11 is a diagram showing another example of information that can be used as projection information, in which the character stamp is scanned in the vertical direction and the number of times it intersects with the character part is used as the projection information.
The handling is similar to the projection information described above.

According to the above theory tV1, according to the present invention, one-way horizontal expansion/contraction normalization processing is first performed from the projection information of the character baton on the horizontal axis -, and then the partial baton is Character recognition by alignment that absorbs two-dimensional expansion and contraction corresponding to the relative positional shift of the button of the part by performing expansion and contraction alignment in the vertical direction for each button #It111
! can be expressed.

Contrary to the above process 111, by performing unidirectional stretching/contraction normalization processing in the vertical direction from the projection information on the vertical axis of the character button, and then performing all stretching/contraction alignment for each partial button in the horizontal direction, similarly, relative Corresponding to misalignment 1. It is possible to realize character recognition based on two-dimensional expansion/contraction total absorption matching. Further, the two different directions are not limited to the above-mentioned vertical 1u direction and horizontal direction.

In general, many character recognition methods try to improve the effectiveness of the recognition method by normalizing the position and size, smoothing character bumps, blurring, etc., but character VfI according to the present invention
The It method can also obtain the same effect as other methods by performing 1Q preprocessing on input character stamps.

Furthermore, various DP matching methods have been announced, and are not limited to the method described in this specification.

[Brief explanation of the drawing]

Figures 1 (a), (b), (C), and (d) are diagrams for intuitively explaining two-dimensional expansion/contraction matching, and Figures 2 (a) to (
1) is a diagram for explaining the means for realizing two-dimensional expansion/contraction matching and its effects, Figures 3(a) to (d) are diagrams showing an example of the DP matching method, and Figure 4 is a diagram for explaining the means for realizing two-dimensional expansion/contraction matching and its effects. A diagram showing an example of the normalization process; FIGS. 5(-) to (h) are diagrams showing the effect of performing expansion/contraction matching for each partial button;
FIG. 6 is a block diagram showing one embodiment of the present invention, FIG. 7 is a block diagram showing one embodiment of the mapping function generating means 3, and FIG.
The figure is a block diagram showing an embodiment of the two-dimensional stretch matching stage 5, FIG. 9 is a block diagram showing an embodiment of the character slam stretch band matching means 52, and FIG.
FIG. 11 is a block diagram illustrating an embodiment of 22, and FIG. 11 is a diagram illustrating another example of information that can be used as projection information. In the figure, 1 is an input character button storage section, 2 is a projection information extraction means, a three-digit mapping function generation means, 4 is a standard projection information storage section, and 5
6 is a standard character button storage unit; 7 is a two-dimensional expansion/contraction matching means;
digit identification means; 31 is a distance calculation unit; 32 is a digit adaptation formula calculation unit;
33 is a cumulative value storage section, 34 is a minimum value condyle section, 35 is a mapping locus storage section, 51 is a one-way expansion/contraction normalization means, 52 is a character slam expansion/contraction matching means, 521 matching partial button selection sections,
522 partial slam expansion/contraction matching means, 523 dissimilarity addition means, 524 vector distance l1Ilt calculation unit, 525 recurrence formula calculation unit, 526 tJ difference cumulative value storage unit, 527
indicates the minimum difference value selection unit 4. -2 (1- Figure 1 ra) (b) (C) (d) Figure 2 (a) (b) t c) (d
) (e) 躬 2 ba (f) (9) Fig. 2 (/1) (L) Fig. 3 (α) (b) Fig. 3 (C) 1 2345 (d) L Fig. 4 Fig. 5 (Q) (b) (C)
(d)(e)
(f)<g)
(h) Figure 6 Figure 9 Figure 11 Figure 10

Claims (1)

[Claims] Regarding a method for recognizing input character bangs expressed as two-dimensional mesh-like information, an input character bang storage means for storing the input character pattern, and a primary recognition method for each of two different predetermined directions with respect to the input character pattern are provided. projection information extraction means for extracting all of the projection information that is a series of original information; standard projection information created in advance for each character type in the same format as either one of the two projection information of the input character pattern; A standard projection information storage means storing a code indicating one of two directions, projection information of the input character pattern and standard projection information are input, and expansion/contraction of both in the direction determined by the previous code. A mapping function generating means for determining a mapping function that maximizes the measure of consistency, two-dimensional mesh-like standard character buttons created in advance for each character type, and position information of partial characters forming the standard character buttons. and a standard character button storage means for storing all of the characters, a nonlinear expansion/contraction button in one direction of the input character pattern is created using the mapping function, and a standard character button and nonlinear expansion/contraction are created using the position information of the partial pattern. A two-dimensional expansion/contraction matching means that performs expansion/contraction matching for each bang and all parts to determine the degree of dissimilarity, and a degree of difference between the input character pattern obtained as a result of the expansion/contraction matching and the standard character bang of each character type to be read, A character recognition device W0 characterized in that it is capable of absorbing expansion and contraction fluctuations of each partial pattern and performing matching by having an identification means for outputting recognition results.