Pattern recognition system with statistical classification

• US 5,537,488 A
• Filed: 09/16/1993
• Issued: 07/16/1996
• Est. Priority Date: 09/16/1993
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Menon, Murali M., Boudreau, Eric R.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/122,705
• Time in Patent Office: 1,034 Days
• Field of Search: 382/225, 382/228, 382/159, 382/160, 382/170, 395/20, 395/23, 395/2, 395/2.4, 395/2.52, 395/2.54
• US Class Current: 382/170
• 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 as 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. The system is incrementally trainable such that new training data can be added without retraining the system.

Claims

1. A pattern recognition system comprising:

a training subsystem that receives during a training operation a plurality of training input patterns of a data type from a plurality of subject classes, that forms a set of categories of the training input patterns, that assigns each category a category definition according to training input patterns received within the category, that counts the training input patterns received for each class within each category and that generates for each category 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; and

a classifier that receives during a testing operation at least one test input pattern of the data type from the subject, that accesses the set of categories and computes a correlation between a category definition and each test input pattern, that forms a category association between each 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 and representing counts of training input patterns received by the training subsystem during the training operation, classification of the subject being determined by a peak class of the observation histogram, the peak class representing the highest training input pattern count of the observation histogram.

2. The pattern recognition system of claim 1 wherein the training subsystem assigns to each category a label that is determined by a 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 during the training operation, the training subsystem computes a correlation between each training input pattern and a category definition vector for each category.

5. The pattern recognition system of claim 4 wherein if the correlation is below a threshold, a new category is formed.

6. The pattern recognition system of claim 4 wherein if the correlation is above a threshold, an existing category definition vector is modified by an incoming training input pattern according to a learning rule.

7. The pattern recognition system of claim 6 wherein the learning rule comprises creating a new category definition vector by multiplying a learning rate by a difference between the incoming training input pattern and the existing category definition vector and adding that product to the existing category definition vector.

8. The pattern recognition system of claim 4 wherein the correlation includes a vector dot product.

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

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

11. The pattern recognition system of claim 10 wherein if the category class contrast exceeds a threshold, the category is labeled as the peak class.

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

13. The pattern recognition system of claim 1 further comprising:

a second training subsystem that receives a second plurality of training input patterns of a second data type from the subject classes and forms a second set of categories;

a second classifier that receives at least one test input pattern of the second data type from the subject during the testing operation and forms a category association between the at least one test input pattern of the second data type and a category of the second set of categories and 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 within a class.

14. The pattern recognition system of claim 13 wherein at least one data type comprises visual data.

15. The pattern recognition system of claim 13 wherein at least one data type comprises sound data.

16. The pattern recognition system of claim 13 wherein the data types comprise visual and sound data.

17. The pattern recognition system of claim 13 wherein at least one data type comprises voice data.

18. The pattern recognition system of claim 1 wherein the observation histogram for a single test input pattern is a single-frame k-nearest neighbor histogram of a predetermined number k of categories which have the closest correlations to the single test input pattern.

19. A pattern recognition system comprising:

a source for generating input patterns of multiple data types;

a plurality of training subsystems, each training subsystem receiving a plurality of training input patterns of a single corresponding data type during a training operation, forming a set of categories of the training input patterns of the data type, generating a category definition for each category according to training input patterns received within the category, counting the number of training input patterns of each class within each category of the data type, and generating a training histogram for each category of the data type, each training histogram including counts of training input patterns of each class within the respective category;

a plurality of classifiers, at least one classifier receiving during a testing operation at least one test input pattern of its corresponding data type, accessing the categories and computing a correlation between a category definition and each test input pattern, forming a category association between each test input pattern and a category based on the correlation and forming for each data type an observation histogram to classify the subject, the observation histogram being formed from each training histogram of each category of each category association and representing counts of training input patterns received by the training subsystem during the training operation; and

a processor that combines each observation histogram for each data type into a cumulative histogram to form a cumulative classification of the subject within a class.

20. The pattern recognition system of claim 19 wherein at least one data type comprises visual data.

21. The pattern recognition system of claim 19 wherein at least one data type comprises sound data.

22. The pattern recognition system of claim 19 wherein the data types comprise visual and sound data.

23. The pattern recognition system of claim 19 wherein at least one data type comprises voice data.

24. A method of pattern recognition comprising:

receiving a plurality of training input patterns of a data type from a plurality of subject classes during a training operation;

forming a set of categories of the training input patterns;

generating a category definition for each category according to training input patterns received within the category;

counting the number of training input patterns received for each class within each category;

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 of each class received within the category;

receiving at least one test input pattern of the data type from a subject during a testing operation;

computing a correlation between a category definition and each test input pattern;

forming a category association between each 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 representing counts of training input patterns received by the training subsystem during the training operation, classification of the subject being determined by a peak class of the observation histogram, the peak class representing the highest training input pattern count of the observation histogram.

25. The method of claim 24 further comprising assigning to each category a label that is determined by a peak class of the category.

26. The method of claim 25 wherein assigning a label includes assigning a label of unknown to a category such that the subject can be classified as unknown.

27. The method of claim 24 wherein the training operation includes computing a correlation between each training input pattern and a category definition vector of each category.

28. The method of claim 27 wherein if the correlation between a training input pattern and a best match category definition vector is below a threshold, a new category is defined.

29. The method of claim 27 wherein if the correlation between a training input pattern and a best match category definition vector is above a threshold, the best match category definition vector is modified by the training input pattern according to a learning rule.

30. The method of claim 29 wherein the learning rule comprises creating a new category definition vector by multiplying a learning rate by a difference between the training input pattern and the existing category definition vector and adding that product to the existing category definition vector.

31. The method of claim 27 wherein the correlation includes a vector dot product.

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

33. The method of claim 24 wherein the training operation includes computing for each category a category class contrast indicative of the degree to which a peak class of the category dominates the category.

34. The method of claim 33 wherein if the category class contrast exceeds a threshold, the category is labeled as the peak class.

35. The method of claim 33 wherein if the category class contrast is below a threshold, the category is labeled as unknown.

36. The method of claim 24 wherein forming an observation histogram comprises generating for a single test input pattern a single-frame k-nearest neighbor class histogram of a predetermined number k of categories which have the closest correlation with the single test input pattern.

37. A pattern recognition system comprising:

a memory having stored therein a set of categories of training input patterns received from a plurality of subject classes during a training operation, each category having a category definition according to training input patterns received within the category, and each category being associated with 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; and

a classifier that receives during a testing operation at least one test input pattern from the subject, that accesses the set of categories and computes a correlation between a category definition and each test input pattern, that forms a category association between each 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 and representing counts of training input patterns received by the training subsystem during the training operation, classification of the subject being determined by a peak class of the observation histogram, the peak class having the highest training input pattern count of the observation histogram.

38. The pattern recognition system of claim 37 wherein the set of categories includes a category labelled as unknown such that the subject can be classified as unknown.

39. The pattern recognition system of claim 37 wherein the observation histogram for a single test input pattern is a single-frame k-nearest neighbor histogram of a predetermined number k of categories which have the closest correlations to the single test input pattern.

40. A method of pattern recognition comprising:

providing a set of categories of training input patterns received from a plurality of subject classes during a training operation, each category having a category definition according to training input patterns received within the category and each category having a training histogram of the training input patterns received within the category, the training histogram including counts of training input patterns of each class received 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 each test input pattern;

forming a category association between each 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 representing counts of training input patterns received by the training subsystem during the training operation, classification of the subject being determined by a peak class of the observation histogram, the peak class representing the highest training input pattern count of the observation histogram.