Computer-Aided Design for a Reader of Hand-Printed Characters

1. Introduction

Various studies have been car ri ed out on the optimum method of designing the recognition l ogic in pattern recognition. Most works were performed on the methods of deriving the optimum discriminant function (~os tly linear) statistically from compilation of the sets of the features of the characters . l, 2 · 3 · 4 · 5 The character recognition system of this type is founded on the assumption of the statistical independency of character features. Thus the method can be utilized in the recognition of a limited font. However, it is not very effective in the recognition of hand-printed characters which greatly vary in style and size.

Many workers postulated that in the recognition of the hand-printed characters , it is advantageous to extract the detectable features which fit the intuition of a person, such as terminals, end points, curvatures, inflections of the strokes, and use their relative positions and conn ection relations for recognition. b, 7 ' 8

In such a system the method of extraction By

Y. Hoshino and K. Kiji

Central Research Laboratories Nippon Electric Co. , Ltd. Kawasaki, Japan

of the effective features necessary for the recognition is important. However, the derivation of the sequential logic to obtain the sequential relations and the method of construct­ ing the decision tree are more important.

If the extracted features are geometrical we shall be able to cons truct the sequential logic by arranging the features sequentially in accordance with our concept on the featur es of the characters. By means of the logic , satisfactory results will not be obtained from the beginning. It is n ecessary to repeat trials and e rrors concerning design and recognition. In hand-printed characters, it is not sufficient to prepare only one sequential logic for one class of characters. Many more, an average of ten, at least are re ~uired.

In order to recognize even only the numer .. als, more than a hundred sequential logi cs are required. To lassen the allowable degree of deformation in the cha racters increases the number of sequential logics. An enormous amount of labor will be requir ed to produce the sequential logi cs .

So far no effective method has been develop­ ed for the recognition logic that takes sequence

into consideration.

In order to design the sequential logic effectivel y, we developed the CADOCR system which makes the display of diverse r ecognition states possible according to our demands, a ll ows communication between the designer and computer, and permits the revision of the sequential logics easily.

2. CADOCR System

In the design of this system, the following items were taken into consideration.

• ( l) In order to design a sequential logic by trial-and-error, there should be va rious data to revise the sequential l ogic.

Macroscopic reviews such as confusion

mat rix are the most suitable to know the results of overall recognition. But the reviews are not suitable for detecting the defective sequential logic. If more detailed information to modify the sequential logic is required to be known, the information must be derived easily from the macroscopic review.

If a modification of the defective logics is necessary, the response to the modification must be returned immediately in a visual from.

1. In order to let the concept of configuration reflect on the design of sequential logic, the intuitive information such as the sequential logic with the codes suggestive of features and the bit pattern of character figure and its corresponding feature string are needed.
2. It is desirable to have the time from our demand to computer reply made short. The turn-around time should be so short as to be agreeable to the designer.
3. The preparation of hard copies will be developed when we have demand to record important information for future reference.
4. The system is to be made independent of recognition method. The systerl'l. should be used by merely replacing the recognition program.

The system is shown in Fig. 1. The input character is first scanned by a scanner and then analyzed into feature array be means of feature extracting program. The bit pattern o.f input character and feature array are named IPT. The IPT's are collected and stored on magnetic tape as IPT file.

The IPT file is one of the original data of this system. For other original data the sequential logic (SRL) file consisting of SRL's, prepared by use and field in magnetic tape, is used.

The graphic CRT display and the line printer are connected to the central processing unit, NEAC 2200/200 digital computer. 9 The program consists of a system program called CADOCR and a recognition program connected to it.

The block diagram of this system is shown in Fig. 2. There are six function keys used in this system, ADD key to add characters, PEAL key to replace characters, INS key to insert characters, . PTN key for bit pattern display, ASGN key to assign light buttons, and EXEQ key to carry out the program connected to the light button.

When the ASGN key is pressed, the light button is assigned by a light pen. Then the EXEQ key is pressed, and the program corresponding to the name of the light button is carried out.

Seven light buttons have been provided.

DISP Displays the recognition result.

LNPR The information displayed on the CRT is printed in the line printer.

• PARA Display the succeeding detail information corresponding to the parameter such as index of column or row of the matrix.

STOR

RECG

UPDT

• Stores the logical formulas of sequential logic displayed on the CRT into the core memory of central processing unit.
• Recognizes the IPT by means of the sequential logic displayed on the CRT.
• Updates the SRL file by means of the sequential logic displayed on the CRT.

• CALL Calls the confusion matrix. Numerous operations can be performed by the use of function keys, light · buttons, light pen and character keyboard.

3. System Functions

Sequential display of recognition information

In order to find the part of a sequential logic which needs revision, the evolution from overall recognition state to detail state must be observed on the CRT.

The desired parameter, input character class, sequential logic class, input character number of the matrix or the table on the CRT, are as signed by means of the light pen. Effective detail information corresponding to the parameter are presented.

For example, take five classes, "0", "1", "2", "3" and "4". We shall explain what kind of recognition state corresponding to the assigned parameter will be displayed.

Review of confusion Matrix By assigning the light button PARA and pressing the EXEQ key, the Confusion Matrix shown in Fig. 3 is displayed. In the column at the left end, the "0", "1", "2", "3"and "4"indicate the input character classes, and in the row at the upper end, the "0 ", "l ", "2", "3" and "4" indicate the sequential logic classes, viz, the class names. C indicates correct, E substitution error, W wander. (This means correct and incorrect recognition), R reject, and T total.

In this example, out of the total 100 input characters belonging to Class 11 2 11 , 91 characters are displayed as being recognized correctly according to the sequential logics in the Class 11 2 11 , while five and two characters are recognized incorrectly according to the sequential logics in Classes 11 0 11 and 11 3 11 , respectively.

There is one input character which is recognized as correct by the sequential logics in Class 2, but recognized incorrectly by the sequential logics in all the other classes. There is also one input character displayed as rejected by all of the sequential 1 ogi cs.

Review of SRL's in a class When sequen­ tial logic class in Fig. 3 (Confusion Matrix) is designated, the numbers of input characters judged by the various SRL's in the designated class are displayed in a matrix form.

Fig. 4 shows the matrix displayed when the Class 11 0 11 sequential logics in Fig. 3 (Confusion Matrix) was designated. It can be seen that sequential logic 0-2 (seconds equential logic in Class 11 0 11 ) has recognized two of the Class 11 0 11 input characters correctly, but recognized four of the Class 11 2 11 input characters incorrectly.

In this way, we find which sequential logic should be revised.

Review of IPT's in a class When the input character class in Fig. 3 or Fig. 4 is designated, the sequential logics recognizing the input characters of the designated class are displayed in a matrix form.

Fig. 5 shows the matrix displayed when the input character class 11 2 11 in Fig. 3 (Confusion Matrix) was designated. ·

For example, the codes indicate that the input character 2-003 (Third input character in class 11 2 11 ) marked with letter W is shown as being incorrectly recognized by the sequential logic 0-2 and correctly recognized by the sequential logic 2-2. This shows the reason why the value of W in Fig. 3 (Confusion Matrix) was one.

The matrix indicated the detail information relating to the input character Class which cannot be found only by looking at Fig. 3 (Confusion Matrix) and Fig. 4.

Review of SRL When the sequential logic in Fig. 4 or Fig. 5 on the CRT is selected by the light pen, the logical formula of the sequential logic and the feature array of the input characters, which can be recognized correctly or incorrectly by the designated sequential logic, are displayed with codes suggestive of the shapes of input character features. In Fig. 6 are shown the feature arrays (1) of the input characters 0-00 6 which the sequential logic 0-2 in Fig. 4 or Fig. 5 recognized correctly, and (2) of the input characters 2-003, 2-009, 2-010, and 2-0l6which the same sequential logic recognized incorrectly.

From the table, we can determined how to revise the sequential logics.

Review of IPT : When the input character number in Fig. 5 is designated, the feature array of the designated input character and the logical formulas of sequential logic which recognizes the input character correctly or incorrectly, are displayed. Among the sequential logics which reject the character, the sequential logics for letters of the same class as that of the input character are also displayed with the codes, and the places in the logical formula which caused the rejection are pointed out by blinking lights.

Fig. 7 gives the table displayed on a CRT when the input character 2-010 in Fig. 5 is designated. Since input character 2-010 is recognized incorrectly by sequential logic 0-2, the logical formula for the sequential logic 0-2 is displayed. Since the input character 2-010 is also rejected by sequential logics 2-1, 2-2, and 2-3, the causes for the rejection are indicated by blinking when the logical formulas of these sequential logics are displayed.

This serves as an aid to determine how to revise the sequential logics to have the rejected input character recognized correctly.

Revision of Sequential Logic

Sequential logics are revised by means of the function keys of addition, replacement and insertion of characters, when the logical formulas of the sequential logics are displayed in Fig. 6.

Verification of Sequential Logic Revision

After revising the sequential logic, it is essential to see if the recognition ability has improved. For this purpose the STOR and RECG light buttons are used.

When the STOR light button is assigned, the revised logical formula of the sequential logic in the CRT buffer memory is transferred into the central processing unit. When the RECG light button is assigned, the input character recog~ nized by the sequential logic prior to recognized once more by the revised sequential logic, and the result is displayed on the CRT in the same manner as Fig. 6. In this checkup, the input character number with the recognition results differing from those prior to revision, a re displayed by blinking.

Updating Sequential Logic File

When it is verified that the recognition capability of the revised sequential logic is superior to that before revision, the sequential logic file can be updated with the revised sequential logic by assigning the UPDT light button.

Recognition by Updat ed Sequential Logic File

After updating the sequential logic file, if necessary, all of the input characters are recognized once more by the updated sequential logic file, and we can obtain the percentage of the correct recognition of the input characters by assigning the CALL light button.

Hard Copy Order

When we want a hard copy of the information on the CRT, we can have it printed by the line printer by assigning the light button LNPR.

Bit Pattern Display

There are two methods of ordering the display of bit pattern in a form of input character. The first method is to press the PTN key and assign the input character number to be displayed on the CRT by means of the keyboard. The second method is to designate the input character numbers to be displayed on the CRT, while the Fig. 6 is being displayed. The digitized pattern of the designated input character and the feature array are displayed on the CRT.

This display may give means to rev1smg the defective logic more intuitively than feature array. It may also prevent the adoption of ineffective features resulting from the poor printing quality into the sequential logic.

4. Testing

Tests were made of the effectiveness of the system used in the design of hand-printed character recognition logic.

The character samples used were 500 numerals, each written ferrly with pencil inside a frame 8 mm x 6 mm large (0. 32" x 0. 24"). From these input characters, the geometrical features such as stroke end point, curvatures and inflections, and their connection relations were extracted sequentially from the bottom end of the character, and the feature array was made as shown in Fig. 8.

In Fig. 8 each feature is shown with a code. This combination of letters and symbols to· represent the features enables us to conceive the shape of the feature easily. The bit pattern of the input character and the feature array obtained from the bit pattern are shown in Fig. 9.

The sequential logic can be expressed by the transition diagram shown in Fig. 10, Fig. 11 shows the confusion matrix concerning the 500 input cha racters in this investigation.

5. Conclusion

From experiment on the construction of sequential logic utilizing this system, it was found that the labor needed to select the necessary data from a multitude of information was greatly reduced and that the revision of sequentia l logic owing to the character editing function is carried out efficiently. The system was very effective in determining how to construct a sequential logic, and combine two sequential logics, since we can make use of man's highly developed concept of patterns.

In the experiment, magnetic tape was used as an external memory. Wewerenot satisfied with the turn-around time. However, we believe that the problem can be solved by using a large capacity random access memory such as a magnetic disk, instead of magnetic tape.

Acknowledgement

We would like to thank Dr. S. Sekiguchi for his continuous guidance, and Messrs. J, Mita, K. Morita, Y. Watanabe, and K. Sasaki for their helpful discussion and suggestion.