SDMCH: Supervised Discrete Manifold-Embedded Cross-Modal Hashing

1 Introduction

In the last several decades, cross-modal retrieval has attracted lots of attention as it has played a fundamental role in many fields such as visual search, machine translation, and text mining. Typically, in the cross-modal retrieval, one can use a query with one type of modality (e.g., text) to retrieve relevant items with another type of modality (e.g., image). More recently, to tackle the large-scale data, hashing based crossmodal retrieval methods have drawn more and more attention due to the fast query speed and low storage cost [Xu, 2016; Zhang et al., 2017]. Roughly speaking, cross-modal hashing methods can be divided into unsupervised and supervised.

∗Corrsponding Author.

The former learns the hash functions and hash codes by exploiting the inter- and intra-modality relatedness of the given data without utilizing the supervised information. The representative unsupervised hashing methods include Inter-Media Hashing (IMH) [Song et al., 2013], Latent Semantic Sparse Hashing (LSSH) [Zhou et al., 2014], Collective Matrix Factorization Hashing (CMFH) [Ding et al., 2014], Composite Correlation Quantization (CCQ) [Long et al., 2016], and Fusion Similarity Hashing (FSH) [Liu et al., 2017]. The latter can further utilize the semantic information to learn the similarity-preserving hash codes and they have demonstrated better performance than that of unsupervised ones in many real-world applications. The representative supervised methods include Cross View Hashing (CVH) [Kumar and Udupa, 2011], Semantic Correlation Maximization (SCM) [Zhang and Li, 2014], Semantics Preserving Hashing (SePH) [Lin et al., 2015], and Discrete Cross-Modal Hashing (DCH) [Xu et al., 2017]. More recently, some deep cross-modal hashing models have been proposed and obtained promising performance [Jiang and Li, 2017; Yang et al., 2017a].

As shown above, although many cross-modal hashing methods have been explored, there still remains several problems that need to be further explored. 1) Most of them fail to exploit the manifold structure which is important to boost the performance of a model. 2) Most of them only preserve the neighborhood relationship while neglect the relative neighborhood proximity. 3) Many hashing methods leverage the manifold learning to generate the binary codes; however, some fail to fully utilize the semantic information and some relax the binary constraints, generating large quantization errors.

To address the aforementioned challenges, in this paper, we present a novel cross-modal hashing method, named Supervised Discrete Manifold-Embedded Cross-Modal Hashing (SDMCH). It can not only exploit the non-linear manifold structure of data, but also construct the correlations among heterogeneous multiple modalities. In addition, it fully utilizes the semantic information to preserve the similarity and generate more precise hash codes. Based on an iterative algorithm proposed in this work, instead of relaxing the binary constraints, SDMCH generates the hash codes directly. Therefore, SDMCH can avoid the large quantization errors. Moreover, SDMCH is a two-step hashing method, making it flexible and effective. Extensive experimental results on three widely used benchmark datasets demonstrate its superiority over several state-of-the-art cross-modal hashing methods.

2 RelatedWork

2.1 Hashing withManifold Learning

Recent studies have demonstrated that it is beneficial for a retrieval model to exploit the non-linear manifold structure of multimedia data [Yang et al., 2008; Zhang et al., 2015]. Therefore, many methods leverage the manifold learning to generate the hash codes. For example, one well-known work is Spectral Hashing [Weiss et al., 2009], generating the hash codes by thresholding the Laplace-Beltrami eigenfunctions of the manifolds. Some other representative manifold hashing methods include Anchor Graph Hashing [Liu et al., 2011], Locally Linear Hashing [Irie et al., 2014], Inductive Manifold Hashing [Shen et al., 2015], and Discrete Locally Linear Embedding Hashing [Ji et al., 2017]. However, these methods can only work on unimodal data. To deal with the data with multiple modalities, some manifold based multimodal hashing methods have been explored, including Composite Hashing with Multiple Information Sources [Zhang et al., 2011], Multiple Feature Hashing [Song et al., 2011], MultiView Complementary Hash [Liu et al., 2015], and Discrete Multi-View Hashing [Yang et al., 2017b]. However, these models cannot perform cross-modal retrieval, limiting their applications.

More recently, although some cross-modal hashing methods have been explored to leverage the manifold learning, there are still several issues that need to be further considered. For example, some cannot fully utilize the semantic information, e.g., Inter-Media Hashing [Song et al., 2013], Sparse Multi-Modal Hashing [Wu et al., 2014], and FullSpace Local Topology Extraction [Zhang et al., 2015]. Some relax the binary constraints during optimization, generating large quantization errors, e.g., Cross-View Hashing [Kumar and Udupa, 2011], Multimodal Similarity-Preserving Hashing [Masci et al., 2014], Supervised Matrix Factorization Hashing [Tang et al., 2016], and Hetero-Manifold Regularisation [Zheng et al., 2017].

2.2 Two-Step Hashing

Two-step hashing [Lin et al., 2013; 2015; Luo et al., 2018] decomposes the hash learning problem into two steps: 1) The binary code inference step; 2) the hash function learning step. And it has attracted broad research interests due to its simplicity, flexibility and effectiveness.

In the second step, given the learnt hash codes, a two-step hashing method learns hash functions to transform the original features into the compact binary codes. Actually, as Lin et al. revealed [Lin et al., 2013], for any bit of the hash code, learning the corresponding hash function to project features into it can be modelled as a binary classification problem and the learning of hash function is open for any effective predictive model, like SVM, boosted decision trees and deep networks. Therefore, the main differences among the two-step hashing methods lie in the first step, which determines the quality of the generated binary codes. Consequently, the twostep hashing methods focus more on how to design effective loss functions and optimization algorithms.

3 Our Method

3.1 Notations

Suppose there are n training instances and m different modalities. Xt = [xt1 , xt2 , · · · , xtn ] ∈ Rn×dt is the feature matrix of the t-th modality, where dt denotes the dimensionality of its feature space and t = 1, · · · ,m. Without loss of generality, we further suppose that the instances are zero-centered in each modality, i.e., ∑ni=1 xti = 0. In addition, the label matrix for all training instances are Y ∈ {0, 1}n×c , where c is the number of classes, Yik = 1 denotes that xi belongs to class k and 0 otherwise. B ∈ {-1, 1}n×r is the to-be-learnt hash code matrix for the training data, r is the length of the hash codes. ‖·‖F denotes the Frobenius norm of a matrix and Tr(·) is the trace of a matrix. sgn(·) is an element-wise sign function defined as sgn(x) = 1 if x ≥ 0, and -1 otherwise.

3.2 Manifold Structure Learning

To embed the manifold structure into the binary codes learning, we first construct the similarity matrix by leveraging Locally Linear Embedding [Roweis and Saul, 2000]. Specifically, one point is approximated as a weighted linear combination of its K-nearest neighbours. The formulation is defined as follows,

where Ptij = 0 if xi and xj are not neighbours in the tth modality and K is the number of neighbors of one instance. By solving Eq. (1), we can learn the weights Pt (t = 1, · · · ,m). To save space, in this work, we do not give the details of how to solve the above problem, which can be found in [Roweis and Saul, 2000]. Besides, other manifold approaches can also be used to substitute LLE in our model. As it is not the focus of this paper to study different manifold methods, we just use LLE for illustrating the effectiveness of SDMCH.

Thereafter, the manifold structure preserving similarity matrix St is defined as Stij = |Ptip | if xtj is the p-th neighbor of xti and Stij = 0 otherwise, where Ptip is the j-th element of Pti . In addition, to ensure the symmetry of St , we further update it with St ← ((St )⊤ + St ).

3.3 Objective Function of SDMCH

Manifold Embedding. To preserve the manifold similarity in the Hamming space, we further define the following problem,

where Lt = Dt - St , and Dt is a diagonal matrix whose entries are given by Dtii = ∑nj=1 Stij . In addition, F is a temporary real-valued representation used to approximate B. Therefore, the first term is used to preserve the manifold similarity in the temporary representation space; the second one is to make F approximate B as much as possible.

Label Preserving. To make full use of the label information, we further assume that the labels can be obtained from the binary codes. For this purpose, we define the following formulation,

where G is a projection matrix, mapping B to Y.

Overall Objective Function. Combining Eq. (2) and (3), we obtain the overall objective function of SDMCH,

where λt, α, β, γ are balance parameters. It is worth noting that, in the fourth term, we replace B with a semanticpreserving latent representation Z. In addition, the third term is introduced to make Z approximate B as much as possible. Intuitively, by solving Eq. (4), both the manifold structure and semantic information can be embedded into the hash codes. Moreover, due to the use of F and Z, the problem becomes easy to be efficiently solved by an iterative optimization scheme without relaxation as shown in the following subsection.

3.4 Optimization

To solve the optimization problem in Eq. (4), we propose a four-step iterative scheme as shown below.

F Step. When Z, G, and B are fixed, the optimization problem can be formulated as,

Setting the derivative of Eq. (5) w.r.t. F to zero, we have,

where A = α(∑mt=1 λtLt + αI)-1 is constant and can be precomputed.

Z Step. Fixing F,G, and B, the problem in (4) is transformed to,

Setting the derivative of Eq. (7) w.r.t. Z to zero, we have,

G Step. When F, Z, and B are fixed, Eq. (4) becomes,

Algorithm 1 Optimization algorithm in SDMCH.

Input: The manifold-embedded similarity matrices St , the label matrix Y, the parameters λt, α, β and γ, the hash code length r, and the iterative number T .

• 1: Randomly initialize F, Z, G, and B.
• 2: for iter = 1 → T do
• 3: Fix Z,G, and B, and update F using Eq (6).
• 4: Fix F,G, and B, and update Z using Eq (8).
• 5: Fix F, Z, and B, and update G using Eq (10).
• 6: Fix F, Z, and G, and update B using Eq (12).
• 7: end for

Output: F, Z,G, and B.

It is a least squares problem w.r.t G, which has a closed-form solution,

B Step. When F, Z, and G are fixed, we can transform all terms into the trace operations, omit the constant terms, and rewrite Eq. (4) as follows,

Thereafter, the optimal solution can be obtained,

The Whole Algorithm. The above optimization procedure is summarized in Algorithm 1.

3.5 Hash Functions Learning

As mentioned previously, SDMCH is a two-step hashing method. In the second step, it adopts the linear regression as the hash functions. Specifically, given the binary codes B learnt in the first step, the hash projection matrix for the t-th modality, i.e., Wt , is learnt by optimizing the following problem,

where θ is a balance parameter, and ‖ Wt ‖2F is a regularization term. Thereafter, the optimal Wt is computed with the following equation,

Once we have obtained Wt , for the query data with the t-th modality Xtquery , the hash codes are generated as follows,

4 Experiments

To evaluate the performance of SDMCH, we conducted extensive experiments on three benchmark datasets and compared it with ten state-of-the-art hashing methods.

4.1 Datasets

Experiments are conducted on three benchmark datasets, i.e., Wiki [Rasiwasia et al., 2010], MIRFlickr [Huiskes and Lew, 2008], and NUS-WIDE [Chua et al., 2009], which are described below.

Wiki consists of 2, 866 image-text pairs collected from Wikipedia. Each instance is annotated with one of 10 semantic classes. The image and text of each instance are represented by a 128-dimension SIFT feature vector and a 10dimension topic vector, respectively. It was initially split into a training set with 2, 173 instances and a test set of 693 instances.

MIRFlickr consists of 25, 000 instances collected from Flickr website, each being manually annotated with at least one of 24 labels. The image and text modalities are represented by a 150-dimension edge histogram and a 500dimension vector generated from PCA on its index tagging vector, respectively. We randomly selected 25% instances of the dataset as the query set, and the remaining 75% ones as the training set.

NUS-WIDE contains 269, 648 instances crawled from Flickr. Each instance has an image with its associated textual tags and is manually annotated with at least one of 81 labels. However, some instances' labels are scare; so we followed the same setting of previous works [Zhou et al., 2014; Lin et al., 2015; Xu et al., 2017] and selected 10 most common concepts and the corresponding 186, 577 instances. For each instance, the visual view is represented by a 500dimension bag-of-visual SIFT feature vector and the textual view is represented by a binary tagging vector w.r.t. the top 1, 000 most frequent tags. We select 2% of the data as the query set and the rest as the training set.

Due to the large computational cost of some baselines, we randomly selected 5,000 instances on MIRFlickr and 10,000 instances on NUS-WIDE from the original training set to train all models.

4.2 Baselines and Implementation Details

Considering that SDMCH is not a deep model, we compared SDMCH with ten shallow state-of-the-art cross-modal hashing methods including: five unsupervised ones, i.e., IMH, LSSH, CMFH, CCQ, and FSH; five supervised ones, i.e., CVH, SCM-orth, SCM-seq, SePH-km, and DCH. The source codes of most baselines are kindly provided by the authors. We carefully tuned their parameters according to the scheme suggested by the authors. All experiments are repeated several times with random data partitions, and the averaged results are reported.

For SDMCH, its parameters are set to K = 6, λ1 = 0.3, λ2 = 0.7, α = 0.3, β = 5, γ = 1000 and θ = 1, selected by a validation procedure. In addition, the total iterative number T in Algorithm 1 is set to 10.

4.3 EvaluationMetrics

In the experiments, we conducted two cross-modal retrieval tasks: 1) Image-to-Text using images as the query to search texts; 2) Text-to-Image using texts as the query to search images. We adopted three widely-used performance metrics for multi-modal hashing to evaluate all methods, namely mean average precision (MAP), top-N precision curves, and precision-recall curves.

4.4 Overall Comparison with Baselines

MAP Results: The MAP values of SDMCH and all baselines on the three datasets are summarized in Table 1. From this table, we have the following observations. First, SDMCH obtains the best results in all cases and performs much better than the baselines in some cases, well demonstrating its effectiveness on the datasets. Second, all of the methods generally perform better at the Text-to-Image task than Image-toText. The main reason is that the text modality can better describe the content of an image-text pair than the image modality. Third, supervised methods, such as DCH, SePH-km, and SDMCH, perform better than unsupervised ones, demonstrating the effectiveness of full utilization of the semantic information.

Top-N Precision Curves: Figure 1 illustrates the topN precision curves in the cases of 64-bit and 128-bit code lengths on the three datasets. From this figure, we have the following observations. First, the curve of SDMCH is much higher than those of the other baselines in most cases, well demonstrating its superiority. Second, SDMCH, DCH, SePH-km, SCM-seq, and FSH are in the first group, performing better than the other baselines. Third, supervised methods, such as DCH, SePH-km, and SDMCH, generally perform better than unsupervised ones, and this phenomenon is consistent with the results in Table 1.

Precision-Recall Curves: The precision-recall curves in the cases of 64-bit and 128-bit code lengths are plotted in Figure 2. We have the similar observations to those with respect to the MAP and Top-N precision curves. For example, SDMCH always performs the best and performs much better than the baselines in some cases; generally, supervised ones also perform better than unsupervised ones.

In summary, SDMCH can achieve the state-of-the-art accuracy, demonstrating that embedding both the manifold structure and semantic information can ensure more precise hash codes. It also verifies the effectiveness of the loss function and optimization algorithm of SDMCH.

4.5 Convergence Analysis

We further made empirical analysis of its convergence by experiments on the three datasets with the hash code length being 128-bit. The curves of the objective values on the three datasets are plotted in Figure 3. It is worth noting that, for convenience, the objective values are normalized by dividing the maximums on each dataset. From this figure, we can observe that SDMCH can converge quickly. For example, it converges within 10 iterations on the three datasets, well demonstrating the effectiveness of the loss function and the iterative optimization algorithm.

4.6 Time Cost Analysis

The time complexity of solving Eq. (8), Eq. (10) and Eq. (12) is O(nr+ncr+r2 +r2 c+r3 +nr2 ), O(nr2 +r3 +nrc+nr2 ), and O(nr + nr), respectively. Since c, r ≪ n, the overall computational complexity of these steps is linear to the size of training data n. Since we can precompute A and A is a sparse matrix, the computation of Eq. (6) is also very efficient.

To verify the efficiency of SDMCH, we further compared the training time (in seconds) of all methods on MIRFlickr. The results are summarized in Table 2 and some observations can be found from these results. First, unlike some baslines, e.g., CCQ, SePH-km, and DCH, the training time of SDMCH does not significantly increase when the code length becomes longer. Second, some baselines, such as CMFH, CVH, and SCM-seq, can be trained fast. However, as shown in the above Section 4.4, their retrieval accuracy is much worse than that of SDMCH. Third, DCH is competitive with SDMCH on the accuracy as shown in Table 1; however, it needs much more training time than that of SDMCH, especially in the cases of longer code lengths.

Therefore, considering both the accuracy and training time, we can conclude that SDMCH is more practical than the baselines.

5 Conclusion and FutureWork

In this paper, we present a novel supervised cross-modal hashing method, named Supervised Discrete ManifoldEmbedded Cross-Modal Hashing, SDMCH for short. With preserving the similarity constructed by manifold learning, SDMCH can exploit the non-linear manifold structure of data and construct the correlation among heterogeneous multiple modalities. Moreover, it can fully utilize the semantic information and generate the binary codes discretely. Extensive experiments on the three benchmark datasets demonstrate that SDMCH outperforms ten state-of-the-art crossmodal hashing methods.

In this work, we implement SDMCH as a shallow model because we want to focus on the design of the loss function and optimization scheme. Recently, deep hashing models have demonstrated more promising results. In our future work, we plan to extend it to a deep hashing model.

Acknowledgments

This work was partially supported by the Key Research and Development Program of Shandong Province (2016GGX101044), the National Natural Science Foundation of China (61573212, 61772310, 61702300, 61702302), and the Project of Thousand Youth Talents 2016.