Relja Arandjelović
email: relja.arandjelovic@inria.fr

Petr Gronat
email: petr.gronat@inria.fr

Akihiko Torii
email: torii@ctrl.titech.ac.jp

Tomas Pajdla
email: pajdla@cvut.cz

Josef Sivic
email: josef.sivic@inria.fr

NetVLAD: CNN architecture for weakly supervised place recognition

We tackle the problem of large scale visual place recognition, where the task is to quickly and accurately recognize the location of a given query photograph. We present the following four principal contributions. First, we develop a convolutional neural network (CNN) architecture that is trainable in an end-to-end manner directly for the place recognition task. The main component of this architecture, NetVLAD, is a new generalized VLAD layer, inspired by the "Vector of Locally Aggregated Descriptors" image representation commonly used in image retrieval. The layer is readily pluggable into any CNN architecture and amenable to training via backpropagation. Second, we create a new weakly supervised ranking loss, which enables end-to-end learning of the architecture's parameters from images depicting the same places over time downloaded from Google Street View Time Machine. Third, we develop an efficient training procedure which can be applied on very large-scale weakly labelled tasks. Finally, we show that the proposed architecture and training procedure significantly outperform non-learnt image representations and off-the-shelf CNN descriptors on challenging place recognition and image retrieval benchmarks.

INTRODUCTION

V ISUAL place recognition has received a significant amount of attention in the past years both in computer vision [1], [2], [3], [4], [5], [6], [7], [8], [9], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF] and robotics communities [START_REF] Cummins | FAB-MAP: Probabilistic localization and mapping in the space of appearance[END_REF], [START_REF]Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF], [START_REF] Mcmanus | Shady dealings: Robust, long-term visual localisation using illumination invariance[END_REF], [START_REF] Maddern | Towards robust night and day place recognition using visible and thermal imaging[END_REF], [START_REF] Sunderhauf | Place recognition with ConvNet landmarks: Viewpoint-robust, condition-robust, training-free[END_REF] motivated by, e.g., applications in autonomous driving [START_REF] Mcmanus | Shady dealings: Robust, long-term visual localisation using illumination invariance[END_REF], augmented reality [START_REF] Middelberg | Scalable 6-DOF localization on mobile devices[END_REF] or geo-localizing archival imagery [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF].

The place recognition problem, however, still remains extremely challenging. How can we recognize the same street-corner in the entire city or on the scale of the entire country despite the fact it can be captured in different illuminations or change its appearance over time? The fundamental scientific question is what is the appropriate representation of a place that is rich enough to distinguish similarly looking places yet compact to represent entire cities or countries.

The place recognition problem has been traditionally cast as an instance retrieval task, where the query image location is estimated using the locations of the most visually similar images obtained by querying a large geotagged database [1], [2], [3], [8], [9], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. Each database image is represented using local invariant features [START_REF] Tuytelaars | Local invariant feature detectors: A survey[END_REF] such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] that are aggregated into a fixed length vector representation for the entire image such as bag-ofvisual-words [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], VLAD [START_REF] Arandjelović | All about VLAD[END_REF], [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] or Fisher vector [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF], [START_REF] Jégou | Aggregating local images descriptors into compact codes[END_REF]. The resulting representation is then usually compressed and efficiently indexed [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. The image database can be further augmented by 3D structure that enables recovery of accurate camera pose [4], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Li | Worldwide pose estimation using 3D point clouds[END_REF].

In the last few years, convolutional neural networks (CNNs) [START_REF] Lecun | Backpropagation applied to handwritten zip code recognition[END_REF], [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] have emerged as powerful image representations for various category-level recognition tasks such as object classification [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF], [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF], [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], [START_REF] Szegedy | Going deeper with convolutions[END_REF], scene recognition [START_REF] Zhou | Learning deep features for scene recognition using places database[END_REF] or object detection [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]. The basic principles of CNNs are known from 80's [START_REF] Lecun | Backpropagation applied to handwritten zip code recognition[END_REF], [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] and the recent successes are a combination of advances in GPU-based computation power together with large labelled image datasets [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF]. It has been shown that the trained representations are, to some extent, transferable between recognition tasks [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF], [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], [START_REF] Donahue | DeCAF: A deep convolutional activation feature for generic visual recognition[END_REF], [START_REF] Sermanet | OverFeat: Integrated recognition, localization and detection using convolutional networks[END_REF], [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF], and direct application of CNN representations trained for object classification [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF] as black-box descriptor extractors has brought some improvements in performance on instance-level recognition tasks [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF], [START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF], [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF], [START_REF] Mohedano | Bags of local convolutional features for scalable instance search[END_REF]. In this work we investigate whether the performance can be further improved by CNN representations developed and trained directly for place recognition. This requires addressing the following four main challenges: First, what is a good CNN architecture for place recognition? Second, how to gather sufficient amount of annotated data for the training? Third, how can we train the developed architecture in an end-to-end manner tailored for the place recognition task? Fourth, how to perform computationally efficient training in order to scale up to very large datasets? To address these challenges, we bring the following four innovations.

First, building on the lessons learnt from the current well performing hand-engineered object retrieval and place recognition pipelines [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Arandjelović | All about VLAD[END_REF], [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF], [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF], we develop a convolutional neural network architecture for place recognition that aggregates midlevel (conv5) convolutional features extracted from the entire image into a compact fixed length vector representation amenable to efficient indexing. To achieve this, we design a new trainable generalized VLAD layer, NetVLAD, inspired by the Vector of Locally Aggregated Descriptors (VLAD) representation [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] that has shown excellent performance in image retrieval and place recognition. The layer is readily pluggable into any CNN architecture and amenable to training via backpropagation. The resulting aggregated representation is then compressed using Principal Component Analysis (PCA) to obtain the final compact descriptor of the image.

Second, to train the architecture for place recognition, we gather a large dataset of multiple panoramic images depicting the same place from different viewpoints over time from the Google Street View Time Machine. Such data is available for vast areas of the world, but provides only weak form of supervision: we know the two panoramas are captured at approximately similar positions based on their (noisy) GPS but we don't know which parts of the panoramas depict the same parts of the scene.

Third, we create a new loss function, which enables end-toend learning of the architecture's parameters, tailored for the place recognition task from the weakly labelled Time Machine imagery. The loss function is also more widely applicable to other ranking tasks where large amounts of weakly labelled data are available.

Fourth, we develop an efficient learning procedure which can be applied on very large-scale weakly labelled tasks. It requires only a fraction of the computational time of a naive implementation thanks to improved data efficiency through hard negative mining, combined with an effective use of caching.

The resulting representation is robust to changes in viewpoint and lighting conditions, while simultaneously learns to focus on the relevant parts of the image such as the building fac ¸ades and the skyline, while ignoring confusing elements such as cars and people that may occur at many different places. We show that the proposed architecture and training procedure significantly outperform non-learnt image representations and off-the-shelf CNN descriptors on challenging place recognition and image retrieval benchmarks.

Related work

While there have been many improvements in designing better image retrieval [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], [START_REF] Arandjelović | All about VLAD[END_REF], [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF], [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF], [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF], [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], [START_REF] Chum | Total recall II: Query expansion revisited[END_REF], [START_REF] Delhumeau | Revisiting the VLAD image representation[END_REF], [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], [START_REF]On the burstiness of visual elements[END_REF], [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF], [START_REF] Mikulik | Learning a fine vocabulary[END_REF], [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF], [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], [START_REF] Simonyan | Descriptor learning using convex optimisation[END_REF], [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF], [START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF], [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF] and place recognition [2], [3], [4], [5], [6], [7], [8], [9], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Cummins | FAB-MAP: Probabilistic localization and mapping in the space of appearance[END_REF], [START_REF]Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF], [START_REF] Mcmanus | Shady dealings: Robust, long-term visual localisation using illumination invariance[END_REF], [START_REF] Maddern | Towards robust night and day place recognition using visible and thermal imaging[END_REF], [START_REF] Sunderhauf | Place recognition with ConvNet landmarks: Viewpoint-robust, condition-robust, training-free[END_REF] systems, not many works have performed learning for these tasks. All relevant learning-based approaches fall into one or both of the following two categories: (i) learning for an auxiliary task (e.g. some form of distinctiveness of local features [2], [9], [START_REF] Cummins | FAB-MAP: Probabilistic localization and mapping in the space of appearance[END_REF], [START_REF] Jégou | A contextual dissimilarity measure for accurate and efficient image search[END_REF], [START_REF] Qin | Hello neighbor: accurate object retrieval with k-reciprocal nearest neighbors[END_REF], [START_REF] Qin | Query adaptive similarity for large scale object retrieval[END_REF], [START_REF] Zepeda | Exemplar SVMs as visual feature encoders[END_REF]), and (ii) learning on top of shallow hand-engineered descriptors that cannot be finetuned for the target task [2], [6], [7], [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF], [START_REF] Qin | Learning to rank bagof-word histograms for large-scale object retrieval[END_REF]. Both of these are in spirit opposite to the core idea behind deep learning that has provided a major boost in performance in various recognition tasks: end-to-end learning. We will indeed show in section 6.2 that training representations directly for the end-task, place recognition, is crucial for obtaining good performance.

Numerous works concentrate on learning better local descriptors or metrics to compare them [START_REF] Mikulik | Learning a fine vocabulary[END_REF], [START_REF] Simonyan | Descriptor learning using convex optimisation[END_REF], [START_REF] Winder | Picking the best DAISY[END_REF], [START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF], [START_REF] Makadia | Feature tracking for wide-baseline image retrieval[END_REF], [START_REF] Bergamo | Leveraging structure from motion to learn discriminative codebooks for scalable landmark classification[END_REF], [START_REF] Qin | Quantized kernel learning for feature matching[END_REF], [START_REF] Simo-Serra | Fracking deep convolutional image descriptors[END_REF], [START_REF] Paulin | Local convolutional features with unsupervised training for image retrieval[END_REF], [START_REF] Yi | LIFT: Learned invariant feature transform[END_REF], but even though some of them show results on image retrieval, the descriptors are learnt on the task of matching local image patches, and not directly with image retrieval in mind. Some of them also make use of hand-engineered features to bootstrap the learning, i.e. to provide noisy training data [START_REF] Mikulik | Learning a fine vocabulary[END_REF], [START_REF] Simonyan | Descriptor learning using convex optimisation[END_REF], [START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF], [START_REF] Makadia | Feature tracking for wide-baseline image retrieval[END_REF], [START_REF] Paulin | Local convolutional features with unsupervised training for image retrieval[END_REF].

Several works have investigated using CNN-based features for image retrieval. These include treating activations from certain layers directly as descriptors by concatenating them [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Babenko | Neural codes for image retrieval[END_REF], or by pooling [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF], [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF], [START_REF] Mohedano | Bags of local convolutional features for scalable instance search[END_REF]. However, none of these works actually train the CNNs for the task at hand, but use CNNs as black-box descriptor extractors. One exception is the work of Babenko et al. [START_REF] Babenko | Neural codes for image retrieval[END_REF] in which the network is finetuned on an auxiliary task of classifying 700 landmarks. However, again the network is not trained directly on the target retrieval task. Very recent works [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], published after the first version of this paper [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF], train CNNs end-to-end for image retrieval by making use of image correspondences obtained from structurefrom-motion models, i.e. they rely on pre-existing image retrieval pipelines based on precise matching of RootSIFT descriptors, spatial verification and bundle adjustment.

Weyand et al. [START_REF] Weyand | PlaNet -Photo geolocation with convolutional neural networks[END_REF] proposed a CNN-based method for geolocalization by partitioning the Earth into cells and treating place recognition as a classification task. While providing impressive rough city/country level estimates of where a photo is taken, their method is not capable of providing several-meter accuracy place recognition that we consider here, as their errors are measured in tens and hundreds of kilometres. Finally, [START_REF] Kendall | PoseNet: A convolutional network for real-time 6-DOF camera relocalization[END_REF] and [START_REF] Lin | Learning deep representations for ground-to-aerial geolocalization[END_REF] performed end-to-end learning for different but related tasks of ground-toaerial matching [START_REF] Lin | Learning deep representations for ground-to-aerial geolocalization[END_REF] and camera pose estimation [START_REF] Kendall | PoseNet: A convolutional network for real-time 6-DOF camera relocalization[END_REF].

METHOD OVERVIEW

Building on the success of current place recognition systems (e.g. [1], [2], [3], [4], [5], [8], [9], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF]), we cast place recognition as image retrieval. The query image with unknown location is used to visually search a large geotagged image database, and the locations of top ranked images are used as suggestions for the location of the query. This is generally done by designing a function f which acts as the "image representation extractor", such that given an image I i it produces a fixed size vector f (I i ). The function is used to extract the representations for the entire database {I i }, which can be done offline, and to extract the query image representation f (q), done online. The visual search is performed by finding the nearest database image to the query, either exactly or through fast approximate nearest neighbour search, by sorting images based on the Euclidean distance d(q, I i ) between f (q) and f (I i ).

While previous works have mainly used hand-engineered image representations (e.g. f (I) corresponds to extracting SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], followed by pooling into a bag-of-words vector [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] or a VLAD vector [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]), here we propose to learn the representation f (I) in an end-to-end manner, directly optimized for the task of place recognition. The representation is parametrized with a set of parameters θ and we emphasize this fact by referring to it as f θ (I). It follows that the Euclidean distance d θ (I i , I j ) = f θ (I i )-f θ (I j ) also depends on the same parameters. An alternative setup would be to learn the distance function itself, but here we choose to fix the distance function to be Euclidean distance, and to pose our problem as the search for the explicit feature map f θ which works well under the Euclidean distance.

In section 3 we describe the proposed representation f θ based on a new deep convolutional neural network architecture inspired by the compact aggregated image descriptors for instance retrieval. In section 4 we describe a method to learn the parameters θ of the network in an end-to-end manner using weakly supervised training data from the Google Street View Time Machine.

DEEP ARCHITECTURE FOR PLACE RECOGNITION

This section describes the proposed CNN architecture f θ , guided by the best practices from the image retrieval community. Most image retrieval pipelines are based on (i) extracting local descriptors, which are then (ii) pooled in an orderless manner. The motivation behind this choice is that the procedure provides significant robustness to translation and partial occlusion. Robustness to lighting and viewpoint changes is provided by the descriptors themselves.

In order to learn the representation end-to-end, we design a CNN architecture that mimics this standard retrieval pipeline in an unified and principled manner with differentiable modules, as shown in figure 2. For step (i), we crop the CNN at the last convolutional layer and view it as a dense descriptor extractor. This has been observed to work well for instance retrieval [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] and texture recognition [START_REF] Cimpoi | Deep filter banks for texture recognition and segmentation[END_REF]. Namely, the output of the last convolutional layer is a H ×W ×D map which can be considered as a set of D-dimensional descriptors extracted at H × W spatial locations. For step (ii) we design a new pooling layer inspired by the Vector of Locally Aggregated Descriptors (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] that pools extracted descriptors into a fixed image representation and its parameters are learnable via back-propagation. We call this new pooling layer "NetVLAD" layer and describe it in the next section.

NetVLAD: A Generalized VLAD layer (f V LAD )

Vector of Locally Aggregated Descriptors (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] is a popular descriptor pooling method for both instance level retrieval [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and image classification [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF]. It captures information about the statistics of local descriptors aggregated over the image. Whereas bag-of-visual-words [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] aggregation keeps counts of visual words, VLAD stores the sum of residuals (difference vector between the descriptor and its corresponding cluster centre) for each visual word.

Formally, given N D-dimensional local image descriptors {x i } as input, and K cluster centres ("visual words") {c k } as VLAD parameters, the output VLAD image representation V is D × K-dimensional. For convenience we will write V as a D × K matrix, but this matrix is reshaped into a vector and, after normalization, used as the image representation. The (j, k) element of V is computed as follows:

V (j, k) = N i=1 a k (x i ) (x i (j) -c k (j)) , (1)
where x i (j) and c k (j) are the j-th dimensions of the i-th descriptor and k-th cluster centre, respectively. a k (x i ) denotes the membership of the descriptor x i to k-th visual word, i.e. it is 1 if cluster c k is the closest cluster to descriptor x i and 0 otherwise. Intuitively, each D-dimensional column k of V records the sum of residuals (x ic k ) of descriptors which are assigned to cluster c k . The matrix V is then L2-normalized column-wise (intra-normalization [START_REF] Arandjelović | All about VLAD[END_REF]), reshaped into a vector, and finally L2normalized in its entirety [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF].

In order to profit from years of wisdom produced in image retrieval, we propose to mimic VLAD in a CNN framework and design a trainable generalized VLAD layer, NetVLAD. The result is a powerful image representation trainable end-to-end on the target task (in our case place recognition). To construct a layer amenable to training via backpropagation, it is required that the layer's operation is differentiable with respect to all its parameters and the input. Hence, the key challenge is to make the VLAD pooling differentiable, which we describe next.

The source of discontinuities in VLAD is the hard assignment a k (x i ) of descriptors x i to clusters centres c k . To make this operation differentiable, we replace it with soft assignment of descriptors to multiple clusters

āk (x i ) = e -α xi-c k 2 k e -α xi-c k 2 , (2)
which assigns the weight of descriptor x i to cluster c k according to their proximity, but relative to proximities to other cluster centres. āk (x i ) ranges between 0 and 1, with the highest weight assigned to the closest cluster centre. α is a parameter (positive constant) that controls the decay of the response with the magnitude of the distance. Note that for α → +∞ this setup replicates the original VLAD exactly as āk (x i ) for the closest cluster would be 1 and 0 otherwise. By expanding the squares in (2), it is easy to see that the term e -α xi 2 cancels between the numerator and the denominator resulting in a soft-assignment of the following form

āk (x i ) = e w T k xi+b k k e w T k xi+b k , (3)
where vector w k = 2αc k and scalar b k = -α c k 2 . The final form of the NetVLAD layer is obtained by plugging the softassignment (3) into the VLAD descriptor (1) resulting in

V (j, k) = N i=1 e w T k xi+b k k e w T k xi+b k (x i (j) -c k (j)) , (4)
where {w k }, {b k } and {c k } are sets of trainable parameters for each cluster k. Similarly to the original VLAD descriptor, the NetVLAD layer aggregates the first order statistics of residuals (x ic k ) in different parts of the descriptor space weighted by the soft-assignment āk (x i ) of descriptor x i to cluster k. Note however, that the NetVLAD layer has three independent sets of parameters {w k }, {b k } and {c k }, compared to just {c k } of the original VLAD. This enables greater flexibility than the original VLAD, as explained in figure 3. Decoupling {w k , b k } from {c k } has been proposed in [START_REF] Arandjelović | All about VLAD[END_REF] as a means to adapt the VLAD to a new dataset. All parameters of NetVLAD are learnt for the specific task in an end-to-end manner.

As illustrated in figure 2, the NetVLAD layer can be visualized as a meta-layer that is further decomposed into basic CNN layers + Fig. 3. Benefits of supervised VLAD. Red and green circles are local descriptors from two different images, assigned to the same cluster (Voronoi cell). Under the VLAD encoding, their contribution to the similarity score between the two images is the scalar product (as final VLAD vectors are L2-normalized) between the corresponding residuals, where a residual vector is computed as the difference between the descriptor and the cluster's anchor point. The anchor point c k can be interpreted as the origin of a new coordinate system local to the the specific cluster k. In standard VLAD, the anchor is chosen as the cluster centre (×) in order to evenly distribute the residuals across the database. However, in a supervised setting where the two descriptors are known to belong to images which should not match, it is possible to learn a better anchor ( ) which causes the scalar product between the new residuals to be small.

connected up in a directed acyclic graph. First, note that the first term in equation ( 4) is a soft-max function σ k (z) = exp(z k ) k exp(z k ) . Therefore, the soft-assignment of the input array of descriptors x i into K clusters can be seen as a two step process: (i) a convolution with a set of K filters {w k } that have spatial support 1 × 1 and biases {b k }, producing the output

s k (x i ) = w T k x i + b k ;
(ii) the convolution output is then passed through the soft-max function σ k to obtain the final soft-assignment āk (x i ) that weights the different terms in the aggregation layer that implements equation ( 4). The output after normalization is a (K × D) × 1 descriptor.

Relations to other methods. Other works have proposed to pool CNN activations using VLAD or Fisher Vectors (FV) [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Cimpoi | Deep filter banks for texture recognition and segmentation[END_REF], but do not learn the VLAD/FV parameters nor the input descriptors. The most related method to ours is the one of Sydorov et al. [START_REF] Sydorov | Deep fisher kernels -end to end learning of the fisher kernel GMM parameters[END_REF], which proposes to learn FV parameters jointly with an SVM for the end classification objective. However, in their work it is not possible to learn the input descriptors as they are handengineered (SIFT), while our VLAD layer is easily pluggable into any CNN architecture as it is amenable to backpropagation. "Fisher Networks" [START_REF] Simonyan | Deep Fisher networks for large-scale image classification[END_REF] stack Fisher Vector layers on top of each other, but the system is not trained end-to-end, only hand-crafted features are used, and the layers are trained greedily in a bottomup fashion. Finally, our architecture is also related to bilinear networks [START_REF] Lin | Bilinear CNN models for fine-grained visual recognition[END_REF], recently developed for a different task of finegrained category-level recognition.

Max pooling (f max ). We also experiment with Max-pooling of the D-dimensional features across the H × W spatial locations, thus producing a D-dimensional output vector, which is then L2normalized. Both of these operations can be implemented using standard layers in public CNN packages. This setup mirrors the method of [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF], but a crucial difference is that we will learn the representation (section 4) while [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] only use pretrained networks. Results will show (section 6.2) that simply using CNNs off-the-shelf [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF] results in poor performance, and that training for the end-task is crucial. Additionally, VLAD will prove itself to be superior to the Max-pooling baseline.

LEARNING FROM TIME MACHINE DATA

In the previous section we have designed a new CNN architecture as an image representation for place recognition. Here we describe how to learn its parameters in an end-to-end manner for the place recognition task. The two main challenges are: (i) how to gather enough annotated training data and (ii) what is the appropriate loss for the place recognition task. To address theses issues, we will first show that it is possible to obtain large amounts of weakly labelled imagery depicting the same places over time from the Google Street View Time Machine. Second, we will design a new weakly supervised triplet ranking loss that can deal with the incomplete and noisy position annotations of the Street View Time Machine imagery. The details are below.

Weak supervision from the Time Machine. We propose to exploit a new source of data -Google Street View Time Machine -which provides multiple street-level panoramic images taken at different times at close-by spatial locations on the map. As will be seen in section 6.2, this novel data source is precious for learning an image representation for place recognition. As shown in figure 4, the same locations are depicted at different times and seasons, providing the learning algorithm with crucial information it can use to discover which features are useful or distracting, and what changes should the image representation be invariant to, in order to achieve good place recognition performance.

The downside of the Time Machine imagery is that it provides only incomplete and noisy supervision. Each Time Machine panorama comes with a GPS tag giving only its approximate location on the map (GPS accuracy of Google Street View has been estimated to 7-15 meters by [8]), which can be used to identify close-by panoramas but does not provide correspondences between parts of the depicted scenes. In detail, as the test queries are perspective images from camera phones, each panorama is represented by a set of perspective images sampled evenly in different orientations and two elevation angles [2], [3], [6], [8].

Each perspective image is labelled with the GPS position of the source panorama. As a result, two geographically close perspective images do not necessarily depict the same objects since they could be facing different directions or occlusions could take place (e.g. the two images are around a corner from each other), etc. Thus, for a given training query q, the GPS information can only be used as a source of (i) potential positives {p q i }, i.e. images that are geographically close to the query, and (ii) definite negatives {n q j }, i.e. images that are geographically far from the query. 1 Weakly supervised triplet ranking loss. We wish to learn a representation f θ that will optimize place recognition performance. That is, for a given test query image q, the goal is to rank a database image I i * from a close-by location higher than all other far away images I i in the database. In other words, we wish the Euclidean distance d θ (q, I) between the query q and a close-by image I i * to be smaller than the distance to far away images in the database I i , i.e. d θ (q, I i * ) < d θ (q, I i ), for all images I i further than a certain distance from the query on the map. Next we show how this requirement can be translated into a ranking loss between training triplets {q, I i * , I i }.

From the Google Street View Time Machine data, we obtain a training dataset of tuples (q, {p q i }, {n q j }), where for each training query image q we have a set of potential positives {p q i } and the set of definite negatives {n q j }. The set of potential positives contains at least one positive image that should match the query, but we do not know which one. To address this ambiguity, we propose to identify the best matching potential positive image p q i * p q i * = argmin

p q i d θ (q, p q i ) (5)
1. Note that even faraway images can depict the same object. For example, the Eiffel Tower can be visible from two faraway locations in Paris. But, for the purpose of localization we consider in this paper such image pairs as negative examples because they are not taken from the same place.

for each training tuple (q, {p q i }, {n q j }). The goal then becomes to learn an image representation f θ so that distance d θ (q, p q i * ) between the training query q and the best matching potential positive p q i * is smaller than the distance d θ (q, n q j ) between the query q and all negative images n q j : d θ (q, p q i * ) < d θ (q, n q j ), ∀j.

Based on this intuition we define a weakly supervised ranking loss L θ for a training tuple (q, {p q i }, {n q j }) as

L θ = j l min i d 2 θ (q, p q i ) + m -d 2 θ (q, n q j ) , ( 7
)
where l is the hinge loss l(x) = max(x, 0), and m is a constant parameter giving the margin. Note that equation ( 7) is a sum of individual losses for negative images n q j . For each negative, the loss l is zero if the distance between the query and the negative is greater by a margin than the distance between the query and the best matching positive. Conversely, if the margin between the distance to the negative image and to the best matching positive is violated, the loss is proportional to the amount of violation. Note that the above loss is related to the commonly used triplet loss [START_REF] Schultz | Learning a distance metric from relative comparisons[END_REF], [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], [START_REF] Wang | Learning fine-grained image similarity with deep ranking[END_REF], [START_REF] Schroff | FaceNet: A unified embedding for face recognition and clustering[END_REF], but adapted to our weakly supervised scenario using a formulation (given by equation ( 5)) similar to multiple instance learning [START_REF] Foulds | A review of multi-instance learning assumptions[END_REF], [START_REF] Kotzias | Deep multi-instance transfer learning[END_REF], [START_REF] Viola | Multiple instance boosting for object detection[END_REF].

EFFICIENT LARGE-SCALE TRAINING

In this section we discuss how to practically implement the weakly supervised learning method outlined in the previous section. Namely, we show that the naive implementation is prohibitively slow when training with large amounts of data, and present a training procedure which uses hard negative mining and caching to alleviate inefficiencies. We further improve upon this method by query clustering in order to share computations across training tuples. While down-scaling images can be used to make the training faster as the forward and backward passes require fewer computations, two points should be noted: (i) our speedups are complementary to any improvements made to the speed of forward and backward passes, (ii) down-sampling images is not recommended as it causes a large decrease in recognition performance [START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF], [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF].

Efficient hard negative mining with caching

A naive implementation of weakly supervised training from section 4 with Stochastic Gradient Descent (SGD) involves constructing training tuples (q, {p q i }, {n q j }) by randomly sampling training queries and adding their respective potential positives and definite negatives to the tuple. In order to compute the value of the loss and the derivative of the loss with respect to network parameters θ, needed to perform learning via back propagation, it is necessary to first obtain the image representations of all the images in the tuple, which involves executing the forward pass of the network for each image.

Inefficiencies of the naive approach. It is clearly intractable to include all the negatives in the tuple, as then the tuple would contain all the images in the training set. SGD would require recomputation of image representations for the entire set, which would be extremely inefficient. A commonly used straight forward solution is to simply randomly sample a set of negatives for the query each epoch2 . However, a problem occurs in the case when there is a very large number of negatives and the image representation is "relatively good", but still far from its potential, so that most of the negatives are "easy". In this case, most of the negatives do not violate the margin and yield zero loss (equation ( 7)), causing zero gradients of the loss with respect to the parameters θ, in turn causing no updates to be made to θ. This leads to a vast waste of computational resources as most of the training time is spent on computing the image representations to evaluate the loss, only to find that the margin has not been violated and that the tuple does not provide useful information for training. This is a real problem -for example, a simple baseline image representation, which performs Max pooling on top of a network pretrained on ImageNet, when searching in a database of 80k images, can retrieve a correct positive within the top 25 retrievals for more than 75% of the queries. While this performance is far from good (as will be seen in section 6.2), it means that for 75% of the queries, a randomly sampled negative is extremely unlikely (less than 25 out of 80k, i.e. 0.03%) to be ranked higher than the best positive, and therefore at least 75% of the computation is wasted because it causes no updates to the parameters.

Hard negative mining. We use hard negative mining [START_REF] Rowley | Neural network-based face detection[END_REF], [START_REF] Dalal | Histogram of Oriented Gradients for Human Detection[END_REF], [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] to solve this problem, namely, the negative set {n q j } is compiled out of 10 hardest negatives for the query q, where the "hardness" of a negative is naturally measured as its contribution to the loss (7), i.e. how much it violates the margin. A natural question arises -how to choose these hard negatives? They can be precomputed once before training begins and the same hard negatives can be used throughout the training. We found that this simple strategy does not perform well as the network quickly learns how to solve the originally hard cases, without departing much from the initial network. Mixing the hard negatives with random negatives also falls short as, again, the original hard negatives are quickly solved and the method degenerates to the naive approach of random negative sampling. Therefore, we propose to keep track and update the current hardest negatives for each query. The negative set {n q j } is compiled out of the 10 hardest negatives from a pool of (i) 1000 randomly sampled negatives and (ii) 10 hardest negatives from the previous epoch for query q.

The large number of randomly sampled negatives is required in order to bring sufficient variability into the negative pool. However, this yields the second inefficiency -at every step of SGD, to find the 10 hardest negatives, one still needs to compute 1010 image representations for the negative pool from which the hardest negatives are selected. Even for efficient GPU implementations, performing thousands of forward passes on full-resolution images at each SGD step creates a large computational bottleneck. Caching. To address this issue, we introduce caching -image representations are computed for the entire training query and database sets, and are cached for a certain amount of time. The hard negative mining then uses these cached but slightly stale representations to obtain the 10 hardest examples and the forward and backward passes are only performed on these 10, compared to the original 1010, thus providing a huge computational saving. Furthermore, we also use the cached representations to select the best potential positive (equation ( 5)) as the number of potential positives for a query can also be relatively large (e.g. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF].

However, it is important to recompute the cached representations every once in a while. We have observed slow convergence if the cache is fixed for too long as the network quickly learns to be better than the fixed cache and then wastes time overfitting it. We found that recomputing the cached representations every 500 to 1000 training queries yields a good trade-off between epoch duration, convergence speed and quality of the solution. As described in section 6.1, we half the learning rate every 5 epochs -this causes the cached representations to change less rapidly, so we half the recomputation frequency every 5 epochs as well. Computational complexity. Next, we compare the computational complexity of our methods. Let N , N q , N n,r , N n,h and N p be the number of training database images, queries, random negatives, hard negatives, and average number of potential positives per query, respectively, and N r the number of queries between the cache recomputation. Typical values of these quantities for our training datasets (table 1) and parameter choices are: N = 80k, N q = 8k, N n,r = 1000, N n,h = 10, N p = 50 and N r = 500.

The main computational cost for the training is the execution of the forward and backward passes through the network, the former computing the image representation and the latter being used for network parameter updates. The speed of the forward and the backward pass is fairly comparable so we express the computational complexity of a learning method in terms of the combined number of times that the forward and the backward passes have to be executed in an epoch.

The number of backward passes, N backward , is constant across all methods. For each query, it is necessary to perform a backward pass on the query, best potential positive, and violating hardest negatives (the number of which is upper bounded by N n,h ), i.e. the backward pass is computed at most N backward times in an epoch, where N backward equals:

N backward = N q × (1 + 1 + N n,h ) (8)
For typical values, N backward = 96k. Without caching (hard+nocache), for each query, the forward pass has to be executed for the query, all its potential positives, random negatives and current hard negatives, i.e. a total number of times is:

N hard+nocache forward = N q × (1 + N p + N n,r + N n,h ) (9)
With caching (hard+cache), where the image representations are recomputed every N r queries, i.e. N q /N r times in an epoch, the number of times the forward pass needs to be executed is:

N hard+cache forward = N q /N r × N + N q × (1 + 1 + N n,h ) (10)
Clearly, the relative speed of hard+cache versus hard+nocache depends on the characteristics of the training data and the parameter settings, but for our typical values listed above, hard+nocache requires N hard+nocache forward + N backward = 8.6 million computations, while hard+cache this number drops to N hard+cache forward + N backward = 1.5 million, giving a 5.7x speedup. While hard+cache takes 19 hours of training per epoch on a single GPU 3 (base network: VGG-16), hard+nocache is impractical for our purposes as it would require almost 5 days for a single epoch.

Scaling up further: query clustering

The techniques presented in the previous section are sufficient for our purposes when training sets include an order of 100k images; all the results (section 6.2) are obtained by using efficient hard negative mining with caching (hard+cache). However, scaling up to even large datasets is desired, as well as the ability to train networks faster even for the training set sizes used in this work.

The main bottleneck of hard+cache is the periodic recomputation of the cache for all images in the training set. With growing datasets, the recomputation becomes less feasible, e.g. revisiting the analysis of the computational complexity in the previous section, if the database grows 10 times (i.e. N = 800k), the caching would actually be slower than not caching. In the following, we present a method, hard+cache+query, which uses caching but its computational complexity does not depend on the database size, providing speedups over both hard+cache and hard+nocache.

First, we investigate what information is required by the weakly supervised training for a block of N r training queries: (i) the N r query images, (ii) N p potential positives for each of the N r queries. (iii) N n,h current hardest negatives for each of the N r queries, and (iv) N n,r random negatives for each of the N r queries. While (i) and (iii) are unavoidable, (ii) and (iv) can be improved upon by sharing as much information as possible across the N r queries.

The random negative pool can be shared across the N r queries, i.e. instead of having a different set of N n,r negatives for each query, we keep the random pool of size N n,r fixed for N r consecutive queries. This strategy brings down the computational complexity to N q /N r ×N n,r +N q ×(1+N p +N n,h )+N backward . The potential positives term N q ×N p becomes the new bottleneck, limiting the speedup versus hard+cache to only 2.5x. At first sight, it does not seem possible to decrease this term as it is essential that each training tuple contains all potential positives, in order to ensure the validity of weakly supervised training.

The key idea that enables a further speedup is to group the queries such that their potential positives overlap, therefore decreasing the forward pass count to:

N hard+cache+query forward = N q /N r × N n,r + N q × (1 + N p,e + N n,h ), (11)
where N p,e is the effective number of potential positives whose image representations have to be computed per query, i.e. the total number of potential positives for all queries in the group divided by the size of the query group. The grouping is accomplished by clustering the training queries according to their GPS location, and processing queries in the order of their cluster membership. Note that to emulate SGD where queries are traversed in a randomized order, each epoch the queries are reclustered starting with a different random seed, and the cluster order as well as within cluster query order are randomized as well.

Computational complexity. The total number of forward and backward passes that have to be computed in an epoch for our hard+cache+query method is N hard+cache+query forward + N backward . In our running example typical training scenario, N p,e is measured to be 5, and the above quantity amounts to a mere 240k, giving a theoretical speedup versus hard+cache of 6.2x, and 36x over hard+nocache. In practice, hard+cache+query only takes 3.5 hours for an epoch, compared to 19 hours of hard+cache, providing a real 5.4x speedup. Note that the query location-based clustering takes next to no time as it only requires clustering of a small number of 2-D data points (in our case N q = 8k), but the method would have no problems scaling to orders of magnitude more queries, and if needed one could also resort to approximate k-means clustering [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

Discussion. The presented hard+cache+query method enables efficient large-scale training, and is substantially faster than both hard+cache and hard+nocache, irrespective of the dataset statistics such as the size of the the training database or the number of training queries. In terms of end place recognition performance, we have not observed any statistically significant differences compared to hard+cache. Hard+cache+query is the only method capable of scaling up to ever increasing training datasets, and we believe that training with even more data will produce better models, as this is a consistently observed trend in deep learning-based methods. One potential downside of the method, although we have not observed its effects, is that, unlike hard+cache/nocache, consecutive training tuples are correlated due to the shared random negatives and overlapping potential positives, which is known to be detrimental when training with SGD. It is likely that applying simple and standard schemes such as experience replay [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF], [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] or parallel training with asynchronous updates [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF] would be beneficial as they are able to effectively counter correlated sequences of training data.

EXPERIMENTS

In this section we describe the used datasets and evaluation methodology (section 6.1), and give quantitative and qualitative (section 6.2) results to validate our approach. Finally, we also test the method on the standard image retrieval benchmarks (section 6.3).

Datasets and evaluation methodology

We report results on two publicly available place recognition datasets.

Pittsburgh (Pitts250k) [8] contains 250k database images downloaded from Google Street View and 24k test queries generated from Street View but taken at different times, years apart. We divide this dataset into three roughly equal parts for training, validation and testing, each containing around 83k database images and 8k queries, where the division was done geographically to ensure the sets contain independent images. To facilitate faster training, for some experiments, a smaller subset (Pitts30k) is used, containing 10k database images in each of the train/val(idation)/test sets, which are also geographically disjoint.

Tokyo 24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] contains 76k database images and 315 query images taken using mobile phone cameras. This is an extremely challenging dataset where the queries were taken at daytime, sunset and night, while the database images were only taken at daytime as they originate from Google Street View as described above. To form the train/val sets we collected additional Google Street View panoramas of Tokyo using the Time Machine feature, and name this set TokyoTM; Tokyo 24/7 (=test) and TokyoTM train/val are all geographically disjoint. The newly collected TokyoTM database (provided on request) was generated from Time Machine panoramas, downloaded using [START_REF] Gronat | streetget -a small python package for building place recognition datasets[END_REF], such that each panorama is represented by a set of 12 perspective images sampled evenly in different orientations [2], [3], [6], [8], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. Figure 4 shows samples from the dataset. The query set is formed as a random subsample of the database, and for each query, the positive and negative sets are sampled from the database so that they have a time stamp at least one month away from the time stamp of the query. This is done for both training and validation sets. Table 1 shows the sizes of the datasets. All images are 640 × 480 apart from the queries of Tokyo 24/7, which are, following [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], resized such that their largest dimension is 640. Evaluation metric. We follow the standard place recognition evaluation procedure [5], [6], [8], [9], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. The query image is deemed correctly localized if at least one of the top N retrieved database images is within d = 25 meters from the ground truth position of the query. The percentage of correctly recognized queries (Recall) is then plotted for different values of N . For Tokyo 24/7 we follow [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] and perform spatial non-maximal suppression on ranked database images before evaluation.

Implementation details. We use two base architectures which are extended with Max pooling (f max ) and our NetVLAD (f V LAD ) layers: AlexNet [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF] and VGG-16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]; both are cropped at the last convolutional layer (conv5), before ReLU. For Max pooling we use raw conv5 descriptors (with no normalization) while for VLAD and NetVLAD we add an additional descriptor-wise L2normalization layer after conv5. We found that not normalizing for Max pooling and normalizing for VLAD/NetVLAD generalizes across architectures, i.e. these are the best configurations for both AlexNet and VGG-16; more details are given in the appendix.

The number of clusters used in all VLAD / NetVLAD experiments is K = 64, resulting in 16k and 32k dimensional image representations for the two base architectures, AlexNet and VGG-16, respectively. The NetVLAD layer parameters are initialized to reproduce the conventional VLAD vectors by clustering conv5 descriptors extracted from a subsample of the train set for each dataset. The α parameter used for initialization is chosen to be large, such that the soft assignment weights āk (x i ) are very sparse in order to mimic the conventional VLAD well. Specifically, α is computed so that the the ratio of the largest and the second largest soft assignment weight āk (x i ) is on average equal to 100.

We use the margin m = 0.1, learning rate 0.001 or 0.0001 depending on the experiment, which is halved every 5 epochs, momentum 0.9, weight decay 0.001, batch size of 4 tuples (a tuple contains many images, c.f. equation ( 7)), and train for at most 30 epochs but convergence usually occurs much faster. The network which yields the best recall@5 on the validation set is used for testing.

All networks were trained using hard negative mining and caching (hard+cache), with the same parameter settings as in section 5. Query clustering (hard+cache+query) was not used in these experiments as we did not observe significant differences in the end performance of hard+cache+query versus hard+cache, and in order not to waste resources since we already performed the full set of experiments with hard+cache before establishing hard+cache+query.

As the VGG-16 network is much deeper and more GPUmemory hungry than AlexNet, it was not possible to train it in its entirety. Instead, in the light of experiments in table 2, the VGG-16 network is only trained down to conv5 layer.

All training and evaluation code, as well as our trained networks, are online [102], implemented in the MatConvNet framework [103]. Additional tuning of parameters and jittering could further improve performance as we have still observed some amount of overfitting.

Results and discussion

Baselines and state-of-the-art. To assess benefits of our approach we compare our representations trained for place recognition against "off-the-shelf" networks pretrained on other tasks. Namely, given a base network cropped at conv5, the baselines either use Max pooling (f max ), or aggregate the descriptors into VLAD (f V LAD ), but perform no further task-specific training. The three base networks are: AlexNet [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF], VGG-16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], both are pretrained for ImageNet classification [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF], and Places205 [START_REF] Zhou | Learning deep features for scene recognition using places database[END_REF], reusing the same architecture as AlexNet but pretrained for scene classification [START_REF] Zhou | Learning deep features for scene recognition using places database[END_REF]. Pretrained networks have been recently used as off-the-shelf dense descriptor extractors for instance retrieval [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] and the untrained f max network corresponds to the method of [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF].

Furthermore we compare our CNN representations trained for place recognition against the state-of-the-art local feature based compact descriptor, which consists of VLAD pooling [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] with ) outperform by a large margin off-the-shelf ones (blue, cyan, green for AlexNet, Places205, VGG-16), f V LAD (-o-) works better than fmax (-x-), and our f V LAD +whitening (- * -) representation based on VGG-16 sets the state-of-the-art on all datasets. [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] only evaluated on Tokyo 24/7 as the method relies on depth data not available in other datasets.

intra-normalization [START_REF] Arandjelović | All about VLAD[END_REF] on top of densely extracted RootSIFTs [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF]. The descriptor is optionally reduced to 4096 dimensions using PCA (learnt on the training set) combined with whitening and L2-normalization [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF]; this setup together with view synthesis yields the state-of-the-art results on the challenging Tokyo 24/7 dataset (c.f. [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]).

In the following we discuss figure 5, which compares place recognition performance of our method to the baselines outlined above on the Pittsburgh and Tokyo 24/7 benchmarks.

Benefits of end-to-end training for place recognition. Representations trained on the end-task of place recognition consistently outperform by a large margin off-the-shelf CNNs on both benchmarks. For example, on the Pitts250k-test our trained AlexNet with (trained) NetVLAD aggregation layer achieves recall@1 of 81.0% compared to only 55.0% obtained by off-the-shelf AlexNet with standard VLAD aggregation, i.e. a relative improvement in recall of 47%. Similar improvements can be observed on all three datasets. This confirms two important premises of this work: (i) our approach can learn rich yet compact image representations for place recognition, and (ii) the popular idea of using pretrained networks "off-the-shelf" [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] is sub-optimal as the networks trained for object or scene classification are not necessary suitable for the end-task of place recognition. The failure of the "off-the-shelf networks" is not surprising -apart from the obvious benefits of training, it is not clear why it should be meaningful to directly compare conv5 activations using Euclidean distance as they are trained to be part of the network architecture. For example, one can insert an arbitrary affine transformation of the features that can be countered by the following fully connected layer (fc6). This is not a problem when transferring the pre-trained representation for object classification [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF], [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF] or detection [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF] tasks, as such transformation can be countered by the follow-up adaptation [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF] or classification [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF] layers that are trained for the target task. However, this is not the case for retrieval [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Razavian | CNN features off-the-shelf: An astounding baseline for recognition[END_REF], [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] when Euclidean distance is applied directly on the output "off-the-shelf" descriptors.

Dimensionality reduction. We follow the standard state-of-theart procedure to perform dimensionality reduction of VLAD, as described earlier, i.e. the reduction into 4096-D is performed using PCA with whitening followed by L2-normalization [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF].

Figure 5 shows that the lower dimensional f V LAD (- * -) performs similarly to the full size vector (-o-).

Another option is to add a fully connected (FC) layer on top of the network, followed by L2-normalization, and train the entire network end-to-end along with dimensionality reduction. We have found this approach to work as well as whitening, but to be sensitive to initialization (random orthogonal projection worked best) due to a large overfitting potential as the FC contains a huge number of parameters.

Comparison with state-of-the-art. Figure 5 also shows that our trained f V LAD representation with whitening based on VGG-16 (magenta - * -) convincingly outperforms Root-SIFT+VLAD+whitening, as well as the method of Torii et al. [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], and therefore sets the state-of-the-art for compact descriptors on all benchmarks. Note that these are strong baselines that outperform most off-the-shelf CNN descriptors on the place recognition task.

NetVLAD versus Max pooling. By comparing f V LAD (-o-) methods with their corresponding f max (-x-) counterparts it is clear that NetVLAD pooling is much better than Max pooling for both off-the-shelf and trained representations. Figure 6 shows that NetVLAD performance decreases gracefully with dimensionality: On Tokyo 24/7, 128-D NetVLAD performs similarly to 512-D Max pooling, resulting in four times more compact representation for the same performance. Similarly, on Pitts250k-test NetVLAD achieves a two-fold memory saving compared to Max pooling. Furthermore, NetVLAD+whitening outperforms Max pooling convincingly when reduced to the same dimensionality.

Max versus Sum. Recent work [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF] suggests that Sum pooling performs better than Max pooling. Indeed, in our experiments Sum outperforms Max in the off-the-shelf set-up (recall@5 on Pitts250k-test -Sum: 67.9%, Max: 59.3%), but only for VGG-16, not AlexNet. Our training also works for Sum getting a significant improvement over the off-the-shelf set-up (+21% relative), but after training Max still performs better than Sum (Max: 88.7%, Sum: 82.3%). We also experimented with adding whitening to the Max-pooling baseline, but observed a drop in performance; detailed discussion is available in the appendix.

Is pooling needed? Another alternative image representation is to use the raw conv activations without any pooling, potentially Lowest trained layer fmax fV LAD r@1 r@5 r@10 r@1 r@5 r@10 none (off-the-shelf) 33. 5 Training data recall@1 recall@10 Pretrained on ImageNet [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF] 33.5 68.5 Pretrained on Places205 [START_REF] Zhou | Learning deep features for scene recognition using places database[END_REF] 24

Image retrieval

We use our best performing network (VGG-16, f V LAD with whitening and dimensionality reduction down to 256-D) trained completely on Pittsburgh, to extract image representations for standard object and image retrieval benchmarks (Oxford 5k & 105k [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], Paris 6k [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]). [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF], [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF] and [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] achieved even better results on the image retrieval tasks by using stronger supervision in the form of automatically cleaned-up image correspondences obtained with structure-from-motion, i.e. precise matching of RootSIFT descriptors and spatial verification. Note that the representation used in [START_REF] Radenović | CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples[END_REF] is identical to our Max pooling baseline, which we show is inferior to NetVLAD in our setting. It would be interesting to see what performance would NetVLAD reach with strong supervision, but this comparison is beyond the scope of this paper.

Competitive performance has been also obtained by recent off-the-shelf methods: Tolias et al. [START_REF] Tolias | Particular object retrieval with integral max-pooling of CNN activations[END_REF] pool at different scales, while Kalantidis et al. [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF] find that picking pool5 features compared to conv5 brings a boost, and perform image-adaptive descriptor weighting. These improvements are complementary to Each column corresponds to one test case: the query is shown in the first row, the top retrieved image using our best method (trained VGG-16 NetVLAD + whitening) in the second, and the top retrieved image using the best baseline (RootSIFT + VLAD + whitening) in the last row. The green and red borders correspond to correct and incorrect retrievals, respectively. Note that our learnt descriptor can recognize the same place despite large changes in appearance due to illumination (day/night), viewpoint and partial occlusion by cars, trees and people.

our NetVLAD architecture and can be incorporated in our endto-end learning framework. Additional performance boosts can be achieved by incorporating a centrality prior [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Mohedano | Bags of local convolutional features for scalable instance search[END_REF]. Mohedano et al. [START_REF] Mohedano | Bags of local convolutional features for scalable instance search[END_REF] pool descriptors using bag-of-words and thus their results are not directly comparable to our compact 256-D image representation, but it would be interesting to investigate if it is possible to train bag-of-words pooling in an end-to-end manner similarly to how we adapted VLAD to NetVLAD. Finally, Kim et al. [START_REF] Kim | Learned contextual feature reweighting for image geo-localization[END_REF] add another component to NetVLAD, which produces per-spatial location weights and performs weighted NetVLAD aggregation to achieve superior results.

CONCLUSIONS

We have designed a new convolutional neural network architecture that is trained for place recognition in an end-to-end manner from weakly supervised Street View Time Machine data. Our trained representation significantly outperforms non-learnt image representations and off-the-shelf CNN descriptors on challenging place recognition and image retrieval benchmarks. The two main components of our architecture -(i) the NetVLAD pooling layer and (ii) weakly supervised ranking loss -are generic CNN building blocks applicable beyond the place recognition task. The NetVLAD layer offers a powerful pooling mechanism with learnable parameters that can be easily plugged into any other CNN architecture. The weakly supervised ranking loss opens up the possibility of end-to-end learning for other ranking tasks where large amounts of weakly labelled data are available, for example, images described with natural language [START_REF] Karpathy | Deep visual-semantic alignments for generating image descriptions[END_REF].

TABLE 4

Comparison with state-of-the-art compact image representations (256-D) on image and object retrieval. We compare (b.) our best trained network, (a.) the corresponding off-the-shelf NetVLAD network (whitening learnt on Pittsburgh), and the state-of-the-art for compact image representations on standard image and object retrieval benchmarks. For completeness, we also include the Max pooling baselines (our best trained and off-the-shelf), reduced to 256-D with whitening. "original" and "rotated" for Holidays denote whether the original or the manually rotated dataset [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Babenko | Neural codes for image retrieval[END_REF] is used. The "crop" and "full" for Oxford/Paris correspond to the testing procedures when the query ROI is respected (the image is cropped as in [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF]), or ignored (the full image is used as the query), respectively. † [START_REF] Razavian | A baseline for visual instance retrieval with deep convolutional networks[END_REF] use square patches whose side is equal to 1.5× the maximal dimension of the query ROI (the detail is available in version 2 of their arXiv paper), so the setting is somewhere in between "crop" and "full", arguably closer to "full" as ROIs become very large.

I N this supplementary material, we provide additional discus- sions and results to complement the main paper.

Which layer to use for base descriptors? Our CNN architecture is based on aggregating activations produced by a particular CNN layer using NetVLAD. There are several choices regarding where exactly to perform the crop -which layer, before or after the ReLU, and whether to do some descriptor postprocessing, such as L2-normalization. Several works have already investigated these questions, including [1], [2], [3], [4], [5], [6], [7]. We have followed commonly used practice of cropping the networks at the last convolutional layer, and conducted preliminary experiments for the decision of using before-or after-ReLU activations, and whether to L2-normalize them or not. Our initial experiments with the off-the-shelf Max-pooling network showed that before-ReLU worked slightly better than after-ReLU, so we kept this setting throughout all experiments. We also done preliminary experiments with L2-normalization of the input descriptors, and observed that L2-normalization helped off-the-shelf NetVLAD slightly (+2%), while substantially hurting off-the-shelf Maxpooling (-7%), so we kept the best setting for each of the methods, i.e. L2-normalization is done for NetVLAD inputs but not for Max-pooling.

Max and Sum with whitening.

[2] suggest using whitening with Sum pooling, but this only makes sense for off-the-shelf networks -the whitening transformation can be incorporated inside the last conv layer due to the linearity of the transformation, so training a Sum pooling network is capable of learning the whitening implicitly. We therefore only test trained Max-pooling with whitening and observe a significant drop in performance on the Tokyo 24/7 benchmark (recall@5: from 52.7% to 42.2%).

Is pooling needed? Here we provide additional details to complement the discussion in the "is pooling needed" paragraph of the main paper. There are multiple issues with "no-pool" approaches. First, if no pooling is performed, then the image representation is not invariant to translation, scale or partial occlusions as it enforces a fixed spatial layout, and the visual search is akin to near-duplicate detection. An analogy with the pre-CNN image retrieval would be to use GIST [8] instead of bag-of-words or VLAD, which has been shown to be clearly inappropriate due to the aforementioned reasons [9]. Second, no-pool cannot handle variable image sizes, as, without pooling, the convolutional map varies in size depending on the input. This is a real problem as Tokyo 24/7 queries, and all image retrieval benchmarks (Oxford, Paris, Holidays) have variable image sizes. The problem can be handled by padding to a predefined fixed size (introducing boundary artifacts), resizing and sacrificing the original aspect ratio (can be very detrimental), or resizing isotropically and taking the central crop (loss of information outside of the crop).

Third, passing a 640 × 480 image through the VGG-16 network and extracting the activations at the last convolutional layer results in a 40 × 30 × 512 feature map, i.e. the image representation would be 600k-D. Note that it is not simple to perform dimensionality reduction of such a large representation, e.g. to reduce the dimensionality to 512 using PCA one would need to estimate 315 million parameters, which is hard to do reliably. Therefore, it is necessary to down-sample images which results in reduced performance [6], [7].

To test no-pooling, 640×480 images are used as input since all database images have this resolution. Images that do not conform to this aspect ratio (Tokyo 24/7 queries) are resized isotropically to the smallest resolution that can accommodate a 640 × 480 rectangular region, and a central crop of this size is taken. The image is passed through a VGG-16 network cropped at conv5 3, but since this results in a huge 40 × 30 × 512 feature map, local Max-pooling is applied to reduce it to a manageable size, comparable to NetVLAD. In more detail, Max-pooling is performed with kernel size and stride 5, resulting in a 8 × 6 × 512 feature map. The feature map is vectorized followed by L2-normalization, and used as a 25k-D image representation. A fully connected layer (FC) is optionally appended to perform dimensionality reduction into 4096-D, followed by another L2-normalization. The no-pool and no-pool+FC representations are trained on TokyoTM using exactly the same procedure and loss as NetVLAD, and evaluated on Tokyo 24/7, making results directly comparable to Figure 5(c) of the main paper.

The no-pool+FC method overfits badly because the FC is very large (25k × 4096 = 100M parameters), achieving recall@5 of only 34.6%, while no-pool gets 63.5%, compared to 82.5% of NetVLAD%. No-pool does beat Max-pooling which gets 52.7%, but it does so with a 48 times much larger image representation (25k-D versus 512-D). Reducing no-pool down to 4096-D with whitening gives only 50.8%, i.e. a 8 times larger representation achieves a lower performance than Max-pooling.

Pretraining. A natural question is whether pretraining the convolutional layers by first training with Max-pooling can be beneficial for the subsequent NetVLAD training. To investigate this, an AlexNet based NetVLAD network was trained on Pitts30k-train and tested on Pitts30k-val. We used the best Max-pooling network from Table 2 of the main paper (i.e. trained down to conv2), as the starting point for NetVLAD, and fine-tuned the NetVLAD network (also down to conv2). As expected, the Max-pooling pretraining learns better features, and therefore the initial performance of the NetVLAD representation, before any NetVLAD training, is much higher than for off-the-shelf NetVLAD: recall@5 on Pitts30k-val is 83.7% compared to 69.8%. However, the final performance after training is similar to that of the NetVLAD initialized with an off-the-shelf network, achieving recalls@1, 5 and 10 of 84.3%, 94.1% and 96.1%, respectively.

Qualitative evaluation. Figure 1 shows additional comparisons between our method and the best baseline (Root-SIFT+VLAD+whitening).

Image retrieval. The complete set of NetVLAD results for different output dimensions is shown in table 1.

Query Ours

Best baseline

Fig. 1. Examples of retrieval results for challenging queries on Tokyo 24/7. Each column corresponds to one test case: the query is shown in the first row, the top retrieved image using our best method (trained VGG-16 NetVLAD + whitening) in the second, and the top retrieved image using the best baseline (RootSIFT + VLAD + whitening) in the last row. The green and red borders correspond to correct and incorrect retrievals, respectively. Note that our learnt descriptor can recognize the same place despite large changes in appearance due to illumination (day/night), viewpoint and partial occlusion by cars, trees and people. The last column corresponds to a difficult query, which is hard for our method because of its overall very dark appearance.

Fig. 1 .

 1 Fig. 1. Our trained NetVLAD descriptor correctly recognizes the location (b) of the query photograph (a) despite the large amount of clutter (people, cars), changes in viewpoint and completely different illumination (night vs daytime). Please see figure 7 and the appendix for more examples.

Fig. 4 .

 4 Fig. 4. Google Street View Time Machine examples. Each column shows perspective images generated from panoramas from nearby locations, taken at different times. The goal of this work is to learn from this imagery an image representation that: has a degree of invariance to changes in viewpoint and illumination (a-f); has tolerance to partial occlusions (c-f); suppresses confusing visual information such as clouds (a,c), vehicles (c-f) and people (c-f); and chooses to either ignore vegetation or learn a season-invariant vegetation representation (a-f).

Fig. 5 .

 5 Fig.5. Comparison of our methods versus off-the-shelf networks and state-of-the-art. The base CNN architecture is denoted in brackets: (A)lexNet (V)GG-16. Trained representations (red and magenta for AlexNet and VGG-16) outperform by a large margin off-the-shelf ones (blue, cyan, green for AlexNet, Places205, VGG-16), f V LAD (-o-) works better than fmax (-x-), and our f V LAD +whitening (- * -) representation based on VGG-16 sets the state-of-the-art on all datasets.[START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] only evaluated on Tokyo 24/7 as the method relies on depth data not available in other datasets.

7 Fig. 6 .

 76 Fig. 6. Place recognition accuracy versus dimensionality. Note the log scale of the x-axis. 128-D NetVLAD performs comparably to the 4× larger 512-D fmax on Tokyo 24/7. For the same dimension (512-D) NetVLAD convincingly outperforms fmax.

Fig. 7 .

 7 Fig.7. Examples of retrieval results for challenging queries on Tokyo 24/7. Each column corresponds to one test case: the query is shown in the first row, the top retrieved image using our best method (trained VGG-16 NetVLAD + whitening) in the second, and the top retrieved image using the best baseline (RootSIFT + VLAD + whitening) in the last row. The green and red borders correspond to correct and incorrect retrievals, respectively. Note that our learnt descriptor can recognize the same place despite large changes in appearance due to illumination (day/night), viewpoint and partial occlusion by cars, trees and people.

TABLE 1

 1 Datasets. Sizes of datasets used in experiments. All train/val(idation)/test datasets are mutually disjoint geographically.

	Dataset	Database Query set
	Pitts250k-train Pitts250k-val Pitts250k-test Pitts30k-train Pitts30k-val Pitts30k-test Tokyo Time Machine-train Tokyo Time Machine-val Tokyo 24/7 (=test)	91,464 78,648 83,952 10,000 10,000 10,000 49,104 49,056 75,984	7,824 7,608 8,280 7,416 7,608 6,816 7,277 7,186 315

TABLE 2

 2 Partial training. Effects of performing backpropagation only down to a certain layer of AlexNet, e.g. 'conv4' means that weights of layers from conv4 and above are learnt, while weights of layers below conv4 are fixed to their pretrained state; r@N signifies recall@N. Results are shown on the Pitts30k-val dataset.

  Importance of Time Machine training. Here we examine whether the network can be trained without the Time Machine (TM) data. In detail, we have modified the training query set for Pitts30k-train to be sampled from the same set as the training database images, i.e. the tuples of query and database images used in training were captured at the same time. As shown in table 3, Recall@1 with f max on Pitts30k-val for the off-theshelf AlexNet is 33.5%, and training without TM improves this to 38.7%. However, training with TM obtains 68.5% showing that

	NetVLAD conv5 conv4 conv3 conv2 conv1 (full)	57.3 68.4 --63.8 83.8 89.0 -62.1 83.6 89.2 69.8 86.7 90.3 69.1 87.6 91.5 68.5 86.2 90.8	54.5 69.8 76.1 80.5 91.8 95.2 84.1 94.6 95.5 85.1 94.4 96.1 85.5 94.6 96.5 84.5 94.6 96.6 84.2 94.7 96.1
	followed with a fully connected (FC) layer. There are multiple
	issues with this approach: (i) it cannot handle variable image sizes,
	(ii) it would be infeasibly large, and, most importantly, (iii) it is not
	invariant to translation, scale or partial occlusions as it enforces a
	fixed spatial layout. Our experiments on Tokyo 24/7 confirm that
	pooling is indeed required, as the best trained "no-pool" baseline
	achieves a recall@5 of 63.5%, compared to 82.5% of NetVLAD.
	Further details are given in the appendix.
	Which layers should be trained? In Table 2 we study the benefits of training different layers for the end-task of place recognition.
	The largest improvements are thanks to training the NetVLAD
	layer, but training other layers results in further improvements,
	with some overfitting occurring below conv2.
	Pretraining. We investigated whether pretraining the convolu-tional layers with Max-pooling can be beneficial for the subse-
	quent NetVLAD training. While the pretraining helped NetVLAD
	to train faster, the final performance was unaffected; details of the
	experiment are available in the appendix.

TABLE 3

 3 Time Machine importance. Recall of fmax on Pitts30k-val (AlexNet) with vs without using Time Machine data for training. Training using Time Machine is essential for generalization.

  The performance of our descriptor is impressive -it can recognize the same place despite large changes in appearance due to illumination (day/night), viewpoint and partial occlusion by cars, trees and people. The main failure cases are queries taken at night which are very dark and featureless, causing problems even for humans. Top ranked images for all queries in the Tokyo 24/7 dataset are available on our project page[102].

	Trained without Time Machine Trained with Time Machine	.8 38.7 68.5	54.4 68.1 90.8
	Time Machine data is crucial for good place recognition accuracy
	as without it the network does not generalize well. The network
	learns, for example, that recognizing cars is important for place
	recognition, as the same parked cars appear in all images of a
	place.
	Qualitative evaluation. Figure 7 compares the top ranked images of our method versus the best baseline (Root-
	SIFT+VLAD+whitening); additional examples are shown in the
	appendix.

Table 4

 4

	compares

TABLE 1

 1 Image and object retrieval for varying dimensionality of NetVLAD. We compare our best trained network (VGG-16, f V LAD ), and the corresponding off-the-shelf network (whitening learnt on Pittsburgh), on standard image and object retrieval benchmarks, while varying the dimensionality (Dim.) of the image representation. .1 36.8 38.2 56.6 60.3 32 36.5 36.0 48.9 51.9 68.0 71.7 64 40.1 38.9 55.7 58.1 76.5 80.4 128 49.0 49.8 60.1 63.2 79.1 83.3 256 53.4 55.5 64.3 67.7 82.1 86.0 512 56.7 59.0 67.5 70.2 82.9 86.7 1024 60.2 62.6 70.9 73.3 83.9 87.3 2048 62.8 65.4 73.7 75.6 84.9 88.2 4096 64.4 66.6 75.1 77.4 84.9 88.3 NetVLAD trained 16 32.5 29.9 45.1 44.9 54.8 58.6 32 43.4 42.6 53.5 54.4 67.5 71.2 64 53.6 51.1 61.8 63.0 75.4 79.3 128 60.4 61.4 68.7 69.5 78.8 82.6 256 62.5 63.5 72.0 73.5 79.9 84.3 512 65.6 67.6 73.4 74.9 81.7 86.1 1024 66.9 69.2 75.7 76.5 82.4 86.5 2048 67.7 70.8 77.0 78.3 82.8 86.9 4096 69.1 71.6 78.5 79.7 83.1 87.5

	Method NetVLAD off-shelf	Dim. Oxford 5k full crop 16 28.7 28	Paris 6k full crop orig rot Holidays

We define one epoch as one pass through the training queries, not necessarily visiting all the training database images.

This is the time for the first epoch -the later epochs tend to be faster as (i) fewer negatives violate the margin so fewer backward passes and parameter updates are required (speedup of second versus first epoch is 1.3x), and (ii) the frequency of cache recomputation decreases, as described in the previous section.

ACKNOWLEDGMENTS

This work was partly supported by RVO13000 -Conceptual development of research organization, ERC grant LEAP (no. 336845), ANR project Semapolis (ANR-13-CORD-0003), JSPS KAKENHI Grant Number 15H05313, the Inria CityLab IPL, CIFAR Learning in Machines & Brains program, the EU-H2020 project LADIO No. 731970, the Intelligence Advanced Research Projects Activity (IARPA) via Air Force Research Laboratory, contract FA8650-12-C-7212, and ESIF, OP Research, development and education project IM-PACT No. CZ.02.1.01/0.0/0.0/15 003/0000468. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, AFRL, or the U.S. Government.

Method