Genetic-Based Selection and Weighting for LBP, oLBP, and Eigenface Feature Extraction Tamirat Abegaz#, Gerry Dozier#, Kelvin Bryant#, Joshua Adams#, Brandon Baker# ,Joseph Shelton#, Karl Ricanek^, Damon L. Woodard* #orth Carolina A&T State University ^The University of orth Carolina at Wilmington *Clemson University Abstract— In this paper, we have investigated the use of function specific to the problem at hand. Parents are then genetic-based feature selection (GEFeS), genetic-based selected based on fitness. New FSs are produced from the feature weighting (GEFeW) on feature sets obtained by selected parents by the processes of reproduction. Survivors Eigenface and LBP. Our results indicate that GEFeS and are selected from the previous generation and combined with GEFeW enhances the overall performance of both the the offspring to form the next generation. This process Eigenface and LBP-based techniques. Compared to continues for user specified number of cycles. Eigenface hybrid, our result shows that both LBP and This work is an extension of the research performed by oLBP hybrids perform better in terms of accuracy. In Abegaz et. al [10]. In their work, Abegaz et al. used Genetic addition, the results show that GEFeS reduces the number and Evolutionary Feature Selection (GEFeS), GEFeS+ (which of features needed by approximately 50% while obtaining is a co-evolutionary version of GEFeS) , and Genetic and a significant improvement in accuracy. Evolutionary Feature Weighting (GEFeW), Eigenface algorithm. In their work, Abegaz et. al. reported that Eigen- Keywords— Local Binary Pattern (LBP), Eigenface, Steady GEFeS, Eigen-GEFeS+, and Egen-GEFeW enhanced the State Genetic Algorithm (SSGA), Overlapping Patches, overall performance of the Eigenface method while reducing Feature Selection. the number of features needed. Comparing Eigen-GEFeS, Eigen-GEFeS+, and Eigen-GEFeW, they reported that Eigen- I. INTRODUCTION GEFeW performed best in terms of accuracy even though it Feature Selection is a computational technique that used a significantly larger number of features as compared to attempts to identify a subset of features that are most relevant either Eigen-GEFeS or Eigen-GEFeS+. In this paper, we to a particular task (such as biometric identification) [1]. The extend the work of Abegaz et. al compare GEFeS, GEFeS+, ideal feature selection technique removes those features that and GEFeW hybrids using Eigenface, LBP, and overlapped are less discriminative and keeps those features that have high LBP (oLBP). discriminatory power. A number of feature selection Our work is partly motivated by the research of Gentile et. techniques have been developed and can be classified as: al [11, 12]. Gentile et. al proposed a hierarchical two-stage Enumeration Algorithms (EAs), Sequential Search Algorithms process to reduce the number of feature checks required for an (SSAs), and Genetic Algorithms (GAs). EAs guarantee the iris-based biometric recognition system. The claimed that a optimal subset of features by evaluating all possible subsets of shorter representation of the iris template by pre-aligning the the features. This works well for a very small sized feature probe to each gallery sample and generate a shortlist of match sets, however, it is computationally infeasible when the size of candidates. Our target is a similar system for Face the feature set is large [2]. Recognition (FR) based on short length biometric templates SSAs attempts to divide a feature set, U, into two subsets that are able to achieve higher recognition accuracies. of features, X, and Y, where X denotes the selected features The remainder of this paper is as follows. Section II and Y denotes the remaining ones. Based on user specified explains the feature extraction techniques used as input for the criteria, SSAs select the least significant features from the GEFeS, GEFeS+, and GEFeW. Section III provides an subset X and moves those features into Y while selecting the overview of GEFeS, GEFeS+, and GEFeW. Section IV most significant features from Y and moving them into X. presents our experiment, and in Section V we present our While SSAs are suitable for small and medium size problems, results. Finally, our conclusions and future work are presented they are too computationally expensive to use on large in Section VI. problems [2]. GAs attempt to find an optimal (or near optimal) subset of II. FEATURE EXTRACTION USING EIGENFACE, LBP, AND OLBP features for a specific problem [3, 4, 5, 6, 7, 8, 9, 10]. First, a In a typical biometric system, the task of sample acquisition number of individuals or candidate Feature Subsets (FSs) are and feature extraction are always performed [13]. Sample generated to form an initial population. Each FS is then acquisition is the gathering of biometric traits such as evaluated and assigned a fitness obtained from the evaluation fingerprints, iris scan, periocular images, or facial images. From the acquired sample, feature extraction is performed to III. GEFES, GEFES+, AND GEFEW create a feature vector to be used for comparison. In the case GEFeS, GEFeS+, and GEFeW were designed for selecting of a facial biometric sample, Eigenface and LBP are and/or weighting the most discriminatory features for commonly used feature extractors. For a typical feature recognition. GEFeS, GEFeS+, and GEFeW are instances of a extractor, the pre-enrolled images (and their associated feature Seady State GA(SSGA) with in eXplanatory Toolset for the vectors) are stored in a database commonly referred to as Optimization Of Launch and Space Systems (X-TOOLSS) gallery [13], while newly acquired images (and their feature [19]. In order to describe GEFeS, consider the following vectors) are called probes [13]. feature vector. For Eigenface based feature extraction [14], each image in the training dataset was converted into a single vector. This conversion is necessary because one needs a square matrix (transformation matrix or covariance matrix) to compute the Eigenvectors (Eigenfaces) and the Eigenvalues . The gallery Figure 1: Sample feature vector images have been used to construct a face space spanned by the Eigenfaces. Each image is then projected into the face Furthermore, consider the vector shown in Figure 2 as a space spanned by the Eigenfaces. 560 discriminatory feature candidate real-coded feature mask. weights were extracted for each image and stored for the feature selection experiments. For LBP based feature extraction [15, 16], an image is first divided into several patches (blocks) from which local binary Figure 2: Real-Coded Feature Mask patterns are extracted to produce histograms from every non- border pixels. The histogram obtained from each patch is For GEFeS a masking threshold value of 0.5 is used to concatenated to construct the global feature histogram that create a binary coded candidate feature mask which will be represents both the micro-patterns and their spatial location. In used as condition for masking features. If the random real other words, the histograms contain description of the images number generated is less than the threshold (0.5 in this case), on three different levels of localities. The first one indicates then the value corresponding to the real generated number is that the labels for histograms contain information about the set to 0 in the candidate feature mask vector or 1 otherwise. pattern on a pixel level. Second, the summation of the labels The candidate feature mask is used to mask out a feature set obtained in the patch level to produce the information on a extracted for a given biometric modality. Figure 3 shows the regional level. Finally, the histograms at the regional level are candidate binary coded feature mask matrix obtained from the concatenated to produce the global descriptor of the image. random real numbers generated in Figure 2. The masking The standard LBP uses those labels which have at most one threshold value is applied on the real numbers to obtain the 0-1 and one 1-0 transitions when viewed as a circular bit binary representation string. Such labels are known as uniform patterns [17] For uniform pattern LBP, every patch (block) consists of    bins where   represents the bins for the patterns with two transitions [18]. The remaining three bins represents the bins for the patterns with 0 transitions (all zeros Figure 3: Binary coded candidate feature mask (00000000) and all ones (11111111), and for all non-uniform patterns (bin that represents more than two transitions) [18]. When Comparing the candidate feature mask with the The total number of histogram is computed using the formula, feature matrix, if a position corresponding to the feature       , where represents the number of blocks matrix value in the candidate feature mask is 0 then that and P represents the of sampling points. For our research, we feature value will be masked out from being considered in the use  =8, and =36 to obtain a feature vector of 2124. distance computation. Figure 4 shows the result of the features oLBP based feature extraction [18] is a variant of LBP that in Figure 1 when feature masking (Figure 3) is applied to a attempts to include the internal border pixels that are left out feature vector. during the process of logical portioning on the standard LBP feature extraction method. This is done by logically overlapping the patches horizontally, vertically, and both horizontally and vertically with a one pixel overlap. This provides information to determine whether including the Figure 4: The Resulting feature vector after feature middle border pixels have impact on the recognition rate of masking the LBP based face recognition algorithm. GEFeS + is a co-evolutionary version of GEFeS where that instead of using the static threshold value of 0.5, we evolve a threshold value between 0 and 1. So each random number generated using a uniform distribution has a masking threshold value that determines whether the feature accuracy is computed using the results obtained from the 30 corresponding to features is masked out or not. runs. The best accuracy is selected from the run that resulted For GEFeW, the real-coded candidate feature mask is used in the smallest number of errors. to weight features within the feature matrix. The real-coded ANOVA and t-Tests were used to divide the GEFeS, candidate feature mask value is multiplied by each feature GEFeS+, GEFeW instances and the baseline algorithms into value to provide a weighted feature. If the number generated equivalence classes. As shown in Table 1, comparing the is 0 (or approximately equal to 0) the feature value is 0, which baseline algorithms, the Eigenface method performs best. The basically means that the feature is masked. results show that when using 100 percent of the features, the As given in Equation 1, the fitness returned by the maximum accuracy obtained for the baseline LBP was evaluation function is the number of recognition errors 70.36%. While the BaselineLBPBest performs slightly better encountered after applying the feature mask multiplied by 10 than the baseline BaselineLBP, it still uses the entire feature set plus the percentage of features used. The selection of the As can be seen in Table 1, applying GEFeS on the feature set parent is based on smaller fitness values because the extracted by the standard LBP significantly improves optimization goal is to reduce the number of recognition accuracy from a 70.36% to 96.62%. This result shows that errors (i.e. increasing the accuracy) while reducing the number GEFeS is actually masking out those features which are less of features. relevant for recognition. This improvement in accuracy comes also with a reduction in the number of features used for         (1) recognition. TABLE I IV. EXPERIMENTS EXPERIMENTAL RESULTS OF THE LBP BASELINE, OLBP AND The dataset used in this research is a subset of the Face THE EIGENFACE METHODS Recognition Grand Challenge (FRGC) dataset [20]. In our Methods Number of % Best dataset, 280 subjects were used, with each subject having a Features Used Accuracy Accuracy total of 3 associated images with it. Out of 840 images, 280 BaselineLBP 2124 70.36 70.36 were used as probe and 560 images were selected for training BaselineoLBPbest 2124 70.71 70.71 images. The images had passed the pre-processing stages such BaselineEigenface 560 87.14 87.14 as eye rotation alignment, histogram equalization, masking Eigen-GEFeS 291.2 86.67 87.85 resizing (each with 225 by 195), and conversion of the images LBP-GEFeS 1022.1 96.62 97.14 into greyscale. oLBP-GEFeS 1018.46 96.43 96.79 For the GEFeS, GEFeS+, and GEFeW, the inputs used Eigen-GEFeS+ 476 88.48 88.92 were the features extracted using Eigenface, LBP, and oLBP LBP-GEFeS+ 463.24 96.52 97.14 feature extraction methods. These methods were used on a oLBP-GEFeS+ 446.89 96.50 97.14 subset of the FRGC dataset. This subset was selected because Eigen-GEFeW 492.8 91.42 92.5 it contains a variety of imaging conditions such as different LBP-GEFeW 1865.29 95.33 95.71 oLBP-GEFeW 1865.08 95.33 96.07 ethnic origins, frontal images that were neutral, and frontal images that had facial expressions. Compared to GEFeS and GEFeS+, all of the results show The objective of this experiment is to compare the impact that GEFeW used a larger number of features. Using a larger of applying GEFeS, GEFeS+, GEFeW on the Eigenface, LBP, number of features brings a better result in the case Eigen- and oLBP based feature extraction methods. GEFeW as compared to Eigen-GEFeS, and Eigen-GEFeS+. Surprisingly, in the case of LBP-GEFeW and oLBP-GEFeW V. RESULTS the result is the opposite. Utilizing a significantly larger For our experiment, nine GEFeS, GEFeS+, GEFeW number of features actually decreases the accuracy for both instances were used. These instances all have a population LBP-GEFeW and oLBP-GEFeW as compared to their size of 20, Gaussian mutation rate of 1 and mutation range of corresponding methods. LBP-GEFeS, LBP-GEFeS+, oLBP-GEFeS, and oLBP- 0.2. The Mutation rate value of 1 implies that all children (100%) must undergo mutation. The mutation range provides GEFeS+ fall in the best equivalence class with respect to a window from the current value (obtained value after accuracy. This means that there is no statistical difference recombination) that the new value will be mutated. among them. All performed well in terms of reducing the number of features needed and in producing a significant Furthermore, they were each run a total of 30 times with a improvement in accuracy from their corresponding baseline maximum of 1000 function evaluations. GEFeS, GEFeS+, and GEFeW were designed for selecting and/or weighting the methods. Figure 1 shows the Cumulative Match Characteristic (CMC) most discriminatory features for recognition. Our results are curve for the BaselineLBP, BaselineoLBPbest, BaselineEigenface and shown in Tables I. In Table I, the columns represent the method used, the for the methods that fall in the first equivalent class. As can be percentage of the average features, the average accuracy, and seen from the Figure 1, LBP-GEFeS, LBP-GEFeS+, oLBP- the best accuracy obtained. The percentage of the average GEFeS, and oLBP-GEFeS+ obtain approximately 97.5% accuracy at rank 10. However, both BaselineEigenface and Eigen- [5] Adams, J., Woodard, D. L., Dozier, G., Miller, P., Glenn, G., Bryant, K. "GEFE: Genetic & Evolutionary Feature Extraction for Periocular- GEFeS performed well (approximately 96%) at rank 10. Based Biometric Recognition," Proceedings 2010 ACM Southeast BaselineLBP performed relatively poorly in terms of accuracy. Conference, April 15-17, 2010, Oxford, MS. [6] Dozier, G., Adams, J., Woodard, D. L., Miller, P., Bryant, K. "A Comparison of Two Genetic and Evolutionary Feature Selection         Strategies for Periocular-Based Biometric Recognition via X- TOOLSS,", Proceedings of the 2010 International Conference on  Genetic and Evolutionary Methods (GEM'10: July 12-15, 2010, Las   Vegas, USA).     [7] Simpson, L. , Dozier, G., Adams, J., Woodard, D. L., Dozier, G.,   Miller, P., Glenn, G., Bryant, K.. "GEC-Based Type-II Feature    Extraction for Periocular Recognition via X-TOOLSS," Proceedings    2010 Congress on Evolutionary Computation, July 18-23, Barcelona,     Spain.     [8] Dozier, G., Bell, D., Barnes, L., and Bryant, K. (2009). "Refining Iris  Templates via Weighted Bit Consistency", Proceedings of the 2009     Midwest Artificial Intelligence & Cognitive Science (MAICS)    Conference, Fort Wayne, April 18-19, 2009.  [9] Dozier, G., Adams, J., Woodard, D. L., Miller, P., Bryant, K. "A        Comparison of Two Genetic and Evolutionary Feature Selection  Strategies for Periocular-Based Biometric Recognition via X- TOOLSS", (to appear in) The Proceedings of the 2010 International Figure 5: Comparisons of CMC results for baseline and the Conference on Genetic and Evolutionary Methods (GEM'10: July 12- best performing algorithms 15, 2010, Las Vegas, USA). [10] Tamirat Abegaz, Gerry Dozier, Kelvin Bryant Joshua Adams, Khary Popplewell, Joseph Shelton, ,Karl Ricanek, Damon L. Woodard” “Hybrid GAs for Eigen-Based Facial Recognition”, accepted for IEEE VI. CONCLUSION AND FUTURE WORK Symposium Series in Computational Intelligence 2011 (SSCI 2011) Our results using GEFeS, GEFeS+, and GEFeW suggests [11] J.E Gentile, N. Ratha, and J. Connell, "SLIC: Short-length iris codes," In Proc. IEEE 3rd International Conference on Biometrics: Theory, that hybrid GAs for feature selection/weighting enhances the Applications, and Systems, 2009. BTAS '09, 28-30 Sept. 2009, pp.1-5. overall performance of the Eigenface, LBP, and oLBP [12] J.E. Gentile, N. Ratha, and J. Connell, “An efficient, two-stage iris methods while reducing the number of features needed. When recognition system”, In Proc. 3rd International Conference on comparing the baseline accuracy, the Eigenface method Biometrics: Theory, Applications, and Systems (BTAS), 2009. [13] Peter T. Higgins, "Introduction to Biometrics", The Proceeding of performed far better than both LBP and oLBP. However, the Biometrics consortium conference 2006, Baltimore”, MD, USA, Sept. hybrid GAs result show that both LBP and oLBP hybrids 2006. performed much better than the Eigenface hybrid method. [14] M. Turk and A. Pentland, "Eigenfaces for recognition", Journal of Our future work will be devoted towards the investigation Cognitive euroscience, Vol. 13, No. 1, pp. 71-86, 1991. [15] Caifeng Shan and Tommaso Gritti, " Learning Discriminative LBP- of GEFeS, GEFeS+, and GEFeW based on other forms of Histogram Bins for Facial Expression Recognition", Proc. of Genetic and Evolutionary Computation[21, 22, 23, 24] 15th EUSIPCO, Poznan, Poland, September 2007. [16] Goldberg, Toimo Ahonen, Abdenour Hadid, and Matti Pietik¨ainen " ACKNOWLEDGMENT Learning Face Expression Recognition”, http://www.ee.oulu.fi/mvg/, visited on sept 10, 2120. This research was funded by the Office of the Director of [17] J. Zhao, H. Wang, H. Ren, and S. C. Kee,” LBP discriminant alalysi National Intelligence (ODNI), Center for Academic for face verification,” in Proceedings IEEE Computer Society Excellence (CAE) for the multi-university Center for Conference on Computer Vision and Pattern Recognition (CVPR’05), Advanced Studies in Identity Sciences (CASIS) and by the vol 3, pp. 167-172, June 2005. [18] Tamirat Abegaz, “GEETIC AD EVOLUTIOARY FEATURE National Science Foundation (NSF) Science & Technology SELECTIO AD WEIGHTIG FOR FACE RECOGITIO”, thesis Center: Bio/computational Evolution in Action CONsortium submitted to North Carolina A&T State University (BEACON). The authors would like to thank the ODNI and [19] M. L. Tinker, G. Dozier, and A. Garrett, “The exploratory toolset the NSF for their support of this research for the optimization of launch and space systems (x-toolss),” http://xtoolss.msfc.nasa.gov/, 2010. [20] P. Jonathon Phillips1, Patrick J. Flynn2, Todd Scruggs3, Kevin W. REFERENCES Bowyer2 Jin Chang2, Kevin Hoffman3, Joe Marques4, Jaesik Min2, [1] Ajay Kumar “ENCYCLOPEDIA OF BIOMETRICS” 2009, Part William Worek3,” Overview of the Face Recognition Grand 6, 597-602, DOI: 10.1007/978-0-387-73003-5_157 Challenge”, IEEE Conference on Computer Vision and Pattern [2] M. Dash and H. Liu, Bartlett, Javier R. Movellan, and Terrence J. Recognition, 2005. Sejnowski,, “Feature Selection for Classification” Genetic Algorithms [21] Danial Ashlock. “Evolutionary Computation for Modeling and for Feature Selection”, Intelligent Data Analysis, vol. 1, no. 3, pp. 131- Optimization.”, Springer, 2005. 156, 1997. [22] Dozier, G., Homaifar, A., Tunstel, E., and Battle, D. (2001). “An [3] J. Adams, D. L. Woodard, G. Dozier, P. Miller, K. Bryant, and G. Introduction to Evolutionary Computation” (Chapter 17), Intelligent Glenn. Genetic-based type II feature extraction for periocular Control Systems Using Soft Computing Methodologies, A. Zilouchian biometric recognition: Less is more. In Proc. Int. Conf. on Pattern & M. Jamshidi (Eds.), pp. 365-380, CRC press. Recognition, 2010. to appear. [23] D. Guillamet, & J. Vitri`a, “Evaluation of distance metrics for [4] Huang C. L. and Wang C. J. “GA-based feature selection and recognition based on non-negative matrix factorization”, Pattern parameters optimization for support vector machines”,. C.-L. Huang, Recognition Letters, 24(9-10), 2003, 1599-1605. C.-J. Wang / Expert Systems with Applications. Vol. 31(2), 2006, [24] Fogel, D. Evolutionary Computation: Toward a New Philosophy of pp231–240. Machine Intelligence . IEEE Press, 2nd Edition., 2000.