In this paper, we present a two-stage process for developing feature extractors (FEs) for facial recognition. In this process, a genetic algorithm is used to evolve a number of local binary patterns (LBP) based FEs with each FE consisting of a number of (possibly) overlapping patches from which features are extracted from an image. These FEs are then overlaid to form what is referred to as a hyper FE. The hyper FE is then used to create a probability distribution function (PDF). The PDF is a two dimensional matrix that records the number of patches within the hyper FE that a particular pixel is contained within. Thus, the PDF matrix records the consistency of pixels contained within patches of the hyper FE. Darwinian-based FEs (DFEs) are then constructed by sampling the PDF via k-tournament selection to determine which pixels of a set of images will be used in extract features from. Our results show that DFEs have a higher recognition rate as well as a lower computational complexity than other LBP-based feature extractors.
Genetic & Evolutionary Biometrics (GEB) is the field of
study devoted towards the development, analysis, and
application of Genetic & Evolutionary Computation (GEC)
to the area of biometrics
GEFEML (Genetic and Evolutionary Feature Extraction –
Machine Learning)
In this paper, we present a two-stage process for facial
recognition
In the second stage of the process, a Darwinian feature extractor (dFE) is developed by sampling the PDF via ktournament selection (Miller and Goldberg 1996). The selected pixels are then grouped into c different clusters by randomly selecting α pixels to serve as centers. Our results show that the computational cost of DFE (in terms of the total number of pixels being processed) via dFEs is far less expensive than the FEs evolved via GEFEML. The dFEs also outperform GEFEML evolved FEs in terms of recognition accuracy.
The remainder of this paper is as follows. Section 2 provides an overview of the LBP feature extraction method, GECs, and GEFEML. Section 3 provides a description of the two-stage process for developing dFEs. Sections 4 and 5 present our experiment setup and our results respectively. Finally, in Section 6, we present our conclusions and future work.
The LBP method (Ojala and Pietikainen 2002; Ahonen, Hadid and Pietikinen 2006) extracts texture patterns from images in an effort to build a feature vector (FV). It does this by segmenting an image into rectangular regions, referred to as patches, and comparing the grey-scale intensity values of each pixel with the intensity values of a pixel’s nearest neighbors. After pixels are compared with their nearest neighbors, a pattern is extracted. This pattern is represented by a binary string. A histogram is built using the frequency of occurring patterns for a patch. The histograms for every patch are concatenated to form a FV.
In the LBP method, images are traditionally partitioned into uniform sized, non-overlapping patches. Within each patch, pixels are sought out that have d neighboring pixels on all sides and that are a distance of r pixels away from a center pixel. Each of these pixels can be referred to as a center pixel, cp, due to it being surrounded by a neighborhood of pixels. A texture pattern can be extracted using Equations 1 and 2, where N is the set of pixel intensity values for each of the neighboring pixels. In Equation 1, the difference between a neighboring pixel and cp is calculated and sent to Equation 2. The value returned will either be a 1 or a 0, depending on the difference. The d bits returned will be concatenated to form a texture pattern.
d LBP(N, c p ) (nt c p )
t0 1, x 0, (x) 0, x 0. (1) (2) Each patch has a histogram that stores the frequency of certain texture patterns extracted. The histograms for all patches of an image are concatenated together to create a FV for an image. This FV can be compared to another FV of an image using a distance measure such as the Manhattan Distance measure or the Euclidean distance measure.
GEFEML uses GECs to evolve FEs
GEFEML evolves LBP-based FEs using some GEC, so FEs
must be represented as a CS. GEFEML represents an FE, fei,
as a six-tuple, <Xi,Yi,Wi,Hi,Mi,fi>. The set Xi = {xi,0, xi,1,…,
xi,n-1} represents the x-coordinates of the center pixel of n
possible patches and Yi = {yi,0, yi,1, … , yi,n-1} represents the
y-coordinates of center pixel of n possible patches. The
widths and heights of the n patches are represented by Wi =
{wi,0, wi,1, … , wi,n-1} and Hi = {hi,0, hi,1,…, hi,n-1}. Because
the patches are uniform, Wk = {wk,0, wk,1, … , wk,n-1} is
equivalent to, wk,0 = wk,1,…, wk,n-2 = wk,n-1, and Hk = {hk,0,
hk,1, … , hk,n-1} is equivalent to, hk,0 = hk,1,…, hk,n-2 = hk,n-1,
meaning that the widths and heights of every patch are the
same. Uniform sized patches are used because uniform
sized patches outperformed non-uniform sized patches in
The fitness fi is determined by how many incorrect matches it makes on a training dataset D and how much of the image is processed by fei. The dataset D is composed of multiple snapshots of subjects and is divided into two subsets, a probe and a gallery set. The fei is applied on both the probe set and gallery set to create FVs for each set. A distance measure is used to compare FVs in the probe to FVs in the gallery and the smallest distances are considered a match. If the FV of an individual in the probe is incorrectly matched with the FV of another individual in the gallery, then that is considered an error. The fitness, shown in Equation 3, is the number of errors multiplied by 10 plus the percentage of image space being processed.
fi 10 (D) ( fei ) (3)
To prevent overfitting FEs on a training set during the evolutionary process, cross-validation is used to determine the FEs that generalize well to a dataset of unseen subjects. While offspring are applied to the training dataset to be evaluated, they were also applied to a mutually exclusive validation dataset which does not affect the evolutionary process. The offspring with the best performance on the validation dataset is recorded regardless of its performance on the training set.
The hyper FE is constructed by taking a set of FEs from GEFEML and overlaying them. Figure 1a shows a set of sample FEs while Figure 1b shows a sample hyper FE. After the hyper FE is constructed, a PDF, in the form of a matrix, is created. Each position in the matrix contains the number of patches a pixel was contained in. When patches in an FE overlapped on a position multiple times, the overlap is considered in the count. So if the hyper FE had n patches, and used κ FEs, the greatest number of times a pixel was contained in a patch would be n * κ. Figure 1c shows a 3D plot of a PDF, while Figure 1d shows the 3D plot laid over a facial image.
(a) (c) (b) (d)
A dFE can be defined by the number of clusters it has, α, the selection pressure of tournament selection, µ, and the patch resolution, ρ. The variables µ and ρ are represented as a percentage, or a value between 0 and 1. Assume that β represents the number of pixels a user would want for a cluster, there are α *ρ*β positions that will be selected to be clustered. Tournament selection selects µ*σ pixels to compete for clustering, where σ represents the total number of positions in the PDF that have been processed at least once. When performing tournament selection, the position with the greatest consistency will be the winner. If there is a tie, then the first selected position is the winner. Winning pixels are selected without replacement.
After α *ρ* β pixels have been selected via tournament selection, α random centers for clusters are chosen to be placed within the PDF. The distance between each of the selected positions for clustering will be compared to the center positions, and the pixel will be clustered towards the closest one. After pixels have been assigned to clusters, those pixels undergo LBP feature extraction to extract texture patterns for a cluster. Due to the random placement of clusters, it is possible for different clusters to have different numbers of pixels clustered to it.
The clusters are similar to patches, therefore histograms are associated with each, and the patterns are used to build the histogram and ultimately create FVs for images.
Two hyper FEs were used in this experiment: (a) a hyper FE composed of a set of FEs that performed well on the training set, HFEtrn and (b) a hyper FE composed of a set of the best performing FEs on the validation set, HFEval. The FEs were evolved using the experimental setup in Shelton et al. (2012c), which used GEFEML. GEFEML was run 30 times using increments of 1000, 2000, 3000 and 4000 evaluations. An EDA instance (Larranga and Loranzo 2002) of GEFEML was used with a population of 20 FEs and an elite of 1, meaning every generation starting from the second contained the single best performing FE of the previous generation. On each run, GEFEML returned the best performing FE on the training set and the best performing FE with respect to the validation set.
The FEs were trained and validated on two mutually exclusive sets, and they were then applied to a test set. The datasets were composed of subjects from the Facial Recognition Grand Challenge database (FRGC) (Phillips et al. 2005). The training set was composed of 100 subjects (FRGC-100trn), the validation set was composed of 109 subjects (FRGC-109), and the test set was composed of 100 subjects (FRGC-100tst). The average number of patches used from the set of generalizing FEs as well as the average number of pixels processed in a patch were calculated in order to set a starting point for this experiment. On average, 12 patches were activated and 504 pixels were processed by each patch using GEFEML.
In this experiment, instances of 16, 12, 8 and 4 clusters were tested. Different patch resolutions, or the amount of pixels that could belong to a cluster, were also used. In this experiment, σ = 504. This was the average number of pixels in patches of the set of FEs from GEFEML. Instances of DFE with patch resolutions of 1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2 and 0.1 were run. Each resolution used selection pressures from 0.0 (where number of pixels to be compared in tournament selection is actually 2) to 1.0 and every tenth percentage in between. A dFE is defined to be a cluster, patch resolution, then selection pressure, giving a total of 880 dFEs (4 clusters * 10 patch resolutions * 11 selection pressures * 2 hyper FEs), and each DFE instance was ran 30 times. For each run, a dFE was applied to FRGC-100tst.
The results were obtained by running each dFE listed in Section 4 on FRGC-100tst.
To compare the effectiveness of each method, we compare the results of different selection pressures within a certain resolution and patch. The results of the best selection pressure for a resolution are compared to the best selection pressures of every other resolution within the cluster group, and this is done for results in every cluster. After the best performing FEs are obtained from each cluster, they are compared to each other as well as the results of GEFEML. Results are compared using an ANOVA test and a t-test on the recognition accuracies for a cluster-resolution-selection pressure instance.
Table I shows the results of this experiment. The first column shows the methods used. The method DFEval represents dFEs that sampled the HFEval, while the method DFEtrn represents dFEs that sampled the HFEtrn. The two methods are compared to the original GEFEML method, shown as GEFEML. The second column, Feature Extractor, shows the number of clusters used, the resolution and the selected pressure for a dFE. The third and fourth columns show the computational complexity (CC) and the average recognition accuracy (Acc) respectively for each method. The computational complexity is the number of pixels processed, or extracted, by each method. Though 880 dFEs were tested, the only ones shown are ones that produced superior results to GEFEML.
For DFEval, each dFE showed in Table I outperformed GEFEML in terms of recognition accuracy. For DFEtrn, the dFE <12,0.5,0.2> was statistically equivalent to FEs evolved using GEFEML. Though we compare results based on recognition accuracy, we also considered computational complexity.
The results show that the <12,0.5,0.2> dFE (of DFEtrn) outperforms GEFEML in terms of computational complexity, and that the <12,0.9,0.1> instance of DFEval outperformed DFEtrn and GEFEMLin terms of recognition accuracy as well as computational complexity. These results are promising in terms of recognition and feature reduction of DFE.
The results of the experiment suggest that the HFEval produces dFEs that generalize well to unseen subjects. The dFEs resulting from the HFEtrn also generalized well, but were not as effective as when using dFEs resulting from the HFEval. Using both hyper FEs performed better than the set of generalized FEs from GEFEML. Future work will be devoted towards using additional GECs for the DFE.
This research was funded by the Office of the Director of National Intelligence (ODNI), Center for Academic Excellence (CAE) for the multi-university Center for Advanced Studies in Identity Sciences (CASIS), NSF SSTEM, Lockheed Martin and the National Science Foundation (NSF) Science & Technology Center: Bio/computational Evolution in Action CONsortium (BEACON). The authors would like to thank the ODNI, the NSF, and Lockheed Martin for their support of this research. Ojala,T., Pietikainen, M.; “Multiresolution Gray-Scale and Rotation Invariant Texture Classification with Local Binary Patterns”, IEEE Trans. Pattern Analysis and Machine Intelligence; 971-987; 2002 Ramadan. R. M. and Abdel-Kader, R. F. ; “Face Recognition Using Particle Swarm Optimization-Based Selected Features,” In International Journal of Signal Processing, Image Processing and Pattern Recognition, Vol. 2, No. 2, June 2009.