Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 3(9), 19-25, September (2014) Res.J.Recent Sci. International Science Congress Association        
19
 
Face Recognition using Weighted Distance TransformMuhammad Ashraf, Muhammad Sarim, Abdul Basit Shaikh, Sheikh Kashif Raffat, Adnan Nadeem, Kamran Ahsan and Muhammad Siddiq Department of Computer Science, Federal Urdu University of Arts, Sciences and Technology, Karachi, PAKISTANAvailable online at: 
www.isca.in
, 
www.isca.me
Received 11th October 2013, revised 29th December 2013, accepted 28th February 2014Abstract  In recent years the task of ecognizing human face with the help of a machine has acquired a significant attention among researchers. A wide range of commercial and law enforcement applications largely accounts for this developing trend. Although current face ecognition systems have reached a certain maturity level they are still far away from the capability of human perceptual system. In a 2D image the unique facial appearance normally consists of intensity curvatures which may be incorporated for ecognizing human face. This work inestigates the use of weighted distance transform to bring improvements in face ecognition. The weighted  distance  transform takes  into account  both  the  spatial  distance  among  pixels  and  the  local intensity  variations.  A standard face dataset is used to alidate the proposed method.  The obtained results are comparable to the state-of-the-art face ecognitiontechniques. Keywords: Weighted distance, geodesic paths, face, recognition, fast marching, facial curvature. IntroductionThe problem of face recognition has received a significant attention among researchers, specially during the last two decades. The emergence of international conferences on face recognition evidences this increasing trend1,2,3. At least two reasons support this: first one is the availability of feasible technology and the second one is its wide range of commercial and law enforcement applications. The task of recognizing human face through machines also attracted researchers from other disciplines such as image processing, pattern recognition, computer graphics and the psychology. The biometric methods are often used for personal identification, for example fingerprint analysis and the retinal or iris scans. These methods are very reliable but they totally rely on participant’s cooperation. In contrast to the conventional biometrics, the personal identification systems which are based on the analysis of frontal or profile face images may perform more effectively without the participant’s cooperation or knowledge. Both the commercial and the law enforcement applications of face recognition techniques range from still photographs to the images from video sequence. That is why we can categorize face recognition systems into the two broad groups depending on whether the input is still photographs or the video. Within these groups significant differences exist in terms of image quality, level of clutter in background, variation in images of particular individual, and the availability of matching criterion. A general statement for the problem of recognizing human face through a machine can be formulated as follows: given still or video images of scene, identify or verify one or more persons in the scene using the stored face database. The solution to the problem of face recognition involves following three sub-tasks: i. Segmentation of faces from the cluttered scene (face detection), ii. Feature extraction from the face regions, iii. Recognition or verification. Research on each sub-task is critical not only because the techniques used for individual sub-tasks need a persistent improvement but also because they play a critical role in many other applications. In recognition problems an unknown face is given to the system, and the system determines its identity from a database of known individuals, whereas in verification problems, the system confirms or rejects the claimed identity of the given face. Face recognition is an important part of the capability of human perceptual system. It is a normal routine task for humans whereas the face recognition in computer vision is still an on-going research area.  A fully automated face recognition system must perform all of the three sub-tasks while the partially automated face recognition system only performs the last two sub-tasks. The face recognition is highly dependent on feature extraction methods which can be distinguished as generic methods face templates based methods and the structural matching methods. The generic methods are based on edges, lines, and the curves. The face templates consist of the facial features such as eyes, nose and the mouth. The structures consider the geometrical constraints on facial features. Many face recognition methods additionally require facial features along with holistic face. Some authors categorized face recognition techniques into holistic and the feature based approaches depending on the input criterion. Even holistic techniques which take whole image as the input need accurate locations of key facial features such as eyes and nose to normalize and properly align the input image4,6. The feature based techniques take facial features as the input but they have difficulty when the appearance of the facial features gets a significant change such as eyes with glasses, closed eyes, and the open mouth. A digital camera captures the 3D human face in a 2D image using intensity curvatures. As the 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
20
facial appearance in 2D images consists of intensity curvatures, we proposed a face recognition technique which incorporates these curvatures. We have used the weighted distance transform for extracting intensity curvatures. It is a transform that works in spatio-intensity domain. It uses not only the spatial distance among neighboring pixels but also considers the local intensity variations among them. For characterizing shape changes of amoebas the signed weighted distance can be applied to biological cells. The unsigned weighted distance of each pixel x from seed point is defined by following equations: \n\rwith \n\r	#$%&	'
where, M is the mask containing seed point ,  the local intensity variations, a,bthe set of all paths between the points a and b; and  
(
)
indicates one such path. 

'(s)
is the spatial  derivative and u  is the unit vector tangent to the direction of the path. The factor  weighs the contribution of the local intensity variation versus spatial distances. The weighted distance D reduces to Euclidean distance when = 0. The unsigned weighted distance can be computed using the algorithms of “raster scan” or the “wavefront propagation”. The “raster scan” algorithms are based on kernel operations which are sequentially applied over image in multiple passes. Whereas the “wavefront propagation” algorithms are based on the iterative propagation of a pixel front with velocity “F”10. The unsigned weighted distance contains redundant information about facial intensity curvatures. For extracting more discriminating information from unsigned weighted distance we have drawn multiple trajectories (geodesic paths) on face. The trajectories were drawn in such a way that they must cover the face regions having prominent intensity curvatures. The computed “weighted distance” and the drawn trajectories can be seen in figure 2. we may increase the contents of more discriminating information by increasing the number of trajectories to be drawn on face but the practical requirements limit a large number of trajectories (geodesic paths) because of large computational effort and memory demands. After the trajectories are drawn they are parameterized to construct feature vectors. The feature vectors were fed to the classifier which determines the identity of the given image on the basis of stored training faces. Several classifiers such as Neural Network, Support Vector machine have been used to perform classification/recognition. We used the KNN classifier which uses the distance measures for classifying/ recognizing the given face. In this work MATLAB Fast Marching Toolbox is used for computing weighted distance transform. The toolbox also draws trajectories on face if their terminal loci are provided. We have used a standard face data base that contains 8 images for each of 124 individuals, a total of 992 face images. We selected two frontal face images of each individual for testing. The remaining 6 images of each individual are used for training. The system pre-processes these images before computing the weighted distance. Related Work: A huge research work has been done on the problem of face recognition in last four decades. This section gives the brief overview of different recognition techniques. The Principal Component Analysis11,12 is one of the face recognition techniques which take holistic face images as input. First a subset of Eigenfaces (principal components) is derived from statistical analysis of stored face images. In this technique Eigenfaces are considered as a set of standardized face ingredients. Each face in data set can be derived by combining the obtained face ingredients. Then feature vectors are obtained for stored images by projecting them in the space of principal components. For recognizing a person its face image is projected in the space of principal component. Then its feature vector is fed to the classifier which matches it to the feature vectors of stored images for determining person identification. This technique shows good performance only under uniform lighting conditions for frontal face images. For deriving principle components, it needs properly aligned normalized images which require the determination of facial features location. The recognition rates of this technique decreases as the number of the classes in dataset increases. Discrete Cosine Transform is a well established data compression technique, which is similar to the Fourier transform but considers only real components. It was first time introduced by Ahmed, Natarajan and Rao in early 70s. Ever since, the DCT has grown its popularity. Wang (1984) categorized DCT into four slightly different transformations named DCTI, II, III and IV, it was used for dimension reduction13. Like PCA the Face Recognition using DCT also takes holistic face images as input5,14. For extracting facial features DCT is computing DCT on cropped input faces. Then a feature vector is derived by taking a small subset of DCT Coefficients in a zigzag pattern. These feature vectors are fed to different classifier for face recognition. This technique performs well under both lighting conditions (i.e. uniform and varying illumination) but it also requires properly aligned and normalized face images. An energy histogram is similar to color histogram but instead of counting pixel color, an energy histogram accumulates the DCT coefficients in corresponding bins. In comparison, energy histogram incurs less computational cost when compared to the color histogram as its dimensions are greatly reduced by the DCT. The DCT was reported to be the second most optimal transformation after PCA with an energy compaction15. It offers numerous advantages over PCA including good computational efficiency whilst producing good quality images at suitable 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
21
compression ratios15,16. The DCT in the energy histogram is implemented through a similar approach as in the JPEG compression. The approach in feature extraction computes the DCT on individual subsets of each facial image where images are first divided into 8 x 8 blocks15. The energy histograms were investigated by Lay and Guan, for image retrieval17. They proposed feature sets identifying similarities of the image. The feature set was consisted of 6 feature blocks, denoted F1, F2A, F2B, F3A, F3B, and F416. The energy histogram is built by counting the number of times each DCT coefficient occurs in the domain of the corresponding bin. This energy histogram is then used as the feature vector. To recognize a face image, the feature vector v of the query image is compared to each of the feature vectors f in the database using the Euclidian distance classifier. If the distance between v and f falls below a threshold, then the images are classified as a matched; otherwise, it is an unmatched. The thresholds, is computed via intra and inter class information gathered from the training dataset. The Sub-Holistic Hidden Markov Model is based on a Hidden Markov Model similar to the simplest dynamic Bayesian Network. In Sub-Holistic Hidden Markov Model the template modules are extracted from a test image, which are then used in recognition process18. Methodology The implementation of the proposed method involves following sub-tasks. The sequence in which the sub-tasks are performed can be seen in figure 1. i. Pre-processing of Image, ii. Computation of weighted distance transform, iii.  Drawing trajectories (geodesic paths) on face, iv. Parameterization of trajectories, v. Classification using different Numerical measures.  Pre-processing of Image: In this task a color image which contains the color information of each pixel is converted into gray-scale image. The gray-scale image contains only the intensity information of pixels. The intensity variations in gray-scale face image correspond to the facial intensity curvatures. The task of pre-processing may involve resizing of the given image if it is not comparable to the stored images. The computation of weighted distance transform requires a seed point . In pre-processing the  is located at nose tip on frontal faces. If size of a stored image is too large then whilst the geodesic path is well defined, the computational requirements increase without a corresponding improvement in recognition. In such cases the task of pre- processing may also involve resizing of stored images. Computation of Weighted Distance Transform: The proposed method heavily depends on facial intensity curvatures therefore the weighted distance transform is an essential attempt to extract intensity curvatures from a D image. In this work it is computed using toolbox Fast Marching. As the location of seed point may have an effect on the contents of resultant weighted distance, we considered six different locations on face to investigate the facial intensity curvatures contained in weighted distance. The weighted distance computed from each location of seed point can be seen in figure 2. Fast Marching Method (FMM): The toolbox Fast Marching contains the Fast Marching Method (FMM) which is one of the “wavefront propagation” algorithms. It takes into account the information that only flows outwards from seeding point. The FMM is based on Dijkstras algorithm which has been employed to identify a shortest network path. James A. Sethian10, 19introduced this method for solving boundary value problems of the Eikonal equation: +,\n-In boundary value problems related to the evolution of a closed curve is defined as function of time . The evolution speed  of closed curve always directs normal to the curve at any point on closed curve. The boundary value problem solved by fast marching method is a special case of level set methods. Level set methods are slower then fast marching method. Drawing of Trajectories (Geodesic aths): As the distance-transform returns redundant intensity curvatures, we need to extract the more discriminating information out of facial intensity curvatures contained in resultant of “weighted distance transform”. Figure-1 Block Diagram of Proposed Method 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
22
Therefore a trajectory (geodesic path) is another attempt that extracts more discriminating intensity curvatures. For drawing a trajectory we also need its ending point location in addition to the location of seed point . To cover the whole face region we defined loci of end points at the elliptical boundary of face. Initially we defined 60 trajectories (geodesic paths) on face which can be seen in figure 2. As the number of trajectories also affects the contents of more discriminating curvatures we investigated to determine the optimal number of trajectories required to obtain sufficient information for improving the recognition rate. The different number of trajectories on face can be seen in figure 3. Along with computing weighted distance the task of drawing trajectories on face was also performed using toolbox Fast Marching. Parameterization of ajectories: For the sake of comparison we need to parameterize the trajectories (geodesic paths) drawn on face. As the discriminating curvatures of a trajectory contain the key information about facial intensity curvatures, the parametric representation of a trajectory should essentially reflect the discriminating curvatures in order to enable face recognition. Initially we parameterized each trajectory by taking two equidistant points. As the number of points (taken on a trajectory) has a direct relation to the contents of curvatures reflected in parametric representation, we investigated for determining the optimal number of points required to parameterize a trajectory. The different number of equidistant points taken on trajectories can be seen in figure 4.Figure-2 Trajectories Patterns at different loci of seed point Figure-3 Different number of trajectories 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
23
Figure-4 Selection of equidistant Points Figure-5 Parametric Representation of a Trajectory (geodesic path) We obtained the following information for each point taken for the parametric representation of a trajectory: i. Coordinates; ii. Displacement from seed point ; iii. Distance along the trajectory between two consecutive points; iv. Displacement between corresponding points of adjacent trajectories; We utilized the collected information to construct a feature space for each image. The parametric representation of a trajectory reflecting the distinguishing curvatures is shown in figure 5, where i. (x, y) . . . the co-ordinates of seed point ; ii. (x, y) . . . the co-ordinates of points i; iii. D . . . the displacement of point i from seed point ; iv. S . . . the distance between two consecutive points i and i 	 . . . the displacement between corresponding points i on two adjacent trajectories. The construction of feature space is formulated as follows: /0	\n123/04/05634	1/0	\n912/;4/;63/;(	4/;(	;(/0	\n12/04/063/(0	4/(0	\n./0	9@\n-AB*9C9D\n-AE\n3/04/0	9@\n-AB*9C9D\n-AE\n8/09@\n-AB*9C9D\n-AE\n&#x3.47;�/0	9@\n-AB*9C9D\n-AE)8\n9I(where the subscripts j and i indicate trajectory and the point numbers respectively, , . . . ,   are showing the information of  displacement from  seed  point  , co-ordinates, distance along paths, and the displacement between corresponding points respectively. To examine the recognition due to individual information we separately fed , ,   and   to the classifier. We also examined the recognition by merging these information and observed an improvement in recognition on assigning a weight    to each of , . . . , . We manually set the value of t on the basis of recognition rate due to individual information. Results and DiscussionThe method is evaluated on the basis of following parameters: i. The no of trajectories drawn on face; ii. The number of points taken on a trajectory; iii. The location of seed point ; iv. The individual information contained in V1,...,V4; v. The number of classes, vi. Comparison with current recognition techniques (PCA and DCT); The evaluation is performed using 8 images for each class (person), where 6 images are taken for training and the remaining two for testing. The Effect of Number of Trajectories: The curvatures of a trajectory represent intensity curvatures contained in weighted distance. The representation of intensity curvatures can be improved on increasing the number of trajectories drawn on face. Therefore we have drawn 10 to 90 trajectories on each face. The effect of number of trajectories on recognition rate is shown in figure 6. The results indicate that an increase in number of trajectories also improves recognition rate. Optimal number of trajectories drawn on a face appears to be between 40 to50. The Effect of Number of oints: The parametric representation of a trajectory is based on number of equidistant points taken on it. We selected 2 to 20 points on each trajectory for its parametric representation. The effect of the number of points on recognition rates is shown in figure 7. The results indicate that an increase in the number of points significantly improves recognition rate when a few points are 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
24
taken on each trajectory but it does not affect recognition rate when a large number of points have already been taken. The figure 6 also shows the effect of number of points on recognition rate which is prominent on fewer trajectories but very little on large number of trajectories. Optimal number of points is found between 12 and 16, which is co-related to the number of trajectories drawn on face. Figure-6 Effect of Number of Trajectories The Effect of Seed Point Location: Because the location of seed point affects the contents of weighted distance, we selected six different locations for seed point . Each location of seed point generates a different unique pattern of trajectories on face which can be seen in figure 2. The generation of a different pattern for each location has a clear effect on recognition rate which can be seen in figure 7. The patterns generated by seed location 4 produces better recognition rates as compared to other patterns because it cover facial curvatures of chin region more appropriately which can be seen in figure 2. The Effect of eatures: In parametric representation of a trajectory we obtained information of four different types (features) for each point. We separately collected each type of information in the formulation of feature space constructed for a face image. The effect of individual information on recognition rate can be seen in figure 8. If we gather the information of four different features in a hybrid manner the optimized results are obtained which are also shown in figure 8. The Effect of Number of Classes: It is a well known fact that most of the recognition techniques degrade their performance in terms of recognition rate and the time taken to recognize a person on large datasets. Therefore we used 40, 60, 80, 100, 120 classes to evaluate the performance of proposed method. The effect of number of classes on recognition rate is shown in table 1. Comparison: The comparative evaluation is shown in table 1, where the better performance of proposed method in terms of recognition rate can be seen. The improvement in recognition rate shows that the use of intensity curvatures can play a vital role in face recognition. 
 
Figure-7 Effect of Seed Locations Figure-8 Recognition due to Individual feature and overall Combined Result Table-1 Comparision with DCT and PCA No. of Classes Our Method DCT PCA 
40 97.3% 98.2% 96.6% 
60 95.4% 95.2% 92.3% 
80 94.9% 94.5% 88.8% 
100 94.3% 92.3% 83.0% 
120 94.0% 92.2% 83.0% 
Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 19-25, September (2014) Res. J. Recent Sci.   International Science Congress Association 
25
ConclusionThe investigation indicates that the facial intensity curvatures can play a critical role in face recognition. The use of weighted distance transform for extracting intensity curvatures shows promising results. The determination of exact loci for end points of trajectories is the main problem which highly affects the recognition rate of proposed method. Comparison against well established techniques such as PCA and DCT showed comparable results, which suggests that the local facial structure plays an important role in face recognition. Future work would include the determination of facial boundary location which may improve the recognition rate. The use of machine learning algorithms would also be investigated to increase robustness and accuracy. References1.Phillips P. J., Grother P., Micheals R., Blackburn D.M., Tabassi E. and Bone M., Face recognition vendor test 2002, Anal. And Mod. of Faces and Gestures 2003, AMFG 2003, IEEE International Workshop, (2003)2.Phillips P.J., Moon H., Rizvi S.A. and Rauss P.J., The feret evaluation methodology for face-recognition algorithms, Pattern Anal. and Machine Intelligence, IEEE Transactions, 22(10), 1090–1104 (2000)3.Phillips P.J., Wechsler H., Huang J. and Rauss P.J., The feret database and evaluation procedure for face-recognition algorithms, Image and vision comput, 16(5), 295–306 (1998)4.Zhao W., Chellappa R., Phillips P.J. and Rosenfeld A., Face recognition: A literature survey, Acm Comput. Surveys (CSUR),35(4), 399–458 (2003)5.Hafed Z.M. and Levine M.D., Face recognition using the discrete cosine transform, Int. J. of Comp. Vision, 43(3), 167–188 (2001)6.Sadeghi R., A comparative face recognition algorithm for dark places, Res. J. of Rec. Sci.,2(9), 92–94 (2013)7.A. Kokou M., and Antoine V., Shape characterization on phase microscopy images using a dispersion indicator: Application to amoeba cells, Res. J. of Comp. and Info. Tech. Sci.,1(5), 8–12 (2013)8.Criminisi A., Sharp T., and Blake A., Geos: Geodesic image segmentation, Computer Vision–ECCV, Springer, 99–112, (2008)9.Borgefors G., Distance transformations in digital images, Computer vision, graphics, and image processing, 34(3), 344–371 (1986)10.Sethian J.A., Fast marching methods, SIAM review, 41(2), 199–235 (1999)11.Prasad M., Panda S., Deepthi G. and Anisha V., Face recognition using pca and feed forward neural networks, Int. J. of Comp. Sci. and Tele.,2(8), 79–82 (2011)12.Perlibakas V., Face recognition using principal component analysis and wavelet packet decomposition, Informatica, 15(2), 243–250 (2004)13.Er M.J., Chen W. and Wu S., High-speed face recognition based on discrete cosine transform and rbf neural networks, Neural Networks, EEE Transactions, 16(3), 679–691 (2005)14.Lai J.H., Yuen P.C. and Feng G.C., Face recognition using holistic fourier invariant features, Pattern Recognition, 34(1), 95–109 (2001)15.Tjahyadi R., Liu W. and Venkatesh S., Application of the dct energy histogram for face recognition, ICITA 2004, Proc. of the Second International Conference on Information Technology and Applications, 314–319, IEEE, (2004)16.Tjahyadi R., Liu W., An S. and Venkatesh S., Face recognition via the overlapping energy histogram, IJCAI, 2891–2896 (2007)17.Lay J.A. and Guan L., Image retrieval based on energy histograms of the low frequency dct coefficients, Acoustics, Speech and Signal Processing, IEEE International Conference, , 3009–3012 (1999)18.Muhammad Sharif S.M.M.R. and Shah J.H., Sub-holistic hidden markov model for face recognition, Res. J. of Rec. Sci.,2(5), 10–14 (2013)19.Sethian J.A., A fast marching level set method for monotonically advancing fronts, Proc. of the National Academy of Sciences, 93(4), 1591–1595 (1996) 
<end><end><end><end><end><end><end><end>