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

• US 6,418,239 B1
• Filed: 05/16/2000
• Issued: 07/09/2002
• Est. Priority Date: 06/06/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Haluptzok, Patrick M., Hullender, Gregory N.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/572,668
• Time in Patent Office: 784 Days
• Field of Search: 382/229, 382/227, 382/187, 382/188, 382/189, 382/230, 382/156, 382/157, 382/158
• 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 computer-readable medium having computer-executable instructions, comprising:

receiving a plurality of current alternates corresponding to a set of input data of a plurality of sets of input data, each of the current alternates having information associated therewith corresponding to a probability;

determining a cost from each of the current alternates to previous alternates of a set of previous alternates of a previous set of input data of the plurality of sets of input data, 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 converges to a common previous alternate, recognizing the common previous alternate as output data for the previous set of input data to provide a partial recognition result relative to the plurality of sets of input data.

2. The computer-readable medium of claim 1 wherein the set of previous alternates corresponds to a plurality of alternate characters, and wherein the output data corresponds to a character of the plurality.

3. The computer-readable medium of claim 1 wherein the set of input data corresponds to a handwritten symbol.

4. The computer-readable medium of claim 1 wherein the output data corresponds to a code point.

5. In a computing device, a system comprising:

a user interface configured to receive sets of input data;

a matching mechanism connected to the user interface and configured to provide alternate data corresponding to each set of input data, the alternate data including a set of at least one alternate for each set of input data and probability information for each alternate;

an analyzer mechanism connected to the matching mechanism to analyze selected alternate data associated with a selected set of input data with prior alternate data associated with at least one set of prior input data, to;

1) determine a lowest cost path between each alternate in the selected set and an alternate in the prior set based on the probability information for each alternate and a transition cost therebetween,

2) detect when the lowest cost path for each alternate in the selected set points to a common alternate in the prior set,

3) provide output data corresponding to at least one set of prior input data when each alternate in the selected set points to a common alternate in the prior set; and

4) provide the output data to the user interface as a partial recognition result relative to other sets of input data received at the user interface.

6. The system of claim 5 wherein each set of alternate data includes at least one possible code point.

7. The system of claim 5 wherein the context analyzer provides the output data to the user interface by providing at least one code point thereto.

8. A system for recognizing hand written information input thereto, comprising:

a shape matcher that receives a plurality of sets of hand written information and for each set of handwritten information, generate shape information comprising sets of alternates having associated probability information;

a context analyzer connected to the shape matcher to analyze the shape information, the context analyzer configured to determine paths from the alternates of one set of shape information to the alternates of a prior set of shape information, and to select a best path from each alternate in the one set to a prior alternate in the prior set based on the probability information associated therewith and a transition cost therebetween, the context analyzer further configured to detect when the best paths from the alternates of the one set of shape information converge at a common alternate of the prior set of shape information, and if detected, to recognize the common alternate as corresponding to an output symbol.

9. The system of claim 8 wherein the alternates correspond to a plurality of alternate characters, and wherein each output symbol corresponds to a character.

10. The system of claim 8 wherein the alternates correspond to a plurality of alternate output symbols.

11. The system of claim 8 wherein the context analyzer further recognizes an output symbol for each alternate on a lowest cost path back from the common alternate.