Feature adaptive multi-view hash for image search

1.   Introduction

The rise of mobile phone and internet users is also fueling the explosive growth of data. This brings two challenges, i.e., (1) how to save the storage cost ^[1,2]; (2) how to achieve fast nearest neighbor retrieval ^[3,4]. The storage cost of saving the original feature is prohibitively high for the first challenge. The classic linear scan solution to nearest neighbor search is not scalable in practical applications for the second challenge. For the second challenge, approximate nearest neighbor search gives faster search speed than nearest neighbor retrieval by balancing accuracy and speed of arithmetic. Among them, tree-based search schemes perform well for low-dimensional data by partitioning the data space via various tree structures^[5,6]. For high-dimensional data, these methods cannot achieve satisfactory performance and do not guarantee faster search compared to linear scan^[7].

For the first challenge, hash methods^[7,8] have been proposed to encode large-scale data, such as images, videos, documents and so on, into a sequence of bits, called hash code. They are designed to embed data from high dimensional feature space into a similarity-preserving low dimensional Hamming space. Hash methods can be categorized into two main categories of hashing algorithms, namely data-independent and data-dependent methods. Data-independent methods include the famous locality sensitive hashing (LSH). The hash codes are generated by a random hash functions satisfying the local sensitive property for various distance measures^[9,10,11,12] followed by rounding. Data-dependent methods can be categorized into unsupervised hashing methods and supervised hashing methods. In unsupervised hashing methods, graph-based ^{[8,13,14,15,16,17]} and vector quantization hashing ^[18,19,20] methods have attracted considerable attention in hashing. In graph-based hashing methods, data-dependent compact binary codes can be obtained by graph based dimensionality reduction. In vector quantization based hashing methods, the feature space is divided into a set of subspaces and compact binary codes are obtained via quantizing each subspace separately into clusters. For example, Jégou et al.^[18] introduced a product quantization based approach for approximate nearest neighbor search. The basic idea is to divide the feature space into a Cartesian product of low dimensional subspaces and then to quantize each subspace separately into clusters. Norouzi et al. ^[19] extended product quantization and introduced a rotation matrix into quantization loss. Zhang et al. ^[20] proposed a novel compact coding approach. The basic idea is to use the composition of several elements selected from the dictionaries to accurately approximate a vector. A constraint condition is introduced into the objective function that the summation of the inner products of all pairs of elements that are used to approximate the vector from different dictionaries is constant. In the supervised hashing method, the class labels information approximate nearest neighbor search. Shakhnarovich ^[21] designed a boosted similarity sensitive coding to learn a similarity from weighted Hamming distance for task-specific similarity search. Hinton et al. ^[22] proposed a binary encoding method with stacked restricted boltzmann machines (RBMs), which can be applied to learn binary codes. Kulis et al. ^[23] proposed a binary reconstructive embedding (BRE) hashing method based on explicitly minimizing the reconstruction error between the metric space and Hamming metric. Wang et al. ^[24] proposed a semi-supervised hashing (SSH) method, which minimized empirical error over the labeled set and maximized the variance of each hash function at the same time.

Most of the prior data-dependent hashing methods take only a single type of feature into consideration, referred to as single-view hashing. In practice, images captured from different scenes in the real world should be represented by different kinds of features to obtain a comprehensive and accurate description. These features describe different characteristics of the given image from different views. Incorporating the multiple features into hash learning, which is referred to as multi-view hashing, has been explored widely. The multi-view hashing methods can be divided into two categories: view-specific hashing methods and view-integrated hashing methods. View-specific hashing methods learn independent hash codes for each view of an instance, and then concatenate multiple view-specific binary codes into the final hash codes. Bronstein et al. ^[25] proposed a framework for supervised similarity learning based on embedding data from different feature spaces into the Hamming space. The hash codes are learned using AdaBoost framework. Kumar et al. ^[26] proposed a cross-view hashing method, which is based on a spectral hashing framework. The similarity of pairwise instances in the Hamming space is computed by summing the Hamming distance of inter views and intra views. Zhen and Yeung ^[27] proposed a Co-Regularized hashing method, which is based on the large-margin strategy while effectively preserving the inter-modality similarity. The view-integrated hashing methods learn unified hash codes for each instance. Zhang et al. ^[28] proposed a composite hashing with multiple information sources (CHMIS) method, which is based on spectral hashing and the maximum margin framework. The affinity matrix is computed by the summation of the affinity matrix from each view. A consistency constraint that the output of hash functions should be close to final integrated hash codes is introduced. Kim et al. ^[29] proposed a multi-view anchor graph hashing (MVAGH) method, which extended single view spectral hashing to multi-view hashing. All single view anchor graphs are combined to approximate the averaged neighborhood graph. Then a random walk method on the multi-view anchor graph is utilized to compute the similarity of pairwise instances. Kim et al. ^[30] proposed a multi-view spectral hashing (MVSH) method, which integrated multi-view information into binary codes, and uses the product of codewords to avoid undesirable embedding. Wang et al. ^[31] proposed a partial multi-modal, i.e., some views of the instances are missing, hashing method. This type of hashing method combines the formulation of matrix decomposition that can find the latent shared semantics, and spectral clustering. Liu et al. ^[32] proposed a multi-view alignment hashing method based on regularized kernel nonnegative matrix factorization. Liu et al. ^[33] proposed a multiple feature kernel hashing method, which preserved certain similarities with linearly combined multiple kernels corresponding to different features. However, large quantization error will be introduced via a sign function and the robustness of multi-view hashing is ignored.

In this paper, we propose a novel feature adaptive multi-view hashing (FAMVH) method based on a robust multi-view quantization framework as shown in Figure 1. Specifically, we utilize multiple feature representations for each image and learning adaptive weights in the vector quantization process. In addition, the $\ell_{2, 1}$-norm loss is embedded in minimizing the reconstruction error and alleviating the impact of outliers. Finally, our approach is evaluated on three large-scale datasets for an approximate nearest neighbor (ANN) search task. All in all, our method is a view-integrated hashing method based on $\ell_{2, 1}$-norm loss, which is robust to outlier data. Our contributions in this paper are summarized in the following:

● We propose a novel feature adaptive hashing method which can integrate multi-view to generate compact and integrated hash codes.

● An efficient algorithm is designed to optimize the proposed method.

● Our approach achieves superior performances in ANN experiments on three large scale datasets.

The remainder of this paper is organized as follows: In Section 2, we briefly introduce the related work. Section 3 presents the detail of our proposed approach. Discussions and analyses are given in Section 4. Section 5 provides extensive experimental validation on three datasets. The conclusions and future work are given in Section 6.

2.   Related work

2.1.   Product quantization

Product quantization (PQ)^[18] splits each $P$ dimensional feature $x_{i}$ into $M$ disjoint subvectors, where the dimension of each subvector is $S_{m}$ and $\Sigma_{m = 1}^{M}S_{m} = P$. The PQ method formulates the encoding problem as follows:

where $N$ is the number of sample instances, ${\textbf{C}}^{i}$ is $m$-th sub codebook and each column is a $S_{m}$ dimensional sub codeword, $\mathcal{H}_{1/K}\equiv\{{\textbf{b}}|{\textbf{b}}\in\{0, 1\}^{K}\; and\; \|{\textbf{b}}\| = 1\}$, i.e., b is a binary vector comprising a 1-of-$K$ encoding. The disadvantages of this method are as follows: $1)$ the $\ell_{2}$-norm used in the objective function is not robust to the outlier data, $2)$ the reconstruction error is high and thus leads to limited search accuracy.

2.2.   Cartesian k-means

The original $p$-dimensional feature space is splitted into $m$ subspaces. $m$ subcenters can be obtained by sub-quantizing the features in each subspace into $h$ centers. In ^[19], each center of original feature space is modeled with a compositional parameterization of $m$ subcenters, each with $h$ elements. The learning objective for Cartesian k-means is to minimise the within-cluster squared distances:

where $\mathbb{D}\equiv\{{\textbf{x}}_{j}\}_{j = 1}^{n}$ denotes a dataset comprising $n$ $p$-dim data points. ${\textbf{C}}\equiv [{\textbf{C}}^{(1)}, \cdots, {\textbf{C}}^{(m)}]\in \mathbb{R}^{p\times mh}$ is block diagonal matrix comprising $m$ subcenters set, where ${\textbf{C}}^{(i)}\in \mathbb{R}^{p\times h}$ is a matrix whose columns comprise the elements of the $i^{th}$ subcenter set and ${{\textbf{C}}^{(i)}}^{T}{\textbf{C}}^{(j)} = 0_{h\times h}, \forall i\neq j$. ${\textbf{C}}$ can be expressed as a product ${\textbf{R}}{\textbf{D}}$, where ${\textbf{R}}\in \mathbb{R}^{p\times p}$ is an orthogonal matrix, i.e., ${\textbf{R}}^{T}{\textbf{R}} = {\textbf{I}}_{p\times p}$, and ${\textbf{D}}\in \mathbb{R}^{p\times mh}$ is a block diagonal matrix.

Then ${\textbf{C}}^{(i)} = {\textbf{R}}^{(i)}{\textbf{D}}^{(i)}$. ${\textbf{D}}^{(i)}\in \mathbb{R}^{s_{i}\times h}$ and ${\textbf{R}}^{(i)}\in \mathbb{R}^{p\times s_{i}}$, where $s_{i} = rank(C^{i}), \sum_{i = 1}^{m} s_{i}\leq p$.

The objective in Eq (2.2) can be solved by an iterative coordinate descent method. Since the rotation matrix ${\textbf{R}}$ is optimally learned, the CKM can achieve lower quantization error than PQ. The performance with $\ell_{2}$-norm embedded in the objective function is susceptible to the outlier data. In addition, the CKM is a single view hashing method and can not integrate multiple features naturally.

2.3.   Multi-view k-means clustering

Cai et al. ^[34] proposed a heterogeneous features clustering method by sharing the same clustering results in different views. ${\textbf{X}}^{(v)}\in \mathbb{R}^{d_{v}\times n}$, $v = 1, \ldots, M$, is used to represent the input data matrix with $n$ instances and $d_{v}$-dim features in the $v$-th view. ${\textbf{F}}^{(v)}\in \mathbb{R}^{d_{v}\times K}$ is the cluster centroid matrix in the $v$-th view. ${\textbf{G}}\in \mathbb{R}^{K\times n}$ is the shared cluster assignment matrix and each row of ${\textbf{G}}$ satisfies the 1-of-$K$ encoding scheme, i.e., $\mathcal{H}_{1/K}$. The proposed multi-view $K$-means clustering method can be solved:

where $\|{\textbf{X}}\|_{2, 1} = \sum_{i = 1}^{n}\|{\textbf{x}}_{i}\|_{2}$, ${\textbf{x}}_{i}$ is the $i$-th column of ${\textbf{X}}$. $\ell_{2, 1}$-norm has been proved robust to noise points^[35,36,37].

The solution of the energy function in Eq (2.3) can be obtained by alternate optimizing over all the variables and the intermediate auxiliary variable. It can not generate compact hash codes as the cost of storing the centers grows linearly with $K$.

3.   Proposed method

The framework of the proposed method is demonstrated in Figure 2. In this section, we first define some terms and notations that will be utilized throughout the paper. In the following subsection, we introduce our feature adaptive multi-view hashing approach, referred as FAMVH. The alternate optimization algorithm is presented in the next subsection. The convergence analysis of FAMVH is given in the end.

3.1.   Terms and notations

Let $V$ denote the number of views, $N$ be the number of instances, ${\textbf{X}}^{v} = [{\textbf{x}}^{v}_{1}, {\textbf{x}}^{v}_{2}, \ldots, {\textbf{x}}^{v}_{N}]\in \mathbb{R}^{d_{v}\times N}$ denote the feature matrix corresponding to the $v$-th view of all the instances. Each ${\textbf{x}}_{i}^{v}$ is split into $M$ disjoint subvectors $\{[{\textbf{x}}_{i}^{v}]^{m}\}$. Assume the $m$-th subvector $\{[{\textbf{x}}_{i}^{v}]^{m}\}$ contains $s_{m}^{v}$ dimensions and then $\sum_{m = 1}^{M}s_{m}^{v} = d_{v}$.

3.2.   Formulation

The straight-forward way of combining all views of features is to concatenate all features together, which has been used in scene classification ^[38], object recognition ^[39] and etc. Feature concatenation preserves the raw information such that hashing methods can utilize the correlation among views. However, in such method, these features are often very high dimension, at the same time, the important view of features and the less important view of features are treated equally, which may not yield optimal hash codes since the structural information of each view has been lost. It is ideal to simultaneously perform the encoding using each view of features and unify their results based on their importance to the encoding task. To achieve the above purpose, three challenging problems have to be solved: 1) how to naturally assemble the multiple encoding losses, 2) how to learn the importance of views to the encoding task, 3) how to learn a compact hash code.

When performing a multi-view clustering algorithm, the clustering results in different views are required to be unique. Therefore, in multi-view hashing, we force the hash codes to be the same across different views. In the meantime, the data outliers can greatly affect the performance of hashing. To alleviate the effect of outlier data in the iterative optimization process, the sparsity-inducing norm, i.e., $\ell_{2, 1}$-norm, is utilized in our quantization loss. The formulation of robust multi-view k-means hashing is as follows:

where ${\textbf{D}}_{v}^{m}\in \mathbb{R}^{s_{m}^{v}\times K}$ is the $m$-th sub codebook for $v$-th view and each column is a $s_{m}^{v}$-dimensional sub codeword. ${\textbf{b}}_{i}^{m}$ is the 1-of-$K$ encoding on the $m$-th subvector. ${\textbf{R}}^{v}\in \mathbb{R}^{d_{v}\times d_{v}}$ is a rotation matrix for the $v$-th view. $\alpha^{(v)}$ is the weight factor for the $v$-th view and $\gamma$ is the parameter to control the weights distribution.

3.3.   Optimization algorithm

The problem in Eq (3.1) is NP hard and difficult to solve with the discrete variable ${\textbf{b}}_{i}^{m}$. There are four types of unknown variables, ${\textbf{R}}^{v}, {\textbf{D}}_{v}^{m}$, ${\textbf{b}}_{i}^{m}$ and $\mathit{\boldsymbol{\alpha}}$. An alternating iteration process is performed where three of them are fixed, and the other one is optimized. Before performing optimization, we introduce some symbols for convenience as follows:

The object function is re-written in a matrix form as

where ${\textbf{B}}\in\{0, 1\}^{MK\times N}$ has been defined in Eq (3.5).

To solve the problem in Eq (3.6), we add intermediate variables $\{\mathit{\boldsymbol{\Lambda}}^{v}\}$ and reformulate the object function as

where $H^{v} = Tr\{({\textbf{X}}^{v}-{\textbf{R}}^{v}\widehat{{\textbf{D}}}_{v}{\textbf{B}})\mathit{\boldsymbol{\Lambda}}^{v}({\textbf{X}}^{v}-{\textbf{R}}^{v}\widehat{{\textbf{D}}}_{v}{\textbf{B}})^{T}\}$. $\mathit{\boldsymbol{\Lambda}}^{v}\in \mathbb{R}^{N\times N}$ is the diagonal matrix for $v$-th view. The $i$-th entry on the diagonal is defined as follows:

where $\delta$ is a very small positive value to avoid the denominator being zero and ${\textbf{E}}_{i}^{v}$ is the $i$-th column of ${\textbf{E}}^{v}$, which is defined as follows:

● Solve ${\textbf{R}}^{v}$ with $\widehat{{\textbf{D}}}_{v}$, $\mathit{\boldsymbol{\Lambda}}^{v}$, ${\textbf{B}}$ and $\mathit{\boldsymbol{\alpha}}$ fixed:

The objective function can be written as

Equation (3.10) can be rewritten as

where $(\mathit{\boldsymbol{\Lambda}}^{v})^{\frac{1}{2}}$ denotes the square root of entries on the diagonal of matrix $\mathit{\boldsymbol{\Lambda}}^{v}$. Then optimizing ${\textbf{R}}^{v}$ is the standard Procrustes Problem ^[40]. The solution of the problem can be obtained by single value decomposition (SVD): ${\textbf{X}}^{v}\mathit{\boldsymbol{\Lambda}}^{v}({\widehat{{\textbf{D}}}_{v}{\textbf{B}}})^{T} = {\textbf{U}}\mathit{\boldsymbol{\Sigma}}{\textbf{V}}^{T}$, the optimal ${\textbf{R}}^{v}$ will be ${\textbf{U}}{\textbf{V}}^{T}$.

● Solve $\widehat{{\textbf{D}}}_{v}$ with ${\textbf{R}}^{v}$, $\mathit{\boldsymbol{\Lambda}}^{v}$, ${\textbf{B}}$ and $\mathit{\boldsymbol{\alpha}}$ fixed:

With straightforward algebraic manipulation, Eq (3.11) can be written as

since

where columns of $({\textbf{R}}^{v})^{\perp}$ span the orthogonal complement of the column-space of ${\textbf{R}}^{v}$, i.e., the block matrix [${\textbf{R}}^{v}$ $({\textbf{R}}^{v})^{\perp}$] is orthogonal. The second term in the formula described above is independent of $\widehat{{\textbf{D}}}_{v}$.

Taking the derivative of $\mathcal{L}_{1} = \|({\textbf{R}}^{v})^{T}{\textbf{X}}^{v}(\mathit{\boldsymbol{\Lambda}}^{v})^{\frac{1}{2}}-\hat{{\textbf{D}}}_{v}{\textbf{B}}(\mathit{\boldsymbol{\Lambda}}^{v})^{\frac{1}{2}}\|_{2}^{2}$ with respect to $\widehat{{\textbf{D}}}_{v}$, we can get

Setting Eq (3.14) as 0, each $\widehat{{\textbf{D}}}_{v}$ can be updated as ${\textbf{R}}^{v}{\textbf{X}}^{v}\mathit{\boldsymbol{\Lambda}}^{v}{\textbf{B}}^{T}({\textbf{B}}\mathit{\boldsymbol{\Lambda}}^{v}{\textbf{B}}^{T})^{\dagger}$, where $(\cdot)^{\dagger}$ denotes the matrix pseudo inverse. As the pseudo inverse will cause numerical instability, we will adopt another optimization method which is more simple. Since $\hat{{\textbf{D}}}_{v}$ is a diagonal block matrix and $\mathit{\boldsymbol{\Lambda}}^{v}$ is a diagonal matrix where the entries in the diagonal are positive, the Eq (3.13) can rewritten as

where $[({\textbf{R}}^{v})^{T}{\textbf{x}}_{i}^{v}]^{m}$ is the $m$-th subvector of $({\textbf{R}}^{v})^{T}{\textbf{x}}_{i}^{v}$. $\{{\textbf{D}}_{v}^{m}\}_{m = 1}^{M}$ can be optimized independently by solving

where ${\textbf{b}}_{i}^{m}$ is the class label vector Eq (3.16) is similar to the weighted k-means clustering. Let $\mathcal{K}$ be the number of classes. Then ${\textbf{D}}_{v}^{m}$ can be updated as

where $C_{k}$ denotes class label $k$, $p$ is the index corresponding to the $p$-th entry in vector ${\textbf{b}}_{i}^{m}$ whose value is 1 and ${[{\textbf{D}}_{v}^{m}]}_{p}$ denotes the $p$-th column of ${\textbf{D}}_{v}^{m}$.

● Solve ${\textbf{B}}$ with ${\textbf{R}}^{v}$, $\mathit{\boldsymbol{\Lambda}}^{v}$, $\widehat{{\textbf{D}}}_{v}$ and $\mathit{\boldsymbol{\alpha}}$ fixed:

From Eq (3.6), ${\textbf{B}}$ can be decoupled into columns and optimized column by column.

where $\widehat{{\textbf{b}}}_{i}$ has been given in Eq (3.4). With the intermediate variable $\mathit{\boldsymbol{\Lambda}}^{v}$, Eq (3.18) can be reformulated

Equation (3.18) can be expanded as in Eq (3.13). The formula is given as

where $[({\textbf{R}}^{v})^{T}{\textbf{x}}_{i}^{v}]^{m}$ is the $m$-th subvector of $({\textbf{R}}^{v})^{T}{\textbf{x}}_{i}^{v}$, $const$ is independent of variable ${\textbf{b}}_{i}^{m}$. ${\textbf{b}}_{i}^{m}$ can be solved by optimizing

where

The ${\textbf{b}}_{i}^{m}$ can be obtained by performing nearest neighbor (NN) search for $\widetilde{{{\textbf{x}}}_{i}}^{(m)}$ to find the assignments coefficients. $\mathit{\boldsymbol{\Lambda}}^{v}$ can be updated by Eq (3.8).

The Lagrange function associated with Eq (3.23) is defined as

Taking the derivative of $\mathcal{L}_{3}$ with respect to $\alpha^{(v)}$, we can find the optimum $\alpha^{(v)}$ by setting the derivative to zero.

which yields the optimal

Substitute the optimal $\alpha^{(v)}$ in Eq (3.26) into the constraint $\sum_{v = 1}^{V}\alpha^{(v)} = 1$, we get

The optimization process is performed by alternatively updating $\mathit{\boldsymbol{\Lambda}}^{v}$, ${\textbf{R}}^{v}$, $\widetilde{{\textbf{D}}}^{(m)}$, ${\textbf{b}}_{i}^{m}$ and $\alpha^{(v)}$ until convergence. The whole algorithm is summarized in Algorithm 1.

3.4.   Convergence analysis

The convergence proof of our proposed method is given as follows. Let the original objective function in Eq (3.6) be $\mathcal{L}({\textbf{R}}, \widehat{{\textbf{D}}}, {\textbf{B}}, \mathit{\boldsymbol{\alpha}})$, where ${\textbf{R}} = \{{\textbf{R}}^{v}\}_{v = 1}^{V}, \widehat{{\textbf{D}}} = \{\widehat{{\textbf{D}}}_{v}\}_{v = 1}^{V}$. For the $t$-step iteration, the alternate update procedure contains the following four subproblems:

where the update procedure of auxiliary variables $\{\mathit{\boldsymbol{\Lambda}}^{v}\}_{v = 1}^{V}$ is omitted for convenience. Thus we have the following inequality:

It indicates that $\mathcal{L}({\textbf{R}}^{(t)}, \widehat{{\textbf{D}}}^{(t)}, {\textbf{B}}^{(t)}, \mathit{\boldsymbol{\alpha}}^{(t)})$ are monotonic nonincreasing as $t\rightarrow \infty$. Finally, the algorithm will converge to a local optimal solution.

4.   Discussion and analysis

4.1.   Computation complexity analysis

The update of the diagonal matrix $\mathit{\boldsymbol{\Lambda}}^{v}$ depends on the matrix ${\textbf{E}}^{v}$ in Eq (3.8). The time complexity to compute ${\textbf{E}}^{v}$ is $O(Nd_{v}^{2})$. The complexity of updating the diagonal matrix $\mathit{\boldsymbol{\Lambda}}^{v}$ is $O(Nd_{v})$. The complexity of updating ${\textbf{R}}^{v}$ requires $O(Nd_{v}^{2}+Nd_{v}+d_{v}^{3})$ time. The complexity of updating the dictionary ${\textbf{D}}_{v}^{m}$ is $O(N(K+s_{m}^{v})+Ns_{m}^{v}d_{v})$. The complexity of updating ${\textbf{b}}_{i}^{m}$ is $O(K+\sum_{v = 1}^{V}s_{m}^{v}d_{v}+K\sum_{v = 1}^{V}s_{m}^{v})$. The updating of $\widehat{{\textbf{D}}}_{v}$ and ${\textbf{B}}$ can be implemented in parallel computating. The complexity of updating $\mathit{\boldsymbol{\alpha}}$ is $O(V)$. The total time complexity of the proposed method is $O(TN\sum_{v = 1}^{V}d_{v}^{2})$, where $T$ is the number of iterations.

4.2.   Approximate nearest neighbor search

In this subsection, we discuss the ANN for comparing quantization techniques. Let ${\textbf{q}}^{v}\in \mathbb{R}^{d_{v}}$ be the $v$-th view of a query instance and ${\textbf{x}}_{i}^{v}\in \mathbb{R}^{d_{v}}$ be the $v$-th view of the $i$-th database point. The $i$-th instance is encoded as $\widehat{{\textbf{b}}}_{i}\in \{0, 1\}^{MK}$ which has been defined in Eq (3.4). The asymmetric quantizer distance between a query $q$ and the binary code $\widehat{{\textbf{b}}}_{i}$ of $i$-th instance is

Given a query, these distances for each $v$, and all $K\times M$ possible values of $\widehat{{\textbf{b}}}_{i}$ can be pre-computed and stored in a query-specific $V\times K\times M$ lookup table. Finally, there are $V$ addition operations to compute the distance $distAQD(q, \widehat{{\textbf{b}}}_{i})$. If the query point is also represented by the binary codes, the symmetric quantizer distance between the query binary codes $\widehat{{\textbf{b}}}_{q}$ and $\widehat{{\textbf{b}}}_{i}$ is given by

We can pre-compute $(\alpha^{(v)})^{\gamma}\|{\textbf{R}}^{v}\widehat{{\textbf{D}}}_{v}\widehat{{\textbf{b}}}_{q}-{\textbf{R}}^{v}\widehat{{\textbf{D}}}_{v}\widehat{{\textbf{b}}}_{i}\|_{2}$ and store them in an $V\times M\times K\times K$ lookup table. Finally, there are $V$ addition operations to compute the distance $distSQD(\widehat{{\textbf{b}}}_{q}, \widehat{{\textbf{b}}}_{i})$.

5.   Experiments

5.1.   Evaluation metric

For each dataset, we use each instance in the testing set as a query example to retrieve instances in the training set. The Hamming ranking by the approximate distance criteria is adopted to perform fair evaluation. In our following experiments, we use three different metrics^[24]: the precision, recall and mean average precision (MAP) for the top $N$ retrieved instances.

where $N_{t}$ and $R_{t}$ denotes the true number of retrieved true nearest neighbor instances in top $N$ retrieved instances.

where $T$ denotes the number of relevant true nearest neighbors.

Average precision (AP) of top $N$ retrieved instances is defined as^[41]:

where $\delta(i)$ is a indicator function, i.e., if the item at rank $i$ is a relevant true nearest neighbor of the given query, $\delta(i) = 1$, otherwise $\delta(i) = 0$. Then MAP can be computed as the mean of AP.

5.2.   Experimental settings

In this section, we evaluate our proposed methods for the high dimensional nearest neighbour search problem with multiple features. Our experiments are carried on three different datasets: Caltech-256^*, CIFAR-10 and CIFAR-20 ^†. The images from Caltech-256 dataset spans 256 object categories ranging from grasshopper to tuning fork with rich color information and texture detail information. The CIFAR-10 and CIFAR-20 datasets share the same images, which are widely used in the community of image retrieval.

^*http://www.vision.caltech.edu/Image_Datasets/Caltech256/

^†https://www.cs.toronto.edu/kriz/cifar.html

Caltech-256. It consists of 30,607 images, each of which is associated with 256 object categories with more than 80 images per category.

CIFAR-10. It consists of 60,000 32 $\times$ 32 color images collected from a subset of 80-million tiny images dataset^{‡ [42]}. It contains 10 class labels with 6,000 images in each class.

^‡http://horatio.cs.nyu.edu/mit/tiny/data/index.html

CIFAR-20. It consists of 60,000 32 $\times$ 32 color images, which belong to 20 superclasses. It is referred as the CIFAR-100 dataset with the 100 fine classes label removed.

For all datasets, we randomly select 1000 images as the query set and the rest of the dataset is used as the training set, following the experimental setting in ^[29,43]. We use scene descriptor GIST ^[44], shape descriptor HOG ^[45], local binary descriptor LBP ^[46], color histogram descriptor, and the bag of visual words descriptor BOW. More concretely, the experimental settings are listed as follows:

-GIST: Gabor filters are applied with 8 different orientations and 4 scales. Each Gabor-filtered image is then averaged over 4 $\times$ 4 grid, which leads to a 512-dimensional vector ($8\times4\times16 = 512$).

-HOG: The image gradients are computed in non-overlapping windows, where the orientation of gradients is quantized into 9 bins and normalized with 4 different normalization factors. Each image is resized into 64 $\times$ 64. We use the publicly available VLFeat toolbox^{§ [47]} to extract HOG features. The cell size is set to 8 $\times$ 8. The length of the ultimate feature vector is 1984-dimensions ($8\times8\times31 = 1984$).

^§http://www.vlfeat.org/

-LBP: The uniform LBP labels the pixels of an image by thresholding a 4 $\times$ 4 neighborhood, and the response is mapped to a 243-dimensional vector.

-ColorHist: The intensities are quantized into 64 bins for each color channel which yield a 192-dimensional color histogram vector ($3\times64 = 192$).

-BOW: The dense SIFT features are quantized into 300-dimensional visual words.

In the test phase, a retrieved point is regarded as a true nearest neighbor if it lies in the top 100,500 and 500 points closest to a query for Caltech-256, CIFAR-10 and CIFAR-20, respectively, similar to ^[32]. Since we use $\ell_{2, 1}$-norm in our model, we also verify the existing methods based on $\ell_{2, 1}$-norm distance for fair comparison. The distance between a query q and an instance x in the database is calculated as $dist({\textbf{q}}, {\textbf{x}}) = \sum_{v = 1}^{V}\|{\textbf{q}}^{v}-{\textbf{x}}^{v}\|_{2}$, where ${\textbf{q}}^{v}, {\textbf{x}}^{v}$ are the $v$-th view of ${\textbf{q}}$ and ${\textbf{x}}$, respectively. The experiments are performed using Matlab 2014a on a server configured with a 2-core processor and 32 GB of RAM running the Windows OS.

5.3.   Evaluation on large scale datasets

In order to validate the efficiency of our approach, we design two experiments: approximate nearest neighbor experiments and comparison experiments on multiple views.

5.3.1.   Approximate nearest neighbor experiments

In ANN experiments, we compare our FAMVH with CKM^[19] hash and PQ^[18]. We set $K = 256$ to make lookup tables small as the same in ^[19]. All the features are normalized. For CKM and PQ, the normalized multiple features are concatenated into a single representation. We use the publicly available source codes of CKM and PQ to perform the comparison experiments. In our approach, a parameter $\gamma$ is used to control the weight factor distribution among all views. The optimal $\gamma$ is selected from one of $\{0.001, 0.01, 0.1, 1.01, 10,100\}$ which yields the best performance. We report the experimental results with $M$ being set to 4, 8, 16 for code length 32, 64,128. The maximal number of iterations for the whole algorithm was set to 10. In Figures 2, 3 and 4, the abbreviations AQ and SQ denote the asymmetric quantizer distance and symmetric quantizer distance metrics in approximate nearest neighbor search, respectively.

Figures 3, 4 and 5 illustrate the recall on Caltech-256, CIFAR-10 and CIFAR-20, respectively. As shown in Figure 3, our approach and CKM outperform PQ for the code length 32, 64 and 128 under the same type of approximate nearest neighbor distance metric. The performances of our approach and CKM are competitive. FAMVH does not seem to have a significant advantage over CKM. The main reason can be attributed to the larger category sizes and larger clutter categories. From the results on CIFAR-10 and CIFAR-20 as shown in Figures 4 and 5, we can see that our approach outperforms all the others under the same type of approximate nearest neighbor distance metric. The performance of methods with the AQ metric significantly outperforms the corresponding methods with the SQ metric. The reason is that the symmetric quantizer distance encodes both the query and the database instances, while the asymmetric quantizer distance only encodes the database instances. As the code length increases, the performances of our approach and CKM increase too. The performance of PQ increases as the code length increases from 32 bit to 64 bit and decreases from 64 bit to 128 bit. The possible reason is that the lack of an optimal rotation matrix yields inconsistent results with the true nearest neighbors.

5.3.2.   Comparison experiments on multiples views

In the multiple views experiment, we compare our approach (FAMVH) against four popular unsupervised multiview hashing algorithms, i.e., MVAGH ^[29], Sequential Update for Multi-View Spectral Hashing (SU$\_$MVSH)^[30], Multi-View Hashing (MVH$\_$CS)^[26] and LSH. Since LSH is a data independent hashing method, it can be extended to deal with the multiple views hashing problem with multiple features being concatenated into a single representation. The experimental settings are the same in ANN experiments. It is worth noting that these benchmark methods including MVAGH, SU$\_$MVSH and MVH$\_$CS share similar ideas of feature clustering with the proposed method. The source codes of ^[26,29,30] have not been published. We implement them ourselves. The results in terms of precision-recall curves are reported in Figures 6, 7 and 8 respectfully. The corresponding MAP values are listed in Table 1. As shown in Figures 6, 7 and 8, our approach achieves the most superior performance gain of all the compared algorithms on Caltech-256, CIFAR-10 and CIFAR-20 datasets. The performance of LSH is next to us on the three datasets. MVAGH performs the worst over the three datasets. The main possible reason is that the computation of similarities is based on the low-rank approximation of the averaged similarity, which is computed by random walk, while the true nearest neighbor is calculated by the summation of the square root of distances in each view.

6.   Conclusions

In this paper, we propose a feature adaptive multi-view hash method, which aims to generate a binary code to approximate the nearest neighbor (NN) search in multiple views. The method extends the classic cartesian k-means hashing method to multi-view. It not only integrates the multi-view naturally, but also generates compact hash codes. In experiments on large scale ANN search tasks, the experimental results are good. In our future work, the kernel extension of our method will be investigated in dealing with nonlinear feature mapping.

Use of AI tools declaration

The authors declare they have not used artificial intelligence (AI) tools in the creation of this article.

Acknowledgments

I would like to thank all anonymous reviewers for their constructive comments through each stage of the process.

Conflict of interest

The authors declare there is no conflicts of interest.