On-line connected handwritten word recognition by a probabilistic method

• US 5,392,363 A
• Filed: 11/13/1992
• Issued: 02/21/1995
• Est. Priority Date: 11/13/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fujisaki, Tetsunosuke, Nathan, Krishna S.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/975,864
• Time in Patent Office: 830 Days
• Field of Search: 382/13, 382/21, 382/37, 382/38, 382/39, 382/40, 382/25
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

Methods and apparatus are disclosed for recognizing handwritten words in response to an input signal from a handwriting transducer. The method includes the steps of: (a) partitioning the input signal into N frames; and (b) processing words from a vocabulary model to determine, for each processed word, a probability that the word represents a written word that is conveyed by the input signal. The determined probability is a function of N letter-frame alignment probabilities and also a probability based on a grouping of the N frames into L groups, where L is a number of letters in the word. A further step (c) identifies a word having a highest determined probability as being a most-likely word that is conveyed by the input signal. The determined probability is also a function of (a) a probability based on a frequency of occurrence of words and portions of words within a selected language model; and (b) when processing a frame other than the Nth frame, a number of frames that remain to be processed. In one embodiment of the invention all words in the vocabulary model are searched in parallel, thereby significantly reducing the recognition time. The use of a beam search technique is illustrated to perform the parallel search. Also, this invention teaches the use of hashing to increase the speed of the beam search technique.

Claims

1. Handwriting recognition apparatus, comprising:

handwriting transducer means having an output providing temporally-ordered stroke coordinate information generated by a writer while writing, in a cursive manner, a word that includes at least one letter;

a pre-processor, comprising,

a splicer having an input coupled to said output of said handwriting transducer means for partitioning the temporally ordered stroke coordinate information into a plurality of frames, each frame containing at least a portion of a stroke; and

a frame shape recognizer coupled to an output of said Splicer for assigning to each frame a probability that the portion of a stroke that is contained within a frame f_j is a part of a letter belonging to an alphabet a_i ;

said handwriting apparatus further comprising a word recognizer having an input coupled to an output of said pre-processor and an output for outputting a most probable word that was written by the writer, said word recognizer comprising,

a vocabulary model stored within said handwriting recognition apparatus and containing a plurality of words, each of the words including at least one character, said vocabulary model being organized as a data structure having a root node, a plurality of intermediate nodes each representing a letter of the alphabet a_i belonging to at least one word, and a plurality of leaf nodes each representing a terminal letter of a word; and

a decoder processor having a first input coupled to an output of said pre-processor and a second input coupled to an output of said vocabulary model, said decoder processor including means for processing, in turn, each of said frames in cooperation with said vocabulary model to determine a most probable letter-frame alignment and for identifying a most probable word written by the writer to be output from said word recognizer.

2. Apparatus as set forth in claim 1 wherein said splicer operates to partition the stroke coordinate information into a plurality of overlapping frames of equal length.

3. Apparatus as set forth in claim 1 wherein said processing means includes means, responsive to information stored within said vocabulary model, for employing at least one conditional probability to identify a most probable word written by the writer.

4. Apparatus as set forth in claim 3 wherein said at least one conditional probability is a function of a frequency of occurrence of words and portions of words within a selected language model.

5. Apparatus as set forth in claim 3 wherein said at least one conditional probability is a function of a number of frames that remain to be processed.

6. Apparatus as set forth in claim 3 wherein said at least one conditional probability is a function of a distribution of a number of frames for each possible letter.

7. Apparatus as set forth in claim 1 wherein said processing means includes means for establishing a search space within said memory, said search space being represented by a two dimensional array having N columns and L rows, wherein N=a number of frames, and where L=a number of letters in a word found within said vocabulary model.

8. Apparatus as set forth in claim 7 wherein said processing means further includes means for managing, within said memory, a plurality (N×

L) of stacks each having at least one entry, said at least one entry including information for specifying a node of said vocabulary model and a probability that a letter string associated with the node represents at least a part of the word written by the writer.

9. Apparatus as set forth in claim 7 wherein said processing means includes means for managing, within said memory, a stack having a plurality of entries, each of said entries including information for specifying a node of said vocabulary model, information for identifying a row and a column location within said two dimensional array, and a normalized probability that a letter string associated with the node represents at least a part of the word written by the writer.

10. Apparatus as set forth in claim 9 wherein said memory further includes a hash table having a plurality of entries, each of said hash table entries including information for representing the normalized probability stored within an entry of said stack, and where said processing means further includes means for generating an index into said hash table in accordance with information that specifies a node of said vocabulary model and information that identifies a row and a column location within said two dimensional array.

11. A method for operating a handwriting recognition apparatus, comprising the steps of:

outputting temporally ordered stroke coordinate information generated by a writer while writing, in a cursive manner, a word that includes at least one character;

operating a handwriting recognition pre-processor in response to outputted stroke coordinate information by the steps of,

operating a splicer to perform a step of partitioning the outputted temporally ordered stroke coordinate information into a plurality of frames, each frame containing at least a portion of a stroke; and

operating a frame shape recognizer to perform a step of assigning to each frame a probability that the portion of a stroke that is contained within a frame f_j is a part of a letter belonging to an alphabet a_i ;

the method further comprising a step of operating a word recognizer for outputting a most probable word that was written by the writer by the steps of,

performing an initial step of storing a vocabulary model as a data structure within a memory of the handwriting recognition apparatus, the data structure being organized to have a root node, a plurality of intermediate nodes each representing a letter of the alphabet a_i belonging to at least one word, and a plurality of leaf nodes each representing a terminal letter of a word; and

operating a decoder processor to process, in turn, each of the frames in cooperation with information retrieved from the vocabulary model to determine a most probable letter-frame alignment for identifying a most probable word written by the writer for output from the word recognizer.

12. A method as set forth in claim 11 wherein the step of operating the decoder processor to process the frames includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a frequency of occurrence of words and portions of words within a selected language model represented within the vocabulary model.

13. A method as set forth in claim 11 wherein the step of operating the decoder processor to process the frames includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a number of frames that remain to be processed.

14. A method as set forth in claim 11 wherein the step of operating the decoder processor to process the frames includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a distribution of a number of frames for each possible letter.

15. A method as set forth in claim 11 wherein the step of operating the decoder processor to process the frames includes a step of establishing a two dimensional array having N columns and L rows, wherein N=a number of frames, and wherein L=a number of letters in a word found within the vocabulary model.

16. A method as set forth in claim 15 wherein the step of operating the decoder processor to process the frames further includes a step of managing a plurality (N×

L) of stacks each having at least one entry, said at least one entry including information for specifying a node of the vocabulary model and a probability that a letter string associated with the node represents at least a part of the word written by the writer.

17. A method as set forth in claim 15 wherein the step of operating the decoder processor to process the frames further includes a step of managing a stack having a plurality of entries, each of the entries including information for specifying a node of the vocabulary model, information for identifying a row and a column location within the two dimensional array, and a normalized probability that a letter string associated with the node represents at least a part of the word written by the writer.

18. A method as set forth in claim 17 wherein the step of operating the decoder processor to process the frames further includes the steps of:

storing a hash table having a plurality of entries, each of the hash table entries including information for specifying the normalized probability stored within an entry of the stack; and

generating an index into the hash table in accordance with information that specifies a node of the vocabulary model and in accordance with information that identifies a row and a column location within the two dimensional array.

19. A method for recognizing handwriting that includes cursively written words, comprising the steps of:

storing a vocabulary model organized as a trie data structure having a root node, a plurality of intermediate nodes each representing a letter of an alphabet a_i belonging to at least one word, and a plurality of leaf nodes each representing a terminal letter of a word;

outputting to a data processor, from a handwriting transducer, temporally ordered stroke coordinate information generated by a writer while cursively writing a word that includes at least one letter;

partitioning, with the data processor, the outputted temporally ordered stroke coordinate information into a plurality of frames, each frame containing at least a portion of a stroke;

operating the data processor to determine a probability that the portion of a stroke that is contained within a frame f_j is a part of a letter belonging to the alphabet a_i ; and

operating the data processor to access the stored vocabulary model to process, in parallel, a plurality of the nodes of the vocabulary model with, in turn, each of the frames to identify a most probable word written by the writer.

20. A method for recognizing handwriting that includes cursively written words, comprising the steps of:

storing a vocabulary model organized as a trie data structure having a root node, a plurality of intermediate nodes each representing a letter of an alphabet a_i belonging to at least one word, and a plurality of leaf nodes each representing a terminal letter of a word;

outputting to a data processor, from a handwriting transducer, temporally ordered stroke coordinate information generated by a writer while cursively writing a word that includes at least one letter;

partitioning, with the data processor, the outputted temporally ordered stroke coordinate information into a plurality of frames, each frame containing at least a portion of a stroke;

operating the data processor to determine a probability that the portion of a stroke that is contained within a frame f_j is a part of a letter belonging to the alphabet a_i ; and

operating the data processor to access the stored vocabulary model to process, with a beam search technique, the nodes of the vocabulary model with, in turn, each of the frames to identify a most probable word written by the writer.

21. A method as set forth in claim 20 wherein the step of operating the data processor to process the nodes of the vocabulary model with the beam search technique includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a distribution of a number of frames for each possible letter of the alphabet a_i.

22. A method as set forth in claim 20 wherein the step of operating the data processor to process the nodes of the vocabulary model with the beam search technique includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a frequency of occurrence of words and portions of words within a selected language model that is represented by the vocabulary model.

23. A method as set forth in claim 20 wherein the step of operating the data processor to process the nodes of the vocabulary model with the beam search technique includes a step of determining at least one conditional probability from a node of the vocabulary model, the at least one conditional probability being a function of a number of frames that remain to be processed.

24. A method as set forth in claim 20 wherein the step of operating the data processor to process the nodes of the vocabulary model with the beam search technique includes the steps of:

establishing a search space as a two dimensional array having N columns and L rows, wherein N=a number of frames, and wherein L=a number of letters in a word of the vocabulary model; and

managing a global stack having a plurality of entries, each of the entries including information for specifying a node of the vocabulary model, information for identifying a row and a column location within the two dimensional array, and a normalized probability that a letter string associated with the node represents at least a part of the word written by the writer.

25. A method as set forth in claim 24 wherein the step of operating the data processor to process the nodes of the vocabulary model with the beam search technique further includes the steps of:

storing within a memory a hash table having a plurality of entries, each of the hash table entries including information for specifying the normalized probability stored within an entry of the global stack; and

generating an index into the hash table in accordance with information that specifies a node of the vocabulary model and in accordance with information that identifies a row and a column location within the two dimensional array.

26. A method for recognizing handwritten words in response to an input signal from a handwriting transducer, comprising the steps of:

performing an initial step of preparing models for each letter that may be included within a word belonging to a vocabulary of words;

storing the prepared letter models;

operating a data processor to perform the steps of,

partitioning the input signal into a plurality of frames, each frame including at least one portion of a handwritten stroke;

determining for each frame a likelihood that the portion of the stroke contained therein is a portion of a letter belonging to a predetermined letter set;

based on the prepared letter models,

(1) choosing one word from a vocabulary at a time;

(2) for a word chosen from the vocabulary, and in accordance with the likelihoods determined for each frame, finding a most-likely letter and frame alignment and a likelihood score that indicates a probability that the input signal was generated in response to a writing that corresponds to the chosen word;

(3) repeating steps 1 and 2 for all words in the vocabulary; and

for a letter and frame alignment that gives the best likelihood score, identifying the corresponding word from the vocabulary as being a most-likely word that corresponds to the input signal.

27. A method for recognizing handwritten words in response to an input signal from a handwriting transducer, comprising the steps of:

performing an initial step of preparing models for each letter that may be included within a word belonging to a vocabulary of words;

storing the prepared letter models;

operating a data processor to perform the steps of,

partitioning the input signal into a plurality of frames, each frame including at least one portion of a handwritten stroke;

determining for each frame a likelihood that the portion of the stroke contained therein is a portion of a letter belonging to a predetermined letter set;

based on the prepared letter models,

processing in parallel all words from a vocabulary to determine, for each word in the vocabulary, and in accordance with the likelihoods determined for each frame, a most-likely letter and frame alignment and a likelihood score that indicates a probability that the input signal was generated in response to a writing that corresponds to the word in the vocabulary; and

for a letter and frame alignment that gives the best likelihood score, identifying the associated word from the vocabulary as being a most-likely word that corresponds to the input signal.

28. A method for recognizing handwritten words in response to an input signal from a handwriting transducer, comprising the steps of:

partitioning the input signal into N frames;

operating a data processor to determine for each of the N frames a probability that the portion of the input signal contained therein is a portion of a letter belonging to a predetermined letter set;

accessing a vocabulary model with the data processor to retrieve a word therefrom;

processing the retrieved word to determine a probability that the word represents a written word that is conveyed by the input signal, the determined probability being a function of N letter-frame alignment probabilities and also being a function of a probability based on a grouping of the N frames into L groups, where L is a number of letters in the word being processed; and

identifying a word having a highest determined probability as being a most-likely word that is conveyed by the input signal.

29. A method as set forth in claim 28 wherein the step of processing processes all of the words from the vocabulary model in parallel.

30. A method as set forth in claim 28 wherein the determined probability is also a function of a probability based on a frequency of occurrence of words, and portions of words, within a selected language model.

31. A method as set forth in claim 28 wherein, for each word, the N letter-frame alignment probabilities are determined by processing each of the N frames in turn, and wherein the determined probability is also a function, when processing a frame other than the Nth frame, of a number of frames that remain to be processed.

32. A method as set forth in claim 28 wherein the input signal represents a plurality of strokes, and wherein each of the N frames is ordered by an x-axis coordinate that lies at a center of each frame.

33. Apparatus for recognizing handwritten words in response to an input signal from a handwriting transducer means, comprising:

a splicer for partitioning the input signal into N frames;

a frame shape recognizer coupled to an output of said splicer for assigning to each of said N frames a probability that the portion of a stroke that is contained within a frame f_j is a part of a letter belonging to an alphabet a_i ;

a vocabulary model that is coupled to a data processor for being accessed thereby;

said data processor including means for processing words read from said vocabulary model to determine, for each processed word, a probability that the word represents a written word that is conveyed by the input signal, the determined probability being a function of N letter-frame alignment probabilities and also a probability based on a grouping of the N frames into L groups, where L is a number of letters in the word; and

means for identifying a word having a highest determined probability as being a most-likely word that is conveyed by the input signal.

34. A method for recognizing handwritten words in response to an input signal from a handwriting transducer, comprising the steps of:

receiving an input signal from a handwriting transducer, the input signal including temporally ordered stroke coordinate information; and

operating a data processor to perform the steps of,

partitioning the input signal into N frames;

assigning to each of said N frames a probability that a portion of the input signal that is contained within a frame f_j is a part of a letter belonging to an alphabet a_i ;

accessing a vocabulary model that stores a plurality of words;

processing words read from the vocabulary model in accordance with a beam search technique to determine, for each processed word, a probability that the word represents a written word that is conveyed by the input signal; and

identifying a word having a highest determined probability as being a most-likely word that is conveyed by the input signal;

wherein

the step of processing maintains a stack for storing a plurality of the determined probabilities;

wherein

the step of processing further maintains a hash table having entries, each of the entries storing an individual one of the plurality of determined probabilities; and

wherein

the step of processing includes a step of accessing an entry within the hash table to compare a currently determined probability against a determined probability that is stored within the entry of the hash table.

35. A method as set forth in claim 34 wherein each of the determined probabilities that are stored within the stack and within the hash table is first normalized in accordance with an associated path length through a search space.

36. A method as set forth in claim 34 wherein the step of accessing an entry within the hash table includes a step of forming a key that includes information specifying a current location within a search space and also information specifying a location within the vocabulary model.