Method of performing facial recognition using genetically modified fuzzy linear discriminant analysis

The method of performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis (LDA) is based on the Fisherface LDA, with a modification being made in calculation of the membership function. Particularly, the membership function is computed using a pair of parameters α and β, which are optimized by a genetic algorithm in order to minimize the recognition error.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to biometrics and computer applications for facial recognition, and particularly to a method of performing facial recognition using genetically modified fuzzy linear discriminant analysis, including modification of the Fuzzy Fisherface classification scheme.

2. Description of the Related Art

Facial recognition has recently found many applications and has attracted substantial research efforts from the areas of computer vision, bio-informatics, and machine learning. The techniques used for facial recognition are broadly classified as either appearance-based or geometrical feature-based. The appearance-based techniques use the holistic features of the face image, whereas the geometrical features of the image are utilized in the latter. Some researchers have also adopted a hybrid methodology by applying the appearance-based techniques on the localized regions of the facial image.

Principal Component Analysis (PCA) is one of the most successful techniques used in face image recognition. PCA can be used to perform prediction, redundancy removal, feature extraction, and data compression, etc. PCA essentially reduces the large dimensionality of the data space. The projection of the data is in the direction of the maximum variance of the data used to find the features. However, this subspace is not necessarily optimal in terms of face classification. Large 1-D vectors of pixels are constructed from 2-D facial images, by concatenating the columns and are then projected onto the eigenvectors of the covariance matrix of the training image vectors. If there are N (the number of images) vectors of size M (rows by columns of an image), then the mean vector of all of the images is given by:

In PCA, the image vectors are first mean-centered. The set of T orthonormal vectors wi's is sought, forming the projection matrix W of order (M×T), and the feature vectors are then given by the following linear transformation:
yk=WTxk(2)

PCA relies on maximizing the total scatter of the training vectors. The total scatter matrix STis given by:

ST=∑k=1N⁢(xk-m)⁢(xk-m)T.(3)
The scatter of the transformed feature vectors is given by WTSTW. The projection matrix WPCAsatisfies the following:
WPCA=argWmax|WTSTW|.(4)

It can be shown from linear algebra that the wiare the eigenvectors of the covariance matrix C=PTP, where P is a matrix composed of the mean centered images mias the column vectors placed side by side. Since N image vectors are summed up, the rank of the covariance matrix cannot exceed (N−1), since the vectors are mean subtracted.

The non-zero eigenvalues of the covariance matrix have corresponding orthonormal eigenvectors. The eigenvector associated with the largest eigenvalue is one that reflects the greatest variance in the image. The eigenvalues decrease very rapidly: Roughly 90% of the total variance is contained in the first 5% to 10% of the dimensions, as shown inFIG. 2.

FIG. 2shows only the first one hundred eigenvectors used for projection, but it is clear that projection using only the first fifteen eigenvectors of the covariance matrix results in above 90% recognition accuracy. Thus, image vectors are projected onto a subspace formed by the most significant eigenvectors (i.e., the principal components) of the covariance matrix. When a test image is projected onto the N-dimensional subspace, it is classified as the class of the vector that minimizes the Euclidean distance with it.

Linear Discriminant Analysis (LDA) looks for the projection matrix that provides the best discrimination among the different classes. LDA tries to achieve this by finding a subspace in which the projected vectors of the different classes are maximally separated. The between-class scatter matrix SBand the within-class scatter matrix SWare defined as:

SB=∑i=1c⁢Mi⁡(xi-m)·(xi-m)T(5)SW=∑i=1c⁢∑xk∈Xi⁢Mi⁡(xi-mi)·(xi-m)T,(6)
where Miis the number of training vectors in the i-th class, c is the number of distinct classes, miis the mean of all the vectors belonging to the i-th class, and Xirepresents the set of samples belonging to the i-th class, where xkis the k-th image of that class.

SWrepresents the scatter of the features around the mean of each class, and SBrepresents the scatter of features around the overall mean for all the classes. In Fisher's LDA, the aim is to maximize SBwhile minimizing SW, which translates to maximize the ratio between their determinants

This ratio is maximized when the column vectors of the projection matrix WLDAare the eigenvectors of SW−1SB. In order to avoid SWfrom becoming singular, PCA is used as a preprocessing step. Thus, the final transformation is given by the following matrix:
WT=WLDAT·WPCAT.  (8)
LDA produces well-separated classes in a low-dimensional subspace, even under severe variations in lighting and facial expressions.

In the Fuzzy Fisherface LDA (FLDA), the basic LDA is modified. The modification is the introduction of fuzziness into the “belong-ness” of every projected vector to the classes. In the conventional approach, every vector is assumed to have a crisp membership in the class to which it belongs. However, this does not take into account the resemblance of images belonging to different classes, which occurs under varying conditions. In FLDA, a vector is assigned the membership grades for every class based upon the class label of its k nearest neighbors. This fuzzy k-nearest neighbor algorithm is used to calculate the membership grades of all the vectors. In this manner, the inter-class image resemblance is accounted for. The fuzzy C-class partitioning of the vectors defines the degrees of membership of each vector to all the classes.

In the following, μijrepresents the membership grade of the j-th vector in the i-th class. The membership functions satisfy the two obvious conditions:

During the training phase, the class labels of the k vectors located in the closest neighborhood of each vector is collected. Then, the membership grade of the j-th vector to i-th class is calculated using the expression as:

m_l=∑j=1N⁢μijp⁢xj∑j=1N⁢μijp(12)FSB=∑i=1C⁢∑j=1N⁢μijp⁡(m_l-m)·(m_l-m)T(13)FSW=∑i=1C⁢∑xk∈Xi⁢μijp⁡(xi-m_l)·(xi-m_l)T(14)
where i=1, 2, . . . , c and p, a fuzzy modifier, is a constant that controls the influence of the fuzzy membership degree.

Although the Fuzzy Fisherface LDA modification results in improved facial recognition, there is still a need for further improvement in computer applications for facial recognition. Thus, a method of performing facial recognition using genetically modified fuzzy linear discriminant analysis solving the aforementioned problems is desired.

SUMMARY OF THE INVENTION

In conventional facial recognition methods, the relationship of each face to a particular class is assumed to be crisp. The Fuzzy Fisherface method introduces a gradual level of assignment of each face pattern to a class, using a membership grading based upon the K-Nearest Neighbor (KNN) algorithm. In the present method, the Fuzzy Fisherface Linear Discriminant Analysis method is modified by incorporating the membership grade of each face pattern into the calculation of the between-class and with-in class scatter matrices in a process referred to herein as “Complete Fuzzy LDA” (CFLDA).

Both the Fuzzy Fisherface and CFLDA methods utilize the Fuzzy-KNN algorithm. The present method further improves the assignment of class membership by improving the parameters of the membership functions. A genetic algorithm is used to optimize these parameters by searching the parameter space. Further, the genetic algorithm is used to find the optimal number of nearest neighbors to be considered during the training phase.

The present method of performing facial recognition using a genetic algorithm-modified fuzzy linear discriminant analysis can be summarized by the following set of steps: (a) establishing a set of N test face images, where N is a non-zero, positive integer; (b) establishing a set of N training face images; (c) calculating a mean vector of all test face images as

m′=1N⁢∑i=1N⁢xi′,
where x′irepresents an i-th test face image vector having a size M′, where i is an integer; (d) calculating a mean vector of all training face images as

m=1N⁢∑i=1N⁢xi,
where xirepresents an i-th training face image vector having a size M; and (e) calculating a total scatter matrix STas

ST=∑k=1N⁢(xk-m)⁢(xk-m)T,
where k is an integer.

The method proceeds further by: (f) calculating a set of orthonormal training image vectors wi, wherein the set of orthonormal vectors wiare eigenvectors of a covariance matrix C=PTP, where P is a matrix composed of mean centered images mias column vectors, placed side by side; (g) forming a projection matrix W of order (M×T) from the set of orthonormal training image vectors wi, where T represents the total number of orthonormal training image vectors wi; (h) calculating a first projection matrix WPCAas WPCA=argWmax|WTSTW|; and (i) calculating a membership grade of a j-th training image vector in the i-th class μijas

μij=α+β⁢⁢(nijk)
if i is the same as a label of the j-th pattern, and as

μij=β⁢⁢(nijk)
if i is not the same as the label of the j-th pattern, where nijrepresents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th training image vector, and wherein β=1−α, and α represents an offset in membership grading assigned to a training vector in its class.

The method continues by: (j) optimizing a using a genetic algorithm in order to minimize recognition error; (k) calculating a mean of all training vectors belonging to the l-th class as

m_l=∑j=1N⁢μijp⁢xj∑j=1N⁢μijp,
where l is an integer; (l) calculating a between-class scatter matrix SBand a within-class scatter matrix SWas

SB=∑i=1C⁢∑j=1N⁢μijp⁡(m_l-m)·(m_l-m)T
and

SW=∑i=1C⁢∑xk∈Xi⁢μijp⁡(xi-m_l)·(xi-m_l)T,
respectively, where Xirepresents a set of training samples belonging to the i-th class, xkis the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier which is a constant controlling influence of fuzzy membership degree; (m) calculating a second projection matrix WLDAas

WLDA=arg⁢⁢maxW⁢⁢WT⁢SB⁢WWT⁢SW⁢W;
(n) calculating a total transformation matrix WTas WT=WLDAT·PCAT; (o) calculating a set of test feature vectors y′kas y′k=WTx′k; (p) calculating a set of training feature vectors ykas yk=WTxk; (q) calculating a Euclidean distance between each of the test feature vectors y′kand each of the training feature vectors yk; and (r) calculating a classification based upon the calculated Euclidean distances.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present method of performing facial recognition using a genetic algorithm-modified fuzzy linear discriminant analysis modifies the LDA method and the Fuzzy Fisherface methods, described above, by calculating the membership function of the training vectors, which was used above in equation (12) to calculate the mean, and which was also used in equations (13) and (14) to calculate the scatter matrices, by using equation (11). Since the grade of membership is calculated in the Fuzzy Fisherface method by weighting the contribution of the k-nearest neighbor vectors, the dominant membership is assigned an offset of 0.51, ensuring the dominant membership remains intact.

It should be noted that it is possible that certain vectors belonging to different classes are close to each other, even after projection, because the higher order dependencies are not addressed by the PCA and LDA methods. The LDA relies on the assumption that the face image classes are homoscedastic; i.e., the class covariance matrices are presumed to be identical. However, in the domain of face recognition, one never knows in advance the underlying distributions for the different classes. Therefore, the value of the offset in assigning the membership grades will have an effect on the performance of the classification and, thus, on accuracy and recognition rate. The present method improves the parameters of the membership function by setting up the problem for optimizing the parameters α and β, as follows:

Further, the number of k-nearest neighbors taken into consideration while calculating the membership grades (i.e., the value of k in equation (15)) also has an impact on the optimal value of α. Therefore, the best value of k is also searched using the genetic algorithm, together with α. These values of α and k are used to calculate the membership grades of the training vectors and to calculate the mean and scatter matrices using equations (12), (13) and (14), respectively.

The mean and scatter matrices are used to find the optimized projection matrix W, as in equation (8) above. When an unknown test image vector is to be recognized, it is first projected using the projection matrix W and is assigned the membership grade of the training vector nearest to it in the projected subspace. This is referred to as “binary classification”. Thus, the unknown image is classified as belonging to the class in which its nearest neighbor has the highest membership degree.

Experimentally, in another classification, the membership grade of the test vector was also assigned from the k-nearest training vectors neighbors using equation (11). Binary classification (i.e., k=1) was then used for the class assignment of the test image vectors in all experiments, as it provided the least recognition error, as shown inFIG. 3.

The present method of performing facial recognition using a genetic algorithm-modified fuzzy linear discriminant analysis can be summarized by the following set of steps: (a) establishing a set of N test face images, where N is a non-zero, positive integer; (b) establishing a set of N training face images; (c) calculating a mean vector of all test face images as

m′=1N⁢∑i=1N⁢xi′,
where x′irepresents an i-th test face image vector having a size M′, where i is an integer; (d) calculating a mean vector of all training face images as

m=1N⁢∑i=1N⁢xi,
where xirepresents an i-th training face image vector having a size M; and (e) calculating a total scatter matrix STas

ST=∑k=1N⁢(xk-m)⁢(xk-m)T,
where k is an integer.

The method proceeds further by: (f) calculating a set of orthonormal vectors wi, wherein the set of test image orthonormal vectors wiare eigenvectors of a covariance matrix C=PTP, where P is a matrix composed of mean centered images mias column vectors, placed side by side; (g) forming a projection matrix W of order (M×T) from the set of orthonormal training image vectors wi, where T represents the total number of orthonormal training image vectors wi; (h) calculating a first projection matrix WPCAas WPCA=argWmax|WTSTW|; and (i) calculating a membership grade of a j-th training image vector in the i-th class μijas

μij=α+β⁢⁢(nijk)
if i is the same as a label of the j-th pattern, and as

μij=β⁢⁢(nijk)
if i is not the same as the label of the j-th pattern, where nijrepresents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th training image vector, and wherein β=1−α, and α represents an offset in membership grading assigned to a training vector in its class.

The method continues by: (j) optimizing a using a genetic algorithm in order to minimize recognition error; (k) calculating a mean of all training vectors belonging to the l-th class as

m_l=∑j=1N⁢μijp⁢xj∑j=1N⁢μijp,
where l is an integer; (l) calculating a between-class scatter matrix SBand a within-class scatter matrix SWas

SB=∑i=1C⁢∑j=1N⁢μijp⁡(m_l-m)·(m_l-m)T
and

SW=∑i=1C⁢∑xk∈Xi⁢μijp⁡(xi-m_l)·(xi-m_l)T,
respectively, where Xirepresents a set of training samples belonging to the i-th class, xkis the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier which is a constant controlling influence of fuzzy membership degree; (m) calculating a second projection matrix WLDAas

WLDA=arg⁢⁢maxW⁢WT⁢SB⁢WWT⁢SW⁢W;
(n) calculating a total transformation matrix WTas WT=WLDAT·PCAT; (o) calculating a set of test feature vectors y′kas y′k=WTx′k; (p) calculating a set of training feature vectors ykas yk=WTxk; (q) calculating a Euclidean distance between each of the test feature vectors y′kand each of the training feature vectors yk; and (r) calculating a classification based upon the calculated Euclidean distances.

The experimental comparisons described below were carried out in MATLAB using the AT&T Database of Faces, formerly known as the Olivetti Research Laboratory (ORL) face database. The sample set for experimental comparisons included ten different images of forty different people. In some cases, the images were taken at different times, with slight variations in light, and variations in facial expressions (such as open or closed eyes, smiling vs. non-smiling images, and varying facial features, such as glasses vs. no glasses).

During the training phase, six images of each of the forty individuals were used, totaling 240 images, and during the testing phase, four images of each of the forty persons, totaling 160 images, were used. The LDA method was first applied on the database and it performed better with a maximum number of eigenvectors of the SBmatrix. In the case of forty classes, there were a maximum of 39 eigenvectors used for projection, as shown inFIG. 4.

The experiment was then performed for the Fuzzy Fisherface method with the values of α taken in the range of 0.45 to 0.55, with a step size of 0.005, for a fixed number of k=3; i.e., three nearest neighbors were considered while calculating the membership grades of the vectors during training. The result, as shown inFIG. 5, showed that the recognition rate varies with the values of α. This provided a rationale to search for the best value of α which gives the highest recognition rate. The experiment was also performed for a fixed value of α=0.51, and varying k from 5 to 15. The result showed that the recognition rate also varies with the different number of k-nearest neighbors, as shown inFIG. 6.

Further, the fuzzy modifier parameter p, which controls the influence of the fuzzy membership degree in equations (12), (13), and (14), also showed some impact on the recognition rate. In the above experiments, the value of p was fixed at 1.FIG. 7shows the effect of the values of p in the range from 1 to 10 on the recognition rate, where α=0.51 and k=3.

The above findings encouraged the use of a genetic algorithm (GA) to search for the optimal values of α, k and p. The error rate in the recognition is the fitness function to be minimized by the genetic algorithm. The population size of the individuals for the genetic algorithm was selected as 50, with the population type as double and the number of maximum generations was set to 100. However, in most cases, the results converged before the 100thgeneration. For every new generation, the population individuals were ranked according to the fitness value. The selection was performed using the stochastic uniform function, and the crossovers of the individuals were carried out using the scattered function with 0.8 as the crossover fraction.

The genetic algorithm was first used to search for the best value of α, in the range of 0.4 to 0.7 for k=3, and was found to be 0.51, giving 2.5% error in the best case, as shown inFIG. 8A. When the search space was increased from 0.1 to 1.0, the error in the best case was found to decrease to 1.875%, with the value of α=0.302, as shown inFIG. 8B. Since the error rate varied for different values of k and α, as shown inFIGS. 5 and 6, the optimal values of α and k were searched together within the following ranges: 0<α<1 and 1≦k≦160.

The values that gave the lowest error in the recognition were found to be α=0.415 and k=141, as shown inFIG. 8C. Finally, the fuzzy modifier p was also included in the above search, for the range 1≦p≦10. The least error was found with the values of p=6.887, α=0.965 and k=62, as shown inFIG. 8D.

The experiments were performed in order to find the optimal values of α and k-nearest neighbor used to generate the fuzzy membership grade of the vectors during the training phase. These were then used to calculate the projection matrix that resulted in an improved projection and, thus, better recognition accuracy. Fuzzy k-nearest neighbor assignment used to assign the class membership to vectors during training was found to be better than the binary assignment used in classical LDA, whereas binary classification was found to result consistently in better recognition rates as compared to k-nearest neighbor classification for the test vectors.

The values of α and k found by the genetic algorithm varied for different search ranges, but the least (i.e., the best) error rate was found to be 1.875% in a number of scenarios. The improvement that resulted in the present method is due to the optimization in assigning the membership grades. The best membership function parameter for the employed database is searched through GA and, therefore, the recognition improves. The different values of α that result in the same minimum recognition error rate of 1.875% (as shown inFIGS. 8A through 8D) indicates that the error surface has multi-modal minima. The values of α found to be less than 0.5, as shown inFIGS. 8B and 8C, point out that the features of different classes are not completely discriminated by FLDA. This is possible because the method does not take into consideration the higher order dependencies of the image vectors.

The computational complexity of the present method is similar to that of the Fuzzy Fisherface (FLDA) method, but more time is consumed by the genetic algorithm to perform the search. This can be reduced by reducing the number of generations used in GA because the fitness function converges in fewer generations, as is evident fromFIGS. 8A-8D. The best (i.e., the least) error rates obtained by the PCA, LDA, FLDA and the present method are compared inFIG. 9.

The bar graph ofFIG. 10shows the comparison with some of the error rates reported in the literature obtained using other methods on the same ORL database. It should be noted that the error rate for the Fuzzy Fisherface (FLDA) method is for a case of similar division of the ORL database as in the present method, i.e., six images per person for training, and four images per person for testing.

It should be understood that the calculations may be performed by any suitable computer system, such as that diagrammatically shown inFIG. 1. Data is entered into the system100via any suitable type of user interface116, and may be stored in memory112, which may be any suitable type of computer readable and programmable memory. Calculations are performed by a processor114, which may be any suitable type of computer processor, and may be displayed to the user on display118, which may be any suitable type of computer display.

The processor114may be associated with, or incorporated into, any suitable type of computing device, for example, a personal computer or a programmable logic controller. The display118, the processor114, the memory112and any associated computer readable recording media are in communication with one another by any suitable type of data bus, as is well known in the art.

Examples of computer-readable recording media include a magnetic recording apparatus, an optical disk, a magneto-optical disk, and/or a semiconductor memory (for example, RAM, ROM, etc.). Examples of magnetic recording apparatus that may be used in addition to memory112, or in place of memory112, include a hard disk device (HDD), a flexible disk (FD), and a magnetic tape (MT). Examples of the optical disk include a DVD (Digital Versatile Disc), a DVD-RAM, a CD-ROM (Compact Disc-Read Only Memory), and a CD-R (Recordable)/RW.