Methods for visual localization

Visual localization, a way to determine location from images, is a method used by robots and self-driving cars to estimate their position. It’s also used in augmented reality applications to interact with the physical world both indoors and out in the open. This article gives an overview of current state-of-the-art methods and their advantages and drawbacks.

Introduction

Technology such as self-driving cars, mobile robots and even augmented reality (AR) applications interact in different ways with the environment which means that they’re dependent upon location. Global navigation satellite systems (GNSS) such as GPS is the most well-known way to get this information yet, although these systems have been used for many years, they still have some limitations. In particular, GNSS systems don’t work indoors, their precision is limited to within a couple of meters, nor do they provide information on orientation. One can combine GPS with a compass to get an estimated position accurate to within 1-2m in distance and about 10 degrees in orientation but applications such as robot navigation and self-driving cars require much higher accuracy and, as satellite-based methods don’t work indoors, we need to find other ways.

Visual localization challenges

Visual localization, the process of estimating camera pose using images, has the potential to provide both outdoor and indoor localization that’s accurate up to a few centimeters and degrees. In the case of self-driving cars, the rich visual information provided by camera images can be used to establish correspondences between a query image and a representation of the world created using a set of reference images. These correspondences can then be used to compute the image’s position with respect to the world. This representation, or ’visual map’, can be a 3D reconstruction, a set of images with poses tagged or a deep neural network. Indoors, this kind of localization is extremely useful for robot navigation and AR applications but also for self-driving cars which find themselves in tunnels or underground car parks where GNSS is compromised.

Visual localization methods need to overcome a number of difficulties including:

• Illumination changes i.e. is it possible to localize a night time image if the map images were taken during daytime?
• Dynamic scenes with moving objects that might not have been present when the map was created
• Images taken in different seasons or weather conditions
• Occlusion of the scene by an object or person
• Strong viewpoint changes between the map and query images

Several benchmark datasets and challenges have recently been proposed to evaluate visual localization ’pipelines’ which address some of these issues. They include large appearance variations caused by changes in the season (summer, winter, spring, etc.) and illumination conditions (dawn, dusk, day, night). Furthermore, as the research field of visual localization is of growing interest, a lot of useful material can be found online, notably the series of tutorials organized by Torsten Sattler. Finally, since many of the datasets are provided in different formats and many open source tools are available, a lot of data conversion is necessary and this can sometimes pose a problem. To address this, we’ve made available Kapture, an open source data format which unifies the existing rich set of data formats and tools for structure from motion (SfM) and visual localization.

Overview of methods

A variety of approaches have been proposed over the years to overcome these challenges. Figure 3 gives an overview of the most relevant methods. The classic methods are structure based, which means that they rely on 3D reconstructions i.e. point clouds, of the environment and use local feature matching to establish correspondences between the query image and the 3D map. Image retrieval can be used to reduce the search space by considering only the most similar reference images instead of all possibilities. Another way of using such similar images, even without relying on 3D reconstructions, is to directly interpolate the pose from the reference images or to estimate the relative pose between the query and the retrieved reference images. Scene point regression methods can directly determine correspondences between 2D pixel locations and 3D points using a deep neural network (DNN) and compute the camera pose similar to structure-based methods.

Modern scene point regression methods benefit from a 3D reconstruction during training time but do not rely on it. Finally, absolute pose regression methods estimate the pose end-to-end using a DNN. Table 1 summarizes the key criteria of these methods. The methods vary in terms of their capability to generalize and their localization accuracy. Furthermore, some methods rely on 3D reconstructions whilst others only need pose-tagged reference images. The benefit of using 3D reconstructions is that the resulting pose can be very accurate. The drawback is that these 3D reconstructions are sometimes hard to obtain and even harder to maintain e.g. if the environment changes they need to be updated.

Structure-based methods

The traditional way of estimating the location of a camera within a given environment is to first create a 3D reconstruction of the area (that’s why the term structure is used) i.e. a map, and then localize an image within this map [33, 24, 34, 22, 41, 37].

The process of camera pose estimation and 3D reconstruction, using a set of images showing the same scene but from different locations and view points, is called structure from motion (SFM) [24, 37]. In more detail, the camera poses are estimated and each 3D point is reconstructed using pixel-wise correspondences across multiple images. These correspondences are first automatically generated between so-called local features [10, 16] for image pairs, where either all possible pair-wise combinations of mapping images (brute force) are considered or between subset of pair images selected using some sort of image similarity (see the next section).

Note that a local feature consists of a precise pixel location (the keypoint) and its unique description using e.g., the pixel neighbourhood within the image (the descriptor). Early methods used handcrafted local feature extractors, notably the popular SIFT descriptor [23] but such keypoint extractors ad descriptors have several drawbacks including the fact that they’re not necessarily tailored to the challenges of the target task. This holds in particular for changing conditions such as day-night and seasons of the year. Several data-driven learned representations were therefore recently proposed [16, 12, 32, 11] including learning local features with end-to-end deep architectures (see the evolution of local features in [10, 38]).

Since the 3D points of the map are generated using image descriptors and these descriptors are part of the map, 2D-3D correspondences between the query image (2D keypoints) and the map (3D points) can again be established using descriptor matching. Once the 2D-3D matches are available, they are used to compute the camera pose using so-called perspective-n-point (PNP) solvers [19]. Since the 2D-3D matches might contain outliers, PNP is computed within a RANSAC loop [13, 8] to increase robustness.

As one can imagine, the maps can become quite big if large areas, such as an entire building or even a city, are to be covered. To give an example, the number of 3D points in the 3D reconstruction of the popular visual localization dataset Aachen-Day-Night [35] varies between 700k and 2.5M (depending on the amount of image pairs used). Note that this dataset only consists of the old inner city of Aachen, Germany. If the map grows even more, efficient correspondence analysis between the keypoints of the query image and all 3D points in the map becomes impossible. In order to reduce the search range in such large 3D reconstructions, image retrieval methods (see the next section) can be used to first retrieve most relevant images from the map then only look for keypoint correspondences in the area defined by those images [15, 31].

Instead of creating a global map (as discussed above) of the environment, those retrieved images can also be used to create an ad hoc local map. The localization step remains the same. The benefit of this approach is that we don’t need to maintain a global map. The drawback is that it might not be possible to generate a local map with the retrieved images. This can happen if not enough images showing the same scene as the query images have been retrieved.

Another approach for establishing the correspondences in structure-based methods is scene point regression where the 2D-3D correspondences are directly estimated using e.g., a DNN [4, 5, 21, 6] or a random forest [40].

Image retrieval-based methods

Image retrieval plays an important role in visual localization. It enables structure based localization methods (see previous section) in large scale environments such as big commercial centers, airports, city areas and it makes both the mapping and localization more robust. It can also be an alternative to structure-based methods i.e. by solving the problem without relying on a pre-computed 3D structure. These methods in general require that the images in the database be stored either with approximate location information such as GPS (geo-localization scenario) or with exact 6 degrees of freedom (DoF) poses within a given world coordinate frame (visual localization).

In both cases, the aim is to select a set of images that are the most similar according to a selected representation followed by an optional re-ranking step (using for example query expansion or filtering techniques). This approach, known as image retrieval, finds images in a given, generally large, dataset that are relevant to the query image according to some predefined criteria. In the context of visual localization, a retrieved image is considered relevant if it sees the same scene (e.g. same landmark) as the query image or if it was captured in the neighborhood of the position from which the query image was taken. When the former criterion is used to define relevance we talk about ’landmark retrieval’. The latter case is in general referred to as ’geo-localization/place recognition’ (Figure 3 shows that, whilst they are related, they might also show some differences). The image retrieval methods used for landmark retrieval and for place recognition therefore have a very similar structure, especially the more recent deep learning based models [1, 43].

In the last decade, most image retrieval methods have used variants and extensions of ’bag of visual words’ representations. However, more recently, DNN activation features have been shown to encode high level semantics and are therefore suitable for image retrieval. The performance can be boosted even further if the network is trained for the retrieval task using ranking losses [14, 17, 29].

While one of the advantages of image retrieval is that it can reduce the search space when performing image localisation given a 3D map of the environment (as mentioned in the previous section), it can also be used for a more direct if, in general, less accurate image localization, especially when the structure is not available. This can be done by considering simple methods such as inferring the pose of the nearest neighbor image or interpolating the poses of top k retrieved images [44, 36]. Note that these simple methods uses only the poses of the retrieved images.

Alternatively, if the intrinsic camera parameters are known, the relative pose between the query image and a retrieved image can be estimated directly by just relying on local feature matches. Then, if the absolute poses of the retrieved database images are known, the query pose can be directly deduced from the relative poses [48, 49].

A comprehensive benchmark of image retrieval for visual localization is presented in [26]. The authors evaluate the image retrieval performance of 4 popular image representations on 3 localization tasks (using a global 3D map, constructing a local 3D map on-the-fly, and camera pose interpolation). They also investigate the correlation between landmark retrieval and visual localization, showing that, while some correlation exists, future research tailored to this task is needed.

Pose regression-based methods

Recent success in image classification, semantic segmentation, image retrieval and other vision tasks have inspired an alternative, deep-CNN-based approach to visual localization. By adopting the same concept, a CNN network can take an RGB image and learn to regress the camera pose in an end-to-end manner. Under the assumption that low level features used for general vision tasks (e.g. image classification) encode useful information for pose estimation, the researchers suggest to leverage on transfer learning from pre-trained deep CNNs for pose estimation.

In particular, PoseNet [18] modified the image classification CNN architecture, like VGGNet or ResNet and replaced softmax layers with fully connected (FC) layers to regress both the 3D location and the orientation of the camera as shown in Figure 5.

Directly regressing the absolute pose with end-to-end learning has several appealing advantages. First, the pose regression does not require any feature engineering, it relies on deep network encodings that are more robust to challenging changes in the scene such as lighting conditions and viewpoints. Second, compared to 3D-based methods, a trained model requires less memory and has a constant inference time. Thirdly, transfer learning enables effective training on commonly used medium-sized datasets. However, the localization error (both translation and rotation) achieved with PoseNet is an order of magnitude larger than the error attained with state-of-the-art structure-based methods.

To reduce the localization error, multiple improvements to the PoseNet architecture have been proposed, including new loss functions [17], adding Long-Short-Term-Memory (LSTM) layers, or relying on additional data sources and sensor measurements [7]. To further improve the performance, VLocNet [45] proposed to jointly learn absolute and relative pose estimations, which was further extended by VLocNet++[28], with semantic segmentation as a second auxiliary task.

However, learning an entire pipeline often results in sub-optimal performance. as it imposes a tight coupling with the scene coordinates, where the network can be viewed as a compressed version of an underlying map (of the scene). This in turn, limits the generalization power of the network.

More recently, hybrid pose learning methods shift the learning towards local or related problems, and combine them with the traditional image retrieval and structure-based pipelines, such as DSAC [3] which relies on geometrical constraints and the learning is focused on local computer vision tasks, such as 2D-3D matches. While this approach significantly improves the pose accuracy, the learned models remain scene-dependent and do not generalize to new scenes.

To address the generalization problem, the recent, SANet [47] proposes a scene agnostic neural architecture for camera localization, where model parameters and scenes are independent of each other. The model leverages geometry through 3D point clouds obtained as dense multi-view stereo (MVS) reconstructions from the top retrieved images and learns query-scene registration as well as camera pose regression.

Conclusion and future directions

• Recent benchmarks and localization challenge results have shown that geometric based methods still outperform end2end methods. It is of note however that to achieve the best performance, several modules in the pure geometric based pipeline are replaced by deep solutions such as the local and global feature extractor. Indeed, deep network based representations have the advantage over handcrafted features to be able to handle various variations and learn to be invariant to them.
• Pure retrieval based solutions can be a low cost solution when the aim is to get just a rough position, e.g. in the case of geo-localization.
• Regression pose generalization is still open when neither a 3D model or point cloud are available.
• An interesting approach to overcome some of the challenges of visual localization is to use semantic information of the scene, such as objects, buildings or landscapes. One could, for example, use semantic classes (e.g. tree, building, street) to improve local feature matches [42, 20] or use objects for localization [30, 9, 2]. Weinzaepfel et al. [46] propose building a database of unique objects of interest and directly regress local feature matches between the detected objects in the query image and their representation in 3D space. Since dynamic areas such as cars, people or even trees, impose challenges for visual localization, one could also ignore such areas for visual localization [16, 24].
• Interesting future directions include further improvements in local and global features, leveraging multi-camera systems and image sequences as well as introducing better generalization capabilities for absolute and relative camera pose regression.