Continuous parameter hidden Markov model approach to automatic handwriting recognition

• US 5,544,257 A
• Filed: 01/08/1992
• Issued: 08/06/1996
• Est. Priority Date: 01/08/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bellegarda, Jerome R., Nahamoo, David, Nathan, Krishna S., Bellegarda, Eveline J.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): ANDERSON, DAVID
• Application Number:
  US07/818,193
• Time in Patent Office: 1,672 Days
• Field of Search: 382/13, 382/36, 382/69
• US Class Current: 382/187
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

A computer-based system and method for recognizing handwriting. The present invention includes a preprocessor, 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.

Claims

1. A computer-based method for recognizing handwriting, wherein the computer comprises an input device, a memory module, a preprocessor unit, a front end unit and a modeling component, the method comprising the steps of:

(1) receiving character signals into the preprocessor unit from the input device, said character signals representing training observation sequences of sample characters;

(2) sorting said character signals in the preprocessor unit according to lexemes which represent different writing styles for a given character, by mapping said character signals in lexographic space, said lexographic space being a location in the memory module which contains one or more character-level feature vectors, to find high-level variations in said character signals;

(3) selecting one of said lexemes;

(4) generating sequences of feature vector signals in the front end unit representing feature vectors for said character signals associated with said selected lexeme by mapping in chirographic space, said chirographic space being a location in the memory module which contains one or more flame-level feature vectors; and

(5) generating a Markov model signal in the modeling component representing a hidden Markov model for said selected lexeme, said hidden Markov model having model parameter signals and 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 said model parameter signals comprising 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 one or more output probability distributions for said emission transitions;

(d) for each of said states, assigning a Gaussian density distribution for each of one or more codebooks; and

(e) alternatively initializing one or more mixture coefficients to be values obtained from a statistical mixture model; and

(ii) updating said model parameter signals.

2. 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.

3. The method of claim 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.

4. The method of claim 3, further comprising the step of:

(13) performing steps (9)-(12) for each of said test characters.

5. The method of claim 1, wherein said step (a) 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.

6. The method of claim 1, wherein step (d) 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.

7. The method of claim 1, wherein said step (ii) comprises the step of performing Viterbi alignment of observation sequences to update said model parameters.

8. The method of claim 1, wherein said step (ii) 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.

9. The method of claim 1, 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.

10. The method of claim 9, wherein step (b) comprises the steps of:

(I) updating said one or more output probability distributions;

(II) updating said one or more mixture coefficients; and

(III) updating state transition probabilities.

11. The method of claim 10, wherein said step (I) comprises the step of determining a probability of observing a feature vector x_t at a state j according to an equation:

##EQU11## where;

"x_t " is one of one or more feature vectors which are grouped into one or more clusters;

"s_j " is a state of said hidden markov model;

"k" is the total number of said feature vector clusters;

"g_k¹ " is one of said one or more clusters;

"g_k² " is one of said one or more clusters; and

"α

" is a weighting term.

12. The method of claim 10, wherein said step (II) comprises the step of updating mixture coefficients according to an equation:

##EQU12## where "s_j " is a state of said hidden markov model, and "g_k " is one of one or more clusters of feature vectors.

13. The method of claim 10, wherein step (III) comprises the step of updating state transition probabilities according to an equation:

##EQU13## where "s_j " is a state of said hidden markov model and "s_j " is a state of said hidden markov model.

14. The method of claim 10, further comprising the step of:

(IV) repeating steps (II)-(III) during each iteration.

15. The method of claim 3, 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.

16. The method of claim 3, 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.

17. A computer-based system for recognizing handwriting, the computer comprising an input device, a memory module, a preprocessor unit, a front end unit and a modeling component, the system comprising:

(a) means for receiving character signals into the preprocessor unit from the input device representing training observation sequences of sample characters;

(b) means for sorting said character signals in the preprocessor unit according to lexemes which represent different writing styles for a given character, by mapping said sample characters in lexographic space, said lexographic space being a location in the memory module which contains one or more character-level feature vectors, to find high-level variations in said character signals;

(c) means for generating sequences of feature vector signals in the front end unit representing feature vectors for said character signals by mapping in chirographic space, said chirographic space being a location in the memory module which contains one or more frame-level feature vectors;

(d) means for generating Markov model signals in the modeling component representing hidden Markov models for said lexemes, each of said hidden Markov models having model parameter signals and one or more states, each of said states having emission transitions and non-emission transitions, wherein said generating means comprises;

(i) means for initializing said model parameter signals in each of said hidden Markov models, said initializing means comprising;

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 one or more output probability distributions for said emission transitions for each of said states;

means for assigning a Gaussian density distribution for each of one or more codebooks for each of said states; and

means for alternatively initializing one or more mixture coefficients to be values-obtained from a statistical mixture model; and

(ii) means for updating said model parameter signals in each of said hidden Markov models.

18. The system of claim 17, 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.

19. The system of claim 17, wherein said updating means comprises a means for performing Viterbi alignment of observation sequences to update said model parameters.

20. The system of claim 17, wherein said updating means comprises:

means for 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

means for updating said model parameters based on relative frequencies of said state transistions and on observed values emitted during said state transitions.

21. The system of claim 17, 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 said one or more output probability distributions;

(II) means for updating said one or more mixture coefficients; and

(III) means for updating state transition probabilities.

22. The system of claim 21, wherein said means for updating output distributions comprises means for determining a probability of observing a feature vector x_t at a state j according to an equation:

##EQU14## where;

"x_t " is one of one or more feature vectors which are grouped into one or more clusters;

"s_j " is a state of said hidden markov model;

"k" is the total number of said feature vector clusters;

"g_k¹ " is one of said one or more clusters;

"g_k² " is one of said one or more clusters; and

"α

" is a weighting term.

23. The system of claim 21, wherein said means for updating mixture coefficients comprises means for updating mixture coefficients according to an equation:

##EQU15## where "s_j " is a state of said hidden markov model, and "g_k " is one of one or more clusters of feature vectors.

24. The system of claim 21, wherein said means for updating state transition probabilities comprises means for updating state transition probabilities according to an equation:

##EQU16## where "s_i " is a state of said hidden markov model and "s_j " is a state of said hidden markov model.

25. The system of claim 18, wherein said computing means 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.

26. The system of claim 18, 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.