Hierarchical parametric apparatus and method for recognizing drawn characters

• US 4,975,975 A
• Filed: 05/26/1988
• Issued: 12/04/1990
• Est. Priority Date: 05/26/1988
• Status: Expired due to Term

• Current Assignee: GTX Corporation (DE) (GTX Corp.)
• Original Assignee: GTX Corp.
• Inventors: Filipski, Alan
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/199,361
• Time in Patent Office: 922 Days
• Field of Search: 382/14, 382/15, 382/38, 382/36
• US Class Current: 382/227
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation

Abstract

A pattern recognition system includes a hierarchical network of parametric pattern recognition components or algorithms of different types. During a "training" phase, distinctions among character types are gathered from a set of correctly labelled training samples. The structure of the component hierarchy is established by recursive training of various subsets of the original training set and, for each component, generation of a "decision function" that either (1) indicates a final classification by the present component the characters of the training, or (2) points to a component lower in the hierarchy, thereby establishing connectivity between components of the hierarchy. The training process continues, generating successively lower components in the hierarchy, until perfect classification is obtained on the training set. The hierarchy of components then is utilized to recognize characters or patterns from a set of unknown patterns or characters, by making successive "passes", if necessary, on features extracted from each unknown character until the unknown character is classified.

Claims

1. A method of statistical pattern recognition comprising the steps of:

(a) training first and second classifier components with elements of a training set by performing the steps of

(1) selecting the first classifier component,

(2) extracting features from elements of the training set,

(3) operating on extracted features of the training set with the first classifier component to determine classes in which the elements of the training set are classified,

(4) producing a first set of training elements of the training set which the first classifier component classifies into a first class,

(5) determining whether all of the first set of training elements are labeled as being included in the first class,

(6) if the determination of step (5) is affirmative, setting a decision indicator in the first classifier component to indicate that the first classifier component can make a final decision that any of the training elements in the first set is in the first class,

(7) if the determination of step (5) is negative, setting the decision indicator to point to the second classifier component and recursively repeating steps (1) through (7) for the second classifier component, wherein the repetition of step (2) includes extracting the features from the first set of training elements;

(b) reading an unknown pattern;

(c) extracting features from the unknown pattern;

(d) operating on extracted features with the first classifier component and making a first decision that the unknown pattern is within the first class;

(e) determining if the first decision is a final decision that the unknown pattern is within the first class, and if it is, determining that the unknown pattern is in the first class, and if it is not, selecting a second classifier component;

(f) if the first decision is not a final decision, operating on extracted features of the unknown pattern with the second classifier component and making a second decision whether the unknown pattern is within the first class, and recursively repeating steps (e) and (f) for the second decision.

2. The method of claim 1 wherein the pattern includes a handwritten character.

3. The method of claim 1 including repeating steps (a) through (e) for additional unknown patterns.

4. The method of claim 1 including repeating steps (3) through (7) for a plurality of other sets of training elements and a plurality of other classes.

5. The method of claim 4 wherein one of the first and second classifier components is a decision tree component and the other is a Gaussian discriminant component.

6. The method of claim 5 wherein, if the first classifier is a decision tree classifier, the step of making the first decision includes finding a child cluster with a least Mahalanobis distance to a mean of extracted features of the unknown pattern.

7. The method of claim 5 wherein if the first classifier is a Gaussian discriminant classifier, the step of making the first decision includes computing a posterior probability that the unknown pattern is in each of a plurality of classes, respectively, and selecting as the first decision the decision that the unknown character is likely to be in the class corresponding to the highest posterior probability.

8. The method of claim 4 wherein if one of the first and second classifier components is a decision tree component, step (3) includes performing isodata clustering on classes of features extracted from the training set, computing cluster overlaps, and interactively building a decision tree for that decision tree component on the basis of the cluster overlaps.

9. A statistical pattern recognition system comprising in combination:

(a) means for reading an unknown pattern;

(b) means for extracting features from the unknown pattern;

(c) means for operating on extracted features with a first classifier component and making a first decision that the unknown pattern is within a first class;

(d) means for determining if the first decision is a final decision that the unknown pattern is within the first class; and

(e) means for determining that the unknown pattern is in the first class if the first decision is a final decision, and if it is not, selecting a second classifier component;

(f) means for operating on extracted features of the unknown pattern with the second classifier component and making a second decision whether the unknown pattern is within the first class if the first decision is not a final decision;

(g) means for training the first and second classifier components with elements of a training set, the training means including

(1) means for selecting the first classifier component,

(2) means for extracting features from elements of the training set,

(3) means for operating on extracted features of the training set with the first classifier component to determine classes in which the elements of the training set are classified,

(4) means for producing a first set of training elements of the training set which the first classifier component classifies into the first class,

(5) means for determining whether all of the first set of training elements are labeled as being included in the first class,

(6) means for setting a decision indicator in the first classifier component to indicate that the first classifier component can make a final decision that any of the training elements in the first set is in the first class if all of the first set of training elements are labelled as being included in the first class.

10. The system of claim 9 wherein the pattern includes a handwritten character.

11. The system of claim 9 wherein one of the first and second classifier components is a decision three classifier component.

12. The system of claim 11 wherein one of the first and second classifier components is a Gaussian discriminant classifier component.

13. The system of claim 12 wherein the unknown character is a handwritten alphanumeric character.