Recognition of handwritten words

• US 5,649,027 A
• Filed: 05/31/1994
• Issued: 07/15/1997
• Est. Priority Date: 07/24/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mahajan, Milind Vasudeo, Pardikar, Shishir
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/252,056
• Time in Patent Office: 1,141 Days
• Field of Search: 382/185, 382/186, 382/189, 382/218, 382/219, 382/229
• US Class Current: 382/185
• CPC Class Codes: G06V 30/2272 with lexical matching

Abstract

A method and system of recognizing words from handwritten symbols that are recognized by a computer recognizer. The recognizer produces a set of one or more alternatives for each symbol and orders the alternatives within each set in terms of the probability that each alternative matches the handwritten symbol for the set. A sequence of strings, each string having one alternative from each set, is enumerated. The enumerating proceeds in order such that the most probable alternatives from each set are used before the lower probability alternatives. Preferably, each string enumerated is looked up in a computer dictionary before enumerating other strings. If the string is found in the dictionary, the string is displayed, and preferably further enumerating stops. In an alternative embodiment, plural strings are enumerated before looking up a string in the dictionary. In another embodiment, plural strings are displayed before stopping further enumeration. Amended symbols may be used to change individual characters within a previously recognized word. A set of alternatives for each amended symbol is coupled with the unchanged symbols before enumerating strings and looking the strings up in a dictionary.

Claims

1. A method of recognizing words from handwritten characters using a computer dictionary and a computer recognizer, the recognizer producing a set of one or more alternatives for each character in a handwritten word, with at least one set having plural alternatives, each alternative having a probability of corresponding to the character ranging from a highest probability alternative to a lowest probability alternative, comprising:

looking up in the computer dictionary a sequence of strings, each string having one alternative from each set and being looked up as a unit, the sequence being in a defined order based on the probabilities of the alternatives, the defined order being such that A varies from Y to 0, where Y is the number of sets produced from the word and A is the number of sets contributing an alternative that is the highest probability alternative of its set;

if the string is found in the dictionary, stopping further looking up if the number of strings found in the dictionary is equal to a preselected wordnumber value; and

displaying at least one of the strings found in the dictionary.

2. The method of claim 1 wherein the wordnumber value is selected as one.

3. The method of claim 1, further including selecting a maximum index value M which is less than the greatest number of alternatives of any set in the word, and wherein the looking up step includes looking up all combinations of the M most probable alternatives in each set before looking up any combinations of less probable alternatives.

4. The method of claim 3, further including:

increasing the maximum index value M by 1 or more after all possible strings have been looked up for the previous maximum index value M; and

looking up all combinations of the M most probable alternatives in each set before looking up any combinations of less probable alternatives.

5. The method of claim 3 wherein the maximum index value M is selected as 3.

6. The method of claim 1, further including displaying a string including the highest probability alternative for each set if there are no strings found in the dictionary.

7. The method of claim 1 wherein in response to a user writing amending character in order to change less than an entire word of previously recognized characters, the method further including producing a set of one or more alternatives for each amending character using the recognizer, grouping the characters not amended with each set produced for the amending characters, and repeating the looking up step using the grouped unchanged characters and each set for the amending characters.

8. The method of claim 1 wherein in response to a user writing an amending character in order to change a previously recognized character, the method further including producing a set of one or more alternatives for the amending character using the recognizer and excluding from the set any alternative that is identical to the previously recognized character.

9. The method of claim 1, further including establishing a maximum string count and stopping further looking up when the number of strings looked up equals the maximum string count.

10. A method of recognizing words from handwritten characters using a computer dictionary and a computer recognizer, the recognizer producing a set of one or more alternatives for each character in a handwritten word, with at least one set having plural alternatives, each alternative having a probability of corresponding to the character ranging from a highest probability alternative to a lowest probability alternative, comprising:

looking up in the computer dictionary a sequence of strings, each string having one alternative from each set and being looked up as a unit, the looking up proceeding in a defined order based on the probabilities of the alternatives, the defined order being such that strings with high probability alternatives are looked up before strings with low probability alternatives; and

if one of the strings is found in the dictionary, outputting the string found in the dictionary.

11. The method of claim 10, further including displaying a string comprising the highest probability alternative for each set of no string is found in the dictionary.

12. The method of claim 10, further including selecting a maximum index value M which is less than the greatest number of alternatives of any set in the world, and wherein the looking up step includes looking up all combinations of the M most probable alternatives in each set before looking up any combinations of less probable alternatives.

13. The method of claim 12, further including:

increasing the maximum index value M by 1 or more alter all possible strings have been looked up for the previous maximum index value M; and

looking up all combinations of the M most probable alternatives in each set before looking up any combinations of less probable alternatives.

14. The method of claim 12 wherein the maximum index value M is selected as 3.

15. The method of claim 10, further including establishing a maximum string count and stopping further looking up when the number of strings looked up equals the maximum string count.

16. The method of claim 10 wherein in response to a user writing amending characters in order to change less than an entire word of previously recognized characters, the method further including using the recognizer to produce a set of one or more alternatives for each amending character, grouping the characters not amended with each set produced, and repeating the looking up step using the grouped, unchanged characters and each set for the amending characters.

17. The method of claim 10 wherein in response to a user writing an amending character in order to change a previously recognized character, the method further including producing a set of one or more alternatives for the amending character using the recognizer and excluding from the set an alternative that is identical to the previously recognized character.

18. The method of claim 10 wherein the defined order in which the strings are looked up is such that A varies from Y to 0, where Y is the number of sets produced from the word and A is the number of sets contributing an alternative that is the highest probability alternative of its set.

19. A system for recognizing words from handwritten characters using a computer dictionary and a computer recognizer, the recognizer producing a set of one or more alternatives for each character in a handwritten word, with at least one set having plural alternatives, each alternative having a probability of corresponding to the character ranging from a highest probability alternative to a lowest probability alternative, comprising:

means for looking up in the computer dictionary a sequence of strings, each string having one alternative from each set and being looked up as a unit, the sequence being in a defined order based on the probabilities of the alternatives, the defined order being such that A varies from Y to 0, where Y is the number of sets produced from the word and A is the number of sets contributing an alternative that is the highest probability alternative of its set;

means for stopping further looking up if the number of strings found in the dictionary is equal to a preselected wordnumber value; and

means for displaying the strings found in the dictionary.

20. The system of claim 19, further including means for stopping further looking up when the number of strings looked up equals a predetermined maximum string count.

21. The system of claim 19, further including means for displaying a string consisting of the highest probability alternative for each set if there are no strings found in the dictionary.

22. The system of claim 19, further including means for preselecting the word number value as 1.

23. A method of recognizing a handwritten word from handwritten characters using a computer dictionary and a computer recognizer, the characters including an amending character that is written in order to change a previously recognized character, comprising:

producing a set of plural alternatives for the amending character, each alternative having a relative probability ranging from a highest probability to a lowest probability;

forming a sequence of strings in a defined order beginning with a string that includes the alternative with the highest probability, each string including unchanged previously recognized characters and an alternative from the set;

looking up in a computer dictionary one or more of the formed strings as units according to the defined order; and

displaying a string found in the dictionary.

24. The method of claim 23, further including excluding from the set an alternative that is identical to the previously recognized character.

25. The method of claim 23 wherein the recognizer assigns relative probabilities to each alternative and the forming strings step includes enumerating a sequence of one or more strings, each string having one alternative from the set, the enumerating proceeding in order such that alternatives having relatively high probability are used before alternatives having relatively low probability.

26. A system for recognizing words from handwritten characters, comprising:

a computer recognizer producing a set of one or more alternatives for each character in a handwritten word, with at least one set having plural alternatives, each alternative having a probability of corresponding to the character ranging from a highest probability alternative to a lowest probability alternative;

a computer dictionary;

means for looking up in a dictionary a sequence of strings, each string having one alternative from each set and being looked up as a unit, the looking up proceeding in a defined order based on the probabilities of the alternatives, the defined order being such that A varies from Y to 0, where Y is the number of sets produced from the word and A is the number of sets contributing an alternative that is the highest probability alternative of its set;

means for stopping further looking up of one of the strings is found in the dictionary; and

means for displaying the string found in the dictionary.

27. The system of claim 26, further including means for stopping further looking up when the number of strings looked up equals a predetermined maximum string count.

28. The system of claim 26, further including means for displaying a string consisting of the highest probability alternative for each set if there is no string found in the dictionary.

29. A computer storage medium having executable instructions for controlling a computer to recognize an input word having handwritten characters, the executable instructions including instructions for:

producing a set of one or more alternatives for each character in the input word, with at least one set having plural alternatives, each alternative having a probability of corresponding to the character ranging from a highest probability alternative to a lowest probability alternative;

looking up in a computer dictionary a sequence of strings, each string having one alternative from each set and being looked up as a unit, the the sequence being in a defined order based on the probabilities of the alternatives, the defined order being such that strings with high probability alternatives are looked up before strings with low probability alternatives; and

outputting one of the strings if the string being output is found in the dictionary.

30. The computer storage medium of claim 29, further including instructions for selecting a maximum index value M which is less than the greatest number of alternatives of any set in the world, and wherein the looking up instructions include instructions for looking up all combinations of the M most probable alternatives in each set before looking up any combinations of less probable alternatives.

31. The computer storage medium of claim 30, further including:

instructions for increasing the maximum index value M by 1 or more after all possible strings have been enumerated for the previous maximum index value M; and

instructions for causing the instructions for looking up and displaying to be executed in view of the increased maximum index value M.

32. The computer storage medium of claim 29, further including instructions for establishing a maximum string count and stopping further looking up when the number of strings looked up equals the maximum string count.

33. The computer storage medium of claim 29, further including instructions that, in response to a user writing amending characters in order to change less than an entire word of previously recognized characters, produce a set of one or more alternatives for each amending character, group the characters not amended with the sets produced for the amending characters, and cause the looking up instructions to be executed using the grouped characters and sets.

34. The computer storage medium of claim 29, further including instructions that, in response to a user writing an amending character in order to change a previously recognized character, produce a set of one or more alternatives for the amending character using the recognizer and exclude from the set an alternative that is identical to the previously recognized character.