Continuous parameter hidden Markov model approach to automatic handwriting recognition

• US 5,636,291 A
• Filed: 06/06/1995
• Issued: 06/03/1997
• 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, Eveline J., Bellegarda, Jerome R., Nahamoo, David, Nathan, Krishna S.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/467,615
• Time in Patent Office: 728 Days
• Field of Search: 382/187, 382/224, 382/228, 382/229, 382/230, 382/197, 382/159, 382/160, 395/2
• 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 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.

Claims

1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for recognizing a handwritten character, said method steps comprising:

(1) receiving character signals from an input device, said character signals representing training observation sequences of sample characters;

(2) sorting said character signals according to lexemes which represent different writing styles for a given character, by mapping said character signals in lexographic space, said lexographic space containing 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 representing feature vectors for said character signals associated with said selected lexeme by mapping in chirographic space, said chirographic space containing one or more frame-level feature vectors; and

(5) generating a Markov model signal 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 parameters 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, typing 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 (ii)(b) comprises the steps of:

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

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

(lII) updating station 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## wherein "s_i " 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 program product for recognizing handwriting, comprising:

(a) a computer usable medium having computer readable program code means embodied in said medium for causing a computer to recognize a handwritten character, said computer readable program code means comprising,

(b) computer readable program code means for causing a computer to receive character signals into a preprocessor unit from the input device representing training observation sequences of sample characters;

(c) computer readable program code means for causing a computer to sort said character signals in said 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 containing one;

or more character-level feature vectors, to find high-level variations in said character signals;

(d) computer readable program code means for causing a computer to generate sequences of feature vector signals in a front end unit representing feature vectors for said character signals by mapping in chirographic space, said chirographic space containing one or more frame-level feature vectors;

(e) computer readable program code means for causing a computer to generate 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) computer readable program code means for causing a computer to initialize said model parameter signals in each of said hidden Markov model, said initializing means comprising;

computer readable program code means for causing a computer to set a length for said hidden Markov model;

computer readable program code means for causing a computer to initialize state transition probabilities of said hidden Markov model to be uniform;

computer readable program code means for causing a computer to tie one or more output probability distributions for said emission transitions for each of said states;

computer readable program code means for causing a computer to assign a Gaussian density distribution for each one or more codebooks for each of said states; and

computer readable program code means for causing a computer to alternatively initialize one or more mixture coefficients to be values obtained from a statistical mixture model; and

(ii) computer readable program code means for causing a computer to update said model parameter signals in each of said hidden Markov models.

18. The computer program product of claim 17, further comprising:

(f) computer readable program code means for receiving test characters;

(g) computer readable program code means for generating sequences of feature vectors for said test characters by mapping in chirographic space;

(h) computer readable program code means for computing probabilities that said test characters can be generated by said hidden Markov models; and

(j) computer readable program code means for decoding said test characters as recognized characters associated with said selected hidden Markov models having greatest probabilities.

19. The computer program product of claim 17, wherein said means for updating comprises a computer readable program code means for causing a computer to perform Viterbi alignment of observation sequences to update said model parameters.

20. The computer program product of claim 17, wherein said means for updating comprises:

computer readable program code means for causing a computer to accumulate 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

computer readable program code means for causing a computer to update said model parameters based on relative frequencies of said state transitions and on observed values emitted during said state transitions.

21. The computer program product of claim 17, wherein said updating means comprises:

(1) computer readable program code means for causing a computer to determine a most probable path through said hidden Markov model for each training observation sequence;

(2) computer readable program code means for causing a computer to update said model parameters based on a relative frequencies of state transitions and on observed values emitted during said state transitions, comprising;

(I) computer readable program code means for causing a computer to update said one or more output probability distributions;

(II) computer readable program code means for causing a computer to update said one or more mixture coefficients; and

(III) computer readable program code means for causing a computer to update state transition probabilities.

22. The computer program product of claim 21, wherein said means for updating output distributions comprises computer readable program means for causing a computer to determine 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 computer program product of claim 21, wherein said means for updating mixture coefficients comprises computer readable program code means for causing a computer to update 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 computer program product of claim 21, wherein said means for updating state transition probabilities comprises computer readable program code means for causing a computer to update 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 computer program product of claim 18, wherein said means for computing comprises computer readable program code means for causing a computer to apply a Viterbi algorithm to calculate, a posteriori, probabilities that said selected test character can be generated by said hidden Markov models.

26. The computer program product of claim 18, wherein said means for computing comprises computer readable program code means for causing a computer to apply a maximum likelihood algorithm to calculate, a posteriori, probabilities that said selected test character can be generated by said hidden Markov models.