Constrained attribute grammars for syntactic pattern recognition
First Claim
1. In a pattern recognition system, a method for determining that a pattern is invalid according to a predetermined grammar, said pattern comprised of a plurality of terminal subpatterns, said terminal subpatterns representing characters in a language implemented in said grammar, said method comprising the steps of:
- a) generating and storing a language implementation of a predetermined grammar, said predetermined grammar having a plurality of production rules, each of said plurality of production rules including a plurality of nonterminal symbols each capable of having a corresponding constraint for defining multi-dimensional spatial relationships between symbols;
b) receiving and storing an input set of symbols, said set of symbols representing subpatterns of a pattern to be recognized according to said language, each of said symbols having a spatial attribute for identifying a spatial placement of said subpattern;
c) identifying a production rule associated with said input set of symbols;
d) comparing spatial attributes of nonterminal symbols of said identified production rules to spatial attributes of symbols in said input set of symbols according to a corresponding constraint of said identified production rule;
e) determining that no symbols in said input set of symbols satisfy said constraints part of said identified production rule; and
f) returning a signal identifying said pattern as invalid.
2 Assignments
0 Petitions
Accused Products
Abstract
A method for defining and identifying valid patterns for used in a pattern recognition system. The method is particularly well suited for defining and recognizing patterns comprised of subpatterns which have multi-dimensional relationships. The definition portion is embodied in a constrained attribute grammar. The constrained attribute grammar includes nonterminal, keyword and non-keyword symbols, attribute definitions corresponding to each symbol, a set of production rules, and a relevance measure for each of the key symbols. Each of the symbols represents a subpattern. The production rules includes syntactic, semantic, constraints and action portions. It is the production rules which define the dimensional relationships between the various subpatterns. An instantiation of a constrained attribute grammar is called a language. The verification portion is comprised of a parsing scheme that determines validity of a pattern. The verification portion receives a set of input subpatterns provided by a character recognition system and a provided language. When a valid pattern is recognized, a representation of the pattern in a form suitable for use by a data manipulation means is provides as output.
-
Citations
4 Claims
-
1. In a pattern recognition system, a method for determining that a pattern is invalid according to a predetermined grammar, said pattern comprised of a plurality of terminal subpatterns, said terminal subpatterns representing characters in a language implemented in said grammar, said method comprising the steps of:
-
a) generating and storing a language implementation of a predetermined grammar, said predetermined grammar having a plurality of production rules, each of said plurality of production rules including a plurality of nonterminal symbols each capable of having a corresponding constraint for defining multi-dimensional spatial relationships between symbols; b) receiving and storing an input set of symbols, said set of symbols representing subpatterns of a pattern to be recognized according to said language, each of said symbols having a spatial attribute for identifying a spatial placement of said subpattern; c) identifying a production rule associated with said input set of symbols; d) comparing spatial attributes of nonterminal symbols of said identified production rules to spatial attributes of symbols in said input set of symbols according to a corresponding constraint of said identified production rule; e) determining that no symbols in said input set of symbols satisfy said constraints part of said identified production rule; and f) returning a signal identifying said pattern as invalid. - View Dependent Claims (2, 3)
-
-
4. In a pattern recognition system coupled to a scanning means, said scanning means for providing a pattern in the form of a plurality of subpatterns, said pattern recognition system for identifying a pattern as being valid according to a language implementation of a predetermined grammar, said predetermined grammar including a plurality of production rules for defining construction of valid patterns, an improvement to said pattern recognition system, said improvement for recognizing invalid pattern, said improvement comprising:
-
a receiving means for receiving and storing each of said plurality of subpatterns, each of said plurality of subpatterns including a spatial attribute; rule storage means of storing production rules for parsing said plurality of subpatterns, said production rules further including means for defining multi-dimensional spatial relationship between subpatterns; parsing means coupled to said rule storage means, said parsing means for parsing said input subpatterns according to said production rules to identify invalid patterns, said parsing means further comprised of; means for identifying a production rule for a set of input subpatterns; means for determining a spatial relationship between a first subpattern and a second subpattern from said set of input subpatterns; means for identifying a pattern as invalid if said first subpattern and said second subpattern do not have said multi-dimensional spatial relationship of said identified production rule.
-
Specification