One of the most important techniques in image representation and feature extraction is Principal Component Analysis (PCA)[1]. The first step of PCA is to transform the matrix associated to an image into vectors of high dimension and then compute the covariance matrix in high-dimensional vector space. The Covariance matrix can not be evaluated accurately due to its large size and the relatively small number of training samples [2]. Furthermore, computing the correspondence eigenvectors is very time consuming. For solving these problems recently a new technique called two-dimensional PCA (2DPCA) has been proposed [2]. The main idea of this method is that it eliminates the image to vector conversion stage and computes covariance matrix directly based on the 2D images. Because of small size of the covariance matrix and adequate training samples, 2DPCA can compute the eigenvectors faster and much more accurate than PCA [2]. Recently in [3] has been shown that 2DPCA is equivalent to block based approach which each block is one line of the image. Although Yang in [2] showed the better performance of matrix-based representation than traditional one-dimensional vector-based approach, there are also some drawbacks in this method. First, it needs to more coefficients for representing an image than previous one-dimensional methods [2]. Kong in [4] tries to solve this problem by proposing two sets of projection directions called Generalized two-dimensional PCA. For finding these projection directions he proposed an iterative algorithm theoretically having local optimal solutions and was dependent on the initial conditions. Second, it loses the covariance information between different local geometric structures in the image while PCA preserves such information which is important for recognition [5]. In this paper we propose a novel method called extended two-dimensional PCA (E2DPCA) which is more useful and efficient for real application. We expose the mathematical relationship between the covariance matrix of the PCA and that of 2DPCA and try to evaluate a new covariance matrix preserving more local structure information than previous 2DPCA. This new covariance matrix can be evaluated more accurately than both that of one and two-dimensional approaches. Also, E2DPCA represents an image with much fewer coefficients which result in more computational efficiency than
2DPCA.
The remaining parts of the paper are organized as follows. In section 2 PCA and 2DPCA and their mathematical relationship is described. The proposed E2DPCA is introduced in section 3. In section 4 experimental results are presented. Finally, we have a
conclusion in section 5.
2.1. PCA
In PCA image A, a random matrix, first is reshaped into a high-dimensional vector, 1)( , by concatenating its columns or its rows, then the scatter matrices are computed as follows:
Where there is training image samples in the database. 1)(
image, and denotes the mean of whole training set.
The optimal projection axis is the set of eigenvectors of corresponding to the first
eigenvalues. For more details see [1].
2.2. 2DPCA
linear transformation. The total scatter of the projected samples, , can be used for determining the
Where , called the image covariance matrix can directly be evaluated by using M training samples. Let the average image of all training samples be denoted by evaluated by:
The optimal projection axis is composed by the
orthonormal eigenvector of the corresponding to the largest eigenvalues.
2.3. Mathematical relationships between PCA and 2DPCA
As stated in [3], 2DPCA can work in either the row or column direction of the images. Here without loss of generality we continue based on the column direction
matrix, is the sample in the database, and
where is defined as:
pApAiAiA M S
of the training images in the database.
is partitioned into submatrices as indicated below:
Therefore we can express
above equation, theorem is proved.
3. Extended Two-Dimensional PCA (E2DPCA)
We can see from equations (1) that is modeled by
sum of all scatter matrices of different column indices in the main diagonal of in term of equality (2). It
can be seen that in many important information
between different local structures of the images has been eliminated which may have important discriminative information for recognition. On the other hand, retaining all this information leads to a large covariance matrix needing to a large number of training data for correctly evaluation. In our method instead of just using the main diagonal, we consider a radius of r diagonals around it and expand the averaging so as to include the covariance information within those diagonals. Moreover, the parameter r unifies PCA and 2DPCA. r=1 produces the covariance of 2DPCA, r=n that of PCA. Hence, by controlling r it is possible to control the trade-offs between recognition accuracy and energy compression (fewer coefficients), and between training and recognition complexity: PCA has lower recognition rates but produces fewer coefficients, and it is harder to compute the PCA covariance but the projection in the resulting eigenvectors is easier. The new covariance matrix when r=2 :
times larger than that of 2DPCA and preserves more local structure information. More precisely, new covariance matrix not only keep covariance information from the main diagonal of in term of
equality (2), but also keep some information from one diagonal above and below it. Although the new covariance matrix becomes larger, extracting eigenvectors from it is still easy task. We should mention that parameter r has a natural interpretation. It is the number of image columns that are stacked for the computation of the PCA transform. In PCA (r=n), the n columns are stacked into a column vector. In 2DPCA (r=1) there is no stacking and the image is represented as a matrix. When r=k, k columns are stacked at a time. Figure 1, Shows an example when r=2. in this situation, we stack two columns at a time, making the matrix twice as tall and half as fat. When the number of columns or rows is odd we add zero
projection direction. It’s well known that the optimal direction is equal to the eigenvectors of
eigenvectors are used to form a )2(
vectors are used for feature extraction. For a given test face image , we at first reshape it in the way as illustrated in figure (1.a) to form an image matrix and then use the following equation:
than feature matrix of 2DPCA . A nearest neighbor classifier with Euclidean distance is used for classification. It’s obvious that when r is greater than 2, the original image matrices transform into matrix and the resulted covariance
matrix have dimension and after feature extraction the dimension of feature matrix is )/( which is much less than the dimension of
2DPCA feature matrix. By increasing r, covariance matrix becomes larger, and feature matrix becomes smaller which result in the decreasing of computation cost. In PCA, finding optimal projection is time consuming but recognition is very fast. Reverse is true for 2DPCA. In E2DPCA we have a trade off between the computation cost in eigenvector decomposition and recognition.
For showing the effect of E2DPCA, we use ORL database [6]. This database contains images from 40 individuals, each providing 10 different images. The pose, expression, and facial details variations are also included. The images are taken with a tolerance for some tilting and rotation of the face of up to 20 degrees. Moreover, there is also some variation in the scale of up to about 10 percent. All images are grayscale and normalized to a resolution of 92112pixels. In our experiments we use first five image sample per class for training, and the remaining images for the test. Thus the total number of training samples and testing samples were both 200. 2DPCA which originally works on row direction of images [4] can also work on the column direction. In our experiments, we use the word “alternative” for expressing column based algorithm. When we want to apply E2DPCA in row direction of the image we should transforms the image in the way as illustrated in figure (1.b). For finding the optimal point E2DPCA is applied with different . Table (1) shows the comparisons of six methods PCA, 2DPCA (row based), alternative 2DPCA (column based), E2DPCA (row based), alternative E2DPCA (column based) and 2D2PCA [7] on recognition accuracy and dimension of feature vectors. As can be seen from this table top accuracy of E2DPCA is better than that of other methods which is because of using more local geometric structure information. Moreover, it represents image with fewer coefficients than both 2DPCA and 2D2PCA. Table (2) compares dimensions of the feature vectors and recognition time cost of the different method under the same accuracy. It can be seen from this table that E2DPCA represents the image with much fewer coefficients than both 2DPCA and 2D2PCA, for instance 2DPCA, 2D2PCA and E2DPCA reach same accuracy with 896, 144 and 50 coefficients, respectively. Also recognition time in E2DPCA is less than other methods.
Figure 1. Illustration of the way for deriving the reshaped image for E2DPCA, Left: original image, Right: reshaped image Table 1. Comparison of top recognition accuracy in different methods on ORL database Method (%) Dimension
Table 2. Comparison of dimensionality of different methods under the same accuracy on ORL database Method (%) Dimension Time (s)
In this paper a novel method called E2DPCA was proposed which is an extension to the current 2DPCA algorithm. We try to unify PCA and 2DPCA by defining a parameter notated as r which it extends the covariance matrix of 2DPCA toward that of PCA. 2DPCA eliminates much local geometric structure information presented in the covariance matrix of PCA. This information is important for recognition so we defined an adjacent radius which let us to adjust how much this information being used. Experimental results show improvement in both recognition accuracy and recognition time over 2DPCA.
[1] Turk, M., Pentland, A.: Eigenfaces for recognition. J. Cognitive Neurosci. 3, 1, 71--86 (1991).
[2] Yang, J., Zhang, D., Frangi, A.F., Yang, J.: TwoDimensional PCA: A New Approach to AppearanceBased Face Representation and Recognition. IEEE Trans. Pattern Anal. Machine Intell. Vol. 26, No. 1, 131--137 (2004).
[3] Wang, L., Wang, X., Feng, J.: On image matrix based feature extraction algorithms. IEEE Trans. Syst. Man. Cybern. Part B, Cybern. 36, 1, 194--197 (2006).
[4] Kong, H., Wang, L., Teoh, E.K., Li, X., Wang, J.G., Venkateswarlu, R.: Generalized 2D principal component analysis for face image representation and recognition. Neural Netw. 18, 585--594, (2005).
[5] Zheng, W.S., Lai, J.H., and Li, S.Z, "1D-LDA vs. 2D-LDA: When is vector-based linear discriminant analysis better than matrix-based?", PR(41), No. 7, pp. 2156-2172, (2008).
[6] AT&T Laboratories Cambridge, http://www.cl.cam.ac.uk.
[7] Zhang, D., Zhou, Z.H.: (2D)2PCA: two-directional two-dimensional PCA for efficient face representation. Neurocomputing 69. 224--231 (2005).