US5550934A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for syntactic signal analysis
Assignee: Canon Production Printing Netherlands BV
•
Filing: 1995-11-27
•
Granted: 1996-08-27
•
Expires: 2015-11-27
Abstract
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.
Inventors
- 👤 Eduardus J. W. van Vliembergen
- 👤 Robertus P. E. H. Heemels
- 👤 Louis M. G. Cremers
- 👤 Frederik J. Hommersom
- 👤 Jan Gerritsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 23:50
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/253; G06V; G06V30/00; G06V30/10; G06V30/18; G06V30/18162; G06V30/18171; G06V30/19; G06V30/196; G06V30/1983; G06V30/1985
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
432 words
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.
Claim 2
Independent Claim
432 words
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.
Claim 3
Dependent Claim
51 words
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.
Claim 4
Dependent Claim
82 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
16 words
An apparatus according to claim 1, wherein: a feature group is represented by a binary number.
Claim 7
Dependent Claim
27 words
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.
Claim 8
Dependent Claim
46 words
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.
Claim 9
Dependent Claim
114 words
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.
Claim 10
Dependent Claim
46 words
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.
Claim 11
Dependent Claim
46 words
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.
Claim 12
Dependent Claim
21 words
An apparatus according to claim 9, wherein: the successive strings of normalized primitives fed to the parsing means overlap one another.
Claim 13
Dependent Claim
21 words
An apparatus according to claim 10, wherein: the successive strings of normalized primitives fed to the parsing means overlap one another.
Claim 14
Dependent Claim
36 words
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.
Claim 15
Dependent Claim
32 words
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.
Claim 16
Dependent Claim
14 words
An apparatus as in claim 14, wherein: at least one grammar rule is concatenation.
Claim 17
Dependent Claim
141 words
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.
Claim 18
Dependent Claim
146 words
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.
Claim 19
Dependent Claim
17 words
An apparatus as in claim 1, wherein: the input signal is an electrical signal representing text information.
Claim 20
Dependent Claim
18 words
An apparatus as in claim 1, wherein: the stack used by the parsing means is a graph-structured stack.
Claim 21
Dependent Claim
359 words
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.
Claim 22
Dependent Claim
359 words
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.
Claim 23
Dependent Claim
49 words
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.
Claim 24
Dependent Claim
23 words
A method according to claim 20, further comprising: j) selecting, if parsing yields at least two solutions, solution having the lowest violation score.
Claim 25
Dependent Claim
72 words
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.
Claim 26
Dependent Claim
25 words
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.
Claim 27
Dependent Claim
32 words
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.
Claim 28
Dependent Claim
21 words
A method according to claim 20, wherein step c) includes the step of: c1) coding feature groups to form binary numbers.
Claim 29
Dependent Claim
33 words
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.
Claim 30
Dependent Claim
40 words
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.
Claim 31
Dependent Claim
32 words
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.
Claim 32
Dependent Claim
14 words
A method as in claim 29, wherein: at least one grammar rule is concatenation.
Claim 33
Dependent Claim
17 words
A method as in claim 20, wherein: the input signal is an electrical signal representing text information.
Claim 34
Dependent Claim
20 words
A method as in claim 20, wherein: the stack used by the step g) of parsing is a graph-structured stack.
References Cited (Backward Citations)
US4907285A
Cited
US4933984A
Cited
EP0357344A2
Cited
US5020112A
Cited
EP0513918A1
Cited
US5317647A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-27 | 2000-02-26 | 2000-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-27 | 2004-02-26 | 2004-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-27 | 2008-02-26 | 2008-08-27 | $7700.00 | Window Closed / Lapsed |