ON PATTERN DESCRIPTION AND ANALYSIS FOR SYNTACTIC PATTERN RECOGNITION WITH APPLICATION TO CHINESE CHARACTER RECOGNITION

Abstract

Three main issues prevail in syntactic pattern recognition: pattern description, pattern analysis and grammatical inference. Pattern description concerns the use of pattern grammars for describing general patterns. Pattern analysis concerns the analysis of the structures of input patterns using a parser, and the classification of input patterns to their respective classes. Grammatical inference is similar to the learning process in general pattern recognition problem except that the knowledge to be acquired are the grammars that describe the patterns. Since grammatical inference is a research topic on its own right, it is not discussed in this thesis. The emphasis of this thesis is on the description and analysis of general patterns. With the use of examples, the author illustrates some of the well-known grammars and parsers, and their shortcomings in describing and analyzing general patterns. These shortcomings include the inadequacy of the grammars in describing general patterns, and the inefficiency of the parsers for parsing complex patterns. To overcome these shortcomings, the author proposes an augmented plex grammar and a heuristic parser for pattern description and analysis, respectively. The augmented plex grammar is an enhanced version of the original plex grammar first proposed by Feder. It includes facilities for describing complex relationships among the components of a pattern. It allows the inclusion of attributes for more precise description of the patterns. Furthermore, error-corrections are incorporated in to the grammar to handle distortion of input patterns resulting from noise corruption. The most important feature that distinguish this grammar from common grammars is that there is only one grammar for all the patterns concerned. All these patterns share the productions in the same grammar. The heuristic parser is a general bottom-up parser. It is precisely the bottom-up approach and the single-grammar concept that enable the application of heuristic search strategies on the parsing algorithm. In other words, the parsing problem is transformed into a state-space search problem which can be solved using well-known methods. The use of heuristic strategies greatly reduces the computational effort required to parse the input patterns. To study the performance of the parser, the author selected handprinted Chinese characters as test samples. These characters are chosen for their complexity in structures and richness in variants which are most appropriate for testing the adequacy of the grammar and the efficiency of the parser. Experimental results show that, indeed, the augmented plex grammar and the heuristic parser have largely fulfilled their requirements.