Algorithms for Face Recognition

Algorithms for Face Recognition

Algorithms for Face Recognition

Shantanu Khare1, Ameya K. Naik2

Department of Electronics and Telecommunication

K.J. Somaiya College of Engineering Mumbai, India

1sk989008@gmail.com, 2ameyanaik@engg.soamiya.edu

AbstractOver the last ten years, face recognition has become a specialized applications area within the field of computer vision. Sophisticated commercial systems have been developed that achieve high recognition rates. The goal of this report is to compare three mathematical algorithms on the basis of a face recognition task. The first technique is principal component analysis (PCA), a well-known baseline for projection techniques. The second technique is independent component analysis (ICA), a newer method that produces spatially localized and statistically independent basis vectors. In the third technique i.e. LDA, the goal is to find an efficient and interesting way to represent the face vector space by taking into account the separate class statistics.

KeywordsPCA; ICA; LDA; Biometrics; Face recognition.

1. INTRODUCTION

   Face recognition is a biometric approach that employs automated methods to verify or recognize the identity of a living person based on his/her physiological characteristics. In general, a biometric identification system makes use of either physiological characteristics (such as a fingerprint, iris pattern, or face) or behavior patterns (such as hand-writing, voice, or key-stroke pattern) to identify a person. Face recognition has the benefit of being a passive, user-friendly and non intrusive system to verify personal identity.

   Fig 1: The Spreading of the most popular biometrics in terms of percentage [1]

   As shown in the figure above, the commonly used biometrics is fingerprints, although many other human characteristics are also being used. However, biometrics has certain drawbacks. Iris recognition is extremely accurate, but expensive to implement and not very accepted by people. Fingerprints are

   reliable and non-intrusive, but not suitable for non- collaborative individuals. On the contrary, FR seems to be a good compromise between reliability and social acceptance and balances security and privacy well.

   1. Face Recognition Applications

      FR has many applications which are centered long two main primary tasks:

   2. Need of an Algorithm-based Facial Recognition System

      .

      1. There is a wide variability in the face recognition ability of humans. Differences in error rates of an order of magnitude are often observed.

         Fig 2. The four general steps in Facial Recognition

      2. The capability of humans recognizing people from their own race is satisfactory but relatively poor for people from another race, which is rather undesirable.

      3. There is a limit to the number of faces a human brain can recognize and process information. At places such as electoral registrations or airports, where identity verification of a large human population is carried out, it is practically very difficult for humans to identify each and every individual with precision. On the other hand, an algorithm based automatic face recognition system can carry out the identification process relatively easily and more accurately since it can work on limitless amount of data in the form of images (high or low intensity) stored in computer databases.

      4. Over the last few years, algorithm-based facial recognition technology has shown dramatic improvement. The best performing systems in 1999 were at the level of the poorest performing humans, however, by 2006, the best performing technology outperforms more than half of the humans performing the same task.

   3. The Process of Face Recognition.

   Facial recognition systems usually consist of four steps, as shown in Figure 1.2; face detection (localization), face preprocessing (face alignment/normalization, light correction and etc.), feature extraction and feature matching. These steps are described in the following sections.

   1. Face Detection

      The aim of face detection is localization of the face in a image. In the case of video input, it can be an advantage to track the face in between multiple frames, to reduce computational time and preserve the identity of a face (person) between frames. Methods used for face detection includes: Shape templates, neural networks and Active Appearance Models (AAM).

   2. Preprocessing

      The aim of the face pre-processing step is to normalize the coarse face detection, so that a robust feature extraction can be achieved. Depending of the application, face pre- processing includes: Alignment (translation, rotation, scaling) and light normalization/correlation.

   3. Feature Extraction

      The aim of feature extraction is to extract a compact set of interpersonal discriminating geometrical or/and photometrical features of the face. Methods for feature extraction include: PCA, FLDA and Locality Preserving Projections (LPP).

   4. Feature Matching

   Feature matching is the actual recognition process. The feature vector obtained from the feature extraction is matched to classes (persons) of facial images already enrolled in a database. The matching algorithms vary from the fairly obvious Nearest Neighbor to advanced schemes like Neural Networks [4]

2. ALGORITHMS

   Over the last few of years, face recognition researchers have been developing new techniques. These developments are being fueled by advances in computer vision techniques, computer design, sensor design, and interest in the field of face recognition systems.

   1. Principal Component Analysis

      Principal component analysis (PCA) was invented in 1901 by Karl Pearson. PCA is a variable reduction procedure and useful when obtained data have some redundancy. This will result into reduction of variables into smaller number of variables which are called Principal Components which will account for the most of the variance in the observed variable. Problems arise when we wish to perform recognition in a high-dimensional space. Goal of PCA is to reduce the dimensionality of the data by retaining as much as variation possible in our original data set. On the other hand dimensionality reduction implies information loss. The best low-dimensional space can be determined by best principal components. The major advantage of PCA is using it in eigenface approach which helps in reducing the size of the database for recognition of a test images. The images are stored as their feature vectors in the database which are found out projecting each and every trained image to the set of Eigen faces obtained. PCA is applied on Eigen face approach to reduce the dimensionality of a large data set [5].

      1) Eigen Face Approach

      It is adequate and efficient method to be used in face recognition due to its simplicity, speed and learning capability. Eigen faces are a set of Eigen vectors used in the Computer Vision problem of human face recognition. They refer to an appearance based approach to face recognition that seeks to capture the variation in a collection of face images and use this information to encode and compare images of individual faces in a holistic manner.

      The Eigen faces are Principal Components of a distribution of faces, or equivalently, the Eigen vectors of the covariance matrix of the set of the face images, where an image with N by N pixels is considered a point in N 2 dimensional sace. Previous work on face recognition ignored the issue of face stimulus, assuming that predefined measurement were relevant and sufficient. This suggests that coding and decoding of face images may give information of face images emphasizing the significance of features. These features may or may not be related to facial features such as eyes, nose, lips and hairs. We want to extract the relevant information in a face image, encode it efficiently and compare one face encoding with a database of faces encoded similarly. A simple approach to extracting the information content in an image of a face is to somehow capture the variation in a collection of face images.

      Given an s-dimensional vector representation of each face in

      a training set of M images, PCA tends to find a t- dimensional subspace whose basis vectors correspond to the maximum variance direction in the original image space. This new subspace is normally lower dimensional (t << s). New basis vectors define a subspace of face images called face space. All images of known faces are projected onto the face space to find a set of weights that describes the contribution of each vector. To identify an unknown image, that image is projected onto the face space to obtain its set of weights. By comparing a set of weights for the unknown face to sets of weights of known faces, the face can be identified. If the image elements are considered as random variables, the PCA basis vectors are defined as eigenvectors of the scatter matrix ST defined as

      ST = (x – µ)(x – µ)T (1)

   2. Independent Component Analysis

      PCA considered image elements as random variables with Gaussian distribution and minimized second-order statistics. Clearly, for any non-Gaussian distribution, largest variances would not correspond to PCA basis vectors.

      Independent Component Analysis (ICA) (Bartlett et al., 2002; Draper et al., 2003) minimizes both second-order and higher order dependencies in the input data and attempts to find the basis along which the data (when projected onto them) are statistically independent.

      The INFOMAX algorithm was proposed by Bell and Sejnowski and used by Bartlett et al. (2002).

      Similar to PCA, ICA seeks a set of vectors that reduces the dimensionality of input images. However, ICA does not require the orthonormalization of vectors, which allows higher-order dependencies in image pixels to be exploited. As the mean (first-order statistic) is removed from the images in PCA, ICA removes first and second order statistics by sphering the data. Each image (with the mean subtracted) is stored as a row vector in X, which is multiplied by the whitening matrix Wz =2 cov(X)-1/2.ICA finds statistically independent images, represented by the rows in matrix U, that are mixed together with matrix W such that U=WX. In comparison to PCA, the rows of U are analogous to eigenfaces and the columns of W-1 are the weights of each image.ICA can account for more variations in the inputs images, but suffers from slower performance [9].

   3. Linear Discriminant Analysis

   LDA encodes discriminatory information in a linear separable space of which bases are not necessarily orthogonal. Researchers have demonstrated that the LDA based algorithms outperform the PCA algorithm for many different tasks [7, 8]. However, the standard LDA algorithm has difficulty processing high dimensional image data. PCA is often used for projecting an image into a lower dimensional space or so-called face space, and then LDA is performed to maximize the discriminatory power.

   In those approaches, PCA plays a role of dimensionality reduction and forma PCA subspace. The relevant information might be lost due to inappropriate choice of dimensionality in the PCA step [9]. However, LDA can be used not only for classification, but also for dimensionality reduction. For example, the LDA has been widely used for dimensionality reduction in speech recognition [10]. LDA algorithm offers many advantages in other pattern recognition tasks, and we would like to make use of these features with respect to face recognition as well.

   i

   One of the failings in PCA and ICA is that the distances between weights from faces of the same person are greater than face weights from different people. To correct this, a method called Fisherfaces, based on LDA attempts to find vectors that not only describe the data, but also best discriminate between classes of data. Given c classes (people) with the mean of class j denoted by µj and the ith image in class j denoted by x j, a within-class scatter matrix Sw and a between-class scatter matrix Sb is calculated [11].

   Sb = (µj µ)( µj µ)T (2)

   Sw = (x j µ)(x j µ)T (3)

   Bartlett et al. (2002) provided two architectures of ICA for i i

   face recognition task: Architecture I statistically independent basis images and Architecture II factorial code representation [6].

3. IMPLEMENTATION SETUP

   1. Algorithms

      The algorithm codes for ICA, PCA as well as LDA have been implemented in MATLAB. ICA has been implemented in Architecture-I. PCA algorithm is based on Eigenface method. LDA algorithm is based on the Fisherface method. Euclidean distance was used as a classifier to find the best match from the input test images.

   2. Databases

   The following databases were used for simulating the algorithm performance evaluation.

   1. AT & T Database

      Ten different images of each of 40 distinct subjects have been taken. For some subjects, the images were taken at different times, varying the lighting, facial expressions (open / closed eyes, smiling / not smiling) and facial details (glasses / no glasses). All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position (with tolerance for some side movement).

      Fig 3. AT & T Database

   2. Indian Face Database

      There are eleven different images of each of 61 distinct subjects. All the images were taken against a bright homogeneous background with the subjects in an upright, frontal position. The files are in JPEG format. The size of each image is 64×48 pixels. The images are organized in two main directories – males and females. In each of these directories, there are directories with name as a serial numbers, each corresponding to a single individual. The following orientations of the face are included: looking front, looking left, looking right, looking up, looking up towards left, looking up towards right, looking down. Available emotions are: neutral, smile, laughter, sad/disgust.

      Fig 4. Indian Face Database

   3. University of Essex, UK

   This database consists of 25 individuals (male and female),

   20 images per individual. Contains images of people of various racial origins, mainly of first year undergraduate students, so the majority of individuals are between 18-20 years old but some older individuals are also present. Some individuals are wearing glasses and beards.

   Fig 5. Few Examples of UOE Database

4. SIMULATION RESULTS

   The three algorithms were tested on the three databases and the following results were obtained. These are tabulated as shown below.

   TABLE I. ACCURACY OF ALGORITHMS ACROSS APPROACHES AND DATABASES (PERCENTAGE)

   Database v/s Algorithm	ATT	IFD	UOE
   ICA	91.25	71.67	54.50
   PCA	94.38	71.47	99.58
   LDA	94.38	86.25	100

   TABLE II. EXECUTION TIMES OF ALGORITHMS ACROSS AT & T

   DATABASE (MS/IMAGE)

   Database v/s

   ATT

   ICA

   Algorithm	Training time	Testing time	Total execution time
   7.8	0.1	7.9
   PCA	0.8	0.5	1.3
   LDA	0.4	0.2	0.6

   on all three databases compared to other two algorithms.PCA shows good accuracy performance over the three databases but takes slightly longer time to execute than LDA.

   Future work shall be focused on determining the generalization abilities of these three algorithms. The algorithms will be implemented using a distance metric other than Euclidean distance. We would also like to study the effect of the exact choice of images in a gallery or in a probe set has on face recognition performance. Also, these algorithms will be tested on different databases under varying illumination, poses, and expressions. The difference in the performances will be studied and worked upon for further improvement.

   TABLE III. EXECUTION TIMES OF ALGORITHMS ACROSS INDIAN FACE DATABASE (MS/IMAGE)

   Database v/s Algorithm	IFD
   	Training time	Testing time	Total execution time
   ICA	6.8	0.2	7.0
   PCA	0.8	0.5	1.3
   LDA	0.3	0.1	0.4

   TABLE IV. EXECUTION TIMES OF ALGORITHMS ACROSS UNIVERSITY OF ESSEX DATABASE (MS/IMAGE)

   Database v/s Algorithm	UOE
   	Training time	Testing time	Total execution time
   ICA	10.5	0.1	10.6
   PCA	0.2	0.1	0.3
   LDA	0.2	0.1	0.3

5. CONCLUSION AND FUTURE WORK

This paper presented an independent, comparative study of three most popular appearance based face recognition algorithms (PCA, ICA and LDA) in completely equal working conditions. Euclidean distance metric was used as a classifier to find the best match.

LDA shows best performance both in terms of accuracy as well as execution time over ICA and PCA. ICA algorithm performs just satisfactorily but takes longer time to execute

ACKNOWLEDGMENT

We would like to thank the University of Essex for providing the face database in order to carry out the simulations.

REFERENCES

1. A.F. Abate, M. Nappi, D. Riccio, and G. Sabatino, "2D and 3D face recognition: A survey presented at Pattern Recognition Letters, 2007, pp.1885-1906.

2. H. Moon, "Biometrics Person Authentication Using Projection-Based Face Recognition System in Verification Scenario," in International Conference on Bioinformatics and its Applications. Hong Kong, China, 2004, pp.207-213.

3. P. J. Phillips, H. Moon, P. J. Rauss, and S. A. Rizvi, "The FERET Evaluation Methodology for Face Recognition Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.22, pp.1090-1104, 2000.

4. P. J. Grother, G. W. Quinn, and P. J. Phillips. Multiple biometric evaluation (MBE) 2010, report on the evaluation of 2D still-image face recognition algorithms. Technical report, NIST, 2010

5. Rafael Gonzalez and Richard Woods. Digital Image Processing. Third Edition, 2009.

6. B. Draper, K. Baek, M.S. Bartlett, and J.R. Beveridge, Recognizing faces with PCA and ICA, Compute Vis Image Understand (Special Issue on Face Recognition) 91 (2003), 115137.

7. P.Belhumeur, J.Hespanha, and D.Kriegman.Using discriminant eigen features for image retrieval.PAMI, 19(7):711720, 1997.

8. W.Zhao, R.Chelappa, and N. Nandhakumar. Empirical performance analysis of linear discriminant classifiers. In Proceedings of the 1998 Conference on Computer Vision and Pattern Recognition, pages 164- 169, Santa Barbara, CA, 1998.

9. W.Zhao, R.Chelappa, and P.Philips. Subspace Linear Discriminant Analysis for Face Recognition. Technical Report CAR-TR-914. Centre for Automation Research, University of Maryland, 1999.

10. R. Haeb-Umbach and H.Ney. Linear discriminant analysis for improved large vocabulary continuous speech recognition. In Proc. ICASSP92, pages 1/13-1/16, 1992.

11. Becker, B.C., Ortiz, E.G., "Evaluation of Face Recognition Techniques for Application to Facebook," in Proceedings of the 8th IEEE International Automatic Face and Gesture Recognition Conference, 2008.