CIMON: Towards High-quality Hash Codes

1 Introduction

Hashing-based Approximate Nearest Neighbour search has attracted ever-increasing attention in the era of big data due to their high retrieval efficiency and low storage cost. The main idea of hashing methods is to project high dimensional datapoints into compact binary codes while preserving the semantic similarity of original datapoints.

Hashing methods include supervised hashing [Luo et al., 2020; Fan et al., 2020; Wang et al., 2020; Xie et al., 2020] and unsupervised hashing. However, it is difficult to apply supervised hashing methods in practice since large-scale data annotations are unaffordable. To address this problem, several deep unsupervised methods were proposed and provided a cost-effective solution to practical applications [Lin et al., 2016; Yang et al., 2018; Tu et al., 2020]. Recently, most unsupervised hashing methods employ a two-step framework: Firstly, the local semantic similarity structure is reconstructed from the pre-trained neural network. To be specific, the local semantic similarity relationships are often derived from the Euclidean distance or the cosine similarity of deep features extracted from the pre-trained model. Secondly, a hashing network is optimized to generate compact and similaritypreserving hash codes by incorporating the defined similarity structure as the guiding information.

∗Equal Contribution. This work was done when Xiao Luo and Daqing Wu interned in Alibaba Group. †Corresponding authors.

However, the existing methods have two significant drawbacks that will harm the quality of hash codes. First, many false positives and negatives will be introduced in the similarity matrix for the insufficient representation ability of the pre-trained model, which will misguide the hashing model during hash code learning and further reduce the retrieval performance. As shown in Figure 1(a), false similar pairs can occur between the boundary points of two manifolds (blue points). Moreover, most methods treat the confident signals and uncertain signals equally (green and red points), which will also accumulate a lot of errors. Second, few of them consider the stability of models, which will cause hash codes to be unstable under disturbances and greatly influence the quality. For example, images of different classes with similar background could be mapped to the same hash code (called hash collisions) while the transformed image could be quite far away from the original image in the hash code space (Figure 1(b)).

To address the above two issues, we propose a new method named CIMON, which comprehensively explores semantic similarity structure to achieve reliable semantic guidance and considers the stability of hash codes by introducing consistency learning. Specifically, CIMON firstly takes advantage of the global information to remove false positives between boundary points and smooths the unconfident signals by confidence adjustment. Secondly, CIMON generates two groups of deep features by data augmentation and constructs two similarity matrices and both parallel semantic consistency and cross semantic consistency are encouraged to generate robust hash codes. Furthermore, contrastive consistency between hash codes is adopted to improve the quality of hash codes. Through these improvements, CIMON could obtain high-quality hash codes in both retrieval performance and robustness, which is also demonstrated by extensive experiments on several challenging benchmark datasets. Our main contributions can be summarized as following:

• CIMON not only utilizes global refinement to refine the initial local semantic similarity structure, but also explores the similarity statistical distribution to adjust the weight for each image pair, which generates a reliable and smooth guide for hash code learning.
• A novel consistency loss including semantic consistency and contrastive consistency is proposed to optimize the hashing network, which helps to generate robust and discriminative hash codes.
• Experiments on several public datasets demonstrate that CIMON outperforms existing state-of-the-art unsupervised hashing techniques by a large margin.

2 RelatedWork

Deep Unsupervised Hashing. Most of the unsupervised deep hashing methods extract deep features to construct a semantic structure, by which unsupervised problems can be turned into supervised problems. In a quite different way, DeepBit [Lin et al., 2016] regards the original images and the corresponding rotated images as similar pairs and attempts to preserve the similarities when learning related hash codes. Stochastic generative hashing [Dai et al., 2017] tries to learn hash functions by using a generative model based on the minimum description length principle. SSDH [Yang et al., 2018] makes use of a specific truncated function on the pairwise distances and constructs the similarity structures. The hashing model is then trained by supervised hashing techniques. Afterwards, the performance of SSDH is improved by DistillHash, which distills the image pairs with confident similarity signals. Clustering-driven Unsupervised Deep Hashing [Gu et al., 2019] recursively learns discriminative clusters by soft clustering model and produces binary code with high similarity responds. MLS3RDUH [Tu et al., 2020] reconstructs the local semantic similarity structure by taking advantage of the manifold structure in feature space, achieving the stateof-the-art performance.

Contrastive Learning. [Hadsell et al., 2006] is the first work to learn representations by contrasting positive pairs against negative pairs. To solve the storage of large scale dataset, [Wu et al., 2018] proposes to utilize a memory bank for class representation vectors. Various pretext work is based on several forms of contrastive loss function, which is related to the exemplar-based task and noise-contrastive estimation [Dosovitskiy et al., 2014]. Recently, Momentum Contrast [He et al., 2020] proposes to build a dynamic dictionary with a queue and a moving-averaged encoder, which enables building a large and consistent dictionary on-the-fly that facilitates contrastive unsupervised learning. SimCLR [Chen et al., 2020] further simplifies the learning algorithms without requiring specialized architectures or a memory bank and achieves better performance on ImageNet.

3 The ProposedModel

In this section, we first formally define the problem and feature our model with two parts as shown in Figure 2: (1) Semantic information generating. A pre-trained VGGF [Simonyan and Zisserman, 2015] without the last fullyconnected layer F(·) is adopted to extract deep features, which will be used to generate the similarity graph and the confidence-based weight matrix. (2) Consistency learning. The hashing network G(·) is modified from VGG-F by replacing the last fully-connected layer with a fully-connected layer with L hidden units to incorporate the hash code learning process. A novel consistency learning framework is adopted to learn high-quality hash codes.

3.1 ProblemFormulation

In the unsupervised hashing settings, X = {xi}Ni=1 is the training set with N samples without label information. We aim to learn a hash function H : x → b ∈ {-1, 1}L, in which x is the input image and b is a compact L-bit hash code. This map should preserve similarity, i.e., images with similar ground truth labels should correspond to hash codes with small Hamming distances.

3.2 Semantic Information Generating

In our model, semantic information is composed of the similarity pseudo-graph and the similarity confidence matrix.

From the local perspective, the pseudo-graph aims to capture pairwise similarity information. Given the pretrained deep features {F(xi)}Ni=1 , the cosine distance between the i-th and the j-th images is obtained by dij = 1 - F(xi)·F(xj) ||F(xi)||2||F(xj)||2 . Since most pairs should be negative in ground-truth, we set a relatively small threshold t = 0.1 following [Wu et al., 2019], and consider pairs with the cosine distance smaller than t as potential positives (Sij = 1) and pairs with the cosine distance larger than t as potential negatives (Sij = -1). Mathematically, the pseudo-graph S can be constructed as:

(a) Generation of Semantic Information

Global Refinement As mentioned in Figure 1, the features of images with the same semantic information should lay on a high-dimensional manifold following [Yang et al., 2019; Tu et al., 2020] and many false positives and negatives will be introduced in local semantic similarity S [Luo et al., 2021]. Hence, we propose to use the global clustering results to refine the semantic similarity by removing contradictory results. Since spectral clustering has been proven to be suitable for clustering high-dimensional manifold data, we take advantage of it to perform global refinement. Specifically, assume ci ∈ {1, ...,K}, i = 1, · · · ,N is the i-th cluster label of spectral clustering (K is the number of clusters). Then each pair of two points with the same class is considered as global potential similar and vice versa. If an image pair has a different potential similarity signal with pseudo-graph S, its similarity is considered as unreliable. After removing the unreliable signals, the final refined pseudo-graph is ˆ S is formulated as:

ConfidenceAdjustment Note that the semantic confidence of similarity signal for each pair is different, we further construct the confidence matrix for pseudo-graph S based on the semantic confidence. Inspired by recent works [Yang et al., 2018], we observe that the distribution of cosine distances for deep feature pairs can be estimated by two half Gaussian distributions, denoted as N(m1, σ2 1 ) and N(m2, σ2 2 ) respectively, in which m1, m2 and σ2 1 and σ2 2 are the corresponding means and variances. Intuitively, we hypothesize that image pairs with distances obviously smaller than others are semantically 'similar' and those with obviously larger distances are semantically 'dissimilar', which are denoted as highly confident pairs. Moreover, the confidence weights are approximated by Cumulative Distribution Function (CDF) of two half Gaussian distributions. Specifically, for potential similar signals, distances have a more confident similarity signal if dij is closer to 0, and for potential dissimilar signals, distances have a more confident similarity signal if dij is closer to 2. Therefore, confidence-based weight matrix is computed as following:

in which Φk(x) = Φ( x-mk σk ) and Φ(·) is the CDF of standard normal distribution. Under this setting, all Wij ∈ [0, 1] and the confidence weights on both ends are relatively larger.

3.3 Consistency Learning

In order to preserve the similarity structure of input images, similar (dissimilar) images are expected to be mapped into similar (dissimilar) hash codes. Different from previous models, here we adopt two groups of semantic information under two different kinds of data augmentation.

Semantic Consistency For each image xi, there are two transformed samples x(1) i and x(2) i . At the semantic information generating stage, two refined similarity graphs with confidence matrices {W (1) , ˆ S(1) }, {W (2) , ˆ S(2) } are generated with extracted features {F(x(1) i )}Ni=1 and {F(x(2) i )}Ni=1 as the guiding information. Simultaneously, images x(1) i and x(2) i are the inputs of the hashing network G(·), and hash codes b(1) i and b(2) i are obtained through activation function sign(·). Therefore, we derive two similarity outputs H(1) and H(2) from hash codes, which is formulated as

in which m = 1 or 2, and Θ represents the set of parameters of hashing network. For the purpose of preserving the semantic structures, we first minimize weighted L2 loss between the hash code similarity and the corresponding pseudo-graph from the same group. The parallel semantic consistency loss can be formulates as:

Inspired by the cross-attention mechanism [Boussaha et al., 2019], we also match the hash code similarity with the pseudo-graph from the different groups. To be specific, the cross semantic consistency loss can be written as:

Contrastive Consistency Self-supervised learning has been proved to generate high-quality representations for downstream tasks [He et al., 2020]. From this points, we randomly sample a minibatch of M images, producing 2M random transformed images {x(1) i , x(2) i }Mi=1 . Given a positive pair x(1) i and x(2) i , we treat the other 2(M-1) augmented images within a minibatch as negative examples. Denote bi ⋆ bj as cosine similarity of bi and bj ( bi·bj ||bi||2||bj||2 ), the contrastive consistency loss is defined as

where Z (m) i = ∑j̸=i (eb(m) i ⋆b(1) j /τ + eb(m) i ⋆b(2) j /τ ), m = 1 or 2, and τ denotes a temperature parameter set to 0.5 following [Chen et al., 2020]. Note that the numerator of each term punishes the distance between hash codes of samples under different transformation while the denominator encourages to enlarge the distance between hash codes of different samples, which encourages the hash codes to be uniformly distributed in the hash code space from [Wang and Isola, 2020]. This point helps to maximize the capacity of each hash bit [Shen et al., 2018], preserving as much information of the data as possible.

Finally, the loss of consistency learning is formulated as

in which η is a balance coefficient to balance different consistency loss. However, the sign(·) is in-differentiable at zero and the derivation of it will be zero for every non-zero input, with the result that the parameters of the hashing model will not be updated by the back-propagation algorithm when minimizing the Equation 8. Thus, we use tanh(·) to approximate the sign function and generate the approximate hash code v(m) i = tanh(G(x(m) i )) to replace b(m) i in loss function. Our loss function is optimized by the mini-batch standard stochastic gradient descent (SGD) method. The whole learning procedure are shown in Algorithm 1.

Algorithm 1 CIMON's Training Algorithm

Require: Training images X = {xi}Ni=1 ; Code length L; Ensure: Parameters Θ for the neural network G(·);

Hash codes B = {bi}Ni=1 for training images.

• 1: Generate two transformed images via data augmentation for each image: X (1) and X (2) ;
• 2: for m= 1, 2 do
• 3: Get pre-train features of X (m) through F(·);
• 4: Construct the pseudo-graph S(m) by Equation 1;
• 5: Perform global refinement to obtain refined pseudograph ˆ S(m) by Equation 2;
• 6: Construct the confidence matrixW (m) by Equation 3;
• 7: end for
• 8: repeat
• 9: SampleM images fromX and obtain their augmentation to construct a mini-batch;
• 10: Calculate loss function by Equation 8;
• 11: Update parameters of G(·) through back propagation;
• 12: until convergence
• 13: Generate image hash codes B

4 Experiments

We conduct extensive experiments on three popular benchmark datasets to evaluate our CIMON by comparisons with various unsupervised hashing methods.

4.1 Datasets and Setup

FLICKR25K [Huiskes and Lew, 2008] contains 25,000 images labeled by some of the 24 categories. We randomly sample 2,000 images as the query set and use the other images as the retrieval set. 10000 images are randomly selected from the retrieval set as the training set. CIFAR-10 [Krizhevsky et al., 2009] contains 60000 images of ten different categories. We randomly sample 1,000 images as the query set for each class, and take the rest as the retrieval set. We sample 500 images per class in the retrieval set as the training set. NUSWIDE [Chua et al., 2009] contains 269,648 images of 81 concepts. Here, we use the subset that contains the 10 most popular concepts. We randomly select 5,000 images as the query set and the remaining images make up the retrieval set. 5000 images randomly sampled from the retrieval set serve as the training set.

Our CIMON is compared with various state-of-the-art unsupervised hashing methods including both traditional methods and deep learning methods. Traditional methods include ITQ [Gong et al., 2012], DSH [Jin et al., 2013], SpH [Heo et al., 2012] and SGH [Dai et al., 2017]. Deep unsupervised hashing methods include DeepBits [Lin et al., 2016], SSDH [Yang et al., 2018], DistillHash [Yang et al., 2019], CUDH [Gu et al., 2019], and MLS3RUDH [Tu et al., 2020]. For deep learning-based methods, we use raw pixels as inputs. For traditional methods, we extract 4096-dimensional feature vectors by the VGG-F model which is pre-trained on ImageNet for fair comparison.

As for evaluation, the ground-truth similarity information is obtained according to the ground-truth image labels. Specifically, two data points are considered similar if they share the same label or share at least one common label. The retrieval quality is evaluated by Mean Average Precision (MAP), Precision-Recall curve and Top N precision curve. MAP is widely-used to evaluate the retrieval accuracy. Given a query and a list of R ranked retrieval results, the average precision (AP) for the given query can be obtained. MAP is defined to be the average of APs for all queries. For experiments on datasets FLICKR25K and NUSWIDE, we set R as 5000. For CIFAR-10, we set R as 50000. Precision-recall curve can reveal the precision at different recall levels, which is a good indicator of overall performance. As a popular way of the performance visualization, Top N precision curve is the precision curve in regard to the top N retrieved instances.

In our implementation, we optimize our model by minibatch SGD with momentum. The mini-batch size is set to 24. The learning rate is fixed at 0.001. For all three datasets, training images are resized to 224 × 224 as inputs. Data augmentation we adopt includes random cropping and resizing, rotation, cutout, color distortion and Gaussian blur. As two introduced hyper-parameters, η and the number of clusters K in spectral clustering are set to 0.3 and 70 as default.

4.2 Experimental Results

The MAPs of different methods on datasets FLICKER25K, CIFAR-10 and NUSWIDE with hash code lengths varying from 16 to 128 are shown in Table 1. The following observations can be derived: 1) Deep learning-based algorithms overall perform better than the traditional methods, which shows that the strong representation-learning ability of deep learning helps to improve the performance of unsupervised hashing methods. 2) The methods that reconstruct semantic similarity structure with global information (CUDH, MLS3RUDH) perform better than other deep unsupervised hashing methods, which indicates that semantic similarity reconstructed only by local information (i.e. pairwise distance of features) is inaccurate and unreliable. 3) We can find that CIMON has a significant improvement over the previous the-state-of-art MLS3RUDH in all cases by a large margin. Specifically, the improvements of our model over the best baseline are 5.51%, 58.4% and 8.39% for average MAP on datasets FLICKER25K, CIFAR-10 and NUS-WIDE respectively, which shows the superiority of our model. We plot the precision-recall curves of SSDH, CUDH, MLS3RDUH and CIMON on three datasets in the first column of Figure

3. We find that the curve of CIMON is always on top of the other three models' curves, which demonstrates that the hash codes obtained by CIMON are also more appropriate for hash table lookup search strategy. The second column of Figure 3 shows that the Top-N precision curves of these four models on the same datasets. Our CIMON significantly outperforms the comparison methods by large margins. Since the precision curves are based on the ranks of Hamming distance, CIMON achieves superior performance under Hamming ranking-based evaluations.

To demonstrate the robustness of CIMON, we add perturbation or transformation noise to the query set, which doesn't break the semantic information. Figure 4(a) shows the distribution of changed bits number before and after adding noise in query images for MLS3RUDH and our model. It is observed that the mean of changed bits number of CIMON is significantly smaller than that of MLS3RUDH, which implies that CIMON can learn more disturb-invariant hash codes. The MAP of CIMON also decreases less after the noise attack compared with the baseline in Figure 4(b). Moreover, CIMON is able to generate informative hash bits because hash bits distribution of CIMON approximates a uniform distribution, making good use of full bit capacity in Figure 4(c).

Ablation Study We investigate the effectiveness of various correlations in Table 2. M1 uses the local similarity structure as guiding information, and trains the hashing network with the degraded loss following [Yang et al., 2018]. The difference between M2 and M1 lies in whether to use the global refinement or not. It can be seen that M2 surpasses M1 significantly, demonstrating the effectiveness of global refinement for reconstructing the accurate similarity graph. After considering the confidence of semantic similarity, M3 achieves better results than M2 because the refined similarity-graph is still noisy and M3 further accounts for the variations in confident and unconfident pairs, which eases the effect of false similarity signals and enlarges the effect of highly confident signals in the similarity graph. M4 makes use of the data augmentation and our novel semantic consistency loss function. We can see that M4 performs much better than M3, which demonstrates the strength of data augmentation and our welldesigned semantic consistency loss. By comparing the results of M5 and M4, we can see that the contrastive consistency can further improve the performance of our model.

Parameter Sensitivity We study the influence of balance coefficient η and the number of clusters K in Figure 5. We first fix η to 0.1 and 0.3 and evaluate the MAP by varying K from 50 to 110. The performance of our model is not sensitive to the number of clusters in the range of [50, 110] and we can set K as any values in that interval. Furthermore, we show the MAP by varying η from 0.05 to 0.5 with K fixed to 70. The MAP of our model first increases and then keeps at a relatively high level. The result is not sensitive to η in the range of [0.2, 0.5]. Then for the proposed model, K and η are set to 70 and 0.3 respectively.

Visualization In Figure 6, we visualize the top 10 returned images of our model and the best baseline for the query image of CIFAR-10, which demonstrates that our model can retrieve much more relevant and user-desired images.

5 Conclusion

Here we propose a novel deep hashing method named CIMON, which generates reliable semantic information by comprehensive similarity mining from local and global views. Then a novel consistency loss function from the view of semantic matching and contrastive learning is proposed to optimize the hashing model by incorporating the semantic information into the training process. Extensive experiments reveal that CIMON boosts the state-of-the-art unsupervised hashing schemes in both image retrieval and robustness.

Acknowledgements

This work was supported by The National Key Research and Development Program of China (No.2016YFA0502303) and the National Natural Science Foundation of China (No.31871342).