A Kernel Sparse Representation Method Based on Virtual Samples for Use with Face Recognition

INTRODUCTION

---

FR, as one of the most active branches of biometrics, is attracting more and more attention and being used in many application domains (Zhao et al., 2003; Xu et al., 2008, 2010; Yang et al., 2005; Zhang et al., 2012). In the past decades, various methods have been proposed for FR (Wang et al., 2012a; Pishchulin et al., 2012; Kautkar et al., 2012). The Principal Component Analysis (PCA) (Moon and Phillips, 1998; Sirovich and Kirby, 1987; Kirby and Sirovich, 1990; Yang et al., 2004) and the Linear Discriminant Analysis (LDA) (Park and Savvides, 2010; Li and Yuan, 2005; Xu and Zhang, 2010) are the most popular and commonly used appearance based FR methods. PCA and LDA are also dimensionality reduction methods, which reduce the dimensionality of samples by transforming samples into a lower-dimensional space. When transforming samples into a new lower-dimensional space, the PCA transforms samples into a space where samples have the maximum variance. For the sake of ensuring the maximal separability the LDA maximizes the ratio of between-class variance to the within-class variance. Some variants of the PCA and the LDA are also used in FR (Debruyne and Verdonck, 2010; Wang et al., 2012b; Murthy and Ghosh, 2012).

Recently, another novel approach, which is named sparse representation, has been devised for FR. The classification based on sparse representation addresses classification problems by evaluating effect in expressing the testing sample of each class and the testing sample is actually expressed by a sparse linear combination of the training samples (Wright et al., 2009, 2010; Lai et al., 2011, 2012a, b; Tang et al., 2012; Zhu and Li, 2012; Yang et al., 2012a, b; Xu et al., 2011, 2012a, b; 2013; Lu et al., 2012; Zhang et al., 2011; Yin et al., 2012; Wagner et al., 2012; Lai and Jiang, 2012; Gao et al., 2010). The methods in literatures (Tang et al., 2012; Zhu and Li, 2012; Yang et al., 2012c; Xu et al., 2011, 2012a; Zhang et al., 2011) have proposed to use a sparse linear combination of the training samples to represent the testing sample, where the main idea of the term “sparse” is that in the linear combination, the coefficients of most training samples are equal or approximately equal to zero. Afterwards, these methods compute the effect, in expressing the testing sample, of the training samples of each class and finally assign the testing sample into the class that making the biggest contribution. These methods indeed exhibit good performance in FR. Because these methods faced with a number of challenges, for example, insufficient available training samples and possible complex variation of the face images, it still can be improved in classification accuracy further (Tang et al., 2012; Zhu and Li, 2012; Xu et al., 2012b). In addition, it seems that more training samples are able to reveal more possible variation of illumination, poses and other changes and are consequently beneficial for true classification of face (Tang et al., 2012; Xu et al., 2013). In practice, a real FR system can capture and store only a limited number of face images. Even in some special cases such as the FR based on personal identity card, there is only one training sample per subject. Insufficient training samples indeed have become one choke point of FR and restrict the development of classification accuracy (Xu et al., 2013). How to conquer the drawback that lacking of sufficient training samples is one of the important problems to be solved.

With the purpose of producing impressive FR result further, in many earlier works, the literatures have designed to synthesize new samples from the original face images. For instance Tang et al. (2012) extended virtual training samples by adding random noise to original training samples. Xu et al. (2013) exploited the symmetry of the face to generate virtual samples, which is the first time to design “symmetrical face” to extend the number of training samples. Moreover, Zhu and Li (2012) introduced the kernel-induced distance to the sparse representation method to identify the closest face image of the testing sample, which has been proved that the kernel-induced distance always leads to higher classification accuracy (Zhu and Li, 2012). In order to conquer the drawback that lacking of insufficient available training samples and deal with the possible complex variation of face images caused by facial expression, poses and illumination simultaneously, this study also adopt the same idea as (Tang et al., 2012; Zhu and Li, 2012) to expand the training samples by adding small random noise to the original training samples to form virtual samples and use the kernel-induced distance to select the nearest face image of the testing sample respectively and devise a two steps kernel sparse representation method based on virtual samples (KSRVS) to perform FR. The first step of the KSRVS is to synthesize the virtual training samples by adding random noise to the original training samples. Both the original and the virtual training samples make up the new training set. Then the KSRVS uses the kernel-induced distance to select the N nearest neighbors from the new training set. The second step of the KSRVS is to express the testing sample as a sparse linear combination of the determined N nearest neighbors and use the representation result to classify which class the testing sample belongs to. The major contributions of this study are: first, through introducing a combination of the virtual samples and the kernel-induced distance to the classification based on sparse representation, the KSRVS can be treated as the extension and continuation of the classification framework based on sparse representation. Second, it conducts comprehensive experiments on the devised method with different public face databases to verify the performance of the KSRVS and the experimental results demonstrate that the KSRVS greatly improves the recognition accuracy for FR.

THE KERNEL SPARSE REPRESENTATION METHOD BASED ON VIRTUAL SAMPLES (KSRVS)

In this section, the details of the KSRVS will be formally showed. Figure 1 shows the flowchart of the KSRVS. Supposing that there are M classes in the face database and each class is composed of R training samples and T testing samples. Both training and testing samples are transformed into column vectors through column by column concatenation in advance.

The KSRVS has two steps. In the first step, for each testing sample, the virtual samples are synthesized by adding small random noise to the original training samples.

Fig. 1:	Flowchart of the devised KSRVS

Both the virtual and the original training samples make up the new training set. Afterwards, the kernel-induced distance is used to select the N nearest neighbors of the testing sample. In the second step, the testing sample is represented and recognized by the sparse linear combination of the selected N nearest neighbors.

To be specific, first, for each original training sample x_i (i = 1,2, ..., MxR), the corresponding virtual training sample x_i (i = 1,2, ..., MxR) is synthesized by adding small random noise to it, the following Eq. 1 shows the virtual training samples:

(1)

where, α and β are positive constants, γ is a random number between 0 and 1, u = 1, 2, ..., row, v = 1, 2, ..., col. row and col stand for the numbers of the rows and columns of training sample, u and v stand for the coordinates of X-axis and Y-axis, respectively. In that way a new training set X is formed by merging original and virtual training samples and the Eq. 2 shows all training samples in the new training set X:

(2)

It means that the new training set X = {X₁, X₂, ..., X_2xMxR}.

For each testing sample Z_j (j = 1, 2, ..., MxT), its N nearest neighbors are determined by the kernel-induced distance from the new training set X. To select the N nearest neighbors of the testing sample, a nonlinear function φ is used to map an input space into a new feature space (Zhu and Li, 2012; Xu et al., 2006, 2012b; Wagner et al., 2012; Gao et al., 2010; Chen and Zhang, 2004; Das and Sil, 2010; Yang et al., 2012a; Kang et al., 2011; Chen et al., 2012), let n(x) be the denotation in the feature space of sample x, the following Eq. (3) shows the formula:

(3)

All the distances between the testing sample and the training samples in the feature space can be calculated by Eq. (3) and denoted by d₁, d₂, ..., d_2xMxR. Then the N nearest neighbors: can be selected based on the first N minimum distances above and . The N selected nearest neighbors can be treated as the most “near” and similar to the testing sample in the new training set X and the class labels of the identified N nearest neighbors are candidates for the class label of the testing sample, in other words, the class label of the testing sample is most possibly the same as one of the class labels of the N selected nearest neighbors.

Second, supposing that the testing sample Z_j (j = 1, 2, ..., MxT) is approximately content with the following Eq. 4:

(4)

where, ai (i = 1, 2, ..., N) is referred to as the corresponding coefficient of the nearest neighbor . It can be inferred from the Eq. 4 that when using the linear combination of the N selected nearest neighbors to express the testing sample, the coefficients of the training samples, which are not members of the , are equal to zero. Let and A= [a₁, a₂, ..., a_N], then Eq. 4 can be rewritten as:

(5)

The matrix of coefficients A is calculated using:

(6)

where, μ is a positive constant and I is the identity matrix.

Supposing that stand for all the training samples of the S_th class among the identified N nearest neighbors and the corresponding coefficients are a_p, ..., a_q, respectively. Then the deviation, between the testing sample and the final effect on expressing the testing sample of the S_th class, can be calculated using the following Eq. 7:

(7)

If d_t = arg_s min D_s, then the classification of the testing sample Z_j will be determined into the t_th class at last. In other words, the smaller deviation of D_s means the bigger final effect of the S_th class () on expressing the testing sample.

ANALYSIS OF THE KSRVS

The KSRVS will be analyzed in this section. One of the most popular FR methods is sparse representation, which has proven to be an extremely powerful tool for FR. The key point of the sparse representation is when representing the testing sample as a linear combination of the training samples, most corresponding coefficients are equal or approximately equal to zero and the sparse nonzero coefficients should concentrate on the training samples with the same class label as the testing sample (Wagner et al., 2012). It could make a good classification decision when there are enough representative training samples. While in most real word cases, a real FR system always do not have sufficient number of representative training samples. Since the face has its easy-to-occur characteristic of deformation, it is reasonable to hypothesis that the face might have various appearances and even sometimes a face image cannot accurately represent the face. Under such circumstances, for example, lighting variation, facial expression and other changes, face images can be deeply affected by these factors. If some derived images can be obtained to enlarge the number of available training samples and in that way, things will go better. According to this view, the KSRVS is devised here.

The KSRVS first produces an equal number of the derived images as the original training samples and both the original and the virtual training samples compose the new training set. Afterwards, the KSRVS uses a kernel-induced distance to select the N nearest neighbors of the testing sample from the new training set. Second, the KSRVS uses the linear combination of the N selected nearest neighbors to express the testing sample and classifies the testing sample by assessing the expression effect on the testing sample.

The earlier work (Tang et al., 2012) has explored the idea that to add small random noise to the original training samples to generate the virtual training samples, which can be beneficial greatly to obtain a lower rate of classification errors. And the earlier work (Zhu and Li, 2012) has explored the idea that to introduce the kernel-based distance to identify the closest face image of the testing face image, which can be also effectively obtain a lower rate of classification errors. If we simultaneously take the insufficient available training samples and the complex variation of face images into account, the classification accuracy can be improved further. According to this view, this study combines the virtual training samples with the kernel-induced distance. That is, after synthesizing the virtual training samples, the KSRVS uses the kernel-induced distance to select the N nearest neighbors of the testing sample for future use. As the KSRVS selects and only uses the linear combination of the N nearest training samples to express the testing sample, which is more informative to exhibit the testing sample, it could efficiently reduce the side-influence of the training samples far from the testing sample. Thus, although the methods proposed by Tang et al. (2012), Zhu and Li (2012), Xu et al. (2011, 2012b) and Zhang et al. (2011) produce high accuracy, it still has room to grow in term of accuracy.

The kernel function (Zhu and Li, 2012) is used when computing the distance between the testing sample and all the training samples. In practice, supposing that each sample is firstly transformed into a new space by using a nonlinear mapping φ. And in general, nonlinear mapping φ is usually unknown. When the testing sample and the training samples are in complex situations, for example, varying facial expression, pose and uneven illumination, the Euclidean distance cannot deal with the distance well. While the kernel-induced distance showed in Eq. 8 can cope with the distance finely. Therefore, the Gaussian Kernel Function G (x, y) (Xu et al., 2004, 2012b; Chen and Zhang, 2004; Gundimada and Asari, 2009) is a widely used kernel function and this study also use the Gaussian Kernel Function:

(8)

where, σ is the parameter of the Gaussian Kernel Function. In particular, G (x, x) = 1, thus, Eq. (3) can be converted into:

(9)

Equation 9 is applied to select N nearest neighbors for each testing sample. The comprehensive experiments conducted on the different public face databases clearly demonstrate that the KSRVS indeed effectively improves the recognition accuracy compared to the various classification methods based on sparse representation (Tang et al., 2012; Zhu and Li, 2012; Xu et al., 2011, 2012b; Zhang et al., 2011).

EXPERIMENTAL RESULTS

In this section, extensive experiments with different public face databases were conducted to illustrate the competitiveness of the KSRVS. Three large public face databases were used: the FERET, ORL and Yale face databases. The FERET face database is challenging due to the large number of subjects, hence, in the experiments, the KSRVS used a subset of the FERET face database to test this method. This subset consists of 700 images from the first 100 subjects each providing 7 images. Each face image from the FERET face database was down sampled to 40x40 pixels. The ORL face database contains images of 40 subjects and each subject is composed of 10 images across simultaneous variation in poses, facial details and illumination.

Fig. 2:	Some original training samples from the FERET face database and the corresponding virtual training samples. The first row shows the original training samples, the second row shows the corresponding virtual training samples

The Yale face database consists of 165 images from 15 subjects each providing 11 images. All face images from the ORL and Yale face databases were also down sampled to 46x56 pixels and 100x100 pixels, respectively.

One drawback of the three public face databases for the purpose of this study is that there is no separate set of training images and testing images, so which sets of images to use for training and testing should be selected first. Thus, to ensure the KSRVS works in practice, it need to find a set of samples as training samples and the remaining samples are treated as the testing samples in advance. For each face database, if P samples of all the Q samples per subject were selected for training samples and the remaining samples were used for testing samples, then the number of possible combinations of training sets and testing sets was:

In the experiments, for each face database, the number of training samples per subject was from 1 to 5. For each possible combination, virtual training samples were extended by Eq. (1) to simulate the variation of illumination, where the parameters α and β were set to 2 and 0.8, respectively, which enabled us to guarantee that there were sufficient number of available training samples. Afterwards, the distances between the testing sample and the training samples in the feature space were figured out by Eq. (9), where the parameter of the Gaussian Kernel Function, i.e., σ, was set to 0.05. The coefficient matrix A was solved by Eq. (6), where μ was set to 0.01. Fig. 2, 3 and 4 show some original training samples and the corresponding virtual training samples from the FERET, ORL and Yale face databases, respectively.

Fig. 3:	Some original training samples from the ORL face database and the corresponding virtual training samples. The first row shows the original training samples, the second row shows the corresponding virtual training samples

Fig. 4:	Some original training samples from the Yale face database and the corresponding virtual training samples. The first row shows the original training samples, the second row shows the corresponding virtual training samples

From the Fig. 2, 3 and 4, it can be seemed that the virtual training samples not only seem to be different from the original training samples, but also indeed somewhat reflect the possible variation of the face images in illumination. As a result, virtual samples are very useful to conquer the drawback of insufficient available training samples.

In order to better examine the effectiveness of the KSRVS, a variety of FR methods based on sparse representation, including the SRMVS (Tang et al., 2012), KBSRM (Zhu and Li, 2012), the TPTSSR (Xu et al., 2011) and the feature space-based representation method (Xu et al., 2012b), the CRC_RLS (Zhang et al., 2011) were also tested. All the experimental results are shown in Table 1, 2 and 3, respectively. Because the recognition accuracy of the KBSRM (Zhu and Li, 2012) has close relation with the parameter N; the recognition accuracy of the feature space-based representation method (Xu et al., 2012b) has close relation with the parameter N; the recognition accuracy of the CRC_RLS (Zhang et al., 2011) has close relation with the parameter feature dimension (dim), in order to get the best classification results of these methods, this study set these parameters to different values and show the best classification results and the corresponding values in Table 1, 2 and 3.

Table 1:	Means of the rates (%) of the classification errors of different methods on the FERET face database

Table 2:	Means of the rates (%) of the classification errors of different methods on the ORL face database

Table 3:	Means of the rates (%) of the classification errors of different methods on the Yale face database

When implementing TPTSSR, the parameter M was set to be half of the number of all the original training samples. Experimental results on the FERET, ORL and Yale face databases show that the KSRVS indeed achieves very good performance, exceeding or competing with the methods mentioned in (Tang et al., 2012; Zhu and Li, 2012; Xu et al., 2011, 2012b; Zhang et al., 2011) in term of classification accuracy. Take the FERET face database for example, when the number of original training samples per class was equal to 3, the means of the rates of the classification errors of the KSRVS (N = 35), SRMVS, KBSRM, TPTSSR, the feature space-based representation method, CRC_RLS are 29.82, 36.76, 39.26, 31.56, 33.64, 39.61%, respectively. It can be observed from the results that with a sufficient set of training samples and kernel-induced distance, the KSRVS can achieve a lower classification error rate than the other tested methods. Fig. 5 shows the recognition results on the FERET face database. In the experiment, the value of N of the KSRVS was set to 35, for each subject in the face database, 3 images were selected as the training samples.

Fig. 5:	Comparison of the means error ratios of different combination on the FERET face database among different methods

It can be observed that the error ratios obtained by the KSRVS are lower more or less than the other tested methods. Fig. 6 shows the experimental results conducted on the ORL face database while selecting 5 training samples and set N = 35.

Fig. 6:	The comparison of the means error ratios of different combination on the ORL face database among different methods

Fig. 7:	Comparison of the means error ratios of different combination on the YALE face database among different methods

Fig. 7 shows the experimental results conducted on the Yale face database while selecting 3 training samples and set N = 55.