Supervised training augmented polynomial method and apparatus for character recognition

• US 5,555,317 A
• Filed: 08/18/1992
• Issued: 09/10/1996
• Est. Priority Date: 08/18/1992
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Anderson, Peter G.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US07/931,741
• Time in Patent Office: 1,484 Days
• Field of Search: 382/16, 382/15, 382/36, 382/27, 382/39, 382/253, 382/299, 382/224, 382/159, 382/187, 382/199, 382/198, 358/140
• US Class Current: 382/159
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/19147 Obtaining sets of training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

A system that classifies or identifies hand printed or machine printed alphanumeric characters using an iterated least squares polynomial discriminant method is disclosed. Super-sampling of labeled training characters is performed prior to feature extraction. Feature extraction subsamples individual character images. The feature vectors and associated labelings are used to create a weight matrix. During iteration, the weight matrix, to be subsequently used for identification, is modified by determining which characters are incorrectly classified, or classified with too small a confidence, and replicating those characters during training to strengthen the correct classification. The correct classification is also strengthened by using negative feedback to inhibit incorrect classification by using negative values in the target vectors. The speed of the learning process is enhanced by maintaining intermediate matrices and step wise increasing the amount of each feature vector and the size of the sample set used during training. The memory efficiency utilization is enhanced by maintaining and modifying intermediate matrices and compressing the sparse binary features vectors.

Claims

1. A method of character classification, comprising the steps of:

(a) performing a polynomial discriminant weight matrix creation operation using a training character set of training character images;

(b) testing the weight matrix to determine classification accuracy;

(c) modifying the training character set responsive to the testing by increasing representation of a character that is incorrectly classified or distinguished in classification strength from an incorrect classification by less than a difference;

(d) repeating steps (a)-(c) for a number of iterations; and

(e) classifying an unclassified character in an image using the weight matrix.

2. A method as recited in claim 1, wherein step (c) further comprises:

(cii) providing a negative classification to the character with the highest incorrect classification of an incorrectly classified character or the character whose incorrect classification is above a predetermined value.

3. A method as recited in claim 1, further comprising creating a substitute training character set that has a larger number of characters than the training character set where the substitute training character set is created from the training character set by offset replication and step (a) uses the substitute training set.

4. A method as recited in claim 3, wherein the substitute training set has a size and step (a) comprises using a larger portion of the substitute training set on each repeat.

5. A method as recited in claim 1, further comprising subsampling pixels of the characters and extracting features of the characters creating feature vectors and step (a) uses the feature vectors.

6. A method as recited in claim 5, wherein each of the feature vectors has a size and step (a) comprises using a larger portion of each of the feature vectors on each repeat.

7. A method as recited in claim 1, wherein step (a) includes creating and maintaining intermediate matrices used to create the weight matrix and step (c) includes modifying the intermediate matrices.

8. A method of character classification, comprising the steps of:

(a) creating, using a computer, a polynomial discriminant character weight matrix using a training exemplar feature vector set of features of captured character images;

(b) testing the weight matrix to determine classification accuracy;

(c) increasing representation of an exemplar in the feature vector set which is not classified correctly by repeating the exemplar;

(d) adding a negative weight for an exemplar that is classified incorrectly;

(e) repeating steps (a)-(d) for a predetermined number of iterations; and

(f) classifying an unclassified character in using the weight matrix, thereby identifying the unidentified character.

9. A method, comprising the steps of:

(a) capturing classified printed character images using a printed character image capture device; and

(b) using a computer for;

(b1) normalizing the images;

(b2) offset replicating the normalized images;

(b3) subsampling the super-sampled normalized images to produce a set of subsampled images;

(b4) extracting character features from the set of subsampled images to create a set of feature vectors for each of the images;

(b5) selecting a subset of the feature vector set;

(b6) selecting a prefix of each feature vector;

(b7) creating intermediate matrices for using the subset of the feature vector set and the prefix of each feature vector;

(b8) creating a weight matrix from the intermediate matrices;

(b9) testing the weight matrix using a test feature vector set with test characters;

(b10) increasing the representation of test characters by replicating the test characters in the intermediate matrices that are not correctly classified by said testing;

(b11) representing incorrect classifications for test characters negatively in the intermediate matrices;

(b12) adjusting the subset of the feature vector set selected;

(b13) adjusting the prefix of each feature vector selected; and

(b14) repeating steps (b7)-(b13) a predetermined number of times.

10. A method as recited in claim 9, further comprising:

(c) capturing a printed character image of an unclassified character; and

(d) classifying the unclassified character using the weight matrix.

11. A system for classifying printed characters, comprising:

image capture means for capturing images of identified printed characters as a training set and for capturing unidentified printed characters;

a computer coupled to said image capture means and comprising;

weight matrix creation means for iteratively creating a weight matrix from the identified printed characters using polynomial discrimination during which the training set is modified by increasing representation of characters that are incorrectly classified; and

identification means for identifying the unidentified printed characters using the weight matrix.

12. A system for classifying data, comprising:

first capture means for capturing identified data as a training set;

a computer coupled to said first capture means and comprising weight matrix creation means for iteratively creating a weight matrix from the identified data using polynomial discrimination during which the training set is modified by increasing representation of identified data in the training set that is not correctly classified;

second capture means for capturing unidentified data; and

identification means for identifying the unidentified data using the weight matrix.

13. A method of data classification, comprising the steps of:

(a) performing, using a computer, a polynomial discriminant weight matrix creation operation using a training data set of training data;

(b) testing the weight matrix using the computer to determine classification accuracy;

(c) modifying the training data set using the computer responsive to the testing by increasing representation of data that is not classified correctly;

(d) repeating steps (a)-(c) for a number of iterations; and

(e) classifying unclassified data using the computer with the weight matrix.