Method and mechanism for providing partial results in full context handwriting recognition

• US 6,111,985 A
• Filed: 06/06/1997
• Issued: 08/29/2000
• Est. Priority Date: 06/06/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hullender, Gregory N., Haluptzok, Patrick M.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E.
• Application Number:
  US08/870,558
• Time in Patent Office: 1,180 Days
• Field of Search: 382/229, 382/227, 382/226, 382/187, 382/188, 382/189, 382/230, 382/231
• US Class Current: 382/229
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

A method and mechanism for displaying partial results of full context handwriting recognition. As handwritten characters are entered into a system, a shape matcher associates the character with a plurality of alternate code points, with each alternate code point having probability information associated therewith. The alternate code points are placed at the end of a queue, and a cost is determined from each alternate code point to any immediately preceding alternate in the queue. The cost is based on the probability information of the alternates and a transition cost therebetween. Then, the lowest cost path back from each of the alternates at the end of the queue to an alternate at the beginning of the queue is determined. If each lowest cost path back converges to a common alternate in the queue, the common alternate and any previous alternates on the path back are recognized as the code points for each of the handwritten characters associated therewith. Because further context cannot affect change the value of these code points, the alternates corresponding to these code points are removed from the queue, and the code points appropriately displayed on a screen as recognized characters, to allow editing thereof. The ability to provide partial results with no loss of accuracy may be extended to include the case where the language model is an arbitrarily complex non-determinsitic state machine including the case where the state machine may be generated from a dictionary.

Claims

1. A method for recognizing a handwritten character previously input into a computer system when another character has been input into the system thereafter, comprising the steps of:

receiving a plurality of current alternates corresponding to a latest handwritten character, each of the current alternates having information associated therewith corresponding to a probability, and after each latest handwritten character is received;

determining a cost from each of the current alternates to each of the previous alternates of a previously input handwritten character, the cost based on probability information of each previous alternate, probability information of each current alternate and a transition cost therebetween;

determining a lowest cost from each of the current alternates to one of the previous alternates, and,

if the lowest cost of each of the current alternates is to a common previous alternate, recognizing the common previous alternate as a code point for the previous character.

2. The method of claim 1 wherein the step of recognizing the common previous alternate as a code point for the previous character further comprises the steps of determining the lowest cost path back from the common previous alternate to a preceding alternate thereof and recognizing the preceding alternate as a code point.

3. The method of claim 1 wherein the step of determining the lowest cost from each of the current alternates to one of the previous alternates includes the step of saving a backpointer pointing from each of the current alternates to the previous alternate having the lowest cost path thereto.

4. The method of claim 3, wherein if the lowest cost of each of the current alternates is not to a common previous alternate, further comprising the steps of, determining if an earlier set of preceding alternates representing an earlier character precedes the previous alternate, and if so, determining the lowest cost from each of the previous alternates having a backpointer thereto to one of the preceding alternates, and, if the lowest cost of each previous alternate having a backpointer thereto converges to a common preceding alternate thereof, recognizing the common preceding alternate as a code point for the earlier character.

5. The method of claim 4 wherein the step of recognizing the common preceding alternate as a code point for the earlier character further comprises the steps of, determining the lowest cost path back from the common preceding alternate to a still-earlier preceding alternate thereof, and recognizing the still-earlier preceding alternate as a code point.

6. The method of claim 1 wherein the step of recognizing the common previous alternate as a code point includes the step of displaying the code point.

7. The method of claim 1 wherein the step of receiving a plurality of current alternates corresponding to a latest handwritten character includes the steps of receiving information of the current handwritten character, passing the information to a shape matcher, and receiving a response from the shape matcher, the response including the alternates and the probability information associated with each alternate.

8. The method of claim 7 wherein a list of language model states is generated from the list of character alternates returned by the shape matcher, the list of language model states corresponding to different paths through the character alternates that are valid character transitions in a language model.

9. The method of claim 1 wherein the probability information is a negative natural log of a probability value, and the transition cost is a negative natural log of a probability value, and wherein the step of determining the cost from each of the current alternates to each of the previous alternates of a previously input handwritten character includes the step of summing the natural log values.

10. A mechanism for recognizing at least one handwritten character previously input into a computer system when another character has been input into the system thereafter, comprising:

means for receiving a set of a plurality of current alternates corresponding to a latest handwritten character, each of the current alternates having information associated therewith corresponding to a probability; and

a recognition mechanism operating as each set of current alternates is received to attempt to recognize based on the information associated with the current alternates at least one character that has been previously input into the computer system, the recognition mechanism including;

means for determining a cost from each of the current alternates to each of the previous alternates of a previously input handwritten character, the determination based on probability information of each previous alternate, probability information of each current alternate and a transition cost therebetween;

means for determining a lowest cost from each of the current alternates to one of the previous alternates,

means for detecting when the lowest cost of each of the current alternates is to a common previous alternate, and,

means for recognizing the common previous alternate as a code point for the previous character when the lowest cost of each of the current alternates is to a common previous alternate.

11. The mechanism of claim 10 wherein the means for recognizing the common previous alternate as a code point for the previous character further comprises means for determining the lowest cost path back from the common previous alternate to a preceding alternate thereof, and means for recognizing the preceding alternate as a code point.

12. The mechanism of claim 10 wherein the means for determining the lowest cost from each of the current alternates to one of the previous alternates includes means for saving a backpointer pointing from each of the current alternates to the previous alternate having the lowest cost path thereto.

13. The mechanism of claim 12 further comprising means for detecting when each of the current alternates is not to a common previous alternate, means for determining if an earlier set of preceding alternates representing an earlier character precedes the previous alternate, means for determining the lowest cost from each of the previous alternates having a backpointer thereto to one of the preceding alternates, and means for recognizing the common preceding alternate as a code point for the earlier character when the lowest cost of each previous alternate having a backpointer thereto converges to a common preceding alternate thereof.

14. The mechanism of claim 13 wherein the means for recognizing the common preceding alternate as a code point for the earlier character further comprises, means for determining the lowest cost path back from the common preceding alternate to a still-earlier preceding alternate thereof, and means for recognizing the still-earlier preceding alternate as a code point.

15. The mechanism of claim 10 wherein the means for recognizing the common previous alternate as a code point includes means for displaying the code point.

16. The mechanism of claim 10 wherein the means for receiving a plurality of current alternates corresponding to a latest handwritten character includes, means for receiving information of the current handwritten character, means for passing the information to a shape matcher, and means for receiving a response from the shape matcher, the response including the alternates and the probability information associated with each alternate.

17. The mechanism of claim 16 wherein a list of language model states is generated from the list of character alternates returned by the shape matcher, the list of language model states corresponding to different paths through the character alternates that are valid character transitions in a language model.

18. The mechanism of claim 10 wherein the probability information is a negative natural log of a probability value, and the transition cost is a negative natural log of a probability value, and wherein the means for determining the cost from each of the current alternates to each of the previous alternates of a previously input handwritten character includes means for summing the natural log values.

19. In a computer system, a method of recognizing at least one handwritten character entered into the system as subsequent handwritten characters are entered into the system, wherein each handwritten character is associated with a plurality of alternate code points therefor, with each alternate code point having probability information associated therewith, the method comprising the steps of, placing the alternate code points for each handwritten character entered at the end of a queue, and after each handwritten character is entered, determining a cost from each alternate in the queue to any immediately preceding alternate in the queue, the cost based on the probability information of the alternates and a transition cost therebetween, determining the lowest cost path back from each of the alternates at the end of the queue to an alternate at the beginning of the queue, and determining if each lowest cost path back converges at a common alternate in the queue, and if so, recognizing the common alternate and any alternates previous thereto on the path back as the code points for each of the handwritten characters associated therewith.

20. In a computer system, a method of recognizing at least one handwritten character entered into the system based on the context of a subsequent handwritten character entered into the system, comprising the steps of:

(a) receiving an entered handwritten character, and as each handwritten character is received;

(b) passing the handwritten character to a shape matcher and receiving a plurality of alternates therefor from the shape matcher, each alternate having a cost associated therewith corresponding to the likelihood of matching the character;

(c) identifying the received alternates as a set of currently active alternates;

(d) appending the alternates to a queue;

(e) determining if there is a previous set of alternates prior to the currently active alternates in the queue, and if not, returning to step (a);

(f) determining the cost from each of the currently active alternates to each of the alternates in the previous set of alternates, the determination based on the cost of each previous alternate, the cost of each currently active alternate and a transition cost therebetween;

(g) determining the lowest cost path from each of the currently active alternates to one of the previous alternates and associating a backpointer with each of the lowest cost paths;

(h) if the backpointers of each of the current alternates point to a common previous alternate,

recognizing the common previous alternate as a code point for the previous character, following backpointers on a path from the common previous alternate through any earlier alternates thereof until the beginning of the queue is reached, recognizing each earlier alternate on the path as a code point for each earlier character, and returning to step (a); and

(i) if the backpointers of each of the current alternates do not point to a common previous alternate,

re-identifying the set of currently alternates as the previous alternates having backpointers thereto, and returning to step (e).

21. A system for recognizing hand written characters input thereto, comprising:

a shape matcher, the shape matcher providing a plurality of alternates for each hand written character input, each of the plurality of alternates having probability information associated therewith; and

a context analyzer interfaced with the shape matcher to analyze shape information associated with at least one prior character with reference to a selected character and shape information associated with at least one subsequent character with reference to the selected character to recognize at least one hand written character before an entire character string has been input, the context analyzer recognizing at least one handwritten character based on the probability information and transition costs between the alternates.

22. The system of claim 21 further comprising a display for displaying images corresponding to recognized hand written characters.

23. The system of claim 21 wherein the context analyzer analyzes at least two paths back from at least two of the alternates of the selected character to at least one of the alternates of at least one prior character that has been previously input into the system to determine whether lowest cost paths back converge on a common alternate.

24. The system of claim 23 wherein if the lowest cost paths back converge on a common alternate, the system recognizes a code point based on the common alternate.

25. The system of claim 23 wherein if the lowest cost paths back converge on a common alternate, the system recognizes a code point based on the common alternate, and further recognizes a code point for each alternate on a lowest cost path back from the common alternate.

26. The system of claim 25 further comprising a display for displaying images corresponding to recognized code points.

27. A system for recognizing and outputting code points corresponding to hand written characters input thereto, comprising:

a shape matcher for providing shape information for each hand written character input, the shape information including a plurality of alternates and probability information for each alternate; and

a context analyzer connected to the shape matcher to analyze the shape information associated with a selected character and the shape information associated with at least one prior character relative to the selected character, the context analyzer recognizing at least one hand written character before an entire character string has been input by analyzing at least two paths back from at least two of the alternates of the selected character to at least one of the alternates of at least one prior character that has been previously input into the system to determine when the paths converge on a common alternate based on the probability information and transition costs between the alternates, and outputting a code point based on the common alternate.

28. The system of claim 27 wherein the context analyzer further recognizes and outputs a code point for each alternate on a lowest cost path back from the common alternate.

29. The system of claim 27 further comprising a display connected to the context analyzer for displaying images corresponding to recognized code points output thereby.

30. A computer-readable medium having computer-executable instructions for performing steps comprising:

maintaining a sequence of at least one set of alternates and any backpointers to the alternates in each set, each set of alternates corresponding to a previous handwritten character;

receiving a new handwritten character as a current character, and as each current character is input into the system;

(a) receiving a plurality of current alternates for the current handwritten character, each of the current alternates having information associated therewith corresponding to a probability;

(b) determining a path cost from each of the current alternates to each of the alternates of a most-recent set in the sequence, each path cost based on the probability information of each current alternate, probability information of each alternate of the most-recent set, and a transition cost therebetween;

(c) for each current alternate, determining which alternate of the most-recent set has a lowest path cost thereto, and providing a backpointer to that alternate;

(d) selecting as a currently selected group each alternate of the most-recent set of alternates that has at least one backpointer thereto;

(e) determining if the backpointers converge at a single alternate of the currently selected group, and if so,

(i) recognizing the single alternate as a recognized code point; and

(ii) determining if any sets precede the currently selected group in the sequence, and if so, for each preceding set, selecting the preceding set as the currently selected group, selecting as the single alternate the alternate having a backpointer from the alternate corresponding to the recognized code point, and repeating step (e)(i) until no sets precede the currently selected group;

and if not;

(iii) determining if any sets precede the currently selected group in the sequence, and if so, selecting the currently selected group as a formerly selected group, selecting as the currently selected group each alternate in the previous set of alternates that has at least one backpointer thereto from the formerly selected group, and returning to step (e).

31. The computer-readable medium of claim 30 wherein the step of recognizing the single alternate as a recognized code point includes the step of placing the code point into a recognition buffer.

32. The computer-readable medium of claim 31 having further computer-executable instructions for performing the step of displaying each code point in the recognition buffer.

33. The computer-readable medium of claim 30 having further computer-executable instructions for performing the step of removing from the sequence each set of alternates having a single alternate therein.

34. The computer-readable medium of claim 30 wherein if the step of determining if any sets precede the currently selected group in the sequence determines that none precede the currently selected group, the computer-readable medium having further computer-executable instructions for performing the step of awaiting receipt of another new handwritten character.

35. The computer-readable medium of claim 30 wherein if the step of determining if any sets precede the currently selected group in the sequence determines that none precede the currently selected group, the computer-readable medium having further computer-executable instructions for performing the step of awaiting receipt of another new handwritten character or receipt of a manual request to recognize.