Patent US4700401A successfully refreshed from Google Patents.
US4700401A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for character recognition employing a dead-band correlator
Assignee: FOOG Inc A CORP OF
•
Filing: 1986-08-27
•
Granted: 1987-10-13
•
Expires: 2006-08-27
Abstract
Abstract A character recognition system is disclosed utilizing a dead-band correlator for providing recognition of printed typestyles having horizontal and vertical stroke width variations without impairing the resolution required for character feature analysis. The system provides fewer character-to-mask registration errors, simultaneous computation of correlation scores of registration positions of masks with respect to the unknown character to compensate for additional registration errors, improved reject and substitution rates by utilizing unique threshold and separation requirements for masks, lower error rates by using small and large noise filtering and combining dual level acceptance criteria used in conjunction with re-try methods, stroke width normalization to aid in recognition of characters with badly degraded stroke widths, and selection of specific mask sets during multiple typestyle recognition processing than has previously been possible.
Inventors
- 👤 Cary H. Masatsugu
- 👤 Bruce S. Denning
- 👤 Martin N. Nelson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 11:10
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
358 words
An apparatus for recognition of printed characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising a microprocessor for producing processing instructions, character storage means coupled to the microprocessor for storing digital data representing the character to be recognized (character data hereafter), mask means coupled to the microprocessor and the character storage means for automatically providing digital data representing a plurality of typestyle masks (mask data hereafter) for comparison with the character data, processor means coupled to the microprocessor, character storage means and mask means for processing and reprocessing digital data representing mask data and character data in response to instructions received from the microprocessor, and correlation means coupled to the character storage means, the mask means and the processing means for correlating the character data and mask data, said correlation means including means for analyzing digital data representing a selectable dead-band region including a plurality of registration zones on and around a selected pixel within the printed characters which can comprise as many as nine registration zones including a central correlation zone centered on the selected central pixel, center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters left, right, up and down respectively, from the selected central pixel, and up-left, up-right, down-left and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, down and left, and down and right, respectively, from the selected central pixel, means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected character pixel, means for comparing each mask pixel with the corresponding combination of character pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected mask pixel, and means for storing digital data representing the correlation of mask data with character data.
Claim 2
Independent Claim
358 words
An apparatus for recognition of printed characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising a microprocessor for producing processing instructions, character storage means coupled to the microprocessor for storing digital data representing the character to be recognized (character data hereafter), mask means coupled to the microprocessor and the character storage means for automatically providing digital data representing a plurality of typestyle masks (mask data hereafter) for comparison with the character data, processor means coupled to the microprocessor, character storage means and mask means for processing and reprocessing digital data representing mask data and character data in response to instructions received from the microprocessor, and correlation means coupled to the character storage means, the mask means and the processing means for correlating the character data and mask data, said correlation means including means for analyzing digital data representing a selectable dead-band region including a plurality of registration zones on and around a selected pixel within the printed characters which can comprise as many as nine registration zones including a central correlation zone centered on the selected central pixel, center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters left, right, up and down respectively, from the selected central pixel, and up-left, up-right, down-left and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, down and left, and down and right, respectively, from the selected central pixel, means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected character pixel, means for comparing each mask pixel with the corresponding combination of character pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected mask pixel, and means for storing digital data representing the correlation of mask data with character data.
Claim 3
Dependent Claim
164 words
In a character recognition system, a correlator comprising: first means for comparing individual bits of digital data representing the character to be recognized (character data bits hereafter) with corresponding individual bits of digital data representing a plurality of typestyle masks (mask data bits hereafter) and with the logical combination of mask data bits immediately adjacent to said corresponding mask data bits, and computing a first comparison score; second means for comparing mask data bits with the corresponding character data bits and with the logical combinations of character data bits immediately adjacent the corresponding character data bits, and computing a second comparison score; score register coupled to the first and second means for storing the first and second comparison scores and producing a first signal in response thereto; and third means, coupled to the score register for producing a second signal if the first signal is above a preselectable value, and for producing a third signal if the first signal is below a preselected value.
Claim 4
Dependent Claim
164 words
In a character recognition system, a correlator comprising: first means for comparing individual bits of digital data representing the character to be recognized (character data bits hereafter) with corresponding individual bits of digital data representing a plurality of typestyle masks (mask data bits hereafter) and with the logical combination of mask data bits immediately adjacent to said corresponding mask data bits, and computing a first comparison score; second means for comparing mask data bits with the corresponding character data bits and with the logical combinations of character data bits immediately adjacent the corresponding character data bits, and computing a second comparison score; score register coupled to the first and second means for storing the first and second comparison scores and producing a first signal in response thereto; and third means, coupled to the score register for producing a second signal if the first signal is above a preselectable value, and for producing a third signal if the first signal is below a preselected value.
Claim 5
Dependent Claim
96 words
An apparatus as in claim 1 wherein the means for analyzing digital data representing the selectable region surrounding each bit of character data comprises: first and second delay means coupled to the character and mask data, respectively, for time delaying the character and mask data; logic gate means coupled to the first and second delay means for digitally measuring the amount of intersection of the character and mask data and for producing a digital score representative of the amount of intersection; and a plurality of digital counters coupled to the output of the logic gate means.
Claim 6
Dependent Claim
34 words
An apparatus as in claim 3 wherein the means for storing digital data representing the correlation of mask and character data comprises a plurality of digital registers coupled to the plurality of digital counters.
Claim 7
Dependent Claim
24 words
An apparatus as in claim 3 wherein the first and second delay means comprise a first and second plurality of serially connected delay lines.
Claim 8
Dependent Claim
20 words
An apparatus as in claim 5 wherein the serially connected delay lines each have one or more time delay taps.
Claim 9
Dependent Claim
39 words
An apparatus as in claim 3 wherein the logic gate means comprises a plurality of digital gates interconnected to produce digital scores in a plurality of registration zones on and around a selected central pixel within the printed characters.
Claim 10
Dependent Claim
14 words
An apparatus as in claim 7 wherein the number of registration zones is nine.
Claim 11
Dependent Claim
98 words
An apparatus as in claim 8 wherein the registration zones comprise: a central correlation zone centered on the selected central pixel; center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters left, right, up, and down, respectively, from the selected central pixel; and up-left, up-right, down-left, and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, down and left, and down and right, respectively, from the selected central pixel.
Claim 12
Dependent Claim
14 words
An apparatus as in claim 7 wherein the number of registration zones is eight.
Claim 13
Dependent Claim
94 words
An apparatus as in claim 10 wherein the registration zones comprise: a central correlation zone centered on the selected central pixel; center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, left, right, up, and down, respectively, from the selected central pixel; and up-left, up-right, and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, and down and right, respectively, from the selected central pixel.
Claim 14
Dependent Claim
64 words
An apparatus as in claim 3 wherein the character data is measured through a mask window centered about a selected pixel made up of a first matrix three horizontal by five vertical pixels in size, and the mask data is measured through a character window centered about the selected pixel made up of a second matrix five horizontal by three vertical pixels in size.
Claim 15
Dependent Claim
158 words
In an optical character recognition system, a method for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said method comprising: (a) digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel, and (d) weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
Claim 16
Dependent Claim
158 words
In an optical character recognition system, a method for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said method comprising: (a) digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel, and (d) weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
Claim 17
Dependent Claim
26 words
A method as in claim 13 further comprising: (e) weighting pixels more than one pixel distant from the nearest matching pixel with a weight of one.
Claim 18
Dependent Claim
29 words
A method as in claim 14 further comprising: (f) correlating the comparison results of a plurality of different character to mask registration zones for each character and mask pixel.
Claim 19
Dependent Claim
26 words
A method as in claim 14 further comprising correlating the comparison results of nine different character to mask registration zones for each character and mask pixel.
Claim 20
Dependent Claim
26 words
A method as in claim 14 further comprising correlating the comparison results of eight different character to mask registration zones for each character and mask pixel.
Claim 21
Dependent Claim
35 words
A method as in claim 15 further comprising: (g) registering the lowest correlation score if the registered correlation is less than a preselected threshold score; and (h) signaling that a potentially satisfactory recognition has occurred.
Claim 22
Dependent Claim
18 words
A method as in claim 18 further comprising resolving the intersection of two similar but different character masks.
Claim 23
Dependent Claim
79 words
A method as in claim 19 wherein the step of resolving the intersection of two similar but different character masks comprises: (i) measuring the threshold score between the mask and character data for a character which is considered recognized to obtain the lowest correlation score; (j) measuring the next lowest correlation score between the recognized character and the next nearest mask neighbor; (k) subtracting the next lowest correlation score from the lowest correlation score to form a separation score.
Claim 24
Dependent Claim
103 words
A method as in claim 20 further comprising: compressing the character data into vertical and horizontal silhouette composites; erasing from the data representing the original character field silhouette bits which are isolated by a selected number of pixels greater than the smallest expected character feature size from the main silhouette; repeating the steps (b) through (k) to produce a second correlation score and a second separation score; and signaling a satisfactory recognition if the character data field is not blank, the second correlation score is less than the original correlation score, and the second separation score is greater than the original separation score.
Claim 25
Dependent Claim
28 words
A method as in claim 19 further comprising dividing the set of mask data into separate sets of mask data for different versions of the same generic typestyle.
Claim 26
Dependent Claim
50 words
A method as in claim 18 further comprising: centering the character data relative to the mask data field; repeating the steps (b) through (h) to produce a third correlation score; comparing the original and the third correlation scores; and accepting the lower of the original and the third correlation scores.
Claim 27
Dependent Claim
54 words
A method as in claim 18 further comprising: (l) erasing from the character data data representing darkened areas in the bottom row of the character field; and repeating steps (b) through (h) and (l) up to a specified number of times if in each repetition the correlation score is less than the previous repetition.
Claim 28
Dependent Claim
57 words
A method as in claim 18 further comprising: (m) removing from the character data data representing at least one pixel from the perimeter of each character stroke; and (n) repeating steps (b) through (h) and (m) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 29
Dependent Claim
22 words
A method as in claim 25 in which the steps (m) and (n) are used continuously within each page of printed characters.
Claim 30
Dependent Claim
76 words
A method as in claim 18 further comprising: (o) removing from the character data data representing one pixel from the top and left of each character stroke; (p) removing from the character data data representing one pixel from the bottom and right of each character stroke; and repeating steps (b) through (h), (o), and (p) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 31
Dependent Claim
59 words
A method as in claim 18 further comprising: (q) adding to the character data data representing one pixel to the top, bottom, left, and right of each character stroke; and (r) repeating steps (b) through (h) and (q) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 32
Dependent Claim
22 words
A method as in claim 28 in which the steps (q) and (r) are used continuously within each page of printed characters.
Claim 33
Dependent Claim
33 words
A method as in claim 18 further comprising applying a single character mask set within one typestyle to each successive character until no satisfactory recognition has occurred for one of the successive characters.
Claim 34
Dependent Claim
165 words
In an optical character recognition system, apparatus for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising: (a) means for digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) means for comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel; and (d) means for weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
Claim 35
Dependent Claim
165 words
In an optical character recognition system, apparatus for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising: (a) means for digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) means for comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel; and (d) means for weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
Claim 36
Dependent Claim
28 words
The apparatus as in claim 31 further comprising: (e) means for weighting pixels more than one pixel distant from the nearest matching pixel with a weight of one.
Claim 37
Dependent Claim
31 words
The apparatus as in claim 32 further comprising: (f) means for correlating the comparison results of a plurality of different character to mask registration zones for each character and mask pixel.
Claim 38
Dependent Claim
28 words
The apparatus as in claim 32 further comprising means for correlating the comparison results of nine different characters to mask registration zones for each character and mask pixel.
Claim 39
Dependent Claim
28 words
The apparatus as in claim 32 further comprising means for correlating the comparison results of eight different character to mask registration zones for each character and mask pixel.
Claim 40
Dependent Claim
39 words
The apparatus as in claim 33 further comprising: (g) means for registering the lowest correlation score if the registered correlation is less than a preselected threshold score; and (h) means for signaling that a potentially satisfactory recognition has occurred.
Claim 41
Dependent Claim
20 words
The apparatus as in claim 36 further comprising means for resolving the intersection of two similar but different character masks.
Claim 42
Dependent Claim
85 words
The apparatus as in claim 37 wherein said means for resolving the intersection of two similar but different character masks comprises: (i) means for measuring the threshold score between the mask and character data for a character which is considered recognized to obtain the lowest correlation score; (j) means for measuring the next lowest correlation score between the recognized character and the next nearest mask neighbor; (k) means for subtracting the next lowest correlation score from the lowest correlation score to form a separation score.
Claim 43
Dependent Claim
111 words
The apparatus as in claim 38 further comprising: means for compressing the character data into vertical and horizontal silhouette composites; means for erasing from the data representing the original character field silhouette bits which are isolated by a selected number of pixels greater than the smallest expected character feature size from the main silhouette; means for repeating the steps (b) through (k) to produce a second correlation score and a second separation score; and means for signaling a satisfactory recognition if the character data field is not blank, the second correlation score is less than the original correlation score, and the second separation score is greater than the original separation score.
Claim 44
Dependent Claim
30 words
The apparatus as in claim 37 further comprising means for dividing the set of mask data into separate sets of mask data for different versions of the same generic typestyle.
Claim 45
Dependent Claim
58 words
The apparatus as in claim 36 further comprising: means for centering the character data relative to the mask data field; means for repeating the steps (b) through (h) to produce a third correlation score; means for comparing the original and the third correlation scores; and means for accepting the lower of the original and the third correlation scores.
Claim 46
Dependent Claim
57 words
The apparatus as in claim 36 further comprising: (l) means erasing from the character data data representing darkened areas in the bottom row of the character field; and means for repeating steps (b) through (h) and (l) up to a specified number of times if in each repetition the correlation score is less than the previous repetition.
Claim 47
Dependent Claim
61 words
The apparatus as in claim 36 further comprising: (m) means for removing from the character data data representing at least one pixel from the perimeter of each character stroke; and (n) means for repeating elements (b) through (h) and (m) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 48
Dependent Claim
22 words
The apparatus as in claim 40 in which the elements (m) and (n) are used continuously within each page of printed characters.
Claim 49
Dependent Claim
82 words
The apparatus as in claim 36 further comprising: (o) means for removing from the character data data representing one pixel from the top and left of each character stroke; (p) means for removing from the character data data representing one pixel from the bottom and right of each character stroke; and means for repeating elements (b) through (h), (o), and (p) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 50
Dependent Claim
63 words
The apparatus as in claim 36 comprising: (q) means for adding up to the character data data representing one pixel to the top, bottom, left, and right of each character stroke; and (r) means for repeating elements (b) through (h) and (q) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
Claim 51
Dependent Claim
22 words
The apparatus as in claim 46 in which the elements (q) and (r) are used continuously within each page of printed characters.
Claim 52
Dependent Claim
35 words
The apparatus as in claim 36 further comprising means for applying a single character mask set within one typestyle to each successive character until no satisfactory recognition has occurred for one of the successive characters.
References Cited (Backward Citations)
US3219974A
Cited
US3274550A
Cited
US3167746A
Cited
US3303466A
Cited
US3295105A
Cited
US3496543A
Cited
US3618016A
Cited
US3634822A
Cited
US3820067A
Cited
US3629826A
Cited
US3905018A
Cited
US3805237A
Cited
US3760356A
Cited
US3846754A
Cited
US3878509A
Cited
US3818445A
Cited
US3934225A
Cited
US4153897A
Cited
US4288782A
Cited
US4308523A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-10-12 | 1991-04-13 | 1991-10-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-10-12 | 1995-04-13 | 1995-10-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-10-12 | 1999-04-13 | 1999-10-13 | $7700.00 | Window Closed / Lapsed |