Bryan C Russell

Josef Sivic

Jean Ponce

Hélène Dessales

Automatic alignment of paintings and photographs depicting a 3D scene

 with the view-synthesis/retrieval of Irschara et al. [14] to obtain a coarse alignment of the painting to the 3D model by view-sensitive retrieval; (ii) we develop an ICP-like viewpoint refinement procedure, where 3D surface orientation discontinuities (folds and creases) and view-dependent occlusion boundaries are rendered from the automatically obtained and noisy 3D model in a view-dependent manner and matched to contours extracted from the paintings. We demonstrate the alignment of XIXth Century architectural watercolors of the Casa di Championnet in Pompeii with a 3D model constructed from modern photographs using the PMVS public-domain multi-view stereo software.

Introduction

Given a set of photographs depicting a static 3D scene, it is often possible to automatically align the photographs and recover the corresponding camera parameters and pose, along with a model of the underlying 3D scene. The ability to reliably find and match features at interest points, along with robust procedures for bundle adjustment, has allowed for the recovery of large-scale 3D models from many images taken from a variety of viewpoints and under many viewing conditions [8,[START_REF] Furukawa | Accurate, dense, and robust multi-view stereopsis[END_REF][START_REF] Goesele | Multi-view stereo for community photo collections[END_REF]. This has allowed several applications, such as image retrieval [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], virtual exploration of a site [START_REF] Snavely | Modeling the world from Internet photo collections[END_REF], preserving cultural heritage [START_REF] Ikeuchi | Digital presentation and restoration of cultural heritage through computer vision techniques[END_REF], and computational rephotography [START_REF] Bae | Computational rephotography[END_REF].

While much success has been shown for aligning photographs, we are not aware of work on automatically aligning non-photographic depictions of a scene, such as paintings and drawings (herein, for convenience, we will refer to both paintings and drawings as paintings). Such depictions are plentiful and comprise a large portion of our visual record. In this paper, we seek to automatically align paintings and photographs depicting a static 3D scene. Our main focus in this work is the ability to handle historical architectural paintings where the artist has made an effort to accurately portray a 3D scene. Such paintings are often made with the aid of a camera lucida, so we will assume, at least to first order, that the paintings are perspective scene renderings. In spite of this assumption, we will see that this is still a challenging scenario, and progress in this direction would be of benefit to fields where paintings were used to record the state of a given site, such as archaeology. We believe that the overall system is relevant to scenarios where local feature matching fails, e.g. texture-less or wiry objects with significant 3D structure (e.g. chairs, mugs, tables) or changes due to time/season, which present significant challenges for current feature-based instance-level matching/recognition techniques. Image to 3D model matching is also important for applications in urban planning and civil engineering, where a reference 3D model may be available but may contain errors or unexpected changes (e.g. something built/destroyed).

A number of difficulties arise when trying to align paintings and photographs. These difficulties are primarily due to what makes paintings fundamentally different from photographs. At first glance, a realistic painting of a scene does not appear to be very different from a photograph taken from a similar viewpoint. However, upon closer inspection, they are usually quite different, since the color, geometry, illumination, shading, shadows and texture may be rendered by the artist in a realistic, but "non physical" manner. These differences can be quite difficult to spot, which artists often exploit to "fake" visual realism with much success [5].

Because of these differences, the main issue is establishing visual correspondences between paintings and photographs. Current successful systems for 3D reconstruction of large-scale data (e.g. PhotoSynth [START_REF] Snavely | Modeling the world from Internet photo collections[END_REF]) completely fail when considering paintings. For example, using SIFT matching [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], the painting in Figure 5(a), which at firstglance looks like a clean image rendering of the scene, only finds 121 putative matches total across all images in our dataset. Upon visual inspection, none of the putative painting-image matches are correct. We believe that local feature matching, as currently implemented in Bundler, would not work for this problem.

In this work, we investigate features for reliably aligning paintings and photographs. We primarily build upon recent success in recovering dense 3D points and a triangular mesh from a set of photographs [START_REF] Furukawa | Accurate, dense, and robust multi-view stereopsis[END_REF][START_REF] Kazhdan | Poisson surface reconstruction[END_REF]. We believe that the use of such a 3D model offers several advantages to aid in alignment. First, the 3D model allows us to extract viewpoint independent features, such as folds and creases, and viewpoint dependent ones, such as occlusion boundaries. We argue that such features are better-suited for matching with paintings, and are not necessarily easily extracted by reasoning about the photographs independently. Furthermore, while impressive results have been shown to densely align challenging image pairs exhibiting drastic appearance changes [13,[START_REF] Shechtman | Matching local self-similarities across images and videos[END_REF][START_REF] Viola | Alignment by maximization of mutual information[END_REF]31], these approaches do not use a 3D model and rely on the image pair to have nearby viewpoints. Such direct matching is difficult when a photograph from a similar viewpoint is not available. In our case, using a 3D model allows us to cope with new, previously unseen and potentially different viewpoints.

For our study, we use modern photographs and historical drawings and paintings depicting the Casa di Championnet, which is located amongst the ancient ruins of the Roman town of Pompeii. As the site sits outside and exposed to the elements, various components of the site have changed over time. For example, many of the wall murals that existed in the earlier paintings have almost completely disappeared in its present state. Furthermore, the central columns have changed shape, with one suffering major collapse since its initial excavation. This site is of particular interest to archaeologists, who wish to study these changes, in addition to digitally restoring the site. This poses an additional challenge for alignment, which must account for these structural changes across time. Some of the above issues are partially addressed in prior work. Procedural modeling is used to build a 3D model of the Pompeii site [START_REF] Müller | Procedural modeling of buildings[END_REF], with the models manually created with the aid of archaeologists. The 4D cities project seeks to align photographs across time [26]. The Piranesi project [16] re-photographs historical paintings by manually finding a similar viewpoint as the painting. While there have been significant efforts to align photographs to 3D models, e.g. [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF][START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF][START_REF] Li | Location recognition using prioritized feature matching[END_REF]25], paintings have been overlooked so far. Dense alignment of challenging image pairs (e.g. infrared and visible spectrum imagery) has only been demonstrated on photographs [13,[START_REF] Shechtman | Matching local self-similarities across images and videos[END_REF][START_REF] Viola | Alignment by maximization of mutual information[END_REF]31], and the focus Inputs: painting I, set of photographs J Output: triangular mesh M, camera parameters Θ for I 1. Recover triangular mesh M from the set of photographs J using Bundler [START_REF] Snavely | Modeling the world from Internet photo collections[END_REF], PMVS [START_REF] Furukawa | Accurate, dense, and robust multi-view stereopsis[END_REF], and Poisson surface reconstruction [START_REF] Kazhdan | Poisson surface reconstruction[END_REF] (Section 2). 2. Coarse alignment by view-sensitive retrieval (Section 3) (a) Generate virtual cameras that uniformly sample the recovered 3D scene and render the views [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF]. (b) Find nearby virtual viewpoint Θ to I by gist feature matching [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF]. has been on 2D alignment models. Recently, there has been work to align silhouettes extracted from topological maps to photographs, with the initial view obtained by GPS [START_REF] Baboud | Automatic photo-to-terrain alignment for the annotation of mountain pictures[END_REF]. In contemporary work [START_REF] Shrivastava | Datadriven visual similarity for cross-domain image matching[END_REF], painting-to-image matching and retrieval over a large database has been explored. However, this work only considers image-based similarity and does not reason about a 3D model.

Our contribution is the use of a 3D model to extract features suitable for matching paintings and photographs. To the best of our knowledge, this is the first system to automatically align paintings and drawings with a 3D model computed from photographs. On the technical level, our contribution over the current state-of-the-art is two-fold. First, we combine the gist descriptor [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF] with the viewsynthesis/retrieval of Irschara et al. [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF] to obtain a coarse alignment of the painting to the 3D model. The viewsynthesis/retrieval allows reasoning about unseen viewpoints [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF] while the gist descriptor is sensitive to viewpoint [START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF] and has been shown to generalize across appearance variation for scene category recognition [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF]. Second, we develop a fine alignment procedure based on the Iterative Closest Point (ICP) algorithm [START_REF] Besl | A method for registration of 3-D shapes[END_REF], where 3D surface orientation discontinuities (folds and creases) and viewdependent occlusion boundaries are rendered from the automatically obtained and noisy 3D model in a view-dependent manner and matched to contours extracted from the paintings. By aligning view-dependent contours, we hope to overcome the limitations of local feature matching for this problem by exploiting the ability to recover reliable contours from the painting and 3D model and by building on the success of contour matching [3]. We demonstrate the alignment of XIXth Century architectural watercolors of the Casa di Championnet in Pompeii with a 3D model constructed from modern photographs.

Overall approach

Given a painting I and a set of photographs J depicting a 3D scene, our goal is to automatically recover a model of the 3D scene, along with parameters describing the viewpoint of the painting with respect to the recovered model. We represent the model of the 3D scene by a triangular mesh M and assume that points in the 3D scene are rendered onto the painting by perspective projection. In other words, we treat the painting as if it were an image, with the desired goal of recovering the standard "camera" parameters Θ that describe the painting's internal calibration and viewpoint with respect to M. The parameters that we seek to recover are the camera center, rotation, focal length, and principal point (we assume zero-skew and square pixels). Our algorithm is summarized in Figure 1.

To start, our aim is to build a high-quality triangular mesh of the 3D scene from the input set of photographs. For this, we use existing algorithms that have shown much success on a variety of real-world scenes. We start by running Bundler [START_REF] Snavely | Modeling the world from Internet photo collections[END_REF] on the input set of photographs. Bundler matches features extracted at interest points to recover a sparse 3D point set, along with camera parameters for each photograph. The recovered camera parameters are then used as input for the PMVS algorithm [START_REF] Furukawa | Accurate, dense, and robust multi-view stereopsis[END_REF], which uses photometric matching and region growing to recover a dense 3D point set. Finally, the dense 3D point set is used as input for the Poisson surface reconstruction algorithm [START_REF] Kazhdan | Poisson surface reconstruction[END_REF], which solves a spatial Poisson problem to recover a triangular mesh. To perform these steps, we use existing publicdomain software. An example triangular mesh recovered from a set of photographs is shown in Figure 2 (more details about the photographs and mesh are given in Section 5).

Given the triangular mesh M extracted from the photographs, we wish to recover the parameters Θ of the painting with respect to M. We begin by coarsely aligning the painting to the 3D model by matching to virtual viewpoints that are uniformly sampled across the 3D model [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF]. In this way, we get a set of initial guesses of the painting viewpoint. Next, we use the initial viewpoints to validate and more accurately align the painting to the 3D model. We discuss in more detail these steps in the following sections.

Coarse alignment by view-sensitive retrieval

Our aim is to find a viewpoint that is sufficiently close to the painting viewpoint, where the depicted scene objects in the painting are close to their 3D model projection. We wish to build upon recent successes in view-sensitive matching in large photo collections [START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF] and matching to synthetic views of 3D models [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF]. This will allow us to be sensitive to different viewpoints, while reasoning about unseen views and generalizing across large appearance variations.

We generate virtual camera matrices that uniformly sample viewpoints of the 3D model. To densely sample viewpoints from the model, we assume that the paintings are drawn upright at eye-level. Hence, we limit our virtual viewpoints to live in a plane at approximately eye-level looking in a direction parallel to the ground plane. To find the ground plane, we search for the dominant scene plane using the Hough transform [7] on the PMVS point set. We determine the eye-level height by finding the average distance of the camera centers for the input photographs to the recovered ground plane. We sample camera centers in a grid and use 12 horizontal orientations at each sample point. The grid spacing is determined empirically (4% of the scene width) to ensure reasonable scene coverage. For the camera intrinsic parameters, we assume zero-skew square pixels, with the principal point in the center of the image and use the average focal length of the recovered cameras.

Next, we render each virtual viewpoint using the set of PMVS points. Figure 3 shows example rendered virtual viewpoints of the 3D model. We discard viewpoints in which the 3D model projects to less than 25% of the pixels in the rendered viewpoint.

Given the large pool of virtual viewpoints, we wish to retrieve a small set of candidate nearby viewpoints to the painting. For this, we match the appearances of the painting and virtual viewpoints using the gist descriptor [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF]. The gist descriptor has been used for recognizing scenes despite significant changes in appearance and has been shown to work well in retrieving similar viewpoints of the same 3D scene [START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF]. We find the gist descriptor to provide a good degree of robustness to the large changes of appearance between the painting and the rendered viewpoints of the 3D model, while being sensitive to viewpoint. Also, the descriptor is robust to the noisy rendering of the 3D scene, which contains holes and incomplete structures. We normalize the descriptors to be unit length and retrieve the set of nearest neighbor viewpoints that minimize L2 distance.

Figure 3 shows example retrievals. In all cases the correct viewpoint is retrieved within the top 3 nearest neighbors.

Fine alignment by matching view-dependent contours

Given the retrieved coarsely matching viewpoint, we wish to refine the viewpoint and align the painting to the 3D model. For this, we need to find correspondences between the 3D model and painting. We find that standard local features, such as SIFT, are not suitable for establishing reliable correspondences between paintings and photographs due to extreme appearance changes. Instead, we establish correspondences by matching contours that are extracted from the painting and the 3D model. As we have a 3D model of the scene, we can extract reliable view-dependent contours that are informed by the shape of the 3D surface. With the established correspondences, we can recover the camera matrix for the painting via camera re-sectioning [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF].

Contours for 3D model and painting. Given the difficulty in matching the appearance of paintings, we wish to extract features from the 3D model that can be reliably matched to the painting. For this, we extract contours corresponding to folds, creases, and occlusions from the 3D model, as these are often depicted in the paintings.

To recover folds and creases, we use the ridges and valleys algorithm of Ohtake et al. [22]. This algorithm draws lines at places with high surface curvature. For this, we use publicly available software [6], which also extracts occlusion contours. We perform smoothing on the surface normals to remove spurious contours, which result from fine undulations in the 3D model. Example extracted line drawings are shown in Figure 4. Notice that the lines follow closely the scene folds, creases, and occlusions.

To match the contours extracted from the 3D model, we find edges in the painting. For this, we find edges in the painting using the global probability of boundary (gPB) detector [20]. Each gPB edge point x has a response strength and edge orientation φ. The edge orientation denotes the edge direction at the given point, with the orientations quantized into 8 directions (between 0 and π). As a preprocessing step, we perform adaptive histogram equalization in Lab color space on the original painting. We threshold the gPB response strength (we use a threshold of 0.05) to obtain binary images B I (x, φ) for each edge orientation. We perform similar thresholding for the contours extracted from the 3D model for the nearby virtual viewpoint Θ and measure the response of a second derivative operator tuned to the 8 edge orientations to obtain binary images B M (x, φ, Θ). ICP-like fine alignment. We seek to align the binary images over edge orientations for the painting and 3D model. Let S I (φ) = {x | B I (x, φ) = 1} be the set of edge points for orientation φ in the binary image for the painting. Particular camera parameters Θ define a similar set of edge points S M (φ, Θ) for the 3D model. We wish to find the viewpoint with camera parameters Θ minimizing the following cost function

min Θ φ xi∈S I (φ) min xj ∈S M (φ,Θ) min |x i -x j | 2 , γ (1)
where γ is an inlier threshold. This is similar to the truncated reprojection error of 3D points along folds, creases, and occlusions from the 3D model to the edge points in the painting. The truncation allows robustness to outlier correspondences. We set the inlier threshold γ to be 0.5% of the painting diagonal.

To solve the optimization problem of Equation ( 1), we begin by searching for putative correspondences between the oriented edge points for the painting and 3D model. For this, we use the shape context descriptor [3], which is a representation used to describe the shape about a given location and has shown success in aligning binary image patterns and for digit recognition.

The shape context descriptor is formed by spatially accumulating sampled edge points about a given location. We sample 1000 edge points from the painting and 3D model, which empirically provides sufficient coverage of the scene. Spatial log-polar bins are formed around each sampled point, and sample points landing in each spatial bin are accumulated. In addition, we use the edge orientation information and accumulate points having the same edge orientation. In total, we use 3 radial bins (the minimal and maximal bin sizes are 7% and 15% of the painting diagonal), 12 angular bins, and 8 edge orientations, which results in a 288 dimensional feature vector. The feature vector is normalized to sum to one. Given shape context features f i , f j and edge orientations φ i , φ j for points belonging to the painting and the 3D model, respectively, we use the following match score:

R i,j = (1 -η) X (f i , f j ) + η E(φ i , φ j ) (2)
where X (f i , f j ) is the Chi-squared distance and E(φ i , φ j ) is the unsigned difference in edge orientation. We set η = 0.1 to the default setting used in [3]. A putative correspondence is formed for each sampled point in the 3D model by matching it with the best scoring sample point in the painting. For each putative correspondence (x i , x j ), sampled points belonging to the 3D model are back-projected to retrieve the corresponding 3D point X j . The putative correspondences (x i , X j ) are used for camera resectioning.

Given the putative correspondences, we use RANSAC to recover the camera parameters Θ and to find inlier correspondences. To speed-up RANSAC, we use a simpler model (known intrinsics) within the RANSAC loop, followed by iterative re-estimation using the full camera model [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. In particular, we assume reasonable values for the intrinsic camera parameters (square pixels, focal length equal to image width and principal point at the image center) and recover only the extrinsic parameters corresponding to the camera rotation and center inside the RANSAC loop. This results in six parameters, which are computed using three putative correspondences at each RANSAC iteration (note that there are up to four solutions, which must all be validated). We run RANSAC for 1000 iterations.

The camera parameters Θ that minimize the cost function given by Equation (1) when projecting the 3D points corresponding to the points in S M (φ, Θ) are returned. In other words, the sparse set of shape context points propose camera parameters, which are then validated (scored) with the dense set of 3D points along the scene creases, folds, and occlusions. The dense set of painting edge points that are inliers (i.e. lie within γ distance to a projected 3D model point), along with the closest 3D model points, are used to minimize geometric reprojection error over all of the camera parameters (intrinsic and extrinsic).

Given the camera parameters Θ, a new viewpoint is generated and corresponding new set of contours are extracted from the 3D model. The new set of contours are used to iteratively optimize Equation [START_REF] Baboud | Automatic photo-to-terrain alignment for the annotation of mountain pictures[END_REF]. At iteration i, we limit the search for shape context correspondences to be within ǫ = ǫ0 2 i pixels, with ǫ 0 set to be 20% of the painting diagonal. The entire process is stopped when ǫ ≤ 1, and the best scoring set of camera parameters are returned.

Experimental results

We have tested our system on paintings of the Casa di Championnet, which is located amongst the ancient ruins of the Roman town of Pompeii (VIII 2, 1). The city was buried during a volcanic eruption in 79 AD, rediscovered in 1599, and was first excavated in 1748. The Casa di Championnet was excavated in 1798. For our study, we have gathered 9 paintings and drawings depicting the 3D structure of the site1 . The paintings were rendered over different periods and provide a glimpse of the site as it changed over time. Example paintings are shown in Figures 3 and5. We focus on paintings where the artist had intended to accu-rately capture the 3D scene structure. In some cases, it is believed that a camera lucida was used to assist the artist. The paintings were manually gathered from archaeological archives, which required an expert to correctly identify that the depictions are of the site of interest. Notice that different styles are represented, ranging from watercolors to cross-hatching. Furthermore, drawings and watercolors were used to produce engravings in the XIXth century publications, with strong rendering differences.

To recover the dense 3D model, we use 563 photographs (4752 × 3164 resolution) that were captured of the Pompeii site over two days during sunrise and sunset (to avoid strong cast-shadows). Figure 2(a) shows example photographs of the site. The final mesh contains 10M vertices and 20M triangles. A snapshot of the mesh is seen in Figure 2(b).

Coarse alignment retrieval results. To coarsely align the painting to the 3D model, we synthesize 16,548 virtual viewpoints and discard viewpoints that back-project to less than 25% of the pixels in the rendered viewpoint. This results in 8,379 virtual viewpoints, which are used to retrieve a similar viewpoint to the input painting. We show results for coarse alignment retrieval in Figure 3 for different paintings in our dataset.

For validation, we obtain correspondences between each painting and the 3D model by hand-clicking on average 19 correspondences at key points in the scene. We use the correspondences to obtain ground-truth camera matrices for the paintings via camera resectioning by minimizing geometric error [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. To declare a virtual viewpoint as correct, we look at the reprojection error when projecting the 3D points lying in the painting onto the virtual viewpoint. Correct viewpoints are highlighted in green in Figure 3. For all paintings, the correct viewpoint is retrieved in the top 3 nearest neighbors. This is noteworthy given the size of the set of virtual viewpoints. In all cases, the correctly retrieved viewpoint is close to the input painting and forms a good initialization for fine alignment.

Fine alignment results. Given the retrieved viewsensitive coarse alignment, we run the ICP-like fine alignment procedure five times and return the output with lowest cost in Equation (1). In Figure 5, we show the final alignment of paintings in our dataset to the 3D model. We show the input painting, extracted contours from the 3D model for the final viewpoint overlaid on the painting, and a rendering of the 3D model for the final viewpoint.

For the paintings in Figure 5(a-c), the output viewpoint is close to the depicted viewpoint and the rendered 3D model contours mostly follow the contours depicted in the painting. Moreover, our system is able to successfully align a variety of different painting styles. Figure 6 shows snapshots of the fine alignment procedure at different iterations. Example failure cases of the fine alignment procedure are shown in Figures 5(d,e). Many of these failures are due to unreliable features extracted from the painting. In particular, pencil strokes indicating shading is difficult for our system. However, note that for the failure cases, a close-by viewpoint is successfully retrieved, as shown in Figure 3.

In Table 1 we quantify the fine alignment procedure for each painting by measuring the average reprojection error (both in pixels and as a percentage of the length of the painting diagonal) using the set of hand-clicked correspondences. The fine alignment procedure successfully finds a viewpoint with average reprojection error within 3% of the painting diagonal for 5 out of 9 paintings in our dataset, which corresponds visually to a nearby viewpoint.

In assessing the quality of the final alignment, one difficulty is in determining the exact source of alignment error. Some 3D model contours do not tightly snap to the painting contours (e.g. the top of the left-column in the painting in Figure 5(a)). These errors are often due to the alignment procedure and features. However, for some depicted features in the painting, the error could be due to drawing error. For example, the columns in Figure 5(b) are depicted closer to the edge of the central pool than in the reconstructed 3D model. This is also suggested by the reprojection error for the ground-truth camera matrix, as shown in Table 1. The set of paintings that were rendered from the viewpoint depicted in Figure 5(b) consistently yield higher ground-truth reprojection error (normalized errors well above 1%). For the scene in Figure 5(c), the paintings do not all appear to After each iteration, the viewpoint is updated. Notice that there are many inliers in the putative set and that the 3D model gets closer to the input painting with each iteration. The matching converges after seven iterations, with iterations 1, 2, 3, and 7 shown.

be painted with the same accuracy, as determined by the reprojection errors of the ground-truth matrices.

Conclusion

We have shown successful alignment of historical paintings depicting the Casa di Championnet in Pompeii to a 3D model constructed from modern photographs of the site. To achieve this we have developed a two-stage alignment procedure. We find an approximate viewpoint by retrieval and then refine the viewpoint by matching to view-dependent contours extracted from the 3D model. Renderings of the 1. Reprojection error for 19 hand-clicked correspondences between the paintings and 3D model. Res: Painting resolution in pixels. GT: Error for ground-truth camera matrix computed from hand-clicked correspondences by minimizing geometric error. Alg: Error for algorithm output. The reprojection error is measured in pixels. In parenthesis, the error is given as a percentage of the length of the painting diagonal. The scenes depicted in Figures 5(b,c) have additional paintings (not shown in Figure 5) that are rendered in different styles (the first sub-columns correspond to the displayed paintings in Figure 5). Notice that some paintings have higher error for the ground-truth camera matrix. This provides an indication of the difficulty of producing an accurate alignment, which may be due to drawing errors. recovered viewpoint are close to the viewpoint depicted in the paintings, with contours extracted from the 3D model following closely the depicted structures in the paintings. As demonstrated, our method copes with challenges in appearance that paintings provide, such as color and texture. Such challenges are difficult for current systems relying on local feature matching.

While collecting the 3D model was relatively easy, collecting the paintings that were used was challenging, as it required an expert to correctly identify from archaeological archives paintings rendered with the intention of accurately depicting the site of interest. We believe that scaling up to additional sites is an interesting future direction that may require successful large-scale painting retrieval [START_REF] Shrivastava | Datadriven visual similarity for cross-domain image matching[END_REF].

  3. Fine alignment by matching view-dependent contours (Section 4) (a) Extract contours (ridges and valleys [22] and occluding contours) for Θ from M. (b) Use shape context features [3] to iteratively match contours for Θ to gPB contours [20] extracted from I and estimate Θ from the correspondences. Figure 1. Algorithm overview.

Figure 2 .

 2 Figure 2. (a) Example photographs captured of the Pompeii site (563 photographs are used in total). (b) Rendered viewpoints of the recovered 3D model. Notice the fine-level details that are captured by the model.

Figure 3 .

 3 Figure3. Coarse alignment by view-sensitive retrieval. For each painting (left), the top three nearest neighbor virtual viewpoints generated from the 3D model using gist feature matching[START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF] are shown. The correctly retrieved viewpoint is highlighted in green. Notice that the correct viewpoints are retrieved in the top nearest neighbors in all cases.

Figure 4 .

 4 Figure 4. Lines for creases, folds, and occlusions extracted from the 3D model. Top row: rendered viewpoints. Bottom row: lines corresponding to ridges and valleys [22] (red) and occlusion boundaries (green). Notice that the drawn lines follow closely the creases, folds, and occlusions in the 3D scene.

Figure 5 .

 5 Figure 5. Final alignment between the paintings and 3D model. For each example, left: painting; middle: 3D model contours projected onto painting; right: synthesized viewpoint from 3D model using recovered camera parameters Θ. For the examples in (a-c), note how the final alignment is close to the painting. Our system handles paintings that depict the 3D structure of the scene over time and span different artistic styles and mediums (e.g. water colors, cross-hatching, copies of originals on engravings). Notice how the site changes over time, with significant structural changes (e.g. the wall murals decay over time, the columns change). Example failure cases are shown in (d,e).

Figure 6 .

 6 Figure 6. Fine alignment by matching view-dependent contours. (a) Extracted edges (painting -red; 3D model -blue). (b) Shape context sample points and putative correspondences (green lines). (c) Dense edge inlier correspondences found by RANSAC.After each iteration, the viewpoint is updated. Notice that there are many inliers in the putative set and that the 3D model gets closer to the input painting with each iteration. The matching converges after seven iterations, with iterations 1, 2, 3, and 7 shown.

Fig

  Fig. 5(a) Fig. 5(b) Fig. 5(c) Fig. 5(d) Fig. 5(e) Mean Res. 476×600 456×550 474×578 459×550 640×393 640×388 640×390 480×547 475×550 GT 3.60 (0.47) 7.88 (1.10) 8.16 (1.09) 9.79 (1.37) 3.60 (0.48) 6.82 (0.91) 6.31 (0.84) 2.52 (0.35) 4.05 (0.56) 5.86 (0.80) Alg. 5.65 (0.74) 12.06 (1.69) 17.80 (2.38) 18.25 (2.55) 10.51 (1.40) 128.92 (17.23) 112.52 (15.01) 36.95 (5.08) 46.03 (6.33) 43.19 (5.82)

  .60 (0.47) 7.88(1.10) 8.16 (1.09) 9.79 (1.37) 3.60 (0.48) 6.82 (0.91) 6.31 (0.84) 2.52 (0.35) 4.05 (0.56) 5.86 (0.80) Alg. 5.65 (0.74) 12.06 (1.69) 17.80 (2.38) 18.25 (2.55) 10.51 (1.40) 128.92 (17.23) 112.52 (15.01) 36.95 (5.08) 46.03 (6.33) 43.19 (5.82)

								(e)	Mean
	Res. 476×600 456×550	474×578	459×550	640×393	640×388	640×390	480×547	475×550
	GT 3Table

The paintings and drawings were collected from publications found in European archives and libraries: Bibliothèque Nationale de France, Ecole nationale supérieure des Beaux Arts, Bibliothèque de l'Institut National d'Histoire de l'Art, Museo archeologico nazionale di Napoli, National Museum of Stockolm.

Acknowledgments. We thank Soprintendenza archeologica di Napoli e Pompei, for access to the site and the possibility of study; Margareta Staub Gierow (Archäologisches Institut, Albert-Ludwigs-Universität, Freiburg), for her collaboration in collecting archives in the National Museum of Stockolm. Supported in part by the MSR-INRIA joint laboratory, the ANR project DETECT (ANR-09-JCJC-0027-01) and the EIT ICT labs (activity 10863).


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

Josef Sivic
email: josef.sivic@ens.fr

Tomas Pajdla
email: pajdla@cmp.felk.cvut.cz

Visual localization by linear combination of image descriptors

We seek to predict the GPS location of a query image given a database of images localized on a map with known GPS locations. The contributions of this work are three-fold: (1) we formulate the image-based localization problem as a regression on an image graph with images as nodes and edges connecting close-by images; (2) we design a novel image matching procedure, which computes similarity between the query and pairs of database images using edges of the graph and considering linear combinations of their feature vectors. This improves generalization to unseen viewpoints and illumination conditions, while reducing the database size; (3) we demonstrate that the query location can be predicted by interpolating locations of matched images in the graph without the costly estimation of multi-view geometry. We demonstrate benefits of the proposed image matching scheme on the standard Oxford building benchmark, and show localization results on a database of 8,999 panoramic Google Street View images of Pittsburgh.

Introduction

The goal of this work is to predict the GPS location of a query image given a database of images with known GPS locations [START_REF] Se | Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks[END_REF][START_REF] Zhang | Image based localization in urban environments[END_REF]. This is a challenging task as the query and database images maybe taken from different viewpoints, under different illumination and partially occluded.

Significant progress has been recently achieved in largescale localization using efficient representations from image retrieval [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF][START_REF] Knopp | Avoiding confusing features in place recognition[END_REF][START_REF] Roshan | Accurate image localization based on google maps street view[END_REF][START_REF] Schindler | City-scale location recognition[END_REF] often coupled with geometric constraints provided by 3D models of the environment [START_REF] Baatz | Handling urban location recognition as a 2D homothetic problem[END_REF][START_REF] Irschara | From structure-frommotion point clouds to fast location recognition[END_REF][START_REF] Li | Location recognition using prioritized feature matching[END_REF].

We investigate a regression approach to the image-based location prediction problem and wish to find a mapping from some features of the query image to its position on the map, given a large database of geotagged images. The choice of the form of such a regressor is an important one Right: Corresponding image descriptors in the feature space. Considering distances between the query descriptor and 1D subspaces (shown in blue) given by affine linear combinations of image descriptors along edges in the graph can lead to better matches. The nearest neighbor descriptor to the query is incorrect (red).

and may depend on a number of factors including the feature representation, measure of image similarity, structure of the map and the number of images in the database. We formulate visual localization as two stage regression: In the first stage, we wish to find a subset, which we call the surrounding image set, of images in the database, which depict the same place (i.e. the same 3D structure) as the query. In the second stage, the goal is to interpolate the location of the query from GPS locations of images in the matched subset of the database.

In the first stage we opt for the efficient bag-of-feature representation that has demonstrated excellent performance in large-scale image/object retrieval [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Jegou | A contextual dissimilarity measure for accurate and efficient image search[END_REF][START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and place recognition [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF][START_REF] Knopp | Avoiding confusing features in place recognition[END_REF][START_REF] Schindler | City-scale location recognition[END_REF]. In addition, we model the geotagged image database as an image graph [START_REF] Li | Landmark classification in large-scale image collections[END_REF][START_REF] Philbin | Geometric latent dirichlet allocation on a matching graph for large-scale image datasets[END_REF][START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problem[END_REF][START_REF] Zheng | Tour the world: building a webscale landmark recognition engine[END_REF], where images are nodes and edges connect images at closeby locations on the map.

We design a matching procedure, illustrated in Fig. 1, that considers linear combinations of bag-of-feature vectors of database images along edges of the image graph.

Considering linear combinations of multiple feature vectors on the image graph can significantly improve matching accuracy by increasing robustness to missing or mismatched local image features, and improving generalization across viewpoint and illumination with only negligible effects on the computational cost at query time.

Given a set of matched images depicting the same 3D structure as the query, the camera of the query image can be estimated using structure from motion (SfM) techniques [START_REF] Hartley | Reconstruction from projections using Grassmann tensors[END_REF][START_REF] Snavely | Photo tourism: exploring photo collections in 3D[END_REF]. SfM methods are getting mature, but they are computationally expensive and often depend on good initialization. Therefore, for the second stage, we investigate how well the location of the query can be predicted by interpolating GPS locations of the matched database images using image-based similarity alone without estimating the multi-view geometry of the underlying scene.

The contributions of this work are three-fold: (1) we formulate the image-based localization problem as a regression on an image graph; (2) we design a novel image matching procedure, which considers linear combinations of image feature vectors along edges in the graph; (3) we demonstrate that query image location can be directly predicted by interpolating locations of matched images. [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF], and Knopp et al. [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF] perform large-scale appearance-based localization using the bag-of-feature representation but consider only matches to individual images in the database without considering linear combinations of bag-of-feature vectors. Schindler et al. [START_REF] Schindler | City-scale location recognition[END_REF] demonstrate appearance-based localization in a dense image sequence using vocabulary trees [START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF], spreading votes of individual query image features across close-by views on the map [START_REF] Lowe | Local feature view clustering for 3D object recognition[END_REF][START_REF] Silpa-Anan | Localization using an image-map[END_REF][START_REF] Zamir | Accurate image localization based on google maps street view[END_REF]. Zamir and Shah [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] localize query image using Google Street View imagery by matching individual feature descriptors (not quantized into visual words) and analyzing spatial distribution of the matches on the 2D map.

Related work: Cummins and Newman

Our similarity measure considers linear combinations of feature descriptors is in spirit similar to query expansion [START_REF] Chum | Total recall II: Query expansion revisited[END_REF][START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], which significantly improves object retrieval performance. We consider all linear combinations (rather than the average), expand the database (rather than the query) and compute the expansion in a closed form at query time, without ever computing and storing additional bag-offeature vectors [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] or descriptors [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problem[END_REF] on the database side.

Irschara et al. [START_REF] Irschara | From structure-frommotion point clouds to fast location recognition[END_REF] considered localization using SfM point clouds and generated synthetic views from a 3D model enabling generalization to unseen viewpoints. 3D point cloud is also used by Li et al. [START_REF] Li | Location recognition using prioritized feature matching[END_REF] who select a subset of 3D features that appear and were successfully matched in many database images. In contrast, we investigate localization by interpolating positions of database images without the costly 3D reconstruction, which might not be always available. We focus on street-side imagery such as Google Street View rather than video sequences [START_REF] Irschara | From structure-frommotion point clouds to fast location recognition[END_REF] or landmark image collections [START_REF] Li | Location recognition using prioritized feature matching[END_REF].

Combinations of feature vectors lead to smaller image databases. Hence, our approach is also related to methods compressing the image datasets for localization and retrieval. Previous work in this area include methods based on image graphs [START_REF] Li | Landmark classification in large-scale image collections[END_REF][START_REF] Philbin | Geometric latent dirichlet allocation on a matching graph for large-scale image datasets[END_REF][START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problem[END_REF][START_REF] Zheng | Tour the world: building a webscale landmark recognition engine[END_REF], epitomes [START_REF] Ni | Epitomic location recognition[END_REF], 3D point clouds [START_REF] Irschara | From structure-frommotion point clouds to fast location recognition[END_REF][START_REF] Li | Location recognition using prioritized feature matching[END_REF], or selecting representative features [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF][START_REF] Li | Probabilistic location recognition using reduced feature set[END_REF][START_REF] Schindler | City-scale location recognition[END_REF]. In particular, we build on the image graph methods, but create the graph using the structure of the 2D map (rather than matching images) and enhance generalization by considering linear combinations of feature vectors along edges of the graph.

Place recognition has been in part formulated as a linear classification task in a discrete set of predefined landmarks [START_REF] Li | Landmark classification in large-scale image collections[END_REF] or nearest-neighbor scene matching to obtain a coarse localization on the level of cities or continents [START_REF] Hays | im2gps: estimating geographic information from a single image[END_REF]. In this work, we formulate the image-based localization as a regression problem and introduce a new, two-stage regression algorithm. Our regression approach is different from the standard regressors, such as e.g. kernel ridge regression [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], that typically consider only datapoint similarities in the feature space. In our case, we take advantage of the fact that images are organized on the map and build this structure into the regressor directly by considering linear combinations of pairs of spatially close images, given by the image graph.

Localization as regression on image graph

Next, we formulate the image-based localization task as a regression problem and outline the two-stage structure of the proposed regression function.

The problem formulation:

We represent the visual content of images by their (tf-idf weighted [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF]) bag-offeatures [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] descriptors d, which are vectors of dimension between 10 4 and 10 6 , depending on the vocabulary size.

We consider an image map organized as a graph G = (D, E) with N vertices D = {(d i , x i )} N i=1 consisting of image descriptors and their corresponding locations on a planar map represented by two-dimensional vectors x i . Edges E of G link close views, which share visual content. In Google Street View data, for instance, D corresponds to panoramic images and E corresponds to links allowing to navigate from an image to its neighbours. In landmark datasets, such as the Oxford building benchmark set [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], edges may link images which share a planar structure which was successfully matched by a homography.

We introduce a localization function f

x q = f (q, G) (1)
that provides the location x q of a descriptor q using an image map G.

We will demonstrate that edges E provide a very convenient structure for image based localization and allow to localize query more accurately than individual image descriptors. Consider a pair of descriptors d 1 , d 2 , which are linked by an edge, i.e. close-by views in the image map. Now, imagine a query descriptor q, from somewhere between the map views. Such q will likely share content with both descriptors d 1 , d 2 . It will be more similar to some combination of d 1 , d 2 than to each of them individually. We will show that linear combination of d 1 , d 2 is a meaningful combination which improves the performance of visual localization.

We will next focus on developing a suitable localization function f , given a visual map G and a representative query set D Q . In the experimental results, section 5, we will investigate localization performance with respect to different natural choices of G, corresponding to different densities of images in the image map. We focus on the analysis of the maximal error, and study the localization performance with respect to the percentage of query images localized within a given maximum distance.

Two stage regression on an image graph:

We consider a set of localization functions constrained by the fact that we wish to predict the relative location of the query image w.r.t. only its surrounding images on the map, which share visual content with the query. The number of such surrounding images depends on the visible 3D structure (e.g. a narrow street vs. an open square), but in typical urban environments would be rather small.

Motivated by this constraint, it is natural to construct f in two consecutive steps. In the first step, (a subset of ) the surrounding images that share the visual content with the query is identified and, in the second step, the location of the query w.r.t. the surrounding images is computed. This twostep approach is also desirable since efficient image search techniques [START_REF] Jegou | On the burstiness of visual elements[END_REF][START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] can be used to generate potential surrounding images and more expensive techniques of image matching with geometric verification can then be used within the surrounding set [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. In this work, though, we will consider purely image-based approaches with no explicit use of multi-view geometry for the second step.

In particular, we consider a linear regression localization function f of the form

x q = s∈S(q) w s x s (2)
where x q is the predicted location of the query and

S(q) = f S (q, G) (3)
is the subset of G determining the surrounding set for query vector q obtained by a surrounding set retrieval function f S .

Next section describes details of obtaining the surrounding set for query vector q and section 4 describes how we obtain the predictive weights w s , for a particular surrounding set.

Matching linear combinations of surrounding views

In this section we define surrounding image sets for a given visual map and explain how we perform retrieval by matching linear combinations of surrounding views linked by edges of E. Surrounding views. Given query q, we wish to determine graph S(q) = (D S , E S ) -a subset of visual map Gwith images D S that share visual content with q.

We observed that the query descriptor vector q is often approximated well by a linear combination of descriptor vectors of images linked by edges in S(q). The intuition behind this approach is twofold. First, visual words present in the query vector, but missing in an individual database image, e.g. due to occlusion but also noise in detection and quantization, could be "filled-in" when multiple images are considered. Second, considering linear combinations of feature vectors is a form of view interpolation, but here performed in the high-dimensional feature space, which effectively expands the database to intermediate views.

With the above motivation, we are looking for a surrounding graph S(q), which consists of only one edge from G. For instance, we exploit the structure of the Google Street View image database which is arranged into a planar graph such that images with small graph distance [START_REF] Diestel | Graph Theory[END_REF] share visual content. By restricting possible S(q) to pairs of images with unit graph distance, we assure that images of S(q) share visual content and can be meaningfully combined by the linear regressor (2). This choice is in particular appropriate for city street localization where only spatially close images, often captured in a sequence along a street, share useful visual content.

It will become clear from the experiments presented in section 5 that the nearest neighbor (NN) matching is sensible, especially for dense maps. For sparser maps, however, it is more successful to retrieve pairs of images with small graph distance. The intuition behind this observation is illustrated in Fig. 1.

The best matching pair S(q) to the query q is obtained by finding the most similar affine combination among all pairs defined by E, where α is the parameter of the affine combination. The minimum over α can be obtained in a closed form as

S(q) = argmin (i,j)∈E min α∈R q-((1-α) d i +α d j ) 2 , (4)
α * = (d j -d i ) ⊤ (q -d i ) d j -d i 2 . ( 5
)
Linear and convex combinations can be also considered. In our case, however, we found that there was no difference between the affine and convex combination and only a very small (a fraction of a percent) difference in performance between the affine and linear combination. The advantage of the affine (and convex) combination is that it is determined by one parameter and hence it facilitates one-dimensional linear regression of the next prediction step (Section 4). Note also, that as the minimum over α can be computed in a closed form, considering linear combinations of feature vectors has only a small effect on the efficiency of the localization. In particular, as in object retrieval [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] efficient inverted file indexing [START_REF] Witten | Managing Gigabytes: Compressing and Indexing Documents and Images[END_REF] can be used to compute inner products between the query and database vectors, which are in turn used to compute optimal α for each pair. In addition, for typical image maps the number of considered image pairs (i.e. edges in the image graph) grows only linearly with the number of images in the image map.

Equipped with the surrounding set S(q) for the query, composed of a pair of images, we now consider the prediction of the query location.

Predicting position of the query image

In this section, we discuss how to obtain weights w s in the predictor given in [START_REF] Bay | SURF: Speeded up robust features[END_REF]. While it may seem that the affine combination parameter α * can be used directly for predicting the location of the query, it turns out that such predictions are significantly biased towards the mean of locations in the pair of surrounding views. This might be explained by missing visual words in the query with respect to its surrounding views, due to occlusions, missed detections or variations beyond invariance built into the descriptor vector. To see this, consider an example where the query image is taken at exactly the same position as the first image in the surrounding set, i.e. x q = x 1 . Ideally, from (2), the desired output would be w 1 = 1 and w 2 = 0. However, due to potential differences in lighting, occlusions and measurement noise, q = d 1 and hence α = 0.

We found that the best predictor of query location is obtained as follows. First, we compute the relative similarity of query to both images in the best matching surrounding set,

β = q ⊤ d s1 q ⊤ d s1 + q ⊤ d s2 . (6)
We examine many descriptors q and their corresponding surrounding images S(q) = (s 1 , s 2 ) and express the position of q as the affine combination of its surrounding images

x q = x s1 + ξ (x s2 -x s1 ).
We thus obtain the corresponding location interpolator ξ. Then, we have also obtained the corresponding relative visual similarity β according to [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF]. Fig. 2 shows values of ξ against values of β for many real images. We can see that there is a strong affine dependence of ξ on β and therefore it is possible to estimate ξ from β by an affine interpolator

ξ q = a 0 + a 1 β. (7)
Given this observation, we train parameters a 0 , a 1 on an independent representative set of images and then use them to predict query position x q as

x = x s1 +(a 0 +a 1 β)(x s2 -x s1 ) with (s 1 , s 2 ) = S(q) (8)
where S(q) is determined by (4) and β by (6).

Results

We evaluate the benefits of considering pairs of feature descriptors along edges in the image graph for image matching and location prediction.

Matching performance. The matching performance is evaluated on two tasks: (i) matching panoramic images from Google Street View and (ii) matching perspective images from the standard Oxford Buildings benchmark [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

In the first task, we use the Google Street View Pittsburgh Research Data Set ("Street View Research"), which consists of a sequence of 8,999 panoramic images. We first downsample all images to 1,664 × 512 pixels (half the original size) to reduce the number of feature detections. The images are then described by the bag-of-features representation [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]: 1) SURF descriptors [START_REF] Bay | SURF: Speeded up robust features[END_REF] are extracted, 2) visual vocabulary of 100,000 visual words from SURF's from every 20th image is built by approximate k-means clustering [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], 3) tf-idf weighted vectors [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] are computed by quantizing the SURF descriptors using the visual vocabulary and re-weighted according to the number of occurrences of each word in the database, 4) tf-idf vectors are normalized to unit length and 5) the image similarity is computed as the inner product of tf-idf vectors. Figure 3. Matching performance for the proposed method (AC) (red), the similarity averaging approach (Ave) (green) and the baseline nearest neighbor based approach (NNnbh) (blue). The error is measured as the percentage of mismatched query images (y-axis) for different database sampling rates ∆ (x-axis). A mismatch is declared when the query is not assigned (a) to the correct (ground truth) edge in the graph or (b) to the correct edge or its neighbors in the graph (a less strict criteria than (a)). Note the significant reduction in error rate for AC compared to baseline NNnbh. AC outperforms the Ave method if exact match is required (a), but both methods perform similarly in coarse-level matching (b).

We use subsets of the odd numbered frames as the image database D with known GPS locations and all even numbered frames as the query set D Q . The image map, represented by graph G, is constructed by regularly sampling every ∆-th image from the database D. We call ∆ sampling rate. Edges of the graph are obtained by connecting consecutive images along the (known) acquisition sequence. In the Street View Research Set, where images are roughly spaced by 1 meter, sampling rate of ∆ ∈ {5, 10, 15, 20, 25} corresponds roughly to image spacing of {10, 20, 30, 40, 50} meters (recall that half the original images are set aside as the query set). Note that by construction, each query image from the query set D Q lies along one edge of graph G, which defines the ground truth surrounding set for the query. The goal of matching is to find the correct surrounding set for each query. We investigate matching performance of the linear combination method (AC) and the averaging method (Ave), which finds the best matching pair by averaging the image descriptor vectors along the edge (equivalent to fixing α = 0.5, or averaging the similarity scores). The results are compared to a baseline method (NNnbh), which finds the best nearest neighbor image followed by finding the second nearest neighbor within the two surrounding locations of the best match. Fig. 3 shows the matching performance with respect to varying database sampling rate ∆.

In the next experiment we use 1,143 Pittsburgh Google Street View images ("Street View Web") as the image map. The image graph is defined by the connectivity between the images as used to navigate on maps.google.com. Images and the graph structure were downloaded from maps.google.com. All images from the Street View Research dataset are used as queries. This is a realistic and ex- tremely challenging scenario, where (most of) the database and test images are obtained under different acquisition conditions (different season, time of day, path, etc). The spacing between the database Street View Web images is between 10-20 meters, which corresponds approximately to sampling rates of 5-10 on the Street View Research data. The proposed approach (AC) is compared to the nearest neighbor matching baseline (NN), its modification (NNnbh) and the averaging based method (Ave) described above. Results are shown in Fig. 4 and examples of correctly and incorrectly matched queries are shown in Fig. 5.

We also evaluate image pair matching on the Oxford Building Dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], a standard benchmark dataset for object retrieval. We use the tf-idf vectors from [10] and obtain the image graph from the authors of [START_REF] Philbin | Geometric latent dirichlet allocation on a matching graph for large-scale image datasets[END_REF]. The image graph has 34,028 edges and is built based on the efficient pairwise matching with geometric verification using planar homographies to ensure that images connected by edges contain the same 3D structures. Retrieval performance is evaluated using the standard mean average precision (mAP) over all 55 queries. Given a query, retrieval using the image graph is performed as follows: (i) all nodes are scored using the similarity (inner product) to the nearest neighbor (NN) [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF];

(ii) all edges are scored using the proposed linear combination method; (iii) images are ranked using the highest scoring edge (if connected) or their individual score (if singletons). We compare four different edge scoring methods for retrieval using the image graph: (a) the linear combination approach and (b-d) the average/max/min similarity of the two images along the edge. Results are compared to the nearest neighbor (NN) [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and NN with soft-assignment (SA) [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] baselines in table 1. Example matches are shown in Fig. 6. All image graph methods significantly improve over the baseline nearest neighbor (NN). In addition, combining images along edges in the graph, either by considering their linear combinations (AC) or averaging their sim-

Baselines

Image graph methods NN [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] SA [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] AC Ave Max Min 0.6138 0.6694 0.7589 0.7546 0.7020 0.6138 Table 1. Mean average precision (mAP) on the Oxford building dataset for the baseline nearest neighbor (NN) and nearest neighbor with soft-assignmnet (SA) methods compared with different image graph retrieval methods that combine images along edges in the graph.

ilarities to the query (Ave), improves over considering images along the edge individually (Max / Min methods) as well as the soft-assignment (SA) baseline. Although the AC method performs the best, the Ave method performs also well. This maybe due to the nature of the benchmark, which evaluates retrieval (i.e. finding all matches containing the query object) as opposed to localization (accurately finding the closest matching pair), where estimating the precise value of α may not be that important. To further evaluate benefits of linear combination matching a dataset with accurate image locations will be necessary. The proposed graph-based matching/localization approaches (AC or Ave) are also memory efficient, as no new views need to be synthesized [START_REF] Irschara | From structure-frommotion point clouds to fast location recognition[END_REF] or individual descriptors propagated to neighboring views [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problem[END_REF]. Finally, further matching improvements are expected by combining the proposed approach with the expansion on the query side [START_REF] Chum | Total recall II: Query expansion revisited[END_REF][START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]. sion parameters in [START_REF] Diestel | Graph Theory[END_REF] and are removed completely from the query set and the database. We measure the localization performance by the percentage of query images, which are localized within gt dist meters from their ground truth GPS location. Again, we investigate performance when varying this localization accuracy threshold.

Predicting
We compare performance of the proposed method (AC) with the standard nearest neighbor baseline (NN), where the query location is predicted as the location of the nearest neighbor to the query. We have also experimented with variations of the NN approach where, the query location is predicted as a (learnt) linear combination of the two nearest neighbor locations in the feature space or a (learnt) linear combination of the nearest neighbor and the second nearest neighbor within surrounding locations. However, we found that the simple NN approach performs the best. Fig. 7 compares the localization performance between the proposed method (AC) (y-axis) and the baseline nearest neighbor approach (NN) (x-axis). When the curves lie under the dashed line the proposed method AC performs better than baseline NN. It is interesting to study the result of sampling rate ∆ = 5 and 10, which corresponds to blue and black curves, because the spacing of 10 to 20 meters is roughly the spacing of Google Street View images available on the Internet. The improvement by AC is significant especially with small localization tolerance threshold gt dist . For example, for ∆ = 5 (see the blue curve in Fig. 7(b)), which corresponds roughly to spacing of 10 meters between images in the image map, and localization tolerance gt dist = 5 meters, the nearest neighbor approach incorrectly localizes about 6% of query images, while the proposed approach reduces this error to half (about 3%). Fig. 9 shows examples of correctly localized queries using the proposed linear combination matching. Fig. 8 illustrates the benefits of using the learnt two-stage regressor over using directly the relative similarity score β to predict the query location.

Note that the better performance of the proposed approach over the baseline NN method is due to two reasons.

First, the proposed method can find the correct surrounding set, in cases when the NN method fails, i.e. considering linear combinations of close-by views provides better matches to the query. Second, once the correct surrounding set is found, the proposed method can more accurately predict a the location of the query as a (learnt) linear combination of locations of the images in the surrounding set.

Scalability: Practical image based localization has to aim at working with millions of images. The state of the art approaches to image search [START_REF] Jegou | On the burstiness of visual elements[END_REF][START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] are based on efficient search for the single most similar (NN) descriptor.

In this work we replace the search for the single most similar descriptor by a search for a pair of descriptors. Although searching for pairs might be too expensive in general, the structure of visual localization makes searching for pairs (almost) as efficient as searching for individual descriptors.

Consider that each image in the image map has only a small number of its potential surrounding sets and therefore the size of surrounding sets is linear (with the slope 1 to 3) in the number of images in the database. For instance, if the database of N images is arranged as a sequence, there is only N -1 surrounding pairs to consider. In case of fully planar localization, when image pairs would be replaced by image triplets, the number of triangles to consider would be maximally 3 N -6 (consider Euler formula for a planar triangulated graph). This makes our technique as scalable as the search for the most similar descriptor at a considerably better performance.

Conclusions

We have formulated the image-based localization task as a regression problem on an image graph and developed a two stage regressor, which takes advantage of the graph structure of the database. We have shown that considering linear combinations of descriptors along edges in the image graph significantly improves matching accuracy over the standard nearest neighbor matching. We have considered linear combinations of two close-by images, which is well suited for matching street-side imagery. The concept, however, can be generalized to image triplets or n-tuples, which may be considered for other scenarios where the 2D visual map is densely connected. Finally, we have used the bagof-features representation, but the proposed approach can be used with other image descriptors developed for largescale matching [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF].

Figure 1 .

 1 Figure 1. Illustration of matching linear combinations of surrounding views on an image graph. Left: Images localized along a path on a 2D map. Images are connected by edges (dotted lines), defining an image graph. The query image is shown in black.Right: Corresponding image descriptors in the feature space. Considering distances between the query descriptor and 1D subspaces (shown in blue) given by affine linear combinations of image descriptors along edges in the graph can lead to better matches. The nearest neighbor descriptor to the query is incorrect (red).

Figure 2 .

 2 Figure 2. Values of the spatial interpolator ξ as a function of the relative similarity β, given by (6), for many training query images sampled along lines connecting image map images. Notice the affine dependence of ξ on β.

Figure 4 .

 4 Figure 4. Matching pairs of Street View images. Y-axis shows the fraction of incorrectly matched query test images ("Street View Research"). Query image is considered mismatched if the best matched database image ("Street View Web") is further than "Thr" meters (x-axis) from the ground truth nearest neighbor in the database. Note the reduction in matching error by the proposed linear combination matching method (AC) compared to the three other baselines (see text for details).

Figure 5 .

 5 Figure 5. Examples of a matched (left column) and a mismatched (right column) query. The map (middle column) shows all matched (red) and mismatched (gray) query images ("Street View Research"). Database images ("Street View Web") are shown in blue. Query image is considered mismatched if the best matched database image is further than 20 meters from the location of the ground truth nearest neighbor.

Figure 7 .

 7 Figure 7. Localization error measured by the percentage of mismatches of the proposed method (AC) (y-axis) vs. the baseline nearest neighbor approach (NN) (x-axis). Each curve shows accuracy for a fixed sampling rate ∆. Each marked point on the curve corresponds to a particular value of the localization tolerance gt dist in meters. The values of gt dist are shown next to each point. (b) is a close-up of (a) at the origin.

Figure 6 .Figure 8 .

 68 Figure 6. The benefits of linear combination matching for retrieval on the Oxford building dataset. Each triplet shows: query image (left) and a pair of images along an edge in the image graph, which were low ranked individually, but matching the query to the linear combination of their tf-idf vectors significantly improved their ranking.

Figure 9 .

 9 Figure 9. Examples of correct localization on the map with sampling rate ∆ = 5 using the proposed method. (a) Query image. (b-c) The image pair selected by the proposed matching of linear combinations of image descriptors (correct). (d-e) The first two nearest neighbors (1st NN is incorrect). The distance between images (b) and (c) on the visual map is about 10 meters. The predicted location of the query is within 3 meters of its true location.

  query location. Here we evaluate the localization accuracy of the complete two stage regressor using the Street View Research dataset.The data is split again into the database set D and the query set D Q as outlined above. The last 900 frames of the sequence are used as training data to obtain the regres-

		50				20
	AC+WM: mismatches [%]	0 0 10 20 30 40 10 11 12 13 6 7 8 9 14 15 16 17 18 19 20 12 11 10 5 10 13 14 15 16 17 18 19 20 14 9 13 15 16 17 18 19 20 17 20 4 8 11 7 12 14 30 9 3 10 12 11 40 6 8 10 5 7 13 15 16 18 19 20 1-to-1 ∆ = 5 ∆ = 10 ∆ = 15 ∆ = 20	9	50	AC+WM: mismatches [%]	0 2 4 6 8 10 12 14 16 18 20 0 2 4 6 8 10 12 14 16 18 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 8 9 10 11 12 14 15 16 17 18 19 20 13 12 13 14 15 16 17 18 19 20 16 17 18 19 20
		NN mismatches [%]				NN mismatches [%]

Acknowledgements

This work was partly supported by the MSR-INRIA laboratory, the ANR project DETECT (ANR-09-JCJC-0027-01), the EIT ICT labs (activity 10863), ME CR MSM 6840770038, CTU SGS10/190/OHK3/2T/13 and FP7-SPACE-241523 PROVISCOUT grants.