Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 4(4), 77-82, April (2015) Res.J.Recent Sci. International Science Congress Association 77 Face Recognition Using Non-negative Matrix Factorization (NMF) An Analysis of Order of Decomposition on Recognition RateNaveed Alam, Muhammad Sarim, Abdul Basit Shaikh, Sheikh Kashif Raffat, Adnan Nadeem and Kamran Ahsan Department of Computer Science, Federal Urdu University of Arts, Sciences and Technology, Karachi, PAKISTAN Available online at: www.isca.in,www.isca.me Received 10th December 2013, revised 15th February 2014, accepted 12th April 2014Abstract Non-negative Matrix Factorization (NMF) is a well established dimension reduction technique. NMF reduces the dimension of the non-negative data matrix by applying the non- negativity constraint. One of the applications of NMF is recognition problem (e-g face recognition). To solve recognition problem using NMF, the order of decomposition play an important role on the recognition rate. This paper presents the details analysis of the order of decomposition on the recognition rate. A standard face dataset A and T is used for analysis. Keywords: Non-negative matrix factorization (NMF), face recognition, dimension reduction. IntroductionFace recognition is one of the most heavily research area in the field of computer vision and pattern recognition for last few decades. Many algorithms are presented to address the problem and the performance of current algorithms decreases on the face images which are captured under different lighting conditions, view angles and expressions. Different approaches are adopted to solve the face recognition problem. Template based approaches1,2 compared the test image to the set of given templates. Statistical techniques like Support Vector Machine (SVM), Principle Components Analysis (PCA), Linear Discriminate Analysis (LDA) 5 and Independent Component Analysis (ICA) can be used to construct the templates. The feature based approachesused local facial features and their geometric relationships to recognize the face image. Some approaches used less information of face feature to recognize in which they process the facial features information separately without considering the relationship between the features and with the whole face. M. Nixon used human eyes as a feature, R. Brunelli and T. Poggio7 utilized a combination of features to recognize the faces. Ashraf et al12 used geodesic distance transform to solved the problem. In model-based approaches developed a human face model for recognition. Generally, these models are morphable and the morphable nature of the model allows them to recognize the human face with the varying face pose. These approaches can be 2D or 3D. The 3D face models are more complicated as compared to 2 D because it attempt to capture the three dimensional features of the human faces. Elastic Bunch Graph Matching9 is the example of the 3D Morphable models. The subspace approaches PCALDAICASub-Holistic11 are the most popular among the methods used for face recognition. PCA, LDA5 and ICA6 are the example of subspace approaches. The first most popular subspace technique is Eigenfaces method (PCA). The conventional Eigen faces method has number of limitations; first it has a poor discriminatory power although it provides a very good representation of the face images. The second limitation is that the basis images of PCA do not provide any natural visual meaning. In addition, the global feature extraction nature of the approach fails to handle the occlusions problem in the images. A powerful subspace technique, named Non-negative Matrix Factorization (NMF)10, is introduced. NMF applied non- negatively constraints on the face images which allow them to handle the occlusion problems in the images. This paper provides the details analysis of the dimension reduction role of NMF technique in the face recognition problem. Non- Negative Matrix Factorization (NMF) Non- negative matrix factorization (NMF)10 is used to determine the linear approximate representation of a non-negative data matrix. For a data matrix X where each column matrix ‘m’ represents the dimension of the data and ‘n’ is the number of samples. The NMF provides the linear approximation of data matrix X is given as \nWhere, W is a basis matrix with columns representing basis vector and H is a coefficient matrix with columns as coefficient vector. The constant d is the rank of the approximation and to achieved the dimension reduction its value is chosen as (m + n) d n × m. Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(4), 77-82, April (2015) Res.J.Recent Sci International Science Congress Association 78 Algorithm 1 Basic ALS Algorithm for NMF 1: procedure ALS(X) 2: 3: W = rand (m; k); 4: Initialize W as random dense matrix 5: for i = 1 - maxiter (LS) do 6: 7: W T WH = W T X (NonNeg) 8: Solve for H in matrix equation 9: Set all negative elements in H to 0 10: HH T W T = HX T (NonNeg) 11: Solve for W in matrix equation 12: Set all negative elements in W to 0 13: end for 14: end procedure For a given matrix X, the optimal value of W and H can be obtained by iteratively minimizing the error function, \r \rThe product of WH is called NMF of X. Alternate least square optimization method is used to minimize (2) due to its fast convergence rate and consistency. Face Recognition Using Non- Negative Matrix Factorization (NMF) A standard database for face recognition AT& T is used. The algorithm of the system is implemented in the Mat lab the details are given below. Initially, the pre-processing is performed on the images of given data set which involve the resizing of the original images. After preprocessing on images of database build the training set for the NMF algorithm. The training set A is formed by linearizing the 2-D images and then arrange the images in such a way that the each column representing the single image. train      ! ! " The dimension of the training set A is m×n, where m is the dimension of each image and n is the total number of images in the training set A. The NMF algorithm is applied to the training set Atrain. train=Wtraintrain Where: W is the basis matrix with the dimension m×r and H is the coefficient matrix with the dimension of r×n. The constant r represents the order of decomposition. The WH is a lower-rank approximation to Atrain. The basis matrix Wtrain of the training set Atrain is used to approximate the test image Ttest as =Wtrainp The above equation provides the coefficient matrix Htest to the test image B. The most closest column matrix F, representing a face, in the training set Atrain, to F is obtained by minimizing equation () over the entire training set Atrain as $%&'()* ,-./Results and Discussion The algorithm used the standard database AT and T for evaluation. The database contains 40 classes and each class has 10 images. The algorithm used 5 images for training and testing. The recognition criteria of the purposed algorithm are that for each test images. It should have the top 5 matches to the same class of the test image for 100 percent recognition. The algorithm is tested on the number of training classes 10, 20 and 40 classes. Per class recognition is also calculated for class. To observe the order decomposition role on the recognition varying the order of decomposition from 1 to 20. Training classes: The training set comprised of 10 classes in which 50 images used for training and testing. The average recognition rate can be calculated by repeating the experiment 10 times. The optimal average recognition rate for all the test images is 98% at the decomposition order of 18 as shown in figure-2 while figure-3 represents the per test class recognition rate as it seen that class 6 has 100 percent recognition rate. Training classes: The training set comprised of 20 classes in which 100 images used for training and testing. The average recognition rate can be calculated by repeating the experiment 10 times. The optimal average recognition rate for all the test images is 92% at the decomposition order of 16 as shown in figure-4 while figure-5 represents the per test class recognition rate. 40 training classes: The training set comprised of 40 classes in which 400 images used for training and testing. The average recognition rate can be calculated by repeating the experiment 10 times. The optimal average recognition rate for all the test images is 81% at the decomposition order of 15 as shown in figure-6 while figure-7 represents the per test class recognition rate. This section provides the comparison of proposed algorithm with PCA as shown in table-1 Table-1 Comparision with PCA No. of Classes NMF PCA 10 98% 94.6% 20 92% 88.3% 40 81% 76.8% Research Journal of Recent Sciences ______ ______________________________ Vol. 4(4), 77-82, April (2015) International Science Congress Association Five Classes of Training data Set T Recognition rate against decomposition order (between 1 to 20) for ten ______________________________ __________ _______________ International Science Congress Association Five Classes of Training data Set Five Classes of Testing Data Set Figure-1 T raining and testing Images of datasetFigure-2 Recognition rate against decomposition order (between 1 to 20) for ten numbers _______________ ISSN 2277-2502 Res.J.Recent Sci 79 Five Classes of Testing Data Set numbers of classes Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(4), 77-82, April (2015) Res.J.Recent Sci International Science Congress Association 80 Figure-3 Recognition rate of each classFigure-4 Recognition rate against decomposition order (between 1 to 20) for 20 numbers of classes Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(4), 77-82, April (2015) Res.J.Recent Sci International Science Congress Association 81 Figure-5 Recognition rate of each class Figure-6 Recognition rate against decomposition order (between 1 to 20) for 40 numbers of classes Research Journal of Recent Sciences _____________________________________________________________ ISSN 2277-2502Vol. 4(4), 77-82, April (2015) Res.J.Recent Sci International Science Congress Association 82 Figure-7 Recognition rate of each class Conclusion This paper presents face recognition using NMF and also provides the details analysis of the role of order of decomposition on the recognition rate. It can be concluded from the obtain results that order of decomposition has an important role on the recognition rate. References 1.Torres L., Is there any hope for face recognition?, In Proc. of the 5th International Workshop on Image Analysis for Multimedia Interactive Services, WIAMIS, Lisboa, Portugal, 21-23, (2004)2.Gross R., Shi J. and Cohn J., Quo vadis face recognition?, The current state of the art in face recognition, Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA, (2001)3.Guo G., Li S. and Chan K., Face recognition by support vector machines, In Proc. of the IEEE International Conference on Automatic Face and Gesture Recognition, 196–201, Grenoble, France, (2000)4.Moghaddam and Pentland A., Probabilistic visual learning for object representation, IEEE Transactions on Pattern Analysis and Machine Intelligence,19(7), 696–710 (1997)5.Belhumeur P., Hespanha J. and Kriegman D., Eigenfaces vs. fisherfaces: Recognition using class specific linear projection, IEEE Transactions on Pattern Analysis and Machine Intelligence,19(7), 711–720 (1997)6.Bartlett M., Movellan J. and Sejnowski T., Face recognition by independent component analysis, IEEE Trans. on Neural Networks,13(6), 1450–1464 (2002) 7.Brunelli R and Poggio T., Face recognition: Features versus templates, IEEE Transactions on Pattern Analysis and Machine Intelligence,15(10), 1042–1052 (1993)8.Nixon M., Eye spacing measurement for facial recognition, Proceedings of the Society of Photo-Optical Instrument Engineers, SPIE,575(37), 279–285 (1985)9.Wiskott L., Fellous J.M., Krueuger N and von der Malsburg C., Face recognition by elastic bunch graph matching, IEEE Trans on Pattern Analysis and Machine Intelligence,19(7), 775–779 (1997) 10.Lee D.D. and Seung H.S., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999)11.Muhammad Sharif S.M.M.R., Shah J.H., Sub-holistic hidden markov model for face recognition, Res. J. of Rec. Sci.,2(5), 10–14 (2013)12.Ahsraf M., Sarim M., Shaikh A.B., Raffat S.K. and Siddiq M., Face recognition using weighted distance transform, Res. J. of Rec. Sci., (2013)