Optimal Bayesian Hashing for Efficient Face Recognition

1 Introduction

For image-based visual recognition tasks, feature representations are often in very high dimensions. Many existing works have demonstrated that the high-dimensional features can yield better accuracies [Jia et al., 2012] than the lower dimensional ones. Face recognition is one of the typical tasks with this phenomenon [Barkan et al., 2013; Chen et al., 2013]. To reduce the cost of both storage and computation, different feature compression (selection, filtering, projection, etc.) techniques have been proposed. This paper takes face recognition as the use-case to study the feature compression problem.

Face recognition has received significant attentions in the past several decades, and it has been applied in a wide range of applications [Zhao et al., 2003; Li and Jain, 2011]. To stimulate research in this area, several real-world benchmarks have recently been created with challenging uncontrolled face images. For instance, Labeled Face in the Wild (LFW) and Face Recognition Grand Challenges (FRGC) have been the popular testbeds for face recognition.

Among all the face recognition techniques developed in recent years, there are roughly two major categories of approaches, i.e., low-level representation design and learningbased methods. The former aims at designing robust handcrafted feature representations, such as Gabor [Wiskott et al., 1997; Liu, 2006], LBP [Ahonen et al., 2006], HoG [Mikolajczyk and Schmid, 2005], etc. The latter leverages modern machine learning techniques in the recognition process. For instance, some methods attempt to learn more discriminative features from the low-level representations or raw images. Representative techniques include subspace based methods [Turk and Pentland, 1991; Belhumeur et al., 1997; He et al., 2005] and mid-level representation (a.k.a. attributes) learning [Kumar et al., 2009; Wright et al., 2009]. Other popular methods build advanced learning models with improved discriminative power. The learning models can be distance metrics [Guillaumin et al., 2009; Kostinger et al., 2012; Nguyen and Bai, 2010], classifiers [Heisele and et al, 2001] and Boosting [Guo and Zhang, 2001]. In addition, some recent works rely on deep learning to simultaneously perform feature learning and model training in a unified framework [Huang et al., 2012; Sun et al., 2013; Taigman et al., 2014; Sun et al., 2014].

In most existing approaches, people tend to employ highdimensional feature representations or over-complete feature sets since they often have better discriminative ability and can yield higher recognition accuracies [Su et al., 2009; Huang et al., 2011; Chen et al., 2013; Barkan et al., 2013]. However, such high-dimensional face features demand additional storage cost and computational time for training and prediction. To alleviate this issue, several works suggest to learn low-rank representations from the high-dimensional features [Li et al., 2014].

Rather than performing the low-rank matrix recovery, in this paper, we present an efficient way to embed highdimensional features into a more compact Hamming space for face recognition. In particular, we propose a novel Bayesian framework to encode face features into compact binary codes that require significantly reduced computation and storage cost. After that, we develop a boosted FERNs based model with a random permutation technique to further exploit bit-level relationships among different binary codes. Finally, we perform sequential forward floating search (SFFS) to select models that lead to high accuracy for face recognition. Different frommost existing face recognition techniques that use continuous feature representation, we utilize the proposed Bayesian Hashing framework to extract compact binary codes that can still maintain state-of-the-art recognition performance. We summarize the main contributions below:

1. We propose a novel Bayesian optimal Hamming embedding method, namely Bayesian Hashing, which can efficiently encode floating point features into compact binary codes.
2. We build boosted FERNs classification models on bitstreams and exploit bit-level relationships with random permutation technique. Further performance improvement could be obtained by sequential model selection. We show that such a framework performs much better than other classifiers like the SVM for binary codes.
3. We conduct extensive experiments on two popular face benchmark datasets, i.e., the FRGC and the LFW. The results show that the proposed method outperforms other competing methods in both accuracy and speed.

This paper is organized as follows. We discuss related works in Section 2 and introduce the proposed Bayesian Hashing in Section 3. In Section 4, we discuss experimental settings and results. Conclusions are drawn in Section 5.

2 RelatedWorks

We divide related works into two categories, namely feature projection and metric learning and supervised hashing.

2.1 Feature Projection andMetric Learning

High-dimensional feature learning has been extensively studied. For example, subspace methods are considered as one of the first choices to reduce redundancy of high-dimensional features. If we project a d-dimensional raw feature into pdimensional discriminant subspace, the projection matrix will be of the size d×p. Usually, the original dimension d of the face features is very high, e.g., the popular Gabor features being with tens of thousands of dimensions [Liu, 2006; Tan and Triggs, 2010]. In some over-complete feature learning algorithms like [Huang et al., 2011; Barkan et al., 2013; Chen et al., 2013], the value of d could be more than several hundreds of thousands. Note that learning such a projection matrix could be very costly for high-dimensional cases. To address the scalability issue, researchers employed various techniques, including the divide-and-conquer strategy [Su et al., 2009], sparse projection matrix learning with ℓ1 regularization [2013], and low-rank representations learning [Li et al., 2014], where promising performance has been achieved with reduced cost in either computation or storage.

Another closely related topic is metric learning, which aims to learn a metric that maximally separates different subject classes. Given features of two face images vi and vj, the distance metric is often defined in a quadric form d(vi, vj) = (vi-vj)T M(vi-vj). The metricM ∈ Rd×d is a symmetric positive definite matrix that can be decomposed as M = AT A with A being a linear transformation matrix. The learned distance function d(vi, vj) can be incorporated into objectives like the logistic discriminant function [Guillaumin et al., 2009], the Cosine function [Nguyen and Bai, 2010], etc. In [Huang et al., 2011], sparse block diagonal constraints are imposed on the metric matrix M for fast training. In [Parkhi et al., 2014], the authors proposed a binary representation with metric learning to reduce the dimensionality of high-dimensional Fisher vector (FV) features. In these approaches, however, the metric learning process is often very time consuming for high-dimensional data. In this paper, we propose to use a fast Bayesian Hashing method to encode the original high-dimensional face features to significantly reduce the computation and storage costs.

2.2 Supervised Hashing

The objective of hashing techniques is to map raw features to compact binary codes, where the similarity in the original feature space can be preserved in the binary code space, namely Hamming space. Supervised hashing techniques have attracted increasing attentions in recent years since the goal is to design hash functions that can preserve semantic similarity in the Hamming space. For example, LDA-Hash [Strecha et al., 2012] maximizes the difference between labelsame/label-different pairs in the linear discriminative projection space. Supervised Hash with Kernels (KSH) [Liu et al., 2012] applies kernelization to formulate hash functions and minimizes the loss function over hash codes. However, the kernel computation is very time consuming in both training and testing. CNN Hash [Xia et al., 2014] simultaneously learns the hash functions as well as feature representations. Semantic correlation maximization Hash (SCM) [Zhang and Li, 2014] uses supervised multimodal hashing for large scale data modeling. Note that most of the existing supervised hashing techniques attempt to preserve semantic similarity in the final Hamming space. The proposed Bayesian Hashing method directly aims at minimizing the Bayes error of the classification problem to generate compact hash codes.

Additionally, a method called BayesLSH was proposed in [Satuluri and Parthasarathy, 2012]. Although the name is similar, this work is fundamentally different from ours as it only utilizes the Bayes theorem to estimate the similarity between two existing hash codes.

3 Bayesian Hashing

In order to speed up face recognition using the highdimensional feature representations, we aim at learning a compact representation from the original features without significant loss of recognition performance. Briefly, we consider the Bayes error as an objective function to find the optimal Hamming embedding. Given the learned hash codes, we further employ the boosted FERNs to perform the classification process. The proposed approach consists of the following three key components:

1. Bayesian Hashing: We obtain an optimal Hamming embedding by minimizing the Bayes error. To reduce the

computational cost, we use face patches to generate hash codes, as discussed in Sec. 3.1.

1. Boosted FERNs based classifiers: We model hash bitstream with boosted FERNs classifiers. Details are discussed in Sec. 3.2.
2. Bit permutation: To exploit the relationships among different patches, we introduce a bit-stream permutation technique, which leads to multiple random FERNs models. Then the sequential forward floating search is applied to select a few good permutation models, as discussed in Sec. 3.3.

For the raw face features, We use Gradient locationorientation histogram (GLOH) in our implementation [Mikolajczyk and Schmid, 2005]. In particular, given the face images with some landmark points, we extract n patches around landmarks with different scales. In addition, we further make a mirror of each face image and extract another n more patches. Thus, we obtain a total of K = 2n patches, each having 17 block segments with a 8 dimensional histogramstyle feature. Finally, we represent each patch with a d0=136 dimensional feature vector.

We use a pair-wise (not limited to) representation for face recognition as suggested in [Pinto and Cox, 2011]. Given a pair of face images vi and vj ∈ Rd (d=K*d0), let xij be the pair representation which is element-wise absolute-difference xij = (‖vi1 - vj1‖p , ..., ‖vid - vjd‖p ). We then define y = 1 if vi and vj are from the same subject, and y = -1 otherwise. Thus, we obtain a positive sample set P from the same-subject pairs, and a negative set N from the other pairs.

3.1 Bayesian Hashing: Formulation

Assuming that both P and N follow normal distribution, i.e., P(x|y = 1) = N(x|µp,Σp) and P(x|y = -1) = N(x|µn,Σn), the log-ratio discriminant function is

where b is the bias parameter for the prior 1 .

The Bayesian Hashing seeks a set of hash functions ˆ y = h(x; b) by minimizing Bayes error on training set,

We will start from the simplest case with only 1-dimensional feature and then extend to multi-dimensional settings.

1-dimensional case

1 The Bayesian Hashing is not limited to univariate discriminant function. We may easily extend our framework to bi-variables (pair inputs) form G(x1, x2), and obtain the discriminant function as in [Kostinger et al., 2012] or [Chen et al., 2012]. Due to space limitation, we will not describe the deduction of hash function for bivariable discriminant function in this paper.

Assuming σp = σn = σa, we have the hash function for 1-dimensional case as

In practice, we obtain b by applying a line search algorithm (like golden section search) to minimize the cost in Eq (2). Figure 1 illustrates how the hash function h(x; b) works in the 1-dimensional case.

d-dimensional case

For the d-dimensional case with d>1, we follow the twostage procedure like many Hamming embedding algorithms [Strecha et al., 2012]. At the first stage, we perform a decorrelation subspace projection. There are many different criteria which could be used for this objective. This paper adopts the Fisher criterion to maximize the separation between P and N by the ratio of variances on P and N ,

With Lagrange multipliers, this gives the projection Σ-1 , where Σ = Σp + Σn. Observing that Σ is a symmetric positive semi-definite matrix, it has an SVD decomposition Σ-1 = (USU T )-1 = (U T S- 12 )(S- 12U) = AT A, where A = S- 12 U . Replacing Σp and Σn with AT A, Eq (1) can be simplified to

where x′ and µ′ are all in the projection space (i.e., x′ = Ax,µ′ = Aµ). At the second stage, we derive a set of hash functions hi(x′i ; bi) for each element of x′ , similar to Eq (4).

Different from the two-stage procedures in [Strecha et al., 2012], our objective is to minimize the Bayes error in Eq (2) to train supervised hash functions in Eq (4). To the best of our knowledge, we are the first to employ Bayes error in learning a Hamming embedding. Notice that the full feature dimension d of the images is very high. Instead of applying subspace projection on the whole d dimensional feature space, we perform subspace projection for each face patch with a relatively lower feature dimension.

3.2 Boosted FERNs

Given a high-dimensional feature input x, Bayesian Hashing will generate a bit sequence f = (f1, · · · , fD), where fi ∈ {0, 1}. We then model the bit stream with a random boosted FERNs framework [Ozuysal et al., 2010]. Figure 2 shows our configuration of the boosted random FERNs.

Generally, given bit-sequence f , we partition them into M groups of size S = DM , obtaining a set of feature groups F = (F1, · · · , FM). Each group Fi is called a FERN, and is modeled with a Naive Bayesian classifier P(Fi|y). Then the joint probability for all FERNs is computed by P(F|y) = ∏Mi=1 P(Fi|y), assuming that all groups are independent. In our implementation, we group every 8-bit (S = 8) together to one byte F. In addition, to reduce possible redundancy among different bytes, we adopt the Boosted framework. We take each FERN as a weak classifier, and train a GentleBoost, a variant of AdaBoost classifiers, to ensemble different FERN bytes. Table 1 summarizes the training algorithm of the boosted FERNs.

During the training procedure, we restrict that each FERN byte can be chosen only once to avoid redundancy. Finally, we can obtain a decision function for recognition as

where T ≤ M is the number of bytes used/picked. This deci- Input: Training set: {(F k i , yi)}Ni=1, k = 1 : M, where N is the number of samples and M is the number of FERN bytes. F k is k-th FERN byte.

Table 1: Boosted FERNs training algorithm using GentleBoost.

Initialize: Iteration number T. t = 0. Initialize weight for positive samples and negative samples.

Step 1: For each byte F k , build Naive Bayesian probability lookup table P(F k |y);

Step 2: Pick the best byte F σ(t) according to the Bayes error on the training set, and define decision function as

Note, here we restrict that each byte can be taken only once.

Step 3: Update weight wt,i = wt-1,i · exp[-yiht(F σ(t) i )]; and normalize the weight so that ∑i w+ t,i =1 and ∑i wt,i =1;

Step 4: t = t+1. If t = T , break; else go to Step 1.

Output: Strong classifier HT (F ) = ∑Tt=1 ht(F σ(t) ).

sion function is in fact a summation of a set of look-up-tables (LUTs), which makes the prediction very efficient. In addition, these LUTs can be further quantized into 8-bit char type so that the model storage can be further reduced.

3.3 Bit Permutation andModel Selection

As discussed in Sec. 3.1, with high dimensional raw features, it is inefficient to performHamming embedding on the whole feature space since the projection procedure will be fairly costly. To address this issue, we conduct patch-level Bayesian Hashing. In order to exploit possible relationships between different patches, we introduce a bit-stream permutation technique. As illustrated in Figure 2, a total of G permutations are generated. After performing permutation, bits in the same byte could come from different patches. Given the original hash code f, the g-th random permutation is defined as fg = {fδ(g,1) , · · · , fδ(g,D) }, where δ(, ) denotes the indices after permutation.

For a set of bit-stream permutations, each permutation δg will produce a boosted FERNs model H(Fδg ). Intuitively, more permutations will produce better discrimination power to gain more performance improvement. However, this also incurs possible redundancy and additional cost. By introducing the Sequential Forward Floating Search (SFFS), we are able to select an optimal set of permutation models to achieve improved performance without additional overhead. Note that the random permutation will not increase the storage significantly since the Hamming embedding is already fixed. Table 2 shows the details of the SFFS algorithm.

4 Experiments

4.1 Datasets and Experimental Settings

FRGC: The FRGC version-2 [Phillips et al., 2005] was designed to be a comprehensive benchmark for face recognition. We focus on experiment-4 (known as FRGC-204), which Input: Random permutation feature grouping set F = {Fg, 1 ≤ g ≤ G}. J(Fk) measures classification accuracy based on permutation set Fk.

Table 2: SFFS algorithm for permutation selection.

Initialize: F0 = ∅, k = 0, preset permutation number GS. Step 1: Inclusion

• Find the best permutation F + = arg max F ∈F\Fk J(Fk ∪ F ), where F\Fk is the set F excludes subset Fk;
• Fk+1 = Fk ∪F +; k = k +1;

Step 2: Conditional exclusion

• Find the worst permutation F - = arg max F ∈Fk J(Fk - F );
• If J(Fk -F -) > J(Fk-1), then Fk-1 = Fk -F -, k = k - 1, go to Step 2; else go to Step 3.

Step 3: If k ≥ GS, break; else go to Step 1.

Output: Good permutation grouping subset Fk.

contains 12,776 training faces, 16,028 target face images and 8,014 query faces. The target face images are taken under controlled environment, while query faces are taken under uncontrolled environment. This makes the FRGC-204 the most challenging task in the FRGC benchmark. The dataset provides manual annotations for 4 landmarks (eye centers, nose tip and mouth center). Each face is normalized to 128×128 according to these landmarks. We extract n=240 patches from the normalized faces according to the landmark positions with different patch sizes. A mirror image is generated for each normalized face and another n=240 patches can be extracted. Therefore, there are totally 480 GLOH patches, and each patch is described by a 136-dimensional feature.

Following the traditions on this dataset, we report the true positive rate at a fixed false positive rate of 0.1% (TPR@FPR=0.1%). In addition to the single-point measure, Receiver Operating Characteristic (ROC) curves are adopted for some of the evaluated approaches.

LFW: The popular LFW dataset consists of 13,233 images of 5,749 individuals, and all the images are collected from the Internet. We adopt the LFW-a (the aligned version of LFW), and similar settings are adopted to for data preprocessing following the previous works on this dataset.

There are several evaluation protocols for LFW. We conduct experiments strictly following the unrestricted with label-free outside data protocol. The evaluation dataset is divided into 10 subsets to form a 10-fold cross-validation. In each trail, we use nine subsets for training and one for testing. We report the mean Equal Error Rate (EER). ROC curves are also plotted.

4.2 Results and Discussions

We conduct several experiments to analyze the impacts from different components of the proposed approach.

Bayesian Hashing: We first evaluate our Bayesian Hashing and compare with two alternative hashing methods: Product Quantization (PQ) [J´egou et al., 2011] and Supervised Hashing with Kernels (KSH) [Liu et al., 2012]. The number of bytes for PQ is the same as that of Bayesian Hashing (8,160). For KSH, because the training process is too expensive, we only manage to train 4,800 hash functions (600 bytes). Table 3 summarizes the results on FRGC and Figure 3(c) shows the corresponding ROC curves. Bit-permutation is not adopted for all the three methods. As shown in the table, Bayesian Hashing has higher accuracy. More importantly, it significantly reduces the computation and memory cost. Our Bayesian Hashing still outperforms KSH with a significant margin when only 500 bytes are used (68.40% vs. 59.20%). For PQ, the accuracy is just slightly lower, but is over 10x slower than our Bayesian Hashing in testing time.

Boosted FERNs classification: Next, we examine the effectiveness of the boosted FERNs and compare with SVM. Table 4 shows the results on FRGC (the bottom five rows). The boosted FERNs classification plays an important role in our method. Replacing it with SVM, we only obtain 79.78% on FRGC using the same set of binary codes. Besides, we also train an SVM classifier on the raw floating point GLOH features, which produces an accuracy of 93.72%. In comparison, the proposed method can achieve 93.20%, while requiring lower computation and memory costs.

Impact of the number of FERN bytes: We now study the impact of the number of the selected FERN bytes. Bitpermutation is not adopted here and will be evaluated in the next experiment. Each GLOH block (8-dimensional; each patch has 17 blocks) is encoded into one byte. The boosting training considers the FERN bytes sequentially according to their contributions. Figure 3(a) and 3(d) plot the performances vs. different numbers of bytes on FRGC and LFW, respectively.

For FRGC, the accuracy tends to be stable after 4,000 bytes, and the trend on LFW is more or less the same. It is worth noting that the original Bayesian Hashing with 8,160 bytes can already yield a 32x compression rate of the original high-dimensional floating point features. If only using 4,000 bytes, the feature compression ratio is more than 64x with only 2% accuracy drop.

This experiment also indicates a very promising property of our method that we can possibly adopt a coarse-to-fine search strategy for large-scale applications. For instance, it is feasible to build a first level coarse search with just the top 1,000 bytes, which can quickly narrow down the search space for fine-grained computations with more bytes.

Impact of bit permutation: We train multiple boosted FERNs models using different random permutations. Figures 3(b) and 3(e) shows the accuracy vs. different numbers of random permutations on FRGC and LFW, respectively. It is clear that the accuracy grows with an increasing number of shuffles, especially at the beginning parts of the curves (# shuffles ≤8).

We also study the effectiveness of SFFS on both FRGC and LFW. Given a large set of different permutation models, we adopt SFFS to select good and complementary ones by evaluating on a separate validation set. As shown in the Figures 3(b) and 3(e), SFFS is able to further improve the results with only a small number of selected permutations on both datasets.

4.3 Comparison with State of the Arts

In this subsection, we compare our results with several stateof-the-art works. Table 4 and Table 5 summarize the results on FRGC and LFW respectively, where "perm-x" indicates x random permutations. On both datasets, we achieve very competitive results. It even outperforms the deep learning based approach [Sun et al., 2013], which is very appealing as we only adopt the traditional hand-crafted GLOH features. Notice that our method can be deployed on any type of features, including the powerful deep learning based ones. We expect a significant gain may be achieved by replacing GLOH with the recently developed deeply learning features. Figure 3(f) further shows the ROC curves of our method and the compared approaches on LFW. For FRGC, we do not have the data needed for plotting ROC curves of the compared works. Finally, we would like to emphasize again that our results are obtained using binary codes that possess the nice property of significantly lower computation and memory costs, while all the compared works reply on the expensive floating features.

5 Conclusions

Recent advances in visual recognition tasks have shown that high-dimensional feature representations often yield high accuracies, while suffering from heavy computational overload and expensive memory cost. In this paper, we have presented a novel method to derive optimal Hamming embedding for high-dimensional features, namely Bayesian Hashing, with a focus on the challenging application of face recognition. To achieve high recognition performance, we also designed a boosted FERNs classification framework to handle the binary features. In addition, a random permutation technique was used to better exploit bit correlations and train multiple classification models, where a SFFS algorithm can be applied to perform model selection and fusion. Extensive experiments and comparison studies using two popular face recognition benchmarks clearly demonstrated that the proposed method achieved competitive performance with significantly reduced computation and memory costs.

Although the proposed method was evaluated in the face recognition task, the Bayesian Hashing technique is a fairly general supervised hashing method and can be extended to various computer vision applications, such as large scale image search and object recognition. One of our future directions is to design a unified framework to learn the Hamming embedding and train classification models simultaneously for general computer vision tasks.

Acknowledgments

This work was supported in part by the National 863 Program of China (#2014AA015101), a grant from NSF China (#61201387) and two grants from the STCSM (#13PJ1400400, #13511504503).