Giorgos Tolias

Ronan Sicre

Hervé Jégou

PARTICULAR OBJECT RETRIEVAL WITH INTEGRAL MAX-POOLING OF CNN ACTIVATIONS

Recently, image representation built upon Convolutional Neural Network (CNN) has been shown to provide effective descriptors for image search, outperforming pre-CNN features as short-vector representations. Yet such models are not compatible with geometry-aware re-ranking methods and still outperformed, on some particular object retrieval benchmarks, by traditional image search systems relying on precise descriptor matching, geometric re-ranking, or query expansion. This work revisits both retrieval stages, namely initial search and re-ranking, by employing the same primitive information derived from the CNN. We build compact feature vectors that encode several image regions without the need to feed multiple inputs to the network. Furthermore, we extend integral images to handle max-pooling on convolutional layer activations, allowing us to efficiently localize matching objects. The resulting bounding box is finally used for image reranking. As a result, this paper significantly improves existing CNN-based recognition pipeline: We report for the first time results competing with traditional methods on the challenging Oxford5k and Paris6k datasets.

INTRODUCTION

C ONTENT based image retrieval has received a sustained attention over the last decade, leading to mature systems for tasks like visual instance retrieval. Current state-of-the-art approaches are derived from the Bag-of-Words model of [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] and mainly owe their success to locally invariant features [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and large visual codebooks [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. These methods are typically composed of an initial filtering stage where all database images are ranked in terms of similarity to a query image and a second re-ranking stage, which refines the search results of the top-ranked elements. The filtering stage is improved in several ways, such as incorporating weak geometric information [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], employing compact approximations of the local descriptors [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], or learning smart codebooks [START_REF] Mikulik | Learning vocabularies over a fine quantization[END_REF][START_REF] Avrithis | Approximate gaussian mixtures for large scale vocabularies[END_REF]. In such cases, local descriptors are individually matched and selective matching functions [START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF][START_REF] Tao | Locality in generic instance search from one example[END_REF] improve the search quality. Geometric matching models [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Avrithis | Hough pyramid matching: Speeded-up geometry re-ranking for large scale image retrieval[END_REF] are typically applied in a pairwise manner during the re-ranking stage of a short-list of images. Query expansion approaches significantly increase the performance [START_REF] Chum | Total recall II: Query expansion revisited[END_REF], at the cost of larger query times.

The recent advances achieved by Convolutional Neural Networks (CNN) and the use of intermediate layer activations as feature vectors [START_REF] Donahue | Decaf: A deep convolutional activation feature for generic visual recognition[END_REF] create opportunities for representations that are competitive for image or particular object retrieval, and not only classification tasks. Several works have already investigated this research direction, such as global or local representations based on either fully connected [START_REF] Babenko | Neural codes for image retrieval[END_REF][START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] or convolutional layers (Razavian et al., 2014b;[START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF]. The performance of CNN-based features has rapidly improved to the point of competing and even outperforming pre-CNN works that aggregate local features (Jégou et al., 2012;[START_REF] Radenović | Multiple measurements and joint dimensionality reduction for large scale image search with short vectors[END_REF]. In particular, activations of convolutional layers followed by a global max-pooling operation [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF] produce highly competitive compact image representations. One limitation is that such approaches are not compatible with the geometric-aware models involved in the final re-ranking stages. This work revisits both filtering and re-ranking stages with CNN-based features. We make the three following contributions.

• First, we propose a compact image representation derived from the convolutional layer activations that encodes multiple image regions without the need to re-feed multiple inputs to the network, in spirit of recent Fast-RCNN [START_REF] Girshick | Fast r-cnn[END_REF] and Faster-RCNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] methods but here targeting particular object retrieval. The underlying primitive representation is used in all stages (initial retrieval and re-ranking).

• Second, we employ the generalized mean [START_REF] Dollár | Integral channel features[END_REF] to enable the use of integral images along with max-pooling. This efficient method is exploited for particular object localization (see Figure 1) directly in the 2D maps of CNN activations. • Third, our localization approach is used for image re-ranking and leads us to define a simple yet effective query expansion method.

These approaches are complementary and, when combined, produce for the first time a system which compete on the Oxford and Paris building benchmarks with state-of-the-art re-ranking approaches based on local features. Our approach outperforms by a large margin previous methods based on CNN, while being more efficient in practice.

RELATED WORK

CNN based representation.

A typical CNN consists of several convolutional layers, followed by fully connected layers and ends with a softmax layer producing a distribution over the training classes. Instead of using this inherent classifier, one can consider the activations of the intermediate layers to train a classifier. In particular, the activations of the fully connected layers have been shown to be very effective and capable of adaptation to various domains [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF], such as scene recognition [START_REF] Donahue | Decaf: A deep convolutional activation feature for generic visual recognition[END_REF][START_REF] Sicre | Discriminative part model for visual recognition[END_REF], object detection [START_REF] Iandola | Densenet: Implementing efficient convnet descriptor pyramids[END_REF], and semantic segmentation [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]. In the case of image retrieval, fully connected layers are used as global descriptors followed by dimensionality reduction [START_REF] Babenko | Neural codes for image retrieval[END_REF]. They are also employed as region descriptors to be compared to database descriptors (Razavian et al., 2014a) or aggregated in a VLAD manner [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF].

Recent works derive visual representations from the activations of the convolutional layers. This is achieved either by stacking activations [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF] or by performing spatial maxpooling [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF] or sum-pooling [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] for each feature channel. According to [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF] such representation offers better generalization properties for test data that are far from the source (training) data. Noticeably, higher performance in particular object or scene retrieval is obtained by using convolutional layers rather than fully connected ones.

The very recent work of [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] shows that sum-pooling performs better than max-pooling when the image representation is whitened. In addition to be a costly choice, we will show that this is not optimal in our context of object localization (see Section 8). Finally, [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF] propose spatial and feature channel weighting that significantly improves performance. Their approach is complementary to what we propose for the filtering and the re-ranking stage.

Recent examples utilize information from fully connected layers to perform generic object detection [START_REF] Iandola | Densenet: Implementing efficient convnet descriptor pyramids[END_REF][START_REF] Papandreou | Untangling local and global deformations in deep convolutional networks for image classification and sliding window detection[END_REF]. Such approaches are prohibitive for the reranking purposes of large scale image retrieval. They have high computational cost and the inherent features are not optimal for particular object matching. Localization. In the recent years, the sliding window principle has been quite successful for many object localization methods. Due to the large number of possible windows, exhaustive search is extremely costly. However, integral images [START_REF] Viola | Robust real-time object detection[END_REF]) offer a constant cost solution to the evaluation of a single region. This attractive alternative is applicable for feature vectors constructed via a sum-pooling operation.

A globally optimal solution is given by Efficient Subwindow Search (ESS) of [START_REF] Lampert | Efficient subwindow search: A branch and bound framework for object localization[END_REF], who use branch-and-bound search to avoid exhaustive search. Their work employs integral images, which are also used in later improvements of ESS [START_REF] An | Efficient algorithms for subwindow search in object detection and localization[END_REF]). [START_REF] An | Efficient algorithms for subwindow search in object detection and localization[END_REF] formalize localization as a maximum sub-array problem and similarly to [START_REF] Chen | Efficient maximum appearance search for large-scale object detection[END_REF] they employ Bentley's algorithm [START_REF] Bentley | Programming Pearls, 2/E[END_REF]. Integral images facilitate the evaluation of many region candidates [START_REF] Uijlings | Selective search for object recognition[END_REF] based on VLAD or Fisher vectors (Van de [START_REF] Van De Sande | Fisher and VLAD with flair[END_REF]. All aforementioned approaches take advantage of integral images due to the inherent sum-pooling operation in the given representation. In this paper, we extend integral images to perform max-pooling over CNN activation maps, which is shown to be a better choice for describing regions (as opposed to the entire image).

Several object localization techniques have been proposed in the context of image retrieval as well. [START_REF] Lampert | Detecting objects in large image collections and videos by efficient subimage retrieval[END_REF] propose a two layer branch-and-bound method that alternates between regions and images. Integral images offer a significant speed-up in the work of [START_REF] Lin | A local bag-of-features model for large-scale object retrieval[END_REF] to perform localization through Bag-of-Words. The overall idea bears similarities with our work. However, we differentiate by employing CNN-based representation with max-pooling. Some approaches [START_REF] Tao | Locality in generic instance search from one example[END_REF][START_REF] Shen | Spatially-constrained similarity measure for large-scale object retrieval[END_REF] individually index local features for localization. In our case, the localization method is built on top of a compact representation, initially used for the filtering stage. Finally, [START_REF] Arandjelovic | All about VLAD[END_REF] propose a localization strategy based on VLAD, where similarity is computed for multiple image regions, giving a more precise localization via regression.

BACKGROUND

We consider a pre-trained CNN and discard all the fully connected layers. Given an input image I of size W I × H I , the activations (responses) of a convolutional layer form a 3D tensor of W × H × K dimensions, where K is the number of output feature channels, i.e. multi-dimensional filters.

The spatial resolution W × H depends on the network architecture, the layer examined, and the input image resolution. We assume that Rectified Linear Units (ReLU) are applied as a last step, guaranteeing that all elements are non-negative.

We represent this 3D tensor of responses as a set of 2D feature channel responses X = {X i }, i = 1 . . . K, where X i is the 2D tensor representing the responses of the i th feature channel over the set Ω of valid spatial locations, and X i (p) is the response at a particular position p. Therefore, the feature vector constructed by a spatial max-pooling over all locations [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF] is given by

f Ω = [f Ω,1 . . . f Ω,i . . . f Ω,K ] , with f Ω,i = max p∈Ω X i (p). (1)
Maximum activations of convolutions (MAC). Two images are compared with the cosine similarity of the K-dimensional vectors produced as described above. This representation, referred to as MAC, does not encode the location of the activations (unlike activations of fully connected layers), due to the max-pooling operated over a single region of size W × H. It encodes the maximum "local" response of each of the convolutional filters and is therefore translation invariant. In all the following, we consider the last convolutional layer of the examined networks.

Figure 2 visualizes the patches that contribute the most to the image similarity. They correspond either to the same object part or similar parts due to repeated structures. We extract MAC from input images of any resolution or aspect ratio by simply subtracting the mean pixel value [START_REF] Iandola | Densenet: Implementing efficient convnet descriptor pyramids[END_REF] from the input images. No crop or change of aspect ratio is required [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF].

The max pooling operation that is performed over a single cell offers translation invariance to the resulting representation. This is in contrast to representation derived from the fully connected layers that requires objects to be aligned. In our case, we assume that objects are up-right and we simply benefit from the rotation tolerance provided by the CNN due to the training data used. The same stands for the tolerance to scale changes.

ENCODING REGIONS INTO SHORT VECTORS

This section describes how we exploit the activations of the CNN convolutional layers to derive representations for image regions. Region vectors are aggregated to produce a short signature used in the filtering stage of image retrieval.

Region feature vector. The feature vector f Ω described in Section 3 is a representation for the whole image I. Now, we consider a rectangular region

R ⊆ Ω = [1, W ] × [1, H],
and define the regional feature vector

f R = [f R,1 . . . f R,i . . . f R,K ] (2)
where f R,i = max p∈R X i (p) is the maximum activation of the i th channel on the considered region.

The regions R are defined on the space Ω of all valid positions for the considered feature map (and not on the input image plane). A region of size 1 corresponds to a feature vector consisting of a single activation at a particular location. We are now able to construct a representation for multiple regions without re-feeding additional input to the CNN, similarly to recent RNN variants [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF][START_REF] Girshick | Fast r-cnn[END_REF], which drastically reduces the processing cost. Now assume a linear mapping of a given region R back to the original image. The proposed region vector captures a larger image region than the back-projected one, due to the large receptive field. A similar effect occurs in the context of object detection [START_REF] Iandola | Densenet: Implementing efficient convnet descriptor pyramids[END_REF], where fully connected layers are applied in a sliding window fashion.

R-MAC: regional maximum activation of convolutions. We now consider a set of R regions of different sizes. The structure of the regions is similar to the one proposed by Razavian et al. (2014b), but we define them on the CNN response maps and not on the original image. We sample square regions at L different scales. At the largest scale (l = 1), the region size is determined to be as large as possible, i.e., its height and width are both equal to min(W, H). The regions are sampled uniformly such that the overlap between consecutive regions is as close as possible to 40%. Remark that the aspect ratio of the original image has an influence on the number m of regions that we extract (1 region only if the input image is square). At every other scale l we uniformly sample l × (l + m -1) regions of width 2 min(W, H)/(l + 1), as illustrated in Figure 3 (left).

Then we calculate the feature vector associated with each region, and post-process it with 2normalization, PCA-whitening [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF] and 2 -normalization. We combine the collection of regional feature vectors into a single image vector by summing them and 2 -normalizing in the end. This choice keeps the dimensionality low which is equal to the number of feature channels. However, we show in our experiments that the resulting representation, referred to as R-MAC, offers a significant better performance than the corresponding MAC with same dimensionality. Note, the aggregation of the region vectors can be seen as a simple kernel that cross matches all possible regions, including across different scale.

OBJECT LOCALIZATION

In this section we propose an extension of integral images to perform approximate max-pooling over a set X of 2D feature channel response maps, which provide a rough yet efficient localization to our CNN-based method.

Approximate integral max-pooling. Noticing that the responses X i are non-negative, we exploit the generalized mean [START_REF] Dollár | Integral channel features[END_REF] to approximate each feature value f R,i associated with a given region R by the estimate

fR,i =   p∈R X i (p) α   1 α ≈ max p∈R X i (p) = f R,i , (3)
where the parameter α > 1 is such that fi → f i when α → +∞.

Figure 3 (middle) shows the average approximation error | fR,i -f R,i | estimated over several image regions. We report the approximation error as a function of the size of the corresponding response set on which the maximum value is computed. The various sizes of response sets are an outcome of using all possible regions. A high value of the exponent α leads to a better approximation, while applying on more elements makes the approximation less precise.

By approximating the maximum in this manner, we can now use integral images [START_REF] Viola | Robust real-time object detection[END_REF] to approximate the regional feature vector f R defined on any rectangular region R. For each channel, we construct the integral image of the 2D tensor whose value at position p is equal to

X i (p) α , p ∈ R.
Then, the sum of Equation ( 3) is simply given by the sum of 4 terms [START_REF] Viola | Robust real-time object detection[END_REF]. This allow us to efficiently compute max-pooling for many regions and therefore to construct the corresponding feature vectors. This is in contrast to the explicit construction of many regions with representation derived from fully connected layers, which is prohibitive due to the need to resize/crop and re-feed each region to the network.

We evaluate the approximation quality by measuring the cosine similarity between the exact vector and its approximate counterpart. The distribution of this similarity is presented in Figure 3 (right) and is measured on all possible regions of 10 randomly selected images. The proposed approximation is very precise even for moderate values of α. We set α equal to 10 in all of our experiments.

Window detection.

Let us now assume that there is another image Q depicting a single object, i.e. cropped via a bounding box defining the object of interest. We denote as q the corresponding MAC feature vector. The 2D region, defined on the CNN activations X of image I, that maximizes the similarity to q is computed as

R = arg max R⊆Ω f R q fR q . ( 4
)
The region R maximizing the similarity is mapped back to the original image I with a precision of ( W W I , H H I ) pixels, providing a rough localization of the object depicted in Q. The corresponding similarity does not take into account all the visual content of image I and is therefore free from the influence of background clutter. The brute-force detection of the optimal region by exhaustive search is expensive, as the number of possible regions is in O(W 2 H 2 ). In preliminary tests, we have evaluated a globally optimal solution based on branch and bound search, as in ESS [START_REF] Lampert | Efficient subwindow search: A branch and bound framework for object localization[END_REF]. The necessary bounds are trivially derived for our representation. The search is not significantly sped up in our case: The maxima are not distinct enough and a large number of regions are considered, while the overhead of maintaining the priority queue is high.

AML: approximate max-pooling localization. Instead, we restrict the number of regions that we evaluate and locally refine the best ones with simple heuristics. Candidate regions are uniformly sampled with a search step equal to t. In addition, regions having an aspect ratio larger than s times that of the query region are discarded. The parameters of the best region are refined in a coordinate descent manner, while allowing a maximum change of 3 units. The refinement process is repeated up to 5 times. Experiments show that the overlap of the detected region to the optimal one is high.

RETRIEVAL, LOCALIZATION AND RE-RANKING

Initial retrieval. The MAC or R-MAC feature vector is computed for all databases images. Similarly, at query time we process the query image and extract the corresponding feature vector. During the filtering stage we directly evaluate cosine similarity between the query and all the database vectors. Therefore, we obtain the initial ranking based on the similarity of MAC or R-MAC vectors.

Re-ranking. We consider a second re-ranking stage, as typically performed in spatial verification [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] with local features. A short-list of N top-ranked images is considered and AML, as described in Section 5, is applied on pairs of query and database images. Note that the query is now represented by the MAC vector, since this is used in AML, while the database image is represented by X . For each re-ranked image we obtain a score given by the region that maximizes the similarity to the query. This similarity is used to re-rank the elements of the short-list. Furthermore, a rough localization of the query object is available.

Remarks: At the filtering stage, whitened MAC (whitening as described in Section 8) or R-MAC can be used, while the localization procedure employs similarity with respect to 2 -normalized MAC. However, once the query object is localized, then, similarity between the query and the detected region is computed via whitened MAC or R-MAC, depending on the chosen filtering method. This similarity score is used to perform re-ranking. The required representation is constructed on query time only for the detected region and is acquired efficiently with integral images.

Query expansion (QE). Re-ranking brings positive images at the very top ranked positions. Then, we collect the 5 top-ranked images, merge them with the query vector, and compute their mean. Finally, the similarity to this mean vector is adopted to re-rank once more the top N images.

IMPLEMENTATION DETAILS

We observe that thresholding the response values of X which are larger than 128 (0.001% of all responses) and mapping each value to the closest smaller integer (floor operation) leads to insignificant losses. This allows the computation of α-th power with a lookup table and speeds-up the construction of integral images. Moreover, we approximate the α-th root of Equation ( 3) by performing binary search on the same lookup table of α-th power. This process allows the optimal window search to be more efficient.

The response maps represented by X are sparse [START_REF] Agrawal | Analyzing the performance of multilayer neural networks for object recognition[END_REF]. In particular, using the network of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] on Oxford buildings dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] results in 81% of response values being zero, which is convenient for storage purpose. We further decrease the memory requirements by uniformly quantizing the responses into 8 values. This results in more elements mapped to the same value. Therefore, we store the positions of non-zeros values with delta coding and use only 1 byte per non-zero element. Note that an image of resolution equal to 1024 × 768 corresponds to feature channel response maps of size 30 × 22 using the same network. Finally, an image requires around 32 kB of memory. At re-ranking time we construct one integral image at a time and use double precision (8 bytes) for its elements.

Table 1: Left: Comparison between the exhaustive sliding window and our alternative of window sampling and refinement. We report the average IoU w.r.t. the globally optimal window and the average percentage of windows evaluated w.r.t. to the exhaustive search (noted by %W). Measurements are conducted on all pairs of Oxford5k query images and their corresponding positive images. Right: Performance (mAP) of MAC and R-MAC on Oxford5k. Resol. corresponds to the input image resolution (maximum dimension).

EXPERIMENTS

This section presents the results of our compact representation for image retrieval, evaluate the localization accuracy AML, and finally employ it for retrieval re-ranking.

Experimental setup. We evaluate the proposed methods on Oxford Buildings dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris dataset [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], which are composed of 5063 and 6412 images, respectively. We refer to these datasets as Oxford5k and Paris6k. We additionally use 100k Flickr images [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] to compose Oxford105k and Paris106k, respectively. A distractor set of 1 million images from Flickr [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] is additionally used to go at larger scale. Retrieval performance is measured in terms of mean Average Precision (mAP). We follow the standard protocol and use the bounding boxes defined on the query images1 . These bounding boxes are also employed to evaluate localization accuracy. PCA is learned on Paris6k when testing on Oxford5k and vice versa. In order to be fair, we directly compare our results only to previous methods that do not perform learning on the test set.

The focus of our work is not to train a CNN, but to extract visual descriptors from its convolutional layers. We use networks widely used in the literature: AlexNet by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and the very deep network (VGG16) by [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. We choose VGG16 instead of VGG19 because we observe that the latter does not always attain better performance while it has higher feature extraction cost. Our representation is extracted from the last pooling layer, which has 256 feature channels for AlexNet and 512 for VGG16. MatConvNet [START_REF] Vedaldi | Matconvnet-convolutional neural networks for matlab[END_REF] is used to extract the features.

Localization accuracy. To evaluate the accuracy of AML, we employ pairs of Oxford5k query images and their corresponding positive images. We first perform exhaustive search to detect the globally optimal window. Then, we apply our speeded-up detector that evaluates fewer regions and in the end refines the best one. In both cases the approximate max-pooling is used for each window evaluation. We report Intersection over Union (IoU) with the optimal window and the percentage of windows evaluated compared to the exhaustive case. Results are shown in Table 1 (left). We provide a large speed-up while maintaining a high overlap with the optimal detection. Recall that our purpose is to apply this detector for fast re-ranking. Measuring IoU provides evidence for localization accuracy, however we observed that it does not directly impact retrieval performance. We finally set s = 1.1 and t = 3 for re-ranking usage.

In order to evaluate the localization accuracy with respect to ground-truth annotation we crossmatch all 5 query images that exist per building. One of them is used as a query (cropped bounding box), while for the other we compare the detected region to the ground-truth annotation. Exhaustive evaluation achieves an IoU equal to 52.6% (52.9%) and the speeded-up approach achieves 51.3% (51.4%) on Oxford5k (Paris6k) datasets. The accuracy loss is limited, while the localization is approximately 180 times faster. AML provides a rough localization at low computational cost. Such Unlike previous description schemes derived from CNN layers, our approach compete with the best approaches based on local features for geometric matching and query expansion. Our AML can even outperform them: while our results are lower on Oxford, we achieve the best performance on Paris and, to the best of our knowledge, outperform all published results on this benchmark. Higher scores on Paris6k are reported by Arandjelovic & Zisserman (2012) (91.0) and by Zhong et al. (2015) (91.5). These are achieved by learning the codebook on Paris6k itself and by performing pre-processing of the indexed dataset.

Discussion about other CNN-based approaches. Razavian et al. (2014b) propose to perform region cross-matching and accumulate the maximum similarity per query region. We evaluate this cross-matching process on the collection of regional vectors used in R-MAC; we simply skip the final aggregation process and keep the regional vectors individually. The cross-matching achieves 75.2% mAP on Oxford5k as a filtering stage, while re-ranking with AML on top of this acts in a complementary way and increases the performance up to 78.1%. However, cross-matching has two drawbacks. Firstly, the region vectors have to be stored individually and increase the memory requirements by a factor of |R|, where |R| is the number of extracted regions. Secondly, the complexity cost is linear in the number of indexed images and quite high since it requires to compute |R| 2 (e.g. 1024 (Razavian et al., 2014b)) inner products per image. The work of Razavian et al. (2014b) follows a non-standard evaluation protocol by enlarging the provided query bounding boxes. In addition, the cost of their feature extraction is extremely high since they feed 32 images of resolution 576 × 576 to the CNN. The recent work of [START_REF] Xie | Image classification and retrieval are one[END_REF] is quite similar to theirs and is applied on both retrieval and classification. [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] show that global sum-pooling on convolutional layer activations is better than max-pooling when the final image vectors are PCA-whitened. When whitening is not employed, then the latter is better. In the context of object localization we efficiently evaluate a large number of candidate regions on query time with AML. Performing whitening on each candidate region vector significantly increases the cost and is prohibitive for this task. We switch max-pooling to sum-pooling for both our proposed R-MAC and AML and test performance. Note that sum-pooling is a special case of our integral max-pooling with α = 1. Switching to sum-pooling makes R-MAC perform 69.8 and R-MAC +AML +QE perform 76.9 on Paris106k. These scores are directly comparable to our scores in Table 2 and reveal that our choice is consistently better in all cases within our pipeline.

CONCLUSIONS

In this work, we re-visit both filtering and re-ranking retrieval stages by employing CNN activations of convolutional layers. Our compact vector representation encodes several image regions with simple aggregation method and is shown to outperform state-of-the-art competitors. Our localization increases the performance of the retrieval system that is initially based on a compact representation. The same CNN information adopted during the filtering stage is employed for re-ranking as well. Our approach competes with state-of-the-art methods that employ costly geometric matching or query expansion and we achieve the highest performance on Paris dataset, and provided a much better performance than existing approaches built upon CNN features. A very recent work [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] shows how MAC performance is improved by end-to-end fine tunning where the objective is based on MAC similarity.

Figure 1 :

 1 Figure 1: Query objects (left) and the corresponding localization in another image (right) are shown. We visualize the patches that contribute the highest to the image similarity score. Displayed patches correspond to the receptive field of CNN activations. Object localization is displayed in magenta, while different colors are used for patches in correspondence.

Figure 2 :

 2 Figure 2: We visualize the receptive fields related to the 5 MAC components that contribute the most to the image similarity. Each displayed receptive field corresponds to the maximum response of a feature channel. A different color is used for each feature channel, while different feature channels are shown for each image pair.

Figure 3 :

 3 Figure 3: Left: Sample regions extracted at 3 different scales (l = 1 . . . 3). We show the top-left region of each scale (gray colored region) and its neighboring regions towards each direction (dashed borders). We depict the centers of all regions with a cross. Middle: Approximation error of the maximum value versus the size of the response set for different values of exponent α. Measurements are performed on 10 randomly selected images by evaluating all possible regions. The responses for this set of images take values in [0, 151]. Right: Empirical distribution of the cosine similarity value between the exact vector f R and its approximation fR . Measurements are collected by constructing the exact and approximate vectors of all possible regions on 10 randomly sampled images.

Figure 4 :

 4 Figure 4: Performance of retrieval with re-ranking by AML versus number of re-ranked images on Oxford105k and Oxford5k combined with 1M distractor images.

Figure 5 :

 5 Figure 5: Examples of top retrieved images before (top) and after (bottom) re-ranking with AML. On the left we show the query image and depict the bounding box in blue color. When re-ranking is used, we present the top ranked images and report for each image its initial and final ranking. The localization window is shown in magenta, while positive/negative/junk images are depicted with green/red/yellow border.

Table 2 :

 2 Performance comparison with state of the art. We report results for compact vector representations (left) and for retrieval approaches employing geometry, re-ranking, query expansion, or vector approximations (right). D = dimensionality. Our approaches are identified with bullets •.

	Method	D	Oxf5k Par6k Oxf105k Par106k Method	Oxf5k Par6k Oxf105k Par106k
	Jégou & Zisserman (2014)	1024 56.0	-	50.2	-	Chum et al. (2011)	82.7 80.5 76.7	71.0

The query regions are cropped and then used as input to the CNN.

[START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF] 128 43.3 -

Small differences of scores compared to the first version of the manuscript on arxiv are due to a slightly different evaluation protocol used before. Now, the evaluation protocol is the standard one for these datasets.

Research partially conducted while G. Tolias and H. Jégou were at Inria. We would like to thank Florent Perronnin for his valuable feedback. This work was partly supported by MSMT LL1303 ERC-CZ grant.

a setup results in an average re-ranking query time of 2.9 sec using AlexNet, when re-ranking 1000 images with a single threaded implementation.

Retrieval and re-ranking. We evaluate retrieval performance using MAC and R-MAC compact representations. The MAC vectors are 2 -normalized, PCA-whitened and 2 -normalized once more, while the corresponding processing of the R-MAC is as described in Section 4. Table 1 (right) presents the results on Oxford5k. We evaluate different input image resolutions and observe that the original image size (1024) provides higher performance. Note that MAC is similar to the one proposed by [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF], however their process remains constrained by standard input size and aspect ratio. The proposed R-MAC gives a large performance improvement at no extra cost, as both feature vectors have exactly the same dimensionality. Regions of different scales are aggregated together, meaning that L = 3 combines regions at scales l = 1, l = 2, and l = 3. We set L = 3 in the following. In order to decompose the components of R-MAC, we construct R-MAC by aggregating only regions of l = 3. It achieves mAP equal to 63.0 on Oxford5k with VGG16.

Aggregating both regions of l = 2 and l = 3 improves to 65.4. Finally, adding l = 1 (original R-MAC) performs 66.9 (see Table 1 right). Filtering time is 12 ms on average for Oxford105k.

Next, we employ AML for image re-ranking and conduct performance evaluation on Oxford105k by re-ranking up to 1000 images. The performance is consistently improved as shown in Figure 4. R-MAC brings a larger benefit and VGG16 performs better than AlexNet. Query expansion, as described in Section 6, improves the performance at low extra cost, since similarity is re-computed only for the re-ranked short-list. Finally, we carry out experiment at larger scale with 1M distractor images and present results in Figure 4. AML improves the performance by 13% mAP.

Examples of ranking using MAC and re-ranking using AML are presented in Figure 5. Recall that we only provide a rough object localization, since our main goal is to obtain improved image similarity. Furthermore, the provided localization is accurate enough for re-ranking.

Comparison to the state of the art. We compare the proposed methods to state-of-the-art performance of compact representations and approaches based on local features that perform precise


Ronan Sicre
email: ronan.sicre@inria.fr

Hervé Jégou
email: herve.jegou@inria.fr

Memory Vectors for Particular Object Retrieval with Multiple Queries

Keywords: H.3.3 [INFORMATION STORAGE AND RETRIEVAL]: Information Search and Retrieval image retrieval, multiple queries, memory vectors

We address the problem of retrieving all the images containing a specific object in a large image collection, where the input query is given as a set of representative images of the object. This problem is referred to as multiple queries in the literature. For images described with bag-of-visualwords (BOW), one of the best performing approach amounts to simply averaging the query descriptors.

This paper 1 introduces an improved fusion of the object description based on the recent concept of generalized maxpooling and memory vectors, which summarizes a set of vectors by a single representative vector. They have the property of reducing the influence of frequent features. Therefore, we propose to build a memory vector for each set of queries and the membership test is performed with each image descriptor from the database, to determine its similarity with the query representative. This new strategy for multiple queries brings a significant improvement for most of the image descriptors we have considered, in particular with Convolutional Neural Networks (CNN) features.

INTRODUCTION

T he last decade has witnessed the rapid increase of mul- timedia data, which has raised numerous challenges regarding the management of large collections. Multimedia search in large collection, such as Content Based Image Retrieval (CBIR) has received a lot of attention. In this work, we are interested in multiple queries image retrieval, where the CBIR system has a set of representative images of an object as input. Arandjelovic et al. [START_REF] Arandjelovic | Multiple queries for large scale specific object retrieval[END_REF] show that simply averaging the scores offers a competitive performance, at least as good as taking the best scores across all queries. Another advantage is that, if the image is a vector representation (e.g., bag-of-words or the Fisher vector), one can equivalently (thanks to linearity of average) average the vector representations of the multiple queries. In this case, only the average vector has to be compared against the databases vectors describing the image collection.

In this paper, we are interested in improving this fusion strategy. Our motivation is that, when multiple queries are given as input, some of the images of the query object are very similar, see Figure 1. The redundant information dominates the representation, while rare discriminative features are comparatively overlooked.

Our solution is inspired by recent papers on image representations, namely generalized max-pooling [START_REF] Murray | Generalized max pooling[END_REF] (GMP) and democratic aggregation [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF], which improve the aggregation stage of coded local descriptors (such as Fisher) by reducing the influence of frequent, often uninformative, descriptors. Conversely, it gives more importance to rare and potentially highly discriminative patterns. Interestingly, GMP [START_REF] Murray | Generalized max pooling[END_REF] was recently shown to be an effective way to construct a memory vector [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF] summarizing, in a continuous manner, a vector set by a single vector. This method was introduced to perform approximate nearest neighbor queries in high-dimensional spaces. The memory vector is a compressed representation of the set used to perform a membership test.

In this paper, we model the multiple-queries set with a representative memory vector summarizing all the images. Then, for each database vector we estimate a membership score and use it to rank the images, which amounts to performing a weighted summation of the input vectors. By exploiting this dual interpretation first proposed for generalized max-pooling [START_REF] Murray | Generalized max pooling[END_REF], we extend our method to other matching methods like the selective match kernel [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF].

The paper is organized as follows. After a review of related works in Section 2, Section 3 presents our strategy and explains how we use it in the context of multiple-queries. Section 4 presents our experiments. Our results demonstrate the interest of our work for several image representations. Importantly, our method is especially effective with features extracted from a convolution network, outperforming the state-of-the-art of multiple-queries with short vectors.

RELATED WORK

Image descriptors. Our method uses on input off-theshelf vector image representations, such as Bag-of-visualwords (BOW) [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], VLAD [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] or improved Fisher vectors [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF].

We are especially interested in using state-of-the-art short representations, for instance based on democratic aggregation [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF]. We also consider descriptors based on Convolutional Neural Networks (CNN), which were recently shown [START_REF] Babenko | Neural codes for image retrieval[END_REF] to be very successful on large scale image retrieval tasks, even when reducing the image description to a few hundreds dimensions. These vector representations can be further reduced with binarization [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF] or product quantization [START_REF] Jegou | Product quantization for nearest neighbor search[END_REF].

Strategies for Multiple-queries. The last few years have witnessed massive progress on the task of finding images depicted a given object in a large database, yet this task still remains challenging when only one image is provided to the system without any annotation. However, in many applications like brand or logo detection, or on output of a text-based search system, several representative images of the objects may be available. This scenario is similar to the instance search task of Trecvid [START_REF] Smeaton | Evaluation campaigns and TRECVid[END_REF] evaluation campaigns.

Multiple image gives a better description of an object to handle problems such as view-point changes, viewing conditions, occlusions, background clutter, shape variation, etc. Arandjelovic & al. [START_REF] Arandjelovic | Multiple queries for large scale specific object retrieval[END_REF] presents this problem as well as several possible strategies to exploit these images: average query, SVM on all queries, maximum of multiple queries, average of multiple queries, and exemplar SVM on each query. Their study concludes while averaging the scores, or equivalently averaging the vector representations of the query set, is competitive while reducing the complexity because only one query is submitted. Other works in this setting have been proposed. Chen & al. [START_REF] Chen | Boosting object retrieval with group queries[END_REF] enrich queries with multiple views in a boosted framework. Fernando & al. [7] use pattern mining to build object specific mid-level image representation. These two strategies aim at explicitly model the query object and are relatively costly. Wu & al. [START_REF] Wu | Interest point selection by topology coherence for multi-query image retrieval[END_REF] reduces background influence by selecting region of interest appearing in multiple queries. [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF] build a vector m(X ) summarizing a set X = {x1, ..., xn} of ddimensional vectors. This vector optimizes the membership test: given a query vector y, it computes the dot product y ⊤ m(X ) to evaluate whether y ∈ X , or close enough to at least one vector in X . The vector are assumed ℓ2-normalized and uniformly distributed on the unit-hypersphere. In practice, these assumptions do not have necessarily to hold for the method to work well. The test is formalized as the following detection problem:

GMP and memory vectors. Memory vectors

• Hypothesis H1: y is not related to X .

• Hypothesis H2: y is related to X . For example, y is related to x j and we write y = αx j + βz, where z is a random vector orthogonal to x j and ||z|| = 1. Thus, we have

α 2 + β 2 = 1, because ||y|| = 1.
We refer to the dot product m ⊤ y as the membership score. The quality of this score obviously depends on how the vector m is constructed, for instance simply with the sum vector:

m(X ) = ∑ x∈X x. (1)
In that case [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF], for a large dimensionality d, the membership score the following distributions:

H1: ⟨m|y⟩ ∼ N (0, n/d) (2) H2: ⟨m|y⟩ ∼ N (α, (n -1)/d) (3)
However, it is possible to obtain a better hypothesis test. This is achieved by imposing that for any of the vector x i in X , x i ⊤ m(X ) = 1, or simply X ⊤ m = 1n in matrix form, where 1n is a n-dimensional vector with all values set to 1. This constraint ensures that the interference with remaining vectors of X are eliminated when the exact same vector is submitted to the system. There are many (a subspace) solutions m(X ) satisfying these constraints.

However, the false positive probability directly depends on the norm of the memory vector and therefore a good way to single a solution is to minimize its norm. In other terms, we want to minimize ||m|| 2 under the constraint X ⊤ m = 1n. The solution is given by the Moore-Penrose pseudo-inverse:

m = (X + ) ⊤ 1n (4)
Since n < d, m = X(X ⊤ X) -1 1n. We note that if no solution exists, m * minimizes ||X ⊤ m -1n||. For large d, this construction leads to the following distributions:

H1: m ⊤ Y ∼ N (0, ||m|| 2 /d) (5) H2: m ⊤ Y ∼ N (α, β 2 ||m|| 2 /d) (6)
Compared to Equation 1, the improvement comes from the decrease of the variance of the scores under H2 at the cost of increasing the variance under H1. This increase under H1 is small for small n/d, meaning that using this optimized construction is comparatively better for short vectors. For a very large dimensionality, the construction of Equation 4is asymptotically equivalent to the sum construction.

MULTIPLE QUERIES: OUR PROPOSAL

Memory vectors for multiple queries

Our main idea is to inverse the formulation proposed of memory vectors by summarizing the multiple representations of the object by a single vector. The memory vectors were proposed for test membership and approximate search [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF], with one query being tested against a set of vectors based on a membership test. In contrast, we aggregate the queries instead of aggregating the database vectors. The query memory vector is compared to all the database vectors and the membership score is used to order them. Note, if the vector is constructed as the average of the input vectors as in Equation 1, this strategy is equivalent to the wellperforming method of averaging the vectors [START_REF] Arandjelovic | Multiple queries for large scale specific object retrieval[END_REF]. In contrast, we optimize it by using the construction of Equation 4.

Assumptions. All the image descriptors are ℓ2-normalized, therefore satisfying the assumption mentioned in Section 2. Additionally, the number n of vectors in the query set is significantly smaller than d. Indeed, there is typically no more than 10 images per query. More precisely, n = 5 images per query for Oxford5k and Paris6k used as a multiple-query, see Section 4.1. As a result, n/d is small and the membership test is likely to be effective, which fits well our objective of using short representations ranging from d=128 to 512.

Discussion. With the pseudo-inverse construction, the common parts of the combined descriptors are down-weighted and the norm of the memory vector ||m|| 2 is minimized. This method has a similar effect as the democratization [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF] or the GMP [START_REF] Murray | Generalized max pooling[END_REF] and equalizes the influence of frequent and rare features. The main difference is that this effect is obtained across images, while previous strategies were proposed to address this problem within a given query image.

Retrieval pipeline

Image representations are computed with VLAD and CNN and other recent single-vector image representations. Since we are mostly interested to improve the initial ranking, we do not use any spatial verification or query expansion techniques, unlike some mentioned previous work [START_REF] Fernando | Mining multiple queries for image retrieval: On-the-fly learning of an object-specific mid-level representation[END_REF].

Multi-VLAD -Vlad3c. Features are first extracted using the Hessian-Affine detector and described by RootSIFT [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], and finally rotated with PCA. VLAD are computed using 16, 64, and 256 clusters and compact representations are built by concatenating these three descriptors, power normalization, centering, and PCA to obtain 128, 256, and 512 dimensional "Vlad-3c" descriptors respectively [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of pca and whitening[END_REF][START_REF] Safadi | Descriptor optimization for multimedia indexing and retrieval[END_REF].

triD. We use off-the-shelf the descriptors of the recent triangulation embedding and democratization [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF].

CNN features.

We extract CNN descriptors pre-trained on the Imagenet dataset with the Fast CNN architecture [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF]. We follow the recommendation of Babenko et al. [START_REF] Babenko | Neural codes for image retrieval[END_REF] and use the output of the 6th layer before applying the ReLU. The descriptors are post-processed as Vlad3c and tridD: power normalized, centered, and PCA is applied.

Dual representation

To evaluate how much an image contributes to the produced memory vector, we employ the dual interpretation proposed by Murray et al. [START_REF] Murray | Generalized max pooling[END_REF], which shows that the memory vector of the set X can be written as a weighted sum:

m(X ) = ∑ x i ∈X wix i , ( 7
)
where wi is the weight for a given vector of the query set. Denoting w = [w1, . . . , wn] ⊤ , the weight vector obtained is

w = (X ⊤ X) -1 1n. ( 8
)
This formulation computes weights that can be interpreted as quantitative measures of the rarity of the different query images (smaller is more frequent). We can therefore visualize the contribution of each image descriptors to the query object fused descriptor. Figure 1 gives the weights used to build the memory vectors. Five query images of the same object are shown, as well as the Gram matrix (X ⊤ X) and the resulting weights for two different descriptors: CNN and tridD reduced to 512 dimensions. It is interesting to note that the first, third and fifth images are visually similar and have high similarity scores in the Gram matrix. The second and fourth images are relatively different from the other queries and have larger contributions (highest weights) in the fused descriptor.

EXPERIMENTS

Datasets

Oxford5k Buildings [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] is a dataset that consists of 5,062 high-resolution images. There are 55 query images, 5 for each of the 11 chosen Oxford buildings. For each query image, a bounding box on the region of interest is available. The dataset Oxford5k can be further combined with an extra 100k images from Flickr forming Oxford105k dataset.

Paris6k [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] contains 6,412 high-resolution images. The dataset has also 55 query images, with bounding boxes, from 11 landmarks in Paris. This dataset is further combined with the extra 100k images in Paris106k.

To perform multiple queries retrieval, the 5 query image descriptors of a specific landmark are combined into a single representation. These representations are used as query for each specific landmark. Performances are measured in terms of mean average precision (mAP).

Results

Precision-recall. Figure 2 shows precision recall curves for two query objects from Oxford5k. Each query image is evaluated, as well as the fused vector either with sum (equivalent to the averaging [START_REF] Arandjelovic | Multiple queries for large scale specific object retrieval[END_REF]) and the optimized memory vector of Equation 4. Observe the benefit of combining multiple queries with our construction compared to sum.

Full descriptors. Table 1 compares the mAP scores for the full representations on Oxford datasets, before any dimensionality reduction. We observe an increase of performance with our strategy for all representations (Vlad, tridD, CNN). It is comparatively smaller for tridD. This can be explained by the fact that democratization method used in this method already reduces the contribution of frequent features within the image. The CNN features receive the largest improvement, which is appealing because they are the best performing descriptors.

Short vectors. Table 2 presents the results for the reduced representations with PCA to 128, 256, and 512 dimensions. We observe a larger improvement in this setup than for the full representations, especially with CNN descriptors. This is expected because high-dimensional descriptors have more chances to be orthogonal to one to another, in which case sum and optimized memory vectors are identical. Figure 3 displays the MAP scores against the dimensionality of the CNN descriptors. For the most compact 64dimensional descriptor, the ratio n/d is not small enough to maintain a low false positive probability and therefore the strategy is not effective. Table 3 shows some supplementary results on Paris datasets, which concur with the ones observed on Oxford buildings.

Finally, we note that centering then applying PCA on CNN descriptors offers a large performance increase in terms of MAP on our various retrieval datasets. For example, reducing the dimensionality to 512 gives an increase of 7% to 9% MAP. Furthermore, we experimentally observed that applying PCA offers better results than PCA with whitening.

CONCLUSION

We have shown that it is possible to improve the fusion of multiple query descriptors. Our method is based on the recent concept of memory vectors, which summarizes a set of vectors by a single representative vector. The proposed retrieval system offers a consistent increase in performance compared to the average query on several description methods and datasets.

Figure 2 :

 2 Figure 2: Precision recall curves for two different objects from Oxford5k with five query images, the sum, and the memory vector.

Figure 3 :

 3 Figure 3: Comparison between sum and memory vectors for the CNN descriptors reduced to [64,128,256,512] dimensions on several datasets.

Visualization of five query images from Oxford5k, and the weights and the Gram matrix for two different types of descriptors.

	wi		Gram matrix
				CNN 512
	0.31	1.00	0.06	0.58	0.02	0.40
	0.89	0.06	1.00	0.07	0.08	-0.03
	0.55	0.58	0.07	1.00	-0.01	0.29
	0.93	0.02	0.08	-0.01	1.00	-0.01
	0.75	0.40	-0.03	0.29	-0.01	1.00
				triD 512
	0.68	1.00	0.01	0.43	-0.04	0.28
	0.69	0.01	1.00	0.19	0.21	0.06
	0.42	0.43	0.19	1.00	-0.04	0.31
	0.88	-0.04	0.21	-0.04	1.00	0.03
	0.61	0.28	0.06	0.31	0.03	1.00
	Figure 1:

Table 1 : Averaging vs our method for standard VLAD with 256 clusters, tridD, and CNN on Ox- ford5k and Oxford105k.

 1

		Oxford5k	Oxford105k
	Representations Avg [1]	Ours	Avg [1]	Ours
	Vlad 256c	0.721	0.727	0.685	0.691
	tridD full	0.792	0.792	0.768	0.769
	CNN full	0.603	0.619	0.581	0.589

Table 2 : Averaging vs our method for various re- duced representations on Oxford5k and Oxford105k.

 2

		Oxford5k	Oxford105k
	Representations Avg [1]	Ours	Avg [1]	Ours
	Vlad-3c 128	0.557	0.562	0.485	0.496
	Vlad-3c 256	0.620	0.628	0.545	0.556
	Vlad-3c 512	0.695	0.695	0.630	0.627
	tridD 128	0.653	0.660	0.627	0.630
	tridD 256	0.710	0.724	0.685	0.696
	tridD 512	0.750	0.756	0.725	0.731
	CNN 128	0.648	0.682	0.617	0.645
	CNN 256	0.667	0.691	0.638	0.659
	CNN 512	0.679	0.703	0.652	0.672

Table 3 : Experiments on Paris6k and Paris106k.

 3

		Paris6k	Paris106k
	Representations Avg [1]	Ours	Avg [1]	Ours
	Vlad 256	0.654	0.661	0.521	0.529
	Vlad-3c 128	0.565	0.569	0.544	0.543
	Vlad-3c 256	0.598	0.607	0.574	0.577
	Vlad-3c 512	0.629	0.640	0.606	0.615
	CNN full	0.689	0.689	0.608	0.605
	CNN 128	0.749	0.752	0.658	0.658
	CNN 256	0.763	0.769	0.680	0.685
	CNN 512	0.767	0.775	0.685	0.692

 [START_REF] Arandjelovic | Multiple queries for large scale specific object retrieval[END_REF]This work was achieved in the context of the FIRE-ID ANR Project (ANR-12-CORD-016).