Letter model and character bigram based language model for handwriting recognition

• US 8,559,723 B2
• Filed: 09/29/2008
• Issued: 10/15/2013
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stevens, Dave, Miljanic, Veljko
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Dunphy, David F
• Application Number:
  US12/239,850
• Publication Number:
  US 20100080462A1
• Time in Patent Office: 1,842 Days
• Field of Search: None
• US Class Current: 382/186
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A handwriting recognition system is described that includes a language model with scoring to improve recognition accuracy, such as for words outside of a selected language model. The handwriting recognition system increases the accuracy of handwriting recognizers that perform segmentation of ink into atomic elements (segments) and then classify each ink segment separately. After segmentation, a shape classifier estimates the class (letter) probabilities for each segment of ink by producing a corresponding score. The system applies the language model scoring to the shape classification results and typically selects the class with the highest score as the recognition result. Because the language model is not too restrictive, it works well for recognizing any word, even those that would not be in a dictionary for the current language. Thus, the handwriting recognition system produces better recognition results and can often recognize words that dictionary-based language models would not recognize correctly.

Claims

1. A computer-implemented method for recognizing user handwriting, the method comprising:

receiving digital ink based on handwriting received from a user;

identifying words within the received digital ink;

for an identified word, identifying segments within the word that are potential characters or parts of characters of the word, the segments having an order, wherein at least some characters are composed of multiple segments;

applying a classifier to each segment of the word to compute a set of segment probabilities for each segment, each segment having a respective set of probabilities, each segment probability indicating a probability that the segment is a particular part of a particular letter, wherein each set of probabilities for a segment comprises probabilities that the segment corresponds to various parts of various letters according to the shape classifier;

applying a language model to alternatives to compute scores for the alternatives, respectively, each alternative comprising one probability from each set of probabilities, the probabilities of each alternative ordered according to the order of the segments, the language model computing a score for an alternative according to bigram probabilities corresponding to the letters, the bigram probabilities computed in advance from a corpora, each bigram indicating a probability that two letters occur in succession, each score of an alternative further computed according to probabilities segments in the alternative are successive parts of a same letter, each score of an alternative further computed according to probabilities the segments thereof are end segments of a letter corresponding to the alternative;

selecting a recognition result for the word based on the determined scores, the recognition result comprising the alternative corresponding to a selected one of the scores.

2. The method of claim 1 wherein the classifier classifies each segment by searching to produce a classification for each possible letter in a language.

3. The method of claim 1 wherein identifying words within the received digital ink comprises invoking a language independent shape classifier that evaluates the probability of space between successive ink strokes.

4. The method of claim 1 wherein determining a score comprises applying the Viterbi algorithm to reduce computational complexity.

5. The method of claim 1 wherein selecting a recognition result comprises selecting the recognition result having a highest score.

6. The method of claim 1 wherein the received digital ink includes at least one word that is not present in the dictionary of words of the currently selected language and wherein selecting the recognition result correctly identifies the word.

7. A computer system for recognizing user handwriting, the system comprising:

an input device that receives input from a user and communicate the input as digital ink to an application;

a word breaking component that divides the received digital ink into one or more words;

an ink segmenting component that divides a word into one or more ink segments;

a shape classifying component that determines one or more classifications that associate each ink segment as a part of a particular letter;

a language model scoring component that assigns a probability to each of the classifications, the language model comprising bigram probabilities computed in advance from a corpora, each bigram probability indicating a probability that two letters occur in succession, the scoring component computing a score according to bigram probabilities corresponding to letters identified by the classifying component, each score further computed according to probabilities segments are successive parts of a same letter, each score further computed according to probabilities the segments are end segments of a letter identifying by the shape classifying component;

a recognition result component configured to produce a recognition result for each word based on scores computed by the language model.

8. The system of claim 7 wherein the input device is selected from the group consisting of a stylus, a digital pen, a mouse, and a user'"'"'s finger moving over a touch screen.

9. The system of claim 7 wherein the input device is further configured to provide received input as an array of ink strokes.

10. The system of claim 7 wherein the word breaking component identifies ink strokes based on detecting a threshold amount of space between strokes.

11. The system of claim 7 wherein the shape classifying component exhaustively attempts to classify each segment as every available letter in a target language and determine which classification is the most probable.

12. The system of claim 7 wherein the shape classifying component uses separate classes for the first ink segment in a letter and for continuation ink segments in the letter to better distinguish boundaries between letters.

13. A computer-readable storage device encoded with instructions for controlling a computer system to determine a score for a recognition alternative, by a method comprising:

receiving a digital ink segment that makes up part of a word;

adjusting a score based on output of a shape classifier for a recognition alternative of the digital ink segment;

if the digital ink segment is the last segment in a letter, adjusting the score based on the probability that the letter ends in the digital ink segment;

if there are more ink segments in the word, adjusting the score based on a bigram probability between the letter and a subsequent letter, the bigram probability selected according to the letter and the subsequent letter from among a set of bigram probabilities computed in advance from a corpora, wherein each bigram probability indicating a probability that two letters appear in succession in a word; and

if the digital ink segment is the last segment in the word, providing the score for the recognition alternative by applying a weak-constrained language model that recognizes words not present in a dictionary of words of a currently selected language, the weak-constrained language model comprising probabilities that segments are last segments of letters.

14. The device of claim 13 wherein the method comprises a language model that exhaustively considers each possible letter in a target language.

15. The device of claim 13 wherein the method avoids at least one calculation using the Viterbi algorithm.

16. The device of claim 13 wherein the provided score indicates the likelihood that the recognition alternative is the correct answer for the word.