Method and system for lexical processing

• US 5,802,205 A
• Filed: 12/18/1995
• Issued: 09/01/1998
• Est. Priority Date: 09/09/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Emico, James H., Murdock, Michael C.
• Primary Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/573,711
• Time in Patent Office: 988 Days
• Field of Search: 382/181, 382/179, 382/182, 382/185, 382/186, 382/187, 382/188, 382/190, 382/310, 382/176, 382/159, 382/198, 382/218, 382/219, 382/228, 395/2.79
• US Class Current: 382/187
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A lexical processor and its method of use is provided. The lexical processor includes an input interface (300) and a word generator (302) for producing an output as a function of an input word and a confusion matrix. The confusion matrix is a handwriting error model that is based on the recognition capabilities of classifiers used in preprocessing inputs to the lexical processor. The lexical processor output comprises any of the following: the input word, a rejection indicator, a candidate replacement word, or a suggestion list of related words.

Claims

1. In a real-time handwriting recognition system, a method of lexical processing that produces a lexical output, the method comprising the following steps:

receiving an input word derived from non-scanned input data, the input word including a plurality of characters and a plurality of character confidence values;

generating a first result by comparing a rejection ratio, based on the plurality of character confidence values, to a reject character ratio threshold;

generating a second result by comparing the average of the plurality of character confidence values to an accept threshold; and

producing the lexical output according to the first result and the second result, wherein the lexical output is produced by a process step selected from the group consisting of;

accepting the input word without correction,

rejecting the input word as unidentifiable and including a rejection indicator in the lexical output, and

generating the lexical output as a function of the plurality of character confidence values and a confusion matrix.

2. The method of claim 1, wherein the step of generating the lexical output includes the following steps:

(a) selecting a replacement character by using the confusion matrix;

(b) producing a candidate word by replacing a character in the input word with the replacement character; and

(c) equating the lexical output to the candidate word.

3. The method of claim 2, wherein step (b) includes the following sub-step:

selecting the replacement character having a likelihood value that minimizes a distance between the candidate word and the input word, wherein the distance has a form;

space="preserve" listing-type="equation">D=C/L

wherein D represents the distance, C represents a character confidence value associated with the character, and L represents the likelihood value.

4. The method of claim 3, further comprising the following step:

deriving the likelihood value from the confusion matrix.

5. The method of claim 2, further including the following steps:

spell-checking the candidate word against a lexicon; and

selecting a suggestion list- to be included in the lexical output if the candidate word is not present in the lexicon.

9. The method of claim 1, further comprising the following steps:

receiving a handwriting input;

extracting a plurality of features from the handwriting input;

distributing the plurality of features to a plurality of polynomial discriminant functions that produce the plurality of character confidence values in response to the plurality of features; and

identifying the input word eased on the plurality of character confidence values.

10. The method of claim 9, wherein the step of identifying includes the following sub-step:

recognizing the plurality of characters by classifying the plurality of character confidence values.

6. In a handwriting recognition system, a method of lexical processing that produces a lexical output, the method comprising the following steps:

receiving an input word having a plurality of characters and a plurality of character confidence values;

generating a rejection ratio as a function of the plurality of character confidence values;

determining whether the rejection ratio is within a reject range;

if so, including a rejection indicator in the lexical output;

if not, generating a mean character confidence as a function of the plurality of character confidence values;

determining whether the mean character confidence value is within an accept range;

if so, equating the lexical output to the input word;

if not, generating a candidate word by;

using a confusion matrix to select a replacement character having a likelihood value that minimizes a distance between the candidate word and the input word; and

replacing at least one of the plurality of characters with the replacement character;

spell-checking the candidate word against a lexicon to determine whether the candidate word is present in the lexicon;

if so,

comparing the distance to a first threshold to produce the lexical output selected from the group consisting of the candidate word and a suggestion list;

if not,

generating a miss rejection ratio as a function of the plurality of character confidence values; and

selecting the lexical output by comparing the miss rejection ratio and the mean character confidence to a pair of miss thresholds, the lexical output being generated by a process selected from the group consisting of;

accepting the input word without correction,

rejecting the input word as unidentifiable and producing the rejection indicator, and generating a suggestion list.

7. The method of claim 6, wherein the distance has a form:

space="preserve" listing-type="equation">D=C/L

wherein D represents the distance, C represents a character confidence value associated with one of the plurality of characters, and L represents the likelihood value.

8. The method of claim 7, further comprising the following step:

deriving the likelihood value from the confusion matrix.

11. A real-time handwriting recognition system, comprising:

a lexical processor that includes an input interface receiving an input word derived from non-scanned input data, the input word comprising a plurality of character confidence values and representing a handwritten word having a plurality of characters, a calculator generating a word confidence value based on the character confidence values, a comparator for comparing the word confidence value to a pair of thresholds to produce a comparator output, and a selector producing a processor output in response to the comparator output, a spell-checker, operatively associated with the selector, for spell-checking a candidate word using a dictionary, and a computer memory for storing a confusion matrix;

wherein the processor output is selected from the input word and candidate word as a function of the comparator output and the confusion matrix.

12. The real-time handwriting recognition system of claim 11, wherein the selector selects a replacement character using the confusion matrix and generates the candidate word by replacing a character in the input word with the replacement character.

13. The real-time handwriting recognition system of claim 12, wherein the selector selects the replacement character based on a likelihood value that minimizes a distance between the candidate word and the input word, wherein the distance has a form:

space="preserve" listing-type="equation">D=C/L

wherein D represents the distance, C represents a character confidence value associated with the character, and L represents the likelihood value.

14. The real-time handwriting recognition system of claim 13, wherein the spell-checker selects the suggestion list if the candidate word is not present in the lexicon.

15. An article of manufacture, comprising:

a computer-readable memory storing a computer program that directs a computer to perform real-time handwriting recognition, wherein the computer program includes steps for receiving an input word derived from non-scanned input data, the input word including a plurality of character confidence values and a plurality of characters representing a word included in the handwriting text,

generating a first result by comparing a rejection ratio, based on the plurality of character confidence values, to a reject character ratio threshold,

generating a word confidence value based on the average of the character confidence values;

comparing the word confidence value to an accept threshold to generate a second result, and

producing the lexical output according to the first result and the second result, wherein the lexical output is produced by a computer program step selected from the group consisting of accepting the input word without correction, rejecting the input word as unidentifiable and including a rejection indicator in the lexical output, and generating the lexical output as a function of the plurality of character confidence values and a confusion matrix.

16. The article of manufacture of claim 15, wherein the computer program further includes the following steps:

(a) selecting a replacement character as a function of the confusion matrix;

(b) producing a candidate word by replacing a character in the input word with the replacement character; and

(c) including the candidate word in the lexical output.

17. The article of manufacture of claim 15, wherein step (b) includes the following sub-step:

selecting the replacement character based on a likelihood value that minimizes a distance between the candidate word and the input word, wherein the distance has a form;

space="preserve" listing-type="equation">D=C/L

wherein D represents the distance, C represents a character confidence value associated with the character, and L represents the likelihood value.

18. The article of manufacture of claim 17, wherein the computer program further includes the following step:

deriving the likelihood value from the confusion matrix.

19. The article of manufacture of claim 15, wherein the computer program further includes the following steps:

spell-checking the candidate word against a lexicon; and

selecting a suggestion list to be included in the lexical output if the candidate word is not present in the lexicon.