Recognition of Handprinted Alphanumerics, Symbols and "Katakana" Characters

1. INTRODUCTION

In handprinted character recognition by feature extraction, measured features, such as concav­ ities, loops, or stroke direction etc. are compared to the standard patterns. However, it is necessary to overcome the problems concerned with feature extraction and decision making technique in order to recognize the large number of symbols, as shown in Fig.l.

• (A) The first problem is concerned with noise smoothing. There are many individual patterns, such as ~ '/ '"/ ;t. ;t; :;.. " : 1 · , and ? in Fig .1. Accordingly, if short lines or small points are erased by the noise smoothing operation, some misrecognitions will occur.
• (B) The second problem· is that there are many similar character pairs among the symbols shown in Fig .1. Especially, there are many pairs of topologically the same symbols, such as (O,o,· ), (5, S), (7, 7 ,J r7 ), (9,9 ), (I, I:) , ('I , ::, ) , etc. Therefore, it is necessary to detect many detail features from the charac­ ters so as to discriminate properly between all
• these pairs.
• (C) The third problem is the necessity to use the contextual information. Since symbol and character sizes depend on individual writers, for example, the size of numeral 0 is sometimes the same as the size of special symbol · (P sound · used in combination with katakana). Accordingly, it is difficult to discriminate between numeral 0 and symbol ·

Since the second problem was included, even in the recognition of freely handwritten numerals, auxiliary features were utilized to assist in emphasizing the main recognition features which have a bearing on determining which symbol is being recognized. However, this recognition algorithm cannot conveniently handle more than 100 character symbols. The authors developed a new recognition system which is capable of solving the above mentioned problems for handprinted Japanese katakana characters. After that, the recognition system was extended for special symbols, the mixed use of alphanumerics and special symbols, and the mixed use of alphanumerics and katakana characters.

2. RECOGNITION ALGORITHM

The digitized character is represented by a binary matrix whose maximum dimensions are 64x48 bits. This is the original pattern. The original pattern is smoothed and transfered to a skeleton pattern. Each consecutive sequence of black dots (ones), between a terminal point and its connected terminal point or branch point, is called a wstrokew. If the length of the stroke is shorter than a predetermined value, the short stroke is eliminated from the skeleton pattern. Instead of elimination, their position and direction are sequentially recorded in the memory. These features are mini features. Terminal points and branch points are easily detected from the skeleton pattern. Those positions are stored in the memory according to their detection order. The stroke is traced in order to detect inflection points, and divided into segments which are defined by consecutive sequence of black dots between the terminal points, the inflection points and the branch points on the stroke. The order of strokes is determined by the detection order of terminal point included in each stroke. Direction code, as shown in Fig.2-l, is given to the segment. The origin of Fig.2-l is corresponding to the preceding singular point detected by tracking. Figure 2-2 is an example of obtained segments, direction codes, and input pattern feature string. Each symbol, used in the input pattern feature string, has one of the following meanings. 0,1,2, ----- 7 : Direction code. ! Stroke tracking ended at a terminal point. K Inflection point. B : Branch point.

First decision is performed by sequentially comparing the input pattern feature string (IPS) to the standard pattern feature strings (SPSs) with category name. The structure of each SPS is similar to that of IPS. After comparing, if no SPS is found, the character is rejected, if unique category SPSs are found, the character is recognized as the SPS category. If SPSs of more than two categories are found, second feature extraction and decision are actuated.

In the second stage, a category, which is most similar to the input character, is determined by a tournament structured decision tree. Each pair of two categories is sequentially combined from the candidate categories. When the winning category is determined by sequentially executing several statements regarding feature extraction and decision (hereafter a feature extraction and decision pair is expressed by FED) , if there are remaining candidate categories, the winning category and first one of the remaining candidate categories become the next pair. When the winning category is not determined, these drawn categories are stored in the drawn categories list and deleted from the candidate categories. If only one candidate remains, the remainder is treated dS the winner. Otherwise, the character is rejected. After all the sequential candidate category combinations, the winning category is confirmed to determine whether the winning category is more similar than all the drawn categories to the input character.

The configuration of the tournament structured decision trees depends on the input character shape. Also, the auxiliary feature to be detected and the parameters, such as the prede­ termined threshold, depend on the category pair. The auxiliary feature name and its parameters are described in an FED. The format of each FED is as follows.

Cl C2 F pl p2 ··. pm dl d2 ..· dn tl t2 s nb nt

Each symbol has the following meaning.

Cl: First category name. It is always necessary. C2: Second category name or logical mark. The second category name is necessary when pair categories are distinguished by the current single FED or at the first FED for a logical combination of FEDs. LOgical mark is used when the current FED is logically combined with the preceding FEDs. pl p2 ··· pm: Singular point name (Bi, Ti, Ki, BI, TI). Bi, Ti, or Ki is i-th branch, terminal, or inflection point respectively. TI or BI is a terminal or branch point connected with another directly assigned point, respectively.

dl d2 ··· dn: Parameters for feature extraction area size or directions for measuring the feature, etc.

F: Auxiliary feature name. Example of auxiliary features are as follows. a Distance between assigned two points vs. the-distance between two other assigned points ratio. b Examine whether an assigned direction mini feature is in the assigned region. c The concavity or convex value in the area determined by two assigned points. d Current character height vs. preceding character height ratio. In execution time, a feature extract i on routine is called by an auxiliary feature name in an FED. The measured feature value f is recorded in a temporary memory.

tl t2 s: Functions of these parameters ar e defined in Table 1

nb nt: Numbers of branch points and terminal points respectively.

A series of FEDs for pair categories Ci and Cj, as shown in Table 2, constructs a decision tree as shown in Fig.3. Feature Fi value is represented by fi in Fig.3.

~HARDWARE IMPLEMENTATION. AND CONCLUSION

The recognition algorithm was implemented in an actual OCR N6370 system. The original pattern is preprocessed in LSis, which were developed for the OCR. Feature detection and decision are carried out by a micro computer. The feature detection program and decision program are recorded in 20k bytes of the micro program memory. The SPSs and the FEDs are recorded in 64k bytes of the data memory. Design work was laborious because the design concept depended on theheuristicsof the designer and recognition experi­ mentation. Instead, an economical OCR system has been successfully developed. The OCR can recognize 100 characters/sec.