Text recognizer and method using non-cumulative character scoring in a forward search

• US 6,285,786 B1
• Filed: 04/30/1998
• Issued: 09/04/2001
• Est. Priority Date: 04/30/1998
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Seni, Giovanni, Seybold, John
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/070,316
• Time in Patent Office: 1,223 Days
• Field of Search: 382/181, 382/182, 382/183, 382/184, 382/185, 382/186, 382/187, 382/188, 382/189, 382/190, 382/191, 382/193, 382/195, 382/199, 382/203, 382/206, 382/209
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

In a method of recognition of handwritten input, a preprocessing module (200) of a recognizer (203) having a recognition module (202), segments handwritten input into strokes, to provide stroke vectors. A search module (204) generates hypothetical character strings for scoring by the recognition module (202). A character hypothesis is generated which is a data set of a character, a start vector and an end vector. The recognizer (203) provides a non-cumulative score for the character hypothesis, where the score represents a likelihood of the character being present in the handwritten input at a position starting at the start vector and ending at the end vector. The recognizer (203) delivers to the search module a result that is either the score for the selected first character hypothesis or a result that allows the search module to temporarily ignore the hypothesis or to kill it altogether. The search module maintains or disregards the first hypothetical character string dependent on the result. The process is repeated for other character hypotheses and other hypothetical character strings.

Claims

1. A text recognizer comprising a non-cumulative character recognition module for providing an indication of the likelihood that a given character is present in a handwritten input at a position starting at a start vector and ending at an end vector, the recognition module coupled to a forward search module to enable multiple parallel non-cumulative scores to be delivered from the character recognition module to the search module, wherein the character recognition module has means for delivering a first out-of-range message to the forward search module indicative of an inability to score a handwriting recognition theory in response to a request from the forward search module defining a selected character theory which encompasses insufficient number of stroke vectors for a character recognition operation to be completed.

2. The text recognizer of claim 1, wherein the forward search module has means for temporarily skipping further evaluation of the selected character theory in response to receipt of the first out-of-range message.

3. The text recognizer of claim 1, wherein the character recognition module has means for delivering a second out-of-range message to the forward search module in response to a request from the forward search module defining a selected character theory that encompasses a number of stroke vectors that is in excess of a predetermined limit for the selected character theory.

4. The text recognizer of claim 3, wherein the forward search module has means for pruning the selected character theory in response to receipt of the second out-of-range message.

5. The text recognizer of claim 1, wherein the character recognition module has means for receiving a request from the forward search module, including a value indicative of a position in an ink stream, means for computing probabilities for a plurality of characters in the ink stream forward of that position and means for delivering to the search module a look-ahead value equivalent to a maximum of those probabilities.

6. The text recognizer of claim 5 wherein the search module has decision means, responsive to the look-ahead value from the character recognition module, for deciding whether to propagate a new theory.

7. The text recognizer of claim 1, wherein the character recognition module has means for receiving a request from the forward search module, including a value indicative of a position in an ink stream, and the recognition module has means for providing to the search module an invalid character list, indicating characters rendered invalid by virtue of a property of the position in the ink stream.

8. The text recognizer of claim 7, wherein the search module has means for temporarily skipping further evaluation of all theories associated with characters of the received invalid character list.

9. A method of recognition of handwritten input comprising:

segmenting the handwritten input into strokes in a preprocessing module, to provide stroke vectors;

delivering one or more out-of-range messages based on the number of provided stroke vectors;

creating a first hypothetical character string in a search module;

creating a first character hypothesis in a search module, the first character hypothesis being a first data set comprising a first character, a first start vector and a first end vector, wherein the first character is a member of the first hypothetical character string;

requesting, from the search module to a character recognition module, a non-cumulative score for the first character hypothesis, where the score represents a likelihood of the first character being present in the handwritten input at a position starting at the start vector and ending at the end vector;

delivering upon request from the character recognition module to the search module multiple Darallel non-cumulative scores for the first character hypothesis; and

selectively maintaining the first hypothetical character string dependent on the scores.

10. The method of claim 9, comprising a step of creating sets of multiple character hypotheses and multiple hypothetical character strings in the search module and requesting multiple scores for the multiple character hypotheses from the character recognition module, wherein numbers of character hypotheses and hypothetical character strings created are constrained by a beam width which is bounded by a range of scores permissible below a maximum score.

11. The method of claim 9, comprising a further step of spawning, for a given selected first character hypothesis, a child character hypothesis which is an expansion of the first hypothetical character string and which comprises a second character hypothesis being a second data set comprising a second character, a second start vector and a second end vector.

12. The method of claim 11, wherein the child character hypothesis is spawned only when the score for the first character hypothesis exceeds a predetermined threshold.

13. The method of claim 9, comprising delivering an out-of-range message from the character recognition module to the search module in response to a request from the search module defining a selected character hypothesis that extends over a number of vectors in excess of a predetermined limit for the selected character hypothesis.

14. The method of claim 13 further comprising pruning the selected character hypothesis in response to receipt of the out-of-range message.

15. The method of claim 14, wherein the selected character hypothesis identifies a selected character and the predetermined limit is dependent on the selected character.

16. A handwriting recognizer comprising:

a digitizer having a surface for receipt of handwritten input, and having an output;

a preprocessor coupled to the output of the digitizer, the preprocessor segmenting the handwritten input into strokes to provide stroke vectors, the processor further delivering an out-of-range message based on the number of provided stroke vectors;

a character recognizer coupled to the preprocessor and operative on the stroke vectors, the character recognizer having an input receiving scoring requests and an output providing non-cumulative scores; and

a forward search module coupled to the input and the output of the recognizer, the forward search module adapted to deliver multiple non-cumulative scores to the recognizer to enable the recognizer to form multiple parallel hypotheses regarding the identity of the input ink.

17. A recognizer according to claim 16, further comprising a memory coupled to the search module, wherein the memory has a dictionary of words stored therein.

18. A method of recognition of handwritten input comprising:

(a) segmenting the handwritten input into strokes in a character recognition module, to provide stroke vectors;

(b) creating a first hypothetical character string in a search module;

(c) creating a first character hypothesis in the search module, the first character hypothesis being a first data set comprising a first character, a selectable start vector and a selectable end vector, wherein the first character is a member of the first hypothetical character string;

(d) requesting, from the search module to the character recognition module, a score for the first character hypothesis, where the score represents a likelihood of the first character being present in the handwritten input at a position starting at the start vector and ending at the end vector, the request from the search module optionally enabling multiple parallel non-cumulative scores to be delivered from the recognition module;

(e) delivering from the character recognition module to the search module a score for the selected first character hypothesis;

(f) repeating steps (c), (d) and (e) for further character hypotheses, including hypotheses corresponding to data sets comprising the first character, the selectable start vector and alternative end vectors;

(g) selectively maintaining the first hypothetical character string dependent on the score; and

(h) delivering an out-of-range message based on the number of provided stroke vectors and preventing the return of the score if an out-of-range message is delivered.