Filip Radenović

Ahmet Iscen

Giorgos Tolias

Yannis Avrithis

Ondřej Chum

Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking

In this paper we address issues with image retrieval benchmarking on standard and popular Oxford 5k and Paris 6k datasets. In particular, annotation errors, the size of the dataset, and the level of challenge are addressed: new annotation for both datasets is created with an extra attention to the reliability of the ground truth. Three new protocols of varying difficulty are introduced. The protocols allow fair comparison between different methods, including those using a dataset pre-processing stage. For each dataset, 15 new challenging queries are introduced. Finally, a new set of 1M hard, semi-automatically cleaned distractors is selected.

An extensive 1 comparison of the state-of-the-art methods is performed on the new benchmark. Different types of methods are evaluated, ranging from local-feature-based to modern CNN based methods. The best results are achieved by taking the best of the two worlds. Most importantly, image retrieval appears far from being solved.

Introduction

Image retrieval methods have gone through significant development in the last decade, starting with descriptors based on local-features, first organized in bagof-words [41], and further expanded by spatial verification [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], hamming embedding [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], and query expansion [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]. Compact representations reducing the memory footprint and speeding up queries started with aggregating local descriptors [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]. Nowadays, the most efficient retrieval methods are based on fine-tuned convolutional neural networks (CNNs) [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF][START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF][START_REF] Noh | Largescale image retrieval with attentive deep local features[END_REF].

In order to measure the progress and compare different methods, standardized image retrieval benchmarks are used. Besides the fact that a benchmark should simulate a realworld application, there are a number of properties that determine the quality of a benchmark: the reliability of the annotation, the size, and the challenge level.

Errors in the annotation may systematically corrupt the comparison of different methods. Too small datasets are prone to over-fitting and do not allow the evaluation of the efficiency of the methods. The reliability of the annotation and size of the dataset are competing factors, as it is difficult to secure accurate human annotation of large datasets. The size is commonly increased by adding a distractor set, which contains irrelevant images that are selected in an automated manner (different tags, GPS information, etc.) Finally, benchmarks where all the methods achieve almost perfect results [START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF] cannot be used for further improvement or qualitative comparison.

Many datasets have been introduced to measure the performance of image retrieval. Oxford [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] datasets belong to the most popular ones. Numerous methods of image retrieval [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF][START_REF] Chum | Total recall II: Query expansion revisited[END_REF][START_REF] Mikulik | Learning vocabularies over a fine quantization[END_REF][START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF][START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF][START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] and visual localization [START_REF] Gammeter | I know what you did last summer: object-level auto-annotation of holiday snaps[END_REF][START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] have used these datasets for evaluation. One reason for their popularity is that, in contrast to datasets that contain small groups of 4-5 similar images like Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] and UKBench [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF], Oxford and Paris contain queries with up to hundreds of positive images.

Despite the popularity, there are known issues with the two datasets, which are related to all three important properties of evaluation benchmarks. First, there are errors in the annotation, including both false positives and false negatives. Further inaccuracy is introduced by queries of different sides of a landmark, sharing the annotation despite being visually distinguishable. Second, the annotated datasets are relatively small (5,062 and 6,392 images respectively). Third, current methods report near-perfect results on both the datasets. It has become difficult to draw conclusions from quantitative evaluations, especially given the annotation errors [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF].

The lack of difficulty is not caused by the fact that nontrivial instances are not present in the dataset, but due to the annotation. The annotation was introduced about ten years ago. At that time, the annotators had different perception of what the limits of image retrieval are. Many instances that are nowadays considered as a change of viewpoint expected to be retrieved, are de facto excluded from the evaluation by being labelled as Junk.

The size issue of the datasets is partially addressed by the Oxford 100k distractor set. However, this contains false negative images, as well as images that are not challenging. State-of-the-art methods maintain near-perfect results even in the presence of these distractors. As a result, additional computational effort is spent with little benefit in drawing conclusions.

Contributions. As a first contribution, we generate new annotation for Oxford and Paris datasets, update the evaluation protocol, define new, more difficult queries, and create new set of challenging distractors. As an outcome we produce Revisited Oxford, Revisited Paris, and an accompanying distractor set of one million images. We refer to them as ROxford, RParis, and R1M respectively.

As a second contribution, we provide extensive evaluation of image retrieval methods, ranging from local-feature based to CNN-descriptor based approaches, including various methods of re-ranking.

Revisiting the datasets

In this section we describe in detail why and how we revisit the annotation of Oxford and Paris datasets, present a new evaluation protocol and an accompanying challenging set of one million distractor images. The revisited benchmark is publicly available2 .

The original datasets

The original Oxford and Paris datasets consist of 5,063 and 6,392 high-resolution (1024 × 768) images, respectively. Each dataset contains 55 queries comprising 5 queries per landmark, coming from a total of 11 landmarks. Given a landmark query image, the goal is to retrieve all database images depicting the same landmark. The original annotation (labeling) is performed manually and consists of 11 ground truth lists since 5 images of the same landmark form a query group. Three labels are used, namely, positive, junk, and negative3 .

Positive images clearly depict more than 25% of the landmark, junk less than 25%, while the landmark is not shown in negative ones. The performance is measured via mean average precision (mAP) [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] over all 55 queries, while junk images are ignored, i.e. the evaluation is performed as if they were not present in the database.

Revisiting the annotation

The annotation is performed by five annotators, and it is performed in the following steps.

Query groups. Query groups share the same groundtruth list and simplify the labeling problem, but also cause some inaccuracies in the original annotation. Balliol and Christ Church landmarks are depicted from a different (not fully symmetric) side in the 2 nd and 4 th query, respectively. Arc de Triomphe has three day and two night queries, while day-night matching is considered a challenging problem [START_REF] Verdie | TILDE: a temporally invariant learned detector[END_REF][START_REF] Radenović | From dusk till dawn: Modeling in the dark[END_REF]. We alleviate this by splitting these cases into separate groups. As a result, we form 13 and 12 query groups on Oxford and Paris, respectively.

Additional queries. We introduce new and more challenging queries (see Figure 1) compared to the original ones. There are 15 new queries per dataset, originating from five out of the original 11 landmarks, with three queries per landmark. Along with the 55 original queries, they comprise the new set of 70 queries per dataset. The query groups, defined by visual similarity, are 26 and 25 for ROxford and RParis, respectively. As in the original datasets, the query object bounding boxes are simulating not only a user attempting to remove background clutter, but also cases of large occlusion.

Labeling step 1: Selection of potential positives. Each annotator manually inspects the whole dataset and marks images depicting any side or version of a landmark. The goal is to collect all images that are originally incorrectly labeled as negative. Even uncertain cases are included in this step and the process is repeated for each landmark. Apart from inspecting the whole dataset, an interactive retrieval tool is used to actively search for further possible positive images. All images marked in this phase are merged together with images originally annotated as positive or junk, creating a list of potential positives for each landmark.

Labeling step 2: Label assignment. In this step, each annotator manually inspects the list of potential positives for each query group and assigns labels. The possible labels are Easy, Hard, Unclear, and Negative. All images not in the list of potential positives are automatically marked negative. The instructions given to the annotators for each of the labels are as follows.

• Easy: The image clearly depicts the query landmark from the same side, with no large viewpoint change, no significant occlusion, no extreme illumination change, and no severe background clutter. In the case of fully symmetric sides, any side is valid. • Hard: The image depicts the query landmark, but with viewing conditions that are difficult to match with the query. The depicted (side of the) landmark is recognizable without any contextual visual information. • Unclear: (a) The image possibly depicts the landmark in question, but the content is not enough to make a certain guess about the overlap with the query region, or context is needed to clarify. (b) The image depicts a different side of a partially symmetric building, where the symmetry is significant and discriminative enough. • Negative: The image is not satisfying any of the previous conditions. For instance, it depicts a different side of the landmark compared to that of the query, with no discriminative symmetries. If the image has any physical overlap with the query, it is never negative, but rather unclear, easy, or hard according to the above.

Labeling step 3: Refinement. For each query group, each image in the list of potential positives has been assigned a five-tuple of labels, one per annotator. We perform majority voting in two steps to define the final label. The first step is voting for {easy,hard}, {unclear}, or {negative}, grouping easy and hard together. In case majority goes to {easy,hard}, the second step is to decide which of the two. Draws of the first step are assigned to unclear, and of the second step to hard. Illustrative examples are (EEHUU) → E, (EHUUN) → U, and (HHUNN) → U. Finally, for each query group, we inspect images by descending label entropy to make sure there are no errors.

Revisited datasets: ROxford and RParis. Images from which the queries are cropped are excluded from the evaluation dataset. This way, unfair comparisons are avoided in the case of methods performing off-line preprocessing of the database [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]; any preprocessing should not include any part of query images. The revisited datasets, namely, ROxford and RParis, comprise 4,993 and 6,322 images respectively, after removing the 70 queries.

In Table 1, we show statistics of label transitions from the old to the new annotations. Note that errors in the original annotation that affect the evaluation, e.g. negative moving to easy or hard, are not uncommon. The transitions from junk to easy or hard are reflecting the greater challenges of the new annotation. Representative examples of extreme labeling errors of the original annotation are shown in Figure 2. In Figure 3, representative examples of easy, hard, and unclear images are presented for several queries. This will help understanding the level of challenge of each evaluation protocol listed below.

Evaluation protocol

Only the cropped regions are to be used as queries; never the full image, since the ground-truth labeling strictly considers only the visual content inside the query region.

The standard practice of reporting mean average precision (mAP) [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] for performance evaluation is followed. Additionally, mean precision at rank K (mP@K) is reported. The former reflects the overall quality of the ranked list. The latter reflects the quality of the results of a search engine as they would be visually inspected by a user. More importantly, it is correlated to performance of subsequent processing steps [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Kalantidis | Viral: Visual image retrieval and localization[END_REF]. During the evaluation, positive images should be retrieved, while there is also an ignore list per query. Three evaluation setups of different difficulty are defined by treating labels (easy, hard, unclear) as positive or negative, or ignoring them:

• Easy (E): Easy images are treated as positive, while

Hard and Unclear are ignored (same as Junk in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]). If there are no positive images for a query in a particular setting, then that query is excluded from the evaluation. The original annotation and evaluation protocol is closest to our Easy setup. Even though this setup is now trivial for the best performing methods, it can still be used for evaluation of e.g. near duplicate detection or retrieval with ultra short codes. The other setups, Medium and Hard, are challenging and even the best performing methods achieve relatively low scores. See Section 4 for details.

Distractor set R1M

Large scale experiments on Oxford and Paris dataset are commonly performed with the accompanying distractor set of 100k images, namely Oxford100k [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Recent results [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF][START_REF] Iscen | Fast spectral ranking for similarity search[END_REF] show that the performance only slightly degrades by adding Oxford100k in the database compared to a small-scale setting. Moreover, it is not manually cleaned and, as a consequence, Oxford and Paris landmarks are depicted in some of the distractor images (see Figure 4), hence adding further noise to the evaluation procedure.

Larger distactor sets are used in the literature [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF][START_REF] Tolias | Speeded-up, relaxed spatial matching[END_REF] but none of them are standardized to provide a testbed for direct large scale comparison nor are they manually cleaned [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. Some of the distractor sets are also biased, since they contain images of different resolution than the Oxford and Paris datasets.

We construct a new distractor set with exactly 1,001,001 high-resolution (1024 × 768) images, which we refer to as R1M dataset. It is cleaned by a semi-automatic process. We automatically pick hard images for a number of state-of-theart methods, resulting in a challenging large scale setup.

YFCC100M and semi-automatic cleaning. We randomly choose 5M images with GPS information from YFCC100M dataset [START_REF] Thomee | YFCC100M: The new data in multimedia research[END_REF]. Then, we exclude UK, France, and Las Vegas; the latter due to the Eiffel Tower and Arc de Triomphe replicas. We end up with roughly 4.1M images that are available for downloading in high resolution. We rank images with the same search tool as used in labeling step 1. Then, we manually inspect the top 2k images per landmark, and remove those depicting the query landmarks (faulty GPS, toy models, and paintings/photographs of landmarks). In total, we find 110 such images. Un-biased mining of distracting images. We propose a way to keep the most challenging 1M out of the 4.1M images. We perform all 70 queries into the 4.1M database with a number of methods. For each query and for each distractor image we count the fraction of easy or hard images that are ranked after it. We sum these fractions over all queries of ROxford and RParis and over different methods, resulting in a measurement of how distracting each distractor image is. We choose the set of 1M most distracting images and refer to it as the R1M distractor set.

Three complementary retrieval methods are chosen to compute this measurement. These are fine-tuned ResNet with GeM pooling [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF], pre-trained (on ImageNet) AlexNet with MAC pooling [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF], and ASMK [START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF]. More details on these methods are given in Section 3. Finally, we perform a sanity check to show that this selection process is not significantly biased to distract only those 3 methods. This includes two additional methods, VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and finetuned ResNet with R-MAC pooling by Gordo et al. [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF]. As shown in Table 2, the performance on the hardest 1M distractors is hardly affected whether one of those additional methods participates or not in the selection process. This suggests that the mining process is not biased towards particular methods.

Table 2 also shows that the distractor set we choose (version 1M (1,2,3) in the Table) is much harder than a random 1M subset and nearly as hard as all 4M distractor images. Example images from the set R1M are shown in Figure 5.

Extensive evaluation

We evaluate a number of state-of-the-art approaches on the new benchmark and offer a rich testbed for future comparisons. We list them in this section and they belong to two main categories, namely, classical retrieval approaches using local features and CNN-based methods producing global image descriptors.

Local-feature-based methods

Methods based on local invariant features [25,[START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF] and the Bag-of-Words (BoW) model [41,[START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Chum | Geometric minhashing: Finding a (thick) needle in a haystack[END_REF][START_REF] Mikulik | Learning vocabularies over a fine quantization[END_REF][START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF][START_REF] Cao | Spatialbag-of-features[END_REF][START_REF] Zheng | Lp-norm idf for large scale image search[END_REF][START_REF] Zhou | Spatial coding for large scale partial-duplicate web image search[END_REF][START_REF] Tao | Locality in generic instance search from one example[END_REF] were dominating the field of image retrieval until the advent of CNN-based approaches [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF][START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF][START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF][START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF][START_REF] Mohedano | Bags of local convolutional features for scalable instance search[END_REF][START_REF] Yue-Hei | Exploiting local features from deep networks for image retrieval[END_REF]. A typical pipeline consists of invariant local feature detection [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF], local descriptor extraction [25], quantization with a visual codebook [41], typically created with k-means, assignment of descriptors to visual words and finally descriptor aggregation in a single embedding [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF][START_REF] Perronnin | Large-scale image retrieval with compressed Fisher vectors[END_REF] or individual feature indexing with an inverted file structure [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF]. We consider state-ofthe-art methods from both categories. In particular, we use up-right hessian-affine (HesAff) features [START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF], RootSIFT (rSIFT) descriptors [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], and create the codebooks on the landmark dataset from [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF], same as the one used for the whitening of CNN-based methods. Note that we always crop the queries according to the defined region and then perform any processing to be directly comparable to CNNbased methods.

Distractor set [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF]; (3) HesAff-rSIFT-ASMK [START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF]; (4) Fine-tuned ResNet101 with R-MAC pooling [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF]; (5) HesAff-rSIFT-VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]. The sanity check includes evaluation for different distractor sets, i.e. all, hardest subset chosen by method (1,2,3), [START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF][START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF][START_REF] Cao | Spatialbag-of-features[END_REF], [START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF][START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Cao | Spatialbag-of-features[END_REF][START_REF] Chum | Total recall II: Query expansion revisited[END_REF], and a random 1M sample.

ROxford RParis Method (1) (2) (3) (4) (5) (1) (2) (3) (4) (
We additionally follow the same BoW-based pipeline while replacing hessian-affine and RootSIFT with the deep local attentive features (DELF) [START_REF] Noh | Largescale image retrieval with attentive deep local features[END_REF]. The default extraction approach is followed (i.e. at most 1000 features per image), but we reduce the descriptor dimensionality to 128 and not to 40 to be comparable to RootSIFT. This variant is a bridge between classical approaches and deep learning. VLAD. The Vector of Locally Aggregated Descriptors [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] (VLAD) is created by first-order statistics of the local descriptors. The residual vectors between descriptors and the closest centroid are aggregated w.r.t. a codebook whose size is 256 in our experiments. We reduce its dimensionality down to 2048 with PCA, while square-root normalization is also used [START_REF] Jégou | Negative evidences and cooccurences in image retrieval: The benefit of PCA and whitening[END_REF]. SMK . The binarized version of the Selective Match Kernel [START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF] (SMK ), a simple extension of the Hamming Embedding [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] (HE) technique, uses an inverted file structure to separately indexes binarized residual vectors while it performs the matching with a selective monomial kernel function. The codebook size is 65,536 in our experiments, while burstiness normalization [START_REF] Jégou | On the burstiness of visual elements[END_REF] is always used. Multiple assignment to three nearest words is used on the query side, while the hamming distance threshold is set to 52 out of 128 bits. The rest are the default parameters. ASMK . The binarized version of the Aggregated Selective Match Kernel [START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF] (ASMK ) is an extension of SMK that jointly encodes local descriptors that are assigned to the same visual word and handles the burstiness phenomenon. Same parametrization as SMK is used. SP. Spatial verification (SP) is known to be crucial for particular object retrieval [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and is performed with the RANSAC algorithm [START_REF] Fischler | Random sample consensus[END_REF]. It is applied on the 100 top-ranked images, as these are formed by a first filtering step, e.g. the SMK or ASMK method. Its result is the number of inlier correspondences, which is one of the most intuitive similarity measures and allows to detect true positive images. To assume that an image is spatially verified, we require 5 inliers with ASMK and 10 with other methods. HQE. Query expansion (QE), firstly introduced by Chum et al. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] in the visual domain, typically uses spatial verification to select true positive among the top retrieved result and issues an enhanced query including the verified images. Hamming Query Expansion [START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF] (HQE) is combining QE with HE. We use same soft assignment as SMK and the default parameters.

CNN-based global descriptor methods

We list different aspects of a CNN-based method for image retrieval, which we later combine to form different baselines that exist in the literature.

CNN architectures. We include 3 highly influential CNN architectures, namely AlexNet [22], VGG-16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], and ResNet101 [12]. They have different number of layers, complexity, and also produce descriptors of different dimensionality (256, 512, and 2048, respectively).

Pooling. A common practice is to consider a convolutional feature map and perform a pooling mechanism to construct a global image descriptor. We consider max-pooling (MAC) [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF], sum-pooling (SPoC) [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF], weighted sum-pooling (CroW) [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF], regional max-pooling (R-MAC) [START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF], generalized mean-pooling (GeM) [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF], and NetVLAD pooling [START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF]. The pooling is always applied on the last convolutional feature map.

Multi-scale. The input image is resized to a maximum 1024 × 1024 size. Then, three re-scaled versions with scaling factor of 1, 1 / √ 2, and 1 /2 are fed to the network. Finally, the resulting descriptors are combined into a single descriptor by average pooling [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] for all methods, except for GeM where generalized-mean pooling is used [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF]. This is shown to improve the performance of the CNN-based descriptors [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF][START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF].

Off-the-shelf vs. retrieval fine-tuning. Networks that are pre-trained on ImageNet [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF] (off-the-shelf) are directly applicable on image retrieval. Moreover, we consider the following cases of fine-tuning for the task. Radenovic et al. [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] fine-tune a network with landmarks photos using contrastive loss [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF]. This is available with MAC [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] and GeM pooling [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF]. Similarly, Gordo et al. [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] fine-tune R-MAC pooling with landmark photos and triplet loss [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]. Finally, NetVLAD [START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] is fine-tuned using street-view images and GPS information.

Descriptor whitening is known to be essential for such descriptors. We use the same landmark dataset [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF] to learn the whitening for all methods. We use PCA whitening [START_REF] Jégou | Negative evidences and cooccurences in image retrieval: The benefit of PCA and whitening[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] for all the off-the-shelf networks, and supervised whitening with SfM labels [START_REF] Mikolajczyk | Improving descriptors for fast tree matching by optimal linear projection[END_REF][START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] for all the fine-tuned ones. One exception is the tuning that includes the whitening in the network [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF].

Query Expansion is directly applicable on top of global CNN-based descriptors. More specifically, we use α query expansion [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF] (αQE) and diffusion [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF] (DFS).

Results

We report a performance comparison between the old and the revisited datasets. Additionally, we provide an extensive evaluation of the state-of-the-art methods on the revisited dataset, with and without the new large-scale distractor set, setting up a testbed for future comparisons.

The evaluation includes local feature-based approaches (see Section 3.1 for details and abbreviations), referred to by the combination of local feature type and representation method, e.g. HesAff-rSIFT-ASMK . CNN-based global descriptors are denoted with the following abbreviations. Network architectures are AlexNet (A), VGG-16 (V), and ResNet101 (R). The fine-tuning options are triplet loss with GPS guided mining [START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF], triplet loss with spatially verified positive pairs [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF], contrastive loss with mining from 3D models [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] and [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF], and finally the off-the-shelf [O] networks. Pooling approaches are as listed in Section 3.2. For instance, ResNet101 with GeM pooling that is fine-tuned with contrastive loss and the training dataset by Radenovic et al. [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF] is referred to as R- [START_REF] Radenović | Fine-tuning CNN image retrieval with no human annotation[END_REF]-GeM.

Revisited vs. original. We compare the performance when evaluated on the original datasets, and the revisited annotation with the new protocols. The results for four representative methods are presented in Table 3. The old setup appears to be close to the new Easy setup, while Medium and Hard appear to be more challenging. We observe that the performance of the Easy setup is nearly saturated and, therefore, do not use it but only evaluate Medium and Hard setups in the subsequent experiments. Table 5. Performance evaluation (mAP, mP@10) on ROxford (ROxf) and RParis (RPar) without and with R1M distractors. We report results with the revisited annotation, using Medium and Hard evaluation protocols. We use a color-map that is normalized according to the minimum (white white white white white white white white white white white white white white white white white) and maximum (green / orange) value per column.

State of the art evaluation. We perform an extensive evaluation of the state-of-the-art methods for image retrieval. We present time/memory measurements in Table 4 and performance results in Table 5. We additionally show the average precision (AP) per query for a set of representative methods in Figures 6 and7, for ROxford and RParis, respectively. The representative set covers the progress of methods over time in the task of image retrieval. In the evaluation, we observe that there is no single method achieving the highest score on every protocol per dataset. Localfeature-based methods perform very well on ROxford, especially at large scale, achieving state-of-the-art performance, while CNN-based methods seem to dominate on RParis. We observe that BoW-based classical approaches are still not obsolete, but their improvement typically comes at significant additional cost. Recent CNN-based local features, i.e. DELF, reduce the number of features and improve the performance at the same time.

CNN fine-tuning consistently brings improvements over the off-the-shelf networks. The new protocols make it clear that improvements are needed at larger scale and the hard setup. Many images are not retrieved, while the top 10 results mostly contain false positives. Interestingly, we observe that query expansion approaches (e.g. diffusion) degrade the performance of queries with few relevant images (see Figures 6 and7). This phenomenon is more pronounced in the revisited datasets, where the the query images are removed from the preprocessing. We did not include separate regional representation and indexing [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF], which is previously shown to be beneficial. Preliminary experiments with ResNet and GeM pooling show that it does not deliver improvements that are significant enough to justify the additional memory and complexity cost.

The best of both worlds. The new dataset and protocols reveal space for improvement by CNN-based global descriptors in cases where local features are still better. Diffu- 5, improves the performance and supports the message that both worlds have their own benefits. Of course this experiment is expensive and we perform it to merely show a possible direction to improve CNN global descriptors. There are more methods that combine CNNs and local features [START_REF] Zheng | Accurate image search with multi-scale contextual evidences[END_REF], but we focus on the results related to methods included in our evaluation.

Conclusions

We have revisited two of the most established image retrieval datasets, that were perceived as performance saturated. To make it suitable for modern image retrieval benchmarking, we address drawbacks of the original annotation. This includes new annotation for both datasets that was created with an extra attention to the reliability of the ground truth, and an introduction of 1M hard distractor set.

An extensive evaluation provides a testbed for future comparisons and concludes that image retrieval is still an open problem, especially at large scale and under difficult viewing conditions.

Figure 1 .Figure 2 .

 12 Figure 1. The newly added queries for ROxford(top) and RParis(bottom) datasets. Merged with the original queries, they comprise a new set of 70 queries in total.→ → →

  • Medium (M): Easy and Hard images are treated as positive, while Unclear are ignored. • Hard (H): Hard images are treated as positive, while Easy and Unclear are ignored.

Figure 3 .

 3 Figure 3. Sample query (blue) images and images that are respectively marked as easy (dark green), hard (light green), and unclear (yellow). Best viewed in color.

Figure 4 .

 4 Figure 4. Sample false negative images in Oxford100k.

Figure 5 .

 5 Figure 5. The most distracting images per query for two queries.

Figure 6 .

 6 Figure 6. Performance (AP) per query on ROxford + R1M with Medium setup. AP is shown with a bar for 8 methods. The methods, from left to right, are HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP, DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP, DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP, V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC, R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM, R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM, R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS, HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS. The total number of easy and hard images is printed on each histogram. Best viewed in color.

Figure 7 .

 7 Figure 7. Performance (AP) per query on RParis + R1M with Medium setup. AP is shown with a bar for 8 methods. The methods, from left to right, are HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP HesAff-rSIFT-ASMK +SP, DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP DELF-ASMK +SP, DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP DELF-HQE+SP, V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC V-[O]-R-MAC, R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM R-[O]-GeM, R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM R-[37]-GeM, R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS R-[37]-GeM+DFS, HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS. The total number of easy and hard images is printed on each histogram. Best viewed in color. sion performs similarity propagation by starting from the query's nearest neighbors according to the CNN global descriptor. This inevitably includes false positives, especially in the case of few relevant images. On the other hand, local features, e.g. with ASMK +SP, offer a verified list of relevant images. Starting the diffusion process from geometrically verified images obtained by BoW methods combines the benefits of the two worlds. This combined approach, shown at the bottom part of Table5, improves the performance and supports the message that both worlds have their own benefits. Of course this experiment is expensive and we perform it to merely show a possible direction to improve CNN global descriptors. There are more methods that combine CNNs and local features[START_REF] Zheng | Accurate image search with multi-scale contextual evidences[END_REF], but we focus on the results related to methods included in our evaluation.

Table 4 .

 4 Time and memory measurements. Extraction time on a single thread GPU (Tesla P100) / CPU (Intel Xeon CPU E5-2630 v2 @ 2.60GHz) per image of size 1024x768, the memory requirements and the search time (single thread CPU) reported for the database of ROxford+R1M images. Feature extraction + visual word assignment is reported for ASMK . SP: Geometry information is loaded from the disk and the loading time is included in search time. We did not consider geometry quantization[START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF].

  .6 35.8 64.6 59.0 97.4 34.1 89.1 35.4 53.7 16.4 27.7 31.2 72.6 10.5 47.6 HesAff-rSIFT-ASMK 60.4 85.6 45.0 76.0 61.2 97.9 42.0 95.3 36.4 56.7 25.7 42.1 34.5 80.6 16.5 63.4 HesAff-rSIFT-SMK +SP 59.8 84.3 38.1 67.1 59.2 97.4 34.5 89.3 35.8 54.0 17.7 30.3 31.3 73.6 11.0 49.1 HesAff-rSIFT-ASMK +SP 60.6 86.1 46.8 79.6 61.4 97.9 42.3 95.3 36.7 57.0 26.9 45.3 35.0 81.7 16.8 65.3

					Medium							Hard
	Method	ROxf	ROxf+R1M	RPar	RPar+R1M	ROxf	ROxf+R1M	RPar	RPar+R1M
		mAP	mP@10	mAP	mP@10	mAP	mP@10	mAP	mP@10	mAP	mP@10	mAP	mP@10	mAP	mP@10	mAP	mP@10
	HesAff-rSIFT-VLAD	33.9 54.9 17.4 34.8 43.6 90.9 19.6 76.1 13.2 18.1 5.6	7.0 17.5 50.7 3.3 21.1
	HesAff-rSIFT-SMK 59.4 83DELF-ASMK +SP 67.8 87.9 53.8 81.1 76.9 99.3 57.3 98.3 43.1 62.4 31.2 50.7 55.4 93.4 26.4 75.7
	A -[O] -MAC	28.3 44.7 14.1 28.3 47.3 88.6 18.7 69.4 8.8 15.5 3.5	5.1 23.1 61.6 4.1 29.0
	A -[O] -GeM	33.8 51.2 16.3 32.4 52.7 90.1 23.8 78.1 10.4 16.7 3.9	6.3 26.0 68.0 5.5 31.6
	A -[36] -MAC	41.3 62.1 23.9 43.0 56.4 92.9 29.6 85.4 17.8 28.2 8.4 11.9 28.7 69.3 8.5 40.9
	A -[37] -GeM	43.3 62.1 24.2 42.8 58.0 91.6 29.9 84.6 17.1 26.2 9.4 11.9 29.7 67.6 8.4 39.6
	V -[O] -MAC	37.8 57.8 21.8 39.7 59.2 93.3 33.6 87.1 14.6 27.0 7.4 11.9 35.9 78.4 13.2 54.7
	V -[O] -SPoC	38.0 54.6 17.1 33.3 59.8 93.0 30.3 83.0 11.4 20.9 0.9	2.9 32.4 69.7 7.6 30.6
	V -[O] -CroW	41.4 58.8 22.5 40.5 62.9 94.4 34.1 87.1 13.9 25.7 3.0	6.6 36.9 77.9 10.3 45.1
	V -[O] -GeM	40.5 60.3 25.4 45.6 63.2 94.6 37.5 88.6 15.7 28.6 7.6 12.1 38.8 79.0 14.2 55.9
	V -[O] -R-MAC	42.5 62.8 21.7 40.3 66.2 95.4 39.9 88.9 12.0 26.1 1.7	5.8 40.9 77.1 14.8 54.0
	V -[1] -NetVLAD	37.1 56.5 20.7 37.1 59.8 94.0 31.8 85.7 13.8 23.3 6.0	8.4 35.0 73.7 11.5 46.6
	V -[36] -MAC	58.4 81.1 39.7 68.6 66.8 97.7 42.4 92.6 30.5 48.0 17.9 27.9 42.0 82.9 17.7 63.7
	V -[37] -GeM	61.9 82.7 42.6 68.1 69.3 97.9 45.4 94.1 33.7 51.0 19.0 29.4 44.3 83.7 19.1 64.9
	R -[O] -MAC	41.7 65.0 24.2 43.7 66.2 96.4 40.8 93.0 18.0 32.9 5.7 14.4 44.1 86.3 18.2 67.7
	R -[O] -SPoC	39.8 61.0 21.5 40.4 69.2 96.7 41.6 92.0 12.4 23.8 2.8	5.6 44.7 78.0 15.3 54.4
	R -[O] -CroW	42.4 61.9 21.2 39.4 70.4 97.1 42.7 92.9 13.3 27.7 3.3	9.3 47.2 83.6 16.3 61.6
	R -[O] -GeM	45.0 66.2 25.6 45.1 70.7 97.0 46.2 94.0 17.7 32.6 4.7 13.4 48.7 88.0 20.3 70.4
	R -[O] -R-MAC	49.8 68.9 29.2 48.9 74.0 97.7 49.3 93.7 18.5 32.2 4.5 13.0 52.1 87.1 21.3 67.4
	R -[37] -GeM	64.7 84.7 45.2 71.7 77.2 98.1 52.3 95.3 38.5 53.0 19.9 34.9 56.3 89.1 24.7 73.3
	R -[10] -R-MAC	60.9 78.1 39.3 62.1 78.9 96.9 54.8 93.9 32.4 50.0 12.5 24.9 59.4 86.1 28.0 70.0
			Query expansion (QE) and diffusion (DFS)
	HesAff-rSIFT-HQE	66.3 85.6 42.7 67.4 68.9 97.3 44.2 90.1 41.3 60.0 23.2 37.6 44.7 79.9 20.3 51.4
	HesAff-rSIFT-HQE+SP	71.3 88.1 52.0 76.7 70.2 98.6 46.8 93.0 49.7 69.6 29.8 50.1 45.1 83.9 21.8 61.9
	DELF-HQE+SP	73.4 88.2 60.6 79.7 84.0 98.3 65.2 96.1 50.3 67.2 37.9 56.1 69.3 93.7 35.8 69.1
	R -[O] -R-MAC+αQE	51.9 70.3 30.8 49.7 77.3 97.9 55.3 94.7 21.8 35.2 5.2 15.9 57.0 87.6 28.0 76.1
	V -[37] -GeM+αQE	66.6 85.7 47.0 72.0 74.0 98.4 52.9 95.9 38.9 57.3 21.1 34.6 51.0 88.4 25.6 75.0
	R -[37] -GeM+αQE	67.2 86.0 49.0 74.7 80.7 98.9 58.0 95.9 40.8 54.9 24.2 40.3 61.8 90.6 31.0 80.4
	R -[10] -R-MAC+αQE	64.8 78.5 45.7 66.5 82.7 97.3 61.0 94.3 36.8 53.3 19.5 36.6 65.7 90.1 35.0 76.9
	V -[37] -GeM+DFS	69.6 84.7 60.4 79.4 85.6 97.1 80.7 97.1 41.1 51.1 33.1 49.6 73.9 93.7 65.3 93.1
	R -[37] -GeM+DFS	69.8 84.0 61.5 77.1 88.9 96.9 84.9 95.9 40.5 54.4 33.1 48.2 78.5 94.6 71.6 93.7
	R -[10] -R-MAC+DFS	69.0 82.3 56.6 68.6 89.5 96.7 83.2 93.3 44.7 60.5 28.4 43.6 80.0 94.1 70.4 89.1
	HesAff-rSIFT-ASMK +SP → R-[37]-GeM+DFS	79.1 92.6 74.3 87.9 91.0 98.3 85.9 97.1 52.7 66.1 48.7 65.9 81.0 97.9 73.2 96.6
	HesAff-rSIFT-ASMK +SP → R-[10]-R-MAC+DFS 80.2 93.7 74.9 87.9 92.5 98.7 87.5 97.1 54.8 70.6 47.5 62.4 84.0 98.3 76.0 96.3
	DELF-ASMK +SP → R-[10]-R-MAC+DFS	75.0 87.9 68.7 83.6 90.5 98.0 86.6 98.1 48.3 64.0 39.4 55.7 81.2 95.6 74.2 94.6

The authors were supported by the MSMT LL1303 ERC-CZ grant.[START_REF] Arandjelovic | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] We thank Facebook for the donation of GPU servers, which made the evaluation tractable.

cmp.felk.cvut.cz/revisitop

We rename the originally used labels {good, ok, junk, and absent} for the purpose of consistency with our terminology. Good and ok were always used as positives.


Ahmet Iscen

Giorgos Tolias

Yannis Avrithis

Ondřej Chum

Mining on Manifolds: Metric Learning without Labels

In this work we present a novel unsupervised framework for hard training example mining. The only input to the method is a collection of images relevant to the target application and a meaningful initial representation, provided e.g. by pre-trained CNN. Positive examples are distant points on a single manifold, while negative examples are nearby points on different manifolds. Both types of examples are revealed by disagreements between Euclidean and manifold similarities. The discovered examples can be used in training with any discriminative loss.

The method is applied to unsupervised fine-tuning of pretrained networks for fine-grained classification and particular object retrieval. Our models are on par or are outperforming prior models that are fully or partially supervised.

Introduction

The success of deep neural networks on large-scale problems has been first demonstrated on the task of supervised classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. It was shown that embeddings, typically provided by the convolutional layers of a network, are applicable beyond classification tasks. These tasks include particular object retrieval [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF], local descriptor learning [START_REF] Han | MatchNet: Unifying feature and metric learning for patchbased matching[END_REF], ranking [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF], and nearest-neighbor regression [START_REF] Bautista | CliqueCNN: Deep unsupervised exemplar learning[END_REF]. A common practice is to start with a pre-trained network [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF][START_REF] Szegedy | Going deeper with convolutions[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF] and apply metric learning [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF][START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]18] to fine-tune the network for a particular task.

To improve over the initial network, novel training samples are sought for which the initial network performs poorly. Such training samples are used to re-train the network using loss functions alternative to cross-entropy (e.g. contrastive [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF], triplet [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF] or batch-level [36]). The approaches to obtain relevant training data range from further human supervision [3,36] to instance clustering [START_REF] Rippel | Metric learning with adaptive density discrimination[END_REF]32,[START_REF] Bautista | Deep unsupervised similarity learning using partially ordered sets[END_REF], exploiting the temporal dimension in video [START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF][START_REF] Wang | Transitive invariance for selfsupervised visual representation learning[END_REF], predicting the spatial layout of image patches [11], or using existing computer vision pipelines to match unstructured image collections pairwise [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF][START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF].

Most recent deep metric learning approaches can learn powerful embeddings but still use class labels. This is unsatisfying not only because we miss the opportunity of learning from unlabeled data, but learned representations of each class are unimodal [START_REF] Rippel | Metric learning with adaptive density discrimination[END_REF]. Therefore, whatever the loss function [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]36]) or sampling [18,[START_REF] Movshovitz-Attias | No fuss distance metric learning using proxies[END_REF], the problem remains supervised classification. On the other hand, conventional nonlinear dimension reduction or manifold learning methods exploit the manifold structure of the data starting from nearest neighbor graphs and are otherwise unsupervised [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF][START_REF] Saul | Think globally, fit locally: unsupervised learning of low dimensional manifolds[END_REF][START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF]. However, most do not learn an explicit mapping from the input to the embedding space and have difficulties in generalizing to new data.

We attempt to bridge this gap in this work. In particular, we propose a novel method of hard training sample mining in a fully unsupervised manner, simply from an unordered collection of images relevant to the final task. We observe that a similarity between two images is improved by considering all, even unlabelled, available data. In particular, we exploit similarity measured on a manifold estimated by a random walk process [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF].

The learning starts from the initial representation space of unlabeled data. Given an anchor point that is part of the data, neighbors on the manifold that are not Euclidean neighbors are considered positive samples. In the new learned representation space, the positive sample should be attracted to the anchor to reflect the similarity measured on the manifold. Conversely, Euclidean neighbors that are not neighbors on the manifold are considered negative and should be repelled. The idea is illustrated in Figure 1.

The advantage of learning a new representation over using the estimated manifold similarity is twofold. First, estimating the manifold similarity has additional computational and memory requirements at query time. Second, we show that the novel embedding generalizes better not only to previously unseen queries, but also to unseen datasets.

We apply the proposed method to fine-grained classification and to particular object retrieval. Our models obtained by unsupervised fine-tuning of pre-trained networks are on par or are outperforming prior models that are human supervised or use additional domain-specific expertise.

The paper is organized as follows. Section 2 discusses related work. Sections 3 and 4 present our learning method and applications, respectively. Experiments are given in Section 5 conclusions are drawn in Section 6.

Related work

This section contains a brief overview of related work on metric learning, embeddings for instance retrieval and representation learning without human labeled data.

Metric learning.

Recent approaches based on low-dimensional CNN-based embeddings achieve promising results on this task [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF]36]. A key ingredient of some approaches is hard negative mining, which comes from the days of SVMs in object detection [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF]. This principle has been known much earlier as bootstrapping [START_REF] Sung | Learning and example selection for object and pattern detection[END_REF]. Instead of sampling all negative instances for an anchor point, the most challenging negative instances are mined which finally offer faster but equally accurate learning. However, this process is not trivial. Simple hard negative mining from a different class label might corrupt the training process due to mislabeled images [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF][START_REF] Mishchuk | Working hard to know your neighbor's margins: Local descriptor learning loss[END_REF].

Schroff et al. [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF] use triplet loss and propose semi-hard mining in an attempt to solve this problem. They sample negatives within the batch, such that they are close to the anchor point but further away from positives. This concept is widely adapted in other metric learning approaches [START_REF] Parkhi | Deep face recognition[END_REF]36]. Wu et al. [START_REF] Wu | Sampling matters in deep embedding learning[END_REF] improve it by uniformly sampling negative instances weighted by their distance. This allows them to sample points from various regions of the feature space instead of certain clusters.

Other methods, such as lifted-structure [36] and n-pair loss [START_REF] Sohn | Improved deep metric learning with multi-class n-pair loss objective[END_REF], focus on the loss function and define constraints on the pairwise distances of all points in a batch. More recently, several methods try to optimize the learned embedding based on the global distribution of the data. Song et al. [START_REF] Song | Deep metric learning via facility location[END_REF] try to optimize the clustering quality. Harwood et al. [18] combine triplet loss and global loss using an efficient hard mining procedure. All these methods use class labels during sampling.

Particular object retrieval is another application where descriptors are trained similarly to metric learning. How-ever, class labels do not usually exist as it is intractable to enumerate all possible instances or their viewpoints. Traditional instance search algorithms use hand-designed descriptors [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF][START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF], but recent advances show the interest of feature learning [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF]. Transfer learning from category-level classification is one case [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF]. Labeling at landmark level has been attempted as well, treating this task as classification, but the labels are quite noisy [3].

The state-of-the-art approaches start with an off-theshelf network, and fine-tune it with algorithmic supervision [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF]. They make use of geometric matching to mine matching and non-matching image pairs. They involve local feature extraction and require an expensive pre-processing of data. Furthermore, they assume that the training set contains landmarks and buildings that perform well with geometric matching of local features. We make no such assumptions nor require additional computer vision system to perform the mining. Our only assumption is that there are multiple object instances in the training set.

Incomplete, noisy, or unavailable labels are handled in various ways in the literature. In the contrastive loss paper of Hadsell et al. [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF], the authors show that it is possible to separate different categories to different subspaces just by assigning the Euclidean nearest neighbors as positive training instances. In recent works, the labeling is guided by the information of different modalities or the data collection process. Arandjelović et al. [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] learn visual descriptors for location recognition by assigning labels based on the GPS location of each image. Wang and Gupta [START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF] sample frames from videos and assume that frames from same videos will be positive to each other. Isola et al. [START_REF] Isola | Learning visual groups from co-occurrences in space and time[END_REF] group objects based on their co-occurence within the same spatial or temporal context. Similarly, learning from the spatial arrangement of the patches within an image is shown feasible [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF][START_REF] Noroozi | Unsupervised learning of visual representations by solving jigsaw puzzles[END_REF]. Finally, other cases utilize different modalities, such as learning visual descriptors from text information [START_REF] Gomez | Self-supervised learning of visual features through embedding images into text topic spaces[END_REF], or learning audio descriptors from unlabeled videos [START_REF] Aytar | Soundnet: Learning sound representations from unlabeled video[END_REF]. By contrast, we make no assumptions on the available modalities or contextual information.

Unsupervised methods and manifold learning. There are very few methods on deep metric learning that are unsupervised. Examples are two methods on learning fine-grained similarity by exploiting mutual proximity [START_REF] Bautista | CliqueCNN: Deep unsupervised exemplar learning[END_REF] and ranking [START_REF] Bautista | Deep unsupervised similarity learning using partially ordered sets[END_REF] in the Euclidean space. Both utilize some form of clustering and splitting the training set in different groups, which is an artificial constraint, and none takes the underlying manifold structure into account. Our method is conceptually simpler and compatible with any loss function requiring positive/negative samples.

The work of Li et al. [START_REF] Li | Unsupervised visual representation learning by graph-based consistent constraints[END_REF] is similar to ours in following a graph-based mining approach. In our comparisons, we show that choosing hard examples is essential and results in better performance for our approach. Recently, Pai et al. [START_REF] Pai | Parametric manifold learning via sparse multidimensional scaling[END_REF] learn the manifold structure by encouraging pairs of points to have a Euclidean distance in the embedding space equal to the geodesic distance on the graph. We use a more relaxed objective that is compatible to most metric learning formulations and loss functions, and a manifold similarity that is more scalable than the geodesic distance.

Embeddings are learned to approximate ranking on manifolds with fast spectral ranking [START_REF] Iscen | Fast spectral ranking for similarity search[END_REF]. However, this approach is dataset specific and does not generalize to unseen images. Improvements on this aspect are introduced by iterative manifold embedding [START_REF] Xu | Iterative manifold embedding layer learned by incomplete data for large-scale image retrieval[END_REF]. Nevertheless, the extension can handle a query image, or potentially a small set of unseen images, while a larger dataset increase significantly affects the manifold structure.

Method

In this section we describe our learning problem, briefly discuss the required background, and present our unsupervised training subset selection and the training process.

Problem formulation

Let X = {x 1 , . . . , x n } ⊂ X be an unordered and unlabeled collection of items, where X is the original input space of all possible items. Depending on the application, an item corresponds to an image, video, image region, local patch, etc. Function f (•; θ) : X → R d maps an item x to a vector z = f (x, θ) in a d-dimensional embedding space, where θ is a set of parameters to be learned.

The input items are represented by a set of features Y = {y 1 , . . . , y n } ⊂ Y, where Y is a feature space and y = g(x) for x ∈ X. Depending on the application, g may be the identity mapping, i.e. learn directly from input space, f (•; θ 0 ), i.e. learn from the same model with initial parameters θ 0 , or a different model. An existing model may have been supervised (in any way) or not.

Two items are matching if they are considered visually similar, otherwise non-matching. Our goal is to learn the model parameters such that matching items are mapped to nearby points in the embedding space, while non-matching items are well separated. This corresponds to a typical metric learning scenario, and common practice is to use manually defined labels in order to construct a training set of matching and non-matching pairs of items [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF][START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]18]. In this work, we only assume that the input items X and their features Y are available at training time.

A training pair is defined w.r.t. to a reference (anchor) item x r . A matching pair consists of the anchor and a positive item x + . Similarly a non-matching pair consists of the anchor and a negative item x -. Alternatively, we may use a triplet (x r , x + , x -). Our goal is to mine such training pairs without any supervision [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF][START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]18,18,[START_REF] Movshovitz-Attias | No fuss distance metric learning using proxies[END_REF], without any complementary computer vision system [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF][START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] or assumptions on the nature of the training data [START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF][START_REF] Wang | Transitive invariance for selfsupervised visual representation learning[END_REF]11].

Preliminaries

By NN e k (y) we denote the k Euclidean nearest neighbors of y ∈ Y , i.e. the k most similar items in Y according to some Euclidean similarity function s e : Y 2 → R. Similarly, by NN m k (y) we denote the k manifold nearest neighbors of y ∈ Y , i.e. the k most similar features in Y according to a manifold similarity s m : Y 2 → R. 1Given s e , we employ a random walk on the Euclidean nearest neighbor graph G to measure the manifold similarity s m [START_REF] Zhou | Ranking on data manifolds[END_REF]. The graph has Y as nodes. It is is undirected, weighted, represented by sparse symmetric adjacency matrix A = (a ij ) ∈ R n×n . Edges correspond to reciprocal k-nearest neighbors, with weights

a ij = s e (y i , y j ), if y i ∈ NN e k (y j ) ∧ y j ∈ NN e k (y i ) 0,
otherwise.

(1) There are no loops in the graph, i.e., the diagonal elements of A are zero. Starting from an arbitrary vector f (0) ∈ R n , the random walk for a given feature y i ∈ Y follows the iteration f

(t) i = α Âf (t-1) + (1 -α)e i , (2)
where e i is the i-th column of an n × n identity matrix, Â = D -1/2 AD -1/2 with D = diag(A1) being the degree matrix, and α ∈ [0, 1). Iteration (2) converges to the solution f i of the linear system

(I -α Â)f = (1 -α)e i . (3)
Following Iscen et al. [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], we use the conjugate gradient method to solve this system efficiently in practice, since Iα Â is positive-definite. We define the manifold similarity

s m (y i , y j ) = f i (j), (4)
i.e., the j-th element of

f i . Observe that s m is symmet- ric because in fact s m (y i , y j ) is the (i, j)-element of ma- trix (1 -α)(I -α Â) -1
, which is symmetric. This matrix is dense but we never compute it; we only compute its columns as needed. For instance, given y i ∈ Y , its manifold nearest neighbors NN m k (y i ) are the k maximum elements of the i-th column.

Manifold-guided selection of training samples

We are guided by the manifold similarity to select training samples. In particular, we exploit the differences between Euclidean and manifold nearest neighbors of anchor items. We first describe the selection of positives and negatives given an anchor. Then we discuss anchor selection.

Positives. Given an anchor item x r and the corresponding feature y r = g(x r ), which is used as query, we choose as positives the items that correspond to the manifold nearest neighbors of y r that are not Euclidean neighbors. Such difference provides evidence of a matching item that is not retrieved well in the feature space, as illustrated in Figure 1(c). In the embedding space, positives should be attracted to the anchor so that Euclidean and manifold neighbors agree.

We therefore simply compare the sets NN m k (y r ) and NN e k (y r ) and select the input items that correspond to their set difference

P + (x r ) = {x ∈ X : g(x) ∈ NN m k (y r ) \ NN e k (y r )} (5)
as the positive pool of anchor x r . The value of k controls the visual diversity of positives, with larger values giving the harder examples. In practice, we maintain the pool ordered by descending manifold similarity, so that we may truncate by keeping the examples with highest confidence. Mining hard positive examples, in contrast to negatives, is not common. Apart from positives being fewer than negatives, this is due to the large intraclass variability; it may result in positives that are too hard to learn. It can be achieved in cases with known geometry of the scene such that extreme cases are avoided [START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF][START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. In our case, the hardness is controlled by the manifold similarity according to the current model g, so drifting into very tough examples is less likely.

Negatives. Similarly, and as illustrated in Figure 1(d), we choose as negatives the items that correspond to the Euclidean nearest neighbors of y r that are not manifold neighbors. Such difference provides evidence of a non-matching item that is too close in the feature space. In the embedding space, positives should be repelled from the anchor. The negative pool of anchor x r is defined accordingly as

P -(x r ) = {x ∈ X : g(x) ∈ NN e k (y r ) \ NN m k (y r )}. (6)
It is common practice, and known to be beneficial [START_REF] Simo-Serra | Fracking deep convolutional image descriptors[END_REF], to select hard negative examples. By construction, its size is controlled by k. Again, we maintain the pool ordered by descending Euclidean similarity to keep the hardest negative examples.

Anchors. We are interested in anchors that have many relevant images in the collection, which facilitates propagating on the manifold and discovering differences with the Euclidean neighborhood. We are also interested in anchors that are diverse, so that there is as little redundancy during training. Both conditions are satisfied by the modes of the nearest neighbor graph G, which we compute as follows.

We first compute the stationary probability distribution π of a random walk [8] on G. This is achieved by the power iteration method [28] yielding the leading left eigenvector of the transition matrix P = D -1 A, such that πP = π. The probability reflects the importance of each node in the graph, as expressed by the probability of a random walker visiting it. We find the local maxima of the stationary distribution on G and out of those, we keep a fixed number having the maximum probability. This is defined as the anchor set A. This method has been previously used for image graph visualization [START_REF] Douze | Polysemous codes[END_REF].

Training

The complete training pool P is the union of the anchor set A and the positive and negative pools P + (x), P -(x) for each x ∈ A. We follow the common practice in metric learning and train a network with two or three branches and use contrastive or triplet loss, respectively. All branches share weights, while the particular network architecture is application specific and is discussed in Section 4.

In both cases of contrastive or triplet loss, we form training tuples of one anchor x r ∈ A, one positive x + ∈ P + (x r ), and one negative item x -∈ P -(x r ) . At each epoch, the embedding z = f (x; θ) for each x ∈ P, where θ is the current set of parameters. For each anchor x r , a positive item x + is drawn at random from its positive pool, and one negative x -is drawn at random from a subset of its negative pool. This subset consists of the items corresponding to the Euclidean nearest neighbors of z r = f (x r ; θ) in the embedding space. Thus, while the manifold neighbors and the training pool are computed once at the beginning, hard negative sampling uses the current network representation. Finally, the training set for this epoch is the set of such tuples (x r , x + , x -).

Given a tuple (x r , x + , x -), we compute the embeddings z r = f (x r ; θ) z + = f (x r ; θ) and z -= f (x -; θ), and use the constrastive loss [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF], combining one positive and one negative pair in a single input,

l c (z r , z + , z -) = z r -z + 2 + [m -z r -z -] 2 + , (7)
or the triplet loss [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF]

l t (z r , z + , z -) = [m + z r -z + 2 -z r -z -] 2 + , (8)
where [•] + denotes the positive part and m is a margin parameter. We also consider a weighted variant of both loss functions, where the loss is multiplied by the manifold similarity s m (x r , x + ) of the positive sample to the anchor. Thus we down-weigh the contribution of the tuples where the positive sample is too hard. Of course, given the positive and negative pools, there are many more possibilities in sampling positives and negatives and forming losses that are functions of more than two or three items [29,36,[START_REF] Bautista | Deep unsupervised similarity learning using partially ordered sets[END_REF][START_REF] Kumar | Learning local image descriptors with deep siamese and triplet convolutional networks by minimising global loss functions[END_REF][START_REF] Ustinova | Learning deep embeddings with histogram loss[END_REF][START_REF] Wu | Sampling matters in deep embedding learning[END_REF]. It is also possible to iterate our approach, updating the graph and the pools based on the current embedding space, updating the embeddings,

x r P + (x r ) NN e 3 (x r ) P -(x r ) X \ NN e 3 (x r )
Figure 2. Sample CUB200-2011 anchor images (x r ), positive images from our method (P + (x r )) and baseline (NN e 3 (x r )), and negative images from our method (P -(x r )) and baseline (X \ NN e 3 (x r )). The baseline is Euclidean nearest neighbors and non-neighbors [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF]. Positive (negative) ground-truth framed in green (red). Labels are only used for qualitative evaluation and not during training. and so on. In this case, given current parameters θ, the set Z = {f (x; θ) : x ∈ X} plays the role of Y for the following iteration. This alternating training scheme is common for methods involving a global dataset structure like a graph or a set of clusters [START_REF] Rippel | Metric learning with adaptive density discrimination[END_REF][START_REF] Bai | Semisupervised learning for convolutional neural networks via online graph construction[END_REF][START_REF] Xu | Iterative manifold embedding layer learned by incomplete data for large-scale image retrieval[END_REF]. Our idea is orthogonal to most concurrent improvements on metric learning.

Applications

We apply the proposed method to learn visual representations on two different tasks: fine-grained categorization [START_REF] Wang | Mining discriminative triplets of patches for fine-grained classification[END_REF]18] and instance-based image retrieval [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF][START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. In both cases, both the features Y and the initial model f (•, θ) are based on a pre-trained model. We assume there are no labeled images available.

Fine-grained categorization

We use the CUB200-2011 dataset [START_REF] Wah | The caltech-ucsd birds-200-2011 dataset[END_REF] comprising 200 bird species. The goal is to learn embeddings that better discriminate instances of the same class from instances of different classes. Following the setup of [36], the training set contains half (100) classes on which embedding is learned, while the rest are used for testing. Given a test query im-age, the remaining test images of the same species should be top-ranked w.r.t. Euclidean distance to the query.

All prior approaches are fully supervised and use the manually assigned labels of the training set. Our method is unsupervised, but otherwise we choose the same settings with the literature in our comparisons. In particular, we initialize the network by GoogLeNet [START_REF] Szegedy | Going deeper with convolutions[END_REF] as pre-trained on ImageNet and add a fully connected layer right after the average pooling layer, reducing the embedding dimensionality to d = 64. We perform training with the triplet loss using all training images as anchors, which is affordable due to the small size (6k images) of the training set.

Our initial features are formed by R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] on the last convolutional feature map of the pre-trained GoogLet-Net, right before the average pooling layer, aggregated over 3 input image scales and whitened. The feature set Y contains all such vectors y = g(x) for x in the entire training set X. In Figure 2 we show examples of anchors and subsets of their positive and negative pools. Despite the absence of labels and the challenges of fine-grained similarity, we achieve a very clean negative pool and a reasonably clean positive one.

Particular object retrieval

Particular object retrieval differs from bird species classification in that images are instances of the same object and not of the same (sub-)category, i.e. the similarity is even more fine-grained than in bird species. Objects are less deformable, but there is extreme diversity in viewpoint, illumination conditions, occlusion and background clutter.

Methods trained with category-level labeling do not perform well [3], while the state-of-the-art approaches use direct geometric matching [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF] or Structure-from-Motion (SfM) [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] to automatically mine matching and nonmatching image pairs. This is appropriate since the geometry of the scene is known, but the whole process assumes the existence of another computer vision system based on local descriptors, which is rather expensive [START_REF] Schonberger | From single image query to detailed 3d reconstruction[END_REF].

To be comparable to the state-of-the-art fine-tuned MAC obtained through SfM by Radenovic et al. [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF], we use similar training set and design choices. In particular, we start from the same set of 7M images, referred to as Flickr 7M in the following 2 , which is downloaded from Flickr with text tag queries. We limit the training set by randomly sampling 1M images. We initialize our network by VGG [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] as pretrained on ImageNet and we fine-tune MAC representation with contrastive loss.

Our initial features are formed by R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] on the last convolutional feature map of the pre-trained VGG network. The feature set Y contains all such vectors y = g(x) for x in the entire training set X. We sample an anchor set A and construct the complete training pool P. Anchor selection is essential here, as using all images as queries would be very expensive. Compared to [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF], our complete training pool is larger (50k vs 22k), however, we only choose 1k anchors per epoch vs 6k.

Examples of selected anchors are shown in Figure 3. They usually correspond to popular locations frequently appearing in the dataset. Examples of training pools are shown in Figure 4, comparing to a baseline where positives and negatives are Euclidean nearest neighbors and nonneighbors, respectively. The same baseline is used for comparisons in our experiments. The baseline positives contain only mild viewpoint and illumination changes, while negatives are random. On the contrary, our positives contain more challenging changes and very interesting negatives: different objects, which still look similar in one way or another. The training set variability, in terms of different objects and viewing conditions, seems a desirable property.

Implementation details

We always create graph G by considering k = 30 nearest neighbors in [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]. Exact computation takes 80min on 12 CPU threads on the 1M retrieval training set. We use the Euclidean similarity function s e (x i , x j ) = [x i x j ] 3 + and α = 0.99 following Iscen et al. [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]. In order to create the positive pool we consider 50 neighbors in [START_REF] Bautista | Deep unsupervised similarity learning using partially ordered sets[END_REF], while for the negative pool we use 100 and 10,000 neighbors in [START_REF] Bautista | CliqueCNN: Deep unsupervised exemplar learning[END_REF] for fine-grained categories and retrieval, respectively, due to the different size of the training dataset. We finally restrict the negative pool of each anchor to have 50 instances at most. All vector representations used for an image in the feature and the embedding space are 2 -normalized.

We use stochastic gradient descent with momentum for optimization. The learning rate is initialized at 10 -2 , and scaled by 0.1 every 10 epochs. The momentum parameter is 0.9. The margin m is set to 0.5 for triplet loss in finegrained categorization, and to 0.7 for contrastive loss in particular object retrieval. The batch size includes 42 triplets for fine-grained categories [36] and pairs for 5 anchors in the retrieval application [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. We train for 100 epochs on fine-grained categorization and 30 epochs on particular object retrieval experiments. 2 Images depicting buildings that are part of the Oxford5k or Paris6k test set are removed as in [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. 1. Impact of choices of anchors and pools of positive and negative examples on Recall@1 on CUB-200-2011 and mAP on Oxford5k. On CUB, all images are used as anchors, while on Oxford5K anchors are selected either at random or by the proposed method (A). The positive and negative pools are formed by either the baseline with Euclidean nearest neighbors (NN e 5 ) [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF] or our selection (P + and P -), optionally with our weighted loss (+W).

Method

Labels R@1 R@2 R@4 R@8 NMI 2. Recall@k and NMI on CUB-200-2011. All methods expect for ours and cyclic match [START_REF] Li | Unsupervised visual representation learning by graph-based consistent constraints[END_REF] use ground-truth labels during training.

Experiments

Fine-grained categorization is evaluated on CUB200-2011 [START_REF] Wah | The caltech-ucsd birds-200-2011 dataset[END_REF], where we use the training set without labels for training and then evaluate on the test set, measuring Recall@k as well as clustering quality by NMI [START_REF] Manning | Introduction to Information Retrieval[END_REF]. Particular object retrieval is evaluated by mean average precision (mAP) on a challenging and diverse set of test datasets comprising landmark and building images (Oxford5k [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris6k [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]), natural landscapes (Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]), as well as planar and 3D objects (Instre [START_REF] Wang | Instre: a new benchmark for instancelevel object retrieval and recognition[END_REF]). Large scale experiments are performed on Oxford and Paris by adding 100k distractors [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], namely Oxford105k and Paris106k respectively. We first evaluate the importance of different components of the selection strategy and then compare our method against state-of-the-art on each task.

Impact of positives, negatives, and anchors

We consider the unsupervised approach proposed by Hadsell et al. [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF] as a baseline method. It sets positives to be the 5 nearest neighbors with Euclidean distance. All other elements are considered negatives out of which we randomly draw the negative pool of an anchor. In this case, hard negative mining per epoch is impossible and random choice is the only choice. We present the results in Table Table 3. mAP on particular object retrieval datasets. We compare VGG as pre-trained on ImageNet, the fine-tuned network of Radenovic et al. [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF], and our fine-tuned one. Fine-tuning is always performed for MAC, but at testing we evaluate both global MAC and regional R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] representations.

without any supervision, while the weighted loss consistently helps. Furthermore, we observe that our hard negatives are beneficial and necessary, while our anchors are essential for the large scale training set. Given popular anchors, even simple nearest neighbors work well as positives. However, our harder positives further improve. CUB's annotation allows us to measure the true positive and true negative rate in our positive and negative pools. These measurements are 40% and 96%, respectively. Additionally, we exploit the labels and train with a positive (negative) oracle, where we replace our positive (resp. negative) pool with one based on labels, yielding 46.7 (resp. 36.5) Recall@1. This shows that our hard positives with weighting are almost as good as true positives and that our hard negatives are better than hard annotated negatives. The latter is due to errors in annotation of CUB dataset, quantified to 4.4% [START_REF] Van Horn | Building a bird recognition app and large scale dataset with citizen scientists: The fine print in fine-grained dataset collection[END_REF]. In this case, hard negative mining frequently finds false negative examples, which are known to cause training failure [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF].

Comparisons on fine-grained categories

To our knowledge there is no other unsupervised method that evaluates on CUB200-2011 dataset. We evaluate the unsupervised approach of Li et al. [START_REF] Li | Unsupervised visual representation learning by graph-based consistent constraints[END_REF] by constructing the same graph as in our method, then using the provided code to construct the positive/negative pool and finally training the same way as in our method. We also compare to supervised methods that use ground-truth labels on the training set, but otherwise an identical experimental setup. As shown in in Table 2, our method competes or even outperforms fully supervised methods. We also outperform the only unsupervised competitor. Although their true positive rate is higher (76%), their positive pairs are mostly extremely similar and not challenging enough for training. Note that there are better-performing methods in the literature with sophisticated sampling schemes [START_REF] Wu | Sampling matters in deep embedding learning[END_REF], which can be complementary to ours.

Comparisons on retrieval

We initialize by VGG as pre-trained on ImageNet and fine-tune using MAC representation. At testing, the fine-tuned network is evaluated with both global MAC and regional R-MAC representations [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. This is the same process as [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF], which makes it comparable in this respect, although the training set and sampling pool sizes are not the same as discussed in section 4.2.

Descriptor whitening is known to be essential for MAC and R-MAC. We follow the common practice in the literature and perform unsupervised PCA whitening [23] for the pre-trained networks, and supervised LDA-based whitening for the fine-tuned networks, learned on a subset of Flickr 7M. In particular, as supervision we use SfM labels for the network of Radenovic et al. [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF], and matching pairs consisting of NN m 50 per anchor for our method. As shown in Table 3, we improve over the pre-trained network on all test sets. Moreover, we outperform [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] with only one exception on Oxford5k. Remarkably, we perform better even on building or landmark oriented test sets, while their method specifically favors this kind of images. With our training pool being more diverse, we improve on Holidays and Instre test sets, where [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] shows little improvement or is even inferior to the pre-trained network.

Conclusions

In this work, we depart from using discrete category level labeling in order to learn fine grained similarity. Not only we avoid the expensive or nearly impossible manual annotation, but also do not restrict the problem to supervised classification. Our unsupervised and manifold-aware sampling of training data is applied to perform metric learning. The learning attracts points that lie on the same manifold and repels points on different manifolds. The method is conceptually simple and applicable with standard contrastive and triplet loss. It is shown to be effective for fine-grained categorization and particular object retrieval, competing or surpassing fully supervised approaches.

Figure 1 .

 1 Figure 1. Given an anchor point (black) and its k nearest Euclidean (NN e k ) and manifold (NN m k ) neighbors in a dataset, we choose positive samples as NN m k \ NN e k , and negative as NN e k \ NN m k . Data is unlabeled and the selection is fully unsupervised, including anchors.

Figure 3 .

 3 Figure 3. Examples of anchor images selected by the proposed method for the image retrieval application. Random samples from the top 100 (1000) anchors are shown in the top (bottom) row according to the node importance.

Figure 4 .

 4 Figure 4. Sample anchor images (x r ), positive images from our method (P + (x r )) and baseline (NN e3 (x r )), and negative images from our method (P -(x r )) and baseline (X \ NN e 3 (x r )). The baseline is Euclidean nearest neighbors and non-neighbors[START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF].

  . Our method improves the pre-trained network in both tasks

	Method	Representation Labels	Oxford5k Oxford105k Paris6k Paris106k Holidays Instre
	Pre-trained [58]		ImageNet	58.5	50.3	73.0	59.0	79.4	48.5
	CNN from BoW [42]	MAC	SfM	79.7	73.9	82.4	74.6	81.4	48.5
	Ours		No	78.7	74.3	83.1	75.6	82.6	55.5
	Pre-trained [58]		ImageNet	68.0	61.0	76.6	72.1	87.0	55.6
	CNN from BoW [42]	R-MAC	SfM	77.8	70.1	84.1	76.8	84.4	47.7
	Ours		No	78.2	72.6	85.1	78.0	87.5	57.7

In fact, se can be any symmetric function but is only a function of two elements of Y; while sm is a function of two elements in Y but also of the entire set Y .

Acknowledgments The authors were supported by the MSMT LL1303 ERC-CZ grant.