Fast Structural Binary Coding

1 Introduction

With the rapid development of massive image collection applications such as Instagram, Flickr, and Pinterest, there is an increasing demand for finding visually relevant images effectively and efficiently. Binary coding techniques, rather than exhaustively searching for the most similar images with respect to a query in a high-dimensional feature space, encode images with compact binary codes and conduct efficient searches in the generated low-dimensional code space (i.e., Hamming space). This can reduce search time and save storage space.

In particular, binary coding methods aim to learn a set of coding functions {hq : Rd 7! H = ¶-1↪ 1♦ rq=1 to map data samples from a d-dimensional data space Rd to an r-dimensional Hamming space Hr . Early binary coding approaches, e.g., Locality-Sensitive Hashing (LSH) [Andoni and Indyk, 2008] and Min-wise Hashing (MinHash) [Broder et al., 1998], produce binary codes with random permutations or projections. These randomized binary coding methods, however, require long code lengths (r ≥ 1↪ 000) to meet search requirements, and usually cannot perform well for large-scale image search [Liu et al., 2012; 2014; Zhang et al., 2014; Wang et al., 2014; 2016] as they consider data points independently.

In contrast to such randomized binary coding approaches, various data-dependent binary coding methods have been invented more recently. These techniques, in general, can be divided into two main categories: unsupervised and supervised (including semi-supervised) approaches. Unsupervised approaches, such as Spectral Hashing (SH) [Weiss et al., 2008], Iterative Quantization (ITQ) [Gong et al., 2012], Isotropic Hashing (ISOH) [Kong and Li, 2012], Discrete Graph Hashing (DGH) [Liu et al., 2014] etc., learn coding functions by modeling the underlying data structures, distributions, or topological information. Supervised approaches, on the contrary, learn coding functions by leveraging supervision information, e.g., instance-level labels, pair-level labels, or tripletlevel ranks. Representative techniques include pointwise supervised methods (e.g., Binary Reconstructive Embedding (BRE) [Kulis and Darrell, 2009]), pairwise supervised methods (e.g., Minimal Loss Hashing (MLH) [Norouzi and Fleet, 2011] and Kernel-based Supervised Hashing (KSH) [Liu et al., 2012]); and rank supervised approaches (e.g., Hamming Distance Metric Learning (HDML) [Norouzi et al., 2012], Ranking-based Supervised Hashing (RSH) [Wang et al., 2013], Column Generation Hashing (CGH) [Li et al., 2013]), Rank Preserving Hashing (RPH) [Song et al., 2015b], and Top Rank Supervised Binary Coding (Top-RSBC) [Song et al., 2015a].

Despite existing rank supervised binary coding techniques having shown their effectiveness and efficiency for scalable visual search tasks, few of them focus on optimizing the precision at the top of a ranking list according to Hamming distance, while considering the underlying structure of the ranking list [Weston and Blitzer, 2012] appropriately (i.e., approximately preserving the geometric relationship between database examples such that the set of similar images can be returned as a whole). Therefore, in this paper, we propose a novel supervised binary coding approach, namely Fast Structural Binary Coding (FSBC), to optimize the precision at the top of a Hamming distance ranking list and approximately preserve the geometric relationships between database examples. The core idea is to train disciplined coding functions by optimizing a lower bound of the area under the ROC (Receiver Operating Characteristic) curve (AUC) and penalizing the objective such that the geometric relationships between database examples in the original Euclidean space is preserved in the Hamming space. In this way, we may avoid producing a set of top ranked images which may be too diverse and include irrelevant examples (e.g., examples from different classes). Since the objective we introduce is discrete and the associated optimization problem is combinatorially difficult, we relax the original discrete objective to a continuous and differentiable surrogate, and then derive a stochastic gradient descent method to optimize the surrogate objective. We compare the proposed approach, FSBC, against various state-of-the-art binary coding techniques through extensive experiments conducted on two benchmark image datasets, i.e., SUN397 [Xiao et al., 2010] and YouTube Faces [Wolf et al., 2011]. The experimental results demonstrate that FSBC outperforms the state-of-the-art approaches for various image search tasks.

2 Lower Bound of AUC

In this section, we first introduce the notation used in the paper. Then we introduce the concept of binary coding. Finally, we derive a lower bound of the area under the ROC (Receiver Operating Characteristic) curve (AUC) based upon binary codes.

2.1 Notation

Let X 2 Rd⇥n be a data matrix of n data samples with d dimensions; we can use xj 2 Rd to represent the j-th column of X, and Xij to denote the entry in i-th row and j-th column of X, respectively. Moreover, we use k · kF to denote the Frobenius norm of matrices, and kxkH to represent the Hamming norm of vector x, which is defined as the number of nonzero entries in x, i.e., the `0 norm. We use kxk1 to represent the `1 norm of vector x, which is defined as the sum of absolute values of the entries in x.

2.2 Binary coding

Given a data matrix X 2 Rd⇥n , we aim to learn a set of mapping functions {hq(x) rq=1 such that a d-dimensional floating-point input x 2 Rd is compressed into an r-bit binary code b = ⇥h1(x)↪ ▷ ▷ ▷ ↪ hr(x)⇤ 2 Hr ⌘ ¶1↪-1♦r . This mapping, also called a coding function in the literature, is defined as:

where sgn(x) is the sign function that returns 1 if x > 0 and -1 otherwise, and fq : Rd 7! R is a proper prediction function. A variety of mathematical forms for fq (e.g., linear or nonlinear) can be taken to apply for domain specific practical applications. In this work, we consider a linear prediction function, i.e., fq(x) = w> q x + tq (where wq 2 Rd and tq 2 R) for simplicity. Based upon the previous work [Gong et al., 2012; Kong and Li, 2012; Liu et al., 2012; Wang et al., 2013], we set the bias term tq = -w> q u by using the mean vector u = Pni=1 xi◁n, which will make each generated binary bit {hq(xi) ni=1 for q 2 [1 : r] be nearly balanced and hence have maximum entropy. For brevity, we can define a coding function h : Rd 7! Hr to comprise the functionality of r hash functions ¶hq♦rq=1 , that is,

which is parameterized by a matrix W = [w1 · · · wr] 2 Rd⇥r . Note that Eq. 2 applies the sign function element-wise. For convenience we write h(x) = h(x↪W).

2.3 Lower bound of AUC

Given a triplet (xi, xj, xs), assuming xi is a query, xj 2 P is a similar example to xi (P is the set of similar examples), and xs 2 N is a dissimilar example to xi (N is the set of dissimilar examples), then the AUC for query xi is given as:

where I(·) is an indicator function which is 1 if the condition in the parenthesis is satisfied and 0 otherwise.

Since AUC counts each pairwise comparison equally, it does not explicitly quantify the fraction of positive examples which achieve the optimal ranking (ranked on the top of a Hamming distance ranking list). For this purpose, we derive a lower bound of AUC in Theorem 1.

Theorem 1. AUC is lower bounded by

with equality holding if within each product operator the condition for each indicator function is jointly satisfied or jointly not satisfied.

Theorem 1 states that the fraction of positive examples which achieve the optimal ranking cannot be greater than AUC. It can be proved using the fact that the arithmetic mean is always greater than or equal to the geometric mean. Note that the calculation of the AUC lower bound in Eq. 4 includes all the possible pairwise comparisons, which may make the underlying optimization problem intractable for a large scale database. An equivalent, more tractable form, can be derived:

Proposition 1. The lower bound of AUC in Theorem 1 is equivalent to1

which can be calculated in linear time.

Proposition 1 suggests that instead of exhaustively searching for the pairwise comparisons which are jointly satisfied, we only need to compare with the minimum Hamming distance over the set N. Proposition 1 also quantifies the fraction of positive examples which are ranked on top of all the negative examples (i.e., on top of the ranking list) [Song et al., 2015c].

3 Fast Structural Binary Coding

In this section, we first present Fast Structural Binary Coding (FSBC). Then we derive a stochastic gradient method to produce binary codes by optimizing the FSBC objective.

3.1 Model

FSBC aims to optimize the precision at the top of a Hamming distance ranking list and approximately preserve the geometric relationship between database examples based upon a linear mapping W. Given a triplet (xi, xj, xs), assuming xi is a query, xj is a similar example, and xs = arg minx2N kh(xi)-h(x)kH is a dissimilar example which is closest to xi in Hamming space within the set N, the objective of FSBC can be given as:

where the first term encodes the lower bound of AUC in Proposition 1. The second term approximately preserves the geometric relationship of the triplet in the original Euclidean space (i.e., the distance of dissimilar pairs (h(xj)↪ h(xs)) and (h(xi)↪ h(xs)) should be large, and the distance of similar pair (h(xi)↪ h(xj)) should be small). This term is necessary because (1) it resolves the degeneracy problem shown in Figure 1; (2) it imposes a constraint over the dissimilar pair (h(xj)↪ h(xs)) to ensure the distance between them is also large; (3) it also explicitly states that the distances between (h(xi)↪ h(xs)) and between (h(xi)↪ h(xj )) should be large/small respectively, while the first term only cares about their difference. The last term is a regularization term to prevent the model from overfitting. λ > 0 and θ > 0 are two hyper-parameters to control the balance of the three terms.

3.2 Relaxation and approximation

The proposed model in Eq. 6 is difficult to optimize because (1) the coding function in Eq. 2 is a discrete mapping; (2) the Hamming norm lies in a discrete space; and (3) the indicator function in Eq. 6 is non-differentiable. Thus the objective in Eq. 6 is discrete, and combinatorially difficult to optimize.

To address these issues we relax the original discrete objective to a continuous and differentiable surrogate. We first approximate the original coding function h(x↪W) = sgn(W>(x - u)) by

which is continuous and differentiable as shown in Figure 2(a). For convenience we write h(xi) = h(xi↪W).

Second, we relax the Hamming norm in Eq. 6 to the `1 norm which is convex and robust to outliers. Finally, we approximate the indicator function in Eq. 6 with the sigmoid function, G(x) = 1 1+exp(-x) , as shown in Figure 2(b), i.e.,

The basic idea is that if h(xi) is closer to h(xj) than h(xs) in the `1 norm, then the value of this objective should be close to 1.

With these relaxations/approximations, the original objec-

Algorithm 1 Fast Structural Binary Coding

• 1: Input: D = ¶xi↪ xj↪ xs♦, ↵,W, λ, and θ
• 3: Repeat
• 2: Output: W 2 Rd⇥k
• 4: Randomly pick up a sample xi.
• 5: Fix xi and randomly select a similar sample xj.
• 6: Fix xi and xj, randomly draw p dissimilar sample xs when s varies to form ¶xi↪ xj ↪ xs♦ps=1 .

8: If kh(xi) -h(xs)k1 < ✏ +kh(xi) -h(xj)k1

7: Determine s by mins2(1↪▷▷▷↪p) (kh(xi) -h(xs)k1 ).

• 9: Calculate @O(W) @W based upon Eq. 10, 11, 12.
• 10: Make a gradient ascent based upon Eq. 13.
• 11: End if

• 12: Until mean average precision does not improve or maximum iteration number is achieved.

tive in Eq. 6 can be fomulated as:

where s is the index of the dissimilar example closest to xi in Hamming space, deefined by xs = arg minx2N kh(xi) - h(x)k1.

3.3 Optimization

To optimize the approximated objective in Eq. 9, in each iteration we first randomly select a query xi, a similar example xj, and a set N of p dissimilar examples. After determining xs as argminx2N (kh(xi) - h(x)k1 ), then if kh(xi) - h(xs)k1 < ✏ + kh(xi) - h(xj)k1 with ✏ > 0, we can calculate the gradient in Eq. 9 with:

where Hab = kha - hbk1 and Tab = kha - hbk22 , @Hab @W is given by:

where ⊙ represents Hadamard product (i.e., element-wise product).

@Tab @W is given by

With the gradient in Eq. 10, we can conduct stochastic gradient ascent as following:

where ↵ is the learning rate. The detailed optimization procedure is provided in Algorithm 1. ✏ is set to be 1 in all our experiments.

Note that our optimization procedure in Algorithm 1 is similar to standard stochastic gradient descent (SGD). The difference is that in each iteration, either than randomly selecting a subset of training examples, we only select the most extreme example from a subset of training examples for optimization. It is very plausible that this approach will work and the empirical results confirm our intuition that this should give good results. We are aware that the theoretical guarantees for standard SGD do not apply directly. It will be an interesting problem to provide theoretical guarantees for Algorithm 1.

4 Experiment

In this section, we first describe two datasets and the setting for our empirical study. Then we introduce the three evaluation metrics used in our experiments. Finally we compare the proposed Fast Structural Binary Coding (FSBC) against several state-of-the-art binary coding and hashing algorithms to demonstrate its effectiveness for large scale image search. Among these baseline approaches, four are unsupervised approaches, including one randomized method, Locality Sensitive Hashing (LSH) [Andoni and Indyk, 2008], one spectral approach, Spectral Hashing (SH) [Weiss et al., 2008], and two linear projection techniques, Iterative Quantization (ITQ) [Gong et al., 2012] and Isotropic Hashing (ISOH) [Kong and Li, 2012]. The other three are supervised approaches which use triplets to encode the label information (similar to our setting); they are Hamming Distance Metric Learning (HDML) [Norouzi et al., 2012], Column Generation Hashing (CGH) [Li et al., 2013], and Ranking-based Supervised Hashing (RSH) [Wang et al., 2013].

4.1 Datasets and setup

In the experiments, we perform image search over two different datasets, i.e., SUN397 [Xiao et al., 2010] and YouTube Faces [Wolf et al., 2011]. SUN397 consists of about 108K images from 397 scene categories. In SUN397, each image is represented by a 1,600-dimensional feature vector extracted by principle component analysis (PCA) from 12,288dimensional Deep Convolutional Activation Features [Gong et al., 2014]. The YouTube Faces dataset contains 614,626 face images of 1,595 different people. In YouTube Faces, each face image is represented by a 1,770-dimensional LBP feature vector [Ahonen et al., 2006]. The detailed statistics of these two datasets are shown in Table 1.

In SUN397, 100 images are randomly sampled from each of the 18 largest scene categories to form a test set of 1,800 query images. For unsupervised approaches, all the database samples are used for training. For supervised methods, we randomly choose 200 images from each of the 18 scene categories to form a training set of 3,600 images; an additional 50 images from each of these 18 scene categories are randomly selected to form a validation set of 900 query images. All the rest of the images in the 397 categories are then used as the database samples. In YouTube Faces, 100 face images from each of the 65 largest face classes are randomly sampled to form a test set of 6,500 query images. For unsupervised learning, all the database images are used for training. For supervised learning, 1,000 images from each of the 65 face classes are randomly draw to form a training set of 65,000 face images; an additional 50 images from each of these 65 scene categories are randomly selected to form a validation set of 3250 query images. All the rest of the face images in the 1,595 face classes are treated as the database samples for retrieval.

We implement the proposed FSBC and baseline algorithms using Matlab on a PC with Intel Core i7-4770K Processor 3.5GHz and 32GB RAM. The parameters λ and θ of FSBC are determined by cross validation over the grid

¶1↪ 10-1 ↪ 10-2 ↪ 10-3 ↪ 10-4 ↪ 10-5 ↪ 10-6 ♦. We will discuss the parameter sensitivity later.

To measure the effectiveness of various binary coding and hashing techniques for image search, we consider three evaluation metrics, i.e., Mean Average Precision (MAP), precision at top-k positions (Precision@k), and recall at top-k positions (Recall@k).

4.2 Results

We compare the proposed Fast Structural Binary Coding (FSBC) against seven binary coding and hashing algorithms based upon SUN397 and YouTube Faces when r varies from 32 bits to 256 bits, as shown in Figure 3(a) and 4(a), respectively. We observe that with the increment of bits (r), FSBC consistently outperforms all baseline approaches for MAP. This is because FSBC not only optimizes the precision at the top of a Hamming distance ranking list, but also approximately preserves the geometric relationship between database examples in the original Euclidean space. For baseline approaches, supervised methods, i.e., HDML, RSH, and CGH generally outperform unsupervised techniques since they can produce discriminative binary codes by incorporating label information appropriately. Among the unsupervised approaches, we notice that SH, ITQ and ISOH consistently outperform LSH. This suggests that utilizing underlying data structures, distributions, or topological information can produce more effective codes for image search tasks. The detailed image search performances in terms of MAP and Precision@100 over the two datasets are provided in Table 2.

We also compare FSBC with baseline methods based upon Precision@k and Recall@k over SUN397 and YouTube Faces (when r is fixed as 256 bits). In Figure 3(b), 3(c), 4(b), and 4(c), we notice that FSBC generally outperforms all baseline approaches when k varies from 10 to 100 for Precision@k and as k varies from 0 to 5000 for Recall@k. This suggests that optimizing the objective of FSBC can significantly improve top-k image search performance. Note that Precision@k does not perform well when k < 30 in Figure 3(b) and 4(b). This may be because we only optimize the objective over a small random subset (p) of training examples in each iteration (for efficiency), not on the entire training set. We observed that as p increases, the performance (k < 30) will improve and may outperform baseline methods.

The training time of the proposed FSBC and baseline algorithms over the two datasets are provided in Tables 1. We observe that the offline training time of FSBC is less than those of HDML and CGH which all use label information in the form of triplet-level ranks. This is because FSBC is only optimized over the most extreme triplet while HDML and CGH weigh each triplet equally. For binary code generation, the main computational cost of FSBC depends on the linear projection and binarization operations. Hence, the test time of FSBC is 1.94⇥10-5 second for SUN397 and 2.26⇥10-5 second for YouTube Faces which is as efficient as typical linear binary coding or hashing algorithms.

2.48⇥103

3.94⇥103

We study the parameter sensitivity for FSBC (when r = 128) in Figure 5 and 6. In Figure 5, we observe that when λ is fixed at 0.01, the performance (MAP and Precision@100) of FSBC is relatively stable when θ varies from 10-3 to 10-6 . In Figure 6, we notice that when θ is fixed as 10-5 , the Precision@100 of FSBC is relatively robust when λ varies from 1 to 10-6 but MAP decreases as λ decreases from 10-2 to 10-6 . These results justify the effectiveness of the regularization term being used for preserving the geometric relationship between the database examples in the original Euclidean space.

5 Conclusion

In this paper, we proposed Fast Structural Binary Coding (FSBC) to explicitly optimize the precision at the top of a Hamming distance ranking list and approximately preserve the geometric relationship between the database examples in the original Euclidean space. The key idea is to train disciplined coding functions by optimizing a lower bound of AUC and penalize this objective such that similar database examples in the original Euclidean space can be returned as a whole in the Hamming distance ranking list. To find such a coding function, we relaxed the original discrete optimization objective with a continuous surrogate, and then derived a stochastic gradient descent method to optimize the surrogate objective. Empirical studies based upon two image datasets demonstrated that the proposed FSBC can outperform the state-of-the-arts for large scale image search.