Image analysis – Pattern recognition – Classification
Reexamination Certificate
1999-06-04
2002-01-08
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Classification
C382S228000, C382S160000
Reexamination Certificate
active
06337927
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to systems and methods for assigning input patterns into one of two classes and more particularly to a system and a method for classifying input patterns based on a linear classification.
DESCRIPTION OF THE RELATED ART
Pattern classification has drawn increasing attention in recent years, due to its application in a number of technological areas, such as acoustic signal processing and image processing. The objective in pattern classification is to separate input patterns into two classes, a target class and a non-target class. For example, for face detection in images, vectors (blocks of pixels) are extracted from an image and each vector is examined to determine whether it contains an image of a human face (target class) or not (non-target class). Another example is the detection of a specific sound, e.g., a piano sound, in an arbitrary sound signal stream. In this case, the components of the sound signal stream are classified into the specific sound class (target class) or background class (non-target class).
Various types of pattern classifiers are known in the art. Most pattern classifiers are configured to discriminate between the two classes by “learning” from two training sets, {circumflex over (X)}={x
i
}
i=1 . . . Lx
(target samples) and Ŷ={y
i
}
i=1 . . . Ly
(non-target samples). Such classifiers are known as example-based classifiers. The simplest and computationally fastest type of pattern classifier is a linear classifier C(z), where the classifying operation is based on a mathematical projection followed by a thresholding. For a given input pattern, i.e., a vector z, the projection of z is performed onto a projection vector u and, thus, C(z)=f(u
T
z), where f(*) is a thresholding operation or some other decision rule.
Various types of pattern classifiers are known in the art. Most pattern classifiers are configured to discriminate between the two classes by “learning” from two training sets, {circumflex over (X)}={x
i
}
i=1 . . . Lx
(target samples) and Ŷ={y
i
}
i=1 . . . Ly
(non-target samples). Such classifiers are known as example-based classifiers. The simplest and computationally fastest type of pattern classifier is a linear classifier C(z), where the classifying operation is based on a mathematical projection followed by a thresholding. For a given input pattern, i.e., a vector z, the projection of z is performed onto a projection vector u and, thus, C(z)=f(u
t
z), where f(*) is a thresholding operation or some other decision rule and where U
T
is the related transpose.
Therefore, what is needed is a system and a method for efficiently and accurately classifying input patterns into two classes, even in cases where the configuration of the two classes is complex and cannot be separated by a linear hyper-plane.
SUMMARY OF THE INVENTION
A system and a method for classifying input vectors into one of two classes, a target class and a non-target class, utilize iterative rejection stages to first label the input vectors that belong in the non-target class in order to identify the remaining non-labeled input vectors as belonging in the target class. Each iterative rejection stage involves a linear projection of an input vector that is followed by a thresholding to determine whether that input vector belongs in the non-target class. The system and method may be used in a number of applications, such as face detection, where the members of the two classes can be represented in a vector form. In a face detecting application, the system operates to determine whether an input vector, representing a block of image pixels, contains a picture of a human face.
The operation of the system can be divided into an off-line (training) procedure and an on-line (actual classification) procedure. During the off-line procedure, a training module of the system computes the projection vectors and their corresponding threshold values that will be used during the on-line procedure. During the on-line procedure, the projection vectors and the threshold values are utilized by a pattern classifier of the system to execute the iterative rejection stages to determine if an input vector should be labeled as a non-target. After all the iterative rejection stages are executed, the input vector is identified as a target, if it had not been previously labeled as a non-target.
An off-line method of computing the projection vectors and their corresponding threshold values in accordance with the invention begins when a training set of vectors, including sample targets and sample non-targets, is received by the training module of the system. Mean-variance pairs for the sample targets and the sample non-targets are then computed by the mean-variance pair calculator of the training module. Using a proximity measure approach, a first projection vector is calculated by the projection vector calculator of the training module. Preferably, the first projection vector facilitates a positive identification of a large portion of the sample non-targets. In particular, the first projection vector is chosen such that projection values of many sample non-targets fall outside a target-containing interval, i.e., an interval of projection values that contains the projection values of all the sample targets when projected onto the first projection vector.
Next, a pair of threshold values is chosen for the first projection vector by the threshold setter of the training module. The pair of threshold values defines the upper and lower limits of the target-containing interval. The threshold values are chosen to include the smallest and the largest projection values of the sample targets. The separation between the two threshold values may include the separation between the smallest and the largest projection values of the sample targets, as well as a safety margin. The safety margin may be some percentage of the separation between the smallest and the largest projection values of the sample targets, e.g., five percent, to reduce the risk of erroneous non-target classification. After the pair of threshold values has been set, the sample non-targets having projection values that fall outside of the target-containing interval defined by the two threshold values are removed from the training set. The result is a reduced training set that contains fewer sample non-targets.
Using the reduced training set, a new mean-variance pair for the remaining sample non-targets is then computed by the mean-variance pair calculator. Next, a second projection vector and its corresponding pair of threshold values are calculated by the projection vector calculator and the threshold setter, respectively, in the same manner in which the first projection vector and its corresponding pair of threshold values were derived. This process is repeated until all the sample non-targets have been removed from the training set. The end product of the off-line procedure is a number of projection vectors and their corresponding threshold values that can be utilized during an on-line procedure to classify unknown input vectors into one of the two classes.
An on-line method of classifying input vectors into one of the two classes is primarily executed by the pattern classifier of the system. The method begins at a step in which the input vectors, as well as the computed projection vectors and their corresponding threshold values, are received by the pattern classifier. For each input vector, successive rejection stages are performed by the linear projection unit and the threshold module of the pattern classifier. During each stage, an input vector is linearly projected using one of the projection vectors computed during the off-line procedure to derive a projection value. The projection value is then compared to corresponding pair of threshold values. If the projection value falls outside the target-containing interval defined by the threshold values, the input vector is labeled as a n
Elad Michael
Hel-Or Yacov
Kresch Renato
Au Amelia M.
Dastouri Mehrdad
LandOfFree
Approximated invariant method for pattern detection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Approximated invariant method for pattern detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximated invariant method for pattern detection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2842850