An Application of Linear Algebra for the Optimal Image Recognition

An Application of Linear Algebra for the Optimal Image Recognition

1Neeraj Kumar, 2Nirvikar

1Assistant Professor, CSE, Institute of Technology Roorkee, Roorkee

2Assistant Professor, CSE, IEC College of Engineering & Technology, Greater Noida

Abstract: The Real-Time approach of detection and identification of human faces in a present day scenario is too difficult and to develop a system for the same is in progress. In this article our approach is for two- dimensional recognition of the faces, taking the advantage of the facts that faces are normally up-right. Face Images are projected onto a Feature Space i.e. Face Space. The Eigenface method uses Principal Component Analysis (PCA) to linearly project the image space to a low dimensional feature space. The LDA method is an enhancement of the Eigenface method that it maximizes the ratio of between-class scatter to that of within- class scatter, therefore, it works better than PCA. Linear Discriminant Analysis (LDA) which effectively see only the Euclidean Structure of face space. Experimental results suggest that the proposed Eigen Faces with LDA approach provides a better representation and achieves lower error rates in face recognition.

Keywords: Feature Space, Eigenface, PCA, LDA, Euclidean Structure, Face Recognition.

approach attempts to capture and define the face as

1. Introduction:

   Face recognition is done by scanning a persons face and matching it against a database of known faces and its a biometric approach. Face recognition is defined as the identification of a person from an image of their face. Face Recognition is done by two ways i.e. firstly Face Identification and secondly, Face Verification. The task of recognition of human faces is quite complex. The human face is full of information but working with all the information is time consuming and less efficient. It is better get unique and important information and discards other useless information in order to make system efficient. Face recognition systems can be widely used in areas where more security is needed, like Air ports, Military bases, Government offices etc. Automatic face recognition by computer can be divided into two approaches, namely, content- based and face-based. In content-based approach, recognition is based on the relationship between human facial features such as eyes, mouth, nose, profile silhouettes and face boundary. The success of this approach relies highly on the accurately is difficult. Every human face has similar facial features; a small derivation in the extraction may introduce a large classification error. Face-based

   a whole. The face is treated as a two-dimensional pattern of intensity variation. Under this approach, face is matched through identifying its underlying statistical regularities.

   However common PCA-based methods suffer from two limitations i.e. poor discriminatory power and large computational load. It is well known that PCA gives a very good representation of the faces. Given two images of the same person, the similarity measured under PCA representation is very high. Yet, given two images of different persons, the similarity measured is still high. That means PCA representation gets a poor discriminatory power and further improve the discriminability of PCA by adding Linear Discriminant Analysis (LDA). But, to get a precise result, a large number of samples for each class are required. The second problem in PCA-based method is the high computational load in finding the eigenvectors. The computational complexity of this is O (d2) where d is the number of pixels in the training images which has a typical value of 128×128. The computational cost is beyond the power of most existing computers. Fortunately, from matrix theory, we know that if the number of training images, N, is smaller than the value of d, the computational complexity will be reduced to

   O (N2). Yet still, if N increases, the computational load will be increased in cubic order. In view of the limitations in existing PCA-based approach, we proposed a new approach in using PCA applying PCA on LDA sub-band for feature extraction.

   1. Digital Image Processing:

      An image can be defined as a twodimension function f (x, y) (2D image), where x and y are spatial coordinates, and the amplitude of f at any pair of (x, y) is gray level of the image at that point. For example, a grey level image can be represented as:

      linear combinations of the original p variables the first k components display as much as possible of the variation among objects.

      1.3. Geometric Rationale of PCA:

      The objects are represented as a cloud of n points in a multidimensional space with an axis for each of the p variables.

      The centroid of the points is defined by the mean of each variable.

      The variance of each variable is the average squared deviation of its n values around the mean of that variable.

      X

      X

      1 n

      fij where fij f ( xi , yj ) (1.1)

      When x, y and the amplitude value of f are finite,

      V

      m

      m

      1

      1

      i n 1

      X im

      (22.1.1)

      i

      discrete quantities, the image is called a digital image. The finite set of digital values is called picture elements or pixels. Typically, the pixels are

      stored in computer memory as a twodimensional

      • Degree to which the variables are linearly correlated is represented by their covariances.

      1 n

      array or matrix of real number.

      Color images are formed by a combination of individual 2D images. Many of the image

      Cij

      n 1 m 1

      X im

      X i X jm

      X j

      (2.1.2)

      processing techniques for monochrome images can be extend to color image (3D) by processing the three components image individually.

      1.2. PCA (Principal Component Analysis):

      Its the most widely-used and well-known of the standard multivariate methods invented by Pearson (1901) and Hotelling (1933) first applied in ecology by Goodall (1954) under the name factor analysis (principal factor analysis is a synonym of PCA). It is a way of identifying patterns in data, and expressing the data in such a way as to highlight their similarities and differences. Since patterns in data can be hard to find in data of high dimension, where the luxury of graphical representation is not available, PCA is a powerful tool for analyzing data. The other main advantage of PCA is that once you have found these patterns in the data, and you compress the data, i.e. by reducing the number of dimensions, without much loss of information. This technique used in image compression. It takes a data matrix of n objects by p variables, which may be correlated, and summarizes it by uncorrelated axes (principal components or principal axes) that are

      Objective of PCA is to rigidly rotate the axes of this p-dimensional space to new positions (principal axes) that have the following properties:

      Ordered such that principal axis 1 has the highest variance, axis 2 has the next highest variance, …. , and axis p has the lowest variance

      Covariance among each pair of the principal axes is zero (the principal axes are uncorrelated).

      1. PCA for images or Eigen-faces:

         The Eigenface method is based on linearly projecting the image space to a low dimensional feature space. The Eigenface method, which uses principal components analysis (PCA) for dimensionality reduction, yields projection directions that maximize the total scatter across all classes, i.e., across all images of all faces.

         Let us conider a set of N sample images{x1, x2, …, xN} taking values in an n-dimensional image space, and assume that each image belongs to one of classes{X1, X2, …,Xc}. Let us also consider a linear transformation mapping the original n-

         dimensional image space into an m-dimensional feature space, where m < n. The new feature vectors Yk Rm are defined by the following linear transformation:

         (2.2.1)

         Where W Rn×m is a matrix with orthonormal columns.

         If the total scatter matrix ST is defined as

         (2.2.2)

         where µ Rn is the mean image of all samples, then after applying the linear transformation WT, the scatter of the transformed feature vectors {y1,

         y2, …, yN} is WTSTW. In PCA, the projection Wopt

         is chosen to maximize the determinant of the total scatter matrix of the projected samples, i.e.

         (2.2.3)

         (2.2.4)

         Where {wi|i = 1,2, …, m} is the set of n-dimensional eigenvectors of ST corresponding to the m largest Eigen values {i|i = 1,2, …, m}, i.e.,

         (2.2.5)

         Since these eigenvectors have the same dimension as the original images, they are referred to as Eigen pictures in and Eigen-faces in. Classification is performed using a nearest neighbor classifier in the reduced feature space. Most Expressive Features (MEF): vectors show the tendency of PCA to capture major variations in the training set such as lighting direction.

      2. Algorithm for Training:

      Step-1: Align training images X1, X2, , XN. Step-2: Compute average face u = 1/N Xi. Step-3: Compute the difference image i = Xi u.

      T T

      T T

      Step-4: Compute the covariance matrix (total scatter matrix)

      ST = (1/N) i i = BB , B= [1, 2 N].

      Step-5: Compute the eigenvectors of the covariance matrix, W.

2. Linear Discriminant Analysis (LDA):

   LDA selects Eigen-vectors U in such a way that the ratio of the between-class scatter and the within class scatter is maximized. PCA on the other hand does not take into account any difference in class. LDA computes the projection U that maximizes the ratio:

   (2.1)

   Where SB and SW are the between class scatter matrix and the within class scatter matrix respectively, such that:

   (2.2)

   and

   (2.3)

   M is the number of the classes, Ni is the number of samples in class i and µi is the mean of class i. Uopt can be found by solving the generalized Eigen value problem.

   LDA assumes that the whole dataset is given in advance, and is trained in one batch. However, in a streaming environment, new samples are being presented continuously, possibly without end. The addition of these new samples will lead to the changes of the original mean vector µ, within class scatter matrix SW, as well as between-class distance matrix SB, therefore the whole discriminant Eigen space model should be updated.

   Let X and Y are two sets observations, where X is the presented observation set, and Y is a set of new observations. Let their discriminant Eigen space models be = (Swx, SBx, µx, N) and = (SWy, SBy, µy, L), respectively. This updating problem is to compute the new fisher space model = (Swv, SBv, µv, N + L) using fisher space models and . Most Discriminating Features

   (MDF): the features (projections) obtained using LDA.

3. Experiments and Interpretations:

   A set of face images were used for the PCA approach and the results is interpreated as below with input facial images and their Eigen faces are listed in Figure 1 and Figure 2.

   Figure 1: The Input facial Images (PCA Approach)

   Figure 2: The Eigen Faces for the set of input facial Images (PCA Approach)

   A set of face images were used for the LDA approach and the results is interpreated as below with input facial images and their Eigen faces are listed in Figure 3 and Figure 4.

   Figure3: The Input facial Images (LDA Approach)

   Figure 4: The Eigen Faces for the set of input facial Images (PCA Approach)

4. PCA vs LDA(Results Comparision):

100

Training

PCA is proper to dimension reduction. PCA are the maximal variance dimensions the relevant dimensions for preservation? LDA perform dimensionality reduction while preserving as much of the class discriminatory information as possible. LDA is proper to pattern classification if the number of training samples of each class is large. Seeks to find directions along which the classes are best separated. Takes into consideration the scatter within-classes but also the scatter between-classes. For example of face recognition, more capable of distinguishing image variation due to identity from variation due to other sources such as illumination and expression. So LDA plays slightly better than PCA for Eigen face recogniations but within some limitations. But can be improved with some other better techniques.

6. References:

1. M.TurkandA.Pentland, Eigen faces for Recognition, Journal of Cognitive Neuroscience, 1991.

2. W.Zhao, A.Krishnaswamy, R.Chellappa, Discriminant Analysis of Principal Components for Face Recognition, In Proceedings, International Conferenceon Automatic Face and Gesture Recognition.336341.

3. M. Turk, A random walk through eigenspace, IEICE Trans. Inf. & Syst., vol. E84- D, no. 12, pp. 15861695, December 2001.

4. S. Kim, S. T. Chung, S. Jung, and S. Cho, An improved illumination normalization based on anisotropic smoothing for face recognition, International Journal of Computer Science and Engineering, Vol. 2, No.3, pp.89-95, 2008.

5. K. R. Singh, M. A. Zaveri, and M. M.Raghuwanshi, Illumination and pose invariant face recognition: a technical review, International Journal of Computer Information Systems and Industrial Applications (IJCISIM), Vol.2, pp.29- 38, 2010.

6. X. Zhang and Y. Gao, Face recognition across pose: A review Pattern Recognition, Vol. 42, No. 11, pp. 28762896, 2009.

7. G. Shakhnarovich and B. Moghaddam, Face recognition in subspaces, Springer, Heidelberg, May 2004.

   50

   0

   1 2 3 4 5

   Images

   Testing Images

8. A. Jain, L. Hong, and S. Pankanti, Biometric identification, Communications of the ACM, Vol. 43, No. 2, Feb. 2000.

9. Imola K. Fodor, A survey of dimension

   5. Conclusion:

   reduction techniques, June 2002

10. www.elsivercomputerscience.com

11. Mat Lab 7.0 Image Processing Tool Box.