Method and system using meta-classes and polynomial discriminant functions for handwriting recognition

• US 5,854,855 A
• Filed: 12/01/1995
• Issued: 12/29/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: Loda, John J., Errico, James H., Labun, Nicholas M., Wang, Shay-Ping T., Murdock, Michael C.
• Primary Examiner(s): Shalwala, Bipin
• Application Number:
  US08/566,328
• Time in Patent Office: 1,124 Days
• Field of Search: 382/159, 382/177, 382/178, 382/179, 382/186, 382/187, 382/190, 382/199, 382/203, 382/241, 382/224, 382/225, 382/228, 382/198
• US Class Current: 382/187
• CPC Class Codes: G06F 18/24317 Piecewise classification, i.e. whereby each classification requires several discriminant rules
• 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/36 Matching; Classification

Abstract

A method and system of identifying text in a handwriting input is provided. The system includes a feature extractor (30) and a classifier (32). The feature extractor (30) extracts a plurality of features from handwriting input. The classifier (32) classifies the handwriting input according to a discriminant function that is based on a polynomial expansion. The text is identified according to the discriminant function output.

Claims

1. In a computer, a method of identifying text in a handwriting input, the method comprising the following steps:

extracting a plurality of features from the handwriting input;

generating a meta-class signal by distributing the plurality of features to a meta-class classifier for identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another;

distributing the plurality of features to a plurality of character classifiers for distinguishing between the meta-class characters;

generating a plurality of character classifier output signals based on a plurality of polynomial discriminant functions, each of the polynomial discriminant functions having a form ##EQU3## wherein x_j represents the plurality of features;

wherein i, j, m and n are integers;

wherein y represents one of the character classifier output signals;

wherein w_i represents a coefficient; and

wherein g_ji represents an exponent; and

identifying the handwritten text as a function of the meta-class signal and the plurality of character classifier output signals.

2. The method of claim 1, wherein at least one of the polynomial discriminant functions represents a second order polynomial.

3. The method of claim 2, wherein the at least one polynomial discriminant function has the form ##EQU4## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

4. The method of claim 1, wherein the step of identifying includes the following sub-step:

distributing the plurality of features to a plurality of discriminant functions, each of the plurality of discriminant functions designating a different character.

5. The method of claim 1, wherein the step of extracting includes the following sub-steps:

receiving a sequence of coordinate-pairs that represent the handwriting input;

low-pass filtering the sequence of coordinate-pairs;

removing duplicate coordinate-pairs from the sequence of coordinate-pairs;

partitioning the sequence of coordinate-pairs into a sequence of data frames; and

extracting the plurality of features from the sequence of data frames.

6. The method of claim 1, wherein the step of identifying includes the following sub-step:

comparing a value based on one of the character classifier output signals to a lexicon to generate a signal representing the text.

7. In a computer, a method of identifying text in a handwriting input, the method comprising the following steps:

extracting a plurality of features from a data frame that represent the handwriting input;

generating a meta-class signal by distributing the plurality of features to a meta-class classifier for identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another;

distributing the plurality of features to a plurality of meta-class character classifiers trained using localized features to distinguish between the meta-class characters;

generating a plurality of meta-class character classifier output signals based on a plurality of polynomial discriminant functions

classifying the plurality of features according to a discriminant function based on a polynomial expansion having a form ##EQU5## wherein x_j represents the plurality of features;

wherein I, j, m and n are integers;

wherein y represents a discriminant function output signal;

wherein w_i represents a coefficient; and

wherein g_ji represents an exponent;

accumulating the meta-class signal over a sequence of data frames to generate a meta-class confidence value;

accumulating the meta-class character classifier output signals over the sequence of data frames to generate a plurality of meta-class character confidence values; and

identifying the text as a function of the meta-class and meta-class character confidence values.

8. The method of claim 7, wherein at least one of the polynomial discriminant functions represents a second order polynomial.

9. The method of claim 8, wherein the at least one polynomial discriminant function has the form ##EQU6## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ji represents a second-order coefficient.

10. The method of claim 7, further comprising the following steps:

receiving a sequence of coordinate-pairs that represent the handwriting input;

low-pass filtering the sequence of coordinate-pairs;

removing duplicate coordinate-pairs from the sequence of coordinate-pairs; and

partitioning the sequence of coordinate-pairs into the sequence of data frames.

11. The method of claim 7, wherein the step of identifying includes the following sub-step:

comparing the meta-class and meta-class character confidence values to a lexicon to generate a signal representing the text.

12. In a computer, a method of identifying text in a handwriting input, the method comprising the following steps:

receiving a sequence of coordinate-pairs that represent the handwriting input;

low-pass filtering the sequence of coordinate-pairs;

removing duplicate coordinate-pairs from the sequence of coordinate-pairs;

partitioning the sequence of coordinate-pairs into a sequence of data frames;

extracting a plurality of features from the sequence of data frames;

distributing the plurality of features to a meta-class classifier for identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another,

generating a meta-class classifier output signal according to a meta-class polynomial discriminant function;

distributing the plurality of features to a plurality of meta-class character classifiers for distinguishing between the meta-class characters;

generating a plurality of meta-class character classifier output signals based on a plurality of meta-character polynomial discriminant functions, each of the meta-class character polynomial discriminant functions having a form ##EQU7## wherein x_j represents the plurality of features;

wherein i, j, m and n are integers;

wherein y_l represents one of the meta-class character classifier output signals;

wherein w_li represents a meta-class coefficient; and

wherein g_lji represents a meta-class exponent;

accumulating the meta-class classifier output signal over the sequence of data frames to generate a meta-class confidence value;

accumulating the meta-class character classifier output signals over the sequence of data frames to generate a plurality of meta-class character confidence values; and

identifying the text as a function of the meta-class and meta-class character confidence values.

13. The method of claim 12, wherein at least one of the meta-class character polynomial discriminant functions represents a second order polynomial.

14. The method of claim 13, wherein the at least one meta-class character polynomial discriminant function has the form ##EQU8## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

15. The method of claim 12, wherein the meta-class polynomial discriminant function is based on a polynomial expansion having the form ##EQU9## wherein y₂ represents a meat-class classifier output signal;

wherein w_2i represents a class coefficient; and

wherein g_2ji represents a class exponent.

16. The method of claim 15, wherein the meta-class polynomial discriminant function represents a second-order polynomial.

17. The method of claim 16, wherein the meta-class polynomial discriminant function has the form ##EQU10## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

18. The method of claim 12, wherein the step of identifying includes the following sub-step:

comparing at least one of the plurality of confidence values to a lexicon to generate a signal representing the text.

19. An article of manufacture, which comprises:

a computer-readable memory for directing a computer to recognize a handwriting input, the computer-readable memory having a structure defined by storing a computer program in the computer-readable memory;

wherein the computer program includes a method for identifying text in the handwriting input, the method comprising the steps of extracting a plurality of features from the handwriting input, generating a meta-class signal by distributing the plurality of features to a meta-class classifier for identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another, distributing the plurality of features to a plurality of character classifiers for distinguishing between the meta-class characters, generating a plurality of character classifier output signals based on a plurality of polynomial discriminant functions, each of the polynomial discriminant functions having a form ##EQU11## wherein x_j represents the plurality of features, wherein i, j, m and n are integers, wherein y represents one of the character classifier output signals, wherein w_i represents a coefficient, and wherein g_ji represents an exponent, and identifying the handwritten text as a function of the meta-class signal and the plurality of character classifier output signals.

20. The article of manufacture of claim 19, wherein at least one of the polynomial discriminant functions represents a second order polynomial.

21. The article of manufacture of claim 20, wherein the at least one polynomial discriminant function has a form ##EQU12## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

22. The article of manufacture of claim 19, wherein the step of identifying includes the following sub-step:

distributing the plurality of features to a plurality of discriminant functions, each of the plurality of discriminant functions designating a different character.

23. The article of manufacture of claim 19, wherein the step of extracting includes the following sub-steps:

receiving a sequence of coordinate-pairs that represent the handwriting input;

low-pass filtering the sequence of coordinate-pairs;

removing duplicate coordinate-pairs from the sequence of coordinate-pairs;

partitioning the sequence coordinate-pairs into a sequence of data frames; and

extracting the plurality of features from the sequence of data frames.

24. The article of manufacture of claim 19, wherein the step of identifying includes the following sub-step:

comparing a value based on the meta-class signal and the plurality of character classifier output signals to a lexicon to generate a signal representing the text.

25. A handwriting recognition system for identifying text in a handwriting input, which comprises:

a feature extractor for extracting a plurality of features from the handwriting input;

a meta-class classifier generating a meta-class signal in response to the plurality of features, the meta-class classifier identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another;

a plurality of character classifiers for distinguishing between the meta-class characters, the character classifiers generating a plurality of character classifier output signals based on a plurality of polynomial discriminant functions, each of the polynomial discriminant functions having a form ##EQU13## wherein x_j represents the plurality of features, i, j, m and n are integers, y represents one of the character classifier output signals, w_i represents a coefficient, and g_ji represents an exponent; and

a selector identifying the handwritten text as a function of the meta-class signal and the plurality of character classifier output signals.

26. The handwriting recognition system of claim 25, wherein at least one of the polynomial discriminant functions represents a second order polynomial.

27. The handwriting recognition system of claim 25, the at least one polynomial discriminant function has a form ##EQU14## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

28. The handwriting recognition system of claim 25, further comprising:

a lexical post processor for comparing a value based on the meta-class signal and the plurality of character classifier output signals to a lexicon to generate a signal representing the text.

29. A handwriting recognition system for identifying text in a handwriting input, which comprises:

a pre-processor, responsive to a sequence of coordinate-pairs representing the handwriting input, for low-pass filtering the sequence of coordinate-pairs to generate a filtered sequence;

a frame extractor for partitioning the filtered sequence into a sequence of data frames;

a feature extractor for extracting a plurality of features from the sequence of data frames;

a meta-class classifier generating a meta-class signal in response to the plurality of features, the meta-class classifier identifying a meta-class comprising a plurality of meta-class characters that are not easily discernible from one another;

a plurality of character classifiers for distinguishing between the meta-class characters, the character classifiers generating a plurality of character classifier output signals based on a plurality of polynomial discriminant functions, each of the polynomial discriminant functions having a form ##EQU15## wherein x_j represents the plurality of features, i, j, m and n are integers, y represents one of the character classifier output signals, w_i represents a coefficient, and g_ji represents an exponent;

a meta-class accumulator for accumulating the meta-class signal over the sequence of data frames to generate a meta-class confidence value;

a plurality of meta-character accumulators for accumulating the meta-class character signals over the sequence of data frames to generate a plurality of meta-class character confidence values; and

a selector identifying the text as a function of the meta-class and meta-class character confidence values.

30. The handwriting recognition system of claim 29, wherein at least one of polynomial discriminant functions represents a second order polynomial.

31. The handwriting recognition system of claim 30, wherein the at least one polynomial discriminant function has a form ##EQU16## wherein a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

32. The handwriting recognition system of claim 29, further comprising:

a lexical post processor for comparing the meta-class and meta-class character confidence values to a lexicon to generate a signal representing the text.

33. The handwriting recognition system of claim 29, wherein the pre-processor removes duplicate coordinate-pairs.