Progressive Generative Hashing for Image Retrieval

1 Introduction

Hashing technique has been widely known for its successful applications to many nearest neighbor search tasks, such as large-scale visual search [He et al., 2012; Liu et al., 2013; Wang et al., 2015], machine learning [Mu et al., 2014], recommendation system [Liu et al., 2014b], etc. It works based on the concept of Locality-Sensitive Hashing (LSH), which guarantees that the nearest neighbors share the similar binary codes, and thus enables fast search with compressed storage over gigantic databases. In the literature, LSH was first introduced by Indyk, and further developed in [Datar et al., 2004], which proposed the popular random projection paradigm. The projection based hashing usually generates the binary codes by first linearly projecting the data along certain directions and then quantizing the projections to binary bits.

∗Corresponding Author

Due to the simple form and efficient computation, many following studies have attempted to further improve the discriminative power of the hash codes, and learnt the projection based hash functions by leveraging the information contained in the data [Weiss et al., 2008; Gong and Lazebnik, 2011; Wang et al., 2017; Liu et al., 2014b; Wang et al., 2018; Kong and Li, 2012; Yu et al., 2014; Liu et al., 2014a; Shen et al., 2015; Wang et al., 2014]. Despite the progress in the linear projection based hashing, these methods still cannot well capture the nearest neighbor relations using the binary codes, mainly due to the fact that the shallow structures lack the capability of modelling complex data distribution [He et al., 2013]. Although the nonlinear mapping techniques like kernel can help uplift the data into an informative space [Raginsky and Lazebnik, 2009; Kulis and Darrell, 2009; Liu et al., 2011], they are usually time-consuming, and meanwhile still fail to exploit the underlying data structures using the linear shallowmodel.

As the deep convolutional neural network yield breakthrough performance on many computer vision tasks, there are several recent studies having been devoted to learning deep hash functions. In these deep network based hashing methods, the hash functions can directly encode the raw images into their binary codes in an end-to-end way. To learn the discriminative hash function, usually we have to train the deep model using a sufficient number of labeled data, which largely limits the power of the deep network based hashing.

There are quite a few deep network based hashing studies that mainly focused on the more generic unsupervised settings, due to the difficulty of training the hashing networks. DH [Liong et al., 2015] and Deepbit [Lin et al., 2016] serve as the pioneering work that learnt the nonlinear end-to-end hash function under independent and balanced constraints on the generated binary codes. Without any supervision information, both methods have shown the encouraging performance in image retrieval. More recently, in [Song, 2017] the more powerful Generative Adversarial Networks (GANs) [Goodfellow et al., 2014] have been further adopted to generate binary representation, which achieved very promising performance compared to the other unsupervised deep hashing methods, but heavily relies on the pre-defined similarity matrix as the side information.

To exhaustively exploit the power of GAN itself, this paper proposes a novel progressive generative adversarial framework to help learn a discriminative deep hashing network in an unsupervised way. Very different from [Song, 2017], our model employs a progressive way to gradually generate more discriminative hash codes, based on the generated semantic and realistic images by GAN. Specifically, for each image we regard its binary code generated by any weak hashing method as a kind of weak semantic condition for the similar image generation, and simultaneously feed it and the original image into the designed GAN to generate the synthetic image. With the real images and their synthetic ones, we can further train a discriminative hashing network by minimizing a triplet loss over them, which can generate more informative hash codes that can well preserve the semantic relations. Progressively, the output hash codes can serve as the new input to the GAN, guiding the following repeated learning process, towards much better hash codes.

To the best of our knowledge, this is the first work that truly pursues deep hash functions in the generative adversarial networks under the unsupervised setting and achieves the stateof-the-art performance over several popular image datasets.

2 Progressive Generative Hashing

In this section, we will elaborate our Progressive Generative Hashing (PGH) model. Before that we first introduce the basic notations used through this paper.

Supposing we have n training images in the training set X = {xi|i = 1, . . . , n}, our goal is to learn a deep hashing network H without any label information. The hashing network H can encode each input image xi into a compact binary code bi ∈ {0, 1}k in an end-to-end way, where k is the code length. Intuitively, the generated binary codes B = {bi|i = 1, . . . , n} are expected to preserve the similarity relationship among the images. To achieve this goal, we employ a generative adversarial architecture, consisting of a generative network G and a discriminative network D, to generate complementary images for training H. Figure 1 illustrates the architecture of the proposed PGH method.

2.1 Hash Conditioned GANs

Learning a deep hashing network usually requires sufficient training images that can convey the intrinsic distribution. Without label information, to learn a discriminative H, we have to resort to certain way to synthesize complementary images that can uncover the underlying structure of the data, together with the original training images.

The generative adversarial architecture has been proved to be a promising solution, owing to its surprising capability of generating the realistic images. However, without any guidance to the desired hash codes, such a solution might diverge from the goal due to its unstable training. Since most of existing hashing methods attempted to preserve the neighbor relations, the generated compact hash codes, which can distinguish the similar data with a large probability, can be viewed as a kind of weak semantic information.

Based on the fact, we propose a hash conditioned generative adversarial networks, where both G and D are conditioned on certain binary codes generated by any weak unsupervised hashing method. This is similar to the idea used in conditional GANs [Mirza and Osindero, 2014] in the literature, where their generator and discriminator are usually conditioned on some semantic information like class labels. Our model largely differs from them by simply utilizing the easily obtained weak hash codes without heavy requirements on the strong semantic clues.

Even though such inferior binary codes may not be discriminative enough for image retrieval tasks, they can provide auxiliary information for generative adversarial networks to produce plausible and semantically similar images. Besides, they can bring extra information that can supervise and thus stabilize the hard-to-train generative adversarial network.

In particular, for a training image xi, the generator network G takes a random noise vector zi and an initial weak binary code bi as the input and generates a synthetic image

Such synthetic images should preserve the original similarity of the input hash codes. Namely, if the Hamming distance between two binary codes bi and bj is greater than that between bi and bk, then the synthetic image ¯xj should be more similar to ¯xi than ¯xk.

For the discriminator D, the real image xi and the generated one ¯xi will be respectively combined with the corresponding binary codes bi as the input. D will evaluate the probability that the input comes from the training data rather than G. Therefore, the whole GANs can be trained in a twoplayer min-max game. Specifically, given an image sample xi and its weak binary code bi, the objective function of the two-player min-max game would be:

min G max D LD,G = logD(xi|bi)+log(1-D◦G(zi|bi)) (1)

2.2 Deep Hashing Network

In our paper, we mainly focus on the unsupervised setting without any label information. Therefore, to learn a discriminative H, we only resort to the training data and its inherent structure. Fortunately, the hash conditioned GANs are able to discover the structure and thus provide more explicit information by the generated images. Since it is reasonable to expect that a real image xi is more similar to its corresponding generated image ¯xi than other synthetic images, we can form real-synthetic triplets using the original real images and their generated images.

Specifically, with the help of our hash conditioned GANs we can easily obtain a set of real-synthetic triplets, where each triplet (xi, ¯xi, ¯xj) consists of a real image xi, its synthetic one ¯xi, and any other synthetic one ¯xj (j ̸= i). Note that ¯xi = G(zi|bi), which means it is synthesized by generator network G conditioned on the weak binary code of xi, and thus has much stronger similarity with xi than any ¯xj generated upon the different images and hash codes.

Intuitively, the desired hash codes should be able to preserve the relative similarities among the images in the triplet. In this way, we can define a triplet loss that has also been successfully applied in prior research [Qiu et al., 2017], which is defined over the output binary codes bi, ¯bi and ¯bj corresponding to the training image triplet (xi, ¯xi, ¯xj)

where ‖·‖H represents Hamming distance and the parameter γ controls the minimum Hamming distance margin between the similar and dissimilar image pairs.

To pursue such discriminative hash codes, we can learn the hashing network H by minimizing the triplet loss. This can drive H to possess strong capability of distinguishing the images with slight changes. Since the hash codes are discrete, we simply adopt the following quantization solution to generate hash codes using H:

where the output of H belongs to [0, 1].

Since directly minimizing h(bi, ¯bi, ¯bj) is quite difficult, mainly due to the involvement of the discrete binary codes. To approximately solve the problem, we first can naturally relax the problem by replacing bi with H(xi), and simultaneously turn Hamming distance to the l1 distance. Therefore, the triplet loss can be defined as

To further force the relaxation to be consistent with the discrete hash codes, we need to minimize the quantization loss

Based on the two types of loss, we can learn the deep hashing network by solving the following problem

which can be efficiently solved by alternating the optimization of the subproblem with respect to each variable while fixing the others. Note that besides generating hash codes, the hashing network together with D can also help improve G for better image generation.

2.3 Progressive Architecture

The initial input binary codes might not be able to accurately characterize the inherent relations among the training images. However, with the triplet loss guiding deep hashing network H, it is possible for us to pursue better binary codes by absorbing more information from both the real images and the synthetic ones. We will later show this fact indeed holds in our experimental part.

Under the assumption that the quality of the binary codes can be improved through our hash conditioned GANs and the hashing network, we can naturally introduce a progressive architecture to feed the improved hash codes into the networks again, and thus continuously increase the code quality, establishing a learning cycle until converging. In the progressive architecture, as shown in Figure 1, the binary codes connect the two successive learning cycle, i.e., the output hash ones, learnt upon the input weak ones in the last round, will be returned as the new input to start the next round learning. By repeating such process, we gradually achieve more realistic image generation and a more discriminative hash function.

Specifically, at the t-th loop we input the weak binary codes B(t-1) , t = 1, . . . , T to G and D, and output new binary ones B(t) by H. We start the progressive learning by B(0) generated by any weak hashing method. Then, for the t-th loop, the overall objective function in our progressive architecture, with respect to current networks G(t) , D(t) , H(t) and the desired binary codes B(t) , should be

2.4 Optimization Details

In the above problem the desired networks and the binary codes can be easily optimized one by one iteratively. However, to achieve fast convergence and satisfying performance, we also should pay much attentions to the training order of the different networks. Since the synthetic images play an important role on the hashing network learning, to guarantee their quality, practically we make sure hash conditioned generative adversarial networks (G and D) are adequately trained first. This can be completed by solving the subproblem in Equation (1) without considering the effect of hashing network. After that, we can simultaneously take the three networks into consideration in the next training process by solving the problem in Equation (4) for each progressive stage. Algorithm 1 lists the main steps of our PGH method.

In the above training process, we believe the hashing network could extract certain semantic information, which in turn will help stabilize and improve the performance of the generator. We find that when training generator G in our method, to emphasize the semantic similarity between real images and synthetic ones, replacing the triplet loss with the following loss can further the performance in practice:

3 Experiments

In this section, we will evaluate the proposed progressive generative hashing (PGH) method in the task of image retrieval. We adopt two widely used large image datasets, i.e.,

Algorithm 1 Progressive Generative Hashing (PGH)

Input: training set X = {xi|i = 1, . . . , n}, weak codes set B = {bi|i = 1, . . . , n} Output: non-linear parameters set WD, WH andWG for number of progressive loops do for number of training epochs do for k1 steps do sample minibatch of m noise {z1, z2, . . . , zm} sample minibatch of m examples {x1, x2, . . . , xm} optimize WD to max D LD,G end for for k2 steps do construct minibatch of m tuples {(xi, ¯xi, ¯xj)} optimize WH to min H LH,G end for sample minibatch of m noise {z1, z2, . . . , zm} sample minibatch of m examples {x1, x2, . . . , xm} construct minibatch of m tuples {(xi, ¯xi, ¯xj)} optimize WG to min G LD,G +λLH,G end for update B with outputs of H end for Return WD, WH and WG Standard gradient-based optimization methods can be used to learn WD, WH and WG

MNIST [LeCun et al., 1998] and CIFAR-10 [Krizhevsky, 2009]. MNIST is a famous handwritten digits dataset containing a training set of 60,000 examples, and a test set of 10,000 examples. It has been widely used for computer vision tasks to test the generalization of different algorithms. CIFAR-10 dataset consists of 60,000 32 × 32 color images in 10 classes, with 6,000 images per class. There are 50,000 training images and 10,000 test images, respectively.

Since we mainly focus on the unsupervised learning, we compare our method only with the state-of-the-art unsupervised hashing methods, including (1) the shallow models: Local Sensitive Hashing (LSH) [Datar et al., 2004], Iterative Quantization (ITQ) [Gong and Lazebnik, 2011], Spectral Hashing (SH) [Salakhutdinov and Hinton, 2009] and Spherical Hashing (SPH) [Heo et al., 2015]; (2) the deep models: Deep Hashing (DH) [Liong et al., 2015] and Deepbit [Lin et al., 2016]. Both DH and Deepbit are the most recent unsupervised deep hashing solutions. Note that DH doesn't take advantages of the deep convolutional neural network, which simply generates hash codes based on the handcrafted features. We also compare our method with BGAN [Song, 2017] that also utilizes GANs for hashing, but heavily relies on the similarity matrix derived from certain type of features. To make the comparison fair under the settings without any supervised information, for DH, BGAN and PGH we adopt the same type of low-level features, instead of deep features like ResNet trained in a supervised way.

3.1 Implementation and Evaluation Protocols

We implement our PGH model using Pytorch, whose architecture is shown in Figure 1. For the hash conditioned GANs, we adopt a combination of DCGAN and CGAN, where the former improves the quality of synthetic images while the latter provides ability of generating similar and dissimilar samples to specific image. We comply with the practical advices in [Radford et al., 2015] and [Mirza and Osindero, 2014], and make certain necessary modification to fit our problem. As to the training, in all experiments we employ the Adam optimizer with a mini-batch size of 64. Besides, we fix the learning rate and the momentum to 0.0002 and 0.9, respectively. For the hashing network, we simply adopt the popular VGGNet [Simonyan and Zisserman, 2014], where to generate hash codes we replace the softmax function after the last fullyconnected layer with the quantization function in Equation (2). Also we choose the sigmoid as our active function, and the stochastic gradient descent algorithm for the optimization. As to the utilization, on CIFAR-10 we borrow the pre-trained weights from the 16 layers VGGNet, which is trained on the similar large scale natural image dataset ImageNet. We set the start learning rate to 0.0003, and decrease it by 10% every 10 epochs. The mini-batch size is 32, and each image is normalized and rescaled to 224 × 224 as the network input. Different from CIFAR-10, on MNIST we train the hashing network from scratch. The start learning rate is 0.002, decreased by 10% every 20 epochs. Here, we use mini-batch size of 64, and all images are normalized to [-1, 1].

To comprehensively evaluate the hashing performance of different methods, we adopt two common search schemes including the Hamming distance ranking and the hash table lookup. The Hamming distance ranking places those points that have small Hamming distances to the query on the top of the result list. We report the ranking performance on this list in terms of mean average precision (mAP). Hash table lookup works like the popular inverted indexing, where the points falling within a small Hamming radius r (usually r ≤ 2 for efficiency) from the query code are retrieved as the final results. We choose the widely used precision within Hamming Figure 2: PH2 performance on MNIST and CIFAR-10.

(b) CIFAR-10

Figure 3: Visualization of real and synthetic images

radius 2 (PH2) to evaluate the search performance.

3.2 Results and Discussions

We will first investigate the performance of our PGH model on image search, compared to the state-of-the-art unsupervised hashing methods. Then we will analyze our model from the aspects of the convergence and progressive improvement.

Image Search Performance

In the image search experiments, we compare our method with the shallow hashing methods using the hand-crafted features and deep features. On CIFAR-10 we adopt both 512-D GIST features and 4096-D deep features extracted by VGGNet. On MNIST, since deep features are not applicable to handwriting digits in the unsupervised setting, we simply choose the pixel-level features and the GIST features.

Table 1 reports the mAP performance with respect to different number of hash bits. From the table, we can observe that the shallow hashing methods based on pixel features and GIST features achieve comparable performance at a similar level in most cases, compared to the deep methods. Besides, it should be noted that the performance of ITQ is quite close to the deep hashing methods including DH, Deepbit and BGAN. Since DH also takes GIST features as its input, we believe that the low-level hand-crafted features lack the capability of describing the underlying structure of the digital images in MNIST. Besides, we find that Deepbit also fails to obtain significant performance gains over the shallow hashing methods. BGAN can achieve satisfying performance in most cases, guided by a similarity matrix based on GIST features. Our PGH also relies on GIST features, and by inputting the hash codes generated by ITQ on GIST features, it can consistently perform best in most cases. The result proves that PGH owns encouraging ability to pursue more discriminative codes than the input weak ones in the progressive learning.

5

We further study the performance of different methods on CIFAR-10. In this experiments, we first compare the deep hashing methods with the shallow ones with hand-crafted features and deep ones. As the results show, the shallow models with deep features can beat the deep ones, and significantly outperform them with hand-crafted features. For example, ITQ with VGG features can perform better than Deepbit and BGAN in all cases. This phenomenon indicates that the conventional unsupervised hashing methods can also work well if equipped with a good feature representation. On the other hand, it also means that existing deep hashing methods have not fully exploited the hashing nature. From this point of view, we believe that our PGH serves as a novel alternative to discover a discriminative coding solution that can capture the semantic differences between the images, mainly relying on the image triplets generated by the hash conditioned GANs. Therefore, on CIFAR-10 PGH obtains the best performance, with significantly performance gains over the second best.

Model Analysis

Besides the Hamming distance ranking performance, Figure 2 also depicts the PH2 performance on MNIST and CIFAR-10. Here, PGH gives a relatively lower performance when using short binary codes. But we can see that it can largely increase its precision when using more hash bits while others drop quickly, which means that PGH can preserve the semantic relations using the progressively enhanced hash codes, mainly owing to the realistic synthetic images. We will further illustrate this point in the following experiments.

In Figure 3 we show several synthetic images generated by our hash conditioned GANs on MNIST and CIFAR-10, where each subfigure presents the real images and the corresponding synthetic ones respectively at the top and bottom rows. We can easily observe that our framework can provide images with the same semantic but slightly varied, which certainly helps enrich the neighbor relations for the code learning and improve the robustness of the hashing network.

Convergence. Traditional GANs usually suffer from the unstable convergence in practice. Here, our hash conditioned GANs enjoy stable and fast convergence at the training stage. This is mainly because the weak hash codes can help avoid the undesired mode collapse and thus lead the networks to approximate the true semantic distribution of the images. Figure 4 shows the convergence curves on MNIST and CIFAR-10, where we mainly depict the variation tendency after the three networks are trained at the same time.

Progressive Improvement. Besides the fast convergence of hash conditioned GANs, we also want to investigate the property of our whole progressive learning framework. To demonstrate PGH can progressively learn more discriminative hash codes based on the weak hash codes, in Figure 5 (a) and (b) we respectively show how the performance varies on MNIST and CIFAR-10 using 64 bits, with respect to the number T of the progressive iterations. It is obvious that on both datasets the mAP performance increases significantly when we iteratively input the learnt hash codes of last iteration into the current hash conditioned GANs. Therefore, we can conclude that our PGH can learn desired hash codes quickly based on the weak ones and improve the performance gradually. In practice, usually the progressive process can stop in 4-5 iterations when it reaches the convergency.

Intuitively, different input hash codes provide different condition information for image generation using hash conditioned GANs. For example, ITQ with the VGG deep features will transmit more rich semantics into the model than LSH with low level GIST features. To check the effect of the input codes, we consider three different but typical initial input hash codes to start PGH learning. In Table 3, we report the progressive performance of different input hash codes on CIFAR-10. First, we observe that in all cases PGH consistently improves the performance iteration by iteration. More importantly, even though the performance of LSH with GIST features is inferior to that of ITQ with VGG features, we can notably see that all the three types of codes almost converge to the same level of performance in a very few iterations. This means that our model doesn't highly depend on the initial input, but can perform robustly and steadily in practice.

Semantic Discovery. We have pointed out and validated in the prior experiments that our PGH can synthesize semantically realistic images, which together with the original training images are able to discover the underlying semantic similarities among the data. To further verify this conclusion, In Figure 6 (a)-(c) we respectively show the distributions of the 10 classes on CIFAR-10 in 2-D space by PCA, according to the 64-bit hash codes generated by ITQ, Deepbit and our PGH. In these figures, each circle in different color corresponds to a unique semantic class, and its size indicates the variance of hash codes belonging to the class. Compared with ITQ and Deepbit, the best shallow and deep hashing methods as we know, our PGH has the largest inter-similarities among images in the same class, i.e., the average code variance of ten classes is 0.1578, which is much smaller than 0.2141 of ITQ and 0.2010 of Deepbit. Moreover, it can discover the latent semantic similarities among different classes as we expect. Compared with ITQ and Deepbit, PGH owns much stronger capability to distinguish the dissimilar images such as 'bird' images from 'deer' and 'horse' with relatively large distances in Figure 6(c), and exploits the semantically similar ones, such as 'automobile' and 'truck', 'deer' and 'horse', etc., with close hash codes. This further proves that our progressive generative strategy can significantly boost the hashing performance even without supervision information.

4 Conclusion

In this paper we presented a novel unsupervised progressive generative hashing (PGH) architecture, which exploits the power of hash conditioned GANs and the progressive learning. The hash conditioned GANs take weak binary codes to guide image generation, and help train a discriminative hash function based on the triplet loss defined over both real and synthetic images. Through progressively feeding the learned binary codes into the network, we can obtain better deep hash function gradually. Experiments and analysis have demonstrated that PGH can discover the semantic relations, and thus achieve the state-of-the-art performance.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (61690202) and MSRA Collaborative Research Grant.