Automatic knowledge database generation for classifying objects and systems therefor

• US 6,104,835 A
• Filed: 11/14/1997
• Issued: 08/15/2000
• Est. Priority Date: 11/14/1997
• Status: Expired due to Term

• Current Assignee: Uniphase Corporation (Lumentum Holdings Inc.)
• Original Assignee: KLA-Tencor Corporation (KLA Corporation)
• Inventors: Han, Ke
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E.
• Application Number:
  US08/970,951
• Time in Patent Office: 1,005 Days
• Field of Search: 382/224, 382/225, 382/159, 707/3-6
• US Class Current: 382/225
• CPC Class Codes: G06F 18/24143 Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]

Abstract

A method for automatically generating a knowledge database in an object classification system having a digital image data source, and a computer, includes the steps of inputting digital image data corresponding to a plurality of training images, and characterizing the digital image data according to pre-defined variables, or descriptors, to thereby provide a plurality of descriptor vectors corresponding to the training images. Predetermined classification codes are inputted for the plurality of training images, to thereby define object class clusters comprising descriptor vector points having the same classification codes in N-dimensional Euclidean space. The descriptor vectors, or points, are reduced using a similarity matrix indicating proximity in N-dimensional Euclidean space, to select those descriptors vectors, called extreme points, which lie on the boundary surface of their respective class cluster. The non-selected points interior to the class cluster are not included in the knowledge database. The extreme points are balanced by eliminating functionally redundant extreme points from each class cluster to provide a preliminary knowledge database. Fine tuning of the preliminary knowledge database is performed by either deleting extreme points that tend to reduce the accuracy of the database, or adding new rules which enhance the accuracy of the data base. Alternately, the fine tuning step may be skipped.

Claims

1. An object classification system having a computer, a digital image data source, a machine readable pattern recognition code encoded in the computer for interpreting digital image data and for characterizing images represented by the digital image data from said digital image source as a multi-dimensional descriptor vector for classification of objects using a knowledge database, and a machine readable code for automatically generating the knowledge database, the classifier comprising:

a) a memory which stores in computer readable form a plurality of descriptor vectors derived from a plurality of training images, each respective one of the training images including a predetermined classification code to permit separating the descriptor vectors into a plurality of class clusters;

b) a similarity matrix stored in a computer memory, said similarity matrix containing similarity values as between all of said descriptor vectors to permit identifying a first least similar descriptor vector and a most similar descriptor vector in each class cluster as compared to all other class clusters to thereby provide at least two inter-class extreme points for each class cluster, and to permit identifying a second least similar descriptor vector from a selected extreme point within a class cluster to thereby permit selecting said least similar descriptor vector as an intra-class extreme point;

c) an extreme point balancer which eliminates redundant extreme points from a class cluster.

2. An object classification system as in claim 1 wherein said extreme point balancer discards a first extreme point most similar to a second extreme point according to a predetermined similarity threshold value.

3. An object classification system as in claim 1 further comprising a knowledge database fine tuner which increases the accuracy of the knowledge database by deleting extreme points that are least accurate in their ability to classify an unknown sample, adding additional extreme points that represent most misclassified descriptor vectors thereby improving the ability of the knowledge database to correctly classify an object.

4. An object classification system as in claim 3 wherein said fine tuner compares each of said predetermined classification codes assigned to each of the training images to a corresponding system-generated classification code for each of the training images to thereby identify an extreme point least accurate in its ability to classify an unknown image, and to thereby permit de-selecting said least accurate extreme point.

5. An object classification system as in claim 3 wherein said comparison of classification codes and said similarity matrix permit identifying a most misclassified descriptor vector to thereby permit adding said most misclassified descriptor vector to the knowledge database as a new extreme point.

6. A method for automatically generating a knowledge database in a classification system having a computer, a computer memory, a digital image data source, and a machine readable code for automatically generating a knowledge database, the method comprising the steps of:

a) characterizing digital image data from the digital image data source representing a plurality of training images and having a predetermined classification code for each respective one of the plurality of images, to provide a plurality of descriptor vectors separated by said predetermined classification codes into a plurality of class clusters stored in the computer memory;

b) calculating a similarity matrix across all the descriptor vectors to permit identifying a most similar descriptor vector and a first least similar descriptor vector in each class cluster as compared to descriptor vectors in all other class clusters thereby providing at least two inter-class extreme points for each class cluster;

c) identifying a second least similar descriptor vector in a class cluster as compared to a selected extreme point in the same class cluster to permit selecting said second least similar descriptor vector as an intra-class extreme point;

d) balancing said extreme points to eliminate redundant extreme points and to thereby define a preliminary knowledge database; and

e) fine tuning the preliminary knowledge database to improve the accuracy of the preliminary knowledge database to provide a knowledge database, said knowledge database being stored in a computer memory.

7. A method for automatically generating a knowledge database in a classification system as in claim 6 wherein said balancing step includes the step of deleting a first extreme point most similar to a second extreme point according to a predetermined similarity threshold.

8. A method for automatically generating a knowledge database in a classification system as in claim 6 wherein said fining tuning step comprises the steps of:

a) providing a system-generated classification code for each of said descriptor vectors representing the plurality of training images;

b) comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors;

c) identifying a least accurate extreme point having associated therewith the highest percentage of misclassified descriptor vectors; and

d) deleting said least accurate extreme point.

9. A method for automatically generating a knowledge database in a classification system as in claim 6 wherein said fine tuning step further comprises the steps of:

a) providing a system-generated classification codes for each of said descriptor vectors representing the plurality of training images;

b) comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors;

c) identifying a most misclassified descriptor vector; and

d) adding said most misclassified descriptor vector to the knowledge database as a new extreme point.

10. An object classification system, comprising a computer useable medium having a computer readable program code means embodied therein for causing the object classification system to automatically generate a knowledge database for classifying unknown objects, the computer readable program code means in the object classification system comprising:

a) computer readable code means for causing a computer to retrieve a plurality of descriptor vectors and predetermined classification codes from a computer memory, each of said descriptor vectors representing a training image, each of said descriptor vectors further comprising a plurality of numerical values corresponding to physical parameters used to characterize an object image, said descriptor vectors separated by said pre-determined classification codes into a plurality of class clusters;

b) computer readable program code means for causing the computer to calculate a similarity matrix across all said descriptor vectors to permit selecting as extreme points a most similar descriptor vector and a first least similar descriptor vector in each class cluster as compared to descriptor vectors in all other class clusters;

c) computer readable program code means for causing the computer to select a second least similar descriptor vector in a class cluster as compared to a selected extreme point in the same class cluster to thereby provide an intra-class extreme point; and

d) computer readable program code means for causing the computer to delete at least one of a first extreme point most similar to a second extreme point according to a predetermined similarity threshold to thereby provide a preliminary knowledge database.

11. An object classification system as in claim 10 wherein said computer readable program code means in the object classification system further comprises:

a) computer readable code means for causing the computer to fine tune said preliminary knowledge database by calculating a system-generated classification code for each of said descriptor vectors representing the plurality of training images, comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors, identifying a least accurate extreme point having associated therewith the highest percentage of misclassified descriptor vectors, and deleting said least accurate extreme point.

12. An object classification system as in claim 10 wherein said computer readable program code means in the object classification system further comprises:

a) computer readable code means for causing the computer to fine tune said preliminary knowledge database by calculating a system-generated classification codes for each of said descriptor vectors representing the plurality of training images, comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors, identifying a most misclassified descriptor vector, and adding said most misclassified descriptor vector to the knowledge database as a new extreme point.

13. A program storage device readable by a machine tangibly embodying a program of instructions executable by the machine to perform method steps for automatically generating a knowledge database for object classification, said method steps comprising:

a) characterizing digital image data from a digital image data source representing a plurality of training images and having a predetermined classification code for each respective one of the plurality of images, to provide a plurality of descriptor vectors separated by said predetermined classification codes into a plurality of class clusters stored in a computer memory;

b) calculating a similarity matrix across all the descriptor vectors to permit identifying a most similar descriptor vector and a first least similar descriptor vector in each class cluster as compared to descriptor vectors in all other class clusters thereby providing at least two inter-class extreme points for each class cluster;

c) identifying a second least similar descriptor vector in a class cluster as compared to a selected extreme point in the same class cluster to permit selecting said second least similar descriptor vector as an intra-class extreme point;

d) balancing said extreme points to eliminate redundant extreme points and to thereby define a preliminary knowledge database; and

e) fine tuning the preliminary knowledge database to improve the accuracy of the preliminary knowledge database to provide a knowledge database, said knowledge database being stored in a computer memory.

14. A program storage device as in claim 13 wherein said balancing step further comprises the step of deleting at least one of a first extreme point most similar to a second extreme point according to a predetermined similarity threshold.

15. A program storage device as in claim 13 wherein said fine tuning step further comprises the steps of:

a) providing a system-generated classification code for each of said descriptor vectors representing the plurality of training images;

b) comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors;

c) identifying a least accurate extreme point having associated therewith the highest percentage of misclassified descriptor vectors; and

d) deleting said least accurate extreme point.

16. A program storage device as in claim 13 wherein said fine tuning step further comprises the steps of:

a) providing a system-generated classification code for each of said descriptor vectors representing the plurality of training images;

b) comparing each respective one of said system-generated classification codes to a corresponding one of said predetermined classification codes thereby identifying misclassified descriptor vectors;

c) identifying a most misclassified descriptor vector; and

d) adding said most misclassified descriptor vector to the knowledge database as a new extreme point.