JPH041385B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a character reading device that reads characters such as numbers recorded on a form and generates a code representing the characters.

In conventional devices of this kind, characters recorded on a form are optically scanned to generate a binary signal corresponding to black and white, and a logic "1" is stored in the memory element at the address position corresponding to the coordinate position of the black part. The character pattern is stored by writing the signal, and the character contour is detected from this character pattern. is divided into these three types of line segments, and in the order of their appearance when examining the character outline in a counterclockwise direction, for example, the concave part is represented by the code 3, the end point is represented by the code 2,
By representing the convex part with the code 1, the character outline is displayed with a code string representing each line segment of the character outline, and the recognition dictionary is searched for a code string that is the same as this code string, and each of the matching codes is For each corresponding code in a string, the similarity in shape between the line segments represented by the code was examined, and the character corresponding to the code string that was most similar overall was determined to be the character name of the character pattern. .

According to the conventional method explained above, the size of the character size with respect to the size of the frame in which one character is to be placed, the deviation of the character center point from the center point of the frame, the angle of each stroke with respect to the frame, and the angle of each stroke with respect to the frame, If size differences do not affect character reading and the types of characters to be read are limited, the characters can be easily read using the above conventional method, so the type of character outline can be Characters were read according to the sequence of the code strings they represented.

However, even if it is the same character, different code strings may be detected depending on the habits of the person writing it in. To deal with such cases, the recognition dictionary above stores multiple code strings for the same character. However, there were disadvantages such as requiring a large storage capacity as a recognition dictionary and reducing recognition accuracy.

This invention was made in order to eliminate the above-mentioned drawbacks of the conventional ones, and improves recognition accuracy by absorbing variations in the code string that occur due to the habits of the person writing the same character in the matching section with the recognition dictionary. The purpose is to provide a character reading device.

Embodiments of the invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing one embodiment of the present invention, in which 1 is a pattern observation storage device, 2
3 is a contour detection device, 3 is a code string detection device, 4 is a line segment feature extraction device, 5 is a recognition dictionary, and 6 is a dissimilarity calculation device.

The characters to be read are recorded on the form, and therefore each character is contained within a frame of a predetermined area. When a photoelectric conversion device such as a television camera scans the frame of the predetermined area, the area is divided into a large number of pixels, and an electric signal train corresponding to the gray level of each pixel is obtained. This electrical signal string is converted into a binary signal corresponding to black and white, and a logic "1" signal is written into the memory element corresponding to the black pixel in the array of memory elements arranged in a similar shape to the array of pixels. A so-called character pattern is stored in the array of memory elements written in this way.

FIG. 2 shows character patterns stored by the arrangement of the memory elements described above, in which a character pattern to be read is shown in the figure, and a reference character pattern is shown in FIG. 2 b in the memory array arranged in the shaded area. A logic "1" signal is stored in one memory element, and a logic "0" signal is stored in the other memory elements. However, the second
The boundary of the memory element array corresponding to a frame of a predetermined area in which one character is stored is not shown in the figure. 1st
The pattern observation and storage device 1 shown in the figure generates a character pattern shown in FIG. 2a from characters recorded on a form and stores it.

The contour line detection device 2 detects contour lines from the character pattern 7 (the shaded area in FIG. 2A) stored in the pattern observation storage device 1. The contour is easily detected because it is made up of logical ``1'' bits adjacent to logical ``0'' bits.
Next, the code string detection device 3 is similar to the conventional example,
For example, each line segment constituting the contour line is classified into three types according to the characteristics of the line segment. The three types are concave portions, convex portions, and end point portions. In Fig. 2a, broken lines are added to the outside of the contour portion and indicated by the numbers 9 to 19, and the line segments are 9, 10, and 11. ,1
2 and 13 are end point parts, 14, 15, 16,
17 and 18 are concave portions, and 19 is a convex portion.
Convex parts, end points, and concave parts are represented by their respective codes.
For example, a convex portion is represented by a code of 1, an end point is represented by a code of 2, and a concave portion is represented by a code of 3. In this way, each line segment expressed by code starts from end point 9, 9 → 14 → 10 → 15 → 11 → 16 → 12 →
The codes are coded and arranged in the order of appearance traced counterclockwise, such as 19→17→13→18. The order in which the coded and arranged line segments appear is called a code string, and the code string detection device stores the code string detected as described above.

FIG. 3 shows a code string, and FIG. 3 a shows a code string corresponding to the character pattern 7 shown in FIG. 2 a, and FIG.
indicates a code string corresponding to the reference character pattern 8 shown in FIG. 2b. The code string shown in FIG. 3b is stored in the recognition dictionary 5 as a code string corresponding to the single character "sa". 20, 21, 22, 23, in Figure 2 b
24, 25 are end point parts, 26, 27, 28, 29,
30 and 31 are concave portions, and 32 is a convex portion. By the way, in the character pattern 7 shown in FIG. 2a, the end point 21 in FIG. 2 b is not represented due to the habit of the person filling it in, and therefore the concave portions 26 and 27 and the part corresponding to the end point 21 are incorrectly displayed. The recess 14 is shown as one recess 14 . Therefore, the code string in FIG. 3a does not match the code string in FIG. Therefore, in order to read the simple character "sa", the code string shown in FIG. 3b in the recognition dictionary 5 corresponding to "sa" is insufficient.
Corresponding to character pattern 7 as shown in Figure 2 a, the third
The code string shown in Figure a also had to be provided.

However, the order of each line segment obtained by contour tracing is defined. For example, the order in which end points 10, 11, and 12 appear in FIG. 2 is always in this order, and the order is never changed, so the
If we shift the correspondence of the signs in diagrams a and b as shown by the arrows, we get
The code string in FIG. 3a matches the code string in FIG. 3b, and the arrows never intersect, allowing line segments that should originally correspond to each other to be associated with each other. In this embodiment, the code string in FIG. 3a has the minimum degree of difference from the code string in FIG. 3b by using the above law, and the code string in FIG. Decide that it should be read as "sa".

Next, a specific method for associating code strings and a method for calculating a degree of difference will be explained. The line segment feature extraction device 4 extracts and stores the center position of each line segment stored as a code string as a feature of the line segment, for example, using the lower left point of a circumscribed rectangle of a character as a reference point.

On the other hand, for all types of characters to be recorded on a form (usually numbers, Roman letters, kana characters, etc., and the number of types of characters is relatively small), the standard character pattern (for example, Figure 2 b) The recognition dictionary 5 stores a code string (for example, FIG. 3b) detected in advance from 8) and the coordinate position of the center point corresponding to each code of this code string.

The dissimilarity calculation device 6 calculates the equation (1 ), the degree of difference D _o between the inputted v-shaped pattern and the reference character pattern n is calculated.
In other words, the degree of dissimilarity is calculated by examining the similarity of the shapes of the line segments represented by each code in all combinations of the correspondence between the code string of the input character pattern and the code string of the reference character pattern n. Calculate and find the combination that minimizes the degree of dissimilarity. Then, let the minimum value of this degree of difference be D _o .

D _o = min {〓 1kk ₀ 〓 1ll ₀ (d _ikjl + K _ikjl ) + S×u} ...(1) However, in this case, the conditions are I ₁ <I ₂ <...<I _n ...(2) J ₁ < Introduce J ₂ <…<J _n …(3). In the above formula, k ₀ is the length of the code string of the input character pattern (for example, Figure 3 a), and l ₀ is the code string of the reference character pattern (for example, Figure 3 b)
m is the number of associated code pairs (for example, the number of arrows in Figure 3), i _k is the kth code appearing in the code string of the input character pattern, and j _l is the code of the reference character pattern. Indicates the lth code appearing in the code string. I ₁ ...I _n indicates the k of the corresponding code i _k arranged in descending order, and J ₁ ...J _n indicates the 1 of the code J ₁ corresponding to the codes i _I1 - i _In arranged in the order of correspondence. The conditions of equations (2) and (3) represent the conditions under which the arrows in FIG. 3 do not intersect. d _ikjl is the coordinate position of the center point of the line segment corresponding to the code i _k (X _il , X _il ) and the coordinate position of the center point of the line segment corresponding to the code j _l (X _jk ,
The Euclidean distance from Y _jk ) is given by d _ikjl = √( _ik − _jl ) ² + ( _ik − _jl ) ² ……(4). K _ikjl is if the sign i _k and the sign j _l are different,
This is a constant predetermined for each combination of codes to make it difficult to respond, and if they are the same, K _ikjl
=0.

u=K ₀ +l ₀ −2 _n (5) is the total number of uncorrelated codes, and S is a constant for increasing the degree of dissimilarity for the uncorrelated line segments.

Since the conditions of equations (2) and (3) exist, the degree of dissimilarity can be calculated using equation (1).
D _o can be calculated efficiently using dynamic programming. For example, the degree of difference between the two code strings shown in FIG. 3 a and b is i _k shown by the arrow in FIG. 3,
It becomes min when there is a correspondence relationship of j _l . However, it goes without saying that K _ikjl should be set relatively large and S should be set relatively small.

As described above, the degrees of difference between the input character pattern 7 and all reference patterns in the recognition dictionary 5 are determined, and the character name of the standard pattern with the minimum degree of difference is determined as the character name of the input character pattern 7. .

With the above configuration, even if the code strings of the input character pattern and the reference character pattern are different, dynamic programming can be used to determine the optimal correspondence between the code strings. Since the degree of difference can be determined to determine the degree of difference, a flexible character reading device can be constructed without increasing the number of reference character patterns.

Note that in the above example, the correspondence between line segments is 1
Although the case of one-to-one or one-to-zero has been described, it goes without saying that one-to-multiple correspondences may also be added. Further, although the coordinate position of the center point is used as the feature of the line segment, other structural analysis features such as the length of the line segment may be used.

As described above, according to the present invention, dynamic programming is used to match an input character pattern with a different code string to a standard character pattern, so a standard code string is prepared even for deformed characters. Characters can be read flexibly without any need for reading.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is a diagram showing outline segments of an input character pattern and a reference character pattern, and FIG. 3 is a diagram showing a code string corresponding to FIG. be. DESCRIPTION OF SYMBOLS 1... Pattern observation storage device, 2... Contour line detection device, 3... Code string detection device, 4... Line segment feature extraction device, 5... Recognition dictionary, 6... Dissimilarity calculation device.

Claims (1)

[Claims] 1. By optically scanning the characters recorded on the form to generate a binary signal corresponding to black and white, and writing a signal of a predetermined logic to the memory element at the address position corresponding to the coordinate position of the black part. a character pattern observation and storage device that stores character patterns; a contour detection device that detects character contours from the character patterns stored in the character pattern observation and storage device; The contour line is divided into three types of line segments: concave parts, convex parts, and end points based on the refraction information, each type of line segment is represented by a different code, and these three types of codes are arranged in the order in which the above line segments are connected. a line segment feature extraction device that detects and stores numerical values representing the characteristics of the line segment, such as the coordinate position of the center point of the line segment; Recognition in which a code string detected in advance from the reference character pattern of the character to be used as a reference for each type of character and a numerical value representing the characteristics of a line segment such as the coordinate position of the center point of the code of this code string are stored. In a character reading device having a dictionary, a code detected by the code string detection device from the storage contents of the code string detection device, the storage contents of the line segment feature extraction device, and the storage contents of the reference character pattern in the recognition dictionary. The degree of correspondence between the line segment type expressed by a different code between the code string of the standard character pattern stored in the recognition dictionary, and the detected code string detected by the line segment feature extraction device and the standard. a dissimilarity calculation device that adds the sum of the degree of coincidence of line segment features such as the coordinates of each center point of a character pattern code string only in a certain direction; A character reading device comprising means for specifying a character name of a character pattern.