Akihiko Torii
email: torii@sc.e.titech.ac.jp

Hajime Taira
email: htaira@ok.ctrl.titech.ac.jp

Josef Sivic
email: josef.sivic@ens.fr

Marc Pollefeys
email: marc.pollefeys@inf.ethz.ch

Masatoshi Okutomi

Tomas Pajdla
email: pajdla@cvut.cz

Torsten Sattler

Are Large-Scale 3D Models Really Necessary for Accurate Visual Localization?

Keywords: Visual Localization, Image-based Localization, Place Recognition, Pose Estimation, Image Retrieval. !

Accurate visual localization is a key technology for autonomous navigation. 3D structure-based methods employ 3D models of the scene to estimate the full 6 degree-of-freedom (DOF) pose of a camera very accurately. However, constructing (and extending) large-scale 3D models is still a significant challenge. In contrast, 2D image retrieval-based methods only require a database of geo-tagged images, which is trivial to construct and to maintain. They are often considered inaccurate since they only approximate the positions of the cameras. Yet, the exact camera pose can theoretically be recovered when enough relevant database images are retrieved. In this paper, we demonstrate experimentally that large-scale 3D models are not strictly necessary for accurate visual localization. We create reference poses for a large and challenging urban dataset. Using these poses, we show that combining image-based methods with local reconstructions results in a higher pose accuracy compared to state-of-the-art structure-based methods, albeight at higher run-time costs. We show that some of these run-time costs can be alleviated by exploiting known database image poses. Our results suggest that we might want to reconsider the need for large-scale 3D models in favor of more local models, but also that further research is necessary to accelerate the local reconstruction process.

INTRODUCTION

D ETERMINING the location from which a photo was taken is a key challenge in the navigation of autonomous vehicles such as self-driving cars and drones [START_REF] Lim | Real-Time Image-Based 6-DOF Localization in Large-Scale Environments[END_REF], robotics [START_REF] Lowry | Visual place recognition: A survey[END_REF], mobile Augmented Reality [START_REF] Middelberg | Scalable 6-DOF Localization on Mobile Devices[END_REF], [START_REF] Lynen | Get Out of My Lab: Large-scale, Real-Time Visual-Inertial Localization[END_REF], and Structure-from-Motion (SfM) [START_REF] Agarwal | Building Rome in a day[END_REF], [START_REF] Schönberger | Structure-From-Motion Revisited[END_REF], [START_REF] Schönberger | From Single Image Query to Detailed 3D Reconstruction[END_REF], [START_REF] Crandall | Discretecontinuous optimization for large-scale structure from motion[END_REF]. In addition, solving the visual localization problem enables a system to determine the content of a photo. This can be used to develop interesting new applications, e.g., virtual tourism [START_REF] Snavely | Modeling the World from Internet Photo Collections[END_REF] and automatic annotation of photos [START_REF] Weyand | Discovering Details and Scene Structure with Hierarchical Iconoid Shift[END_REF], [START_REF] Gammeter | I Know What You Did Last Summer: Object-Level Auto-Annotation of Holiday Snaps[END_REF].

Currently, approaches that tackle the visual localization problem can mainly be divided into two categories (c.f . figure 1 and table 1). Visual place recognition approaches [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF], [START_REF] Torii | Efficient localization of panoramic images using tiled image descriptors[END_REF], [START_REF] Torii | Visual place recognition with repetitive structures[END_REF], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF], [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF] cast the localization problem as an image retrieval, i.e., instance-level recognition, task and represent a scene as a database of geo-tagged images. Given a query photo, they employ 2D image-based localization methods that operate purely on an image level to determine a set of database images similar to the query. The geo-tag of the most relevant retrieved photo then often serves as an approximation to the position from which the query was taken. Image-based localization methods [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF], [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF], [START_REF] Choudhary | Visibility probability structure from sfm datasets and applications[END_REF], [START_REF] Irschara | From Structurefrom-Motion Point Clouds to Fast Location Recognition[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF] cast the localization problem as a camera resectioning task. They represent scenes via 3D models, with image descriptors attached to the 3D points, which are obtained from SfM or by attaching local features/patches to 3D point clouds [START_REF] Sibbing | SIFT-Realistic Rendering[END_REF], [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF]. 3D structure-based localization algorithms then use these descriptors to establish a set of 2D-3D matches. In turn, these matches are used to recover the full 6DOF camera pose, i.e., position and orientation, of the query image [START_REF] Kukelova | Real-Time Solution to the Absolute Pose Problem with Unknown Radial Distortion and Focal Length[END_REF], [START_REF] Haralick | Review and analysis of solutions of the three point perspective pose estimation problem[END_REF].

A common perception is that 2D image-based approaches can be used by 3D structure-based methods to determine which parts of a scene might be visible in the query [START_REF] Irschara | From Structurefrom-Motion Point Clouds to Fast Location Recognition[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Sattler | Image Retrieval for Image-Based Localization Revisited[END_REF], [START_REF] Cao | Graph-Based Discriminative Learning for Location Recognition[END_REF]. Purely 2D-based techniques are considered unsuited for accurate visual localization due to only approximating the true camera position of the query. Consequently, 2D-and 3D-based localization methods are only compared in terms of place recognition performance [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. However, this ignores the fact that a more accurate position, together with the camera orientation, can be computed if two or more related database images can be Requires extra post-processing to obtain 6DOF poses Needs to construct a consistent 3D model retrieved [START_REF] Zhang | Image based localization in urban environments[END_REF], [START_REF] Zamir | Accurate Image Localization Based on Google Maps Street View[END_REF], [START_REF] Zheng | Structure From Motion Using Structure-Less Resection[END_REF]. This naturally leads to the question whether 2D image-based localization approaches can achieve the same pose accuracy as 3D structure-based methods. This is a compelling question due to the way both types of methods represent scenes: especially for large-scale scenes, building and maintaining the 3D models required by structure-based techniques is a non-trivial task. At the same time, image-based techniques just require a database of geo-tagged images, which is significantly easier to maintain.

Contributions. In this paper, we want to answer whether large-scale 3D models are actually necessary for accurate visual localization or whether sufficiently precise pose estimates can already be obtained from a database of geo-tagged images. Our work makes the following contributions: i) We generate reference camera pose annotations for the query images of the San Francisco Landmarks dataset [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], resulting in the first city-scale dataset with such information. We make our reference poses together with all data and evaluation scripts required to reproduce our results or use our dataset for further research publicly available 1 .

ii) We use this new dataset for the first comparison of 2D-and 3D-based localization approaches regarding their pose accuracy.

To this end, we combine 2D image-based methods with a SfMbased post-processing step for pose estimation. Our results clearly show that 2D image-based methods can achieve a similar or even better positional accuracy than 3D structure-based methods. As such, our paper refutes the notion that purely 2D image-based approaches are inaccurate. iii) We demonstrate that the previously used strategy of evaluating localization methods via a landmark recognition task is unsuitable for predicting pose accuracy. Also, we show that pose precision results obtained on smaller landmark datasets do not translate to large-scale localization. Thus, our new benchmark closes a crucial gap in the literature and will help to drive research on accurate and scalable visual localization. This paper is an extended version of [START_REF] Sattler | Are large-scale 3D models really necessary for accurate visual localization?[END_REF] with a new extended version of the reference poses for the San Francisco dataset and detailed description of our approach to improve the reference poses (section 3.1). In detail, we provide 157 new reference poses compared to the 442 poses provided in [START_REF] Sattler | Are large-scale 3D models really necessary for accurate visual localization?[END_REF]. To register these images, we use another source of geo-registered images to fill the spatial gap of queries and original database images. The newly added reference poses thus correspond to more challenging images. We also measure the uncertainty of our reference poses, showing the limitations of our dataset. We perform additional experiments with variants of existing methods that use pose priors, add additional baselines, provide timing results, and use more evaluation measures compared to [START_REF] Sattler | Are large-scale 3D models really necessary for accurate visual localization?[END_REF]. In particular, we propose modifications of SfM-based post processing that both reduce the run-time and increase pose accuracy. All the results in section 6 are renewed using the new reference poses.

RELATED WORK

Image-based approaches model localization as an image retrieval problem. They employ standard retrieval techniques such as Bag-of-Words (BoW) representations with inverted files [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF], followed by fast spatial verification [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], [START_REF] Schönberger | A Vote-and-Verify Strategy for Fast Spatial Verification in Image Retrieval[END_REF], or more compact representations such as VLAD or Fischer Vectors [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], [START_REF] Arandjelović | All about VLAD[END_REF].

A more discriminative BoW representation can be constructed by only using informative features for each place [START_REF] Schindler | City-scale location recognition[END_REF]. Similarly, detecting and removing confusing features [START_REF] Knopp | Avoding Confusing Features in Place Recognition[END_REF], e.g., structures appearing in multiple places, or down-weighting their influence [START_REF] Torii | Visual place recognition with repetitive structures[END_REF] improves performance as well. Arandjelović & Zisserman consider the descriptor space density to automatically weight the influence of image features [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF]. Thus, features on repetitive structures have a smaller impact on the similarity score between images than features with unique local appearance.

One major challenge in visual localization is to handle large changes in illumination, e.g., between day and night. To this end, Torii et al. create synthetic views from novel viewpoints by using the depth maps associated with street-view images to warp the original images [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. Adding these images to the database lessens the burden on the feature detector to handle both viewpoint and illumination changes, resulting in a higher localization performance. Very recently, convolutional neural networks (CNNs) have been used to directly learn compact image descriptor suitable for place recognition [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF], [START_REF] Radenović | Fine-tuning CNN Image Retrieval with No Human Annotation[END_REF], [START_REF] Kim | Learned contextual feature reweighting for image geo-localization[END_REF], [START_REF] Noh | Large-scale image retrieval with attentive deep local features[END_REF].

Another approach is to model visual localization as a classification task [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF], [START_REF] Cao | Graph-based discriminative learning for location recognition[END_REF], [START_REF] Weyand | PlaNet -Photo Geolocation with Convolutional Neural Networks[END_REF]. Such methods subdivide a scene into individual places and then learn classifiers, e.g., based on a BoW representation [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF], [START_REF] Cao | Graph-based discriminative learning for location recognition[END_REF] or using CNNs [START_REF] Weyand | PlaNet -Photo Geolocation with Convolutional Neural Networks[END_REF], [START_REF] Seo | CPlaNet: Enhancing Image Geolocalization by Combinatorial Partitioning of Maps[END_REF], to distinguish between images belonging to different places.

3D Structure-based localization methods assume that a scene is represented by a 3D model. Each 3D point is associated with one or more local descriptors. Thus, structure-based methods establish 2D-3D matches between features in a query image and the 3D points via descriptor matching. In a second stage, the camera pose can be estimated by employing a PnP solver [START_REF] Kukelova | Real-Time Solution to the Absolute Pose Problem with Unknown Radial Distortion and Focal Length[END_REF], [START_REF] Haralick | Review and analysis of solutions of the three point perspective pose estimation problem[END_REF], [START_REF] Bujnak | New efficient solution to the absolute pose problem for camera with unknown focal length[END_REF] inside a RANSAC [START_REF] Fischler | Random Sampling Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography[END_REF], [START_REF] Sattler | On Sampling Focal Length Values to Solve the Absolute Pose Problem[END_REF] loop.

Descriptor matching quickly becomes a bottleneck and three (partially orthogonal) approaches exist to accelerate this stage: i) Prioritized search strategies [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF], [START_REF] Choudhary | Visibility probability structure from sfm datasets and applications[END_REF], [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF] terminate correspondence search early on, ii) model compression schemes use only a subset of all 3D points [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF], [START_REF] Cao | Minimal Scene Descriptions from Structure from Motion Models[END_REF], [START_REF] Camposeco | Hybrid Scene Compression for Visual Localization[END_REF], iii) retrieval-based approaches restrict matching to the 3D points visible in the topranked database images [START_REF] Irschara | From Structurefrom-Motion Point Clouds to Fast Location Recognition[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Sattler | Image Retrieval for Image-Based Localization Revisited[END_REF], [START_REF] Cao | Minimal Scene Descriptions from Structure from Motion Models[END_REF], [START_REF] Liu | Efficient Global 2D-3D Matching for Camera Localization in a Large-Scale 3D Map[END_REF].

Lowe's ratio test [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], which measures the local density of the descriptor space, is commonly used to reject ambiguous matches. Larger 3D models induce a denser descriptor space, forcing the ratio test to reject more correct matches as ambiguous [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF]. In order to handle the higher outlier ratios resulting from a relaxed test, large-scale, structure-based localization methods use co-visibility information [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF] or advanced pose estimation approaches [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF], [START_REF] Svärm | City-Scale Localization for Cameras with Known Vertical Direction[END_REF], [START_REF] Camposeco | Toroidal Constraints for Two Point Localization Under High Outlier Ratios[END_REF], [START_REF] Toft | Semantic Match Consistency for Long-Term Visual Localization[END_REF].

Structure-based localization approaches naturally benefit from deep learning by replacing handcrafted feature detectors and descriptors such as SIFT [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] with learned alternatives [START_REF] Noh | Large-scale image retrieval with attentive deep local features[END_REF], [START_REF] Savinov | Quadnetworks: unsupervised learning to rank for interest point detection[END_REF], [START_REF] Yi | LIFT: Learned Invariant Feature Transform[END_REF], [START_REF] Mishchuk | Working hard to know your neighbor's margins: Local descriptor learning loss[END_REF], [START_REF] Schönberger | Semantic Visual Localization[END_REF]. Rather than replacing individual components, learning-based localization approaches aim to replace larger parts of the localization pipeline. Camera pose regression techniques such as PoseNet and its variants [START_REF] Kendall | PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization[END_REF], [START_REF] Kendall | Geometric loss functions for camera pose regression with deep learning[END_REF], [START_REF] Naseer | Semantics-aware visual localization under challenging perceptual conditions[END_REF], [START_REF] Walch | Image-based localization using LSTMs for structured feature correlation[END_REF] replace the full localization stack by a single convolutional neural network (CNN) that is trained to directly predict a 6DOF camera pose. However, these methods do not yet achieve the same pose accuracy as structure-based methods on outdoor scenes [START_REF] Walch | Image-based localization using LSTMs for structured feature correlation[END_REF]. In addition, training them on larger datasets still seems to be an open problem [START_REF] Sattler | Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions[END_REF], [START_REF] Taira | InLoc: Indoor visual localization with dense matching and view synthesis[END_REF]. In this paper, we show that a state-of-the-art PoseNet variant [START_REF] Kendall | Geometric loss functions for camera pose regression with deep learning[END_REF] performs worse than a simple image-based baseline on a medium-scale dataset. Approaches that predict the poses of two subsequent images in a sequence [START_REF] Brahmbhatt | Geometry-Aware Learning of Maps for Camera Localization[END_REF], [START_REF] Valada | Deep Auxiliary Learning for Visual Localization and Odometry[END_REF] could potentially lead to more accurate poses, but are not applicable to the single-image scenario considered in this paper.

Rather than replacing the complete localization pipeline, scene coordinate regression techniques [START_REF] Brachmann | DSAC-differentiable RANSAC for camera localization[END_REF], [START_REF] Brachmann | Learning less is more-6d camera localization via 3d surface regression[END_REF], [START_REF] Cavallari | On-The-Fly Adaptation of Regression Forests for Online Camera Relocalisation[END_REF], [START_REF] Massiceti | Random Forests versus Neural Networks -What's Best for Camera Relocalization?[END_REF], [START_REF] Shotton | Scene coordinate regression forests for camera relocalization in RGB-D images[END_REF], [START_REF] Valentin | Exploiting Uncertainty in Regression Forests for Accurate Camera Relocalization[END_REF] only replace the 2D-3D matching stage while keeping the RANSAC-based pose estimation stage. These methods outperform structure-based approaches in terms of pose accuracy [START_REF] Brachmann | Learning less is more-6d camera localization via 3d surface regression[END_REF]. However, they currently are not able to handle larger scenes such as the ones considered in this paper [START_REF] Taira | InLoc: Indoor visual localization with dense matching and view synthesis[END_REF], [START_REF] Brachmann | Learning less is more-6d camera localization via 3d surface regression[END_REF].

SAN FRANCISCO REVISITED

In this section, we first motivate our new pose dataset by reviewing the currently used evaluation protocols. Next, we review the San Francisco dataset before detailing how we generate reference poses for some of its query images.

Current evaluation protocols & their shortcomings. 3D structure-based localization approaches are typically evaluated by counting how many query images have an estimated pose with at least X inliers, where X is some threshold. This is based on the observation, made on smaller datasets, that wrong pose estimates are rarely supported by many inliers. However, this observation does not transfer to large-scale datasets [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. At scale, repetitive structures and sheer size increase the chance of finding more wrong matches that are geometrically consistent [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. Simply counting the query images with at least X inliers thus overestimates the performance of structure-based methods. As such, it is necessary to also consider pose accuracy.

The datasets commonly used to evaluate the localization accuracy of structure-based approaches, 7 Scenes [START_REF] Shotton | Scene coordinate regression forests for camera relocalization in RGB-D images[END_REF], Arts Quad [START_REF] Crandall | Discretecontinuous optimization for large-scale structure from motion[END_REF], Cambridge Landmarks [START_REF] Kendall | PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization[END_REF], Dubrovnik [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF], and the recent Aachen Day-Night, RobotCar Seasons, and CMU Seasons benchmarks [START_REF] Sattler | Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions[END_REF], all depict small-to medium-scale scenes with significant texture. Consequently, it is often possible to find many matches, which aids pose accuracy. Richly textured scenes are less frequent in urban environments due to the prevalence of reflecting or texture-less surfaces. This creates a need to also evaluate pose accuracy for truly large-scale datasets characterized by more ambiguous structures. Creating a benchmark for such a scene is one of the contributions of this paper.

2D image-based localization methods are mostly evaluated in the context of landmark or place recognition [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF], [START_REF] Torii | Efficient localization of panoramic images using tiled image descriptors[END_REF], [START_REF] Torii | Visual place recognition with repetitive structures[END_REF], [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF], [START_REF] Zamir | Accurate Image Localization Based on Google Maps Street View[END_REF], [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF], [START_REF] Zamir | Image Geo-Localization Based on Multiple-Nearest Neighbor Feature Matching Using Generalized Graphs[END_REF]. For landmark recognition, the goal is to retrieve at least one database image that depicts the same landmark or scene element as the query photo [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. Vision is a long-range sensor and as such, a relevant database image might depict the same landmark while being taken tens or hundreds of meters away from the position of the query image. Thus, the geo-tag of such an image is not necessary a good approximation to the position of the query. Still, it might be possible to accurately determine this position through camera pose estimation (c.f . section 4). One of the contributions of this paper is to evaluate to what extend landmark recognition performance translates to accurate localization.

In terms of place recognition, image-based localization methods are tasked to find a database image whose geo-tag is within a certain radius of the query's GPS position [START_REF] Torii | Visual place recognition with repetitive structures[END_REF], [START_REF] Zamir | Accurate Image Localization Based on Google Maps Street View[END_REF]. The fact that vision is a long-range sensor again causes problems in this setting as it is can be hard to distinguish between database images depicting the same part of the scene taken close to or far away from the query position [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF]. In addition, the GPS positions associated with the query images can be rather inaccurate, especially in urban environments [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], requiring the use of a high threshold of tens or even hundreds of meters.

The San Francisco dataset. The publicly available San Francisco (SF) dataset, originally presented in [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], consists of 1, 062, 468 street view images, cutout of panoramas using perspective projection from panoramas and denoted as PCI images, taken from the top of a car and 803 query images taken with cell phones by pedestrians. All photos depict downtown San Francisco (see the gray points in figure 2 for the distribution of the PCI images). Each PCI is associated with an accurate GPS position and a building ID, generated by back-projecting a 3D model of the city into the image [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. Similarly, most query images have a GPS position and a list of IDs of the buildings visible in them. Unfortunately, the GPS coordinates of the query photos are not very precise and thus cannot be used as ground truth to measure localization accuracy.

There exist two SfM reconstructions of the San Francisco models [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF]. The SF-0 version of the dataset contains around 30M 3D points, associated with SIFT descriptors [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], reconstructed from 610, 773 images. To create the SF-1 variant, the database images were histogram-equalized before extracting upright SIFT features, resulting in a model containing roughly 75M points reconstructed from 790, 409 images. For both 3D models, each 3D point can be associated with the building IDs from the database photos it was reconstructed from. However, both models do not provide reference poses for the query images. Thus, the SF dataset is commonly used to evaluate and compare structure-and imagebased localization methods in the context of landmark recognition. Using the reference poses generated in this paper enables us to evaluate camera pose accuracy on the SF dataset.

Generating Reference Poses

Without any precise geo-tags, which are hard to obtain in downtown areas due to multi-path effects, the easiest way to obtain ground truth poses at scale is to use SfM algorithms. We follow this approach. Yet, instead of adding the query images to an existing model, which would require us to solve the localization problem, we generate local reconstructions around the queries which we subsequently geo-register. While we took great care to ensure the accuracy of our pose estimates, there is still a certain error in them. We thus use the term "reference poses" rather than "ground truth poses" to indicate that our poses are a rather precise reference and not a centimeter accurate ground truth.

Generating local reconstructions. The first step is to generate SfM reconstructions from the database images around the query images. Unfortunately, the GPS coordinates for the query images provided by the SF dataset are inaccurate with errors up to hundreds of meters [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. Thus, we determine relevant PCI images for each query photo by exploiting the readily available building IDs. For each query, we perform feature matching against all database photos with a relevant building ID, followed by approximate geometric verification [START_REF] Torii | Visual place recognition with repetitive structures[END_REF], [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. We visually inspect the 20 images with the largest number of inliers, as long as they have at at least 5 inliers, and select the photo that is visually most similar to the query image for a later consistency check.

There is a strong change in viewpoint between the PCI (taken from the road) and query (taken mostly from sidewalks) images. Thus, finding sufficient matches to include the query image in the local reconstruction can be challenging. To increase the chance of finding enough matches, we thus include additional images that are not part of the original SF dataset. More precisely, we use Google Street View Time Machine (GSVTM) data [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF], [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF] that covers the same area as the San Francisco dataset. We chose GSVTM instead of GSV images as they provide a denser spacial sampling. GSVTM provides panoramas of 13, 312 × 6, 656 pixels associated with geo-tag information, more precisely, longitude, latitude, and orientation (heading to the north) 2 . Similar to [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF], [START_REF] Torii | Visual place recognition with repetitive structures[END_REF], we cut 24 perspective images of 1, 920 × 1, 440 pixels, with a 60 • field-of-view and 50% overlap to the neighboring views, from each panorama. For each query image, we use the 240 perspective images corresponding to the 10 GSVTM panoramas spatially closest to the most relevant PCI image.

We run SfM on the query, PCI images, and GSVTM perspective images. For redundancy, both COLMAP [START_REF] Schönberger | Structure-From-Motion Revisited[END_REF] and Visu-alSFM [START_REF] Wu | Multicore bundle adjustment[END_REF], [START_REF] Wu | Towards Linear-time Incremental Structure From Motion[END_REF] are used to obtain two SfM reconstructions.

2. GSVTM provides two location and orientation estimates, the original GPS information and geo-tags obtained via some alignment. We use the former as they are better aligned with the geo-tags of the PCI images.

Geo-registration with gravity constraint. In order to obtain the global positions and orientations of the cameras in each local reconstruction, we transformed the local model coordinate system to UTM coordinates. We first convert the GPS tags of the PCI and GSVTM images to UTM. Since the geo-tags do not include the height of the cameras above ground, we set it to zero. We then estimate the similarity transform between the camera positions in the model and their UTM coordinates.

A naive approach to geo-registration is to calculate a 7DOF similarity transform (scale, rotation, translation) between the SfM camera positions and the UTM coordinates of the database images [START_REF] Sattler | Are large-scale 3D models really necessary for accurate visual localization?[END_REF]. However, this results in unstable estimates in degenerated camera configurations. A common degenerate configuration in our setting is that the cameras used for an SfM reconstruction align on a straight line since the car drives down a road.

This degenerated camera configuration problem can be addressed using the gravity direction computed from the SfM model. We first assume that all the PCI and GSVTM perspective images are aligned with respect to the gravity direction in UTM coordinates. Each camera pose in the SfM model and its pitch angle in UTM give a mapping of the gravity direction in UTM to the SfM coordinates. We determine the gravity direction in the SfM coordinates by taking a median of all the mapped gravity directions. Using this median gravity direction, we rotate the SfM model and finally compute a 5DOF similarity transform (1D scale, 1D rotation, and 3D translation), using LO-RANSAC with a 1 meter tolerance threshold3 .

Verification.

Besides not being able to register the query image in the model, there are multiple ways a SfM reconstruction might provide an inaccurate estimate for a query's camera pose. For example, only few matches might be found or the correspondences might be in an unstable configuration, e.g., all matches are situated in a small region of the query image. Consequently, we verify the poses after the registration process through consistency checks.

Let Q be the query image for which we want to verify the estimated pose and let D be the PCI image we selected for it. Using D and the SF-0 model, also registered to UTM coordinates, we generate a set of 2D-3D matches for the query image Q. From the SF-0 model, we obtain a list of 3D points visible in D. We project these 3D points into D to obtain 2D pixel positions, which we use to manually annotate the corresponding image positions in the query image. This results in a set of 2D-3D matches and, as a side product, also produces a set of 2D-2D correspondences between Q and D. To obtain additional correspondences, we manually annotate 20 to 50 2D-2D matches between D and Q. We use all these 2D-2D matches to compute the relative pose between the two images and use the 2D-3D matches to determine the scale of the translation. The resulting pose in UTM coordinates is then refined using bundle adjustment [START_REF] Agarwal | Ceres solver[END_REF]. Ideally, this procedure should result in a precise estimate of Q's camera pose. However, it is hard to obtain accurate manually annotated pixel matches, resulting in some inaccuracy on the pose. We thus use it for a consistency check on the absolute camera pose. The check accepts a SfM pose if it is inside 10 meters of the position and within 15 • of the view angle of the pose obtained from the manual matches.

A second consistency check employs the manually annotated 2D-2D matches between D and Q. From each of the two SfM models, we extract the essential matrix E describing the relative pose between the two images. For a given 2D-2D match (x Q , x D ), we measure the pixel distances from the epipolar lines defined by E and E -1 . E is considered to be consistent with the match if both errors are less than 3 pixels each. We consider a pose obtained by SfM to be consistent with this relative check if E is consistent with at least 10 of the manually annotated matches.

For each query image, a pose obtained by COLMAP or Visu-alSFM is accepted as a reference pose if it passes one of the two consistency checks. If poses from both COLMAP and VisualSFM pass this test, we select the one estimated by COLMAP.

Statistics. We created manual annotations for 687 out of the 803 query images from the SF dataset. Table 2 shows statistics on how many SfM poses, obtained with either COLMAP or VisualSFM, pass the two consistency checks. Finally, we obtain 598 reference poses that are consistent with our manual annotations. For comparison, we only obtained 442 reference poses without using the additional GSVTM images.

Reference pose accuracy. In the next sections, we present the image-and structure-based localization methods that we evaluate using our reference poses in section 6. In order to draw valid conclusions, it is however necessary to understand the accuracy of these poses. We thus measure the uncertainty of the estimated poses as follows: Using RANSAC, we compute multiple poses from a subset of the 2D-3D matches used for each reference pose. From the resulting 100 poses, those supported by more than 80% of the 2D-3D matches are used to measure the differences to the reference pose. The mean median position and orientation errors are 1.01 meters and 2.19 • .

The accuracy of any pose estimation approach, including SfM, that minimizes reprojection errors depends on the distance of the camera to the scene. More precisely, the uncertainty of the estimated pose grows roughly quadratically with the distance to the scene. On average, a query image is 10.5 meters away from its selected PCI image and 35.6 meters away from the 3D structure estimated during SfM. We thus consider the reference poses to be reasonably accurate.

We also measured the positional gap between the geo-tags of the PCI and the reconstructed PCI cameras registered in UTM coordinates. The mean average positional discrepancy is 0.39 meters, i.e., the UTM coordinates estimated by SfM reconstruction and registration are consistent with the geo-tags of the PCI images.

2D IMAGE-BASED LOCALIZATION

The introduction posed the question whether 2D image-based localization approaches can achieve the same pose accuracy as structure-based methods. In other words, we are interested in determining whether an underlying 3D representation is necessary for high localization precision or whether a database of geo-tagged images can be sufficient.

In the following, we first review the 2D image-based methods that we chose for evaluation. We then explain different strategies to obtain camera poses of the query images using photos retrieved by the image-based methods.

Disloc [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF], [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF] is a state-of-the-art method based on the BoW paradigm and Hamming embedding [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. During the voting stage of the retrieval pipeline, Disloc takes the density of the Hamming space into account to give less weight to features found on repeating structures while emphasizing unique features.

We also use the combination of Disloc with the geometric burstiness weighting scheme recently proposed in [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF]. Given a list of spatially verified database images found by Disloc, the weighting strategy clusters these photos into places based on their geo-tags. It identifies features in the query image that are inliers to database photos coming from different places, i.e., features found on repeating structures. Finally, the strategy performs a second reranking step where such features have less influence, which has been shown to improve landmark recognition performance.

DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. Disloc is based on the BoW paradigm and thus needs to store one entry per each image feature in an inverted file. This quickly leads to high memory requirements for large-scale scenes such as San Francisco. The DenseVLAD descriptor [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] is an example for a state-of-the-art localization algorithm based on compact image representations. Each image is represented by a single VLAD vector [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], [START_REF] Arandjelović | All about VLAD[END_REF], resulting in a more compact database representation. The DenseVLAD descriptor is constructed by aggregating RootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] descriptors densely sampled on a regular grid in each image. As such, the method foregoes the feature detection stage, which has been shown to lead to more robust retrieval results, especially in the presence of strong illumination changes [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Sattler | Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions[END_REF].

NetVLAD [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF]. The DenseVLAD descriptor is based on handcrafted RootSIFT descriptors. In contrast, the NetVLAD representation uses a convolutional neural network to learn the descriptors that are aggregated into a VLAD vector. Training this representation in an end-to-end manner using a weakly supervised triplet loss has been shown to improve place recognition performance over DenseVLAD and other compact image descriptors.

Pose Estimation for 2D-based Approaches

Nearest neighbor (NN). Traditionally, most 2D image-based methods approximate the pose of the query image by the pose of the most relevant database image, i.e., the database photo with the most similar BoW or VLAD descriptor. We use this strategy as a baseline and refer to it as Nearest Neighbor (NN) pose.

Spatial re-ranking (SR). Re-ranking the retrieved database images after spatial verification is known to improve image retrieval performance. As a second baseline, we use the pose of the best-matching database image after verification and refer to this strategy as Spatial Re-ranking (SR) pose. We perform spatial verification [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] for the top-200 retrieved images. For Disloc, we exploit the matches computed during the retrieval process while we extract and match RootSIFT features for both VLAD-based methods. For the VLAD-based methods, we re-rank based on the raw number of inliers. For Disloc, we also experiment with re-rank based on the geometric burstiness score.

SfM-on-the-fly (SfM). The previous two pose estimation strategies only consider the top-ranked database image. They ignore that each 2D-based approach typically retrieves multiple database images depicting the same place. In addition, the geo-tags of the database photos can also be used to identify a larger set of potentially relevant images. Inspired by [START_REF] Schönberger | From Single Image Query to Detailed 3D Reconstruction[END_REF], who generate a SfM model from a single photo by repeatedly querying an image database, we use small-scale SfM to obtain a local 3D model around the query image. Poses in the local model can then be converted into global poses by registering the SfM reconstruction into UTM coordinates based on the geo-tags of the database images. We refer to this strategy as SfM-on-the-fly (SfM).

For 2D image-based methods, we generate a small subset from the top-200 retrieved images which are located within 25 meters from the pose obtained via the NN or SR strategy. We use COLMAP on the selected photos to obtain the 3D reconstruction. If COLMAP fails to recover the pose of a query camera, e.g., when the reconstruction fails, we resort to the NN or SR pose.

A naive implementation of SfM-on-the-fly constructs a local model from scratch and ignores the fact that the poses of the database images are available. We thus also evaluate a version (SfM init.) that uses these known poses for initialization. This accelerates the reconstruction process and also makes it more robust. Compared to 3D-based methods, this approach achieves a higher pose accuracy.

Another approach to accelerate the local SfM process is to avoid exhaustive matching between all images. In order to reconstruct the query pose, database images with feature matches to the query image are most relevant. We thus also experiment with a transitive matching strategy (trans.). We first match the query image against all retrieved database images. We then match two database images against each other only if each has a sufficient number of matches with the query image.

3D STRUCTURE-BASED LOCALIZATION

This section reviews the two large-scale 3D structure-based localization methods used in this paper and justifies their selection.

Camera Pose Voting (CPV) [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. Following [START_REF] Svärm | City-Scale Localization for Cameras with Known Vertical Direction[END_REF], CPV assumes that the gravity direction, both in the local coordinate system of the camera and the global coordinate frame of the 3D model, is known together with a rough prior on the camera's height above the ground and its intrinsic calibration. In this setting, knowing the height of the camera directly defines the distance dist(p) of the camera to a matching 3D point p up to ±ε, where ε is a small distance modeling the fact that the point might not re-project perfectly into the image. Thus, the camera's center falls into a circular band with minimum radius dist(p) -ε and maximum radius dist(p) + ε around p. As shown in [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF], fixing the final 4 orientation angle of the camera also fixes the position of the camera inside the circular band.

The last observation directly leads to the camera pose voting scheme from [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]: Iterating over a set of discrete camera heights (defined by the coarse height prior) and a set of discrete camera orientations, each 2D-3D match votes for a 2D region 5 in which the camera needs to be contained. The matches voting for the cell receiving the most votes define a set of putative inliers and the position of the cell, together with the corresponding height and orientation, provides an approximation to the camera pose. This approximation is then refined by applying RANSAC with a 4. The other angles are already fixed by knowing the gravity direction. 5. Regions account for the discretization of the pose parameters.

3-point-pose (P3P) solver on these matches. If available, a GPS prior can be used to further restrict the set of plausible cells and thus possible camera positions.

CPV was selected for our evaluation as [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF] report state-ofthe-art pose accuracy on the Dubrovnik dataset [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF] and the stateof-the-art landmark recognition performance on the San Francisco dataset among structure-based localization methods.

Hyperpoints (HP) [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF]. Rather than using Lowe's ratio test, which enforces global uniqueness of a match in terms of descriptor similarity, the HP method searches for locally unique matches [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF]. It uses a fine visual vocabulary of 16M words [START_REF] Mikulík | Efficient image detail mining[END_REF] to define the similarity between the descriptor d(f ) of a query image feature f and the descriptor d(p) of a 3D point p based on a ranking function:

p has rank r(p, f ) = i if d(p) falls into the i-th nearest visual word of d(f ). The point's rank is r(p, f ) = ∞ if d(p)
does not fall into any of the k = 7 nearest words of d(f ). A 2D-3D match (f, p) is locally unique if there exists no other 3D point p that is co-visible with p and has r(p , f ) ≤ r(p, f ). Two points are co-visible if they are observed together in one of the database images used to reconstruct the model.

Each locally unique 2D-3D match (f, p) votes for all database images observing p and the top-N images with the most votes are considered for pose estimation. Let D be one of these database images. All matches whose 3D point is visible in D as well as all matching points visible in nearby images are used for RANSACbased pose estimation. Two images are considered nearby if they share at least one jointly observed 3D point in the SfM model. Considering points outside D increases the chance of obtaining more correct matches. Restricting the additional matches to nearby cameras avoids considering unrelated matches, thus avoiding high outlier ratios in RANSAC.

After computing a camera pose for each retrieved database image, the pose with the highest effective inlier count is selected. The effective inlier count takes both the number of inliers and their spatial distribution into account [START_REF] Irschara | From Structurefrom-Motion Point Clouds to Fast Location Recognition[END_REF].

HP was selected as it represents a hybrid between 2D imagebased and 3D structure-based localization methods. In addition, HP also outperforms other structure-based approaches employing retrieval techniques [START_REF] Irschara | From Structurefrom-Motion Point Clouds to Fast Location Recognition[END_REF], [START_REF] Sattler | Image Retrieval for Image-Based Localization Revisited[END_REF], [START_REF] Cao | Minimal Scene Descriptions from Structure from Motion Models[END_REF] at large scale.

Active Search (AS) [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF]. CPV and HP have been designed to operate at large-scale. We compare their performance with Active Search, a state-of-the-art method for efficient localization at small-to-medium scale [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF], [START_REF] Walch | Image-based localization using LSTMs for structured feature correlation[END_REF]. AS relies on Lowe's ratio test to identify and reject ambiguous matches. As the ratio test rejects more and more correct matches at scale [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF], we expect AS to localize significantly fewer images than CPV and HP. The comparison with AS thus serves to demonstrate the challenges encountered when scaling to larger, more complex scenes.

EXPERIMENTS

This section uses our new reference poses to compare the localization accuracy of 2D image-and 3D structure-based methods. After describing the experimental setup and the evaluation protocol, we quantitatively evaluate the different approaches. We then discuss the results and their relevance.

Experimental setup. For Disloc [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF], [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF], DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], and NetVLAD [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF], we use source code provided by the authors for our evaluation. Disloc uses a visual vocabulary of 200k words trained on a subset of all database images. DenseVLAD uses a dictionary with 128 words also trained on the SF dataset, while NetVLAD uses 64 words. Unfortunately NetVLAD does not provide a version fine-tuned on San Francisco. Instead, we use the variant trained on the Pitts30k dataset [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF]. Both DenseVLAD and NetVLAD generate 4,096 dimensional descriptors. For Hyperpoints (HP) [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], Camera Pose Voting (CPV) [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF], and Active Search (AS) [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF], we use poses estimated on the SF-0 dataset [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF] as all methods use an SfM model to represent the scene. We run AS with vocabularies with 10k and 100k words, trained on the 3D point descriptors of the SF-0 dataset. We denote structure-based models by "(3D)" in the tables and legends.

Evaluation metric. We are mostly concerned with the pose accuracy achieved by the different methods. We measure the positional error in UTM coordinates since the local models used to construct the reference poses and the SF-0 reconstruction are registered to this coordinate system. However, the SF dataset only provides geodetic latitudes and longitudes of the cameras and not the altitudes. Thus, there is one degree of freedom in these registrations, namely the height above the plane defined by graticule. Accordingly, we measure the position error in 2D coordinates and evaluate how many images can be correctly localized by the different methods within a certain distance threshold.

In addition to the positional error, measured in meters, we also measure the orientation error. Given the reference camera orientation R ref and the estimated query orientation R Q , both expressed as rotation matrices, we measure the angular error |α| between the two orientations as 2 cos(|α|

) = trace(R ref R Q ) -1 [85].

Quantiative Evaluation

We first evaluate the positional and orientational accuracy achieved by the 2D image-based methods. We compare the accuracy obtained when using the pose of the best-matching database image after retrieval (NN), the pose of the best-matching image after spatial verification (SR), and after local SfM reconstruction (SfM). The latter resorts to the NN (NN-SfM) and SR (SR-SfM) strategies if a pose cannot be estimated from the local model.

Figures 3 and4 show results for BoW-based methods (a) and VLAD-based methods (b). As can be seen, spatial re-ranking (SR) increases the chance that the top-ranked database image is related to the query, i.e., that the position and orientation of the retrieved database photo is close to the reference pose of the query. As a result, more query images can be correctly localized for larger distance thresholds. However, SR does not improve performance much in the high-accuracy regime. The reason is that the database images of the SF dataset were captured from a car driving on the road while the query photos were taken by pedestrians on the sidewalks. Thus, there is a certain minimal distance between their respective locations. A much better estimate can be obtained when using local SfM models (SfM), boosting the percentage of queries localized correctly within 5m from below 20% to about 60%. Similarly, local SfM improves the orientation accuracy by a large margin for smaller thresholds (0 • to 20 • ). Interestingly, SR-SfM degrades the orientation accuracy compared to SR for angular errors above 20 • (c.f . figure 4). This indicates that the orientation estimates provided by SfM can sometimes be rather inaccurate. As can be seen from the results in (c), using known poses for the database images (SfM init.) rater than computing them from scratch improves pose accuracy.

We observe that Disloc with inter-place geometric burstiness [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF] (Disloc (SR * )) shows no additional improvement in comparison with the original Disloc (SR) [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF] in this dataset. Disloc (SR * -SfM) uses relatively smaller subsets of images because Disloc (SR * ) clusters relevant images by their geo-tags. This changes the quality of local reconstructions. This is an interesting result as [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF] showed that accounting for geometric burstiness leads to a better location recognition performance. Our result thus indicates that better location recognition performance does not automatically translate to better camera pose accuracy.

For the VLAD-based representations, we notice that NetVLAD with the NN strategy performs worse than DenseVLAD (NN). DenseVLAD has the advantage that its vocabulary was trained on SF, while NetVLAD was trained on another dataset. However, their performance is virtually the same in combination with spatial re-ranking and local SfM. In the following, we focus on DenseVLAD and do not use NetVLAD for further experiments.

Figures 3(c) and 4(c) compare the positional and orientational accuracy of the best-performing 2D-based approaches with the two structure-based methods, Hyperpoints (HP) and Camera Pose Voting (CPV). As can be seen, both Disloc and DenseVLAD perform as good as HP for queries with an smaller error (2m and 5 • ) when using SfM as a post-processing step. 2D-based approaches are able to localize more images overall. If a pose cannot be estimated via local SfM, the 2D-based methods resort to reporting the position of the highest-ranking database image. The overall lower percentage of localized images observed for HP and CPV comes from such cases. For these images, their 2D-3D matching stage fails to produce enough matches for pose estimation. The interesting implication is that it is still possible to find relevant database images even when pose estimation itself fails due to a lack of matches.

Many interesting applications, e.g., self-driving cars, require highly accurate poses. In order to better understand the behavior of 2D-based and 3D-based methods in the high-precision regime, we compare their performance on two subsets of our reference poses. The first subset, containing 334 poses, is constructed from all reference poses for which either COLMAP or VisualSFM provides a pose that passes both consistency checks explained in section 3.1. This subset represents the more accurate among all of our reference poses. The second subset contains all 142 poses where both reconstructed poses pass both tests, thus containing the reference poses most likely to be highly accurate. Figure 5 depicts the performance of the different methods on both subsets. We again observe that HP performs better in the error range 2.5m to 9.0m than DenseVLAD (SfM) and Disloc (SfM). Yet, the best performance is again obtained using the SfM init. strategy. This clearly demonstrates that using known database poses for initialization increases the robustness of the SfM process. Based on the results, we conclude that large-scale 3D models are not really necessary for highly accurate visual localization.

The previous experiment considered the orientation and position errors separately. Following [START_REF] Sattler | Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions[END_REF], [START_REF] Shotton | Scene coordinate regression forests for camera relocalization in RGB-D images[END_REF], we next jointly consider both errors. Table 3 shows the percentage of query images that are localized within certain thresholds on the position and orientation error. The best results are clearly obtained by DenseVLAD (SR-SfM init.). The transitive matching strategy accelerates the local SfM process, but also decreases pose accuracy slightly. For more relaxed thresholds (25-30 meters, 20 degrees), 2D-based methods (DenseVLAD / Disloc (SR-SfM)) show better a recall than 3D-based methods (HP and CPV). Overall, imagebased method can achieve a similar or higher performance than structure-based methods without a single consistent 3D model. We next evaluate positional and orientational accuracy in a single unit, i.e., pose accuracy, by computing reprojection errors. As described in section 3.1, the accuracy of any approach that estimates a camera pose by minimizing a reprojection error depends on the scene. Consequently, we can expect larger errors if the image is taken rather far away from the scene. In contrast, the mean reprojection error does not depend the distance to the scene.

To compute the reprojection errors, we retrieve 2D-3D correspondences associated with the query reference pose. The reprojection errors are calculated by projecting 3D points to the image plane of the estimated query pose and computing the distances to the reference 2D points. Table 4 shows the mean reprojection error for each method. Not surprisingly, the patterns of results are similar to the positional and orientational accuracy evaluations. The higher errors of DenseVLAD / Disloc (SR-SfM) for the 75% quantile result from resorting to image retrieval if local SfM fails.

Using positional priors. At large scale, it is often reasonable to assume that some coarse positional prior is given, e.g., via GPS / WiFi localization. This prior can then be used to simplify the localization problem by restricting the search space. For example, image-based methods can restrict the search for relevant images to a certain radius around the positional prior of a given query [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. Similarly, CPV can use such a regional prior to restrict the voting space [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. We extend AS to use a position prior by restricting 2D-to-3D matching to points within 200 meters of the prior.

As can be seen in tables 3 and 4, using a pose prior for CPV has little impact on camera pose accuracy. This is an interesting observation and its relevance will be discussed in detail in section 6.3.

In contrast, AS clearly benefits from the prior, which is due to its use of Lowe's ratio test. The prior allows AS to ignore some 3D points during matching. This results in a sparser descriptor space and thus decreases the chance that the ratio test rejects correct matches. Still, AS localizes significantly fewer images than CPV, even with the prior. The original GPS measurements provided with the SF dataset are rather noisy, with errors of up to 150 meters [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. These measurements were obtained with rather old hardware and software. We thus generate a more accurate positional prior by randomly sampling a position from a region which centers our reference pose and has a radius of 50 meters. We then incorporate the GPS priors into the 2D image-based methods. Figure 6(a) evaluates the localization performances for a search radius of 100 meters. As can be seen from the plots, using a GPS prior improves the localization performance of DenseVLAD.

We next evaluate the robustness of the localization to the search radius. In figure 6(b), both DenseVLAD (SR+GPS) and DenseVLAD (SR-SfM+GPS) show the best performances with the 50 meters radius, which is equal to the GPS uncertainty. This result is in line with the observation reported by Chen et al. [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF]. DenseVLAD (SR-SfM) robustly retains its localization rate at the larger searching radius as it accurately estimates the pose of the query image. In contrast, we notice a significant drop in performance for DenseVLAD (SR) as it approximates the pose of the query through the pose of the top-retrieved database image.

Memory requirements. When dealing with large-scale datasets, the memory required to represent the scene is no longer a negligible issue. In the following, we summarize the memory requirements of each method. Here, we focus on the amount of data that needs to be kept in main memory during processing. For example, the image-based methods need access to the original images for the local SfM stage. However, these images could be read from disk after the initial retrieval step.

Storing 4096-dimensional VLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF], [START_REF] Arandjelović | NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[END_REF] for all 1,062,468 database images requires 17.4GB, and the requirements can be reduced further, e.g., using product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], with negligible loss in performance [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF]. For comparison, the DisLoc implementation from [START_REF] Sattler | Large-Scale Location Recognition and the Geometric Burstiness Problem[END_REF] requires about 20GB, although its memory footprint could be reduced to about 9.4GB by storing quantized feature geometry [START_REF] Chum | Total Recall II: Query Expansion Revisited[END_REF]. As reported in [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], the Hyperpoints approach requires 4.9GB to store the 3D model information and the visual vocabulary. In contrast, camera pose voting [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF] uses all 149.3M SIFT descriptors of the SF-0 model for matching, thus requiring more than 18GB of memory. The memory footprint could be reduced to about 4.9GB by storing a single mean descriptor for each of the 30M 3D points, although this might reduce the localization performance. The two best-performing methods (Disloc and Hyperpoints) show similar localization accuracy but Hyperponts has five times smaller memory footprint. AS requires about 15GB of storage space and the difference in memory requirements for different vocabulary sizes is negligible.

Timings. Table 6 shows timings for the online components of the different algorithms, evaluated on Dubrovnik dataset. As can be seen, DenseVLAD (SR-SfM) is significantly slower than all other methods. This is unsurprising as it avoids the need for generating and maintaining a single 3D model by computing small 3D models on the fly. It thus trades flexibility for run-time. The corresponding run-times for the San Francisco dataset are shown in table 3. Note that local SfM is less efficient on the Dubrovnik dataset due to larger image resolutions, resulting in more extracted features.

Computing the DenseVLAD and NetVLAD descriptors for Dubrovnik's 6044 database images took 2.4h and 0.85h, respectively. While we use existing 3D models for Dubrovnik and SF-0, we expect that reconstructing the datasets from scratch takes less than 1 day and about 1-2 weeks, respectively. HP requires about 3s per image for online processing on SF-0.

Table 5 provides more detailed timings for the different Impact of different variations of SfM-on-the-fly on timings and performance. We provide the average computation time for each component of SfM-on-the-fly, and the percentage of queries that are localized within the thresholds by each method. variants of SfM-on-the-fly discussed in section 4.1, together with the impact of the modifications on pose accuracy. These timings were obtaining for COLMAP, using a GPU for feature extraction and parallelization for matching and reconstruction. As can be seen, most of the time is spent on the incremental reconstruction process. Using known database poses for initialization decreases the reconstruction time by a factor of about 3 while also increasing localization performance. Using transitive matching improves the matching times at a slight reduction of pose accuracy at the stricter thresholds. Feature extraction could be accelerated at the price of memory by pre-extracting features for the database images.

Qualitative Results.

We next show some qualitative examples to visually investigate when and how 2D image-and 3D structure-based methods work. Based on the quantitative results, we choose the methods for 2D image-and 3D structure-based localization as Disloc (SR-SfM) and Hyperpoints (HP). We chose (SR-SfM) rather than (SR-SfM init.) to illustrate potential failure cases and since the former only requires coarse geo-tags for the database images. Figures 7 and8 show examples of query images correctly localized within 5m of the reference position by Disloc (SR-SfM) but not HP, respectively localized within 5m by HP but not by Disloc. Similarly, figures 9 and 10 show examples for which Disloc respectively HP provide pose estimates within 30m whereas the other method is less accurate.

HP uses quantized decriptors for matching. As a result, it has problems handling scenes with dominantly repetitive and similar structural elements. In contrast, Disloc (SR-SfM) uses the full feature descriptors and thus handles these scenes better.

However, Disloc (SR-SfM) has problems with accurately lo- calizing images taken rather far away from the scene. This problem is compounded if the scenes are weakly textured. In this scenario, the local 3D models build from a few PCI images via SfM are less precise than the global model build used by HP. This reflects in the localization accuracy of Disloc (SR-SfM). If the viewpoint change between the retrieved PCI images and the query image is too large, the local SfM reconstruction process often fails to register the query image. In these cases, Disloc (SR-SfM) defaults to the pose provided by the (SR) strategy.

Relevance of the Results.

To put the results obtained at large scale with our references poses into context, we provide results on the medium-scale Dubrovnik dataset [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF]. The 3D model consists of 1.9M 3D points reconstructed from 6044 database images. Table 6 compares the DenseVLAD variants with CPV and AS. In addition, we also provide results for PoseNet [START_REF] Kendall | PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization[END_REF], [START_REF] Kendall | Geometric loss functions for camera pose regression with deep learning[END_REF], a learning-based approach. HP is not applicable for this dataset as it was designed for larger-scale scenes where memory consumption and matching quality are issues. On the Dubrovnik dataset, the fine vocabulary of 16M words used by HP already requires more memory than the complete dataset. As can be seen from table 6, combining DenseVLAD with local SfM results in a localization accuracy comparable to Active Search but worse than CPV. The opposite is the case for the larger SF-0 model, where DenseVLAD (SR-SfM) is clearly more precise. The reason is that finding good matches is easy on the smaller and well-textured Dubrovnik dataset while it is extremely challenging for the significantly larger SF-0 model. This is evident when comparing CPV's median positional accuracy on Dubrovnik (0.56m) and SF-0 (>2m). The matching step of local SfM is able to recover matches lost by CPV, enabling more accurate poses at large scale. The pose accuracy of DenseVLAD (SR-SfM) strongly depends on the quality of the local 3D models. Here, the SF-0 model is better suited due to the regular spatial distribution of its database images. In contrast, the spatial density of Dubrovnik's database photos varies strongly, making it harder to obtain good local models for some query images.

An interesting observation can be made from the relative performance between HP and CPV on SF-0. Previously, the SF dataset was used to evaluate the performance of structure-based localization methods in a landmark recognition scenario [START_REF] Li | Worldwide Pose Estimation Using 3D Point Clouds[END_REF], [START_REF] Sattler | Hyperpoints and fine vocabularies for large-scale location recognition[END_REF], [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF]. In this scenario, an image was considered correctly localized if it observed the correct building as specified by the building IDs provided by the SF dataset. Methods are evaluated based on their recall@95% precision, i.e., based on the percentage of correctly localized images if the algorithm is allowed to make a mistake in 5% of all cases. In this scenario, CPV achieves a recall of TABLE 6 Additional comparison on the Dubrovnik dataset [START_REF] Li | Location Recognition using Prioritized Feature Matching[END_REF].

Time

Quantile errors [m] Method

[sec] 25% 50% 75% DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] (NN) 1.42 1.4 3.9 11.2 DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] (SR)

1.43 0.9 2.9 9.0 DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] (SR-SfM) ∼200 0.3 1.0 5.1 DisLoc [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF] (NN) 11.28 1.1 3.7 11.1 DisLoc [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF] (SR) 11.29 0.9 2.9 8.9 DisLoc [START_REF] Arandjelović | DisLocation: Scalable descriptor distinctiveness for location recognition[END_REF] (SR-SfM) ∼200 0.5 1.9 9.4 Camera Pose Voting (CPV) (3D) [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF] 3.78 0.19 0.56 2.09 Active Search (3D) [START_REF] Sattler | Efficient & effective prioritized matching for large-scale image-based localization[END_REF] 0.16 0.5 1.3 5.0 PoseNet [START_REF] Kendall | PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization[END_REF], [START_REF] Kendall | Geometric loss functions for camera pose regression with deep learning[END_REF] ∼0.005 -7.9 -67.5% and 74.2% without and with a GPS prior, respectively. In contrast, HP only obtains a recall of 63.5%. This shows that good performance on the landmark recognition task does not necessarily translate to pose accuracy.

Another interesting observation can be made from the results obtained with CPV and a pose prior. In [START_REF] Zeisl | Camera pose voting for large-scale image-based localization[END_REF], including a pose prior improved landmark recognition performance. Yet, we observe no improvement in pose accuracy. This behavior is due to a peculiarity of the landmark recognition protocol: In order to increase the recall@5% precision, a large margin between the scores of correct and incorrect results is desirable. CPV uses the GPS prior to restrict the camera pose voting space, thus reducing the number of votes for incorrect poses. This, in turn, allows CPV to better distinguish between correct and incorrect poses. As such, our new dataset closes a crucial gap in the literature as it enables measuring pose accuracy at a large scale.

Regarding the performance of PoseNet, we observe that simply approximating the pose of a query image via the pose of the topretrieved database image (DenseVLAD (NN)) already provides more accurate pose estimates. This shows that pose regression techniques such as PoseNet currently do not scale well. This is in line with reports from other work, which reports problems when trying to train such methods in more complex scenes [START_REF] Schönberger | Semantic Visual Localization[END_REF], [START_REF] Sattler | Benchmarking 6DOF Outdoor Visual Localization in Changing Conditions[END_REF], [START_REF] Taira | InLoc: Indoor visual localization with dense matching and view synthesis[END_REF].

Comparing the results obtained with Active Search on SF-0 (table 3) and Dubrovnik (table 6), we observe that AS scales well in terms of run-time. Part of this is due to the fact that the query images for Dubrovnik contain about five times more features on average, which compensates for the larger model size of SF-0. Yet, AS localizes significantly fewer images on the larger dataset. This demonstrates the need to also consider pose accuracy when evaluating the scalability of localization methods.

CONCLUSION

In this paper, we have presented the first comparison of 2D imagebased and 3D structure-based localization methods regarding their localization accuracy at a large scale. To facilitate this comparison, we have created reference poses for some query images from the San Francisco dataset [START_REF] Chen | City-Scale Landmark Identification on Mobile Devices[END_REF].

Our results show that purely 2D-based methods achieve the lowest localization accuracy. However, they offer the advantage of efficient database construction and maintenance and can localize images even if local feature matching fails. In contrast, 3Dbased methods offer more precise pose estimates at the price of significantly more complex model construction and maintenance. Feature matching becomes harder at large-scale and finding fewer matches results in a lower pose quality. Combining 2D-based methods with local SfM reconstruction takes the advantages of both worlds, simple database construction and high pose accuracy, and results in state-of-the-art results for large-scale localization. However, this comes at the price of longer run-times during the localization process. Still, there is potential to accelerate this stage, e.g., by caching local reconstructions. Alternatively, one could represent the scene using multiple smaller modes instead of a single large 3D model.

To the best of our knowledge, ours is the first dataset that can be used to measure the pose estimation accuracy on a large, complex dataset. Our results show that our dataset closes a crucial gap in the literature as this case is not covered by previous benchmarks and evaluation protocols. Our results show that there is still room for improvement in terms of pose precision. We make our reference poses, as well as all data required for evaluation, publicly available to facilitate further research on this topic.

Fig. 1 .

 1 Fig. 1. The state-of-the-art for large-scale visual localization. 2D imagebased methods (bottom) use image retrieval and return the pose of the most relevant database image. 3D structure-based methods (top) use 2D-3D matches against a 3D model for camera pose estimation. Both approaches have been developed largely independently of each other and never compared properly before.

Fig. 2 .

 2 Fig.2. The San Francisco dataset with the reference poses of query images. We provide the reference poses of query images (blue) which can be used as the ground truth for large-scale localization benchmarks on the SanFrancisco dataset.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Evaluation of the positional localization accuracy for BoW-based methods (a), VLAD-based approaches (b), and when comparing 2D-and 3D-based methods (c). Each plot shows the fraction of correctly localized queries (y-axis) within a certain distance to the reference pose (x-axis).As can be seen, using local SfM reconstructions (SfM) to estimate the camera poses allows 2D-based methods (Disloc, DenseVLAD) to achieve a positional accuracy similar or superior to 3D-based methods (Hyperpoints (HP), Camera Pose Voting (CPV)).

Fig. 5 .Fig. 6 .

 56 Fig. 5. Localization accuracy subsets of the reference poses, selected to include more accurate camera poses: (a) reference poses from either COLMAP or VisualSFM passing both consistency checks (334 reference poses) and (b) reference poses where both reconstructions pass both checks (142 poses). For each subset, we evaluate both positional (left) and orientational (right) accuracy for 2D-and 3D-based localization methods.

Fig. 7 .

 7 Fig. 7. Examples of query images localized within 5m of the reference poses by a 2D image-based method (Disloc (SR-SfM)) (left) but not by a 3D structure-based method (Hyperpoints) (middle). Colored dots are the reference 2D points used for computing the reference pose (blue) and the 3D points, associated to the reference 2D points, reprojected at the pose estimated by each method (red). The numbers below the images show the positional and orientational errors. The right column shows manually selected database PCI images that are most relevant to the queries.

Fig. 8 .

 8 Fig. 8. Examples of query images localized within 5m of the reference position by a 3D structure-based method (Hyperpoints) (middle) but not by a 2D image-based method (Disloc (SR-SfM)) (left). See caption of figure 7 for details.

Fig. 9 .

 9 Fig. 9. Examples of query images localized within 30m of the reference position by a 2D image-based method (Disloc (SR-SfM)) (left) but not by a 3D structure-based method (Hyperpoints) (middle). The right column shows manually selected database PCI images that are most relevant to queries. "(*)" besides the results for Disloc (SR-SfM) indicate that local SfM fails so the results are the same as Disloc (SR). See also the caption of figure 7.

Fig. 10 .

 10 Fig. 10. Examples of query images localized within 30m of the reference position by a 3D structure-based method (Hyperpoints) (middle) but not by a 2D image-based method (Disloc (SR-SfM)) (left). See the caption of figure 9 for details.

TABLE 1

 1 System-level summary of visual localization approaches.

		2D image-based localization	3D structure-based localization
	Scene representation	Database of geo-tagged images	3D points with associated image descriptors
	Approach	Image retrieval	Descriptor matching followed by pose estimation
	Output	Set of database images related to query,	6DOF camera pose of the query image
		coarse position estimate	(position and orientation)
	Advantage	Easy to maintain / update database	Directly provides pose estimates
	Disadvantage

TABLE 2

 2 Statistics on the consistency of the reconstructed SfM poses with our manual annotations.

	Method \Consistency Test	Absolute	Relative	Both
	COLMAP	311	553	306
	VisualSFM	269	279	170
	COLMAP & VisualSFM	228	245	142

TABLE 3

 3 Localization performance depending on the positional and orientational errors. For each pair of thresholds, we provide the percentage of queries that are localized within the thresholds by each method.

		Time	Thresholds [meters, degrees]
	Method	[sec] 5, 5 10, 5 15, 10 20, 10 25, 20 30, 20
	DenseVLAD (SR-SfM)	18.38 57.02 58.03 68.56 69.73 80.43 80.77
	DenseVLAD (SR-SfM init.) 9.08 66.89 67.39 77.76 78.43 85.79 86.12
	+trans.	7.26 63.71 64.55 77.26 77.93 85.62 85.95
	Disloc (SR-SfM)	18.38 57.19 58.53 69.06 70.40 81.94 82.11
	AS, 10K w/o GPS (3D)	0.62 27.42 27.76 33.44 33.44 35.79 35.79
	AS, 10K w/ GPS (3D)	0.66 35.79 36.62 43.81 43.98 44.98 45.15
	AS, 100K w/o GPS (3D)	0.09 29.43 29.93 35.95 36.12 37.46 37.46
	AS, 100K w/ GPS (3D)	0.12 34.28 35.28 42.64 42.64 43.81 43.81
	Hyperpoints (3D)	∼3 55.85 57.53 72.24 72.41 76.76 76.92
	CPV w/ GPS (3D)	∼3 38.63 43.14 62.21 62.71 70.23 70.74
	CPV w/o GPS (3D)	∼3 38.63 42.98 61.20 62.04 69.06 69.23

TABLE 4

 4 Quantiles for mean reprojection errors.

	Method	25%	50%	75%
	DenseVLAD (SR)	100.09 155.75 233.56
	DenseVLAD (SR-SfM)	10.92	33.78	165.30
	DenseVLAD (SR-SfM init.)	9.04	22.35	85.43
	DenseVLAD (SR-SfM init.)+trans.	9.90	24.03	86.95
	Disloc (SR)	100.09 157.22 246.18
	Disloc (SR-SfM)	10.46	38.60	160.02
	Hyperpoints (3D)	14.93	32.21	124.82
	CPV w/ GPS (3D)	21.05	46.87	116.99
	CPV w/o GPS (3D)	21.18	44.74	122.36

TABLE 5

 5

We experimented with three registration approaches based on the geo-tags of (1) only the PCI images, (2) only the GSVTM images, and (3) all images. All variants show a similar pose accuracy, but the last version registers the largest number of query images.

ACKNOWLEDGMENTS

This work was partly supported by EU-H2020 project LA-DIO No. 731970, JSPS KAKENHI Grant Number 15H05313, 17J05908, ERC grant LEAP (no. 336845), CIFAR Learning in Machines & Brains program and European Regional Development Fund under the project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000468), Grant Agency of the CTU in Prague project SGS18/104/OHK3/1T/37, and Google Tango.