Efficient Image Retrieval via Decoupling Diffusion into Online and Offline Processing

Introduction

The success of deep neural networks on feature representation has led it to become a standard technique in image retrieval. Models pre-trained on popular datasets such as ImageNet (?), Landmarks (?) etc. can be used to extract features of images. Particularly, convolutional layers have been proved to be most beneficial at retrieving images (?; ?; ?; ?). Nearest neighbor search is then used on the feature vectors to find the most similar images to a query.

Datasets are usually scraped from the internet, resulting in images with the same object/landmark shown in a variety of angles, lighting, and other conditions. The diversity often results in a manifolds in the feature space that are not conducive to ranking using a distance-based metric. Unlike the rigid distance metric used in $k$-NN search, diffusion (?; ?; ?; ?) exploits the intrinsic manifold structure of data based on a neighborhood graph. Such a graph consists of nodes and edges, where each node represent a feature vector from the database, with the edges connect each node to its neighbors with corresponding weights proportional to the pairwise affinities between nodes. Using this graph, diffusion performs a restartable random walk given a query as the initial state. The final state of random walk can be viewed as ranking scores showing the similarities of each image in database to the query. To obtain the convergence of the final state, there are two main approaches: running iterative random walk or computing the convergence state by the closed-form theorem proposed in (?). Diffusion has demonstrated its potential in improving retrieval performance (?; ?; ?), and is also utilized in other fields such as unsupervised learning (?). Recently, other works have attempted to improve the efficiency of diffusion (?), but their speed up is still not sufficient enough to handle the amount of queries found in large-scale image retrieval datasets.

We notice that the main bottlenecks in speed of online diffusion processes come from the random walk and preparation steps. Inspired by the closed-form solution of diffusion, we find that the diffusion for each query can be converted to a linear combination of the pre-computed diffusion results of all database elements. Following this observation, our proposed method completely removes the random walk from the online stage. As a result, our work is able to improve the efficiency of the diffusion process by a factor of ten in a large-scale image retrieval setting.

In addition, the previous versions of diffusion utilize an early truncation that happens before the affinity matrix normalization process. In our proposed process, we propose to perform a late truncation after normalization, that results in significantly better performance. Fig. 1 summarizes the efficiency and performance of the aforementioned methods. The source code to replicate our experiments is available at https://github.com/fyang93/diffusion.

Related Works

Although originally developed for ranking on manifolds (?; ?; ?), diffusion was soon applied to classification (?), and image segmentation (?). Recently, some variants of diffusion (?; ?; ?; ?) are also developed to conduct diffusion processes on tensor product graph with a smoothness criterion, showing its potential for image retrieval tasks as a re-ranking method.

Query expansion, a common technique in image retrieval, can improve retrieval performance during query time. Average query expansion (AQE) (?; ?), a popular type of query expansion because of its simplicity, averages the features of the query’s nearest neighbors to form a new query to run search again. When AQE is applied iteratively, the recomputation of the query is akin to traveling along the manifolds of the feature space. Although this traversal is similar to diffusion, AQE only utilizes the relationships between query and database images, but not between each of the database images with each other. With prior knowledge of the relationships between all of the database images, diffusion is thus better able to exploit the manifolds in the feature space than query expansion can.

In previous works of diffusion, the query is provided as a part of the database. However, in a real-world setting, queries are unavailable until they are issued by users. To tackle this issue without introducing any computational overhead, (?) uses the short list of $k$-NN search results to form a sparse initial state vector, instead of using a one-hot vector as the initial state. As a consequence, queries are not included in the neighborhood graph. The downside to this is that the graph needs to be stored and loaded during the search stage for random walk, which is both memory and computationally inefficient. Since the previous methods were evaluated on the Oxford (?) and Paris (?) datasets, smaller datasets only containing 55 queries, the inefficiency of those methods did not have much impact on the total computation time. When these methods are used on large-scale datasets with many queries, the inefficiency during online search becomes magnified and intractable.

To tackle this inefficiency, past efforts have been made to scale diffusion up to handle larger datasets. (?) proposed to accelerate the construction of the affinity matrix denoting the graph. Iscen et al. reported that Dong’s method is orders of magnitude faster than exhaustive search with only limited decreases in performance (?). Another approach to improve efficency is using approximate nearest neighbor search (ANN). Compared to constructing the graph by exhaustive $k$-NN search, ANN search is faster and provides comparable accuracy (?; ?). Most recently, (?) approximated the affinity matrix by using a low-rank spectral decomposition to reduce the online computational cost. However, this method did not result in much improvement in terms of retrieval performance.

Preliminaries of Diffusion

There are two main approaches to conducting diffusion: through iterative updates or solving the closed form directly. Both Zhou et al. and Donoser et al. describe diffusion as a mechanism for spreading the query similarities over the manifolds (?; ?), while Iscen et al. utilizes the closed form theorem in (?) and proposed an efficient solution (?). We mainly follow the steps from (?) and (?) below.

Graph construction.

$\forall i,j\in\{1,\dots,n+m\}$, denoting $\textrm{NN}_{k}(\mathbf{x})$ the $k$-NNs of $\mathbf{x}$. Since the similarity metric $s$ is usually symmetric and positive, $\mathbf{A}$ is a symmetric matrix. Eq. 1 allows $\mathbf{A}$ to be sparse, providing memory and computational efficiency.

The degree matrix $\mathbf{D}$ is a diagonal matrix and each diagonal element is the corresponding row-wise sum of $\mathbf{A}$, i.e. the element $d_{ii}$ in $\mathbf{D}$ is defined as $\sum_{j=1}^{n+m}a_{ij}$. It’s later used to symmetrically normalize $\mathbf{A}$ into the stochastic matrix $\mathbf{S}$:

$\mathbf{S}$ is a variant of the typical transition matrix $\mathbf{D}^{-1}\mathbf{A}$, and both have the same eigenvalues and eigenvectors (?).

Random walk.

Essentially, there is a probability $\alpha$ to randomly walk from the current state $\mathbf{f}^{t}$ or $1-\alpha$ to restart from the initial state $\mathbf{f}^{0}$. Given the fact that $\alpha\in(0,1)$ and the abstract eigenvalues of $\mathbf{S}$ is no larger than 1 according to the Perron-Frobenius theorem, this iteration converges to a closed-form solution (?):

After convergence, the values in $\mathbf{f}^{*}$ contain the similarities of each database element to the query, which will be used as ranking scores for re-ranking.

Decomposition.

The above steps incorporate the query into the graph during the diffusion process. Grady proposed to decompose queries from the above operations (?), and his technique was recently followed by (?).

where $\mathbf{S}_{dd}$ can be viewed as the transition matrix for random walk on the database side, and $\mathbf{S}_{dq}=\mathbf{S}_{qd}^{\top}$ consists of normalized similarities between the query and its nearest neighbors. Subsequently, we can then obtain the cleaner form:

Truncation.

$\forall i,j\in\{1,\dots,L\}$, where $\mathcal{I}_{i}$ is the $i$-th index in the set $\mathcal{I}$. After truncation, $\hat{\mathbf{A}}$ is normalized into a stochastic matrix $\hat{\mathbf{S}}$ and then random walk is subsequently performed on $\hat{\mathbf{S}}$. We refer to the process of normalizing the truncated graph as subgraph normalization throughout the rest of the paper.

Proposed Method

We propose a remarkably fast diffusion achieving state-of-the-art retrieval performance. Iscen et al. reported that $\mathcal{L}_{\alpha}^{-1}$ is not sparse like $\mathcal{L}_{\alpha}$ making it less efficient to compute than using $\mathcal{L}_{\alpha}$ to solve $\mathcal{L}_{\alpha}\mathbf{f}_{d}^{*}\propto\mathbf{y}$ online (?). Our method makes it possible to pre-compute and maintain a sparsified $\mathcal{L}_{\alpha}^{-1}$ offline to achieve better efficiency. Given a new query, its diffusion result can be obtained by linear combination according to Eq. 7. As a result, we achieve a substantial improvement in the online search speed. Moreover, we argue that the subgraph normalization that takes place in (?) has negative effects on the retrieval performance. After the offline computation to obtain $\mathcal{L}_{\alpha}$ from the entire matrix $\mathbf{A}$, we apply slicing to $\mathcal{L}_{\alpha}$ to fetch the values on the corresponding rows and columns limited in the truncation subset.

In the following sections, we compare the time complexity between Iscen’s method and our method to analyze the efficiency gains of our method.

In prior works, the entire process of diffusion is performed during runtime when queries are processed. A combination of global and regional features are also used, but for simplicity, we choose to analyze Iscen’s online diffusion with only global features in this section.

Given the global feature $\mathbf{q}$ of a new query, the pipeline of online diffusion can be broken down to the following steps:

Truncation: the nearest neighbors $\textrm{NN}_{L}(\mathbf{q})\subset\chi$ of $\mathbf{q}$ is obtained by $k$-NN search for truncation

Graph construction: the truncated affinity matrix $\hat{\mathbf{A}}$ denoting subgraph is constructed for the subset $\textrm{NN}_{L}(\mathbf{q})$ with a reciprocity check, then subgraph normalization is applied to form the matrix $\hat{\mathbf{S}}$ and $\hat{\mathcal{L}}_{\alpha}$ are created afterward

Initialization: the vector $\mathbf{y}=\mathbf{S}_{dq}\mathbf{f}_{q}^{0}$ contains the similarities between the query and its nearest neighbors, which is subsequently truncated to fit the size of $\hat{\mathcal{L}}_{\alpha}$

Random walk: the convergence state is solved by Eq. 7 to obtain the result of diffusion by conjugate gradient

The above steps include $k$-NN search, which is responsible for most of the time needed to process those steps. Recent $k$-NN search strategies are sufficiently efficient (?; ?; ?), so we do not discuss the complexity which is beyond the scope of this work. Constructing the affinity matrix denoting the subgraph also requires $k$-NN search, and the subgraph normalization according to Eq. 2 costs $\mathcal{O}(Lk)$ time. Here, $Lk$ is the number of non-zero entries in the truncated affinity matrix, and $k$ is the parameter for the number of nearest neighbors in $k$-NN search. In the random walk step, the result is approximated by the early-terminated conjugate gradient (CG) (?; ?). Suppose we iterate CG for $\tau$ steps, its time complexity is $\mathcal{O}(Lk\tau)$.

From the above analysis, we can see that the cost to process each query is non-trivial and the most time-consuming steps are the subgraph construction and random walk. This motivates us to solve these inefficiencies.

From online to offline

We propose a new form of diffusion that moves the online steps, processing the heavy computation steps during runtime, to offline, pre-computing those steps beforehand.

The right side of Eq. 7 can be considered as a linear combination of column vectors in $\mathcal{L}_{\alpha}^{-1}$ with weights in vector $\mathbf{y}$. In other words, the results of any new query is merely the linear combination of the columns of $\mathcal{L}_{\alpha}^{-1}$ with corresponding weights in $\mathbf{y}$. Unfortunately, the inverse of a large sparse matrix is hard to compute even though $\mathcal{L}_{\alpha}$ is positive-definite. Despite this difficulty, it is still possible to compute the approximate inverse by either global iteration or a column-oriented algorithm, two approaches summarized in (?). Global iteration computes the inverse on the entirety of the matrix, whereas the column-oriented algorithm computes it one column at a time. Between the two, the column-oriented algorithm is more appealing for parallelism since it computes each column separately. It also allows us to apply truncation in computing each column to make a sparser structure. Therefore, we choose to adopt the column-oriented strategy in our proposed method.

with conjugate gradient (CG) (?), we obtain $\mathbf{c}_{i}$, the approximate $i$-th column vector in $\mathcal{L}_{\alpha}^{-1}$. Essentially, $\mathbf{c}_{i}$ can be viewed as the diffusion result of $i$-th database element $\mathbf{b}_{i}$. After the database-side diffusion, given a new query, the pipeline becomes

Initialization: prepare the initial state vector $\mathbf{y}$ for the query, where the indexes of non-zero entries are $\{i_{1},\dots,i_{h}\}$, and their values are $\{v_{1},\dots,v_{h}\}$

Linear combination: combine the corresponding columns $\{\mathbf{c}_{i_{1}},\dots,\mathbf{c}_{i_{h}}\}$ from $\mathcal{L}_{\alpha}^{-1}$ with the values in step 1 to obtain the diffusion result: $\mathbf{f}_{d}^{*}\propto\sum_{j}{v_{j}\mathbf{c}_{i_{j}}}$

Note that the inverse matrix $\mathcal{L}_{\alpha}^{-1}$ obtained from the above procedure is a dense matrix, which is less memory efficient. We propose the sparsified version (Fig. 3) of inverse matrix $\mathcal{L}_{\alpha}^{-1}$ to provide better memory efficiency in the next section.

Database-side truncation

As we discussed, truncation is crucial for scaling up to large datasets. The time complexity of diffusion is deeply related to $L$, the size of subgraph after truncation. Thus, the process of random walk can be accelerated if the database is truncated to a smaller size. Despite increases in speed, Iscen et al. observed that truncation has a negative effect on the retrieval performance (?).

Contrary to Iscen’s findings, we find that truncation by itself is not a detrimental practice. Rather, the order in which it is applied in relation to normalization is the important factor. We find that applying normalization after truncation is the reason for the decrease in retrieval performance. The subgraph after truncation contains incomplete manifolds and the later normalization raises the probabilities to transition to the nodes on such manifolds. This causes the random walk to be more likely to visit misleading nodes.

To tackle this issue, we normalize the complete matrix $\mathbf{A}$ to build $\mathcal{L}_{\alpha}$, and then apply late truncation (slicing) to $\mathcal{L}_{\alpha}$ directly, as shown in Fig. 2. Denoting the indexes of the nearest neighbors of a query as $\mathcal{I}=\textrm{NN}^{\textrm{ID}}_{L}(\mathbf{q})$, the truncation is applied by

where $l_{ij}$ is the element in $\mathcal{L}_{\alpha}$ while $\hat{l}_{ij}$ stands for the element in $\hat{\mathcal{L}}_{\alpha}$ after truncation. From our experiments, such a truncation can provide a significant performance boost.

In previous works, diffusion cannot be performed without the query because truncation process is applied under the guide of queries with a subsequent random walk. This forces diffusion in those works to be computed online. Our proposed method differs by instead using the elements in the database themselves as queries, thus moving the entire diffusion process offline. In addition, truncation is applied to the database elements as previous works applied it on queries.

To summarize, the late truncation directly applied on $\mathcal{L}_{\alpha}$ removes the negative effects of early truncation, and is completely pre-computed offline. In addition, the truncated initial state vector is fixed, meaning there is no extra overhead cost to build it.

Online search

Once the sparsified inverse matrix is obtained, the online search results can be calculated by using Algorithm 1. We denote $\textrm{NN}_{k}^{\textrm{SIM}}(\mathbf{q}_{i})$ as the similarities between the query feature $\mathbf{q}_{i}$ and its nearest neighbors in $\chi$. The online search thus becomes very fast because it only includes the $k$-NN search and linear combination. Moreover, since we only need $k$ columns in $\mathcal{L}_{\alpha}^{-1}$ for each query, our approach can merely cost $\mathcal{O}(Lk)$ RAM during runtime.

Experiments

This section presents the experimental setup and investigates the computational efficiency as well as retrieval performance of our methods for image retrieval. For the efficiency evaluation, we use a single core of Intel Xeon 2.80GHz CPU.

We use the Oxford Buildings (?) and Paris (?) datasets in our experiments. The datasets are referred to as Oxford5k and Paris6k respectively in correspondence with the size of each dataset. Another set of 100k random images from Flicker (?) are commonly used as distractors to enlarge the above datasets to Oxford105k and Paris106k. We measure the online computational time on the 55 queries of the datasets for Iscen’s method (?) and our proposed method. For evaluation, we adopt the standard mean average precision (mAP) as a performance measurement.

Features.

We use the 512 and 1,024 dimensional global R-MAC descriptors (?; ?) provided by Iscen et al. for fair comparison. We experiment on both global and regional features provided. For the Oxford and Paris datasets, there are 21 regional features per image on average.

K-NN search.

We conduct $k$-NN search by using the efficient FAISS toolkit https://github.com/facebookresearch/faiss, containing a CPU version and a faster GPU version (?), which allows us to deal with the larger Oxford105k and Paris106k datasets, especially for offline pre-computation.

Implementation details.

We use the same graph construction parameters as in the previous work (?). In particular, the parameter $\alpha$ to build $\mathcal{L}_{\alpha}$ is set to $0.99$. For global features, 50 nearest neighbors of each database element are used for graph construction, and the initial state vector contains the similarities between the query and its 10 nearest neighbors. While for regional features, the corresponding numbers of nearest neighbors are set to 200, 200 respectively. Through our experiments, deviating from these parameters consistently resulted in worse performance.

Runtime computational efficiency

We evaluate the computational efficiency on each query for $k$-NN search, Iscen’s method and our proposed method. Each method is run 10 times and the average computational time is used for comparison. The results on Oxford5k and Oxford105k datasets are shown in Fig. 4. Since most of the computation in our proposed method is already done offline on database side, we observe that our method can be remarkably fast during online search, close to the speed of $k$-NN search. Fig. 4 shows that the average search time per query of our method with global features are $\sim$2ms and $\sim$10ms on Oxford5k and Oxford105k datasets respectively, and its extra computation over $k$-NN search is negligible. In contrast, Iscen’s method is rather time-consuming since it has a lot of runtime processes. The search time per query for online diffusion without truncation is slower: $\sim$20ms on Oxford5k and $\sim$0.2s on Oxford105k. When truncation is applied during the offline diffusion process, the overhead to construct the graph during runtime causes it to be slow. We also observed a decrease in efficiency as the size of truncated graph grows as shown in Fig. 4.

Pre-computational efficiency

Now that we have shown the online search of our proposed approach is very efficient, we investigate the offline computational cost. The offline process mainly consists of two parts: the database vs. database $k$-NN search for truncation and random walk processes on each of the database element. Since exhaustive $k$-NN search on a large scale dataset is time-consuming, we utilize approximate nearest neighbor (ANN) search. Figure 5 shows the speed/accuracy trade-off when using ANN search for either truncation or graph construction. We adopt IVFADC (?) for ANN search using Faiss library (?), where the codebook size of coarse quantizer $\sqrt{n}\approx 316$, the number of subvectors $M=128$ is used and the number of clusters to scan is varied. When compared to the exhaustive $k$-NN search, ANN is generally good at approximating the top results of the search but its ranking and scores can be out of order and imprecise. This makes it applicable to truncation which only requires a coarse set of the top results. Graph construction, however, would be negatively affected by even small differences in the scores of the search results. We therefore use ANN search only for truncation and use exhaustive $k$-NN search for graph construction.

Since the $k$ in $k$-NN search for graph construction is small compared to truncation, it can be efficiently processed even without using approximate search, especially by using Faiss on a GPU. As a result, the entire process of truncation and graph construction takes $\sim$1ms using a single GPU per image. Diffusion processes take $\sim$6 minutes to process the whole Oxford105k dataset using global features and a truncation size of 5,000 (3.4 ms per image). We measured using a single core of CPU, but these processes can be easily parallelized. Compared to the offline processing in (?) which takes a few hours, our method is much faster.

Influence of subgraph normalization

In (?), truncation enables diffusion on large scale datasets but is described to be detrimental to retrieval performance. The authors claim that retrieval performance of diffusion grows as the percentage of the whole graph used grows, with a complete graph without any truncation having the best performance. However, we argue that the retrieval performance is mainly influenced by the early truncation leading to subgraph normalization. In order to avoid subgraph normalization, we first obtain the complete graph and apply late truncation (slicing) on the complete matrix $\mathcal{L}_{\alpha}$ in the process of diffusion. For comparison, we implement Iscen’s method with and without subgraph normalization. We vary the truncation size $L$ to observe the influence of subgraph normalization on the retrieval performance.

The experimental results with global features for the Oxford and Paris datasets are presented in Fig. 6. On the Oxford datasets, it is clear that the performance is significantly improved without subgraph normalization when the truncation size $L$ is small, but its effectiveness on the Paris datasets is smaller. We observe that merely performing $k$-NN search on the Paris datasets already results in a high retrieval performance. This could mean that the Paris datasets have standard-shaped manifolds conducive to comparison by Euclidean distance, so it limits the benefits gained from diffusion.

While previous works always encouraged using larger values of $L$ for performance gains, our method can achieve state-of-the-art performance with smaller $L$ values found through validation. As a bonus, a smaller truncation size $L$ will lead to acceleration of the offline computation.

Comparison to other methods

Table 1 compares our method with other competitive methods that use global and regional features. Testing on all datasets using global features, we observe up to a 5% increase in mAP performance compared to the previous state-of-the-art. Similarly, on diffusion with regional features, we achieve competitive or better performance. We note that Iscen et al. used global features to guide the truncation in their regional diffusion. For each query, they first apply $k$-NN search using the global features to obtain the closest images to that query. Subsequently, these results are used as a bounded set to perform regional diffusion. In contrast, we only use regional features in our regional diffusion for simplicity. To exploit global features, we apply a simple late fusion by computing a weighted mean of scores from regional and global diffusion, setting the weight for regional diffusion to 0.75. This further increases the performance (proposed diffusion w/ late fusion in Table 1), leading to better performance than Iscen et al. on all datasets.

Conclusion

In this paper, we propose a novel efficient diffusion to achieve fast retrieval during runtime with significant improvement in retrieval performance. We experimentally show that our approach has a similar efficiency to $k$-NN search, which is 10$\sim$ times faster than existing diffusion methods with global features. Moreover, our method achieves state-of-the-art performance on Oxford and Paris datasets. In conclusion, our method makes diffusion more practical for image retrieval on large-scale datasets, and has the potential to improve retrieval in other fields, such as text and video.

Acknowledgment

This study is supported by CREST (JPMJCR 1686).

References