Face Recognition via the Overlapping Energy Histogram

1 Introduction

Face recognition has many potential applications in security and surveillance. Over many years, several different techniques have been proposed to mimic the inherent human ability to recognize faces using computers and some of these techniques have been successfully deployed in numerous surveillance systems, e-commerce application and computer login systems [Zhao et al., 2000].

One successful approach to face recognition is to use the Principal Component Analysis (PCA), originally proposed by Sivorich and Kirby [Kirby and Sivorich, 1987]. PCA is an optimal signal representation that extracts the eigenvectors from a covariance matrix constructed from an image database. This technique reduces the number of dimensions to represent images in the database. In 1991, Turk and Pentland [Turk and Pentland, 1991] incorporated PCA into a face recognition system known as Eigenfaces, demonstrating promising results in recognizing frontal images of individuals. Experimentation with a database of 2500 images of 16 individuals generated 96% correct classification over various light conditions, 85% with orientation variations and 64% with size variations.

PCA is an optimal signal representation, however this technique suffers from high computational cost in determining the eigenspace for a large number of images [Kirby and Sivorich, 1990]. In addition, the computational cost for PCA increases when new images are added into the facial image database as the eigenspace in PCA requires recompilation due to its data dependent characteristic [Turk and Pentland, 1991]. Recently, the two dimensional PCA is proposed and it has proven to be much better than Eigenfaces in terms of performance and computational cost [Yang et al., 2004]. In order to reduce the computational cost, fast transforms such as Discrete Cosine Transform (DCT) has been used as an alternative. The DCT has been used for feature extraction and has been demonstrated to be superior to PCA in terms of computation cost since recompilation is not required when adding or removing new images into or from the facial image database [Hafed and Levine, 2001]. Some face recognition algorithms incorporating DCT can be found in [Zhao et al., 2000] and most of them incorporate the DCT coefficients directly into Hidden Markov model and Neural Networks.

This paper is an extension of paper [Tjahyadi et al., 2004]. Compared to the previous paper, first, we use the overlapping method to extract the DCT coefficients in order to enhance the performance. Second, we introduce automatic threshold and number of bins selection to the proposed overlapping energy histogram. Finally, we do more comparisons with other techniques, such as Eigenfaces, 2DPCA and energy histogram.

The overlapping energy histogram is based on the DCT and it measures the distribution of the DCT coefficients of an image. The performance of energy histogram with varying numbers of bins is investigated using six datasets constructed from the Yale face database. In addition, a systematic threshold selection method is proposed which utilises the distance information obtained from the training dataset. The information gathered from the threshold selection procedure is further used to select a suitable number of bins. The performance of overlapping energy histogram face recognition is analyzed and discussed. To illustrate the effectiveness of the technique, comparisons are made with the Eigenfaces, 2DPCA and energy histogram techniques.

2 Preliminaries

2.1 The Discrete Cosine Transform

DCT is a popular technique in imaging and video compression and was first applied in 1974 by Ahmed et al. [Ahmed et al., 1974] to transform image signals from a spatial representation into a frequency representation. In 1992, the first international standard for image compression, JPEG, was established with the DCT as the encoder and decoder and it uses the DCT to remove the redundancies from images. Each image frame is divided into 8x8 blocks, where each block is transformed independently using the two-dimensional DCT (2D-DCT).

Figure 1 shows the zigzag pattern used to process the 8x8 DCT coefficients blocks by JPEG compression. Although the total energy remains the same in the 8x8 blocks, the energy distribution changes with most energy being present in the low frequency DCT coefficients. The DC coefficient, which is located at the upper left corner, holds most of the image energy and represents the proportional average of the 64 blocks. The remaining 63 coefficients denote the intensity changes among the block images and are referred to as AC coefficients.

The DCT was reported to be the second most optimal transformation after PCA with an energy compaction. Although PCA is the optimal transform in an energy packing sense, most practical transform coding systems still apply the DCT as it offers numerous advantages over PCA including good computational efficiency whilst producing good quality images at suitable compression ratios.

2.2 Energy Histogram

Histograms are commonly used in computer vision. The advantages of color histograms are described in [Swain and Ballard, 1990] and include invariance to image manipulations such as rotations, translations and scale, angle of view or occlusions. Despite these advantages, the histogram approach performs poorly under different lighting conditions. It is also ineffective in distinguishing different images that have similar color distributions and suffers from inefficient computation due to its high dimensionality.

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. Lay and Guan [Lay and Guan, 1999] investigated the energy histogram in image retrieval and proposed feature sets identifying similarities of the images. The feature set was obtained by applying the DCT to an individual subset of each facial image and it consisted of 6 feature blocks, denoted F1, F2A, F2B, F3A, F3B, and F4 in Figure 2.

Lay and Guan [Lay and Guan, 1999] reported that the combination of the DC and AC coefficients (F2B, F3B and F4) yield the best performance results in image retrieval. The feature sets F2B and F3B were shown to be more ideal than the F4 feature set, due to the fact that as the feature block grows, more coefficients are involved in creating the energy histogram, thus possibly, introducing more errors. The F1 feature set was observed to perform well when retrieving images that have high color similarity, whilst the F2A and F3A feature sets were shown to have adequate retrieval performance due to the contribution of the AC coefficients which carry the texture and edge information. However, they did not investigate the threshold selection issue.

3 Face Recognition SystemDesign

3.1 Face Recognition Systemwith the Overlapping Energy Histogram

Research on face recognition has been conducted to solve three distinct scenarios: face verification, face identification and the watch list [Lu, 2003]. The aim of face verification is to verify that an individual is who he or she claims to be, whereas the face identification attempts to identify an individual in a database with the assumption that the individual is known. The watch list scenario is similar to face identification, except that the individual to be identified may not be in the database. Of these scenarios, the watch list is generally considered to be the most difficult, as face recognition under this scenario confronts a large number of false alarms [Phillips et al., 2003].

In this section we will use the overlapping energy histogram to design a face recognition system for the watch list scenario (Figure 3). It consists of feature extraction using the energy histogram algorithm, and a classifier which recognizes images based on their feature vectors. In the training stage, we will obtain all the DCT coefficients for each training image with overlap blocks and then select the number of bins and threshold as outlined in the next section. In the recognition stage, we will only use the selected number of bins to extract features from the testing images and classify the testing images based on the selected threshold and generated feature set.

In feature extraction, each facial image is divided into 8x8 blocks with 75% overlapping (6 column pixels overlapped) and the DCT is then computed on each block. The 75% overlapping was reported to perform better recognition rates compared to others [Kohir and Desai, 1998]. In this paper, we only use the F2 feature set (Figure 4). Preliminary investigations have shown that the F2 feature sets achieve better recognition rates in comparison to other feature sets (F1, F3 and F4) [Tjahyadi, 2004]. 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 (Ω). The threshold and bin number selection approaches are outlined in the next section.

Figure 4: The F2 feature set for overlapping energy histogram

To recognize a face image, the system compares the image's feature vector (Ω) to each of the feature vectors in the database. A straightforward pattern classification approach to recognition is to find a face image n that minimises the corresponding Euclidean distance. In experimentation [Tjahyadi, 2004], it is discovered that the Euclidian distance performs better than neural networks on the original energy histogram. Further, the Euclidean distance has been used in many face recognition techniques [Turk and Pentland, 1991; Yang et al., 2004].

where Ωn is a feature vector describing the nth face image.

If ϵn is below some chosen classification threshold (θ), then the new image is classified as belonging to a face image n, and classified as "unknown" otherwise.

3.2 Threshold Selection

The proposed threshold selection is computed via intra and inter class information gathered from the training dataset. The intra-class (D) is a set where the distances between the images of the same individual are calculated as shown in Algorithm 1. This class gives an indication of how similar the images of the same individual are. The inter-class (P) is a set where the distances between the images of an individual are measured against the images of other individuals in the training dataset as described Algorithm 1. This class indicates how different each image of an individual is when compared to images of other individuals in the training dataset. The classification threshold (θ) is then calculated from intraand inter-class information, and described in Algorithm 2. The training dataset requires a suitable number of images per individual in order to obtain sufficient distance information. From [Tjahyadi, 2004], every individual should have at least 4 images for training. A large training dataset should result in better estimation of thresholds. The proposed algorithm for threshold selection is as follows:

Denote

I ′ = number of individuals K′ = number of images per individual I = {1,. . . ,I ′} K = {1,. . . ,K′}

Algorithm 1: Finding the Intra and inter Classes

for each image Mik where i ∈ I and k ∈ K do

Compute hik for kth image of the ith individual, where hik is the feature vector obtained with the selected feature set and histogram bin size.

Compute the intra distances

end

Get the intra class (D) = {dik′ ik | k ̸= k′ , k, k′ ∈ K, i ∈ I} Get the inter class (P) = {pjl ik | j ∈ I, j ̸= i, k, l ∈ K}

and sort the D and P in ascending order

Dmax is a measure of generalization among images for all individuals

Pmin is a measure of differences between one individual against others.

Algorithm 2: Finding the Classification Threshold

The classification threshold (θ) can be defined through Dmax and Pmin. If Dmax < Pmin, then TP ′ and FP ′ rates defined below can reach 100% and 0% respectively. Thus, θ is directly defined as:

If Dmax > Pmin, then one needs to find the θ that maximizes the TP ′ and minimizes the FP ′ with the following steps:

Now, we have obtained D and P from the training dataset which will be used to calculate True Positive′ (T P ′ ) and False Positive′ (FP ′ ). The TP ′ and FP ′ measure the percentage of correct classification and misclassification respectively and are defined as follows:

where Q is the number of elements in D that are less than a given threshold. ‖D‖ is the number of elements in D which is calculated by (K′ -1)×K′ ×I ′ . L is the number of elements in P that are less than a given threshold. ‖P‖ is the number of elements in P which is calculated by K′2 × (I ′ - 1) × I ′ .

Next, we will select a threshold to balance the correct classification and misclassification ratio. The idea is to separate D as N parts evenly and draw a curve of FP ′ and TP ′ with different thresholds. We intend to find the balanced point on this curve. The detail is as below.

From the Algorithm 1, we have obtained D = {d1, d2, . . . , d‖D‖} where d1 ≤ d2 ≤ . . . ≤ d‖D‖. Then we need to find the index x1, x2, . . . , xN such that D is grouped into D = {Dx1 ,Dx2 , . . . ,DxN } where Dxj = {dxj-1+1, . . . , dxj } for j = 1, 2, . . . ,N with xN = ‖D‖,

and [-xj] refers to rounding the number (-xj) to the nearest integer. This process is to divide D into N groups where N is chosen subjectively depending on the database. In the experiments of this paper, N is chosen as 10, which gives us very good performance.

Now, we have obtained the threshold (θj) = {dx1 , dx2 , . . . , dxN }, and we can compute the TP ′ and FP ′ with each element in (θj). Then, the derivative (Tj) is calculated as:

where maxFP ′ is the maximumvalue of FP ′ ; ΔT P ′ j = TP ′ j+1 - TP ′ j for j = 1, 2, . . . ,N - 1; and ΔF P ′ j = FP ′ j+1 - FP ′ j for j = 1, 2, . . . ,N - 1; TP ′ j and FP ′ j are the TP ′ and FP ′ values respectively when we choose the threshold θj with j = 1, 2, . . . , N;

To find the classification threshold (θ), we have to search for a j0 ∈ {2, 3, . . . , N - 1} such that Tj0-1 > 1 and Tj0 < 1. The threshold θ is chosen as the value in dθj0-1 . If none of the Tj values is less than 1, then θ is set as dN. Mathematically, we intend to find a point on the curve (FP ′ -TP ′ ) with Tj = 1, which can balance the rates of correct classification and misclassification. The above algorithm gives us a rough approximation for this selection due to the nature of discrete discontinuity.

3.3 Selection of the Number of Bins

Lay and Guan [Lay and Guan, 1999] empirically discussed the performance of six feature sets in retrieving images and identified that the F2B and F3B feature sets yielded the best performance. However, the effect of varying the number of bins was not investigated. The effectiveness of histogram indexing depends on the number of bins used. Brunelli and Mich [Brunelli and Mich, 1999] suggested that an image retrieval system can rely on small numbers of bins without severe degradation of retrieval performance and showed that a bin number of 16 was sufficient for image retrieval using the City-Block (L1) distance.

In this section we present a systematic approach in selecting a suitable feature set and number of bins for face recognition. We explore the number of bins ranging from 20 to 40 with an increment of 1. The selection algorithm for feature set and number of bins is as follows: LetW = {2}

Fi is the feature set where i ∈W

B = number of bins ranging from 20 to 40 with increment of 1: {21, 22, . . . , 40}

for each histogram F j i with feature set Fi and j ∈ B do

Compute the classification threshold (θj i ) with the algorithm defined in Algorithm 2.

end

Now, we have obtained the following information {TP ′ji , FP ′ji } for i ∈ W, j ∈ B with θj i These values are the balanced correct classification and misclassification ratios with the chosen threshold.

for each histogram F j i with i ∈ W and j ∈ B do

//Get number of bins that maximize the TP ′ for each i ∈W

//Get number of bins from Si that minimize the FP ′ for each i ∈ W

end

The above procedure is to choose the bin size which maximizes the correct classification ratio while minimizing the misclassification ratio. Alternatively, we can also minimize FP ′ first and then maximize TP ′ .

4 Experimental Results

Experimentation was carried out on six datasets created from Yale database [Database, 2004]. This database contains 15 individuals, (mostly male), with 8 images each, since face images in the original database with strong light configurations were excluded as the excessive light cast shadow on the background requires to be preprocessed in practice. The total number of images used in this experiment is 120. In all the dataset, the number of individuals for training is set to be 10 and the number of individuals for testing is set to be 15. Table 1 shows a brief description of all datasets. For each dataset we created 10 subsets via randomly selecting the training images per individual. The remaining images, not included in each training subset, were used to construct the corresponding testing subsets.

These datasets were used to evaluate the proposed face recognition algorithm in two scenarios. In the first scenario, the experiments were carried out on four datasets with fixed threshold value. The results were then compared to the Eigenfaces [Turk and Pentland, 1991], 2DPCA [Yang et al., 2004] and energy histogram [Tjahyadi et al., 2004]. In the other scenario, we investigated the performance of the proposed au-

tomatic threshold and number of bins selection algorithms on the remaining datasets. The query effectiveness is evaluated using precision and recall statistics.

4.1 Evaluation on the Overlapping Energy Histogram Face Recognition System

In this subsection we compare the overlapping energy histogram with the Eigenface, 2DPCA and energy histogram with all datasets in Scenario 1 where each dataset consists of 10 subsets. The threshold for each dataset (Table 2) was selected via trial and error method such that precision and recall rates are balanced. The average results in Table 4 indicate that the overlapping energy histogram outperforms the Eigenface, 2DPCA and energy histogram in all datasets with higher precision and recall rates. In dataset 4, the recall rate of energy histogram is slightly higher than the overlapping method, however, the precision rates are much lower. Significant performance of the overlapping energy histogram can be seen in dataset 1 where only 1 image per individual was used as a training image while the remaining images were used as testing images.

4.2 Evaluation on Automatic Threshold and Number of Bins Selection Algorithms

In this subsection we will examine the proposed threshold and number of bins selection algorithms with 2 datasets in Scenario 2 where each dataset consists of 10 subsets. We select 2 subsets from dataset 5 and 6 to demonstrate the effectiveness of the proposed number of bins selection algorithm. Table 5 shows the selected number of bins and their corresponding accuracies for the subsets. From Figure 5, one can see that the proposed number of bins selection performs well in selecting number of bins where the precision and recall are balanced with high rates.

The selected classification thresholds and their corresponding accuracies are shown in Figures 6 and 7 respectively. The numbers of bins and classification thresholds are calculated from the proposed approaches. From these figures one can see that the threshold selection approach performs more stable with dataset 6. This is due to the fact that dataset 6 has more training images, hence, it provides more intra and inter distances for selecting the threshold. Overall, these results indicate that the selected classification thresholds are very stable with regard to the subsets.

5 Conclusions

In this paper we proposed a new approach to feature extraction with the overlapping energy histogram of the DCT coefficients for face recognition. Some important issues related to the recognition performance were investigated, in particular, the issue of selection of threshold and number of bins. Experimentation was conducted on Yale face database. Results have shown that the threshold selection provides a balance in precision and recall rates. The number of bins selection approach has producedconvincing results. In addition, the overlapping energy histogram approach has shown to outperform the Eigenfaces, 2DPCA and energy histogram in all selected datasets.