Feature classification using supervised statistical pattern recognition.

Technical Field

0001This invention relates in general to feature classification techniques for a static or moving image, and more particularly, to a feature classification system and method which employ supervised statistical pattern recognition using a novel vector classification model of spatially decomposed multi-dimensional feature space.

Background Art

0002As the use of optical scanning and electronic imperfection detection have continued to increase, automatic differentiation of defect classes has come within reach of available technology. Pattern recognition is applicable to feature classification problems because pattern recognition automatically assigns a physical object or event to one of several pre-specified categories. Each defect (or feature) shows up as a connected region in the image and each defect can be assigned to a category.

0003There are two types of pattern recognition (PR), structural and statistical. Structural methods use a representation of a feature's shape known as a boundary representation (BREP), while statistical methods use an array of numbers or measurements containing properties of each feature; this numerical information is called a feature vector. In structural pattern recognition the picture of the feature can be recreated from the reduced data since the BREP has complete boundary information in polygonal form. In statistical pattern recognition, however, the picture cannot be recreated from its representation; but, a feature vector is a more compact representation of the object than a BREP. With either method, the goal is to construct a classifier, i.e., a machine to automatically process the image to generate a classification for each feature.

0004In structural pattern recognition, the classifier is based on formal language theory. The BREP is processed into a series of symbols representing the length and direction of the vectors in the boundary. A set of strings consisting of concatenations of these symbols is the language. The grammar, which is a mathematical system of describing the language, describes the structure or the boundary of the features as ordered combinations of symbols. A recognizer, which is constructed from this grammar, works like a computer language compiler used to recognize and distinguish computer language statements. For example, the box of <b>FIG. 1</b> can be thought of as a language. As shown, L = {aⁿ, bⁿ, cⁿ, dⁿ n ≧ 1} is a language describing the box with each side of length "1" or greater.

0005In real-world problems a feature or defect does not have an exact description so the problem is more difficult than parsing a computer language. A structural recognizer that can handle realistic problems has to be based on complicated context sensitive or stochastic grammars to deal with high data complexity and variation. Because of this, structural methods are not readily implemented in typical engineering situations.

0006In contrast, statistical pattern recognition uses a recognizer based on statistical decision theory. Several different types of statistical pattern recognition exist but in general there are two main approaches, called supervised and unsupervised classification.

0007Supervised classification uses a labelled training sample formed when an expert identifies the category of each member of the sample. Probability distributions are estimated or recognizers are constructed directly from the training sample. An expert must examine the data and label each of the features. (Again, the novel pattern recognition approach described herein uses supervised classification.) The effort of labelling a training sample can be made easier by providing a graphical interface to facilitate an expert's interaction with the data.

0008Unsupervised classification doesn't use a labelled training sample. This approach requires the recognizer to learn the underlying probability distribution of the data as it goes, which is often a difficult problem. However, unsupervised classification also does not require the sometimes lengthy process of accumulating a sufficiently large training sample and it does not necessarily require the effort of identifying the members of this sample. The method can be useful in augmenting supervised classification by allowing the system to adapt to changes in the data.

0009In addition to the above-noted approaches, statistical pattern recognition employs two main methods, parametric and non-parametric. Parametric methods assume an underlying probability distribution of the real world data. Non-parametric methods make no such assumptions.

0010Parametric methods are generally used when the distribution is known to be in one of the familiar forms, such as Normal or Gaussian. Classifiers can be generated based on Bayes rule with the <i>a priori</i> distributions known and joint probability distributions determined from the sample data. Specific features can then be compared to the statistics of the known distribution function thereby classifying them.

0011In real-world situations, the data often does not conveniently fall into a Normal or other known distribution. The distribution of a class of features might be multi-modal, i.e., with two or more peaks in the distribution of a defect category (e.g., see <b>FIG. 2)</b>. As in the example of <b>FIG. 2</b>, spot like defects are roundish and easily recognized by an approximately equal length and width, but there might be relatively small and large defects all of which are known as spots. In this example, the spots might be better recognized as the ratio of area to perimeter, which will remain approximately constant as the size of the roundish spots vary. Although a specialized recognizer can be constructed to deal with this example, a method is needed which is generally applicable.

0012Non-parametric methods provide a more general solution to the above problem in that they generate decision functions or a classifier directly from a training sample. By doing this such approaches bypass the parameter estimation problem and ignore any presumed form for the density function. (As described below, the present invention comprises a non-parametric technique.)

0013One of the main difficulties of non-parametric methods is the exponential increase in storage and computational requirements as the dimensionality increases. If the feature is described by a large number of measurements (or elements), the problem can grow to be very large when some of the known methods are used. (Since the technique of the present invention divides the feature space recursively by powers of two, the problem is made more manageable because the storage space only increases as the log base 2.)

<b>Disclosure of the Invention</b>

0014Briefly described, in one aspect a method for generating a statistical classification model from a sample test image having a plurality of features thereon is provided. The statistical model is used for real-time supervised feature classification by an associated image processing system. The model generating method includes the steps of: imaging the sample test image having the plurality of features thereon and producing a digital representation thereof; using the digital image representation to assign a unique classification to selected features of the same type; producing an n-element feature vector for each feature classified, the n-element feature vectors defining an associated n-dimensional feature space; using the assigned classifications to cluster the corresponding feature vectors in feature space, wherein this clustering employs a minimax search to define a tree-like hierarchical decomposition of n-dimensional feature space; and storing the hierarchically decomposed n-dimensional feature space for access by the image processing system during real-time feature classifying of a new pattern.

0015In another aspect, the present invention comprises a real-time image processing method for classifying web features using a supervised statistical classifier. The statistical classifier comprises a tree-like hierarchical decomposition of n-dimensional feature space wherein different feature types are clustered in different feature space cells of the hierarchical tree. This method includes the steps of: imaging the web and producing a digital representation thereof, the imaging operation including producing an n-dimensional feature vector for each imaged feature of the web; referencing the supervised statistical classifier and automatically locating imaged features within corresponding feature space cells of the tree-like hierarchical decomposition of n-dimensional feature space, this locating step comprising searching the hierarchical decomposition of feature space for the smallest cell of the hierarchical tree including the feature vector; and accumulating statistics on imaged features based on the located feature vectors relative to the hierarchical tree. The accumulated statistics include a feature-type classification for the corresponding web feature.

0016In still another aspect of the present invention, a real-time image processing system for classifying web features using a supervised statistical classifier is provided. The statistical classifier comprises a tree-like hierarchical decomposition of n-dimensional feature space wherein different feature types are clustered in different feature space cells of the hierarchical tree. The system includes imaging means for producing a digital image representation of the web, including n-dimensional feature vectors for selected web features. Referencing means for accessing the supervised statistical classifier in a real-time manner and automatically locating feature vectors within corresponding feature space cells of the tree-like hierarchical decomposition of n-dimensional feature space are also provided. For each located feature vector, the locating means includes searching means for traversing the hierarchical decomposition of feature space for the smallest cell of the hierarchical tree including the subject feature vector. Finally, accumulating means accumulates statistics on the selected web features based on their location within the hierarchical tree. The statistics provide for each located feature vector a feature-type classification of the corresponding web feature.

0017Numerous additional method and system enhancements are also described and claimed herein.

0018It will be observed from the above discussion that a novel method for generating a statistical model from a sampled test image (or, preferably, a plurality of sampled test images) is provided. The flexible, non-parametric approach presented produces a classification tree to be searched by an on-line image processing system, e.g. as part of a quality control process. The processing system locates a particular feature vector within a corresponding feature space cell. Once created, the data model remains accurate for the given process and imaging conditions. The resultant data model is more efficient and more accurate at classifying features than heretofore known modeling techniques. Further accuracy may be obtained by simultaneous application of non-supervised methods to automatically learn the probability distribution of defect categories through multiple applications of the technique (herein termed "hyper-tree"). The resultant cell size and ratio of size of cells with the number of defects in them instantly yields information on the quality of the statistical performance. A degree of certainty of recognition can be provided along with an estimation of defect classification. In addition, the technique can be implemented in software or hardware.

<b>Brief Description of the Figures</b>

0019These and other objects, advantages and features of the present invention will be more readily understood from the following detailed description of certain preferred embodiments thereof, when considered in conjunction with the accompanying drawings in which: <ul id="ul0001" list-style="none"><li><b>FIG. 1</b> depicts by way of example a representation of a structural pattern language;</li><li><b>FIG. 2</b> graphically depicts a sample multi-modal distribution of a given class of defects over a defined area;</li><li><b>FIG. 3</b> graphically depicts a simple example of two-dimensional recursive subdivision of feature space pursuant to the present invention;</li><li><b>FIG. 4</b> is a functional flowchart of one embodiment of preliminary processing during creation of a data model pursuant to the present invention;</li><li><b>FIG. 5</b> is a functional flowchart of a specific embodiment of "hyper-tree" processing pursuant to the present invention;</li><li><b>FIG. 6</b> is a block diagram representation of one system embodiment of the present invention; and</li><li><b>FIG. 7</b> is a block diagram of one embodiment of storage structure for a data model constructed pursuant to the present invention.</li></ul>

<b>A Detailed Account Of At Least One Way Of Carrying Out The Invention</b>

0020In the detailed embodiments described herein, the claimed invention is referred to as "hyper-tree."

0021In a hyper-tree method, each defect or feature is initially described by a feature vector containing n measurements or characteristics of the feature. These vectors form a multi-dimensional (or, more specifically, n-dimensional) feature space where the number of dimensions is equal to the number "n" of measurements in the feature vector. Statistical analysis pursuant to the present invention is enhanced by inclusion of greater than three elements or measurements per feature vector. The inventive method breaks down this feature space to form clusters for each defect class. A data model results directly from the clusters of sample data. This data model is ultimately transferred to the on-line defect imaging system and used to categorize new defect data in real-time.

Algorithms

0022The hyper-tree algorithm uses a type of heuristic search, referred to in the art as a "minimax search", which is similar to that used in game theory because it recursively subdivides a multi-dimensional feature space by assuming the presence of a malicious opponent that is trying to destroy the purity of a hyper-cube by introducing features assigned to other classes. It combines this approach with a technique similar to oct-trees used to segment 3-d space for positioning and measuring geometric solids. The oct-tree approach is extended from three dimensions into multiple dimensional (i.e., greater than three-dimensional) "hyper-space" to form a "hyper-tree." It recursively divides the space into smaller and smaller hyper-cubes trying to maintain the purity of the region in hyper-space. The hyper-tree algorithm terminates when a region is pure or when a predefined minimum cell size is reached.

0023The hyper-cube is initially assumed to be an unspecified classification, empty of all points. The first point to arrive in an empty hyper-cube causes the cube to be sub-divided into 2^d child hyper-cubes. As each new point of a given class appears, and it is placed in an empty barren region or in a region of a different class, a sub-division occurs. If the point appears in a classified pure hyper-cube then the count is augmented for that hyper-cube. This process continues recursively until all points in the training sample are read. Since the feature space is a discrete sampled space, the subdivision is repeated only enough times to yield unit-sized hyper-cubes as leaf-nodes on the classification hyper-tree. Hyper-tree doesn't necessarily resolve to a minimum type cell. For example, another criteria can be used to terminate the heuristic search yielding larger than real size hyper-cubes, herein referred to as the maximum decomposition level. In general, an impure leaf-node indicates that points of opposing categories occurred in approximately the same position of hyper-space.

0024<b>FIG. 3</b> is a simplified, two-dimensional example of how the feature space might be divided to distinguish two defect categories in 2-d feature space where each feature vector consists of area and perimeter. In this case the feature space is sub-divided to yield pure squares for each category. The points which fall within the dotted squares are classified as spots and the points which fall within the cross-hatched area are classified as streaks. The clear areas are unclassified. If the points of opposing categories were closer together, the space would be sub-divided into still smaller squares. A more realistic example, however, is harder to illustrate because of the difficulty of drawing multi-dimensional space. If two more dimensions such as length and width are included they would subdivide the resultant hyper-space more accurately. Also in practical applications, an unspecified classification, such as category zero, can be included to cover any defects or features in the training sample not explicitly categorized.

0025The number of leaf-nodes and the level of decomposition indicate the quality of the training sample and the success the resulting data model will have in differentiating between defect categories. Loss and risk functions are generated by considering the ratio of the number of points of other categories in a region dominated by a given category. The encoded feature space or resulting data model is saved, e.g., to a disk, using one bit to indicate the presence of each child hyper-cube. This model can then be read by an on-line image processing program for classification of fresh data in real-time. An overview of one software embodiment of model building pursuant to the present invention is set forth below. <dl id="dl0001"><dt><b>Main program</b></dt><dd>reads each feature in the training sample from the database calling <b>Decompose</b> after reading each new feature.</dd><dt><b>Decompose</b></dt><dd>puts the feature in the hyper-cube if it is of the same type, a minimum sized hyper-cube, or empty. If the node hasn't been initialized yet, it is initialized. If the node is not a leaf node, <b>Decompose</b> is called recursively. If the node is a leaf-node but not a minimum node then <b>Try-to-Exclude</b> is called for every point in the node that has a category different from the current feature. <b>Decompose</b> is then called recursively for every feature of the same category as the current feature.</dd><dt><b>Try-to-Exclude</b></dt><dd>puts the feature in the node if it is a minimum cell, or empty. If the node hasn't been initialized yet, it is initialized. If the node is a leaf-node but not a minimum node then <b>Decompose</b> is called for every point in the node that has a category the same as feature. <b>Try-to-Exclude</b> is then called recursively with the feature.</dd><dt><b>Traverse</b></dt><dd>accumulates the statistics of the data model. It traverses the hyper-tree calculating the <i>a priori</i> and <i>a posterior</i> probabilities, the mean, the variance and the cost and risk functions for each defect category.</dd><dt><b>Printstat</b></dt><dd>prints a summary of the statistics gathered by <b>Traverse.</b></dd><dt><b>Writemx</b></dt><dd>recursively descends the hyper-tree writing a data model to the disk using an encoded form where only one bit is used for each child hyper-cube.</dd></dl>

0026The pseudo-code below describes the principal program components summarized above. Variable names are in italics.    ©1992 Eastman Kodak Company

Main program

0027Initialize head pointer to hyper-tree.    Establish maximum level of decomposition.    Determine minimum cell size for leaf-nodes.    For n = 1 to the total number of features (N) do the following     Read <i>feature</i>_{<u><i>n</i></u>} from Segmented Image Database     Call <b>Decompose</b> (<i>feature</i>_{<u><i>n</i></u>}, <i>head</i>) which attempts to place feature in correct hyper- cube.    Call <b>Traverse</b> to accumulate the statistics for each category.    Call <b>Printstat</b> to print the statistics.

Decompose

(<i>feature, node</i>)

0028If <i>node</i> is at minimum size or the maximum level of decomposition is reached then     put <i>feature</i> in child's list of features    else is <i>node</i> is leaf node then     if there are no points of other categories in <i>node</i> then      put <i>feature</i> in <i>node's</i> list of features else begin block      find center of cell for point <i>feature</i>.      if child cell corresponding to new center is NIL then       make new <i>child-cell</i>      call <b>Decompose</b><i>(child-cell, feature)</i> for all categories Ω ={ω₁..ω_k},i=1...k do       if category of <i>feature</i> is not the same as ω_i then begin       for all old points in <i>node's</i> list of category ω_i do        take old point,        <i>oldpoint</i> of category ω_i        from list        find center of cell for <i>oldpoint</i>.        if <i>child-cell</i> for new center is NIL         make new <i>child-cell</i>        call <b>Try-to-Exclude</b><i>(child_cell, oldpoint)</i>       end for all      end if      end for all     end of block    else begin block     find center of cell for <i>feature</i>.     if child cell corresponding to new center is NIL then      make new <i>child-cell</i>     call <b>Decompose</b><i>(child-cell, feature)</i>    end of block    end of procedure <b>Decompose.</b>

Try-to-exclude (<i>feature, node</i>)

0029If node is minimum size or maximum level of decomposition is reached then     put <i>feature</i> in <i>node's</i> list of features    else if <i>node</i> is leaf-node then     if there are no points of other categories in <i>node</i> then      put <i>feature</i> in <i>node's</i> list of features else begin block      find center of cell for <i>feature</i>.     if <i>child-cell</i> corresponding to new center is NIL then      make new <i>child-cell</i>     for all points in <i>child-cell's</i> list     for category of <i>feature</i> do      take <i>oldpoint</i> from list      find center of cell for <i>oldpoint</i>      if child cell corresponding to new center is NIL then       make new <i>child-cell</i>      call <b>Decompose</b><i>(child-cell, oldpoint)</i>     end for all     call <b>Decompose</b><i>(child-cell, feature)</i> to push <i>feature</i> down list.     end of block    else begin block     find center of cell for point feature. if <i>child-cell</i> corresponding to new center is NIL then      make new <i>child-cell</i>     call <b>Try-to-Exclude</b><i>(child-cell, feature)</i>    end of block    end of procedure <b>Try-to-Exclude.</b>

Traverse

0030For category = 0 to maximum feature type do     Initialize area and count to 0     For i = 0 to Max Dimension Do      Initialize mean and variance to 0     Initialize risk, apriori and aposteriori to 0    For level = 0 to Maximum decomposition level do      Initialize area and count to 0    If root node is not barren     bump level     For n = 0 to 2^DIM do      if child cube (n) exists       call <b>follow branch</b><i>to accumulate sum for mean</i>      <i>calculate mean</i>      for category = 0 to maximum feature type do       if count for this cat is 0        mean = 0       else        mean = sum/count [category]        <i>calculate aposteriori</i>        if volume_total[category] is 0         aposti = 0        else         aposti = count/volume total       <i>Do the traversal again to get sum²</i> for variance       for n = 0 to 2^DIM        if root is not barren         call <b>follow again</b>       <i>Now calculate standard deviation and apriori</i>    for category 1 to maximum feature type do apriori = count/total     for i = 0 to DIM      SD[i] = sqrt [sum²/total count]     For category 2 to maximum feature type DO      if category 1 = category 2       expected loss [category 2] = 0      else       expected loss = vol_count [category 1 * category 2] / category_count * apriori for category 1.       risk = 1 category_count/volume total [category 1].

Follow branch

0031If this note is barren <i>it is a leaf node</i>     sum area     find the category of this cell     sum feature vectors into array    else     for n = 0 to 2^DIM      if progeny [n] exists       call <b>follow branch</b>

Follow again

0032if this node is a leaf node     for each vector in this cell      sq_accum = sq_accum + (vector[i] -mean[i])² <i>Used to calculate variance and standard deviation</i>    else      for n = 0 to 2^DIM

Implementation of Hyper-tree

0033Referring to <b>FIG. 4</b>, the Hyper-tree method of supervised classification requires a large training sample, which comes from the real-time imaging system in the form of encoded thresholded binary images, 20 "Training Sample of Encoded Threshold Binary Images." The connected regions or features are then extracted from the image by performing a connectivity analysis, 22 "Extract Connected Regions." Each connected region is described by a list of vertices, a boundary description or an enclosing polygon. Each list of vertices is stored in a database indexed by a unique identifier or feature number, 24 "Store Connected Regions in Database."

0034Geometric measurements are obtained from each region in the database and formed into an array of integers called a feature vector, 26 "Obtain Geometric Measurements &amp; Form Into Feature Vector." This array includes, for example, x and y positions, width, length, perimeter and area such that multi- dimensional hyper-space is defined thereby. Each feature vector is stored in the database indexed by the feature number, 28 "Save Feature Vectors." After this step the database contains information describing all the features in the training sample.

0035For supervised classification as in hyper-tree, it is necessary to establish <i>a priori</i> classifications of each feature of interest in the training sample. Pictures of all the features are displayed on the screen of a graphic workstation so an expert can scroll through them marking all interesting features with the appropriate classifications, 30 "Classify Feature Vectors."

0036Hyper-tree reads the sample set of classified features from the database, develops the classifier or data model and stores it, 32 "Call Hyper-Tree To Create Data Model." This is accomplished by building a multidimensional hyper-tree in memory, dividing the feature space as specified by the classifications of the sample data. The <i>a priori</i> probability, the <i>a posteriori</i> probability, mean, variance, loss function, and the risk function for each defect category are all preferably calculated (and printed). The loss function is the probability of choosing any wrong classification for a given feature when the true state of nature is a different classification. The risk function is the probability of choosing a specific wrong classification.

0037<b>FIG. 5</b> depicts a specific hyper-tree processing approach utilizing the subroutines summarized above. Hyper-tree processing begins by initializing a pointer to the main program, 40 "Initialize Pointer To <b>Hyper- Tree."</b> Thereafter, the maximum level of decomposition is determined, 42 "Establish Maximum Level Of Decomposition," and a minimum cell size is determined, 44 "Determine Minimum Cell Size For Leaf-Nodes." For each stored feature, the decomposed subroutine is called to place the feature in a correct hyper-cube, 46 "For Each Feature, Read Feature From Database &amp; Call <b>Decompose</b><i>(Feature</i>_n, <i>Head)</i> To Place Feature In Correct Hyper-Cube." Once each feature has been positioned, the classification tree is traversed to accumulate statistics for each classification, 48 "Call <b>Traverse</b> To Accumulate Statistics For Each Category," and the statistics are printed, 50 "Call <b>Prinstat</b> To Print The Statistics."

0038By way of example, <b>Table</b> 1 below is an output listing from one embodiment of hyper-tree run on a sample of two defect types on motion picture film. The table shows the extent of the subdivision of the feature space, the calculated cost and risk functions and the mean and standard deviation for each element in the feature vector. <tables id="tabl0001" num="0001"><img file="EP0572335A2_D0001.tif" /></tables><tables id="tabl0002" num="0002"><img file="EP0572335A2_D0002.tif" /></tables><tables id="tabl0003" num="0003"><img file="EP0572335A2_D0003.tif" /></tables><tables id="tabl0004" num="0004"><img file="EP0572335A2_D0004.tif" /></tables><tables id="tabl0005" num="0005"><img file="EP0572335A2_D0005.tif" /></tables><tables id="tabl0006" num="0006"><img file="EP0572335A2_D0006.tif" /></tables><tables id="tabl0007" num="0007"><img file="EP0572335A2_D0007.tif" /></tables>

0039The first part of the listing shows the breakdown of the feature space. The "areas" are actually the sizes of one edge of a hyper-cube. Large areas mean that the hyper-space was subdivided less meaning that the feature clusters are more distinct. Also the number of features of each category are shown for each level of decomposition.

0040The statistics are shown in the second part of the listing. The <i>a priori</i> probability is based on the number of features of a given category in the total sample. The loss function, risk function and the <i>a posteriori</i> probability are based on a determination of the "purity" of the feature clusters.

0041A program, <b>Decision</b> (discussed below), reads the classifier or data model and uses it to classify each file of new feature vectors. It first builds a hyper-tree in memory from the compact representation on the disk. <b>Decision</b> then reads all the feature vectors in the file and generates the classifications. It does this by traversing the hyper-tree assigning a classification when a feature falls into a leaf-node hyper-cube.

Derivation of Hyper-tree

0042The derivation of the formulas for <i>a posteriori</i> probability, calculated loss, and calculated risk functions for each defect category are shown in this section. In hyper-tree, the actual classifier or data model is based on non-parametric methods where the classifier results directly from the subdivision of feature space bypassing estimation of the probability distributions and the density function. Estimated probability distributions and density functions can be calculated from the training sample but these estimations are not used by the hyper-tree program. Hyper-tree's formula for the <i>a posteriori</i> probability is:<maths id="math0001"><math display="block"><mrow><mfrac><mrow><msub><mrow><mtext>k</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow><mrow><mtext>k</mtext></mrow></mfrac></mrow></math><img file="EP0572335A2_D0008.tif" /></maths> where k_i is the number of features in sub-volume V of type i, and k is the total number of features in sub-volume V. If the assumption is made that the feature space is already optimally subdivided into hyper-cubes, this section shows the derivation.

0043In the hyper-tree method, the feature space is a discrete sampling of real feature space and the sub-divisions are binary so some sampling error may be introduced. This sampling error is presumed to be small and is not taken into account. Also since the data consists of measurements taken from a sampled image and the feature space is sub-divided no further than a minimum hyper-cube size of one, the sampling error should be negligible. Given a set of n categories:<maths id="math0002" num="(1)"><math display="block"><mrow><mtext>Ω</mtext><mtext> = (</mtext><mtext>ω</mtext><mtext>₁...</mtext><msub><mrow><mtext>ω</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>...</mtext><msub><mrow><mtext>ω</mtext></mrow><mrow><mtext>s</mtext></mrow></msub><mtext>), 1 ≦ j ≦ s.</mtext></mrow></math><img file="EP0572335A2_D0009.tif" /></maths>

0044The sample set consists of a number of feature vectors <b>X</b>, each of which has d elements:<maths id="math0003" num="(2)"><math display="block"><mrow><msub><mrow><mtext>x = (x₁...x</mtext></mrow><mrow><mtext>d</mtext></mrow></msub><mtext>), forming hyper-space </mtext><msub><mrow><mtext>R</mtext></mrow><mrow><mtext>d</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0572335A2_D0010.tif" /></maths>

0045If we assume that the sample size is sufficiently large such that the apriori probability of a defect occurring as a given category ω_j, <b>P</b>(ω_j) can be predicted accurately, than the probability of P(ω_j) is equal to:<maths id="math0004" num="(3)"><math display="block"><mrow><msub><mrow><mtext>p(ω</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) = </mtext><mfrac><mrow><msub><mrow><mtext>n</mtext></mrow><mrow><mtext>j</mtext></mrow></msub></mrow><mrow><mtext>N</mtext></mrow></mfrac></mrow></math><img file="EP0572335A2_D0011.tif" /></maths> where n_j is the number of points category j and N is the total number of points.

0046If we assume the probability P that a feature <b>x</b> will fall in a region in hyper-space <b>R</b> is,<maths id="math0005"><img file="EP0572335A2_D0012.tif" /></maths> were d<b>x</b>' is a volume element.<maths id="math0006" num="(5)"><math display="block"><mrow><mtext>P ≅ p(</mtext><mtext>x</mtext><mtext>)V</mtext></mrow></math><img file="EP0572335A2_D0013.tif" /></maths> where V is the volume of a region <b>R</b> in hyper-space.

0047In non-parametric techniques such as the Parzen windows and nearest neighbor methods, a hyper-volume in d-space is chosen of sufficient size to include a certain number of features of a given category ω_j. In hyper-tree, the method presented herein, the hyper-volume V is chosen to contain k points such that k ≧ k_j where k_j is all the defects of category j in volume V. The space average conditional probability density p(<b>x</b>|ωj) where<maths id="math0007" num="(6)"><math display="block"><mrow><msub><mrow><mtext>p(x|ω</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) = </mtext><mfrac><mrow><msub><mrow><mtext>k</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>/N</mtext></mrow><mrow><mtext>V</mtext></mrow></mfrac></mrow></math><img file="EP0572335A2_D0014.tif" /></maths>

0048Bayes rule states that p(ω_j)p(<b>x</b>|ω_j) = p(<b>x</b>)p(ω_j,<b>x</b>) where<maths id="math0008"><img file="EP0572335A2_D0015.tif" /></maths>

0049So Bayes' rule can be applied to calculate the a <i>posteriori</i> probability:

0050When a feature of type <b>x</b> is encountered the<maths id="math0009"><img file="EP0572335A2_D0016.tif" /></maths> decision rule which minimizes the cost of making a wrong decision should be applied. The decision rule used in this method minimizes the overall risk given a particular sample space. This is the Bayes risk and is the minimum risk that can be achieved.

0051If action α_i is taken when the true classification is <b>ω</b>_j, the expected loss is<maths id="math0010" num="(9)"><math display="block"><mrow><msub><mrow><mtext>λ(α</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>|ω</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0572335A2_D0017.tif" /></maths>

0052This expected loss function can be estimated from the training sample by the number of points of type i in the volume V.<maths id="math0011" num="(10)"><math display="block"><mrow><msub><mrow><mtext>λ(α</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>|ω</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext>) = </mtext><mfrac><mrow><msub><mrow><mtext>k</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext>k</mtext></mrow><mrow><mtext>j</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0572335A2_D0018.tif" /></maths>

0053The total conditional risk for taking action α_i given feature <b>x</b>, R(<b>α</b>_i|<b>x</b>) is:<maths id="math0012"><img file="EP0572335A2_D0019.tif" /></maths>

Performance Analysis

0054In this section, the hyper-tree algorithm is analyzed and compared to other algorithms used to do statistical pattern recognition. Execution time and storage space considerations involved in the choice of non-parametric methods vs. parametric methods are discussed and some specific performance improvements of hyper-tree processing in comparison with other non-parametric methods are set forth.

0055Parametric methods require less storage space than non-parametric methods. In parametric methods, the underlying probability distribution functions are known and discriminant functions can be calculated from the <i>a priori</i> and the class conditional density functions so there is no need to store an actual representation of the feature space. Thus the total storage space requirements are minimized. Hyper-tree's use of memory is minimized by efficient binary encoding of the multidimensional classifier, and with the ever decreasing memory costs in today's computers the consideration of storage space requirements is of decreasing importance.

0056In non-parametric methods such as nearest-neighbor or Parzen windows, the computational requirements can be prohibitive for high data dimensionality. For each feature, or point in hyper-space, a volume must be selected which will grow to enclose a number of neighboring points, large enough to be able to classify the point in terms of the majority of its neighbors. This will run in O(n²) where n is the number of features for a one category classifier. For a two category classifier this will run in O(n⁴) and for three categories, it will run in O(n⁸). For c classes, it will run in O(n²**^c).

0057In hyper-tree the feature space is decomposed by successive binary division. Therefore the worst case execution time for a one category classifier when the feature space is completely decomposed is O[nlog(n)], where n is the number of features. An increase in dimensionality does not greatly increase execution time. The factor is linear because there is only one more compare operation per feature for every extra element in the feature vector. For multiple categories the effect is as follows. For two categories hyper-tree will run in O[n²log(n)], for three categories it will run in O[n³log(n)], and for c categories, O[n^clog(n)]. Although there is degradation in performance of hyper-tree for very large numbers of unique categories the performance doesn't degrade as fast as other methods.

Operational Defect Classification System

Using Hyper-Tree

0058This section discusses a complete system, shown in block diagram form in <b>FIG. 6</b>, using an off-line workstation (denoted 60) and a <b>VEREDUS</b>™ Real-time Surface Flaw Detection and Analysis System, labeled 80, which is marketed by EKTRON Applied Imaging, Inc., an Eastman Kodak Company located in Rochester, New York, to recognize and classify defects by category. At the core of this system is the hyper-tree method of statistical pattern recognition.

0059The <b>VEREDUS</b>™ system 80 is a special purpose fast pipe-lined image processing system used to detect surface or imbedded flaws or defects optically in a web 62 based coating, plating or similar process. <b>VEREDUS</b>™ can be connected to one or more linear optical image sensors 64. It produces reports 72 which are statistical tabulations of defect types and statistics for an operator (not shown).

0060Hyper-tree is part of a system 60 used to "teach" the <b>VEREDUS</b>™ real-time system 80 to recognize defects on a moving web while it is scanning in real-time. This program is integrated with other programs in a system centered on a relational defect database 74. The system consists of the following programs: (1) <b>Connect</b> 73 which segments the image and inserts the segmented image information into the database 74; (2) <b>Geo</b> 75 which takes the geometric measurements of the defects forming the feature vectors and puts the results into the database 74; (3) <b>Classify</b> 76 which is a program run by the operator to assign apriori or known classifications to the features in the "training sample"; and (4) <b>Hyper-tree</b> 77, described above which partitions the feature space to form the classifier or classification model, called here the "OFCLAS Data Model." There is also a fifth program, <b>Decision</b> 70 in System 80 which takes the data model, OFCLAS, and applies it to new as yet unclassified data, i.e., to do an a posteriori classification operation.

0061A special mode is available on <b>VEREDUS</b>™ system 80 to grab part of a scanned image of interest in compressed form, known as Y-group encoding 66. This Y-group encoded image can be moved from the <b>VEREDUS</b>™ system to the off-line classification system 60 through either shared VMEbus memory, serial port or tcp/ip if system 80 is so equipped. <ul id="ul0002" list-style="none"><li>1. <b>Connect</b> obtains the compressed image. This is generally a binary image, e.g., 1 bit per pixel, but could have more bits per pixel. The image is decompressed from Y-group coding as it is segmented into physically separate features by following each scan line and recording each intersection with a change in the image pixel value. This in effect finds the boundaries of each feature in the image. After thinning to reduce the number of vertices to the minimum necessary, each feature is stored in the database as a list of x,y pairs of vertices which describe the outline or boundary of all negative and positive space of the feature. In other words, the outer boundary is stored along with the boundaries of any holes or negative regions. Each of these features is stored in the database with a unique key.</li><li>2. <b>Geo</b> reads the features from the database and takes geometric measurements of each one. These measurements form what is called a feature vector, i.e., a list of numbers describing the geometric characteristics of each of these features. The feature vector can include the width at the widest point, the length along the longest point, the perimeter, and the area excluding any holes. It can also optionally include the x,y coordinate position, the centroid or center of gravity and the projected length. <b>Geo</b> puts the feature vector for each feature into the database and keys it to the boundary obtained by <b>Connect.</b></li><li>3. <b>Classify</b> paints a graphical representation of the original image on the screen of the off-line workstation using the boundary vertex lists found in the database and allows the user to choose features of interest by picking them with a mouse. The user of the program can choose a classification for each feature of interest. This is how the a priori classifications are determined. Each of these a priori classifications are stored in the database and keyed to the boundary list and the feature vector described above.</li><li>4. The <b>Hyper-tree</b> program is run to create the classifier or classification model. This model is known as the OFCLAS data model. The method used by <b>Hyper-tree</b> to develop this model is described in detail above. The model is transferred to the <b>VEREDUS</b> system 80 using one of the above-noted interfaces.</li><li>5. <b>Decision</b> classifies new data according to the model. There can also be a version to be run on the off-line system to verify or check the results.</li></ul>

0062<b>FIG. 7</b> depicts one embodiment of a data model structure, again denoted "OFCLAS" and constructed pursuant to of the present invention. Standardized names and numbers are preferably assigned to each measurement. In the sample data model of <b>FIG. 7</b>, the following terms apply: <dl id="dl0002"><dt><b>Dim</b></dt><dd>The dimensionality of the data model. This is equivalent to the number of elements in the feature vector.</dd><dt><b>Level</b></dt><dd>The number of decomposition levels used in this model.</dd><dt><b>Class</b></dt><dd>The classification.</dd><dt><b>MAXCLASS</b></dt><dd>The maximum number of classifications or categories possible.</dd><dt><b>Risk</b></dt><dd>The loss function (or cost) associated with choosing category <b>j</b> when the actual category is <b>i</b>. This is implemented as a 2 dimensional array of <b>MAXCLASS</b> elements where each element is a floating point number.</dd><dt><b>Loss</b></dt><dd>The loss function (or cost) associated with any wrong choice of category. This is represented as an array of floating point numbers.</dd><dt><b>Daughtermask</b></dt><dd>The mask has one bit for every possible daughter, where the maximum number of daughters is <b>2</b>^<b>dim</b>. A 1 in a bit position means that a daughter exists, a 0 means the daughter doesn't exist. There is always a <b>Daughtermask</b> in the root node. In other nodes the <b>Daughtermask</b> exists only if the class of the node is >0.</dd><dt><b>Cube</b></dt><dd>The data structure containing the classification and the <b>Daughtermask</b> for the next level. If the cube is a leaf-node, the class is >0. If the class is less than 0, a <b>Daughtermask</b> follows.</dd></dl>

0063The data structure is recursive where the maximum possible number of cubes is equal to the number of decomposition levels multiplied by 2 raised to the power of the dimensionality, <b>dim.</b> Or in other words    <b>maxcubes = level x 2</b>^<b>dim</b><b>.</b>

0064Expressed in <b>"C"</b> the maximum number of cubes is    <b>maxcubes = level</b> * <b>(1</b><b>&lt;&lt;</b><b>dim).</b>

0065The number of bytes necessary for the daughtermask is    <b>2</b>^<b>dim-3</b>.

0066Expressed in <b>"C"</b> the daughter mask is defined as:    <b>char daughtermask [1 &lt;&lt; (dim-3) ].</b>

0067The actual number of cubes will generally be much less than the maximum. It is related to the quality of the classifier, the statistical distribution of the original data in the training sample which was used to create the model.

0068The top of the data model will have a header. Next will be the loss function array, followed by the risk arrays. Finally the cubes are found in order from the root cube to the leaves.

0069It will be observed from the above discussion that a novel method for generating a statistical model from a sampled test image (or, preferably, a plurality of sampled test images) is provided. The flexible, non-parametric approach presented produces a classification tree to be depth-first searched by an on-line image processing system, e.g. as part of a quality control process. The processing system locates a particular feature vector within a corresponding feature space cell. Once created, the data model remains accurate for the given process and imaging conditions. The resultant data model is more efficient and more accurate at classifying features than heretofore known modeling techniques. Further accuracy may be obtained by simultaneous application of non-supervised methods to automatically learn the probability distribution of defect categories through multiple applications of the technique (herein termed "hyper-tree"). The resultant cell size and ratio of size of cells with the number of defects in them instantly yields information on the quality of the statistical performance. A degree of certainty of recognition can be provided along with prior estimations of defect classification. In addition, the technique can be implemented in software or hardware.

0070Although specific embodiments of the present invention have been illustrated in the accompanying drawings and described in the foregoing detailed description, it will be understood that the invention is not limited to the particular embodiments described herein, but is capable of numerous rearrangements, modifications, and substitutions without departing from the scope of the invention. The following claims are intended to encompass all such modifications.