1.

Introduction

Face recognition (FR) has received increasing attention in recent years due to its potential applications. Many FR systems have been devised in the past few decades. One of the most popular techniques for FR is subspace analysis. Two of the most important and representative ones are principal component analysis (PCA)¹ and linear discriminant analysis (LDA).² Many other methods such as 2DPCA,³ 2DLDA,⁴ ICA,⁵ ${\left(2\mathrm{D}\right)}^2\mathrm{LDA}$ ,⁶ $\mathrm{BDPCA}+\mathrm{LDA}$ ,⁷ and $\mathrm{IPCA}-\mathrm{ICA}$ ⁸ are all extended from them. LPP⁹ is also a subspace analysis method. As stated in,⁹ it performs better than LDA in terms of error rate. However, all methods [including locality preserving projections (LPP)] mentioned above are inefficient, because they identify a test face image by comparing it with all training images. To overcome this disadvantage, we propose to combine LPP with affinity propagation (AP)¹⁰ to give a new FR framework, APLPP, which uses much fewer training images, free of noise, to identify a test image. Thus APLPP is more computationally efficient than LPP.

The reason why we propose to combine AP with LPP is as follows: AP can detect a representative sample for each class. Therefore, we can use AP to detect a representative face image for each subject and use only the representative images rather than all training ones for identification. However, the original AP regards the negative Euclidean distance between two images as their measure of similarity, which is directly computed on the gray pixel values. As we stated in Ref. 11, such a definition of similarity is unreasonable. To solve this problem, we propose to compute the similarity on low-dimensional features derived from LPP, not only because LPP can be used for dimensionality reduction and best detect the essential face manifold structure, but because it can reduce the unwanted variations resulting from changes in lighting, facial expression, and pose. By using LPP on the high-dimensional face data, more efficient low-dimensional features can be obtained. Obviously, the similarity on these features should be better than that directly computed from the gray pixel values. In addition, it needs much less computational time, because the dimension has been reduced greatly. In view of this analysis, we propose to combine AP with LPP and make full use of their advantages.

The rest of this paper is as follows: AP and LPP are reviewed in Secs. 2, ³, respectively. In Sec. 4, we summarize the APLPP method. Experimental results are given in Sec. 5. The final section gives the conclusions.

2.

Affinity Propagation

AP¹⁰ is an efficient clustering method. It first builds a similarity matrix $s$ , in which $s(i,k)$ between data points $x_i$ and $x_k$ is their negative Euclidean distance. Before clustering, each point also needs to be assigned a number $P\left(B\right)$ , which characterizes the prior knowledge of how good point $B$ is as a representative example. The data points with larger values of $P\left(B\right)$ are more likely to be chosen as representative examples. These values are referred to as preferences. In fact, all data points are equally suitable as representative examples; thus the preferences should be set to the same value, which can be varied to produce different numbers of clusters. Generally, that value is the median of $s$ . After the construction of similarity matrix and the setting of preferences, two kinds of messages (responsibility, availability) are passed between data points. The responsibility $r(i,k)$ , sent from the data point $x_i$ to the candidate representative example data point $x_k$ , reflects the accumulated evidence for how proper it would be for point $x_k$ to serve as the representative example for point $x_i$ . It is updated using the rule

Availabilities and responsibilities can be combined to recognize representative examples at any time during affinity propagation. For point $x_i$ , the $k$ that maximizes $a(i,k)+r(i,k)$ indicates that point $x_k$ serves as the representative example for point $x_i$ .

3.

Locality Preserving Projections

LPP, or Laplacianface,⁹ is also a subspace analysis method for recognition. Here, it is formulated as follows: Suppose a set of face images $\{x_1,x_2,\dots ,x_N\}$ . Let $S$ be a similarity matrix defined on the data points. Laplacianface can be obtained by solving the minimization problem

Once the eigenvectors are computed, let $W=[w_1,w_2,\dots ,w_k]$ be the transformation matrix. Thus the low-dimensional feature can be obtained by using $Y=W^{T}X$ .

4.

Proposed Affinity Propagation Locality Preserving Projections

Suppose there are $N$ training images $\{x_1,x_2,\dots ,x_N\}$ belonging to $c$ different subjects. Firstly, select $n$ $(n>1)$ images per person (hence $nc$ in total) to form the training set, and use LPP on the training set to get the transformation matrix $W$ and the $nc$ corresponding reduced features. Secondly, use AP to cluster these $nc$ reduced features into $c$ different classes and obtain a representative reduced feature for each class. Thus there will be $c$ representative features $A_1,A_2,\dots ,A_c$ , such that each feature is assigned an identity ${\omega }_i$ $(1\le i\le c)$ , and each class has just one representative feature. The reason why these features should be clustered into $c$ different classes can be found in Ref. 11. Finally, convert the test face image $T$ into the low-dimensional feature $L$ using $L=W^T\times T$ , and then identify it using a nearest-neighbor classifier (NNC) or AP. Thus two methods APLPP(NNC) and APLPP(AP) are generated. APLPP(NNC) uses NNC to find which representative face image is nearest to the test face image. In this case, Euclidean distance is used. On the other hand, APLPP(AP) uses AP again to cluster $c+1$ features ( $c$ representative features plus a test feature) into $c$ classes and find which representative features the test one belongs to. It should satisfy two conditions: (a) the number of classes after clustering must equal $c$ ; (b) the representative features achieved in the training stage must remain representative ones after clustering. How to achieve this goal? As described before, the points with larger preference are more likely to be chosen as representative examples, and each test feature $B$ is supposed to be clustered into one of these representative features; thus we assign large values (e.g., 1) to $A_1,A_2,\dots ,A_c$ and very small values (e.g., $-1000$ ) to $L$ , and then perform the clustering.

Since APLPP(NNC) and APLPP(AP) use only $c$ representative features for recognition, their recognition time mainly depends on the number of subjects. It increases linearly with $c$ , while the recognition time of LPP increases linearly with the number of training images $\left(nc\right)$ . Obviously, both our methods are more computationally efficient than LPP.

5.

Experiments

In this section, experiments are described that validate the effectiveness of APLPP and compare it with LPP, using the extended YaleB face database.¹² It contains around 64 near-frontal images for each of 38 distinct subjects. All images were preprocessed¹¹ so that the final images have size $32\times 32$ , with 256 gray levels per pixel. Different numbers of images per individual were taken to form the training set. The rest of the database was considered to be the testing set. The experiments were repeated 20 times, and the average accuracy was recorded. In general, the performance of the LPP and APLPP varies with the number of dimensions. We only show the best results obtained by them in Table 1. The values in parentheses denote the dimensions to attain top recognition rate. As can be seen, APLPP(AP) performs uniformly better than APLPP(NNC), followed by LPP. This means AP is more suitable for use as a classifier than NNC in these cases. Moreover, both of our methods improve the FR performance by large margins over LPP.

Table 1

Performance comparison on extended YaleB database. Here n is the number of training face images per person.

The experiments reveal some interesting points:

6.

Conclusions and Further Work

LPP has been proposed to be combined with AP to give a new FR framework. In contrast with LPP, which identifies a test image by comparing it with all training images, our proposed method uses only representative face images. We also apply the AP clustering method for identification. The new framework has been evaluated on the extended YaleB database. Comparative experimental results show the effectiveness of the new framework. Further work will include applying the proposed method to human gait recognition and digital character recognition.