The Inference Process of Programmed Attributed Regular Grammars for Character Recognition

摘要

The paper presents the grammar inference engine of a pattern recognition system for character recognition. The input characters are identified, thinned to a one pixel width pattern and a feature-based description is provided. Using the syntactic recognition paradigm, the features are the set of terminals (or terminal symbols) for the application. The feature-based description includes a set of three attributes (i.e. A, B, C) for each feature. The combined feature and attribute description for each input pattern preserves in a more accurate way the structure of the original pattern. The grammar inference engine uses the feature-based description of each input pattern from the training set to build a grammar for each class of patterns. For each input pattern from the training set, the productions (rewriting rules) are derived together with all the necessary elements such as: the nonterminals, branch and testing conditions. Since the grammars are regular, the process of deriving the production rules is simple. All the productions are collected together providing the tags to be consecutive, without gaps. The size of the class grammars is reduced at an acceptable level for further processing using a set of Evans heuristic rules. These algorithms identifies the redundant productions, eliminating those productions and the correspondent nonterminal symbols. The stop criteria for the Evans thinning algorithm makes sure that no further reductions are possible. The last step of the grammar inference process enables the grammar to identify class members which were not in the training set: a cycling production rule. The above built grammars are used by the syntactic (character) classifier to identify the input patterns as being members of a-priori known classes.