Pattern recognition system with statistical classification

• US 5,703,964 A
• Filed: 05/06/1996
• Issued: 12/30/1997
• Est. Priority Date: 09/16/1993
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Menon, Murali M., Boudreau, Eric R.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/617,854
• Time in Patent Office: 603 Days
• Field of Search: 382/170, 382/159, 382/160, 382/224, 382/225, 382/228, 395/2, 395/2.4, 395/2.52, 395/2.54, 395/20, 395/23
• US Class Current: 382/228
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

A pattern recognition system is described. During training, multiple training input patterns from multiple classes of subjects are grouped into clusters within categories by computing correlations between the training patterns and present category definitions. After training, each category is labeled in accordance with the peak class of patterns received within the cluster of the category. If the domination of the peak class over the other classes in the category exceeds a preset threshold, then the peak class defines the category. If the contrast does not exceed the threshold, then the category is defined unknown. The class statistics for each category are stored in the form of a training class histogram for the category. During testing, frames of test data are received from a subject and are correlated with the category definitions. Each frame is associated with the training class histogram for the closest correlated category. For multiple-frame processing, the histograms are combined into a single observation class histogram which identifies the subject with its peak class within a predefined degree of confidence. In a multiple-channel configuration, the training patterns and testing patterns are divided into multiple features.

Claims

1. A pattern recognition system comprising:

a memory that stores a set of categories of training input patterns from a plurality of subject classes, each training input pattern representing multiple features of a subject, each category having a category definition according to training input patterns within the category, each category definition comprising a plurality of input pattern feature definitions, each category being associated with a training histogram of the training input patterns within the category and the training histogram including counts of training input patterns for each subject class within the category; and

a classifier that receives during a testing operation at least one test input pattern from the subject, that accesses the set of categories, that computes a correlation between a category definition and the at least one test input pattern, that forms a category association between the at least one test input pattern and a category based on the correlation and that forms an observation histogram to classify the subject, the observation histogram being formed from each training histogram of each category of each category association, the observation histogram containing counts of training input patterns in the category, classification of the subject being determined by a peak class of the observation histogram.

2. The pattern recognition system of claim 1 wherein each category is assigned a label which is determined by the peak class of the category.

3. The pattern recognition system of claim 2 wherein the set of categories includes a category labeled as unknown such that the subject can be classified as unknown.

4. The pattern recognition system of claim 1 wherein the correlation between the category definition and the at least one test input pattern comprises plural feature correlations between features of the at least one test input pattern and feature definitions in the category definition.

5. The pattern recognition system of claim 4 wherein the correlation between the category definition and the at least one test input pattern is based on one of the feature correlations.

6. The pattern recognition system of claim 1 further comprising a training subsystem that receives the set of training input patterns during a training operation and forms the set of categories.

7. The pattern recognition system of claim 6 wherein, during the training operation, an existing category definition vector is modified by multiplying a learning rate by a difference between an incoming training input pattern and an existing category definition vector and adding that product to the existing category definition vector.

8. The pattern recognition system of claim 7 wherein, for each category, the training subsystem computes a category class contrast indicative of the degree to which the peak class of the category dominates the other classes of the category.

9. The pattern recognition system of claim 8 wherein, if the category class contrast exceeds a threshold, the peak class is assigned to the category as a label.

10. The pattern recognition system of claim 8 wherein, if the category class contrast is below a threshold, the category is labelled as unknown.

11. The pattern recognition system of claim 1 further comprising a feature extraction subsystem for separating each input pattern into a plurality of feature representations.

12. The pattern recognition system of claim 6 further comprising:

a second training subsystem that receives a second plurality of training input patterns from the subject classes during the training operation and that forms a second set of categories, each category of the second set having associated therewith a category definition and a training histogram;

a second classifier that receives a second test input pattern from the subject, that computes a correlation between a category definition of the second set of categories and the second test input pattern and that forms a second observation histogram; and

a processor for combining the first and second observation histograms into a cumulative histogram to produce a cumulative classification of the subject.

13. A method of pattern recognition comprising:

forming a set of categories of a plurality of training input patterns from a plurality of subject classes, each training input pattern representing multiple features of a subject;

generating a category definition for each category according to the training input patterns within the category, each category definition comprising a plurality of category feature definitions;

for each category, generating a training histogram of the training input patterns received within the category, the training histogram including counts of training input patterns received for each class within the category;

receiving at least one test input pattern from a subject during a testing operation;

computing a correlation between a category definition and the at least one test input pattern; and

forming a category association between the at least one test input pattern and a category based on the correlation; and

forming an observation histogram to classify the subject, the observation histogram being formed from each training histogram of each category of each category association and containing counts of training input patterns in the category, classification of the subject being determined by a peak class of the observation histogram.

14. The method of claim 13 further comprising labelling each category with a label determined by a peak class of the category.

15. A method as recited in claim 14 wherein the set of categories includes a category labelled as unknown such that the subject can be classified as unknown.

16. A method as recited in claim 13 wherein the correlation between the category definition and the at least one test input pattern comprises plural feature correlations between features of the at least one test input pattern and feature definitions in the category definition.

17. A method as recited in claim 16 wherein the correlation between the category definition and the at least one test input pattern is based on one of the feature correlations.

18. A method as recited in claim 13 wherein the step of generating a category definition comprises modifying an existing category definition vector by multiplying a learning rate by a difference between an incoming training input pattern and an existing category definition vector and adding that product to the existing category definition vector.

19. A method as recited in claim 13 further comprising the step of computing a category class contrast for each category indicative of the degree to which the peak class of the category dominates the other classes of the category.

20. A method as recited in claim 19 wherein, if the category class contrast exceeds the threshold, the peak class is assigned to the category as a label for the category.

21. A method as recited in claim 19 wherein, if the category class contrast is below a threshold, a category label of unknown is assigned to the category.

22. A method as recited in claim 13 further comprising separating each input pattern into a plurality of feature representations.

23. A method as claimed in claim 13 further comprising receiving a plurality of training input patterns from a plurality of subject classes during a training operation to form the set of categories.

24. A method as recited in claim 23 further comprising:

receiving a second plurality of training input patterns from the subject classes during the training operation;

forming a second set of categories, each category of the second set having associated therewith a category definition and a training histogram;

receiving a second test input pattern from the subject;

computing a correlation between a category definition and the second test input pattern;

forming a second observation histogram; and

combining the first and second observation histograms into a cumulative histogram to produce a cumulative classification of the subject.