US5644648A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for connected and degraded text recognition
Assignee: Nokia of America Corp
•
Filing: 1995-05-09
•
Granted: 1997-07-01
•
Expires: 2015-05-09
Abstract
Abstract A method and apparatus for recognizing connected and degraded text is presented. A text enhancement process which may be used in combination with text recognition comprises filtering a scanned image to determine whether a binary image value of an image pixel should be complemented, determining whether complementing the value of the pixel reduces the sharpness of wedge-like figures in the image, and complementing the binary value of the pixel when doing so does not reduce sharpness. Image preprocessing may also provide a line adjacency graph (LAG) based on a set of image pixels and the removal of a path from a LAG when the path is located either at the top or bottom of the set of image pixels and is of degree (1,0) or (0,1), respectively, and connected to a junction of the LAG. The recognition process may comprise determining primitive strokes in a scanned image, segmenting the scanned image into sub-character segments based on the primitive strokes, identifying features which characterize the sub-character segments, and comparing identified features to stochastic models of known characters and determining an optimum sequence of known characters based on the comparisons through the use of Viterbi scoring and level building procedures.
Inventors
- 👤 Chinmoy Bhusan Bose
- 👤 Shyh-Shiaw Kuo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:49
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/16; G06V30/164; G06F; G06F18/00; G06F18/20; G06F18/29; G06F18/295; G06V10/00; G06V10/70; G06V10/84; G06V10/85; G06V30/18; G06V30/1801; G06V30/18076; G06V30/19; G06V30/191; G06V30/19187; G06V30/196
Claims Analysis
Total Claims: 53
Claim 1
Independent Claim
146 words
A method for recognizing characters in a scanned text image, the method comprising the steps of: segmenting the scanned image into one or more sub-character segments, each sub-character segment comprising a substantially vertical portion of said scanned text image; identifying one or more features characterizing a sub-character segment; and recognizing characters based on identified sub-character features, wherein said step of segmenting the scanned image comprises the steps of: determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; determining one or more strokes in the scanned text image based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and segmenting the scanned text image into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 2
Independent Claim
146 words
A method for recognizing characters in a scanned text image, the method comprising the steps of: segmenting the scanned image into one or more sub-character segments, each sub-character segment comprising a substantially vertical portion of said scanned text image; identifying one or more features characterizing a sub-character segment; and recognizing characters based on identified sub-character features, wherein said step of segmenting the scanned image comprises the steps of: determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; determining one or more strokes in the scanned text image based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and segmenting the scanned text image into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 3
Dependent Claim
29 words
The method of claim 1 wherein the step of recognizing characters based on identified sub-character features comprises the step of comparing sub-character features to known features of known characters.
Claim 4
Dependent Claim
80 words
The method of claim 1 wherein the step of determining strokes comprises: representing a scanned image with one or more compressed line adjacency graphs, a compressed line adjacency graph comprising one or more compressed paths; dividing a compressed path of a compressed line adjacency graph into two or more groups of nodes based on node width and center location information; and determining one or more strokes for a group based upon a set of one or more stroke identification rules.
Claim 5
Dependent Claim
32 words
The method of claim 3 wherein the step of determining one or more strokes comprises the step of merging adjacent strokes based on a set of one or more stroke merging rules.
Claim 6
Dependent Claim
15 words
The method of claim 1 wherein a feature characterizing a sub-character segment comprises a stroke.
Claim 7
Dependent Claim
15 words
The method of claim 1 wherein a feature characterizing a sub-character segment comprises an arc.
Claim 8
Dependent Claim
17 words
The method of claim 1 wherein a feature characterizing a sub-character segment is represented by a 5-tuple.
Claim 9
Dependent Claim
49 words
The method of claim 1 wherein the step of identifying features comprises the steps of: representing a sub-character segment with a compressed line adjacency graph, the compressed line adjacency graph comprising one or more compressed paths; and analyzing a compressed line adjacency graph to determine one or more features.
Claim 10
Dependent Claim
33 words
The method of claim 8 wherein the step of identifying features further comprises the step of excluding from a segment one or more pixels associated with a compressed path from a neighboring segment.
Claim 11
Dependent Claim
31 words
The method of claim 8, wherein the step of analyzing a compressed line adjacency graph comprises the step of identifying a horizontal stroke for a compressed path of a horizontal segment.
Claim 12
Dependent Claim
39 words
The method of claim 8 wherein the step of analyzing a compressed line adjacency graph comprises the step of defining for a compressed path of a nonhorizontal segment one or more groups of nodes based on node width information.
Claim 13
Dependent Claim
34 words
The method of claim 11 wherein the step of analyzing a compressed line adjacency graph further comprises the step of merging two adjacent groups into a single group based on average group width information.
Claim 14
Dependent Claim
27 words
The method of claim 11 wherein the step of analyzing a compressed line adjacency graph further comprises the step of identifying an arc feature within a group.
Claim 15
Dependent Claim
86 words
The method of claim 13 wherein the step of identifying an arc feature within a group comprises the steps of: defining a line segment connecting the centers of the first and last nodes in a group; determining a node center within the group which is the greatest distance from the line; and identifying an arc feature defined by the centers of the first and last nodes and the determined node center when the greatest distance divided by the length of the line segment exceeds a threshold.
Claim 16
Dependent Claim
27 words
The method of claim 11 wherein the step of analyzing a compressed line adjacency graph further comprises the step of identifying a stroke feature within a group.
Claim 17
Dependent Claim
49 words
The method of claim 1 wherein the step of recognizing comprises the steps of: comparing identified sub-character features to one or more stochastic models of known characters and determining one or more scores based on each comparison; and determining a sequence of known characters based on the determined scores.
Claim 18
Dependent Claim
19 words
The method of claim 16 further comprising training a stochastic model based on identified sub-character features of known characters.
Claim 19
Dependent Claim
21 words
The method of claim 17 wherein training comprises performing a K-means clustering of feature vectors to adaptively partition a feature space.
Claim 20
Dependent Claim
26 words
The method of claim 18 wherein training further comprises representing a segment vector in a binary N-dimensional space, where N is a number of feature clusters.
Claim 21
Dependent Claim
17 words
The method of claim 16 wherein the stochastic model of a character comprises a Hidden Markov Model.
Claim 22
Dependent Claim
23 words
The method of claim 20 further comprising the step of training the Hidden Markov Model by determining probabilities for states of the model.
Claim 23
Dependent Claim
18 words
The method of claim 20 wherein the Hidden Markov Model comprises penalty functions for skipping a model state.
Claim 24
Dependent Claim
19 words
The method of claim 20 wherein a Hidden Markov Model comprises penalty functions for remaining in a model state.
Claim 25
Dependent Claim
19 words
The method of claim 16 wherein the step of determining a distance score comprises determining a Bayesian distance score.
Claim 26
Dependent Claim
24 words
The method of claim 16 wherein the step of determining an optimum sequence of known characters is further based on a model of context.
Claim 27
Dependent Claim
19 words
The method of claim 25 wherein the model of context comprises a stochastic model for a sequence of characters.
Claim 28
Dependent Claim
17 words
The method of claim 26 wherein the stochastic model for a sequence of characters comprises n-gram probabilities.
Claim 29
Dependent Claim
18 words
The method of claim 25 wherein the model of context comprises a lexicon of sequences of text characters.
Claim 30
Dependent Claim
23 words
The method of claim 16 wherein the step of determining an optimum sequence of known characters comprises the step of performing Viterbi scoring.
Claim 31
Dependent Claim
18 words
The method of claim 29 wherein the step of performing Viterbi scoring comprises performing a level building process.
Claim 32
Dependent Claim
200 words
A text recognition system, the system comprising: means for performing image enhancement on a scanned text image; means, coupled to the means for performing image enhancement, for performing sub-character segmentation, each resulting sub-character segment comprising a substantially vertical portion of said scanned text image; means, coupled to the means for performing sub-character segmentation, for performing feature extraction based on sub-character segments; means, coupled to the means for performing feature extraction, for performing recognition of text based on a comparison of extracted sub-character features and stochastic models of known characters; and memory means, coupled to the means for performing recognition of text, for storing the results of text recognition, wherein said means for performing sub-character segmentation comprises: means for determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; means for determining one or more strokes in the scanned text image based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and means for segmenting the scanned text image into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 33
Dependent Claim
200 words
A text recognition system, the system comprising: means for performing image enhancement on a scanned text image; means, coupled to the means for performing image enhancement, for performing sub-character segmentation, each resulting sub-character segment comprising a substantially vertical portion of said scanned text image; means, coupled to the means for performing sub-character segmentation, for performing feature extraction based on sub-character segments; means, coupled to the means for performing feature extraction, for performing recognition of text based on a comparison of extracted sub-character features and stochastic models of known characters; and memory means, coupled to the means for performing recognition of text, for storing the results of text recognition, wherein said means for performing sub-character segmentation comprises: means for determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; means for determining one or more strokes in the scanned text image based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and means for segmenting the scanned text image into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 34
Dependent Claim
23 words
The system of claim 31 further comprising a scanner for scanning a paper copy of a document and producing a pixel image thereof.
Claim 35
Dependent Claim
29 words
The system of claim 32 further comprising a page preprocessor, coupled to the scanner, for determining pixel images of words based on a scanned pixel image of a document.
Claim 36
Dependent Claim
18 words
The system of claim 31 further comprising a means for training a stochastic model of a known character.
Claim 37
Independent Claim
221 words
A method of training an optical text character recognition system with use of a plurality of sets of pixel signals representing text characters, the system including a memory for storing training information signals, the method comprising the steps of: segmenting each set of pixel signals into one or more sub-character segments, each sub-character segment comprising a substantially vertical portion of said set of pixel signals; generating one or more feature signals characterizing a sub-character segment of a given set of pixel signals; generating signals reflecting a stochastic representation of a particular sub-character segment, which signals reflect occurrences of feature signals corresponding to said sub-character segment in said sets of pixel signals; and storing said signals reflecting said stochastic representation of said particular sub-character segment in said memory, wherein said step of segmenting each set of pixel signals comprises the steps of: determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; determining one or more strokes in the set of pixel signals based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and segmenting the set of pixel signals into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 38
Independent Claim
221 words
A method of training an optical text character recognition system with use of a plurality of sets of pixel signals representing text characters, the system including a memory for storing training information signals, the method comprising the steps of: segmenting each set of pixel signals into one or more sub-character segments, each sub-character segment comprising a substantially vertical portion of said set of pixel signals; generating one or more feature signals characterizing a sub-character segment of a given set of pixel signals; generating signals reflecting a stochastic representation of a particular sub-character segment, which signals reflect occurrences of feature signals corresponding to said sub-character segment in said sets of pixel signals; and storing said signals reflecting said stochastic representation of said particular sub-character segment in said memory, wherein said step of segmenting each set of pixel signals comprises the steps of: determining one or more groups of nodes, wherein a node comprises a set of consecutive scanned pixels of a first binary value; determining one or more strokes in the set of pixel signals based on characteristics of said determined groups of nodes, wherein each stroke comprises a line segment characterizing a group of nodes; and segmenting the set of pixel signals into one or more of said substantially vertical sub-character segments based on one or more of said determined strokes.
Claim 39
Dependent Claim
82 words
The method of claim 35 wherein the step of determining strokes comprises: representing a set of pixel signals with one or more compressed line adjacency graphs, a compressed line adjacency graph comprising one or more compressed paths; dividing a compressed path of a compressed line adjacency graph into two or more groups of nodes based on node width and center location information; and determining one or more strokes for a group based upon a set of one or more stroke identification rules.
Claim 40
Dependent Claim
32 words
The method of claim 36 wherein the step of determining one or more strokes comprises the step of merging adjacent strokes based on a set of one or more stroke merging rules.
Claim 41
Dependent Claim
16 words
The method of claim 35 wherein a feature signal characterizing a sub-character segment comprises a stroke.
Claim 42
Dependent Claim
16 words
The method of claim 35 wherein a feature signal characterizing a sub-character segment comprises an arc.
Claim 43
Dependent Claim
18 words
The method of claim 35 wherein a feature signal characterizing a sub-character segment is represented by a 5-tuple.
Claim 44
Dependent Claim
53 words
The method of claim 35 wherein the step of generating one or more feature signals comprises the steps of: representing a sub-character segment with a compressed line adjacency graph, the compressed line adjacency graph comprising one or more compressed paths; and analyzing a compressed line adjacency graph to determine one or more features.
Claim 45
Dependent Claim
37 words
The method of claim 41 wherein the step of generating one or more feature signals further comprises the step of excluding from a segment one or more pixels associated with a compressed path from a neighboring segment.
Claim 46
Dependent Claim
31 words
The method of claim 41 wherein the step of analyzing a compressed line adjacency graph comprises the step of identifying a horizontal stroke for a compressed path of a horizontal segment.
Claim 47
Dependent Claim
39 words
The method of claim 41 wherein the step of analyzing a compressed line adjacency graph comprises the step of defining for a compressed path of a non-horizontal segment one or more groups of nodes based on node width information.
Claim 48
Dependent Claim
34 words
The method of claim 44 wherein the step of analyzing a compressed line adjacency graph further comprises the step of merging two adjacent groups into a single group based on average group width information.
Claim 49
Dependent Claim
27 words
The method of claim 44 wherein the step of analyzing a compressed line adjacency graph further comprises the step of identifying an arc feature within a group.
Claim 50
Dependent Claim
86 words
The method of claim 46 wherein the step of identifying an arc feature within a group comprises the steps of: defining a line segment connecting the centers of the first and last nodes in a group; determining a node center within the group which is the greatest distance from the line; and identifying an arc feature defined by the centers of the first and last nodes and the determined node center when the greatest distance divided by the length of the line segment exceeds a threshold.
Claim 51
Dependent Claim
27 words
The method of claim 44 wherein the step of analyzing a compressed line adjacency graph further comprises the step of identifying a stroke feature within a group.
Claim 52
Dependent Claim
23 words
The method of claim 35 wherein the step of generating is performed with use of a set of vector quantized feature space signals.
Claim 53
Dependent Claim
34 words
The method of claim 35 further comprising the steps of: analyzing sub-character segments to generate representations of portions of characters corresponding to the segments; and clustering said representations to adaptively partition a feature space.
References Cited (Backward Citations)
US3737855A
Cited
DE2550700A1
Cited
US4783753A
Cited
US5170442A
Cited
US4783840A
Cited
US4791679A
Cited
US5067165A
Cited
US5142589A
Cited
US5148500A
Cited
US5263097A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-30 | 2000-12-30 | 2001-07-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-30 | 2004-12-30 | 2005-07-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-30 | 2008-12-30 | 2009-07-01 | $7700.00 | Window Closed / Lapsed |