# A Novel Face Recognition Approach Based on Two-Step Test Sample Representation

Authors: Zun-xiong Liu; Zhi-qiang Huang; Heng Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The two-step test sample representation method is proposed for face recognition. It first identifiesk “representative” samples from each category training samples for the test sample then produces a weighted sum of all the “representative” samples that well approximates the test sample. This method assigns the test sample to the class whose training samples have the smallest deviation from the test sample. As the method proposed in this paper is able to reduce the side-effect of the other training samples that are very “far” from the test sample on the recognition decision of the test sample, the high recognition rates can be obtained.


---

## Body

## 1. Introduction

Face recognition has attracted much attention in the computer-vision-related fields which has a wide range of applications including identity authentication, access control, and surveillance [1–3]. The K nearest neighbor (KNN) is a simple and popular machine learning approach for classification and has been widely used for face recognition [4–6]. The basic idea of KNN is to use the K nearest neighbors of the test sample from the training set to classify the test sample. In particular, it assigns the test sample to the class which has the more nearest neighbors for the test sample than all the other classes. The principle of nearest neighbor classification was first proposed by Skellam [7], it takes the ratio of expected and observed mean value of the nearest neighbor distances to determine whether a data set is clustered or not.The following works can be viewed as recent improvements of KNN. In 1999, Li and Lu proposed the nearest feature line (NFL) classifier [8]. Actually, NFL is a method that exploits virtue training samples to improve KNN. In other words, NFL treats the line between two sample points from the same class as the so-called feature line and views all points on feature lines as virtue training samples. Suppose that some certain class has n training samples, there are n(n-1)/2 feature lines with it. Chien and Wu [9] proposed the nearest feature plane (NFP) and the nearest feature space (NFS) classifiers. With n training samples from some certain class, there are n(n-1)(n-2)/6 feature planes and one feature space, respectively. In 2004, Zheng et al. [10] proposed both the nearest neighbor line (NNL) and the nearest neighbor plane (NNP) classifiers. Moreover, Orozco-Alzate and Castellanos-Domínguez [11] proposed the k nearest feature line (KNFL) and the k nearest feature plane (KNFP) classifiers based on the k nearest feature lines and the k nearest feature planes, respectively. Du and Chen [12] proposed the rectified nearest feature line segment (RNFLS) classifier. Fu et al. [13] presented the k-nearest-neighbor simplex (KNNS) classifier where k is the number of vertexes in a simplex. Moreover, Majumdar [14] proposed the nearest subspace (NS) classifier.There exists some differences among the nearest-neighbor-based classifiers. The first difference is that they have different-dimensional coefficient vectors. Specifically, the dimensionalities of the coefficient vectors in NFL, NFP, and NFS are 2, 3, andn, respectively. n stands for the number of training samples of the given class. The second difference is that the coefficients of some approaches satisfy the constraint that their sum are equal to one whereas the other methods do not. In particular, NFL is subject to this constraint, but NFP and NFS are not. The third difference is that all the coefficients should be nonnegative with RNFLS and KNNS, whereas NFL, NFP, and NFS do not have the requirement.Recently, the sparse representation-based classification (SRC) [15] has been proposed and can be considered as an improvement to KNN. SRC treats a weighted sum of all the training samples from a class as the center of this class and classifies the test sample into the class whose center is the nearest to the test sample. In SRC, the weights can be learned using some algorithms. Moreover, SRC outperforms most of the state-of-the-art facial classifiers.The common characteristic of the classifiers presented earlier is that all of them use the deviation between the test sample and the linear combination of the training samples from some certain class to classify the test sample. They assign the test sample to the class that has the smallest deviation. Different from the other improvements of KNN, SRC exploits a sparse linear combination of all the training samples to represent the test sample. “Sparse” means that some coefficients of the linear combination are equal or close to zeros.In this paper, we propose the two-step test sample representation method for face recognition. This method first identifiesk “representative” samples from every category training samples, the representative samples are more similar to the test sample. The method also exploits a linear combination of all the “representative” samples from all the classes to represent and classify the test sample. Here, the proposed method is employed for face recognition, and the experiments are conducted with different face databases.The remainder of this paper is organized as follows. Section2 overviews previous improvements of KNN. Section 3 presents the proposed method. Section 4 shows the experimental results. Finally, Section 5 summarizes the paper.


## 2. Improvements of KNN

### 2.1. Nearest Feature Line

With the nearest feature line (NFL), any two feature points of the same class are generalized by the feature line (FL) passing through the two points. So more variation of available samples can be captured, and the classification is based on the nearest distance from the query point to each FL. LetX(i)=[X1(i),…,XNi(i)]∈Rd×Ni denote the matrix composed of all training samples from the ith class, i=1,…,c (c is the number of class). Y∈Rd×1 is a given test sample. For each pair of training samples Xp(i) and Xq(i) from the ith class, there exist feature lines Xp(i)Xq(i) defined as
(1)Xp(i)Xq(i)={X∣X=αXp(i)+(1-α)Xq(i),α∈R}.
The NFL classifier defines the distance between Y and feature lines Xp(i)Xq(i) as
(2)d(Y,Xp(i)Xq(i))=minα∈R∥Y-αXp(i)-(1-α)Xq(i)∥2.
The distance between Y and the ith class is calculated using
(3)dLi(Y)=min1≤p<q≤Nid(Y,Xp(i)Xq(i)).
If l=argmin1≤i≤cdLi(Y), then the NFL classifier assigns Y to the lth class. l is one element of the set of the class labels, that is, {1,…,c}.It is clear that the NFL classifier indeed evaluates the deviation between a linear combination of two training samples from the same class and the test sample, and the smallest deviations generated from all the classes can be obtained. If the smallest deviation of a class is smaller than those of all other classes, then the NFL classifier assigns the test sample into this class.


### 2.2. Nearest Feature Space

The NFS classifier first defines the feature space spanned by all training samples from theith class using
(4)Si={X∣X=∑j=1NiαjXj(i),αj∈R,j=1,…,Ni}.
This classifier takes the minimum value of the distances between test sample Y and the elements of Si as the distance between Y and the ith class. That is, the distance between Y and the ith class is calculated using
(5)dSi(Y)=minαj∈R,j=1,…,Ni∥Y-∑j=1NiαjXj(i)∥2.
If l=argmin1≤i≤cdSi(Y), then the NFS classifier assigns Y to the lth class.


### 2.3. Sparse Representation-Based Classification

LetX=[X(1),…,X(c)]∈Rd×N stands for the matrix consisting of all training samples, and let N be the number of training samples. Let Y be the test sample. SRC aims to use a sparse linear combination of all training samples to represent Y. In other words, if α denotes the coefficient vector of the sparse linear combination, SRC has the following objective function:
(6)minα∥α∥1subjectto∥Y-Xα∥2≤ε,
where ε is a user-defined small positive constant. Let α^ be the solution of α. The distance between the test sample Yand the ith class is calculated using
(7)di(Y)=∥Y-Xδi(α)∥2,
where δi(α^)∈RN×1 is a vector whose nonzero entries are the entries in α^ that are associated with the ith class, i=1,…,c. If l=argmin1≤i≤cdi(Y), SRC assigns test sample Y to the lth class.


## 2.1. Nearest Feature Line

With the nearest feature line (NFL), any two feature points of the same class are generalized by the feature line (FL) passing through the two points. So more variation of available samples can be captured, and the classification is based on the nearest distance from the query point to each FL. LetX(i)=[X1(i),…,XNi(i)]∈Rd×Ni denote the matrix composed of all training samples from the ith class, i=1,…,c (c is the number of class). Y∈Rd×1 is a given test sample. For each pair of training samples Xp(i) and Xq(i) from the ith class, there exist feature lines Xp(i)Xq(i) defined as
(1)Xp(i)Xq(i)={X∣X=αXp(i)+(1-α)Xq(i),α∈R}.
The NFL classifier defines the distance between Y and feature lines Xp(i)Xq(i) as
(2)d(Y,Xp(i)Xq(i))=minα∈R∥Y-αXp(i)-(1-α)Xq(i)∥2.
The distance between Y and the ith class is calculated using
(3)dLi(Y)=min1≤p<q≤Nid(Y,Xp(i)Xq(i)).
If l=argmin1≤i≤cdLi(Y), then the NFL classifier assigns Y to the lth class. l is one element of the set of the class labels, that is, {1,…,c}.It is clear that the NFL classifier indeed evaluates the deviation between a linear combination of two training samples from the same class and the test sample, and the smallest deviations generated from all the classes can be obtained. If the smallest deviation of a class is smaller than those of all other classes, then the NFL classifier assigns the test sample into this class.


## 2.2. Nearest Feature Space

The NFS classifier first defines the feature space spanned by all training samples from theith class using
(4)Si={X∣X=∑j=1NiαjXj(i),αj∈R,j=1,…,Ni}.
This classifier takes the minimum value of the distances between test sample Y and the elements of Si as the distance between Y and the ith class. That is, the distance between Y and the ith class is calculated using
(5)dSi(Y)=minαj∈R,j=1,…,Ni∥Y-∑j=1NiαjXj(i)∥2.
If l=argmin1≤i≤cdSi(Y), then the NFS classifier assigns Y to the lth class.


## 2.3. Sparse Representation-Based Classification

LetX=[X(1),…,X(c)]∈Rd×N stands for the matrix consisting of all training samples, and let N be the number of training samples. Let Y be the test sample. SRC aims to use a sparse linear combination of all training samples to represent Y. In other words, if α denotes the coefficient vector of the sparse linear combination, SRC has the following objective function:
(6)minα∥α∥1subjectto∥Y-Xα∥2≤ε,
where ε is a user-defined small positive constant. Let α^ be the solution of α. The distance between the test sample Yand the ith class is calculated using
(7)di(Y)=∥Y-Xδi(α)∥2,
where δi(α^)∈RN×1 is a vector whose nonzero entries are the entries in α^ that are associated with the ith class, i=1,…,c. If l=argmin1≤i≤cdi(Y), SRC assigns test sample Y to the lth class.


## 3. The Proposed Method

### 3.1. Description of the Proposed Method

The proposed method is composed of two steps. The first step determinesk “representative” training samples from each category for the test sample. The c classes will have k*c “representative” samples in total. The second step represents the test sample via a linear combination of the k*c representative samples. Let P1,…,Pkc be all the k*c representative samples of the c classes, the test sample can be represented with the linear combination of the k*c representative samples. Finally, the second step calculates the deviation between the test sample and the linear combination of each class and assigns the test sample to the class that has the minimum deviation.In the first step, the test sample is represented with a linear combination of all the training samples of theith class (i=1,…,c). The coefficients of the obtained liner combination will be used to compute the deviation between the test sample and the ith class (i=1,…,c). It then computes the deviation between the test sample and the linear combination of arbitrary k  (k<ni) training samples of the ith class (i=1,…,c), that is, the deviation between the test sample and the ith class.N
i training samples from the ith class is formulated as a matrix X(i)=[X1(i),…,XNi(i)], the test sample Y can be approximated as
(8)Y=X(i)A(i).A
(
i
) is the combination coefficients of the ith class samples which represent the test sample, can be solved using A^(i)=(X(i)TX(i)+λI)-1X(i)Ty. λ and I are a small positive constant and the identity matrix, respectively. Let z1,…,zk denote arbitrarily k samples of X1(i),…,XNi(i), the deviation between the test sample and z1,…,zk can be calculated using
(9)di(z1,…,zk)=∥y-∑g=1kzgb^g(i)∥,b^1(i)⋯b^k(i) are k coefficients of {a^1(i)⋯a^Nii} related to z1,…,zk, respectively. di(z1,…,zk) is the so-called deviation between the test sample and some ith class representation. If k training samples are selected from all Ni training samples of the ith class, there will be (Ni(Ni-1)⋯(Ni-k+1))/k! possible cases. Also, there will be (Ni(Ni-1)⋯(Ni-k+1))/k! different di. For a class, the k training samples that produce the minimum di(z1,…,zk) are selected as the “representative” samples of the ith class for the test sample. In the experimental section, we also perform a classification based on the first step of the proposed method as follows: the minimum deviation of every class from the test sample can be computed, and the test sample is assigned to the class with which the minimum deviation is the smallest among all the classes.After thek*c representative samples are determined, the test sample is approximated with them as
(10)Y=∑j=1k*cηjPj,
where P=[P1,…,Pk*c] and η=[η1,…,ηk*c]T. The solution of (10) is obtained with
(11)η^=[η^1,…,η^k*c]T=(PTP+γI)-1PTY,I is the identity matrix, and γ stands for a small positive constant. The final deviation between the test sample and the ith class is calculated using
(12)di=∥Y-Giη^i∥,
where η^i=[η^(i-1)k+1,…,η^(i-1)k+k]T,  Gi=[P(i-1)k+1,…,P(i-1)k+k] is composed of the k representative samples of the ith class. If h=argminidi, then the test sample is assigned to the hth class.


### 3.2. Insight into the Proposed Method

#### 3.2.1. Why the Proposed Method Is Reasonable

This section will show why the proposed method is reasonable. The first step of the proposed method is indeed a step to identify thek “representative” samples that are the most similar to the test sample from each class. Then, only the training samples that are similar to the test sample are used to represent and classify the test sample. It is known that the face images of the same subject have much variation owing to the varying pose, facial expression, and illumination [16, 17], and the training samples dissimilar to the test sample might be or not be from the genuine subject of the test sample. As a result, it is not feasible to use the “dissimilar” training samples to distinguish which class the test sample is truly from. On the contrary, it is very helpful to use only the training samples that are similar to the test sample for classification.The second step of the proposed method also enables all the classes to represent the test sample in a competitive way. Actually, if one class contributes much, that is, has a small deviation in representing the test sample, the other classes will contributes less. The experiments show that the genuine class of the test sample usually has the smallest deviation with the test sample; thus, the proposed method allows the test sample to be classified with a high accuracy.The first step is somewhat able to remove the “outlier” of a class, that is, the training samples that are very close to other classes. Thus, it is useful for obtaining a high accuracy. Figures1, 2, and 3 show a test sample from the AR face database and the classification result of our method on this test sample (the occluded image in the first column is the test sample). In these three figures, the first image always stands for the same test sample. In this example, our method takes the first six face images and the remaining face images of each subject as training and test samples, respectively, and k is set to 3. Figure 1 shows a sample and its 34 neighbors from the set of training samples (these neighbors were determined using the Euclidean distance between the training sample and test sample). Among these 34 neighbors only the last one is from the same subject as the test sample, and the second to sixth images are the first five neighbors of the test sample.Figure 1
One test sample (the first image) and its 34 neighbors from the set of training samples.Figure 2
The three training samples from the first three classes closest to the test sample obtained using the proposed method.Figure 3
The three training samples from the first three classes closest to the test sample obtained using the first step of our method (the test sample misclassified only with them).Figure2 shows that the second step of our method correctly assigns the test sample to its genuine class, the second to fourth images are the three training samples of the first closest class to the test sample, the fifth to seventh images and eighth to tenth images are the three training samples of the second and third classes that are the closest to the test sample, respectively. On the other hand, Figure 3 shows that if the results from the first step of our method are directly employed to perform classification, the test sample is misclassified. The three training samples form three closest class to the test sample are also presented, the genuine class of the test sample is only the seventeenth class among all the classes that are “close” to the test sample. In other words, if the test sample is assigned to the class with the smallest di(z1,…,zk) (defined in (9)), it will be misclassified.Figures4 and 5, respectively, show the difference between the same test sample as shown in Figures 1, 2, and 3 and its representation results obtained using the first and second steps of our method. In these two figures, the horizontal and vertical axes show the number of class (class label) and difference, respectively. The genuine class label of the test sample is 3. Figure 5 shows that in terms of the representation result obtained using the second step, the test sample has the smallest deviation from its representation result generated from the third class. As a result, the second step will correctly assign the test sample to the third class. However, Figure 4 shows that the test sample is assigned to the fifty-fourth class only with the deviations from the first step of our method, and the class that has the minimum deviation is not the genuine class (the genuine class is the third class).Figure 4
Deviation between the test sample and its representation result obtained using the first step of our method.Figure 5
Deviation between the test sample and its representation result obtained using the second step of our method.Differing from conventionall1-norm-based sparse representation method, our method is an l2-norm-based. The l2-norm based representation method proposed by Xu et al. not only is computationally much more efficient than conventional sparse representation methods but also can lead to a higher face recognition accuracy [18].


#### 3.2.2. Explore the Relationship between the Accuracy and the Representation Error

We will show whether the accuracy is directly related to the representation error or not. As shown earlier, if the representation result generated from a class has the minimum deviation from the test sample, the test sample is assigned to this class. LetY^=Pη^, e=||Y-Y^||, e is the so-called representation error. If the number of the available training samples is equal to or greater than the dimensionality of the sample vector, the representation error of the test sample can be zero. Under the other conditions, the more the available training samples the lower the representation error. In the real-world face recognition applications, the condition that the number of the available training samples is equal to or greater than the dimensionality of the sample vector is usually not satisfied. Nevertheless, the experiment shows that a lower representation error usually does not lead to a higher recognition accuracy. Moreover, our method usually has a high representation error, whereas it obtains a high recognition accuracy. Figure 6 shows the representation errors of the first 300 test samples in the case where the first four face images of each subject in the AR database are used as training samples and the remaining face images are used as test samples. It is clear that k=4 obtains a lower representation error than k=2; however, k=2 obtains a higher classification accuracy. Thus, the representation error is not a good index of the accuracy. However, the accuracy is directly related to the deviation between the test sample and the representation result of the genuine class of the test sample. Moreover, it seems that the smaller the deviation, the better the classification performance.Figure 6
Representation errors of the first 300 test samples in the AR database.k=4 means that all the available training samples were used for training. k=2 means that the second step of our method uses 2 representative samples from each subject.


## 3.1. Description of the Proposed Method

The proposed method is composed of two steps. The first step determinesk “representative” training samples from each category for the test sample. The c classes will have k*c “representative” samples in total. The second step represents the test sample via a linear combination of the k*c representative samples. Let P1,…,Pkc be all the k*c representative samples of the c classes, the test sample can be represented with the linear combination of the k*c representative samples. Finally, the second step calculates the deviation between the test sample and the linear combination of each class and assigns the test sample to the class that has the minimum deviation.In the first step, the test sample is represented with a linear combination of all the training samples of theith class (i=1,…,c). The coefficients of the obtained liner combination will be used to compute the deviation between the test sample and the ith class (i=1,…,c). It then computes the deviation between the test sample and the linear combination of arbitrary k  (k<ni) training samples of the ith class (i=1,…,c), that is, the deviation between the test sample and the ith class.N
i training samples from the ith class is formulated as a matrix X(i)=[X1(i),…,XNi(i)], the test sample Y can be approximated as
(8)Y=X(i)A(i).A
(
i
) is the combination coefficients of the ith class samples which represent the test sample, can be solved using A^(i)=(X(i)TX(i)+λI)-1X(i)Ty. λ and I are a small positive constant and the identity matrix, respectively. Let z1,…,zk denote arbitrarily k samples of X1(i),…,XNi(i), the deviation between the test sample and z1,…,zk can be calculated using
(9)di(z1,…,zk)=∥y-∑g=1kzgb^g(i)∥,b^1(i)⋯b^k(i) are k coefficients of {a^1(i)⋯a^Nii} related to z1,…,zk, respectively. di(z1,…,zk) is the so-called deviation between the test sample and some ith class representation. If k training samples are selected from all Ni training samples of the ith class, there will be (Ni(Ni-1)⋯(Ni-k+1))/k! possible cases. Also, there will be (Ni(Ni-1)⋯(Ni-k+1))/k! different di. For a class, the k training samples that produce the minimum di(z1,…,zk) are selected as the “representative” samples of the ith class for the test sample. In the experimental section, we also perform a classification based on the first step of the proposed method as follows: the minimum deviation of every class from the test sample can be computed, and the test sample is assigned to the class with which the minimum deviation is the smallest among all the classes.After thek*c representative samples are determined, the test sample is approximated with them as
(10)Y=∑j=1k*cηjPj,
where P=[P1,…,Pk*c] and η=[η1,…,ηk*c]T. The solution of (10) is obtained with
(11)η^=[η^1,…,η^k*c]T=(PTP+γI)-1PTY,I is the identity matrix, and γ stands for a small positive constant. The final deviation between the test sample and the ith class is calculated using
(12)di=∥Y-Giη^i∥,
where η^i=[η^(i-1)k+1,…,η^(i-1)k+k]T,  Gi=[P(i-1)k+1,…,P(i-1)k+k] is composed of the k representative samples of the ith class. If h=argminidi, then the test sample is assigned to the hth class.


## 3.2. Insight into the Proposed Method

### 3.2.1. Why the Proposed Method Is Reasonable

This section will show why the proposed method is reasonable. The first step of the proposed method is indeed a step to identify thek “representative” samples that are the most similar to the test sample from each class. Then, only the training samples that are similar to the test sample are used to represent and classify the test sample. It is known that the face images of the same subject have much variation owing to the varying pose, facial expression, and illumination [16, 17], and the training samples dissimilar to the test sample might be or not be from the genuine subject of the test sample. As a result, it is not feasible to use the “dissimilar” training samples to distinguish which class the test sample is truly from. On the contrary, it is very helpful to use only the training samples that are similar to the test sample for classification.The second step of the proposed method also enables all the classes to represent the test sample in a competitive way. Actually, if one class contributes much, that is, has a small deviation in representing the test sample, the other classes will contributes less. The experiments show that the genuine class of the test sample usually has the smallest deviation with the test sample; thus, the proposed method allows the test sample to be classified with a high accuracy.The first step is somewhat able to remove the “outlier” of a class, that is, the training samples that are very close to other classes. Thus, it is useful for obtaining a high accuracy. Figures1, 2, and 3 show a test sample from the AR face database and the classification result of our method on this test sample (the occluded image in the first column is the test sample). In these three figures, the first image always stands for the same test sample. In this example, our method takes the first six face images and the remaining face images of each subject as training and test samples, respectively, and k is set to 3. Figure 1 shows a sample and its 34 neighbors from the set of training samples (these neighbors were determined using the Euclidean distance between the training sample and test sample). Among these 34 neighbors only the last one is from the same subject as the test sample, and the second to sixth images are the first five neighbors of the test sample.Figure 1
One test sample (the first image) and its 34 neighbors from the set of training samples.Figure 2
The three training samples from the first three classes closest to the test sample obtained using the proposed method.Figure 3
The three training samples from the first three classes closest to the test sample obtained using the first step of our method (the test sample misclassified only with them).Figure2 shows that the second step of our method correctly assigns the test sample to its genuine class, the second to fourth images are the three training samples of the first closest class to the test sample, the fifth to seventh images and eighth to tenth images are the three training samples of the second and third classes that are the closest to the test sample, respectively. On the other hand, Figure 3 shows that if the results from the first step of our method are directly employed to perform classification, the test sample is misclassified. The three training samples form three closest class to the test sample are also presented, the genuine class of the test sample is only the seventeenth class among all the classes that are “close” to the test sample. In other words, if the test sample is assigned to the class with the smallest di(z1,…,zk) (defined in (9)), it will be misclassified.Figures4 and 5, respectively, show the difference between the same test sample as shown in Figures 1, 2, and 3 and its representation results obtained using the first and second steps of our method. In these two figures, the horizontal and vertical axes show the number of class (class label) and difference, respectively. The genuine class label of the test sample is 3. Figure 5 shows that in terms of the representation result obtained using the second step, the test sample has the smallest deviation from its representation result generated from the third class. As a result, the second step will correctly assign the test sample to the third class. However, Figure 4 shows that the test sample is assigned to the fifty-fourth class only with the deviations from the first step of our method, and the class that has the minimum deviation is not the genuine class (the genuine class is the third class).Figure 4
Deviation between the test sample and its representation result obtained using the first step of our method.Figure 5
Deviation between the test sample and its representation result obtained using the second step of our method.Differing from conventionall1-norm-based sparse representation method, our method is an l2-norm-based. The l2-norm based representation method proposed by Xu et al. not only is computationally much more efficient than conventional sparse representation methods but also can lead to a higher face recognition accuracy [18].


### 3.2.2. Explore the Relationship between the Accuracy and the Representation Error

We will show whether the accuracy is directly related to the representation error or not. As shown earlier, if the representation result generated from a class has the minimum deviation from the test sample, the test sample is assigned to this class. LetY^=Pη^, e=||Y-Y^||, e is the so-called representation error. If the number of the available training samples is equal to or greater than the dimensionality of the sample vector, the representation error of the test sample can be zero. Under the other conditions, the more the available training samples the lower the representation error. In the real-world face recognition applications, the condition that the number of the available training samples is equal to or greater than the dimensionality of the sample vector is usually not satisfied. Nevertheless, the experiment shows that a lower representation error usually does not lead to a higher recognition accuracy. Moreover, our method usually has a high representation error, whereas it obtains a high recognition accuracy. Figure 6 shows the representation errors of the first 300 test samples in the case where the first four face images of each subject in the AR database are used as training samples and the remaining face images are used as test samples. It is clear that k=4 obtains a lower representation error than k=2; however, k=2 obtains a higher classification accuracy. Thus, the representation error is not a good index of the accuracy. However, the accuracy is directly related to the deviation between the test sample and the representation result of the genuine class of the test sample. Moreover, it seems that the smaller the deviation, the better the classification performance.Figure 6
Representation errors of the first 300 test samples in the AR database.k=4 means that all the available training samples were used for training. k=2 means that the second step of our method uses 2 representative samples from each subject.


## 3.2.1. Why the Proposed Method Is Reasonable

This section will show why the proposed method is reasonable. The first step of the proposed method is indeed a step to identify thek “representative” samples that are the most similar to the test sample from each class. Then, only the training samples that are similar to the test sample are used to represent and classify the test sample. It is known that the face images of the same subject have much variation owing to the varying pose, facial expression, and illumination [16, 17], and the training samples dissimilar to the test sample might be or not be from the genuine subject of the test sample. As a result, it is not feasible to use the “dissimilar” training samples to distinguish which class the test sample is truly from. On the contrary, it is very helpful to use only the training samples that are similar to the test sample for classification.The second step of the proposed method also enables all the classes to represent the test sample in a competitive way. Actually, if one class contributes much, that is, has a small deviation in representing the test sample, the other classes will contributes less. The experiments show that the genuine class of the test sample usually has the smallest deviation with the test sample; thus, the proposed method allows the test sample to be classified with a high accuracy.The first step is somewhat able to remove the “outlier” of a class, that is, the training samples that are very close to other classes. Thus, it is useful for obtaining a high accuracy. Figures1, 2, and 3 show a test sample from the AR face database and the classification result of our method on this test sample (the occluded image in the first column is the test sample). In these three figures, the first image always stands for the same test sample. In this example, our method takes the first six face images and the remaining face images of each subject as training and test samples, respectively, and k is set to 3. Figure 1 shows a sample and its 34 neighbors from the set of training samples (these neighbors were determined using the Euclidean distance between the training sample and test sample). Among these 34 neighbors only the last one is from the same subject as the test sample, and the second to sixth images are the first five neighbors of the test sample.Figure 1
One test sample (the first image) and its 34 neighbors from the set of training samples.Figure 2
The three training samples from the first three classes closest to the test sample obtained using the proposed method.Figure 3
The three training samples from the first three classes closest to the test sample obtained using the first step of our method (the test sample misclassified only with them).Figure2 shows that the second step of our method correctly assigns the test sample to its genuine class, the second to fourth images are the three training samples of the first closest class to the test sample, the fifth to seventh images and eighth to tenth images are the three training samples of the second and third classes that are the closest to the test sample, respectively. On the other hand, Figure 3 shows that if the results from the first step of our method are directly employed to perform classification, the test sample is misclassified. The three training samples form three closest class to the test sample are also presented, the genuine class of the test sample is only the seventeenth class among all the classes that are “close” to the test sample. In other words, if the test sample is assigned to the class with the smallest di(z1,…,zk) (defined in (9)), it will be misclassified.Figures4 and 5, respectively, show the difference between the same test sample as shown in Figures 1, 2, and 3 and its representation results obtained using the first and second steps of our method. In these two figures, the horizontal and vertical axes show the number of class (class label) and difference, respectively. The genuine class label of the test sample is 3. Figure 5 shows that in terms of the representation result obtained using the second step, the test sample has the smallest deviation from its representation result generated from the third class. As a result, the second step will correctly assign the test sample to the third class. However, Figure 4 shows that the test sample is assigned to the fifty-fourth class only with the deviations from the first step of our method, and the class that has the minimum deviation is not the genuine class (the genuine class is the third class).Figure 4
Deviation between the test sample and its representation result obtained using the first step of our method.Figure 5
Deviation between the test sample and its representation result obtained using the second step of our method.Differing from conventionall1-norm-based sparse representation method, our method is an l2-norm-based. The l2-norm based representation method proposed by Xu et al. not only is computationally much more efficient than conventional sparse representation methods but also can lead to a higher face recognition accuracy [18].


## 3.2.2. Explore the Relationship between the Accuracy and the Representation Error

We will show whether the accuracy is directly related to the representation error or not. As shown earlier, if the representation result generated from a class has the minimum deviation from the test sample, the test sample is assigned to this class. LetY^=Pη^, e=||Y-Y^||, e is the so-called representation error. If the number of the available training samples is equal to or greater than the dimensionality of the sample vector, the representation error of the test sample can be zero. Under the other conditions, the more the available training samples the lower the representation error. In the real-world face recognition applications, the condition that the number of the available training samples is equal to or greater than the dimensionality of the sample vector is usually not satisfied. Nevertheless, the experiment shows that a lower representation error usually does not lead to a higher recognition accuracy. Moreover, our method usually has a high representation error, whereas it obtains a high recognition accuracy. Figure 6 shows the representation errors of the first 300 test samples in the case where the first four face images of each subject in the AR database are used as training samples and the remaining face images are used as test samples. It is clear that k=4 obtains a lower representation error than k=2; however, k=2 obtains a higher classification accuracy. Thus, the representation error is not a good index of the accuracy. However, the accuracy is directly related to the deviation between the test sample and the representation result of the genuine class of the test sample. Moreover, it seems that the smaller the deviation, the better the classification performance.Figure 6
Representation errors of the first 300 test samples in the AR database.k=4 means that all the available training samples were used for training. k=2 means that the second step of our method uses 2 representative samples from each subject.


## 4. Experimental Results

### 4.1. Experiment on the Lab2 Data

The first experiment is conducted on the Lab2 database [19]. This database contains 50 subjects and 1000 visible face images. Each subject is provided with twenty face images. These images were acquired under the following four different illumination conditions: (a) the environmental illumination (referred to as “normal illumination”) condition, (b) the environmental illumination puls the illumination of the left incandescent lamp (referred to as “left illumination”), (c) the environmental illumination puls the illumination of the right incandescent lamp (referred to as “right illumination”), and (d) the environment illumination puls the illumination of the left and the right incandescent lamps (referred to as “both illumination”). The face images also have a variation in facial expression and pose. Figure 7 shows several visible face images of one subject in the Lab2 database. We used the ten visible face images captured with “both illumination” and “left illumination” of every subject as training samples and took the remaining images as test samples. Table 1 shows the experimental results of our method on the Lab2 database. Table 2 shows the experimental results of NFL, NFP, and NFS on the Lab2 database. It is shown that our method obtained much fewer classification errors than NFL, NFP, and NFS. Table 1 also illustrates that if we depend on only the first step of our method to perform classification, a higher error rate will be obtained.Table 1
Experimental results of our method on the Lab2 database.
Our method
Number of representative samples
6
7
8
9
Number of erroneously classified test samples
216
194
195
190
The first step of our method
Number of representative samples
6
7
8
9
Number of erroneously classified test samples
419
409
402
362Table 2
Experimental results of NFL,NFP,  and NFS on the Lab2 database.
Method
NFL
NFS
NFP
Number of erroneously classified test samples
319
278
289Figure 7
Some visible face images of one subject in the Lab2 database.


### 4.2. Experiments on the AR Face Database

The second experiment is conducted on the AR database [19]. The face images of this database were obtained under the condition of varying pose, facial expression, or lighting. Occluded face images are also included in the AR face database. There are 120 subjects and 3120 gray face images captured in two sessions. We resized each image to a 40 by 50 image. A series of experiments are carried out, where the first certain number of images (set to 4, 6, 8, 12, and 14, resp.) for each subject constitute the training samples, all the other images make the test samples. The number of representative samples are selected in the view of Tables 3 and 4, and the experimental results are also shown there. The table shows the comparison results with another three KNN algorithms (NFL, NFS, and NFP) on the AR database. “ER” is the abbreviation of “error rate”.Table 3
The experimental results on the AR database.
Number of training samples
4
6
8
Number of representative samples
1
2
3
4
2
3
4
2
3
4
8
ER of the first step of our method
42.69%
41.89%
41.93%
41.86%
37.12%
37.37%
37.00%
40.09%
40.19%
40.28%
40.37%
ER of our method
32.39%
32.46%
32.63%
32.46%
28.54%
28.54%
28.33%
29.17%
28.47%
28.80%
30.05%Table 4
Experimental results of our method on the AR database (complementary of Table3).
Number of training samples
12
14
Number of representative samples
2
3
4
2
3
ER of the first step of our method
33.04%
32.20%
32.20%
16.32%
13.75%
ER of our method
25.12%
24.58%
25.18%
9.86%
9.24%From Tables3, 4, and 5, it is known that our method leads to the lowest error rate than other methods. These tables also show that the first step of our method obtains a much higher error rate than the second step. Thus, the second step plays an important role in representing and classifying the test sample. This is mainly owing to that the second step evaluates the contribution of every class to representing the test sample, in a competitive way.Table 5
ER of NFL, NFS, and NFP on the AR database.
Number of training samples
4
6
8
12
14
NFL
42.12%
37.29%
40.46%
32.92%
15.97%
NFS
41.86%
37.46%
40.46%
32.02%
12.99%
NFP
41.93%
41.86%
40.09%
37.98%
17.02%


## 4.1. Experiment on the Lab2 Data

The first experiment is conducted on the Lab2 database [19]. This database contains 50 subjects and 1000 visible face images. Each subject is provided with twenty face images. These images were acquired under the following four different illumination conditions: (a) the environmental illumination (referred to as “normal illumination”) condition, (b) the environmental illumination puls the illumination of the left incandescent lamp (referred to as “left illumination”), (c) the environmental illumination puls the illumination of the right incandescent lamp (referred to as “right illumination”), and (d) the environment illumination puls the illumination of the left and the right incandescent lamps (referred to as “both illumination”). The face images also have a variation in facial expression and pose. Figure 7 shows several visible face images of one subject in the Lab2 database. We used the ten visible face images captured with “both illumination” and “left illumination” of every subject as training samples and took the remaining images as test samples. Table 1 shows the experimental results of our method on the Lab2 database. Table 2 shows the experimental results of NFL, NFP, and NFS on the Lab2 database. It is shown that our method obtained much fewer classification errors than NFL, NFP, and NFS. Table 1 also illustrates that if we depend on only the first step of our method to perform classification, a higher error rate will be obtained.Table 1
Experimental results of our method on the Lab2 database.
Our method
Number of representative samples
6
7
8
9
Number of erroneously classified test samples
216
194
195
190
The first step of our method
Number of representative samples
6
7
8
9
Number of erroneously classified test samples
419
409
402
362Table 2
Experimental results of NFL,NFP,  and NFS on the Lab2 database.
Method
NFL
NFS
NFP
Number of erroneously classified test samples
319
278
289Figure 7
Some visible face images of one subject in the Lab2 database.


## 4.2. Experiments on the AR Face Database

The second experiment is conducted on the AR database [19]. The face images of this database were obtained under the condition of varying pose, facial expression, or lighting. Occluded face images are also included in the AR face database. There are 120 subjects and 3120 gray face images captured in two sessions. We resized each image to a 40 by 50 image. A series of experiments are carried out, where the first certain number of images (set to 4, 6, 8, 12, and 14, resp.) for each subject constitute the training samples, all the other images make the test samples. The number of representative samples are selected in the view of Tables 3 and 4, and the experimental results are also shown there. The table shows the comparison results with another three KNN algorithms (NFL, NFS, and NFP) on the AR database. “ER” is the abbreviation of “error rate”.Table 3
The experimental results on the AR database.
Number of training samples
4
6
8
Number of representative samples
1
2
3
4
2
3
4
2
3
4
8
ER of the first step of our method
42.69%
41.89%
41.93%
41.86%
37.12%
37.37%
37.00%
40.09%
40.19%
40.28%
40.37%
ER of our method
32.39%
32.46%
32.63%
32.46%
28.54%
28.54%
28.33%
29.17%
28.47%
28.80%
30.05%Table 4
Experimental results of our method on the AR database (complementary of Table3).
Number of training samples
12
14
Number of representative samples
2
3
4
2
3
ER of the first step of our method
33.04%
32.20%
32.20%
16.32%
13.75%
ER of our method
25.12%
24.58%
25.18%
9.86%
9.24%From Tables3, 4, and 5, it is known that our method leads to the lowest error rate than other methods. These tables also show that the first step of our method obtains a much higher error rate than the second step. Thus, the second step plays an important role in representing and classifying the test sample. This is mainly owing to that the second step evaluates the contribution of every class to representing the test sample, in a competitive way.Table 5
ER of NFL, NFS, and NFP on the AR database.
Number of training samples
4
6
8
12
14
NFL
42.12%
37.29%
40.46%
32.92%
15.97%
NFS
41.86%
37.46%
40.46%
32.02%
12.99%
NFP
41.93%
41.86%
40.09%
37.98%
17.02%


## 5. Conclusions

The two steps of the proposed method play different and positive roles in performing classification. The first step indeed identifies the training samples which are the most similar to the test sample. This is beneficial to reduce the side-effect on classification of the other dissimilar training samples. The second step allows the “representative” samples of every class to represent the test sample in a competitive way by using a linear combination of them. This is useful for the method to better evaluate the deviation between the test sample and each class than NFL, NFP, and NS. The proposed method is easy to implement and achieve better performance than the conventional nearest feature classifiers. But the selection of all possible subsets of training samples with each class needs more computation that will bring some negative effects.



---

*Source: 895051-2013-03-19.xml*