System and method for automatic handwriting recognition with a writer-independent chirographic label alphabet

• US 5,644,652 A
• Filed: 04/19/1995
• Issued: 07/01/1997
• Est. Priority Date: 11/23/1993
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bellegarda, Eveline Jeannine, Nahamoo, David, Bellegarda, Jerome Rene, Nathan, Krishna Sundaram
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/424,236
• Time in Patent Office: 804 Days
• Field of Search: 382/224-228, 382/186-187, 381/41-43
• US Class Current: 382/186
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

An automatic handwriting recognition system wherein each written (chirographic) manifestation of each character is represented by a statistical model (called a hidden Markov model). The system implements a method which entails sampling a pool of independent writers and deriving a hidden Markov model for each particular character (allograph) which is independent of a particular writer. The HMMs are used to derive a chirographic label alphabet which is independent of each writer. This is accomplished during what is described as the training phase of the system. The alphabet is constructed using supervised techniques. That is, the alphabet is constructed using information learned in the training phase to adjust the result according to a statistical algorithm (such as a Viterbi alignment) to arrive at a cost efficient recognition tool. Once such an alphabet is constructed a new set of HMMs can be defined which more accurately reflects parameter typing across writers. The system recognizes handwriting by applying an efficient hierarchical decoding strategy which employs a fast match and a detailed match function, thereby making the recognition cost effective.

Claims

1. A method for operating a handwriting recognition system having a programmed digital data processor, comprising the data processor executed steps of:

generating a sequence of feature vectors in response to a two-dimensional trace associated with the input handwriting;

projecting the sequence of feature vectors onto a higher dimensional feature space that represents sub-character sections of the input handwriting;

performing a fast match of the sequence of feature vectors by generating a list of probable candidate characters using single-state, hidden Markov models (HMMs) having output probability distributions obtained from writer-independent higher dimensional feature space prototype distributions; and

performing a detailed match on the list of probable candidate characters using multi-state, writer independent HMMs to identify a most probable character sequence that the input handwriting represents;

wherein

at least one of the steps of performing a fast match and performing a detailed match operate in accordance with a supervision process.

2. A method as set forth in claim 1 and further including a preliminary step of:

for each character of interest, representing each allograph in terms of a multi-state HMM, where each allograph represents a different style for writing the character of interest.

3. A method for operating a handwriting recognition system having a programmed digital data processor, comprising the steps of:

generating a sequence of feature vectors in response to a two-dimensional trace associated with the input handwriting;

projecting the sequence of feature vectors onto a higher dimensional feature space that represents sub-character sections of the input handwriting;

performing a fast match of the sequence of feature vectors by generating a list of probable candidate characters sequentially using single-state, hidden Markov models (HMMs) having output probability distributions obtained from writer-independent higher dimensional feature space prototype distributions; and

performing a detailed match on the list of probable candidate characters using multi-state, writer independent HMMs to identify a most probable character sequence that the input handwriting represents; and

further including the initial steps of;

tagging individual ones of handwriting feature vectors in accordance with a statistical alignment;

constructing a binary clustering tree from the tagged feature vectors;

pruning the binary clustering tree in accordance with a predetermined pruning criteria to retain a first number of leaves L₁ for forming clusters;

further pruning the binary clustering tree to retain a second number of leaves L2, wherein L_2<

L₁, for forming a plurality of elementary handwriting units representing a writer-independent label alphabet; and

establishing a relationship between the elementary handwriting units and clusters by a step of determining mixture coefficients.

4. A method as set forth in claim 3 wherein the step of tagging includes a step of:

in accordance with the statistical alignment, tagging each feature vector in a current higher dimensional feature space with an index which unambiguously identifies the following properties;

(a) an associated allograph identity L_x from an alphabet A_lx that contains all the allographs for all the characters, and (b) the position P of a state within the HMM associated with L_x against which the feature vector was aligned, wherein each distinct (L_x, P) represents a leaf of the binary clustering tree; and

wherein the step of constructing the binary clustering tree includes the steps of,

(a) computing centroids for each distinct Leaf (L_x, P) using the tagged feature vectors;

(b) computing a distance D between each pair of centroids;

(c) ranking the centroid pairs in order of increasing distance D;

(d) computing a tentative new centroid for the top k (clustering) pairs;

(e) computing a distance D'"'"' between tentative new centroids and each remaining centroid;

(f) merging the centroid pair from the top k pairs which maximizes the distance D'"'"';

(g) determining if only one centroid is remaining, and if no, then repeating steps (b) through (g);

else

if only one centroid is remaining, then the step of constructing the binary clustering tree is complete.

5. A method as set forth in claim 4, wherein each of the steps of pruning are accomplished by the steps of:

(a) in accordance with the handwriting feature vectors and the constructed binary clustering tree, computing a number of vectors C for each distinct Leaf ((L_x, P) Tag);

(b) comparing the value of the vectors C to a predetermined minimum threshold value C_min to determine if C<

C_min, and if yes, merging the Leaf with its sibling;

(c) computing a change Δ

S in a spread S which would result from merging each Leaf with its sibling;

(d) merging a Leaf pair having a smallest Δ

S value to form a new Leaf;

(e) computing a new centroid and a new spread for the new Leaf;

(f) determining if the number of Leaves is greater than some predetermined number of Leaves;

(g) if the number of Leaves is greater than the predetermined number, then repeating steps (c) through (g), else

if the number of Leaves is not greater than the predetermined number, then the step of tree pruning is complete.

6. A method as set forth in claim 5, wherein for the first step of pruning the predetermined number of Leaves (L₁) is equal to approximately 750, and wherein for the second step of pruning the predetermined number of Leaves (L₂) is equal to approximately 100.

7. A method as set forth in claim 3 wherein the step of determining mixture coefficients includes the steps of:

in accordance with the tagged feature vectors, maintaining a record of cluster assignments at level L₁, and maintaining a record of elementary handwriting unit assignments at level L₂ ;

accumulating all assignment pairs at level L₁ and at level L₂ ; and

normalizing on a row-by-row basis to obtain a composition of elementary handwriting units in terms of cluster identities.

8. A method as set forth in claim 3 wherein the step of determining mixture coefficients includes the steps of:

in accordance with the tagged feature vectors, maintaining a record of cluster assignments at level L₁, and maintaining a record of elementary handwriting unit assignments at level L₂ ;

accumulating all assignment pairs at level L₁ and at level L₂ ; and

normalizing on a column-by-column basis to obtain a composition of clusters in terms of elementary handwriting unit identities.

9. A handwriting recognition system that includes a programmed digital data processor, said digital data processor being programmed to implement a handwriting recognition system that is comprised of:

means for generating a sequence of feature vectors in response to input handwriting received from a handwriting transducer means;

means for projecting the sequence of feature vectors onto a higher dimensional feature space that represents sub-character sections of the input handwriting;

means for performing a fast match of the sequence of feature vectors, including means for generating list of probable candidate characters using single-state, hidden Markov models (HMMs) having output probability distributions obtained from writer-independent higher dimensional feature space prototype distributions; and

means for performing a detailed match on the list of probable candidate characters using multi-state, writer independent HMMs, said detailed match performing means having an output for expressing a most probable character sequence that the input handwriting represents;

wherein

at least one of said means for performing a fast match and said means for performing a detailed match operate in accordance with a supervision process.

10. A handwriting recognition system as set forth in claim 9 and further comprising:

means for representing each character of interest as an allograph in terms of a multi-state HMM, where each allograph represents a different style for writing the character of interest.

11. A handwriting recognition system that includes a programmed digital data processor, said digital data processor being programmed to implement a handwriting recognition system that is comprised of:

means for generating a sequence of feature vectors in response to input handwriting received from a handwriting transducer means;

means for projecting the sequence of feature vectors onto a higher dimensional feature space that represents sub-character sections of the input handwriting;

means for performing a fast match of the sequence of feature vectors, including means for generating a list of probable candidate characters sequentially using single-state, hidden Markov models (HMMs) having output probability distributions obtained from writer-independent higher dimensional feature space prototype distributions; and

means for performing a detailed match on the list of probable candidate characters using multi-state, writer independent HMMs, said detailed match performing means having an output for expressing a most probable character sequence that the input handwriting represents; and

further comprising;

means for tagging individual ones of handwriting feature vectors in accordance with statistical alignments;

means for constructing a binary clustering tree from the tagged feature vectors;

means for pruning the binary clustering tree in accordance with a predetermined pruning criteria to retain a first number of leaves L₁ for forming clusters;

means for further pruning the binary clustering tree to retain a second number of leaves L2, wherein L₂ <

L₁, for forming a plurality of elementary handwriting units representing a writer-independent label alphabet; and

means for establishing a relationship between the elementary handwriting units and clusters in accordance with determined mixture coefficients.

12. A method for operating a handwriting recognition system having a programmed digital data processor, comprising the data processor executed steps of:

obtaining training data from a plurality of writers;

extracting parameter vectors from the obtained training data;

determining from the parameter vectors a plurality of allographs, where each allograph represents a different style for writing a character of interest;

generating an initial hidden Markov model (HMM) for each allograph;

extracting feature vectors from the obtained training data;

projecting the feature vectors onto a higher dimensional feature space that represents sub-character sections of the input handwriting;

aligning each feature vector against an appropriate one of the HMMs;

forming a cluster comprised of all feature vectors that are aligned against the same allograph;

determining a statistical description of each cluster;

forming a clustering tree in accordance with the statistical descriptions;

forming a set of prototypes from the clustering tree;

forming a set of elementary handwriting units from the clustering tree;

generating a set of HMMs for each allograph based on the formed set of prototypes and the formed set of elementary handwriting units;

performing a fast match of the sequence of feature vectors by generating a list of probable candidate characters sequentially using single-state, hidden Markov models (HMMs) having output probability distributions obtained from writer-independent higher dimensional feature space prototype distributions; and

performing a detailed match on the list of probable candidate characters using multi-state, writer independent HMMs to identify a most probable character sequence that the input handwriting represents.

13. A method as set forth in claim 12 wherein the step of generating an initial HMM for each allograph includes a step of, for each character of interest, representing each allograph in terms of a multi-state HMM, where each allograph represents a different style for writing the character of interest.

14. A method as set forth in claim 12 wherein the step of forming a clustering tree includes the steps of:

tagging individual ones of handwriting feature vectors in accordance with a statistical alignment;

constructing a binary clustering tree from the tagged feature vectors;

pruning the binary clustering tree in accordance with a predetermined pruning criteria to retain a first number of leaves L₁ for forming clusters;

further pruning the binary clustering tree to retain a second number of leaves L2, wherein L₂ <

L₁, for forming a plurality of elementary handwriting units representing a writer-independent label alphabet; and

establishing a relationship between the elementary handwriting units and clusters by a step of determining mixture coefficients.

15. A method as set forth in claim 14 wherein the step of tagging includes a step of:

in accordance with the statistical alignment, tagging each feature vector in a current higher dimensional feature space with an index which unambiguously identifies the following properties;

(a) an associated allograph identity L_x from an alphabet A_lx that contains all the allographs for all the characters, and (b) the position P of a state within the HMM associated with L_x against which the feature vector was aligned, wherein each distinct (L_x, P)

represents a leaf of the binary clustering tree; and

wherein the step of constructing the binary clustering tree includes the steps of,

(a) computing centroids for each distinct Leaf (L_x, P) using the tagged feature vectors;

(b) computing a distance D between each pair of centroids;

(c) ranking the centroid pairs in order of increasing distance D;

(d) computing a tentative new centroid for the top k (clustering) pairs;

(e) computing a distance D'"'"' between tentative new centroids and each remaining centroid;

(f) merging the centroid pair from the top k pairs which maximizes the distance D'"'"';

(g) determining if only one centroid is remaining, and if no, then repeating steps (b) through (g);

else

if only one centroid is remaining, then the step of constructing the binary clustering tree is complete.

16. A method as set forth in claim 15, wherein each of the steps of pruning are accomplished by the steps of:

(a) in accordance with the handwriting feature vectors and the constructed binary clustering tree, computing a number of vectors C for each distinct Leaf ((L_x, P) Tag);

(b) comparing the value of the vectors C to a predetermined minimum threshold value C_min to determine if C<

C_min, and if yes, merging the Leaf with its sibling;

(c) computing a change Δ

S in a spread S which would result from merging each Leaf with its sibling;

(d) merging a Leaf pair having a smallest Δ

S value to form a new Leaf;

(e) computing a new centroid and a new spread for the new Leaf;

(f) determining if the number of Leaves is greater than some predetermined number of Leaves;

(g) if the number of Leaves is greater than the predetermined number, then repeating steps (c) through (g), else

if the number of Leaves is not greater than the predetermined number, then the step of tree pruning is complete.

17. A method as set forth in claim 16, wherein for the first step of pruning the predetermined number of Leaves (L₁) is equal to approximately 750, and wherein for the second step of pruning the predetermined number of Leaves (L₂) is equal to approximately 100.

18. A method as set forth in claim 14 wherein the step of determining mixture coefficients includes the steps of:

in accordance with the tagged feature vectors, maintaining a record of cluster assignments at level L₁, and maintaining a record of elementary handwriting unit assignments at level L₂ ;

accumulating all assignment pairs at level L₁ and at level L₂ ; and

normalizing on a row-by-row basis to obtain a composition of elementary handwriting units in terms of cluster identities.

19. A method as set forth in claim 14 wherein the step of determining mixture coefficients includes the steps of:

in accordance with the tagged feature vectors, maintaining a record of cluster assignments at level L₁, and maintaining a record of elementary handwriting unit assignments at level L₂ ;

accumulating all assignment pairs at level L₁ and at level L₂ ; and

normalizing on a column-by-column basis to obtain a composition of clusters in terms of elementary handwriting unit identities.

20. A method as set forth in claim 12, wherein the step of obtaining training data includes the steps of pre-filtering data received from a digitizing tablet means, in response to a movement of a pen means, to normalize for a speed of the pen means when forming a stroke;

and interpolating the pre-filtered data, as necessary, to locate equally spaced points.

21. A method as set forth in claim 20 wherein the step of extracting parameter vectors includes the steps of, for each point P_n of coordinate (x_n,y_n) in the training data, forming a P-dimensional vector P_n of feature elements representative of a local pen means trajectory around P_n ;

and for each point P_n of coordinates (x_n,y_n) in the training data, forming a P'"'"'-dimensional vector P_n of feature elements representative of a global pen means trajectory up to P_n.

22. A method as set forth in claim 21 wherein feature elements of the P-dimensional vector P_n are given by:

(i) horizontal and vertical incremental changes;

(ii) the sine and cosine of the angle of the tangent to the pen means trajectory at P_n ; and

(iii) incremental changes in the sine and cosine of the angle of the tangent, and wherein feature elements of the P'"'"'-dimensional vector P_n are given by;

(i) the height from a baseline y_n, (ii) the width from the beginning of a stroke x_n -x_n, where xi is the first coordinate of a current stroke, and (iii) an inter-stroke distance if a current character is comprised of more than one stroke.

23. A method as set forth in claim 20 and further including a step forming a window by the steps of, for each stroke in the training data, determining a subset of the points P_n in that stroke Q_i, with each Q_i being approximately equally spaced apart;

at each location Q_i, constructing a Q-dimensional spliced vector by concatenating together the H vectors P_n preceding Q_i, the vector q_i corresponding to Q_i, and the H vectors P_n following Q_i ; and

constructing a Q'"'"'-dimensional spliced vector by concatenating together the H'"'"' vectors P'"'"'_n preceding Q_i, the vector q'"'"'_i corresponding to Q_i, and the H'"'"' vectors P_n following Q_i.