Apparatus and method for syntactic signal analysis

• US 5,550,934 A
• Filed: 11/27/1995
• Issued: 08/27/1996
• Est. Priority Date: 02/19/1993
• Status: Expired due to Term

• Current Assignee: Oce-Nederland B.V. (Canon Inc.)
• Original Assignee: Oce-Nederland B.V. (Canon Inc.)
• Inventors: Cremers, Louis M. G., Heemels, Robertus P. E. H., Van Vliembergen, Eduardus J. W., Hommersom, Frederik J., Gerritsen, Jan
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/562,787
• Time in Patent Office: 274 Days
• Field of Search: 382/324, 382/229, 382/230, 382/231, 395/50, 395/54, 395/62, 395/63
• US Class Current: 382/229
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18171 Syntactic representation, e.g. using a grammatical approach
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

An apparatus and method for syntactic signal analysis which is suitable for processing signals which deviate, within a freely selected margin, from a set of signals predetermined by a grammar, the apparatus being provided with a feature unification mechanism which detects violations of features, and an adaptive threshold mechanism coupled thereto. The feature unification mechanism, which processes the features in groups so that rapid processing is obtained, determines a violation score, thus providing a measure of the deviation of the analyzed signal from the set of signals predetermined by the grammar and indicates what elements of the signal are not satisfactory so that these can be corrected if necessary. The adaptive threshold mechanism enables a number of analyses to be delivered each having a violation score, so that on the basis thereof, in combination with other factors which may be available, it is possible to select the best analysis. The apparatus is applicable to signal correction, signal verification and signal recognition.

Claims

1. An apparatus for syntactic signal analysis, comprising:

primitive conversion means for converting an input signal to a string of primitives;

normalized primitive conversion means, responsive to the primitive conversion means, for converting the primitives to a corresponding string of normalized primitives;

wherein conversion from a primitive to a set of at least one normalized primitive results in a loss of information content;

feature extraction means, responsive to the primitive conversion means and the normalized primitive conversion means, for at least partially restoring the loss of information content, between a primitive and the corresponding set of at least one normalized primitive, by extracting features associated with a primitive;

grouping means, responsive to the feature extraction means, for grouping the features extracted from a primitive into at least one current feature group corresponding to the primitive;

assignment means, responsive to the grouping means, for assigning, relative to a particular primitive, the at least one current feature group to the normalized primitives to which the particular primitive corresponds;

a memory for storing a grammar, the grammar including;

grammar rules; and

declared feature groups;

a grammar rule establishing a relationship between a non-terminal and a replaceable set of terms, the rule permitting an occurrence of the replaceable set to be replaced by the non-terminal;

the terms in the replaceable set including at least one of a terminal, a non-terminal, and an empty-symbol, a terminal being equivalent to a normalized primitive;

a declared feature group being associated with the non-terminals and with the replaceable sets of the reduction rules;

parsing means, responsive to the normalized primitive conversion means and operatively interconnected to the memory, for shifting the stream of normalized primitives onto a stack as terms in the stack until a grammar rule is satisfied, and for applying the grammar rule to replace a replaceable set of terms on the stack with a non-terminal;

feature checking means, operatively connected to the memory, responsive to the assignment means and parsing means when the parsing means determines that a grammar rule is satisfied, for processing a current feature group, associated with a replaceable set of terms of the satisfied grammar rule, to produce a violation score if the grammar rule and the corresponding declared feature groups are not satisfied perfectly;

production of the violation score by the feature checking means enabling a sequence of normalized primitives, that would otherwise not satisfy any grammar rule not having feature groups corresponding thereto, to satisfy at least one grammar rule and the corresponding declared feature groups, albeit to a lesser degree of satisfaction than a situation where no violation score is generated.

2. An apparatus according to claim 1, wherein said apparatus further comprises:

breaking means for breaking off parsing if the violation score exceeds a threshold value; and

threshold means for raising the threshold value if the violation score exceeds the threshold value; and

means, responsive to the threshold means, for re-starting parsing.

3. An apparatus according to claim 1, wherein said apparatus further comprises:

correction means, which are activated if the violation score is unequal to zero, for applying secondary grammar rules not present in the grammar to a second sequence of normalized primitives, the second sequence being longer than a first sequence which generated the violation score, the second sequence including the first sequence, such that the correction means takes advantage of context provided by the longer second sequence to thereby resolve the violation.

4. An apparatus according to claim 1, wherein said apparatus further comprises:

warning means, which are activated in dependence on the violation score, for producing a warning signal.

5. An apparatus according to claim 1, wherein:

a feature group is represented by a binary number.

6. An apparatus according to claim 1, wherein:

the input signal is an optical signal; and

the primitive conversion means converts the optical signal to an electrical signal.

7. An apparatus for signal analysis according to claim 1, wherein:

said feature extraction means derives mutually exclusive features from a primitive and includes these features in the current feature groups; and

said pattern recognition means processes the mutually exclusive features included in the current feature groups.

8. An apparatus for syntactic signal analysis according to claim 1, wherein:

the memory also is for storing a character image associated with a recognized character and formed by the primitives corresponding to the normalized primitives from the associated input string together with the violation score; and

the apparatus further comprises;

comparison means for comparing a stored violation score with a violation score determined by the feature checking means for one and the same recognized character and for overwriting a stored character image by a character image associated with one and the same recognized character if the comparison means shows that the stored violation score is greater than the violation score of the recognized character.

9. An apparatus for syntactic signal analysis according to claim 7, wherein:

the strings of normalized primitives fed to the parsing means each comprise a number of normalized primitives such that the corresponding syntactic analyses in each case comprise a substantially equal number of characters for recognition.

10. An apparatus for syntactic signal analysis according to claim 8, wherein:

the strings of normalized primitives fed to the parsing means each comprise a number of normalized primitives such that the corresponding syntactic analyses in each case comprise a substantially equal number of characters for recognition.

11. An apparatus according to claim 9, wherein:

the successive strings of normalized primitives fed to the parsing means overlap one another.

12. An apparatus according to claim 10, wherein:

the successive strings of normalized primitives fed to the parsing means overlap one another.

13. An apparatus as in claim 1, wherein:

the input signal is transformed into a plurality of pixels; and

the feature-extraction means derives current features as a function of the geometry of pixels encompassed by the primitive.

14. An apparatus as in claim 1, wherein:

each grammar rule in the grammar is a one-dimensional relationship between at least one of terminals and terminals, terminals and non-terminals, and non-terminals and non-terminals.

15. An apparatus as in claim 14, wherein:

at least one grammar rule is concatenation.

16. An apparatus as in claim 1, wherein:

the feature checking means process a current feature group in at least one of the following ways;

by determining if all the features in a declared feature group are present in a current feature group, and assigning a violation to the non-terminal if not;

by determining whether all the features, in a current feature group associated with the replaceable set of the reduction rule, are consistent, and assigning a violation to the non-terminal of the reduction rule if not; and

by determining whether all the features in a declared feature group associated with a non-terminal of the reduction rule will be present, according to a number of features present in the current feature group associated with the replaceable set reduced by the reduction rule, and assigning a violation score to the non-terminal if not.

17. A method as in claim 1, wherein:

the step i) of processing a current feature group processes a current feature group in at least one of the following ways;

by determining if all the features in a declared feature group are present in a current feature group, and assigning a violation to the non-terminal if not;

by determining whether all the features, in a current feature group associated with the replaceable set of the reduction rule, are consistent, and assigning a violation to the non-terminal of the reduction rule if not; and

by determining whether all the features in a declared feature group associated with a non-terminal of the reduction rule will be present, according to a number of features present in the current feature group associated with the replaceable set reduced by the reduction rule, and assigning a violation score to the non-terminal if not.

18. An apparatus as in claim 1, wherein:

the input signal is an electrical signal representing text information.

19. An apparatus as in claim 1, wherein:

the stack used by the parsing means is a graph-structured stack.

25. A method according to claim 1, further comprising:

j) providing a warning if one of the following occurs;

parsing does not deliver a solution; and

the violation score exceeds an adjustable value.

20. A computer-implemented method for syntactic signal analysis, the computer performing the steps comprising:

a) converting signal, input to the computer, to a string of primitives;

b) converting the primitives to a corresponding string of normalized primitives;

wherein conversion from a primitive to a set of at least one normalized primitive results in a loss of information content;

c) at least partially restoring the loss of information content, between a primitive and the corresponding set of at least one normalized primitive, by extracting features associated with a primitive;

d) grouping the features extracted from a primitive into at least one current feature group corresponding to the primitive;

e) assigning, relative to a particular primitive, the at least one current feature group to the normalized primitives to which the particular primitive corresponds;

f) storing a grammar into a memory accessible by the computer, the grammar including;

grammar rules; and

declared feature groups;

a grammar rule establishing a relationship between a non-terminal and a replaceable set of terms, the rule permitting an occurrence of the replaceable set to be replaced by the non-terminal;

the terms in the replaceable set including at least one of a terminal, a non-terminal, and an empty-symbol, a terminal being equivalent to a normalized primitive;

a declared feature group being associated with the non-terminals and with the replaceable sets of the reduction rules;

g) shifting the stream of normalized primitives onto a stack as terms in the stack until a grammar rule is satisfied;

h) applying the satisfied grammar rule to replace a replaceable set of terms on the stack with a non-terminal;

i) processing a current feature group, associated with a replaceable set of terms of the satisfied grammar rule, to produce a violation score if the grammar rule and the corresponding declared feature groups are not satisfied perfectly;

production of the violation score by the step i) enabling a sequence of normalized primitives, that would otherwise not satisfy any grammar rule not having feature groups corresponding thereto, to satisfy at least one grammar rule and the corresponding declared feature groups, albeit to a lesser degree of satisfaction than a situation where no violation score is generated.

21. A method according to claim 20, further comprising:

if the violation score exceeds a threshold value, then;

j) breaking off parsing;

k) increasing the threshold value to the value of the violation score summed up with an adjustable value; and

l) restarting parsing of the string of normalized primitives.

22. A method according to claim 20, further comprising:

j) selecting, if parsing yields at least two solutions, solution having the lowest violation score.

23. A method according to claim 20, further comprising:

j) applying if the violation score is unequal to zero, secondary grammar rules not present in the grammar to a second sequence of normalized primitives, the second sequence being longer than a first sequence which generated the violation score, the second sequence including the first sequence, so as to take advantage of context provided by the longer second sequence to thereby resolve the violation.

24. A method according to claim 23, wherein said step j) comprises:

j1) adapting a primitive on the basis of the analysis delivered by the parser.

26. A method according to claim 20, wherein step c) includes the step of:

c1) coding feature groups to form binary numbers.

27. A method as in claim 20, wherein the step a) of converting includes:

a1) providing an optical signal to a scanner; and

a2) transforming, via scanner, the optical signal into an electrical signal.

28. A method as in claim 20, wherein:

the step a) converts the input signal into a plurality of pixels; and

wherein the step c), the computer extracts features as a function of the geometry of pixels encompassed by the primitive.

29. A method as in claim 20, wherein:

each grammar rule in the grammar is a one-dimensional relationship between at least one of terminals and terminals, terminals and non-terminals, and non-terminals and non-terminals.

30. A method as in claim 29, wherein:

at least one grammar rule is concatenation.

31. A method as in claim 20, wherein:

the input signal is an electrical signal representing text information.

32. A method as in claim 20, wherein:

the stack used by the step g) of parsing is a graph-structured stack.