Handwriting recognition system simultaneously considering shape and context information

• US 6,137,908 A
• Filed: 06/29/1994
• Issued: 10/24/2000
• Est. Priority Date: 06/29/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rhee, Sung Sik
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/269,156
• Time in Patent Office: 2,309 Days
• Field of Search: 382/186, 382/187, 382/179, 382/203, 382/226, 382/227, 382/228, 382/229
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2272 with lexical matching
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

The speed and accuracy of a computer implemented handwriting recognition system is enhanced by several innovations, including integrated segmentation and context processing. The recognition processing occurs while the user is providing ink data. The system quickly reaches the recognition result once all of the input is received. More than one result may be returned by the system.

Claims

1. A method of processing data that represents strokes of handwritten information, thereby to identify characters represented by the data, the method comprising the steps of:

receiving the data provided by a user, the data having a beginning part and an end part that define therebetween a complete amount of handwritten information to be processed;

assembling portions of the data into a sequence of packages; and

determining for the sequence of packages a probable result set of characters represented by the sequence, the determining step occurring before the end part of the data is received and comprising the steps of simultaneously considering information pertaining to the character shapes represented by the packages and information pertaining to the literal context of the characters represented by the packages;

wherein the determining step includes searching for the result set of characters from among a plurality of character candidates using a first search technique; and

wherein the first of two search techniques comprises the steps of;

developing for each package at least one path representing a string of character candidates, each path having a respective beginning and a respective end; and

generating for each path a first cost value that reflects the probability that the path includes the result set of characters, the first cost value being based upon information pertaining to the character shapes represented by the packages and information pertaining to the literal context of the characters represented by the packages and

wherein the second of the two search techniques assigns a second cost value to a considered path based upon the literal context of the considered path, and wherein the second search technique conducts a reverse search towards the respective beginning of at least some of the paths developed by the first search technique to identify the result set as a path having the lowest of the combine first and second cost values.

2. The method of claim 1 wherein the second of the search techniques assigns the second cost value to a considered path based upon whether the character string represented by the path appears in a dictionary.

3. The method of claim 1 wherein considering the information pertaining to the character shapes represented by the packages and the information pertaining to the literal context of the characters represented by the packages includes considering the likelihood of the occurrence of three adjacent character candidates.

4. The method of claim 1 wherein considering the information pertaining to the character shapes represented by the packages and the information pertaining to the literal context of the characters represented by the packages includes comparing the relative sizes of adjacent character candidates to establish whether one of the character candidates is an uppercase character.

5. A method of processing data that represents strokes of handwritten information, thereby to identify characters represented by the data, the method comprising the steps of:

receiving the data provided by a user, the data defining an amount of handwritten information to be processed;

assembling portions of the data into a sequence of packages;

determining for the sequence of packages a probable result set of characters represented by the sequence, the determining step comprising the step of simultaneously considering information pertaining to the character shapes represented by the packages and information pertaining to the literal context of the characters represented by the packages

wherein the determining step includes searching for the result set of characters from among a plurality of character candidates using a first search technique and combining the first search technique with a second search technique that is performed subsequent to the first technique;

wherein considering the information pertaining to the character shapes represented by the packages and the information pertaining to the literal context of the characters represented by the packages includes considering whether the size of a space between two adjacent character candidates exceeds a predetermined amount representative of a space between adjacent character candidates.

6. A method of processing a received stream of data that is representative of stylus tip movement on a tablet or the like, comprising the steps of:

dividing the stream into a plurality of sequential frames;

combining the frames of input data into one or more packages;

assigning one or more character hypotheses to at least some of the packages;

constructing in a sequence conforming to the sequence with which the data is received paths of multiple character hypotheses;

assigning to portions of the paths values based upon the shape and literal context of the character hypotheses contained in the path; and

reverse-searching the constructed paths in a direction opposite to the direction the data was received.

7. The method of claim 6 wherein the reverse-searching step includes using the values assigned in the assigning step to direct the reverse-search.

8. The method of claim 6 including the step of beginning the constructing step before the end of the stream of data is received.

9. The method of claim 6 including the step of receiving the data stream provided by a user, the data stream having a beginning part and an end part that define therebetween an amount of handwritten information to be processed and wherein the constructing step is executed as soon as the beginning part is provided by a user.

10. A handwriting recognition system for providing a result of a recognition task comprising:

input means for collecting ink data that represents strokes of handwritten information, the data having a beginning part and an end part that define therebetween an amount of handwritten information to be processed;

classifier means for providing character hypotheses based the ink data; and

search means for selecting the result by substantially simultaneously considering the shape and literal content of the character hypotheses as soon as the beginning part is provided by a user.

11. The system of claim 10 wherein the search means includes first search means for modeling the collected ink data as dynamic programming paths each having a beginning and an end;

and

second search means for reverse searching the paths modeled by the first search means towards their respective beginnings.