A survey on deep supervised hashing methods for image retrieval

Convolutional Neural Network Hashing(CNNH) [2] is the first approach to make full use of the CNN architecture. It first proposes a scalable coordinate descent method to decompose the pairwise similarity matrix $\displaystyle S$ into $\displaystyle HH^{T}$, where $\displaystyle H$ is a matrix with each of its row being the approximate hash code associated to a training image. Then feature representations of training images are learnt through a CNN architecture as well as a set of hash functions. Moreover, the author further improve the stage of hash functions learning by incorporating the image class labels as a part in the output layer.

Figure1 shows the overview of CNNH. It consists of two main stages. In stage1, approximate hash codes are calculated by minimizing the following reconstruction errors:

where $\displaystyle H$ is $\displaystyle n\times q$ matrix, with each row being the target q-bit hash code of image $\displaystyle I_{k}$. $\displaystyle S_{i,j}=1$ when $\displaystyle I_{i},I_{j}$ are semantically similar, $\displaystyle S_{i,j}=-1$ respectively. In stage2, CNNH simultaneously learn a feature extractor for query images as well as a set of hash functions.Herein, CNNH leverages the convolutional neural network to take advantage of the 2D structure of images and to learn the underlying features, and then uses these features to control the outcomes of the corresponding hash codes.

CNNH devises a CNN architecture in which the CNN can be viewed as a feature extractor and capture the underlying semantic structure of images in spite of significant appearance variations. From this aspect, it surpasses most classical hashing methods. However, since it is the first try with the CNN architecture, it inevitably has some drawbacks. In this two-stage method, the learned approximate hash codes are used to guide the learning of the image representation, but the learned image representation cannot give feedback for learning better approximate hash codes. It seems like these two stages are in a bit of reverse order.

One should note that in supervised learning, similarity set $\displaystyle S=\{s_{ij}\}$ can be constructed from semantic labels of data points or relevance feedback from click-through data in real retrieval systems. Although CNNH is not an end-to-end method, the requirement of the similarity matrix should not be viewed as a main drawback. In fact, such matrix is involved as the supervised information in most of the deep supervised methods.

In CNNH, the approximate hash codes are determined at the very beginning of the whole process, which seems to be contradictory to our common logic. The approximate hash codes guide the learning process of hash function, which fails to give any feedback to the hash codes learning process. In other words, a pair of semantically similar or dissimilar images may not have feature vectors with relatively small or large Euclidean distance. This one-way interaction is limited and needs to be changed.

Deep Neural Network Hashing(DNNH) [3] generates hash codes of images through a CNN-based architecture. Throughout the deep network, input images are converted into unified image representations via a shared subnetwork of stacked convolution layers. Then, as shown in figure2, these intermediate image representations are encoded into hash codes by divide-and-encode procedure. Specifically, the input intermediate features are divided into $\displaystyle q$ slices, with each of the slices mapped to one dimension by a fully connected layer. Furthermore, a triple ranking loss is designed to preserve relative similarities as well as pulling dissimilar pairs far away.

This work makes a few designs on the network architecture. First, at the end of the full-connected layer, each hash bit is generated from a separated slice of features in order to reduce the redundancy among the hash bits. Second, in order to encourage the output of a divide-and-encode module to be binary codes, a sigmoid activation function is used followed by a piece-wise threshold function. Third, a triplet loss function is designed to characterize that two images are similar and other two are dissimilar. Unlike CNNH, this one-way method plans as a whole for the two learning stage and make sure the two stages are instructing each other so that the coding process is compatible with the feature-extraction process.

Deep Supervised Hashing(DSH) [4] constructs a CNN architecture and elaborately designs a loss function to maximize the discriminability of the Hamming space by encoding the supervised information from the input image, then imposes regularization on the real-valued outputs to approximate the desired discrete values. As shown in figure3, DSH devises a CNN model which processes pairs of images to determine whether two images are similar and then generates the corresponding hash code with relatively small distance. The loss function is designed to make sure similar query points are projected to close outputs in Hamming space

and push the outputs of the dissimilar ones far away. The loss function is defined as:

where $\displaystyle m>0$ is a margin threshold parameter. The first term punishes similar pairs when projected far away. The second term punishes dissimilar pairs projected close when their distance fall in the threshold $\displaystyle m$. Suppose N pairs are trained, the loss function is defined as :

.

Herein, we cannot directly optimize this loss function due to the discrete constraints. A common relaxation method is to use $\displaystyle tanh$ or $\displaystyle sigmoid$ function to approximate the discrete constraints. However, working with such non-linear function would slow down the network. DSH designs the loss function by adding a regularizer as follows.

In this work, a novel idea is to impose an additional regularizer to replace the binary constraints and substitute the sigmoid function or tanh function, non-linear functions restraining and slowing the convergence of the network, especially when the output is near the boundary. The proposed regularizer overcome the problem because its gradient is always 1. More importantly, DSH is an end-to-end architecture. The learned approximate hashing codes are used to guide the learning of the image representation and the learned representation gives feedback to the learning of hash codes.

Deep Anchor Graph Hashing(DAGH) [5] mainly addresses the mini-batch issue. Due to the high computation cost and limited hardware’s memory, lots of deep supervised hashing methods will first select a subset from the training set, and then form a mini-batch to update the network in each iteration. Therefore, the remaining labeled data cannot be fully utilized and the model cannot directly obtain the binary codes of the entire training set for retrieval. This method regards the samples in subsets as anchors and design a regression term to establish the connections between the anchors and all the binary codes. A training subset is selected in every iteration and is used to update the neural network by back-propagation.

The DAGH gives a try to tackle the mini-batch issue by using the anchor graph to characterize the similarities between the deep features and all the binary codes. But we should note that this issue is caused by CNNs, whether or not the time-consuming is less by this work which actually do not improve the CNNs architecture should be tested further. However, we should admit that this work provides us with a new perspective towards the mini-batch issue.

Although the mini-batch issue is difficult to solve, Deep Incremental Hashing Network(DIHN) [6] open a new path to somehow tackle the issue. DIHN learns the hash codes for the new coming images directly, while keeping the old ones unchanged. We should remind that the incremental hashing codes are not simply quantified through the original deep hashing network. Instead, DIHN first devises a incremental hashing loss to preserve the semantic similarity between training points, and then learns the new incremental binary codes by integrating the CNN learning model into the incremental hashing loss. DIHN is the first deep incremental hashing approach, It simultaneously generate hash codes for incremental database images and learn a CNN model for producing hash codes for query images. Predictably, DIHN performs well on large scale retrieval system and decrease the training time with no accuracy decline.

Most deep supervised hashing methods adopt a symmetric strategy to learn one deep hash function for both query points and database points. The training of these symmetric deep supervised hashing methods is typically time-consuming. The storage and computational cost for these hashing methods with pairwise supervised information is $\displaystyle\mathcal{O}(n^{2})$ where n is the number of database points. Besides the requirement of mini-batch for CNNs, most deep supervised hashing methods subject to the time-consuming hashing learning procedure so that only a small subset from the whole database are sampled. Asymmetric Deep Supervised Hashing(ADSH) [7] treats the query points and database points in an asymmetric way. ADSH learns a deep hashing function only for query points, while the hash codes for database points are directly learned. The computational cost of ADSH is $\displaystyle\mathcal{O}(n)$.

As shown in Figure4, the model architecture of ADSH consists of two parts, namely feature learning part and loss function part. Unlike previous hashing methods, ADSH assumes that the whole database contains $\displaystyle m$ query points $\displaystyle X=\{x_{i}\}_{i=1}^{m}$ and $\displaystyle n$ database points $\displaystyle Y=\{u_{j}\}_{j=1}^{n}$. The corresponding binary hash code are denoted as $\displaystyle U=\{u_{i}\}_{i=1}^{m}\in\{-1,+1\}^{m\times k}$ and $\displaystyle V=\{v_{j}\}_{j=1}^{n}\in\{-1,+1\}^{n\times c}$ . In the feature learning part, ADSH adopt the CNN architecture to extract semantic feature from the query images and leverages the outputs to construct the following loss function.

However, it is difficult to optimize $\displaystyle h(x_{i})$ due to the discrete constraints, so ADSH sets $\displaystyle h(x_{i})=sign(F(x_{i},\mathcal{O}))$, where $\displaystyle\mathcal{O}$ is the parameter of the CNN model. Moreover, ADSH adds a regularizer to keep $\displaystyle v_{i}$ and $\displaystyle tanh(F(y_{i},\mathcal{O}))$ as close as possible. So the final loss function is designed as:

In the loss function stage, the learning algorithm consists of two stages. In the first steps, we learn $\displaystyle\mathcal{O}$ with $\displaystyle V$ fixed. By back propagation algorithm, the neural network parameters $\displaystyle\mathcal{O}$ is updated. In the second stage, we learn $\displaystyle V$ with $\displaystyle\mathcal{O}$ fixed. So the problem can be rewritten as

. We can get the optimal solution as:

where, $\displaystyle U_{*k}$ denotes the $\displaystyle k$th column of $\displaystyle U$ and $\displaystyle\tilde{U_{k}}$ denotes the matrix of $\displaystyle U$ excluding $\displaystyle U_{*k}$

Although it seems incredible to reduce the computational complexity so much, we have to notice that the feature of the database points are not taken into account throughout the whole algorithm since the hash codes for database points are directly learned without the CNNs extracting the features. As a result, the binary codes for database points are not compact with respect to those query points. However, this work gives us a new perspective. And a possible improvement for this work can be adding an additional procedure in which the database points and the query points reverse their positions. A whole new loss function is probably able to be given. What’s more, the computational cost should still be O(n). We can go on looking for this trying then.

HashNet [8] mainly focuses on two problems in deep supervised hashing, ill-posed problem and data imbalanced problem.

First, most deep learning hash methods have to give a continuous representation through CNNs and generate binary hash codes in separated step, which would result in suboptimal binary codes. HashNet addresses this problem by gradually reducing the amount of smoothing during the training, which results in a sequence of optimization problems converging to the original optimization problem. Second, the similarity information is usually very sparse in real retrieval systems. The number of similar pairs is much smaller than the number of dissimilar pairs. This will result in the data imbalanced problem, making similarity-preserving ineffective. HashNet tackles the problem by weighting the training pairs according to the importance of misclassifying the pair.

HashNet addresses deep learning to hash from imbalanced similarity data by a continuation method. Admittedly, this continuation method cannot be applied to large-scale dataset since it will definitely cost too much running time. On the other hand, it is better to adopt this method to check out those updates during every iteration in most deep supervised hashing methods.

Based on HashNet, Deep Cauchy Hashing(DCH) [9] improves the Hamming space retrieval by designing a pairwise cross-entropy loss based on Cauchy distribution, which penalizes significantly on similar image pairs with Hamming distance larger than the given Hamming radius threshold. Most state-of-the-art deep hashing methods usually adopt generalize sigmoid function as the probability function. However, we can observe that the probability of generalized sigmoid function stays high when the Hamming distance between hash codes is much larger than 2 and only starts to decrease obviously when the Hamming distance becomes close to $\displaystyle K/2$. DCH solves the misspecification problem of sigmoid function by constructing the probability function based on the Cauchy distribution instead of the sigmoid function. As we know, for large-scale dataset, to quantize the distances among those compact and concentrated hash codes is significant. The DCH approach enables more efficient and effective Hamming space retrieval based on a Bayesian learning framework. However, the drawbacks of DCH is also apparent. To compensate the efficient retrieval among concentrated hash codes, most of the distances in Hamming spaces are probability stay quite large, thus obscuring the original image retrieval.

DCH mainly focuses on concentrating relevant images to be within a small Hamming ball, thus enables the most efficient constant-time search, which is Hamming space retrieval, instead of using linear scan. DCH first proposed a Bayesian learning framework to perform deep hashing on query images by quantizing the similarity of pairwise images. The goal is converted to maximize the likelihood function:

where $\displaystyle P(\mathcal{S}|\textbf{H})=\prod_{s_{i,j}\in\mathcal{S}}[P(s_{i,j}|h_{i},h_{j})]^{\omega_{ij}}$,$\displaystyle P(s_{i,j}|h_{i},h_{j})=\sigma(d(h_{i},h_{j}))^{s_{ij}}(1-\sigma(d(h_{j},h_{j})))^{1-s_{ij}}$,$\displaystyle\sigma$ is probability function.

Most deep hashing methods adopt sigmoid function $\displaystyle\sigma=\frac{1}{1+e^{-\alpha x}}$ as probability function. DCH proposed to use a novel probability function based on Cauchy distribution so as to concentrate relevant images to be within a small Hamming ball and make efficient Hamming space retrieval possible.

We are given a training set of $\displaystyle N$ images: $\displaystyle I={I_{1},I_{2},..,I_{N}},I_{i}\in R^{d_{1}\times d_{2}\times 3}$. $\displaystyle Y={y_{i,j}}$ is the corresponding supervised information, which is the similarity matrix in this case. For image $\displaystyle I_{i}$ and $\displaystyle I_{j}$,$\displaystyle Y_{i,j}=0$ if they are similar, and $\displaystyle Y_{i,j}=1$ otherwise. We denote the binary network output of $\displaystyle I_{i}$ by $\displaystyle b_{i}$,where $\displaystyle b_{i}\in\{\pm 1\}^{k}$, $\displaystyle k$ is the length of hashing codes.

Our goal is to give a map from $\displaystyle I$ to $\displaystyle k$-bit binary codes: $\displaystyle F:I_{i}\rightarrow b_{i}$ , such that the distances of hashing codes from similar pairs are small, while large for dissimilar pairs.

The purpose of supervised hashing is to preserve the small Hamming distances between hashing codes from similar images. As a result, we should minimize the following loss function:

However, we cannot directly optimize (1) through back propagation due to the discrete constraints. To fulfill the discrete constrains, lots of supervised methods leverage a common relaxation scheme, which is to replace $\displaystyle b_{i}$ by $\displaystyle sigmoid(b_{i})$ or $\displaystyle tanh(b_{i})$ and get the final hashing codes by $\displaystyle signum$ function. Nevertheless, such nonlinear functions will definitely slow down the learning process[222] and the $\displaystyle signum$ function may lead to suboptimal results. To tackle this problem, a good idea is to transfer the discrete constraints into the regularizer terms. Specifically, a loss function is designed as:

Herein, L2-norm is used to measure the distances between pairs instead of Hamming distance because the subgradient of Hamming distance will treat pairs with different distances equally. Although this model achieves relatively good performance, the disadvantage is obvious. We should notice that the absolute value of subgradient of the regularizer always stays at $\displaystyle\alpha\cdot\mathbf{1}$. During training, when the first term is becoming relatively small compared to the regularizer, the subgradient causes the loss function create jump movements. As a result, the loss function will be basically caught at a value and fails to be optimized further.

Given that we have gave up utilizing nonlinear relaxation in loss function and regularizer with subgradient like (1), how can we express the discrete restriction in the loss function?

We propose the concept: the ”shadow” $\displaystyle u_{i}$ of the network output $\displaystyle b{i}$. During training, we use the ”shadow” to instruct the learning of $\displaystyle b_{i}$. In this process, ”shadow” stays fixed until this epoch of training ends. Then in the next step, the ”shadow” is determined according to the output of the neural network. In other word, $\displaystyle b_{i}$ and its shadow $\displaystyle u_{i}$ are guiding each other in the whole process. Specifically, our loss function is defined as:

During optimization, we sequentially update the parameters of the deep neural network and binary matrix $\displaystyle U$ in the following two steps: First, update weights with U fixed: we use back propagation to update the neural network parameter. In each iteration, we randomly sample a minibatch of images and use BP algorithm to update the weights. The gradient of the loss with respect to $\displaystyle b_{i}$ follows:

In the second step, we update U according to instant B. When B is fixed ,(2) becomes:

So we have,$\displaystyle U=sign(B)\quad(4)$.

We iteratively solve the above two steps until the loss function reaches the optimal solution. The algorithm can be summarized as Algorithm1.