Abstract:
A system for automatic object classification including means for applying a plurality of binary rules to an object, where any of the binary rules is operative to classify the object to one of a pair of classes, and means for determining to which of the classes the object is classified the greatest number of times subsequent to the application of the binary rules.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/283,635, filed Apr. 16, 2001, entitled “Device and Method for General Classification of Objects Based on Selection Procedure Applied to Object Pairs,” and incorporated herein by reference in its entirety. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The present invention relates to automatic classification of objects in general, and more particularly to automatic defect classification.  
         BACKGROUND OF THE INVENTION  
         [0003]    Automatic object classification is an increasingly important aspect of many industrial systems. For instance, automatic defect classification (ADC) is important aspect of semiconductor production. In conventional classification systems, classification rules are derived from a learning set of reference objects (e.g. defect images in ADC) and then applied in a production environment.  
           [0004]    One of the most difficult and important stages in object classification is choosing an optimal set of formal features to form a feature space. The feature space should not only describe the objects of classification, but it should also relate to those object properties which best discriminate objects between different classes. Moreover, feature space selection may impact the balance between precision and generality, known to be a difficult aspect of any pattern recognition problem, as it has been shown that greater generalization may be achieved with simple rules containing a relatively small number of features, but at the expense of precision when defining rules for the learning set.  
         SUMMARY OF THE INVENTION  
         [0005]    The present invention provides a system and method of automatic object classification that overcomes disadvantages of the prior art. A novel technique for the automatic generation and application of object classification rules is described. A binary rule is defined for every pair of different defined classes C i ,C j , where ij=1,2, . . . ,n; i&lt;j; and where n is the number of defined classes, resulting in n*(n-1)/2 binary rules for n classes. A binary rule for classes C i  and C j  is generated in such a way that it discriminates between these classes only. Thus, when relating a binary rule to pair of classes C i , C j , an object O is classified either as belonging to class C i  or as belonging to class C j . A tournament strategy of classification is then employed where for every pair of classes a winning class is found to which the object most likely belongs. The class which wins the most times then becomes the ultimate winner and thus the class among all other classes to which the object most likely belongs.  
           [0006]    For specific types of binary rules, such as where a fuzzy-logic calculation mechanism is used, a binary rule for class pair (C i , C j ) may be represented in the form of two fuzzy classification rules R ij  and R ji . Thus, for every object O, values R ij (O) and R ji (O) may characterize a fuzzy degree of belonging of object O to classes C i  and C j  respectively. Thus, when relating a pair of rules R ij , R ji  to pair of classes C i , C j , object O will be classified either as belonging to class C i  (if R ij (O)&gt;R ji (O)), or as belonging to class C j  (if R ji (O)&gt;R ij (O)).  
           [0007]    In one aspect of the present invention a system for automatic object classification is provided including means for applying a plurality of binary rules to an object, where any of the binary rules is operative to classify the object to one of a pair of classes, and means for determining to which of the classes the object is classified the greatest number of times subsequent to the application of the binary rules.  
           [0008]    In another aspect of the present invention the system further includes means for automatically generating the binary rules.  
           [0009]    In another aspect of the present invention the system further includes a learning set having a plurality of the objects, where each of the objects in the learning set is pre-classified as belonging to one of the classes, and where the means for automatically generating is operative to generate the binary rules using the learning set.  
           [0010]    In another aspect of the present invention the means for automatically generating is operative to generate using supervised learning.  
           [0011]    In another aspect of the present invention each of the binary rules includes a first part and a second part, the means for determining is operative to calculate using the first part a degree of belonging of the object to one of the classes in the class pair, the means for determining is operative to calculate using the second part a degree of belonging of the object to the other of the classes in the class pair, and the means for applying is operative to select one of the classes in the class pairs to which the degree of belonging of the object is greater.  
           [0012]    In another aspect of the present invention each of the parts includes at least one fuzzy logic formula including at least one named predicate related to a numerical characteristic of one of the objects, and where the means for determining is operative to calculate the degrees of belonging using the fuzzy-logic formulae.  
           [0013]    In another aspect of the present invention the objects are images.  
           [0014]    In another aspect of the present invention the objects are semiconductor defect images and where the classes describe defect classes for application in semiconductor production.  
           [0015]    In another aspect of the present invention a method is provided for automatic object classification including applying a plurality of binary rules to an object, where any of the binary rules is operative to classify the object to one of a pair of a plurality of classes, and determining to which of the classes the object is classified the greatest number of times subsequent to the application of the binary rules.  
           [0016]    In another aspect of the present invention the method further includes pre-classifying a plurality of objects in a learning set as belonging to one of the classes, and automatically generating the binary rules using the learning set, where any of the binary rules of any of the pairs of classes is generated using any of the objects in the learning set that are pre-classified as belonging to the pair of classes.  
           [0017]    In another aspect of the present invention the automatically generating step includes generating using supervised learning.  
           [0018]    In another aspect of the present invention the determining step includes calculating a degree of belonging of the object to one of the classes in the class pair using a first part of each of the binary rules, the determining step includes calculating a degree of belonging of the object to the other of the classes in the class pair using a second part of each of the binary rules, and the applying step includes selecting one of the classes in the class pairs to which the degree of belonging of the object is greater.  
           [0019]    In another aspect of the present invention the determining step includes calculating the degrees of belonging using a fuzzy-logic formula included in each of the parts and including at least one named predicate related to a numerical characteristic of one of the objects.  
           [0020]    The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference in their entirety. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0021]    The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which:  
         [0022]    [0022]FIG. 1A is a simplified block flow illustration of a supervised method of generating classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention;  
         [0023]    [0023]FIG. 1B is a simplified block diagram of interaction between a user and system components for generating classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention;  
         [0024]    [0024]FIG. 1C is a simplified block diagram of interaction between a user and system components for applying generated classification rules, operative in accordance with a preferred embodiment of the present invention;  
         [0025]    [0025]FIG. 2 is a simplified flowchart illustration of a method of generating tournament classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention; and  
         [0026]    [0026]FIG. 3 is a simplified flowchart illustration of a method of applying tournament classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention. 
     
    
     GLOSSARY OF TERMS  
       [0027]    The following terms are used throughout the specification and claims and are defined as follows:  
         [0028]    AOCS (Automatic Object Classification System): a system for describing classes of objects (e.g., microchip layer defect images) and automatically classifying similar objects.  
         [0029]    Object: A named unique entity (e.g., a microchip defect image) that can be analyzed according to specific features.  
         [0030]    Class: A set of objects that are related to a unique class name, provided by the user.  
         [0031]    Classification: The process and result of manually and/or automatically providing class names to groups of objects.  
         [0032]    Learning set: A set of objects, typically manually classified by a user and applied for building rules for automatic classification of objects.  
         [0033]    Feature: A named real function of an object.  
         [0034]    Predicate: A named real function of an object, which has values belonging to interval [0,1].  
         [0035]    Crisp predicate: An expression in the form f&gt;n or f&lt;n, where f is name of a feature (for which normalization is not defined), and n is a real number. Like an ordinary predicate, a crisp predicate defines numerical function of objects as follows:  
         [0036]    If crisp predicate p is of the form (f&gt;n) and f(O)&gt;n then p(O)=1;  
         [0037]    If crisp predicate p is of the form (f&gt;n) and f(O)&lt;n then p(O)=0;  
         [0038]    If crisp predicate p is of the form (f&lt;n) and f(O)&gt;n then p(O)=0;  
         [0039]    If crisp predicate p is of the form (f&lt;n) and f(O)&lt;n then p(O)=1;  
         [0040]    where 0 is an object.  
         [0041]    Examples of Crisp predicates include:  
         [0042]    Dimension &gt;50  
         [0043]    where Dimension is a feature name.  
         [0044]    Transformation of features into predicates: The process of forming a predicate from a feature. This can be done in either of the following ways:  
         [0045]    1) By applying a special function;  
         [0046]    2) By applying a statistical normalization.  
         [0047]    Modifier: An expression such as Somewhat, Not, Not Somewhat, More-or-Less, Not More-or-Less.  
         [0048]    Predicate with modifier: An expression in the form &lt;Modifier&gt; &lt;Predicate&gt;, defined for non-crisp predicates only. For every non-crisp predicate P, modifiers change the function of the predicate. For example:  
         [0049]    Not P(O)=1−P(O);  
         [0050]    Somewhat P(O)=sqrt(P(O));  
         [0051]     where O is an object. Other functions may be applied as operators for implementation of modifiers.  
         [0052]    Or-predicate: An expression in the form P 1 |P 2 | . . . |P n , where P 1 ,P 2 , . . . , P n  are predicates which may contain modifiers or be crisp predicates, and n is a natural number. An or-predicate defines a real function of objects. For example: Let predicate P be an Or-predicate (P 1 |P 2 | . . . P n ). For every object O, P(O)=max((P 1 (O),P 2 (O), . . . , P n (O)).  
         [0053]    And-predicate: An expression in the form P 1 &amp;P 2 &amp; . . . &amp;P n , where P 1 ,P 2 , . . . , P n  are predicates, which may contain modifiers or be crisp predicates, or Or-predicates, and n is a natural number. An and-predicate defines a real function of objects. For example: Let predicate P be an And-predicate (P 1 &amp;P 2 &amp; . . . &amp;P n ). For every object O, P(O)=min((P 1 (O),P 2 (O), . . . , P n (O)).  
         [0054]    Rule: A predicate, which may contain modifiers or be crisp predicate, or-predicate, or and-predicate. For a rule R and an object O, a rule value is designated as R(O). Rule value R(O) characterizes the degree of belonging of an object 0 to an object class as defined by rule R.  
         [0055]    Examples of rules:  
         [0056]    1) A simple rule containing one predicate:  
         [0057]    R 1 =Circular  
         [0058]    2) A rule formed from an and-predicates:  
         [0059]    R 2 =Black &amp; Not Circular &amp; (Dimension&gt;50). Here Black and Circular are predicate names, Dimension is a feature name, and Dimension&gt;50 is a crisp predicate.  
         [0060]    3) A rule which contains an or-predicate:  
         [0061]    R 3  =Circular &amp; (Black|Dimension&gt;50). Here Circular and Black are predicate names, and (Black|Dimension&gt;50) is an or-predicate.  
         [0062]    Degree of belonging: A numerical value (e.g., between 0 and 1), which characterizes a fuzzy value of classification of an object O in a class C.  
         [0063]    Types of classification results: A characterization of a degree of belonging, for example:  
         [0064]    Belonging to class C i , Unknown, Cannot decide.  
         [0065]    Belonging to class C i : A classification result for object O if:  
         [0066]    a) Its maximal degree of belonging for object O relates it to C i .  
         [0067]    b) Its degree of belonging is greater than a certain threshold.  
         [0068]    c) The difference between its degree of belonging and the maximal degree for other classes is greater than a certain threshold.  
         [0069]    Unknown: A classification result for object O if its maximal degree of belonging to defined classes is less than certain threshold.  
         [0070]    Cannot decide: A classification result for object O if:  
         [0071]    a) Its maximal degree of belonging is greater than certain threshold;  
         [0072]    b) The difference between its degree of belonging and the maximal degree for other classes is less than certain threshold.  
         [0073]    Error function h(R,C1,C2): The numerical characteristics of errors which arise when applying rule R for discrimination between class C1 and class C2 in a given learning set. An error function may be calculated as follows:  
         h(R,C1,C2)=n11/(n11+n12)+n22/(n22+n21),  
         [0074]    where  
         [0075]    n11=number of objects O, classified as class C1 by the user and as class C1 by AOCS;  
         [0076]    n12=number of objects O, classified as class C1 by the user and as class C2 by AOCS;  
         [0077]    n21=number of objects O, classified as class C2 by the user and as class C1 by AOCS;  
         [0078]    n22=number of objects O, classified as class C2 by the user and as class C2 by AOCS.  
         [0079]    Note: Class C2 also may represent all objects not belonging to class C1.  
         [0080]    Winning strategy of classification. Given two or more rules R 1 , R 2 , . . . , describing classes C 1 , C 2 , . . . correspondingly, an object O is classified as belonging to the class for which its degree of belonging (i.e. related rule value) is maximal. The corresponding class and rule are called the winning class and rule.  
         [0081]    Binary rule: A classification rule related to a pair of different classes (C i ,C j ) only. Given an object O, a binary rule classifies it either as belonging to C i  or C j . For example, a binary rule for classes (C i ,C j ) consists of a rule pair (R ij ,R ji ), where rule R ij  discriminates objects of class C i  from class C j  and rule R ji  discriminates objects of class C j  from class C i . Rules R ij  and R ji  may include predicates as described above, and a comparison of values R ij (O) and R ji (O) determines the class to which object O belongs according to the winning strategy of classification.  
         [0082]    Tournament strategy of classification. Given two or more classes C1, C2, . . . C n , an object O is classified in tournament fashion where, for every pair of classes, a winning class is determined as being the class which wins the most times using binary rules.  
       DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0083]    Reference is now made to FIG. 1A, which is a simplified block flow illustration of a method of generating classification rules in an automatic object classification system, operative in accordance with a preferred embodiment of the present invention. In the method of FIG. 1A supervised learning is used in which, after every learning step (i.e. after changing a classification rule) the rules are applied to objects of a learning set, and their classification results are compared with classifications of the objects that are a priori known to be correct. After this comparison, specific rule changes may be effected, in case of successful learning, or prevented in consideration of alternative rule changes. Evaluation of success or failure may be performed with respect to the number of classification errors for all objects in the learning set.  
         [0084]    Reference is now made to FIG. 1B, which is a simplified block diagram of a method of interaction between a user and system components for generating classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention. In FIG. 1B a user provides, typically manually, a priori correct class names for reference objects and thus creates a learning set. The learning set is then used for creation of classification rules according to method of FIG. 1A and/or FIG. 2, described in greater detail hereinbelow.  
         [0085]    Reference is now made to FIG. 1C, which is a simplified block diagram of a method of interaction between a user and system components for application of generated classification rules operative in accordance with a preferred embodiment of the present invention. In FIG. 1C a user obtains the classification of an object. Classification is carried out using classification rules obtained according to the method of FIG. 1B. The automatic object classifier operates according to method of FIG. 3, described in greater detail hereinbelow.  
         [0086]    Reference is now made to FIG. 2, which is a simplified flowchart illustration of a method of supervised generation of tournament classification rules in an automatic object classification system, operative in accordance with a preferred embodiment of the present invention. In a tournament classification system a binary rule is generated for every pair of different defined classes, where a binary rule for classes C i , C j  may include a pair of rules, R ij  and R ji . When relating a pair of rules R ij , R ji  to classes C i , C j , an object O will be classified as belonging to class C j  if R ij (O)&gt;R ji (O), and as belonging to class C i  if R ij (O)&lt;R ji (O).  
         [0087]    In the method of FIG. 2 n defect classes are defined with each class C, (where 1≦i≦n) having n−1 rules R i1 , R i2 , . . . , R i,i−1 , R i,i+1 , . . . , R in . The role of every such rule R ij  is to discriminate objects of class C i  from objects of class C j . For all pairs (C i , C j ) of defined classes the corresponding rule pairs (R ij , R ji ) are created as follows:  
         [0088]    1) Transform features into predicates.  
         [0089]    2) Build initial rule pair table.  
         [0090]    3) Improve rule pairs.  
         [0091]    Step 1, Transformation of features into predicates, is described hereinabove. Steps 2 and 3 are now described in greater detail.  
         [0092]    2) Build initial rule pair table. The rules may be organized in a table as is shown in Table A below.  
                                                                 TABLE A                           C 1     C 2     C 3     . . .    C n                                      C 1     —   R 21     R 31     . . .    R n1             C 2     R 12     —   R 32     . . .    R n2             C 3     R 13     R 23     —   . . .    R n3             . . .    . . .    . . .    . . .    . . .    . . .            C n     R 1n     R 2n     R 3n     . . .    —                      
 
         [0093]    In Table A every box related to class C i  is populated by copies of a rule R(C i ) which may be obtained by conventional fuzzy-logic methods based on the winning strategy of classification. Thus, R i1 =R i2 = . . . =R in =R(C i ); i=1,2, . . . , n. Rules R ii  in the diagonal boxes are made empty. Alternatively, all boxes of Table A may be initially made empty. In this case, all initial rules R ij  are considered to be empty. Non-empty initial rules may help in avoiding local minima of the error function applied for improvement of rule pairs.  
         [0094]    3) Improve rule pairs. For every pair of defined classes (C i , C j ), where i&gt;j, the corresponding pair of rules R ij  and R ji  may be improved. Arrays P ij  and P ji  of prospective predicates for inclusion into rules R ij  and R ji  are formed as follows. For every defined predicate p (with or without a modifier), average predicate values A pi  and A pj  may be calculated where A pi  is the average value of p for objects of class C i  and A pj  is the average value of p for objects of class C j . It may be seen that predicates with small average values are not desirable as prospective predicates for being and-predicates in rules since a) the minimum value of all and-predicates forms the rule value and b) for rule improvement the greatest possible rule values are sought. Therefore, a threshold constant T p  may be defined such that only predicates with an average value grater than T p  are included into the arrays P ij  and P ji . Typically a value of T p =0.6 is believed to be suitable for filtering out predicates with small average values. Thus, for every predicate p, if A pi &gt;T p  then p is included into array P ij , and if A pj &gt;T p , then p is included into array P ji . A predicate may also be considered as more prospective for inclusion where the predicate has a larger difference of average values for classes C i  and C j . A value T pij  which characterizes the power of every predicate p for discriminating classes C i  and C j  may be then calculated by conventional statistical methods.  
         [0095]    Both arrays P ij  and P ji  may then be sorted by descending of value T pij . A constant K may be defined such that only the first K elements of arrays P ij  and P ji  are kept, and all other elements removed. The value of K is preferably set in accordance with effectiveness and efficiency considerations. Typically, a value of K=20 is believed to provide satisfactory results and may be increased for achieving still better classification at the expense of rule generation time.  
         [0096]    Once arrays P ij  and P ji  have been constructed, the rules R ij  and R ji  may be improved by applying an oscillation algorithm for finding optimal rule sets. Each rule pair is evaluated using the error functions h(R ij ,C i ,C j ) and h(R ji ,C j ,C i ) calculated using the winning strategy of classification for two classes only. The oscillation algorithm is then used in parallel for rules R ij  and R ji , performing one forward and one backward step for R ij , and then performing the same for R ji , and so on. In a forward oscillation step predicates are added to the rule. Each next predicate P[I] which does not yet belong to rule R is taken from the associated array P. Rule R          P[I] is tested. If h(R          P[I])&gt;h(R), then predicate P[I ] is added to rule R. Otherwise, proceed to element P[I+1]. This procedure is repeated up to the end of array P. In a backward oscillation step predicates are deleted from rule R. The removal of the first predicate p from rule R is attempted. If the resulting rule has a better error function, then predicate p may be removed from rule R, otherwise predicate p remains in rule R. The removal of the second predicate p from rule R is attempted, and so on, until all predicates in rule R are considered. The oscillation algorithm terminates if no change results after performing the backward oscillation step, or once a predetermined number of the oscillation steps are performed.  
         [0097]    Once the oscillation algorithm has been applied for all rule pairs, a table may then be constructed from the optimal rule pairs R ij  and R ji  for every pair of different classes C i  and C j .  
         [0098]    Reference is now made to FIG. 3, which is a simplified flowchart illustration of a method of applying tournament classification rules in an object classification system, operative in accordance with a preferred embodiment of the present invention. In the method of FIG. 3 the results of the method of FIG. 2 are applied to an object using a Tournament strategy of classification. A maximum of n(n−1)/2 binary rules are applied, distinguishing between classes C i  and C j , where i, j&lt;n, and where n is number of classes defined in the learning set. Preferably, these rules are applied to objects whose expected classes are the same as those in the learning set.  
         [0099]    In the method of FIG. 3 the following steps are performed:  
         [0100]    1) Prepare a table of initial tournament values.  
         [0101]    2) Apply binary rules and correct tournament values.  
         [0102]    3) Sort the tournament values.  
         [0103]    4) Determine the winning class for the object.  
         [0104]    Each of these steps are now described in greater detail.  
         [0105]    1) Prepare a table of tournament values. A table is preferably prepared as is shown in Table B below.  
                                       TABLE B                                       C 1     C 2     C 3     . . .    C n             V 1     V 2     V 3     . . .    V n                        
 
         [0106]    In Table B n is the number of defined classes. Initially, all the values V 1 , V 2 , V 3 , . . . , V n  are typically set to 0.  
         [0107]    2) Apply binary rules and correct tournament values. For the object O being classified, binary rules related to class pairs (C i , C j ) for all i=1,2, . . . ,n, j=1,2, . . . ,n, i&lt;j are applied for all class pairs, preferably sequentially. After every such application V i  is increased by a fixed amount, typically 1, if class C i  wins, or V j  is increased by the same fixed amount if class C j  wins. Where the calculation results in a classification type of “cannot decide” or “unknown” V i  and V j  are left unchanged. If the binary rules are in the form of rule pairs (R ij ,R ji ) then rule values R ij (O) and R ji (O) for all i=1,2, . . . ,n, j=1,2, . . . ,n, i&lt;j are calculated for all rule pairs. After every step in this calculation V i  is increased by a fixed amount, typically 1, if R ij (O)&gt;R ji (O), or V i  is increased by the same fixed amount if R ji (O)&gt;R ij (O).  
         [0108]    3) Sort the tournament values. The resulting tournament values [V 1 , V 2 , . . . , V n ] are sorted in descending order. An analysis of the three maximal values V i , V j , V k  is then performed as follows.  
         [0109]    4) Determine the winning class for the classified object. For classes C i , C j , and C k :  
         [0110]    a) If V i &gt;V j =V k  (i.e. exactly one maximum value exists), then C i  is the winning class.  
         [0111]    b) If V i =V j &gt;V k  (i.e. exactly two maximum values V i  and V j  exist), then:  
         [0112]    C i  is the winning class if R ij (O)&gt;R ji (O);  
         [0113]    C j  is the winning class if R ji (O)&gt;R ij (O);  
         [0114]    c) If V i =V j =V k  (i.e. more than two maximum values exist), then no winning class is selected.  
         [0115]    The present invention is thus advantageous over the prior art in that a simple and effective feature space is provided for every binary rule, thus ensuring better utilization of a priori information and better generalization of the rules in a testing environment. The present invention also provides more precise classification of the objects. The evaluation of a predicate which separates two homogeneous classes only as in the present invention, is simpler than the evaluation of a predicate which separates a given class from all other classes as in traditional automatic object classification systems. Design and application of new predicates is also simplified for the user who needs only to consider two classes at a time with the present invention, rather than approach design and application as a multi-class problem.  
         [0116]    It is appreciated that one or more of the steps of any of the methods described herein may be omitted or carried out in a different order than that shown, without departing from the true spirit and scope of the invention.  
         [0117]    While the methods and apparatus disclosed herein may or may not have been described with reference to specific hardware or software, it is appreciated that the methods and apparatus described herein may be readily implemented in hardware or software using conventional techniques.  
         [0118]    While the present invention has been described with reference to one or more specific embodiments, the description is intended to be illustrative of the invention as a whole and is not to be construed as limiting the invention to the embodiments shown. It is appreciated that various modifications may occur to those skilled in the art that, while not specifically shown herein, are nevertheless within the true spirit and scope of the invention.