# Locally Linear Discriminate Embedding for Face Recognition

Authors: Eimad E. Abusham; E. K. Wong
Journal: Discrete Dynamics in Nature and Society
 (2009)

---

## Abstract

A novel method based on the local nonlinear mapping is presented in this research. The method is called Locally Linear Discriminate Embedding (LLDE). LLDE preserves a local linear structure of a high-dimensional space and obtains a compact data representation as accurately as possible in embedding space (low dimensional) before recognition. For computational simplicity and fast processing, Radial Basis Function (RBF) classifier is integrated with the LLDE. RBF classifier is carried out onto low-dimensional embedding with reference to the variance of the data. To validate the proposed method, CMU-PIE database has been used and experiments conducted in this research revealed the efficiency of the proposed methods in face recognition, as compared to the linear and non-linear approaches.


---

## Body

## 1. Introduction

Linear subspace analysis has been extensively applied to face recognition. A successful face recognition methodology is largely dependent on the particular choice of features used by the classifier. Linear methods are easy to understand and are very simple to implement, but the linearity assumption does not hold in many real-world scenarios. Face appearance lies in a high-dimensional nonlinear manifold. A disadvantage of the linear techniques is that they fail to capture the characteristics of the nonlinear appearance manifold. This is due to the fact that the linear methods extract features only from the input space without considering the nonlinear information between the components of the input data. However, a globally nonlinear mapping can often be approximated using a linear mapping in a local region. This has motivated the design of the nonlinear mapping methods in this study.The history of the nonlinear mapping is long; it can be traced back to Sammon's mapping in 1969 [1]. Over time, different techniques have been proposed such as the projection pursuit [2], the projection pursuit regression [3], self-organizing maps or SOM [4], principal curve and its extensions [5–8], autoencoder neural networks [9, 10], and generative topographic maps or GTM [11]. A comparison of some of these methods can be found in Mao and Jain [12]. Recently, a new line of nonlinear mapping algorithms was proposed based on the notion of manifold learning. Given a data set that is assumed to be lying approximately on manifold in a high-dimensional space, dimensionality reduction can be achieved by constructing a mapping that respects certain properties of the manifold. Manifold learning has been demonstrated in different applications; these include face pose detection [13, 14], high-dimensional data discriminant analysis [15], face recognition [16–18], analysis of facial expressions [19, 20], human motion data interpretation [21], gait analysis [20, 22], visualization of fibre traces [23], and wood texture analysis [24].The remainder of this paper is organized as follows. In Section2, Block diagram of Locally Linear Discriminate Embedding (LLDE) and a Brief review of Locally Linear Discriminate Embedding algorithm are shown. In Section 3, the proposed method is tested on CMU-PIE database and compared to the other methods such as Principal Component Analysis (PCA) and Linear Discriminate Analysis (LDA). Finally, a brief conclusion is given.


## 2. Materials and Methods

### 2.1. Preprocessing and Normalization

Face preprocessing and normalization is significant parts of face recognition systems. Changes in lighting conditions have been found to dramatically decrease the performance of face recognition. Therefore, all images have been preprocessed to obtain a representation of the face which is invariant to illumination, while keeping the information necessary to allow a discriminative recognition of the subjects. Gaussian kernel has been used to estimate the local mean and standard deviation of images to correct nonuniform illumination. The local normalization is computed as follows:(2.1)g(x,y)=f(x,y)-mf(x,y)σf(x,y),
where f(x,y) is the original image, m is an estimation of a local mean of f,ands is an estimation of the local standard deviation.Figure1 illustrates a block diagram of the developed method. All face images have to preprocess to obtain a representation of the face which is invariant to illumination by (2.1). Then we obtain the reconstruction weights by capturing the intrinsic geometry of the neighborhood. The detail of the diagram is illustrated below.Figure 1
Block diagram of the Locally Linear Discriminate Embedding (LLDE).


### 2.2. The LLDE Algorithm

Find reconstruction weights by capturing the intrinsic geometry of the neighborhood. The LLDE creates a locally linear mapping, from the high-dimensional coordinates to the low dimensional embedding, as shown in Figure2.Figure 2
Reconstruction weights of face data and its neighbors.Compute the average weight that represent every face data by its neighbors:(2.2)φ(w)=∥xi-∑j=1Kwijxij∥,xij∈X∈RN,
where xi means the ith unknown sample, and xij the corresponding training samples, according to the K values (nearest neighbors).Computing the low-dimensional embeddingD, the following cost function is minimized:(2.3)Φ(D)=∑i=1N∥Di-∑j=1KWijDj∥2,
where N is the number of training and K is the number of the nearest neighbors.The RBF classifier is a one hidden layer neural network, with several forms of radial basis activation functions, as follows:(2.4)fj(D*)=exp∥D*-μj∥22σj2,
where σj is the width parameter, μj is the vector determining the centre of the basis functionf, and D* is the n-dimensional input vector. In an RBF network, a neuron of the hidden layer is activated whenever the input vector is close enough to its central vector. The second layer of the RBF network, that is, the output layer, comprises one neuron to each class. The final classification is given by the output neuron with the greatest output.


## 2.1. Preprocessing and Normalization

Face preprocessing and normalization is significant parts of face recognition systems. Changes in lighting conditions have been found to dramatically decrease the performance of face recognition. Therefore, all images have been preprocessed to obtain a representation of the face which is invariant to illumination, while keeping the information necessary to allow a discriminative recognition of the subjects. Gaussian kernel has been used to estimate the local mean and standard deviation of images to correct nonuniform illumination. The local normalization is computed as follows:(2.1)g(x,y)=f(x,y)-mf(x,y)σf(x,y),
where f(x,y) is the original image, m is an estimation of a local mean of f,ands is an estimation of the local standard deviation.Figure1 illustrates a block diagram of the developed method. All face images have to preprocess to obtain a representation of the face which is invariant to illumination by (2.1). Then we obtain the reconstruction weights by capturing the intrinsic geometry of the neighborhood. The detail of the diagram is illustrated below.Figure 1
Block diagram of the Locally Linear Discriminate Embedding (LLDE).


## 2.2. The LLDE Algorithm

Find reconstruction weights by capturing the intrinsic geometry of the neighborhood. The LLDE creates a locally linear mapping, from the high-dimensional coordinates to the low dimensional embedding, as shown in Figure2.Figure 2
Reconstruction weights of face data and its neighbors.Compute the average weight that represent every face data by its neighbors:(2.2)φ(w)=∥xi-∑j=1Kwijxij∥,xij∈X∈RN,
where xi means the ith unknown sample, and xij the corresponding training samples, according to the K values (nearest neighbors).Computing the low-dimensional embeddingD, the following cost function is minimized:(2.3)Φ(D)=∑i=1N∥Di-∑j=1KWijDj∥2,
where N is the number of training and K is the number of the nearest neighbors.The RBF classifier is a one hidden layer neural network, with several forms of radial basis activation functions, as follows:(2.4)fj(D*)=exp∥D*-μj∥22σj2,
where σj is the width parameter, μj is the vector determining the centre of the basis functionf, and D* is the n-dimensional input vector. In an RBF network, a neuron of the hidden layer is activated whenever the input vector is close enough to its central vector. The second layer of the RBF network, that is, the output layer, comprises one neuron to each class. The final classification is given by the output neuron with the greatest output.


## 3. Results and Discussion

### 3.1. CMU-PIE Database

One of the largest datasets developed to investigate the affect of Pose, Illumination, and Expression. It contains images of 68 people, each under 13 different poses, 43 different illumination conditions, and 4 different expressions [25]. In the experiments conducted in this study, 6 out of 13 poses for each person were selected. Out of 43-illumination configurations, 21 were selected to typically span the set of variations; these covered the left to the right profile.The Locally Linear Discriminate Embedding (LLDE) is a manifold learning technique, in which the local geometric properties within each class are preserved, based on the local neighbour structure, and the local structure is generally important for discriminate analysis. Each face image can linearly be approximated by its neighbours, with the same set of coefficients, computed from the high-dimensional data in the input space while minimizing reconstruction cost. For classification, the resulting embedding spaces are fed to Gaussian Radial Basis Function to produce feature vectors. A Gaussian Radial Basis Function could be a good choice for the hidden layers; it is widely used and researched tool for (nonlinear) function approximation, which is a central theme in pattern analysis and recognition. The transformation from the input space to the hidden-unit space is nonlinear. On the other hand, the transformation from the hidden space to the output space is linear.Suppose that each hidden layer node is a Gaussian Radial Basis Function equation (2.4) and μj is the centre of the j the class. The closer Di to the μi  is, the higher the value of the Gaussian function will be produced. The outputs of the hidden layer can be viewed as a set of discriminate features, extracted from the input space. Figure 3 shows the plots of the recognition rate versus the dimensionality of the PCA, LDA, and LLDE. The dimensions used are ranging between 10 and 150; based on the figure, the LLDE was shown to significantly outperform the PCA, and LDA. The novelty of the proposed method is to extract discriminate nonlinear features and to solve the problem of using the linear methods to extract features from nonlinear manifold; the global nonlinear structure of nonlinear data will be destroyed by applying linear methods so that the recognition rate is dropped down. The proposed LLDE is invariant to translations and rescaling and takes full advantages of the property manifold learning methods that are superior to linear feature extraction methods.Figure 3
The recognition rates of the PCA, LDA, and LLDE.As shown in the figure, the recognition rates of 49.66%, 55.9%, and 83.1% were achieved by the PCA, LDA, and LLDE, with the reduced feature dimensions of 110, 67, and 95, respectively. For performance assessment and consistent, experiments are conducted on reduced selected dimension (65, 75, 90, 110). The average recognition rates are presented in Figures4, 5, 6, and 7. The upper bound of the dimensionality of LDA is c-1, where c is the number of individuals.Figure 4
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 65).Figure 5
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 75).Figure 6
The average recognition rates of the PCA, LDA, and LLDE across 10 tests (dimension 90).Figure 7
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 110).Table1 shows the average recognition error rates, the comparison of the proposed method, and KPCA Plus LDA, and GDA, across ten tests and four dimensions (65, 75, 90, and 110). From the table, it is obvious that the performance of the proposed method is better and it achieves the lowest error rate as compared to the standard linear methods of PCA and LDA.Table 1
The average error rates (%) of the PCA, LDA, and LLDE, across ten tests and four dimensions.
PCALDALLDE60.7548.1516.98The comparison of the proposed methods and KPCA Plus LDA [26] and GDA [27] is shown in Figure 8. From the figure, it is clear that the performance of the proposed methods is consistently better as compared to other nonlinear discriminant methods. The method was shown to achieve a maximum accuracy of 83.1%, as compared to only 77.22% and 79.92% by the KPCA and GDA, respectively. This is attributed to the number of the features obtained by the LLDE, which are not limited to c-1, and where c is the number of subjects.Figure 8
The recognition rates of the KPCA plus LDA, GDA, and LLDE.


## 3.1. CMU-PIE Database

One of the largest datasets developed to investigate the affect of Pose, Illumination, and Expression. It contains images of 68 people, each under 13 different poses, 43 different illumination conditions, and 4 different expressions [25]. In the experiments conducted in this study, 6 out of 13 poses for each person were selected. Out of 43-illumination configurations, 21 were selected to typically span the set of variations; these covered the left to the right profile.The Locally Linear Discriminate Embedding (LLDE) is a manifold learning technique, in which the local geometric properties within each class are preserved, based on the local neighbour structure, and the local structure is generally important for discriminate analysis. Each face image can linearly be approximated by its neighbours, with the same set of coefficients, computed from the high-dimensional data in the input space while minimizing reconstruction cost. For classification, the resulting embedding spaces are fed to Gaussian Radial Basis Function to produce feature vectors. A Gaussian Radial Basis Function could be a good choice for the hidden layers; it is widely used and researched tool for (nonlinear) function approximation, which is a central theme in pattern analysis and recognition. The transformation from the input space to the hidden-unit space is nonlinear. On the other hand, the transformation from the hidden space to the output space is linear.Suppose that each hidden layer node is a Gaussian Radial Basis Function equation (2.4) and μj is the centre of the j the class. The closer Di to the μi  is, the higher the value of the Gaussian function will be produced. The outputs of the hidden layer can be viewed as a set of discriminate features, extracted from the input space. Figure 3 shows the plots of the recognition rate versus the dimensionality of the PCA, LDA, and LLDE. The dimensions used are ranging between 10 and 150; based on the figure, the LLDE was shown to significantly outperform the PCA, and LDA. The novelty of the proposed method is to extract discriminate nonlinear features and to solve the problem of using the linear methods to extract features from nonlinear manifold; the global nonlinear structure of nonlinear data will be destroyed by applying linear methods so that the recognition rate is dropped down. The proposed LLDE is invariant to translations and rescaling and takes full advantages of the property manifold learning methods that are superior to linear feature extraction methods.Figure 3
The recognition rates of the PCA, LDA, and LLDE.As shown in the figure, the recognition rates of 49.66%, 55.9%, and 83.1% were achieved by the PCA, LDA, and LLDE, with the reduced feature dimensions of 110, 67, and 95, respectively. For performance assessment and consistent, experiments are conducted on reduced selected dimension (65, 75, 90, 110). The average recognition rates are presented in Figures4, 5, 6, and 7. The upper bound of the dimensionality of LDA is c-1, where c is the number of individuals.Figure 4
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 65).Figure 5
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 75).Figure 6
The average recognition rates of the PCA, LDA, and LLDE across 10 tests (dimension 90).Figure 7
The average recognition rates of the PCA, LDA, and LLDE, across 10 tests (dimension 110).Table1 shows the average recognition error rates, the comparison of the proposed method, and KPCA Plus LDA, and GDA, across ten tests and four dimensions (65, 75, 90, and 110). From the table, it is obvious that the performance of the proposed method is better and it achieves the lowest error rate as compared to the standard linear methods of PCA and LDA.Table 1
The average error rates (%) of the PCA, LDA, and LLDE, across ten tests and four dimensions.
PCALDALLDE60.7548.1516.98The comparison of the proposed methods and KPCA Plus LDA [26] and GDA [27] is shown in Figure 8. From the figure, it is clear that the performance of the proposed methods is consistently better as compared to other nonlinear discriminant methods. The method was shown to achieve a maximum accuracy of 83.1%, as compared to only 77.22% and 79.92% by the KPCA and GDA, respectively. This is attributed to the number of the features obtained by the LLDE, which are not limited to c-1, and where c is the number of subjects.Figure 8
The recognition rates of the KPCA plus LDA, GDA, and LLDE.


## 4. Conclusion

Literature surveys and previous studies stated that if linear classifier does not work well, then there are at least two potential reasons for this: (1) regularization was not done well or no robust estimators were used; (2) intrinsically nonlinear: since our dataset is high-dimensional data and the nature of face images is nonlinear, then it is recommended to use an appropriate nonlinear feature space. The proposed method performs an implicit reduction over the whole set of features and effectively extracts the most discriminate features, as shown by the results from the experiments. We think that this is significant when the runtime speed is as important as the actual classification rate: if only a subset of the features is used. In addition to that the proposed method does not suffer from the Small Size (SSS) problem. Our experiments did show clearly that our method is superior to state-of-the art methods.



---

*Source: 916382-2010-01-05.xml*