Beyond Product Quantization: Deep Progressive Quantization for Image Retrieval

1 Introduction

With the rapidly increasing amount of images, similarity search in large-scale image datasets has been an active research topic in many domains, including computer vision and information retrieval [Wang et al., 2018]. However, exact nearest-neighbor (NN) search is often intractable because of the size of dataset and the curse of dimensionality for images. Instead, approximate nearest-neighbor (ANN) search is more practical and can achieve orders of magnitude in speed-up compared to exact NN search [Shakhnarovich et al., 2008;

∗Contact Author

Song et al., 2018b; Song et al., 2018a; Song et al., 2018c; Lew et al., 2006].

Recently, hashing methods [Wang et al., 2018; Gionis et al., 1999; Liu et al., 2012; Kulis and Darrell, 2009; Shen et al., 2015; Liu et al., 2016; Zhu et al., 2016; Xia et al., 2014; Lai et al., 2015] are popular for scalable image retrieval due to their compact binary representation and efficient Hamming distance calculation. Such approaches embed data points to compact binary codes by hash functions, while the similarity between vectors are preserved by Hamming distance.

On the other hand, quantization-based methods aim at minimizing the quantization error, and have been shown to achieve superior accuracy [Cao et al., 2017; Zhang et al., 2015] over hashing methods, with sacrifice of efficiency. For input data X ∈ RN×D which contains N samples of D dimensions, Vector Quantization [Gersho and Gray, 2012] tries to create a codebook C ∈ RK×D which contains K codewords c(k) ∈ RD , k = 1, 2, · · · ,K, and assigns each data xi, i = 1, 2, · · · ,N to its nearest codeword by a quantizer q(xi) = c(e(xi)). In information theory, the function e(·) is called an encoder, and c(·) is called a decoder [Gersho and Gray, 2012]. The goal of quantization is to minimize the distortion between raw data and quantized data:

After encoding, a D-dimensional data becomes e(xi) ∈ [1, 2, ...,K], which can be represented as a compact binary code bi of length log2K. Product Quantization [Jegou et al., 2011] and Optimized Product Quantization [Ge et al., 2013] first divide the feature space RD to M subspaces (OPQ also performs a rotation on the data) and perform previous minimization on each subspace. Obviously, the codebooks increase from 1 to M. Composite Quantization [Zhang et al., 2015] also learns M codebooks, but its codewords have the same dimension as the original features. Similar to CQ, Stacked Quantization [Martinez et al., 2014] also uses the sum of multiple codewords to approximate the raw data. But Stacked Quantization uses residual of the quantized results and proposes a hierarchical structure so that the minimization can be performed on each codebook. By integrating deep learning to quantization methods, Cao et al. proposed Deep Quantization Network [Cao et al., 2016]. It is the first deep learning structure that learns feature by pairwise cosine distance. Then, Cao et al. proposed Deep Visual-Semantic Quantization [Cao et al., 2017] which projects the feature space to semantic space. Inspired by NetVLAD [Arandjelovic et al., 2016], Benjamin et al. proposed Deep Product Quantization [Klein and Wolf, 2017] that enabled differentiable quantization.

To generate an exponentially large codebook at very low memory/time cost, a product quantizer is still the first option. Despite its success, PQ and its variants have several issues. First, to generate binary codes with different code lengths, a retraining is usually unavoidable. Second, it is still tricky for the decomposition of high-dimensional vector space. Different decomposition strategies may result in huge performance differences. To address these issues, we propose a deep progressive quantization (DPQ) model, as an alternative to PQ, for large scale image retrieval. The contributions of DPQ can be summarized as: 1) DPQ is a general framework which can learn codes with different lengths simultaneously, by approximating the original feature space progressively. Different components of DPQ are replaceable and we instantiate it with a few specific designs of label utilization, input and quantization blocks; 2) Each component in the framework is designed to be differentiable, and thus the whole framework can be trained in an end-to-end manner; and 3) Extensive experiments on the benchmark dataset show that DPQ significantly outperforms the state-of-the-art for image retrieval. Additional ablation study demonstrates the effect of each component of our model.

2 ProposedMethod

Given N images I and a query q, the NN search problem aims to find the item NN(q) from I such that its distance to the query is minimum. We study the ANN search problem and we propose a coding approach called Deep Progressive Quantization (DPQ) for fast image retrieval.

The idea is to approximate a vector x by the composition of several (L) elements {c1 (k1), c2 (k2), ..., cL(kL)}, each of which is selected from a dictionary Cl with K elements, e.g., c1 (k1) is the k1-th element in dictionary C1 , and to represent a vector by a short code composed of the indices of selected elements, resulting in a binary codes of length L· log2 K with each element coded by log2 K bits.

We illustrate our proposed DPQ architecture by the scheme in Fig. 2. It consists of two major components: (1) a supervised feature extraction component in a multi-task fashion and (2) a Deep Progressive Quantization component to convert the features to binary codes. In the remainder of this section, we first describe each of them and then illustrate the optimization and search process.

2.1 Feature Extraction usingMulti-task Learning

For feature extraction, we use AlexNet [Krizhevsky et al., 2012], and we use the output of fc7 layer to extract 4096d features. To fully utilize the supervision information, we introduce two losses based on labels. The first one is a traditional classification loss, which is defined as:

where x is the input feature, yi is the label and y′i is the predicted label. When our images have multi-labels, we modify this loss by multi-label sigmoid cross-entropy:

The second one is an adaptive margin loss. We first embed each label into a 300-d semantic vector zn using wordembedding [Cao et al., 2017]. By applying a fully connected layer on the 4096-d features, we can predict the semantic embedding vi of each data. Following DVSQ [Cao et al., 2017], to embed the projects with the semantic label, an adaptive margin loss is defined as:

These two branches can be described as two different tasks.

2.2 Deep Progressive Quantization

The structure of DPQ is shown in Fig. 2. We denote x ∈ RD as the features of an input image. It goes through L quantization layers (Q-Block), and each Q-Block outputs m-bit quantization codes bl and quantized value ql . The quantization process can be formulated as:

where xl is the input of the l-th quantization layer, and it is quantized to ql by the l-th quantizer Ql .

The target of DPQ is to progressively approximate x by ∑l qi , and objective function can be formulated as:

The final objective function can be formulated as a weighted sum of quantization losses:

An important property of this quantization algorithm is that it can generate hash codes with different code lengths simultaneously. In the l-th Q-Block, the sum of the 1 ∼ l quantized value can approximate the original feature x, as shown in Eq. 9. Note that this is a general form for Deep Progressive Quantization. To instantiate DPQ, we need to specify the design of each quantizer Ql and its input xl .

A straightforward candidate for the Q-Block is K-means algorithm. Given N D-dimensional points X, the K-means algorithm partitions the database into K clusters, each of which associates one codeword ck ∈ RD . Let C = [c1, c2, ..., cK] ∈ RD×K be the corresponding codebook. Kmeans first randomly initializes a C, and then each data point xi is quantized to:

Then the codebook is learned by minimizing the within cluster distortion, i.e.,

This optimization can be done by Lloyd algorithm. However, if we directly use K-means as our Q-Block, it is not an end-toend model, because QKmeans(xi) is non-differentiable to c(i).

To integrate the traditional quantization method into the deep architecture, we have to design a differentiable quantization function. Inspired by NetVLAD [Arandjelovic et al., 2016], we observe that Eq. 11 is equivalent to:

When γ → +∞, xi is quantized to its closest cluster center c(e(xi)). In implementation, choosing a large γ can approximate QKmeans(x) well. Therefore, we design our quantization function as:

where d(x, c(k)) indicates the distance between a vector x and a cluster center c(k). Importantly, the proposed quantization function is continuously differentiable, which can be readily embedded to any neural networks. d(x, c(k)) can be any distance function. In practice, we find cosine similarity is better than Euclidean distance, and we define it as:

where 〈·, ·〉 denotes the inner product between two vectors.

We then focus on the input of Q-Block. Following the composition in [Martinez et al., 2014] and based on Eq. 8, q1 can be interpreted as a quantizer which approximates the input. But the other quantizers, i.e., ql , can be interpreted as quantizers to approximate the residual of the previous l-1 quantizers. It is not required that ql ≈ xl . The solution is to let:

ql can be interpreted as a quantizer to approximate the input. After we determine the quantization functions (Eq. 14) and their inputs (Eq. 16), we can calculate the quantization loss based on Eq. 8, Eq. 9 and Eq. 10. However, the quantization functions (Eq. 14) is not a hard assignment, i.e., QDPQ(x) is a linear combination of all codewords in codebook. While during the retrieval, each vector is quantized to its closest codeword, named hard assignment, defined as:

Therefore, we further define the quantization losses based on the hard assignment as:

where qlH is the hard quantization value of x in the l-th layer. We further constrain that the learned ql should be similar to the hard assignment qlH , formulated as:

Therefore, the overall distortion loss function is:

2.3 Optimization

We train our network by optimizing loss functions (LS,LC,E). The pipeline of the whole training can be described as follows: Firstly, we collect a batch of training images I as inputs of CNN and extract their features X. We then use Q-Block to obtain its quantized features qi, qH,i and associated binary code bi:

where θ and π are the parameters of CNN and Q-Block.

Now, we can use the outputs to calculate total loss function:

Note that the loss function has parameters θ and π to be learned, we use mini-batch gradient descent to update parameters and minimize the loss:

where η is the learning rate. We train our network until the maximum iteration is reached.

2.4 Retrieval Procedure

After the model is learned, we will obtain a codebook π. Next, we need to encode the database and perform the search. Given a data point xi in the database, the l-th Q-Block quantizes the input xli to:

And therefore, xi is quantized by xi and represented by bi:

where binary(.) operation is to convert an index in the range of [1, K] to a binary code with the code length of M=log2 K. Therefore, we can simultaneously obtain L binary codes with different lengths.

The Asymmetry Quantization Distance (AQD) of a query q to database point xi is approximated by ‖q-x‖22 = ∥∥q - ∑l cl (e(xli ))∥∥22 , which can be reformulated as:

We can see that the first and third term can be precomputed and stored, while the second term is constant. Therefore, the AQD can be efficiently calculated.

3 Experiments

We evaluate our DPQ on the task of image retrieval. Specifically, we first evaluate the effectiveness of DPQ against the state-of-the-art methods on three datasets, and then conduct ablation study to explore the effect of important components.

3.1 Setup

We conduct the experiments on three public benchmark datasets: CIFAR-10, NUS-WIDE and ImageNet.

CIFAR-10 [Krizhevsky and Hinton, 2009] is a public dataset labeled in 10 classes. It consists of 50,000 images for training and 10,000 images for validation. We follow [Cao et al., 2016; Cao et al., 2017] to combine all images together. Randomly select 500 images per class as the training set, and 100 images per class as the query set. The remaining images are used as database.

NUS-WIDE [Chua et al., 2009] consists of 81 concepts, and each image is annotated with one or more concepts. We follow [Cao et al., 2016; Cao et al., 2017] to use the subset of the 21 most frequent concepts (195,834 images). We randomly sample 5,000 images as the query set, and use the remaining images as database. Furthermore, we randomly select 10,000 images from the database as the training set.

ImageNet [Deng et al., 2009] contains 1.2M images labeled with 1,000 classes. We follow [Cao et al., 2017] to randomly choose 100 classes. We use all images of these classes in the training set and validation set as the database and queries respectively. We randomly select 100 images for each class in the database for training.

We compare our method with state-of-the-art supervised hashing and quantization methods, including 5 shallowbased methods (KSH [Liu et al., 2012], SDH [Shen et al., 2015], BRE [Kulis and Darrell, 2009], ITQ-CCA [Gong et al., 2013] and SQ [Martinez et al., 2014]) and 6 deepbased methods (DSH [Liu et al., 2016], DHN [Zhu et al.,

2016], DNNH [Lai et al., 2015], CNNH [Xia et al., 2014], DQN [Cao et al., 2016] and DVSQ [Cao et al., 2017]). For shallow-based methods, we use fc7 of pre-trained AlexNet as features. We evaluate all methods with 8, 16, 24 and 32 bits.

To evaluate retrieval effectiveness on these datasets, we follow [Cao et al., 2016; Cao et al., 2017; Lai et al., 2015] to use three evaluation metrics: mean Average Precision (mAP), Precision-Recall curves, and Precision@R (number of returned samples) curves. We follow the settings in [Cao et al., 2016; Cao et al., 2017] to measure mAP@54000 on CIFAR-10, mAP@5000 on NUS-WIDE and mAP@5000 on ImageNet. Following [Zhu et al., 2016; Liu et al., 2016; Cao et al., 2016; Cao et al., 2017], the evaluation is based on Asymmetric Quantization Distance (AQD). We use 300d features as the input of the Q-Block. In order to compare with other methods using the same bit-length, we construct the codebook with L = 4, K=256=28 , so that each codebook can provide a piece of 8-bit binary code. We set epoch to 64 and batch to 16. We use the Adam optimizer with default value. We tune the learning rate η from 10-4 to 10-1 . As for λ, τ, µ, ν in loss function Eq. 24, we empirically set them as λ = 0.1, τ = 1, µ = 1, ν = 0.1. Our implementation is based on Tensorflow.

3.2 ComparisonWith the State-of-the-Art Methods

The mAP of compared methods are based on DVSQ [Cao et al., 2017], and the results are shown in Tab. 1. It can be observed that: 1) Our method (DPQ) significantly outperforms the other deep and non-deep hashing methods in all datasets. In CIFAR-10, the improvement of DPQ over the other methods is more significant, compared with that in NUS-WIDE and ImageNet datasets. Specifically, it outperforms the best counterpart (DVSQ) by 9.9%, 10.6%, 10.4% and 9.8% for 8, 16, 24 and 32-bits hash codes. DPQ improves the state-of-the-art by 0.6%, 3.1%, 4.0% and 3.7% in NUS-WIDE dataset, and 2.1%, 6.6%, 2.1%, 1.2% in ImageNet dataset. 2) With the increase of code length, the performance of most indexing methods is improved accordingly. For our DPQ, the mAP increased by 2.0%, 4.8% and 10.2% for CIFAR-10, NUS-WIDE and ImageNet dataset respectively. The improvement for CIFAR-10 dataset is relatively small. One possible reason is that CIFAR-10 contains simple images, and short codes are good enough to conduct accurate retrieval. 3) Deep-based quantization methods perform better than shallow-based methods in general. This indicates that jointly learning procedure can usually obtain better features. On the other hand, the performances of two deep hashing methods (CNNH [Xia et al., 2014] and DNNH [Lai et al., 2015]) are unsatisfactory. A possible reason is that the deep hashing methods use only a few fully connected layers to extract the features, which is not very powerful.

The precision-recall curves and precision@R curves for CIFAR-10 and NUS-WIDE datasets are shown in Fig. 3, and the results for ImageNet dataset are shown in Fig. 4. In general, curves for different methods are consistent with their performances of mAP.

3.3 Ablation Study

In this subsection, we conduct a series of ablation studies on all three datasets to see the effect of each component. Specifically, we compare our method with the following changes: 1) E: which removes LS and LC from our model. The quantization is directly conducted on fc7 from pre-trained AlexNet; 2) E + LS: which remove the LS loss; 3) E + LC, which removes the LS loss; 4) Two-Step: which learns features and conducts quantization separately; 5) No-Soft: which removes ℓquanH and ℓmatch from Eq. 21, and optimize hard assignments. The results are shown in Tab. 2.

From Tab. 2, it can be observed that the best performance is achieved by using all the components of our model DPQ. Compared with E which is an unsupervised model, our DPQ improves the mAP by 64.2%, 64.5%, 65.0%, 62.6% for CIFAR-10 dataset, 31.4%, 20.1%, 14.8%, 12.1% for NUSWIDE dataset and 27.3%, 33.7%, 33.6%, 34.0% for ImageNet dataset. This indicates that the supervised information is very important for learning good representation. E+LS is a strong competitor, and its performance is very close to DPQ in NUS-WIDE dataset. However, for CIFAR-10 and ImageNet dataset, it is outperformed by DPQ with a large margin.

This indicates that LC is very helpful to guide the learning of features. On the other hand, E + LC, which also utilizes the supervision information by LC, is not as good as E + LC. This implies that LS is superior to LC for retrieval task. Unsurprisingly, DPQ outperforms Two-Step by large margin, especially in NUS-WIDE and ImageNet dataset. This indicates that in Two-Step method, suboptimal hash codes may be produced, since the quantization error is not statistically minimized and the feature representation is not optimally compatible with the quantization process. A joint learning of visual features and hash code can achieve better performance. Compared with No-Soft which only defines the loss function on the hard assignment, DPQ has significant performance gain. Soft-assignment plays the role of intermediate layer, and applying a loss function to soft-assignment is beneficial for hash codes learning.

3.4 Qualitatively Results

We randomly select 5,000 images from CIFAR-10 database and perform t-SNE visualization. Fig. 5 shows the results of DQN, DVSQ and DPQ. As a quantization method, the target is to cluster the data points with the same label, and separate the data points with different labels. Obviously, our DPQ performs the best compared with DQN and DVSQ. For both DQN and DVSQ, the data points with the same label may form several clusters which are far away. This may result in a low recall. On the other hand, the overlapping between different clusters in DQN and DVSQ is more serious than that of DPQ. This may cause a low retrieval precision of DQN and DVSQ, which is also reflected in Tab. 1.

4 Conclusion

In this work, we propose a deep progressive quantization (DPQ) model, as an alternative to PQ, for large scale image retrieval. DPQ learns the quantization code sequentially, and approximates the original feature space progressively. Therefore, we can train the quantization codes with different code lengths simultaneously. Experimental results on the benchmark dataset show that our model significantly outperforms the state-of-the-art for image retrieval.

Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (Grant No. ZYGX2014J063, No. ZYGX2016J085), the National Natural Science Foundation of China (Grant No. 61772116, No. 61872064, No. 61632007, No. 61602049).