EP0550865A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A continuous parameter hidden Markov model approach to automatic handwriting recognition
Assignee: International Business Machines Corp
•
Filing: 1992-12-21
•
Granted: —
•
Expires: 2012-12-21
Abstract
Abstract A computer-based system and method for recognizing handwriting. The present invention includes a pre-processor, a front end, and a modeling component. The present invention operates as follows. First, the present invention identifies the lexemes for all characters of interest. Second, the present invention performs a training phase in order to generate a hidden Markov model for each of the lexemes. Third, the present invention performs a decoding phase to recognize handwritten text. Hidden Markov models for lexemes are produced during the training phase. The present invention performs the decoding phase as follows. The present invention receives test characters to be decoded (that is, to be recognized). The present invention generates sequences of feature vectors for the test characters by mapping in chirographic space. For each of the test characters, the present invention computes probabilities that the test character can be generated by the hidden Markov models. The present invention decodes the test character as the recognized character associated with the hidden Markov model having the greatest probability.
Inventors
- 👤 Eveline Jeannine Bellegarda
- 👤 Jerome Rene Bellegarda
- 👤 David Nahamoo
- 👤 Krishna Sundaram Nathan
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 14:01
CPC Classifications
G; G06; G06F; G06F18/00; G06F18/20; G06F18/29; G06F18/295
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
200 words
A computer-based method for recognizing handwriting, the method comprising the steps of: (1) receiving sample characters, said sample characters represented by training observation sequences; (2) sorting said sample characters according to lexemes by mapping said sample characters in lexographic space to find high-level variations in said sample characters; (3) selecting one of said lexemes; (4) generating sequences of feature vectors for said sample characters associated with said selected lexeme by mapping in chirographic space; (5) generating a hidden Markov model for said selected lexeme, said hidden Markov model having one or more states, each of said states having emission transitions and non-emission transitions, wherein said step (5) comprises the steps of: (i) initializing model parameters; and (ii) updating said model parameters, wherein said step (ii) preferably comprises the step of performing Viterbi alignment of observation sequences to update said model parameters, and/or wherein said step (ii) preferably comprises the steps of: (a) accumulating probabilities of each state transition and each observed value corresponding to all possible paths through said hidden Markov model for each training observation sequence; and (b) updating said model parameters based on relative frequencies of said state transitions and on observed values emitted during said state transitions.
Claim 2
Dependent Claim
30 words
The method of claim 1, further comprising the step of: (6) generating individual hidden Markov models for all lexemes by performing steps (3) - (5) for each of said lexemes.
Claim 3
Dependent Claim
84 words
The method of claim 1 or 2, further comprising the steps of: (7) receiving test characters; (8) generating sequences of feature vectors for said test characters by mapping in chirographic space; (9) selecting one of said test characters; (10) computing probabilities that said selected test character can be generated by said hidden Markov models; (11) selecting one of said hidden Markov models having a greatest probability; and (12) decoding said selected test character as a recognized character associated with said selected hidden Markov model.
Claim 4
Dependent Claim
22 words
The method of claim 3, further comprising the step of: (13) performing steps (9) - (12) for each of said test characters.
Claim 5
Independent Claim
188 words
The method of any one of the preceding claims, wherein said step (i) comprises the steps of: (a) setting a length for said hidden Markov model; (b) initializing state transition probabilities of said hidden Markov model to be uniform; (c) for each of said states, tying output probability distributions for said emission transitions; (d) for each of said states, assigning a Gaussian density distribution for each codebook; and (e) alternatively initializing mixture coefficients to be values obtained from a statistical mixture model, wherein said step (a) preferably comprises the steps of: determining an average length of observed sequences; identifying one of said observed sequences closest in length to said average length; and setting a length for said hidden Markov model to a value longer than said identified observed sequence, and/or wherein step (d) preferably comprises the steps of: generating multiple Gaussian density distributions by using said statistical mixture model; for each of said states, selecting one of said Gaussian density distributions based on cluster memberships g k of individual frames of an observation sequence; and alternatively initializing mixture coefficients to be values obtained from said statistical mixture model.
Claim 6
Independent Claim
55 words
The method of any one of the preceding claims, wherein said step (ii) comprises the steps of: (a) determining a most probable path through said hidden Markov model for each training observation sequence; and (b) updating said model parameters based on relative frequencies of state transitions and on observed values emitted during said state transitions.
Claim 7
Dependent Claim
86 words
The method of claim 6, wherein step (b) comprises the steps of: (I) updating output distributions; (II) updating mixture coefficients; and (III) updating state transition probabilities, wherein said step (I) preferably comprises the step of determining a probability of observing a feature vector x t at a state j according to an equation: wherein said step (II) preferably comprises the step of updating mixture coefficients according to an equation: and wherein step (III) preferably comprises the step of updating state transition probabilities according to an equation:
Claim 8
Dependent Claim
17 words
The method of claim 7, further comprising the step of: (IV) repeating steps (II)-(III) during each iteration.
Claim 9
Independent Claim
42 words
The method of any one of the claims 3 to 8, wherein said step (10) comprises the step of applying a Viterbi algorithm to calculate, a posteriori , probabilities that said selected test character can be generated by said hidden Markov models.
Claim 10
Independent Claim
43 words
The method of any one of the claims 3 to 9, wherein said step (10) comprises the step of applying a maximum likelihood algorithm to calculate, a posteriori , probabilities that said selected test character can be generated by said hidden Markov models.
Claim 11
Dependent Claim
150 words
A computer-based system for recognizing handwriting, the system comprising: (a) means for receiving sample characters, said sample characters represented by training observation sequences; (b) means for sorting said sample characters according to lexemes by mapping said sample characters in lexographic space to find high-level variations in said sample characters; (c) means for generating sequences of feature vectors for said sample characters by mapping in chirographic space; (d) means for generating hidden Markov models for said lexemes, each of said hidden Markov models having one or more states, each of said states having emission transitions and non-emission transitions, wherein said generating means comprises: (i) means for initializing model parameters in each of said hidden Markov models; and (ii) means for updating said model parameters in each of said hidden Markov models, wherein said updating means preferably comprises a means for performing Viterbi alignment of observation sequences to update said model parameters.
Claim 12
Dependent Claim
99 words
The system of claim 11, further comprising: (e) means for receiving test characters; (f) means for generating sequences of feature vectors for said test characters by mapping in chirographic space; (g) means for computing probabilities that said test characters can be generated by said hidden Markov models; and (h) means for decoding said test characters as recognized characters associated with said selected hidden Markov models having greatest probabilities, wherein said computing means preferably comprises means for applying a Viterbi algorithm to calculate, a posteriori , probabilities that said selected test character can be generated by said hidden Markov models.
Claim 13
Dependent Claim
82 words
The system of claim 11 or 12, wherein said initializing means comprises: means for setting a length for said hidden Markov model; means for initializing state transition probabilities of said hidden Markov model to be uniform; means for tying output probability distributions for said emission transitions for each of said states; means for assigning a Gaussian density distribution for each codebook for each of said states; and means for alternatively initializing mixture coefficients to be values obtained from a statistical mixture model.
Claim 14
Independent Claim
67 words
The system of any one of the claims 11 to 13, wherein said updating means comprises: means for accumulating probabilities of each state transistion and each observed value corresponding to all possible paths through said hidden Markov model for each training observation sequence; and means for updating said model parameters based on relative frequencies of said state transistions and on observed values emitted during said state transitions.
Claim 15
Independent Claim
107 words
The system of any one of the claims 11 to 14, wherein said updating means comprises: (1) means for determining a most probable path through said hidden Markov model for each training observation sequence; (2) means for updating said model parameters based on relative frequencies of state transitions and on observed values emitted during said state transitions, comprising: (I) means for updating output distributions; (II) means for updating mixture coefficients; and (III) means for updating state transition probabilities, wherein said means for updating output distributions preferably comprises means for determining a probability of observing a feature vector x t at a state j according to an equation:
Claim 16
Dependent Claim
22 words
The system of claim 15, wherein said means for updating mixture coefficients comprises means for updating mixture coefficients according to an equation:
Claim 17
Dependent Claim
26 words
The system of claim 15 or 16, wherein said means for updating state transition probabilities comprises means for updating state transition probabilities according to an equation:
Claim 18
Independent Claim
42 words
The system of any one of the claims 12 to 27, wherein said computing means comprises means for applying a maximum likelihood algorithm to calculate, a posteriori , probabilities that said selected test character can be generated by said hidden Markov models.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.