Diacritical processing for unconstrained, on-line handwriting recognition using a forward search

• US 6,453,070 B1
• Filed: 03/17/1998
• Issued: 09/17/2002
• Est. Priority Date: 03/17/1998
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Seybold, John, Seni, Giovanni
• Primary Examiner(s): Lee, Thomas D.
• Application Number:
  US09/042,829
• Time in Patent Office: 1,645 Days
• Field of Search: 382/186, 382/187, 382/230, 382/231, 382/119, 382/123, 382/229
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

Handwritten ink is scanned to identify potential diacriticals. A list of diacriticals (19) is generated by traversing the ink. Potential diacritical-containing characters are processed by scoring them with and without a diacritical to generate a first and second score. The first score is compared to the second score to in order to make a decision as to which variant of the potential diacritical-containing character produced a highest score. The highest score is used as a score for a theory and the decision is recorded. A data structure (50) is added to the theory. Each data unit in the data structure (50) corresponds to an entry in the list of diacriticals (19). As a new theory is created by propagation, contents of the data structure (50) are copied into the new theory. Thus, the data structure (50) is used to ensure that all handwritten ink is used and is used only once.

Claims

1. A method of diacritical processing for unconstrained, on-line handwriting recognition using a forward search comprising:

scanning an ink stream of handwritten input to identify potential diacriticals;

building a list of diacriticals;

traversing the ink stream;

processing a potential diacritical-containing character;

scoring the potential diacritical-containing character without adding a diacritical to generate a first score for a first variant of the potential diacritical-containing character;

scoring the potential diacritical-containing character with a diacritical selected from the list of diacriticals to generate a second score for a second variant of the potential diacritical-containing character;

comparing the first score with the second score in order to make a decision as to which variant of the potential diacritical-containing character produced a highest score;

using the highest score as a score for a theory, wherein the theory consists of a current character hypothesis and a record of a character string preceding the current character hypothesis; and

recording the decision.

2. The method according to claim 1 wherein the step of recording the decision comprises:

adding a data structure having a plurality of data units to the theory, wherein each data unit in the data structure corresponds to an entry in the list of diacriticals;

as the diacritical-containing character is scored highest using a selected diacritical from the list of diacriticals, setting a data unit in the data structure of the theory corresponding to the selected diacritical; and

as a new theory is created by propagation, copying contents of the data structure into the new theory.

3. The method according to claim 2 wherein the data structure is a bit-field.

4. The method according to claim 2 further comprising determining if a next character hypothesis conflicts with a previously used diacritical.

5. The method according to claim 2 further comprising checking that all subsequent ink has been used as a diacritical when scoring an end-of-word theory.

6. A method of handwriting recognition using diacritical processing in a forward search comprising:

scanning an ink stream of handwritten input to identify a predetermined number of potential diacriticals in writing order;

terminating the step of scanning after identifying the predetermined number of potential diacriticals at time X;

building a list of diacriticals;

traversing the ink stream;

processing potential diacritical-containing characters; and

as a potential diacritical is passed in the step of traversing, discarding the potential diacritical from the list of diacriticals and replacing the potential diacritical with a next potential diacritical in the ink stream in writing order beginning at time X.

7. A method of handwriting recognition using diacritical processing in a forward search comprising:

scanning an ink stream of handwritten input to identify potential diacriticals;

building a list of diacriticals;

traversing the ink stream;

processing a potential diacritical-containing character;

scoring the diacritical-containing character with a selected diacritical from the list of diacriticals to generate a score;

using the score for a theory to progressively build interpretation strings for the ink stream of handwritten input, wherein the theory consists of a current character hypothesis and a record of a character string preceding the current character hypothesis;

adding a data structure having a plurality of data units to the theory, wherein each data unit in the data structure corresponds to an entry in the list of diacriticals; and

as a new theory is created by propagation, copying contents of the data structure into the new theory.

8. The method according to claim 7 further comprising setting a data unit in the data structure of the theory corresponding to the selected diacritical.

9. An apparatus used for handwriting recognition using diacritical processing in a forward search comprising:

a preprocessor module for scanning an ink stream of handwritten input to identify potential diacriticals and building a list of diacriticals;

a character recognizer module, coupled to the pre-processor module, for scoring a potential diacritical-containing character without adding a diacritical to generate a first score for a first variant of the potential diacritical-containing character and scoring the diacritical-containing character with a diacritical selected from the list of diacriticals to generate a second score for a second variant of the potential diacritical-containing character; and

a search module, coupled to the pre-processor module and to the character recognizer module, for comparing the first score with the second score in order to make a decision as to which variant of the potential diacritical-containing character produced a highest score, using the highest score as a score for a theory, wherein the theory consists of a current character hypothesis and a record of a character string preceding the current character hypothesis and recording the decision.

10. The apparatus according to claim 9 further comprising at least one of the following coupled to the search module:

a word and line segmentation logic module, a dictionary and a language model.

11. An apparatus used for handwriting recognition using diacritical processing in a forward search comprising:

a pre-processor module for scanning an ink stream of handwritten input, generating a list of diacriticals based on the scanned ink stream, traversing the ink stream, and generating a sequence of feature vectors based on the traversed ink stream;

a character recognizer module, coupled to the pre-processor module, for associating a recognition score with a received character scoring query; and

a search module, coupled to the pre-processor module and to the character recognizer module, for generating character scoring queries and propagating a plurality of theories.

12. A storage medium having stored thereon a set of instructions, which when loaded into a microprocessor causes the microprocessor to scan an ink stream of handwritten input to identify potential diacriticals, build a list of diacriticals, traverse the ink stream, process a potential diacritical-containing character, score the diacritical-containing character with a selected diacritical from the list of diacriticals to generate a score, use the score for a theory, wherein the theory consists of a current character hypothesis and a record of a character string preceding the current character hypothesis, add a data structure having a plurality of data units to the theory, wherein each data unit in the data structure corresponds to an entry in the list of diacriticals and, as a new theory is created by propagation, copy contents of the data structure into the new theory.

13. The storage medium according to claim 12 wherein a data unit in the data structure of the theory is set corresponding to the selected diacritical.

14. A storage medium having stored thereon a set of instructions, which when loaded into a microprocessor causes the microprocessor to scan an ink stream of handwritten input to identify potential diacriticals, build a list of diacriticals, traverse the ink stream, process a potential diacritical-containing character, score the potential diacritical-containing character without adding a diacritical to generate a first score for a first variant of the potential diacritical-containing character, score the diacritical-containing character with a diacritical selected from the list of diacriticals to generate a second score for a second variant of the potential diacritical-containing character, compare the first score with the second score in order to make a decision as to which variant of the potential diacritical-containing character produced a highest score, use the highest score as a score for a theory, wherein the theory consists of a current character hypothesis and a record of a character string preceding the current character hypothesis, and record the decision.