Efficient Diffusion on Region Manifolds: Recovering Small Objects with Compact CNN Representations

Introduction

Object search is a key tool behind a number of applications like content based image collection browsing , visual localization , and 3D reconstruction . Many applications benefit from retrieving images taken from various viewing angles and under different illumination, e.g. more information for the user while browsing, localization in day and night, and complete 3D models. Each image is represented by one or more descriptors designed or learned to exhibit a certain degree of invariance to imaging conditions. Retrieval is formulated as a nearest neighbor search in the descriptor space, performed by approximate methods .

While collections of local descriptors provide good invariance, global descriptors like VLAD have smaller memory footprint, but are more prone to locking onto the clutter. This mainly holds when the queried object covers only a small part of the image. In case of global CNN descriptors, the invariance is partially designed by global max or sum pooling layers or multi-scale querying , and partially learned by the choice of the training data. Robustness to background clutter is improved by computing descriptors over object proposals or over a fixed grid of regions . Better performance is observed at a cost of increased memory footprint .

In image collections, objects are depicted in various conditions. As a consequence, query and relevant images are often connected by a sequence of images, where consecutive images are similar. The descriptors of these images form a manifold in the descriptor space. Even though the images of the sequence contain the same object, the descriptors may be completely unrelated after a certain point.

This idea has been first exploited by Chum et al. who introduce query expansion. The average query expansion (AQE) is now used as a standard tool in image retrieval, due to its efficiency and significant performance boost. However, AQE only explores the neighborhood of very similar images. Recursive and scale-band recursive methods further improve the results by explicitly crawling the image manifold. This is at a cost of increased query time.

Query expansion exploits the manifold of images at query time—starting from nearest neighbors of the query and using these neighbors to issue new queries. On the other hand, diffusion is based on a neighborhood graph of the dataset that is constructed off-line and efficiently uses this information at query time to search on the manifold in a principled way.

We introduce a regional diffusion mechanism, which handles one or more query vectors at the same cost. There is one vector per region and a few regions per image so that constructing and storing the graph is tractable. This approach significantly improves retrieval of small objects and cluttered scenes.

In diffusion mechanisms , query vectors are usually part of the dataset and available at the indexing stage. A novel approach to unseen queries with no computational overhead is proposed.

Though a closed form solution is known to exist, it has been explicitly avoided so far . We show that the commonly used alternative is in fact a well known iterative linear system solver. Since the relevant matrix is sparse and positive definite, the conjugate gradient method is more efficient resulting in practical query times well below one second.

To study the dependence of performance on relative object size, we experiment on INSTRE dataset , which has not received much attention so far. We propose a new evaluation protocol that is in line with other well known datasets and provide a rich set of baselines to facilitate future comparisons.

Searching in parallel in more than one manifolds via diffusion and using the nearest neighbors of unseen queries are illustrated in Figure 1.

The remaining text is structured as follows. Sections 2 and 3 discuss related work and background respectively, focusing on diffusion mechanisms. Sections 4 and 5 present our contributions in detail and the experimental body.

Related work

This section discusses existing query expansion or re-ranking methods. We also review the concept of diffusion in computer vision and image retrieval in particular. Apart from AQE , none of these methods has been applied to retrieval in the context of convolutional features.

Query expansion. A variety of methods employ local features and are well adapted to the Bag-of-Words model . Others are generic and applicable on any global image representation . In both cases, ranking is performed on the image level. Extension to regional level is not always straightforward. If even possible, such an extension would come at a significant cost, as each query region would need to be treated independently. This is unlike our regional diffusion mechanism, which has a fixed cost with respect to the number of query regions.

Diffusion. We are focusing on diffusion mechanisms, which propagate similarities through a pairwise affinity matrix . They are applied to many computer vision problems, such as semi-supervised classification , seeded image segmentation , saliency detection , clustering and image retrieval .

The power of such methods lies in capturing the intrinsic manifold structure of the data . The popular PageRank algorithm was originally used to estimate the importance of web pages by exploiting their links in a graph structure. Our retrieval scenario comes closer to its so called personalized or query dependent versions , where the final ranking both respects the data manifold and the similarity to a number of query vectors.

Diffusion is used for retrieval of general scenes or shapes of particular objects . It can also fuse multiple feature modalities by jointly modeling them on the same graph. In these approaches, images are the nodes of the graph with edges established given a pairwise similarity measure. We differentiate by defining a graph of image regions linked based on region similarities while performing a single pseudo random walk for multiple query regions. Diffusion with regional similarity has been investigated before, but only to define image level affinity , to aggregate local features , or to handle bursts .

Donoser and Bischof review a number of diffusion mechanisms for retrieval. They focus on iterative solutions arguing that closed form solutions, when existing, are impractical due to inversion of large matrices. We rather focus on a closed form solution computed approximatively with an iterative method that is particularly designed for this problem and show that this approach is faster.

Ranking with diffusion

Diffusion in the work of Donoser and Bischof denotes a mechanism spreading the query similarities over the manifolds composing the dataset. This is only weakly related to continuous time diffusion process or random walks on graph. We mainly follow Zhou et al. below.

Matrix $A$ is the adjacency matrix of a weighted undirected graph $G$ with vertices $\mathcal{X}$. The degree matrix of the graph is $D:=\operatorname{diag}(A\mathbf{1}_{n})$, i.e. a diagonal matrix with the row-wise sum of $A$. The Laplacian of the graph is defined as $L:=D-A$. It is usual to symmetrically normalize these matrices, for instance,

for the affinity matrix and $\mathcal{L}:=I_{n}-S$ for the Laplacian, where $I_{n}$ denotes the identity matrix of size $n$. Matrices $L,\mathcal{L}$ are positive-semidefinite .

We focus on a particular diffusion mechanism that, given an initial vector $\mathbf{f}^{0}$, iterates according to

Assuming $0<\alpha<1$, Zhou et al. show that sequence $\{\mathbf{f}^{t}\}$ defined by (3) converges to

where $\mathcal{L}_{\alpha}:=I_{n}-\alpha S$ is positive-definite. This follows since $\mathcal{L}_{\alpha}=\alpha\mathcal{L}+(1-\alpha)I_{n}\succ\alpha\mathcal{L}\succeq 0$. In this work, we focus on the closed form solution (4) rather than its intuitive derivation from iterative process (3).

Relation to other approaches. A diffusion mechanism also appears in seeded image segmentation , where query points correspond to labeled pixels (seeds) and database points to the remaining unlabeled pixels. This problem is equivalent to semi-supervised classification . In our context, the approach of Grady decomposes $\mathbf{f}=(\mathbf{f}_{d}^{\!\top},\mathbf{f}_{q}^{\!\top})^{\!\top}$ for the scores of the query (fixed $\mathbf{f}_{q}$) and database (unknown $\mathbf{f}_{d}$) points. Diffusion interpolates $\mathbf{f}_{d}$ from $\mathbf{f}_{q}$ by minimizing, w.r.t. $\mathbf{f}_{d}$, the quadratic cost $\sum_{i,j}a_{ij}(f_{i}-f_{j})^{2}=\mathbf{f}^{\!\top}L\mathbf{f}$ to enforce that neighboring points should have similar scores. By decomposing $L=[L_{d},\,-S_{qd};-S_{qd}^{\!\top},\,L_{q}]$, it is shown that the solution fulfills $L_{d}\mathbf{f}_{d}=\mathbf{y}$ with $\mathbf{y}=S_{qd}^{\!\top}\mathbf{f}_{q}$. In our setup, $L_{d}$ would be singular, preventing us to single out a solution $\mathbf{f}_{d}^{\star}$. Yet, it is easy to show that the minimizer of the cost $\alpha\mathbf{f}^{\!\top}L\mathbf{f}+(1-\alpha)\|\mathbf{f}\|^{2}$ has a similar expression to (4). The regularization term singles out a solution by forcing $\mathbf{f}$ to be zero in subgraphs not connected to any query point. The details are omitted for brevity.

be the similarity of $\mathbf{x}\in\mathcal{X}$ given $\mathbf{z}$, that is, restricted to the $k$ nearest neighbors $\text{NN}_{k}(\mathbf{z})$ of $\mathbf{z}$ in $\mathcal{X}$. Then,

equals $s(\mathbf{x},\mathbf{z})$ if $\mathbf{x},\mathbf{z}$ are the $k$-nearest neighbors of each other in $\mathcal{X}$, and zero otherwise. We use similarity function $s_{k}$ to construct affinity matrix $A$ like in (1).

Method

This section describes our contributions on image retrieval: handling new query points not in the dataset, searching for multiple regions with a single diffusion mechanism, and efficiently computing the solution.

In prior work on diffusion, a query point $\mathbf{q}$ is considered to be contained in the dataset $\mathcal{X}$ . This does not hold in a retrieval scenario, but a query can be included in the dataset graph at query time as follows. The $k$ nearest neighbors $\text{NN}_{k}(\mathbf{q})$ of $\mathbf{q}$ in $\mathcal{X}$ are found and reciprocity is checked. The rows and columns of the affinity matrix $A$ corresponding to $\text{NN}_{k}(\mathbf{q})$ are updated to maintain (6) in the presence of $\mathbf{q}$, and $A$ is augmented by appending an extra row and column for $\mathbf{q}$. Matrix $S$ is computed by normalizing $A$ (2). Finally, vector $\mathbf{y}$ indicates that $\mathbf{q}$ is a query. Generalizing to multiple query points is straightforward.

Even if we ignore the time needed for the above computation, we argue that locking, modifying and augmenting the entire affinity matrix for each query is not acceptable in terms of space requirementsImagine the case of multiple users querying at the same time; a different matrix per query is required. Also, updating mutual neighbors requires $k$-NN lists which are not available any longer.. We introduce here an alternative method which defines vector $\mathbf{y}$ in a new way rather than modifying $A$. Qualitatively, instead of searching for $\mathbf{q}$, we are searching for its neighbors $\text{NN}_{k}(\mathbf{q})$, appropriately weighted. In particular, we define $\mathbf{y}$ as

Our motivation for this choice is detailed in Section 4.2 including the more general case of multiple query points. Figure 1 shows a toy 2-dimensional example of diffusion, where the $k$-nearest neighbors to each query point taken into account in (7) are depicted. It is evident that multiple manifolds are captured when multiple queries are issued. Section 5 experimentally shows improved performance compared to the conventional approach.

2 Regional diffusion

The diffusion mechanism described so far is applicable to image retrieval when database and query images are globally represented by single vectors. We call this global diffusion in the rest of the paper. Unlike the traditional representation with local descriptors , global diffusion fits perfectly with the early CNN-based global features .

Global features still fail under severe occlusion or when the object of interest is small. Local CNN features from multiple image regions have been investigated for this purpose, either aggregated or represented as a set . Given a query image, the latter means that one searches for each query feature individually.

Each dataset point $\mathbf{x}_{i}$ is assigned a scalar that is the sum of similarities over all query points $\mathbf{q}$ for which $\mathbf{x}_{i}$ appears in the corresponding $k$-nearest neighbor set $\text{NN}_{k}(\mathbf{q})$, and zero if it appears in no such set.

Provided this system converges, the data part satisfies

if $\mathbf{f}^{\star}_{q}\propto\mathbf{1}_{m}$, $S_{q}=\mathbf{0}_{m\times m}$ and $B_{qd}=\mathbf{0}_{m\times n}$. In words, the query points are perfectly retrieved, they are dissimilar to each other, and the graph is indeed directed with query regions pointing to dataset regions, but the reverse is not allowed. Comparing (12) with (4), it follows that $B_{dq}\mathbf{1}_{m}$ is a good choice for $\mathbf{y}$. Since $B_{dq}$ stores the similarities between the dataset and the query points, this analysis justifies the single query (7) and the multiple queries (8) cases.

Diffusion. Given this definition of $\mathbf{y}$, diffusion is now performed on dataset $\mathcal{X}$, jointly for all query points in $Q$. Affinities of multiple query points are propagated in the graph in a single process at no additional cost compared to the case of a single query point. Here we are excluding the additional cost of computing $\mathbf{y}$ itself in (8) compared to (7). This search takes place in all related work. We also do not discuss how to make this search more efficient in space and time , which is beyond the scope of this work.

Figure 1 illustrates the diffusion on single and multiple query points. The contour lines show the ranking score any point on the plane would be assigned given the query point(s). It is evident that multiple manifolds are captured when multiple queries are issued.

Pooling. After diffusion, each image is associated with several elements of the ranking score vector $\mathbf{f}^{\star}$, one for each point $\mathbf{x}$ in $X\subset\mathcal{X}$. A simple way to combine these scores is to define the score of image $X$ as

where $i_{X}(j)$ is the index of the $j$-th point of $X$ in the dataset $\mathcal{X}$ and $\mathbf{w}=(w_{j})$ a weighting vector. The latter is defined as $\mathbf{w}=\mathbf{1}_{m}$ for sum pooling and, assuming $m<d$,

3 Efficient solution

Iteration (3) works well in practice but is slow at large scale. Taking the closed-form solution (4) literally, one may be tempted to compute the inverse $\mathcal{L}_{\alpha}^{-1}$ offline, but this matrix is not sparse like $\mathcal{L}_{\alpha}$. We propose a more efficient solution by making the connection to linear system solvers.

Diffusion is an iterative solver. Eq. (3) can be seen as an iteration of the Jacobi solver . Given a linear system $A\mathbf{x}=\mathbf{b}$We adopt the standard linear system notation in this section; matrix $A$ is not to be confused with our affinity matrix defined in (1)., Jacobi decomposes $A$ as $A=\Delta+R$ where $\Delta=\operatorname{diag}(A)$. It then iterates according to

In our case, $\mathbf{x}=\mathbf{f}$, $\mathbf{b}=(1-\alpha)\mathbf{y}$, and $A=\mathcal{L}_{\alpha}=I-\alpha S$. It follows that $\Delta=I_{n}$ and $R=-\alpha S$, so that

We have just re-derived (3). Note that a sufficient condition for Jacobi’s convergence is that matrix $A$ is strictly diagonally dominant, i.e. $|a_{ii}|>\sum_{j\neq i}a_{ij}$ for $i\in[n]$. It is easily checked that $\mathcal{L}_{\alpha}$ does satisfy this condition by construction, given that $0<\alpha<1$. This provides an alternative proof of the main result of Zhou et al. .

Conjugate gradient (CG) is the method of choice for solving linear systems like ours

where $\mathcal{L}_{\alpha}$ is positive-definite, and in particular for graph-related problems . It has been used for random walk problems , but not diffusion-based retrieval according to our knowledge. In fact, the linear system formulation has been explicitly avoided in this context .

Here we argue, as in , that it is the solution of (17) that we seek, rather than the path followed by iteration (3). However, we use CG to approximate this solution, since matrix $\mathcal{L}_{\alpha}$ is indeed positive-definite. At each iteration, CG minimizes the quadratic function $\phi(\mathbf{x})=\frac{1}{2}\mathbf{x}^{\!\top}A\mathbf{x}-\mathbf{x}^{\!\top}\mathbf{b}$ in a particular direction by analytically computing the optimal step length. More importantly, the direction chosen at each iteration is conjugate to previous ones. Thus, any update of $\mathbf{x}$ along this direction does not destroy the optimality reached in the entire subspace considered thus far.

Contrary to other iterative methods including (16), CG is guaranteed to terminate in $n$ steps. Remarkably, it provides good approximations in very few steps.

Normalization is preconditioning. Finally, a standard improvement is preconditioning, i.e. , solving a related system with $A$ replaced by $C^{-1}AC^{-\!\top}$, a matrix satisfying a weak condition like its eigenvalues being clustered. Unfortunately, finding an appropriate matrix $C$ can be quite complex . We observe that normalization (2) is preconditioning.Indeed, we could equally consider matrix $L_{\alpha}=D-\alpha A=\alpha L+(1-\alpha)I\succ 0$ and solve the linear system

instead, which is equivalent to (17). By normalizing $L_{\alpha}$ into $\mathcal{L}_{\alpha}$, we are actually performing preconditioning with $C=\operatorname{diag}(L_{\alpha})^{1/2}$. This is a simple form of symmetric preconditioning, known as diagonal scaling or Jacobi . It improves convergence, be it for CG or diffusion (3).

4 Scaling up

Despite the efficient solution described in the previous section, there are still issues concerning space and offline pre-processing at large scale. We address these issues here.

Compact representation. At large scale, the number of region features per database image should be kept as low as possible. For this reason, we learn a Gaussian Mixture Model (GMM) on the original features of each database image and represent the image by the unit normalized means. This is an even more natural choice when dealing with overlapping regions (see Section 5). As a result, it decreases the number of region features and their redundancy.

The off-line construction of the affinity matrix is quadratic in the number of vectors in the database and might not be tractable at large scale. We employ the efficient and approximate $k$-NN graph construction method by Dong et al. . Section 5 shows that it is orders of magnitude faster than exhaustive search and has almost no effect on performance.

Truncating the affinity matrix. Instead of ranking the full dataset, diffusion re-ranks an initial search. This baseline in our experiments is done with global descriptors and kNN search. Then we apply diffusion only on the top ranked images. We truncate the affinity matrix keeping only the rows and columns related to the regions of the top ranked images and re-normalize it according to (2). The cost of this step is not significant compared to the actual diffusion.

Experiments

This section presents the experimental setup and investigates the accuracy of our methods for image retrieval compared with the state-of-the-art approaches.

Datasets. We use three datasets. Two are well-known image retrieval benchmarks: Oxford Buildings and Paris . We refer to them as Oxford5k and Paris6k. We experiment at large-scale by adding 100k distractor images from Flickr , forming Oxford105k and Paris106k datasets. The third corpus is the recently introduced instance search dataset called INSTRE . It contains various everyday 3D or planar objects from buildings to logos with many variations such as different scales, rotations, and occlusions. Some objects cover a small part of the image, making it a challenging dataset. It consists of 28,543 images from 250 different object classes. In particular, 100 classes with images retrieved from on-line sources, 100 classes with images taken by the dataset creators, and 50 classes consisting of pairs from the second category. We differentiate from the original protocol , which uses all database images as queries. We randomly split the dataset into 1250 queries, 5 per class, and 27293 database images, while a bounding box defines the query regionhttp://people.rennes.inria.fr/Ahmet.Iscen/diffusion.html. The query and the database sets have no overlap. We use mean average precision (mAP) as a performance measure in all datasets.

Representation. We employ a CNN that is fine-tuned for image retrieval to extract global and regional representation. In particular, this fine-tuned VGG produces 512 dimensional descriptors. We extract regions at 3 different scales as in R-MAC , while we additionally include the full image as a region. In this fashion, each image has on average 21 regions. The regional descriptors are aggregated and re-normalized to unit norm in order to construct the global descriptors, which is exactly as in R-MAC. We apply supervised whitening to both global and regional descriptors. We use this network to perform all our initial experiments. In Section 5.4, we also report scores with higher dimensional descriptors derived from the fine-tuned ResNet101 using the same fixed grid.

Implementation details. We define the affinity function using a monomial kernel as $s(\mathbf{x},\mathbf{z})=\max(\mathbf{x}^{\!\top}\mathbf{z},0)^{3}$. The diffusion parameter $\alpha$ is always 0.99, as in the work of Zhou et al. . The $k$-NN search required by (8) is assumed to access all database vectors exhaustively. Our work does not investigate how approximate search methods could improve time and space consumed by this process. After computing (8), we only keep the largest $k$ values of $\mathbf{y}$ and set the rest to zero.

2 Impact of different components

Neighbors. We vary the number of nearest neighbors $k$ for constructing the affinity matrix and evaluate performance for both global and regional diffusion. The global baseline method is $k$-NN search with R-MAC, while the regional one is the method by Razavian et al. , where image regions are indexed and cross-matched. We refer to the latter as R-match in the rest of our experiments.

Results for Oxford5k are presented in Figure 2, and are consistent in other datasets. The performance stays stable over a wide range of $k$. The drop for low $k$ is due to very few neighbors being retrieved (where regional diffusion is more sensitive), whereas for high $k$, it is due to capturing more than the local manifold structure (where regional diffusion is superior). This behavior is consistent with the fact that small patterns appear more frequently than entire images.

We set $k=200$ for regional diffusion, and $k=50$ for global diffusion for the rest of our paper. Since only mutual neighbors are linked, the actual number of edges per element is less: The average number of edges per image (resp. region) is 25 (resp. 75) for global (resp. regional) diffusion, measured on INSTRE. We set $k=200$ for the query as well in the case of the regional diffusion, while for the global one $k=10$ is needed to achieve good performance.

Pooling. We evaluate the two pooling strategies after regional diffusion in Table 1. Generalized max pooling has a small but consistent benefit in all datasets. We use this strategy for the rest of our experiments. Weights (14) are computed off-line and only one scalar per region is stored.

Efficient diffusion with conjugate gradient. We compare the iterative diffusion (3) to our conjugate gradient solution. We iterate each method until convergence. Performance is presented in Figure 3 with timings measured on a machine with a 4-core Intel Xeon 2.00GHz CPU. CG converges in as few as 20 iterations, which are also faster, while (3) reaches the same performance as CG only after 110 iterations.

The average query time on Oxford5k including all stages for global baseline, regional baseline, global diffusion and regional diffusion without truncation is 0.001s, 0.321s, 0.02s, and 0.664s, respectively.

Handling new queries. We compare our new way of handling new queries to the conventional approach that assumes queries to be part of the dataset. Our method achieves 80.0 mAP on INSTRE compared to 77.7 achieved by the conventional approach. We therefore not only offer space improvements but also better performance,mainly in the case of regional diffusion. The main difference is that $k$ nonzero elements are kept both per query region (8) and for the entire vector $\mathbf{y}$. This, due to the overlapping nature of the CNN regions, may filter out incorrect neighbors.

3 Large scale diffusion

We now focus on the large scale solutions of Section 4.4.

Reduced number of regions. Figure 4 shows the impact of reducing the number of regions with Gaussian mixture models. Having as few as 5 descriptors per image already achieves competitive performance, while reducing the online search complexity. We decrease the number of neighbors $k$ to 50 when GMM reduction is used, as there are now less positive neighbors.

Affinity matrix with Dong’s algorithm . We compare the exhaustive construction of matrix $A$ to Dong’s efficient $k$-NN graph algorithm . Exhaustive search for Oxford105k composed of 2.2M regions takes 96 hours on a machine with a 12-core Intel Xeon 2.30GHz CPU. The approximate graph only takes 45 minutes and affects the final retrieval performance only slightly. It achieves 91.6 mAP on Oxford105k and 94.6 on Paris106k, while the exhaustive construction yields 92.5 and 95.2 respectively.

Truncation is a means to handle large scale datasets, i.e. more than 100k images. Regional diffusion on the full dataset takes 13.9$s$ for Oxford105k, which is not practical. We therefore rank images according to the aggregated regional descriptors, which is equivalent to the R-MAC representation , and then perform diffusion on a short-list. Figure 5 reports results with truncation. The performance of the full database diffusion is nearly attained by re-ranking less than 10% of the database. The entire truncation and diffusion process on Oxford105k takes 1s, with truncation and re-normalization taking only a small part of it. In the following, search on Oxford105k and Paris105k is performed by truncating the top 10k images. This choice results in an affinity matrix $A$ of around 200k regions. When GMM reduction is used, our short-list size is chosen so that $A$ has 2M regions too, keeping re-ranking complexity fixed.

Our approach is scalable thanks to truncation: the shortlist length is fixed and so is the re-ranking time, regardless of the database size and the dimensionality of the descriptors. Although this shortlist contains a small fraction of the database, its significantly outperforms the baseline.

Small objects. We present quantitative and qualitative results revealing that images benefit from our method mainly when the depicted object is small and the scene is cluttered. Figure 7 shows that the retrieved images with the highest increase of precision of regional compared to global diffusion contain small objects that the latter cannot see. Since the bounding boxes are available for all images of INSTRE, we quantitatively measure precision for all positive images: Figure 6 shows that the highest improvement indeed comes for objects with small relative size.

4 Comparison to other methods

We compare with the state-of-the-art approaches with global or regional representation, with or without query expansion. Table 2 summarizes the results. We implement three methods typically combined with BoW, namely Average Query Expansion (AQE) , Spatially Constrained Similarity Measure (SCSM) and Hello Neighbor (HN) . AQE is also effective with CNN global representation . A baseline for the regional scenario is R-match . We additionally extend AQE to regional representationAQE has not been proposed in a regional scenario. We extend it as competitive baseline derived from prior work. combined with the similarity used in R-match. Hamming Query ExpansionWe evaluated HQE on INSTRE for the purposes of this work. (HQE) is the only method not using CNNs, but local descriptors.

Regional diffusion significantly outperforms all other methods in all datasets. Global diffusion performs well on Paris because query objects almost fully cover the image in most of the database entries. This does not hold on INSTRE, which contains a lot of small objects. The improvements of regional diffusion are in this case much larger.

Conclusion

We propose a retrieval approach capturing distinct manifolds in the description space at no additional cost compared to a single query. We experimentally show that it significantly improves retrieval of small objects and cluttered scenes. The conclusion is that as few as 5-10 regional CNN descriptors can convey important information on small objects while thousands of conventional local descriptors are typically needed. Thus, a regional affinity matrix becomes possible. Regional diffusion was not possible before. In contrast to prior work, we use the closed form solution of the diffusion iteration, obtained by the conjugate gradient method. Combined with our contributions on space efficiency, this achieves large scale search at reasonable query times. Using recent CNN architectures, we achieve state-of-the-art and near optimal performance on two popular benchmarks and a recent more challenging dataset.

Acknowledgments The authors were supported by the MSMT LL1303 ERC-CZ grant. The Tesla K40 used for this research was donated by the NVIDIA Corporation.

References