Stefan Lee

Nicolas Maisonneuve

David Crandall

Alexei A Efros

Josef Sivic

Linking Past to Present: Discovering Style in Two Centuries of Architecture

With vast quantities of imagery now available online, researchers have begun to explore whether visual patterns can be discovered automatically. Here we consider the particular domain of architecture, using huge collections of street-level imagery to find visual patterns that correspond to semantic-level architectural elements distinctive to particular time periods. We use this analysis both to date buildings, as well as to discover how functionallysimilar architectural elements (e.g. windows, doors, balconies, etc.) have changed over time due to evolving styles. We validate the methods by combining a large dataset of nearly 150,000 Google Street View images from Paris with a cadastre map to infer approximate construction date for each facade. Not only could our analysis be used for dating or geo-localizing buildings based on architectural features, but it also could give architects and historians new tools for confirming known theories or even discovering new ones.

Introduction

With the era of "big data" at hand, many academic disciplines are beginning to use online data to perform analyses that would have been impossible with traditional methods. For example, collaborations between sociologists and computer scientists are using online social network data to measure human behavior at unprecedented scales [START_REF] Lazer | Computational social science[END_REF], while work in health informatics is using online data to monitor outbreaks of diseases [START_REF] Ginsberg | Detecting influenza epidemics using search engine query data[END_REF] and to predict their spread [START_REF] Salathé | Digital epidemiology[END_REF] (albeit with some controversy [START_REF] Ruths | Social media for large scale studies of behavior[END_REF] and missteps [15]). In the humanities, analysis of online data has given insight into historical legal records [14] and the dynamics of cultural history [START_REF] Schich | A network framework of cultural history[END_REF]. Large-scale analysis of digitized books through several centuries has been used to quantify changes in linguistic and cultural phenomena over time [START_REF] Michel | Quantitative analysis of culture using millions of digitized books[END_REF].

The vast majority of this analysis has been on textual content, often looking at simple features like occurrences and co-occurrences of keywords [START_REF] Ginsberg | Detecting influenza epidemics using search engine query data[END_REF][START_REF] Michel | Quantitative analysis of culture using millions of digitized books[END_REF]. But analyzing im-Figure 1: Using thousands of Street View images aligned to a cadastral map, we automatically find visual elements distinctive to particular architectural periods. For example, the patch in white above was found to be distinctive to the Haussmann period (late 1800's) in Paris, while the heat map (inset) reveals that the ornate balcony supports are the most distinctive features. We can also find functionally-similar elements from the same and different time periods (bottom). ages could help unlock other latent sources of data for the sciences and humanities. Some work has investigated using vision to organize and navigate historical images [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF][START_REF] Schindler | 4d cities: analyzing, visualizing, and interacting with historical urban photo collections[END_REF] and to discover hidden features in artwork [START_REF] Kim | Large-scale quantitative analysis of painting arts[END_REF][START_REF] Stork | Computer vision and computer graphics analysis of paintings and drawings: An introduction to the literature[END_REF], but is limited in scale by the relatively small number of artifacts available. In these cases when big datasets are not involved, human experts can often perform the analysis as well and as quickly as the automated algorithms.

Here we consider a domain in which we can study the dynamics of the past through vast image collections from the present: architecture. Architecture involves creating buildings "taking both aesthetic and practical factors into account" [START_REF]The Oxford Dictionary of English[END_REF]. Thus architectural styles change over time, reflecting the evolving artistic design, social and cultural attitudes, and technological and socioeconomic conditions of the peoples that built them. Studying features of buildings gives a window into the past, letting us observe properties of style and design at the time they were built.

Of course, manually collecting building data and images would be extremely tedious. We propose a novel analysis using Google Street View images geo-referenced against digitized maps. Street View includes street-level imagery from over 5 million miles of roads in more than 39 countries and 3,000 cities [START_REF] Farber | Google takes Street View off-road with backpack rig[END_REF], capturing a huge number and variety of buildings around the world. For a given city (in our case, Paris), we associate individual building facades within Street View images and fine-grain urban planning records, letting us annotate each individual facade image with an approximate year of its construction.

With these combined data sources, we use mid-level visual features (similar to those of Doersch et al. [START_REF] Doersch | What makes Paris look like Paris?[END_REF]) to discover visual elements that are distinctive to particular architectural periods. We visualize these features over space and time, using a novel graph-based formulation to find functional elements (e.g. windows, doorways, etc.) whose style has changed across periods. In our experiments, we apply this analysis to nearly 150,000 images of 120,000 buildings of Paris. We show that these visual elements are useful for classifying the architectural style and construction date of buildings based on visual information alone (which could be useful for example for geo-localizing images by matching to city planning maps or for dating vintage photos), while potentially also generating new insights into how architectural styles have changed over time.

A key challenge is that we want to perform all of this analysis automatically. It is easy to find repeated visual elements in Street View, but most correspond to architecturally uninteresting objects like signs, bus stops, etc. We are instead interested in elements having roughly the same appearance because they correspond to the same function (balconies, windows, etc.), but whose appearance changes across time as styles evolved. Of course, boundaries between architectural styles are inherently blurry with a high degree of visual similarity between adjacent periods, and multiple distinct styles can exist within one time period. Important stylistic elements also wax and wane in popularity and can quickly rise to prominence only to be forgotten. Our approaches allow us to detect many diverse features, and connect functionally-similar elements through time with arbitrary start and end points. We evaluate our techniques both quantitatively and qualitatively.

To summarize our contributions, we:

1. generate large-scale architecture datasets automatically, using a novel combination of Street View image data aligned to cadastral maps; 2. discover architectural elements distinctive to particular time periods; 3. visualize these elements in detail, including which subelements make them distinctive, and how they combine to form distinctive facades; 4. find chains of visual elements corresponding to functional elements whose appearance has evolved; and 5. evaluate these techniques both quantitatively and qualitatively on a dataset of Paris.

Related Work

Perhaps most related to this paper is work in midlevel visual mining that tries to find discriminative image patches. Doersch et al. [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF][START_REF] Doersch | What makes Paris look like Paris?[END_REF] discover patches that discriminate between different cities using geo-referenced street-level imagery from Street View. The method requires iterative refinement of the patches using SVMs. Like us, Lee et al. [START_REF] Lee | Style-aware mid-level representation for discovering visual connections in space and time[END_REF] consider the temporal domain, finding style-independent classifiers of style-discriminative elements present throughout multiple time periods (like automotive headlights, which have been on cars for fifty years but whose style has changed dramatically over time). Our work also tries to find patches with similar semantics through time, but we face the additional challenge that elements in architecture are much more dynamic, with certain elements such as window shutters rising to prominence for decades only to fall out of favor later. Some work in computer vision has considered architecture applications, including classifying between different architectural styles. For example, Shalunts et al. [START_REF] Shalunts | Architectural style classification of building facade windows[END_REF]26] classify specific elements like windows and domes into three architectural periods (Gothic, Baroque, and Romanesque). Their results are promising, although their dataset was small (a few hundred images manually cropped around each element), in contrast to our huge collection of unconstrained Street View images. Xu et al. [START_REF] Xu | Architectural style classification using multinomial latent logistic regression[END_REF] classify whole building facades in about 5,000 images from Wikimedia, where buildings are well-centered and in full view. Since Wikimedia images are selected to be good examples of specific styles, they exhibit little of the blending and other complications that one observes in practice. They use deformable part-based models to visualize which facade elements are characteristic of which styles. Other work parses facade images into predefined elements such as doors, walls, windows, roofs, and balconies [START_REF] Berg | Parsing images of architectural scenes[END_REF][START_REF] Simon | Parameter-free/pareto-driven procedural 3d reconstruction of buildings from ground-level sequences[END_REF][START_REF] Weissenberg | Is there a procedural logic to architecture?[END_REF]. These approaches generally require cropped and rectified facade images. Though this parsing allows for well-aligned comparison of elements, defining elements by hand can be tedious and can introduce bias, so we instead follow a datadriven approach here in which elements are discovered automatically from large-scale image data.

Other recent work has used Google Street View, but for other applications than ours. Arietta et al. [START_REF] Arietta | City forensics: Using visual elements to predict non-visual city attributes[END_REF] use regressors based on mid-level patches to predict geospatially dis- tributed statistics such as crime rate and wealth. Ordonez and Berg [START_REF] Ordonez | Learning high-level judgments of urban perception[END_REF] predict attributes of neighborhood safety, uniqueness, and wealth. Zhou et al. [32] demonstrate that the frequency with which Street View images contain certain attributes like green space, tall buildings, water, and social activities can be used to identify a particular city.

Data

We start by introducing our large-scale dataset of building facades constructed through many time periods. Rather than manually photographing buildings and researching their construction dates, we employ a noisy but automated process combining images from Google Street View, a 3D city map, and real estate records. We focus here on Paris, because it is one of the world's best-known cities and because fine-grained data on building construction dates is available (but our analysis could be easily applied to any other city covered by Street View).

Fine-grained building geometry. We use a digital cadastre (a survey of real estate boundaries) of Paris to retrieve detailed building geometry and construction dates. The cadastre was provided by the Paris Urban Planning Agency (Atelier Parisien d'Urbanisme) [2] and comes prepared in a standard GIS format including over 120,000 buildings (almost the entire city). The building geometries are recorded as 2d polygons plus maximum building height. Almost all of the buildings have a label indicating their coarse construction period, in terms of 10 periods: pre-1800, 1801-1850, 1851-1914, 1915-1939, 1940-1967, 1968-1975, 1976-1981, 1982-1989, 1990-1999, and after 2000. Some periods contain more buildings, like 1851-1914 during which the city grew from about 1 to nearly 3 million citizens. The cadastre also includes construction years for about 57% of buildings, although like much real-world data, these are noisy (for example, a suspiciously large number of years are divisible by 10).

Street View images. We collected every current Street View image and location metadata taken within the Paris city limits, yielding about 145,000 panoramas. The images were primarily captured in 2008 and 2012, with only about 11% captured in other years. The panoramas are composites of multiple images and have a resolution of about 13,300 by 6,600 pixels. They were generated from arrays of 9 to 15 cameras using Google's custom Street View vehicles [START_REF] Anguelov | Google Street View: Capturing the world at street level[END_REF].

Combining Street View and cadastre data. To link Street View images and building information, we need to align the images with the cadastre data. Each Street View image has a GPS coordinate, but we must still decide which buildings an image has captured and how to crop the panoramas to extract individual images. To do this, for each panorama we look up the Street View vehicle's heading from the metadata and cast rays in 160 • cones from each side of the vehicle. The rays are cast at 1 • intervals and are 30 meters long, which is sufficient to reach the buildings on even the larger Parisian thoroughfares (see Figure 2a). We compute the first facade encountered by each ray, and select the pair of rays from each facade with the greatest angular difference (see Figure 2b). We then crop and warp the panoramas to produce multiple facade images per Street View panorama.

A temporally labeled architectural dataset. Many of these 450,000 candidate facade images are not suitable for analysis because of extreme skews and angles of view. We remove facades which we see too narrowly, thresholding at a minimum field of view of 50 • . To avoid images with high degrees of perspective warping, we remove facades that are within 5m of the camera or that are more than 10 degrees askew from the heading direction. This leaves us with images that are nearly parallel to the vehicle, such that the building facade is approximately planar. We crop the ground floor from all facades, since ground floors are often renovated and are poor representations of period architecture. From the remaining 70,000 facades, we sampled 20,000 images for analysis, evenly distributed among the construction periods such that each has 2,000 facades.

Discovering period-discriminative elements

Given our large dataset of building facades with time period annotations, our goal is to automatically discover discriminative architectural elements, and to capture their characteristics at multiple scales through time. We begin by finding patches that are highly representative of their respective time periods, by randomly sampling candidate patches and then performing nearest neighbor searches to evaluate discriminativeness. We then connect high quality patches to discover evolving trends across time periods.

Candidate generation

We begin with a mining approach similar to that of Doersch et al. [START_REF] Doersch | What makes Paris look like Paris?[END_REF], generating a large set P of candidate visual elements by sampling 25 patches at different resolutions from each of 2,000 images (which are then withheld from the remaining analysis). These images were selected uniformly across the periods, with low-gradient regions ignored during patch extraction. We represented each patch in Whitened HOG (WHO) space [START_REF] Gharbi | A gaussian approximation of feature space for fast image similarity[END_REF]12], with WHO mean and covariance parameters learned over the 2,000 images. For each of the 50,000 patches, we build a set of initial "detections" by finding the closest match in each of the remaining 18,000 images, across all scales of the WHO pyramid. The result is a set of nearly 1 billion associations between images and patches, which we denote C = {C 1 , C 2 , ..., C 50000 } where C i = (D i,1 , ..., D i,18000 ) and D i,j is the location and WHO distance of the best match of patch i in image j, sorted in order of increasing distance.

Identifying stylistically important elements

We define a patch to be stylistically important if it occurs often in one construction time period and rarely in others [START_REF] Lee | Style-aware mid-level representation for discovering visual connections in space and time[END_REF]. For each patch C i , we find the closest 200 image matches (i.e. D i,1 , ..., D i,200 ) to evaluate its discriminativeness. We observe that matches past these 200 often degrade to the point that visual correspondences are weak and would add noise to our analysis. (If our task were classification, we would not be concerned about this noise as long as it improved performance, but here we are attempting to find salient elements.) To evaluate each candidate C i , we give each of the 200 close detections a binary label indicating whether the close detection is in the same period as the candidate. We define a simple linear classifier

f i (x) = sign( Ĉi • x + b i ),
where Ĉi is the whitened HOG descriptor of the candidate written as a vector, and b i is a scalar bias. This choice of classifier is justified because the vector Ĉi can be interpreted as a classifier trained with the square loss from the candidate C i as a positive example and large number of negative data points [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF][START_REF] Gharbi | A gaussian approximation of feature space for fast image similarity[END_REF]12].

We apply f i (x) to each of the image matches D ij and vary b i to produce a precision-recall curve. We rank the candidates C i by area under the curve (AUC), because candidates high AUC should be distinctive to a given period. We prune this set by finding candidates that have overlapping detections (i.e. two detections in the same image which have an intersection over union greater than 0.5) and removing the one with the weakest rank. Typically this process culls the population down to a few thousand per period. This procedure finds visual elements whose appearance correlates with building age, and ignores other common elements found throughout the city (like pavement, signs, bus stops, etc.) due to their very poor ranking; Figure 4 shows some examples. Some of the remaining elements are distinct to a given period, while others correspond to elements that have undergone visual evolution, as we now discuss.

Tracking the evolution of style

Functionally-identical elements of buildings can change substantially over time; for example, the styles of windows, doors, balconies, etc. vary dramatically across different architectural periods. We try to automatically identify these evolutions by looking for "chains" of elements that are discriminative to a particular time period, but that are still coarsely similar in visual appearance to elements in neighboring periods. More concretely, given the set of deduplicated and ranked candidates Ĉ with period labels L generated as described in the previous section, we want to find a chain C 1 , . . . , C k of similar elements such that L Ci+1 = L Ci + 1. We cannot fix the length k of the chain or the beginning or ending periods (L C1 or L C k ) in advance, since elements may appear or disappear over time. This problem is reminiscent of multiple-target tracking [START_REF] Berclaz | Multiple object tracking using k-shortest paths optimization[END_REF], in which detections of an object from sequential frames of video are stitched together to form trajectories, except that we are "tracking" patches over sets of images from different time periods.

We define a directed acyclic graph G = {V, E} such that V = {s, t} ∪ Ĉ where s and t are special source and sink nodes. The graph forms a trellis, such that each patch in any given time period has an outgoing edge to every patch in the next period, while the source and sink connect to all nodes (in all time periods) of the graph. Figure 3 presents a sample graph with four periods and three patches per period. Intuitively, the inter-period connections provide possible evolutions of corresponding elements. The source and sink nodes are added to determine the start and end of a chain, with weights such that if many matches for a patch are from the future, it is likely to be a starting point; otherwise, it tends to be an ending point.

For the edge weights, we need a measure of visual similarity that will connect patches likely to correspond to the same functional elements (e.g. windows, balconies, etc.). We could use visual similarity in WHO space, except that the appearance of some functional elements varies rather dramatically across time. We thus instead use relationships between images and candidate patches, looking at the spatial consistency of detections between candidates as a measure of similarity. For example, even if a window from 1939 looks quite different from one from the 1800s, it will still likely find its closest detection on a window region instead of anywhere else on a facade.

In particular, for pairs of patches C i and C j with (C i , C j ) ∈ E, we compute the intersection-over-union between their top 200 detections, (D i,1 ...D i,200 ) and (D j,1 ...D j,200 ). We store this overlap value and the spatial offsets of the centers of overlapping pairs as θ and ∆, where θ ∈ R N and ∆ ∈ R N ×2 and N is the number of overlapping pairs. We also compute the component-wise trimmed mean ∆, discarding outliers outside the 0.1 and 0.9 quantiles. To capture the consistency of the overlaps, we take a mean deviation µ ∆ = 1 n ||∆ i -∆||, where higher values indicate less consistency, and compute an edge weight,

w ij = µ ∆ * e λ/ θ ,
where λ is a constant (5 in our experiments) controlling how steeply the cost rises for low confidence overlaps. The exponential term incorporates our level of confidence in µ ∆ based on the number and quality of the overlaps. Intuitively, two elements i and j that co-occur in the same images with a consistent spatial offset will have a low weight.

The source and sink nodes are attached to every other node with weights dependent on each candidate's closest detections. In particular, the weight from source to C i is defined as n < * β * f < where f < is the fraction of the top 200 detections for C i that are from periods before L Ci and n < is the number of periods before L Ci . The weights to the sink are defined similarly, considering periods and fractions of those periods past L Ci . Generally these weights will be low when a patch lacks many detections in earlier or later periods respectively. We set β empirically as a typical edge cost in a high quality chain, so that these weights balance the total cost of continuing the chain, amortized by how likely the chain should continue. To generate chains we greedily find the shortest path from source to sink, remove it, and repeat.

Results

We now evaluate our dataset construction and visual element discovery methodology on our large-scale dataset from Paris. Our goal of automatically producing informative architectural visualizations is inherently qualitative, so we evaluate it in several different ways. First we view the problem in terms of the discriminativeness of our patches. Then we look in detail at sample output and identify historical trends that our automatic methods have captured. Finally, we report on qualitative results based on the feedback of an expert on Parisian architecture, who used an interactive version of our analysis.

Period-wise Analysis

One way of evaluating our discriminative patches is to test their classification effectiveness, i.e. how well they discern visually similar elements from different periods. As discussed in Section 4, we score our candidate patches by taking the nearest 200 detections for each candidate as our collection of visually similar elements, and compute the area under a precision-recall curve for each patch. We show the top eight elements ranked by AUC for each period in Figure 4.

In Figure 5a we plot the mean AUC for the highest ranked k patches from each period, varying k between 1 and 200. Note that after about the 10th to 30th best patch, the mean AUC drops substantially for all periods. We take this to imply that periods are surprisingly well characterized by only about a dozen key elements. Also interesting is the relatively higher mean AUC for the two periods spanning 1801-1914. These periods include Haussmann's renovation of Paris (during which Emperor Napoléon III commissioned Georges-Eugène Haussmann to redesign much of the city center) and perhaps are more cohesive because of the heavy influence of a single person. Figure 5b shows the distribution of period labels for the 200 nearest detections for the top 200 patches in each period. As we would expect, much of the mass is around the diagonals, indicating that most confusion is with adjacent periods. Both Figures 5a and5b show that later periods are more challenging than earlier ones, perhaps because they are shorter and thus presumably more similar to neighboring periods.

Facade-level analysis. While these results suggest that we are discovering discriminative patches, one of our larger goals is to find patches that are relevant and useful to studies of architecture. This is difficult to quantify, so we showed our discovered patches to an expert on Parisian architecture and asked for feedback [START_REF] Ubelmann | [END_REF]. They informed us that many of the patches did capture key elements known to be prevalent in their respective periods, but that architects usually look at entire facades where many details combine to indicate the facade's period, as opposed to studying individual features.

Inspired by this observation, we used our ranked candidates to evaluate the 'periodness' of whole facades. For each facade, we found the top 100 detected patches. We sum the AUC of the detected patches for each period in a facade to produce an unnormalized distribution over how well each period's patches fit the given facade. In Figure 6 we show the highest likelihood facade for each period. Each image is accompanied by an over-painting of patch detections with colors corresponding to source period (using the same color coding as in Figure 5a) and a "reconstruction" of the image made by averaging these detections. For instance, notice how the 1851-1914 facade demonstrates the similarity in the periods spanning pre-1800 to 1914; its overpainting has colors corresponding to patch detections from pre-1800 (red) and 1801-1850 (orange) in addition to its own (yellow). The figure presents a sense of the progression in style and types of buildings constructed in Paris over the last two centuries, as modern materials gradually overtake old. The confusion about later periods is again seen here, with later periods exhibiting higher degrees of confusion (indicated by more mixture of color in the over-painting).

Fine-grained substructures. We also took a finer-grained perspective, looking for the most discriminative substructures within each patch. In particular, we drop each spatial cell of the WHO feature in sequence, by recomputing the patch's distances and AUC while ignoring that cell. This shows us which spatial cells are important, by observing drops in the AUC relative to the entire patch. We visualize this with a histogram of these differences where the i, j-th entry is the difference in AUC when the i, j-th spatial bin is masked. A sample of these visualizations is shown in Figure 7 along with some candidates and their nearest detections. The 1915-1939 period is characterized by new raw brick facades, highlighted in Figure 7a. Figures 7b and7c give importance to details not identified by our expert. In Figure 7b, the spacing between adjacent window shutters appears to be influential in discerning between periods. In

Style chains

Next we evaluated our technique for finding "chains" of similar functional elements whose appearance has evolved over time. Figure 8 shows sample chains of varying length and differing elements. Figures 8a and8i show increasingly ornate window dressings starting from very plain structures before 1800, to multiple decorative structures in the 1851-1914 period. Figure 8c shows the long window balconies of the 1850s to 1940s, while Figure 8d shows an evolution of short balconies. Many similar chains are produced as there is a great deal of variety in balcony shapes over time. Some chains show consistent directions of change, for instance Figure 8e demonstrates the increasing depth of windows. The last chain in Figure 8f highlights railings for large buildings after 1940, with the railings transitioning to glass in 1982-1989 and into metal in the 1990s.

Conclusion

We presented simple but effective methods to automatically discover and track visually important architectural elements using an automatically annotated collection of thousands of street-level images of Paris. The images are mapped to buildings in a fine-grain urban planning model that annotates each with a rough construction date. Using these combined data sources, we mine for period specific stylistics elements, analyze facade-level architectural influences, and find evolutions of elements across times. This work is one step towards a longer-term goal of developing automatic techniques to mine large-scale image collections in order to help experts in other disciplines discover important and meaningful visual patterns.

Figure 2 :

 2 Figure 2: Overview of data generation from Google Street View images and cadastre maps. We first (a) cast 30m rays to the sides of each Street View capture location at 1 • intervals, then (b) compute intersections with facades and select the widest view, and (c) project onto the panoramas and crop and warp the facade images according to Street View metadata.

Figure 3 :

 3 Figure 3: Sample chain graph. Elements in adjacent periods are fully connected with weights depending on their co-occurrence, while the source and sink connect to every node with weights that penalize the number of skipped periods. Here, the shortest path (in red) skips pre-1800 and 1915-1939 because they lack the long balconies of the other periods. (For clarity, this visualization shows only four periods (instead of ten), and only some source and sink edges.)

Figure 4 :

 4 Figure 4: Top 8 discriminative elements for each period. For each element, five example patches are shown in a row. Notice how as we move towards modern times the patches largely become repeated geometries.

Figure 5 :

 5 Figure 5: Evaluation of top 200 patches per period: (a) Mean AUC as a function of number of top candidates. (b) Distribution of labels in top detections for each period.

Figure 7 :

 7 Figure 7: Sample discriminative elements. Each figure shows a patch (top left), a fine-grained importance map (top right), close examples from the same (bottom left) and other (bottom right) time periods. Best viewed in color.

Figure 6 :

 6 Figure 6: Exemplars of each period according to facade level analysis. In each row we show the original facade (left), the original overpainted with the periods of the top 100 detections (middle), and a reconstructed version of the facade where the period patches are replaced by their average images (right). Note the progression of style and the types of building constructed over the 200 year span. (Best viewed in color.)

Figure 8 :

 8 Figure 8: Sample chains of architectural elements across time periods, showing how our technique can discover functionallysimilar elements whose visual appearance has evolved over time (see Section 5.2).

Acknowledgments. We are grateful to Yves Ubelmann for discussions and thoughtful comments. This research was supported in part by the National Science Foundation through CAREER grant IIS-1253549, by the Intelligence Advanced Research Projects Activity (IARPA) via Air Force Research Laboratory, contract FA8650-12-C-7212, and by the European Research Council (ERC grant LEAP no. 336845), Agence Nationale de la Recherche (Semapolis project, ANR-13-CORD-0003) and the Inria CityLab IPL. The U.S. Government is authorized to re-produce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, AFRL, NSF, or the U.S. Government.


Member, IEEE Akihiko Torii
email: torii@ctrl.titech.ac.jp

Member, IEEE Josef Sivic
email: josef.sivic@ens.fr

Member, IEEE Masatoshi Okutomi

Member, IEEE Tomas Pajdla
email: pajdla@cmp.felk.cvut.cz

Visual Place Recognition with Repetitive Structures

Keywords: Place Recognition, Bag of Visual Words, Geometric Verification, Image Retrieval. ✦

Repeated structures such as building facades, fences or road markings often represent a significant challenge for place recognition. Repeated structures are notoriously hard for establishing correspondences using multi-view geometry. They violate the feature independence assumed in the bag-of-visual-words representation which often leads to over-counting evidence and significant degradation of retrieval performance. In this work we show that repeated structures are not a nuisance but, when appropriately represented, they form an important distinguishing feature for many places. We describe a representation of repeated structures suitable for scalable retrieval and geometric verification. The retrieval is based on robust detection of repeated image structures and a suitable modification of weights in the bag-of-visual-word model. We also demonstrate that the explicit detection of repeated patterns is beneficial for robust visual word matching for geometric verification. Place recognition results are shown on datasets of street-level imagery from Pittsburgh and San Francisco demonstrating significant gains in recognition performance compared to the standard bag-of-visual-words baseline as well as the more recently proposed burstiness weighting and Fisher vector encoding.

Visual Place Recognition with Repetitive Structures

INTRODUCTION

G IVEN a query image of a particular street or a building, we seek to find one or more images in the geotagged database depicting the same place. The ability to visually recognize a place depicted in an image has a range of potential applications including automatic registration of images taken by a mobile phone for augmented reality applications [START_REF] Aguera Y Arcas | Augmented reality using Bing maps[END_REF] and accurate visual localization for robotics [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF]. Scalable place recognition methods [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF], [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF], [START_REF] Quack | World-scale mining of objects and events from community photo collections[END_REF], [START_REF] Schindler | City-scale location recognition[END_REF] often build on the efficient bag-of-visual-words representation developed for object and image retrieval [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], [START_REF] Jegou | On the burstiness of visual elements[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], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. In an offline pre-processing stage, local invariant descriptors are extracted from each image in the database and quantized into a pre-computed vocabulary of visual words. Each image is represented by a sparse (weighted) frequency vector of visual words, which can be stored in an efficient inverted file indexing structure. At query time, after the visual words are extracted from the query image, the retrieval proceeds in two steps. First a short-list of top ranked candidate images is obtained from the database using the bag-of-visual-words representation. Then, in the second verification stage, candidates are re-ranked based on the spatial layout of visual words.

A number of extensions of this basic architecture have been proposed. Examples include: (i) learning better visual vocabularies [START_REF] Mikulik | Learning a fine vocabulary[END_REF], [START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF]; (ii) developing quantization methods less prone to quantization errors [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], [START_REF] Van Gemert | Visual word ambiguity[END_REF]; (iii) combining returns from multiple query images depicting the same scene [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], [START_REF] Chum | Total recall II: Query expansion revisited[END_REF]; (iv) exploiting the 3D or graph structure of the database [START_REF] Irschara | From structurefrom-motion point clouds to fast location recognition[END_REF], [START_REF] Li | Location recognition using prioritized feature matching[END_REF], [START_REF] Philbin | Geometric latent dirichlet allocation on a matching graph for large-scale image datasets[END_REF], [START_REF] Torii | Visual localization by linear combination of image descriptors[END_REF], [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problem[END_REF], [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF]; or (v) indexing on spatial relations between visual words [START_REF] Chum | Geometric min-hashing: Finding a (thick) needle in a haystack[END_REF], [START_REF] Jegou | Hamming embedding and weak geometric consistency for large-scale image search[END_REF], [START_REF] Zhang | Image retrieval with geometrypreserving visual phrases[END_REF].

In this work we develop a scalable representation for large-scale matching of repeated structures. While repeated structures often occur in man-made environments -examples include building facades, fences, or road markings -they are usually treated as nuisance and down-weighted at the indexing stage [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF], [START_REF] Jegou | On the burstiness of visual elements[END_REF], [START_REF] Schaffalitzky | Automated location matching in movies[END_REF], [START_REF] Schmid | Local greyvalue invariants for image retrieval[END_REF]. In contrast, we develop a simple but efficient representation of repeated structures and demonstrate its benefits for place recognition in urban environments. In detail, we first robustly detect repeated structures in images by finding spatially localized groups of visual words with similar appearance. Next, we modify the weights of the detected repeated visual words in the bag-of-visualword model, where multiple occurrences of repeated elements in the same image provide a natural softassignment of features to visual words. In addition, the contribution of repetitive structures is controlled to prevent dominating the matching scores. This is illustrated in Figure 1. Finally, we develop a geometric verification method that takes into account the detected repetitions and suppresses ambiguous tentative correspondences between repeated image patterns.

The paper is organized as follows. After describing related work on finding and matching repeated structures (Section 1.1), we review in detail (Section 2) the common tf-idf visual word weighting scheme and its extensions to soft-assignment [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] and repeated structure suppression [START_REF] Jegou | On the burstiness of visual elements[END_REF]. In Section 3, we describe our method for detecting repeated visual words in images. In Section 4, we describe the proposed model for scalable matching of repeated structures, and in Section 5, we detail the proposed geometric matching that takes into account the detected repetitions. Experiments demonstrating the benefits of the developed representations are given in Section 6.

Related work

Detecting repeated patterns in images is a well-studied problem. Repetitions are often detected based on an assumption of a single pattern repeated on a 2D (deformed) lattice [START_REF] Hays | Discovering texture regularity as a higher-order correspondence problem[END_REF], [START_REF] Leung | Detecting, localizing and grouping repeated scene elements from an image[END_REF], [START_REF] Park | Deformed lattice detection in real-world images using mean-shift belief propagation[END_REF]. Special attention has been paid to detecting planar patterns [START_REF] Schaffalitzky | Geometric grouping of repeated elements within images[END_REF], [START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF], [START_REF] Pritts | Detection, rectification and segmentation of coplanar repeated patterns[END_REF] and in particular building facades [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], [START_REF] Hauagge | Image matching using local symmetry features[END_REF], [START_REF] Wu | Detecting large repetitive structures with salient boundaries[END_REF], for which highly specialized grammar models, learnt from labelled data, were developed [START_REF] Muller | Image-based procedural modeling of facades[END_REF], [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF].

Detecting planar repeated patterns can be useful for single view facade rectification [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF] or even single-view 3D reconstruction [START_REF] Wu | Repetition-based dense single-view reconstruction[END_REF]. However, the local ambiguity of repeated patterns often presents a significant challenge for geometric image matching [START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF], [START_REF] Sattler | SCRAMSAC: Improving RANSAC's efficiency with a spatial consistency filter[END_REF] and image retrieval [START_REF] Jegou | On the burstiness of visual elements[END_REF].

Schindler et al. [START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF] detect repeated patterns on building facades and then use the rectified repetition elements together with the spatial layout of the repetition grid to estimate the camera pose of a query image, given a database of building facades. Results are reported on a dataset of 5 query images and 9 building facades. In a similar spirit, Doubek et al. [START_REF] Doubek | Image matching and retrieval by repetitive patterns[END_REF] detect the repeated patterns in each image and represent the pattern using a single shift-invariant descriptor of the repeated element together with a simple descriptor of the 2D spatial layout. Their matching method is not scalable as they have to exhaustively compare repeated patterns in all images. In scalable image retrieval, Jegou et al [START_REF] Jegou | On the burstiness of visual elements[END_REF] observe that repeated structures violate the feature independence assumption in the bag-of-visual-word model and test several schemes for down-weighting the influence of repeated patterns.

This paper is an extended version of [START_REF] Torii | Visual place recognition with repetitive structures[END_REF] with detailed description of the proposed algorithms, new geometric verification method that takes into account the detected repetitive structures (Section 5), and additional experiments.

REVIEW OF VISUAL WORD WEIGHTING

STRATEGIES

In this section we first review the basic tf-idf weighting scheme proposed in text retrieval [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] and also commonly used for the bag-of-visual-words retrieval and place recognition [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF], [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], [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], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Jegou | Hamming embedding and weak geometric consistency for large-scale image search[END_REF]. Then, we discuss the soft-assignment weighting [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] to reduce quantization errors and the "burstiness" model proposed by Jegou et al. [START_REF] Jegou | On the burstiness of visual elements[END_REF], which explicitly downweights repeated visual words in an image.

Term frequency-inverse document frequency weighting

The standard "term frequency-inverse document frequency" (tf-idf) weighting [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF], is computed as follows. Suppose there is a vocabulary of M visual words, then each image is represented by a vector

y d = (y 1 , ..., y t , ..., y M ) ⊤ (1)
of weighted visual word frequencies with components

y t = n td n d log N N t , (2)
where n td is the number of occurrences of visual word t in image d, n d is the total number of visual words in the image d, N t is the number of images containing term t, and N is the number of images in the whole database. The weighting is a product of two terms: the visual word frequency, n td /n d , and the inverse document (image) frequency, log (N/N t ). The word frequency weights words occurring more often in a particular image higher (compared to visual word present/absent), whilst the inverse document frequency down-weights visual words that appear often in the database, and therefore do not help to discriminate between different images. The generalization of the idf weighting has been recently proposed by Zheng et al [START_REF] Zheng | Lp-norm idf for large scale image search[END_REF]. At the retrieval stage, images are ranked by the normalized scalar product (cosine of angle)

score d = y q ⊤ y d y q 2 y d 2 (3)
between the query vector y q and all image vectors y d in the database, where y 2 = y ⊤ y is the L 2 norm of y.

The scalar product in Equation ( 3) can be implemented efficiently using inverted file indexing schemes.

Soft-assignment weighting

Visual words generated through descriptor clustering often suffer from quantization errors, where local feature descriptors that should be matched but lie close to the Voronoi boundary are incorrectly assigned to different visual words. To overcome this issue, Philbin et al. [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] soft-assign each descriptor to several (typically 3) closest cluster centers with weights set according to exp -d 2 2σ 2 , where d is the Euclidean distance of the descriptor from the cluster center and σ is a parameter of the method.

Burstiness weighting

Jegou et al. [START_REF] Jegou | On the burstiness of visual elements[END_REF] studied the effect of visual "burstiness", i.e. that a visual-word is much more likely to appear in an image, if it has appeared in the image already. Burstiness has been also studied for words in text [START_REF] Katz | Distribution of content words and phrases in text and language modelling[END_REF]. Jegou et al. observe by counting visual word occurrences in a large corpus of 1M images that visual words occurring multiple times in an image (e.g. on repeated structures) violate the assumption that visual word occurrences in an image are independent. Further, they observe that the bursted visual words can negatively affect retrieval results. The intuition is that the contribution of visual words with a high number of occurrences towards the scalar product in Equation ( 3) is too high. In the voting interpretation of the bag-of-visual-words model [START_REF] Jegou | Hamming embedding and weak geometric consistency for large-scale image search[END_REF], bursted visual words vote multiple times for the same image. To see this, consider an example where a particular visual word occurs twice in a query and five times in a database image. Ignoring the normalization of the visual word vectors for simplicity, multiplying the number of occurrences as in (3) would result in 10 votes, whereas in practice only up to two matches (correspondences) can exist.

To address this problem Jegou et al. proposed to down-weight the contribution of visual words occurring multiple times in an image, which is referred to as intra-image burstiness. They experimented with different weighting strategies and empirically observed that down-weighting repeated visual words by multiplying the term frequency in Equation ( 2) by factor 1 √ n td , where n td is the number of occurrences, performed best. Similar strategies to discount repeated structures when matching images were also used in [START_REF] Schaffalitzky | Automated location matching in movies[END_REF], [START_REF] Schmid | Local greyvalue invariants for image retrieval[END_REF].

Note that Jegou et al. also considered a more precise description of local invariant regions quantized into visual words using an additional binary signature (Hamming embedding) [START_REF] Jegou | Hamming embedding and weak geometric consistency for large-scale image search[END_REF] more precisely localizing the descriptor in the visual word Voronoi cell. The Hamming embedding is complementary to the method developed in this paper.

Contrary to down-weighting repeated structures based on globally counting feature repetitions across the entire image, we (i) explicitly detect localized image areas with repetitive structures, and (ii) use the detected local repetitions to adaptively adjust the visual word weights in the soft-assigned bag-of-visual words model. The two steps are described next.

DETECTION OF REPETITIVE STRUCTURES

The goal is to segment local invariant features detected in an image into localized groups of repetitive patterns and a layer of non-repeated features (see Figure 2). Examples include detecting repeated patterns of windows on different building facades, fences, road markings or trees in an image (see Figure 3). We will operate directly on the extracted local features (rather than using specially designed features [START_REF] Hauagge | Image matching using local symmetry features[END_REF]) as the detected groups will be used to adjust feature weights in the bag-ofvisual-words model for efficient indexing. The feature segmentation problem is posed as finding connected components in a graph.

In detail, we build an (undirected) feature graph G = (F , E) with N vertices F = {f i } N i=1 consisting of local invariant features at locations x i , scales s i and with corresponding SIFT descriptors d i . Each SIFT descriptor is further assigned to the K nearest visual words

W K i = {w k i } K
k=1 in a pre-computed visual vocabulary (see Section 6 for details). Two vertices (features) f i and f j are connected by an edge if they have close-by image positions as well as similar scale and appearance. More formally, a pair of vertices f i and f j is connected by an edge if the following three conditions are satisfied:

1) The spatial L 2 distance x ix j 2 between features satisfies x i -x j 2 < γ (s i +s j ) where γ is a constant (we set γ = 10 throughout all our experiments); 2) The ratio σ of scales of the two features is in 0.5 < σ < 2; 3) The features share at least one common visual word in their top K visual word assignments, where K is typically 50. Note that this condition avoids directly thresholding the distance between the SIFT descriptors of the two features, which we found unreliable. Having built the graph, we group the vertices (image features) into disjoint groups by finding connected components of the graph [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF]. These connected components group together features that are spatially close, and are also similar in appearance as well as in scale. In For descriptor d i find the K nearest visual words

W K i = {w k i } K k=1 from vocabulary C. 4: for i = 1, . . . , N do 5:
For feature f i retrieve matching features f j s.t. j ∈ J :

W K i ∩ W K j = ∅.
6:

for j ∈ J do 7: if e ij = FALSE then 8: if 0.5 < s i /s j < 2 then 9: if x i -x j < γ (s i + s j ) then 10:
e ij = e ji := TRUE. % Create edge.

the following, we will call the detected feature groups "repttiles" for "tiles (regions) of repetitive features". The repttile detection is summarized in Algorithm 1. only weak assumptions on the type and spatial structure of repetitions, not requiring or attempting to detect, for example, feature symmetry or an underlying spatial lattice.

REPRESENTING REPETITIVE STRUCTURES FOR SCALABLE RETRIEVAL

In this section we describe our image representation for efficient indexing taking into account the repetitive patterns. The proposed representation is built on two ideas. First, we aim at representing the presence of a repetition, rather than measuring the actual number of matching repeated elements. Second, we note that different occurrences of the same visual element (such as a facade window) are often quantized to different visual words because of the noise in the description and quantization process as well as other non-modeled effects such as complex illumination (shadows) or perspective deformation. We take the advantage of this fact and design a descriptor quantization procedure that adaptively softassigns local features with more repetitions in the image to fewer nearest cluster centers. The intuition is that the multiple examples of a repeated feature provide a natural and accurate soft-assignment to multiple visual words.

Formally, an image is represented by a bag-of-visualwords vector

z d = (z 1 , ..., z t , ..., z M ) ⊤ (4)
where the t-th visual word weight

z t = r t if 0 ≤ r t < T T if T ≤ r t (5)
is obtained by thresholding weights r t by a threshold T . Note that the weighting described in Equation ( 5) is similar to burstiness weighting, which down-weights repeating visual words. Here, however, we represent highly weighted (repeating) visual words with a constant T as the goal is to represent the occurrence (presence/absence) of the visual word, rather than measuring the actual number of occurrences (matches). Weight r t of the t-th visual word in image d is obtained by aggregating weights from adaptively soft-assigned features across the image taking into account the repeated image patterns. In particular, each feature f i ∈ F d detected in image d is assigned to the α i nearest (in the feature space) visual words W αi i = {w k i } αi k=1 . Thus, w k i , for 1 ≤ k ≤ α i , is the index of the k-th nearest visual word of f i . The number α i , which varies between 1 and α max , will be defined below. Weight r t is computed as

r t = N i=1 αi k=1 1[w k i = t] 1 2 k-1 (6)
where the indicator function

1[w k i = t] is equal to 1 if visual word t is present at the k-th position in W αi
i . This means that weight r t is obtained as the sum of contributions from all assignments of visual word t over all features in F d . The contribution of an individual assignment depends on the order k of the assignment in W αi i by the weight 1/(2 k-1 ). The number α i is computed by the following formula

α i = α max log( n d +1 mi ) max i∈F d log( n d +1 mi ) (7)
where α max is the maximum number (upper bound) of assignments (α max = 3 in all our experiments), m i is the number of features in the repttile of which f i belongs, and n d is the total number of features in the image d.

We use ⌈x⌉ = ceiling(x), i.e. ⌈x⌉ is the smallest integer greater than or equal to x. This adaptive soft-assignment is summarized in Algorithm 2. Note that image features belonging to relatively larger repttiles are soft-assigned Algorithm 2 BoVW weighting with adaptive assignment Input W K i : K-nearest visual words for each feature i in F . Output r t : Weights of the bag-of-visual-word vector.

1: Initialize r t := 0 for t = 1, . . . , M . 2: for i = 1, . . . , N do 3:

Compute number of assignments α i by Eq. ( 7). r p := r p + 1/2 k-1 .

7: Apply thresholding in Eq. 5 to r t for t = 1, . . . , M .

to fewer visual words as image repetitions provide a natural soft-assignment of the particular repeating scene element to multiple visual words (see Figures 4 and5). This adaptive soft-assignment is more precise and less ambiguous than the standard soft-assignment to multiple nearest visual words [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] as will be demonstrated in Section 6.

GEOMETRIC VERIFICATION WITH REPTTILE DETECTION

In this section we describe our geometric verification method that takes advantage of the detected repeated patterns. Similarly to the standard image retrieval, the place recognition accuracy can be significantly improved by re-ranking retrieved images based on geometric consistency of local features [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. The retrieved images in the initial shortlist are typically re-ranked using the number of inliers that are consistent with the 2D affine geometric transformation, homography, or the epipolar constraint.

The geometric verification has two steps: (i) generating tentative matches based on local feature appearance, and (ii) finding subsets of matches consistent with the geometric transformation. The tentative matches are typically found by matching raw (SIFT) feature descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] or via visual word matching [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]. For large scale matching problems, visual word matching is preferred due to its memory efficiency as we can store only 4 bytes for an unsigned-int32 visual word ID instead of 128 bytes for an unsigned-int8 SIFT descriptor. However, as reported in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], [START_REF] Chum | Scalable near identical image and shot detection[END_REF], visual word matching usually results in some drop in matching accuracy due to quantization effects. In addition, when using visual words it is not straightforward to find the most distinctive matches as can be done with raw descriptors using Lowe's first to second nearest neighbor ratio test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. We develop a method for generating tentative matches for geometric verification that addresses both these issues.

First, to overcome the quantization effects we assign descriptors to multiple visual words (multiple assignment). This is similar to [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] but to minimize false matches we take advantage of the detected repeated patterns and only compute tentative matches from the The number of visual word assignments of each feature is adaptively defined by the number of features in the repttile as in Equation [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]. The color indicates the number of multiple assignments, red = 1, green = 2 and blue= 3. Features belonging to larger repttiles are assigned to fewer visual words (red) but discriminative features (blue and green) are assigned to multiple visual words (up to 3). distinct visual words with the limited amount of repetitions in the image. This is implemented by removing features from the largest repttiles (those where α i = 1, see Section 4). The remaining features are assigned to multiple (K) nearest visual words, where K is typically 50. The multiple assignment is performed only on the query side, and therefore, it is not necessary to store K visual words for all database images as in [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. Note that no additional computations are required as the K nearest visual words are already computed during the repttile detection (Section 3). The results in Section 6 demonstrate that it is beneficial to remove the heavily repeated features during geometric verification as they are highly ambiguous for the task of establishing feature to feature correspondences. The visual word matching with repttile removal and multiple assignments is summarized in Algorithm 3.

Second, we develop a variant of Lowe's first to second nearest neighbor ratio test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] for visual word matching Algorithm 3 Visual word matching with repttile removal and multiple assignments Input W K iq : Visual words of F q in query image I q . α iq : Numbers of adaptive assignments for F q . W 1 id : Visual words of F d in image I d . α id : Numbers of adaptive assignments for F d . Output m i : Indices of matches to the query features.

1: Initialize m i := ∅ for i = 1, . . . , N q . 2: Remove f id ∈ F d if α id = 1.
%Remove large repttiles in I d .

3: for i = 1, . . . , N q do 4:

if α iq > 1 then %Use only small repttiles in Iq.

k := k + 1 8:
Seek a set J where {j ∈ J | w k iq ∩ w 1 jd = ∅}.

%Find visual word match. 9:

if J / ∈ ∅ then 10:

Pick an index j ∈ J randomly.

11:

m i := j 12:
break when the raw (SIFT) descriptors for the images in the database are not available. The main idea of the original ratio test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] is to compute, for each query image descriptor d iq , the ratio

L = d iq -d N N1 2 d iq -d N N2 2 , (8)
where d N N1 is the first nearest neighbor and d N N2 is the second nearest neighbor of the query descriptor d iq in the candidate database image. The ratio L lies between 0 and 1. The ratio is close to 1 if the query feature d iq is non-distinctive. While this test works extremely well in practice, it requires storing (or re-computing) local feature descriptors for both the query image and all database images, which, as argued above, is prohibitive for large databases.

To address this issue, we develop an asymmetric version of the ratio test, which is inspired by the asymmetric distance computation in product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], and which only requires knowing the local feature descriptors for the query image. The local feature descriptors in the database images are represented by their quantized representation, i.e. the centroids of their closest visual words. In detail, we replace each feature descriptor d id in database image d by its quantized descriptor corresponding to the centroid of its closest visual word c t ∈ C. The approximate ratio is then computed as

L a = d iq -c N C1 2 d iq -c N C2 2 , (9)
where d iq is the descriptor of the local feature in the query image, c N C1 is its closest (quantized) descriptor in the database image and c N C2 is its second closest (quantized) descriptor in the database image. L a also lies between 0 and 1 and is close to 1 if the descriptor match is ambiguous. The intuition is that N C 1 and N C 2 are approximations of the first and second nearest neighbors N N 1 and N N 2 in the original ratio test given by Equation [START_REF] Jegou | On the burstiness of visual elements[END_REF]. Note that the asymmetric ratio ( 9) can be computed efficiently as the distances d iqc N C 2 between the query descriptor and multiple (up to 50) closest cluster centers are pre-computed during the assignment of query descriptors to visual words. In addition, N C 1 and N C 2 can be efficiently found by only accessing the inverted file list.

Results demonstrating benefits of both tentative matching with reptile detection and the asymmetric ratio test are shown in Section 6.

EXPERIMENTS

In this section we describe the experimental validation of our approach. First, we describe the experimental set-up (Section 6.1), describe the evaluation metric (Section 6.2) and give the implementation details (Section 6.3). Next, we evaluate place recognition performance of the proposed representation with repttile detection and adaptive soft-assignment and compare it with the state-of-theart BoVW baseline methods (Section 6.4). Then we evaluate the sensitivity to the different method parameters (Section 6.5) and compare performance with compact image descriptors (Section 6.6). Finally, we experimentally evaluate the proposed geometric verification method (Section 6.7).

Datasets

We perform experiments on the following two geotagged image databases.

Pittsburgh dataset

The Pittsburgh dataset is formed by 254, 064 perspective images generated from 10, 586 Google Street View panoramas of the Pittsburgh area downloaded from the the Internet. From each panorama of 6, 656 × 3, 328 pixels, we generate 24 perspective images of 640 × 480 pixels (corresponding to 60 degrees of horizontal FoV) with two pitch directions [4 • , 26.5 • ] and 12 yaw [0 • , 30 • , ..., 360 • ] directions. This is a similar setup to [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF]. As testing query images, we use 24, 000 perspective images generated from 1, 000 panoramas randomly selected from 8, 999 panoramas of the Google Pittsburgh Research Data Set 1 . The datasets are visualized on a map in Figure 6(a). This is a very challenging place recognition set-up as the query images were captured in a different session than the database images and depict the same places from different viewpoints, under very different illumination conditions and, in some cases, in different seasons. Note also the high number of test query images compared to other existing datasets [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF].

1. Provided and copyrighted by Google. The ground truth is derived from the (known) GPS positions of the query images. We have observed that GPS positions of Street View panoramas are often snapped to the middle of the street. The accuracy of the GPS positions hence seems to be somewhere between 7 and 15 meters.

San Francisco visual place recognition benchmark

This dataset consists of the geotagged images formed by 1, 062, 468 perspective central images (PCIs), 638, 090 perspective frontal images (PFIs), and 803 cell phone images. We use the PCIs as the geotagged image database and the cell phone images as testing query images. The dataset is visualized on a map in Figure 7(a). This dataset involves challenges similar to the Pittsburgh dataset. Some query images undergo more severe viewpoint changes than those in the Pittsburgh dataset because the cell phone query images are captured on the street-side whereas the PCI database images are captured from the middle of street.

Each image in this dataset has labels of visible buildings computed using 3D building models [START_REF] Pylvanainen | Automatic alignment and multi-view segmentation of street view data using 3d shape prior[END_REF]. The ground truth is given by matching the building IDs between query and database images 2 .

Evaluation metric

Similarly to [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF], [START_REF] Sattler | Image retrieval for image-based localization revisited[END_REF], we measure the place recognition performance by the fraction of correctly recognized queries. Following [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF], we denote the fraction of correctly recognized queries as "recall" 3 . We measure performance by recall on both datasets. However, the definition of a correctly recognized query is different between the two datasets due to different type of available ground truth annotations. For the Pittsburgh dataset, a query is deemed correctly recognized if at least one of the top N retrieved database images is within m meters from the ground truth position of the query. For the San Francisco dataset, the query is deemed 2. We note that 60 query images do not have the corresponding ground truth building label in the dataset.

3. While this terminology is slightly different from image retrieval, it meets the definition of recall, i.e. it measures the fraction of true positives (correctly recognized queries) over all positives (all query images). correctly recognized if at least one of the top N retrieved database images has the ground truth building ID match with the query. We evaluate the fraction of correctly recognized queries (recall) for the different lengths N of the candidate shortlist.

Implementation details

We build a visual vocabulary of 200,000 visual words by approximate k-means clustering [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF]. We have not observed any significant improvements by using larger vocabularies. The vocabulary is built from features detected in a subset of 100, 000 randomly selected database images in each dataset. We use the upright SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF] for each feature (assuming the upright image gravity vector) followed by the RootSIFT normalization [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF], i.e. L1 normalization and square root weighting. We have not used the histogram equalization suggested by [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF] as it did not improve results using our visual word setup.

Comparison with BoVW baselines

We compare results of the proposed adaptive softassignment approach (AA thr-idf) with several baselines: the standard tf-idf weighting (tf-idf) [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], burstiness weights (brst-idf) [START_REF] Jegou | On the burstiness of visual elements[END_REF], and the standard soft-assignment weights [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] (SA tf-idf). Results for the two datasets are summarized below.

• Pittsburgh. Results for different methods for m = 25 meters and varying value of N are shown in Figure 6 (b). Figure 8 shows examples of place recognition results. Notice that the top ranked results by the baseline burstiness method [START_REF] Jegou | On the burstiness of visual elements[END_REF] still suffer from repetitive structures that dominate visual word matching (Figure 8 (top row)). However, the proposed repttile detection and adaptive soft-assignment effectively down-weight repetitive structures, while mitigating "quantization effects" for the distinctive features (Figure 8 (bottom row)). • San Francisco. Results for the different methods are shown in Figure 7. The results of [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF] were obtained directly from the authors but to remove the effect of geometric verification we ignored the threshold on the minimum number of inliers by setting T P CI = 0. Note also that the GPS position of the query image was not used for any of the compared methods. The pattern of results is similar to the Pittsburgh data with our adaptive soft-assignment method (AA thridf) performing best and significantly better than the method of [START_REF] Chen | City-scale landmark identification on mobile devices[END_REF] underlying the importance of handling repetitive structures for place recognition in urban environments. Example place recognition results demonstrating benefits of the proposed approach are shown in Figure 9.

Sensitivity to parameters

Here we list the main parameters of our method and evaluate its sensitivity to their settings.

• The weight threshold T . The weight threshold T in Equation ( 5) is an important parameter of the method and its setting may depend on the dataset and the size of the visual vocabulary. Since 97% of visual word weights r t (see Equation ( 6)) are ≤ 1 (measured on the Pittsburgh database), setting T = 1 effectively down-weights the bursted visual words. Figures 10(a • The maximum repttile soft-assignment α max . We have also tested different values of the adaptive soft-assignment parameter α max (Equations ( 6) and ( 7)). Figures 10(b) and 11(b) again show the method is fairly insensitive to its choice, where values of 2 (AA thr-idf (amax=2)), 3 (AA thr-idf (K = 50)), and 5 (AA thr-idf (amax=5)) result in a similar performance. We use α max = 3 following [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] (unless stated otherwise). Note that the base of the exponential in Equation ( 6) is chosen so that the weights decrease with increasing k and we found 1/2 to work well. In general, this value needs to be set experimentally, similarly to the sigma parameter in the standard soft-assignment [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. • Which stage helps. Here, we evaluate separately the benefits of the two components of the proposed method (weight thresholding and adaptive softassignment) compared to the baseline burstiness weights. Figures 10(c) and 11(c) show separately results for (i) thresholding using Equation ( 5) (thridf) and (ii) adaptive soft-assignment using Equations ( 6) and ( 7) (AA brst-idf). Combining the two components results in a further improvement (AA thr-idf).

Comparison with compact descriptors

We compare results of the proposed adaptive softassignment approach with Vector of Locally Aggregated Descriptors (VLAD) and Fisher Vector (FV) matching [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF]. Following [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], we construct VLAD and FV from RootSIFT descriptors reduced to 64 dimensions by PCA. The 512 centroids for VLAD and the 512 Gaussian mixture components for FV were trained on the same training images, which were used for the BoVW methods. As in [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], resulting 512 × 64 dimensional descriptors are then reduced to 512 (VLAD 512, FV 512) or 4, 096 (VLAD 4096, FV 4096) dimensions using PCA.

The similarity between a query and database images is measured by the normalized scalar product. Figures 6(c) and 7(c) show the place recognition performance of our method compared to VLAD and FV.

Our adaptive soft-assignment can be indexed using standard inverted files and in terms of memory requirements compares favorably to the standard softassignment and Fisher vector representations. For the database of BoVW vectors, we count the memory complexity as 8 bytes per visual word entry (4 bytes for the index and 4 bytes for the weight). For the FV, we count 4 bytes (single precision) per dimension. Tables 1 and2 show that the proposed BoVW representation (AA thr-idf) has a smaller memory footprint than softassignment [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] (SA tf-idf) and FV 4, 096 while achieving better place recognition performance. The memory complexity vs. recognition accuracy (recall) are plotted for the two datasets in Figure 12. For a given memory complexity, the proposed method (AA thr-idf) clearly outperforms the FV matching. The memory footprint of the database (x-axis) vs. the fraction of correctly recognized queries (Recall, y-axis) at the top 1 rank by the proposed method (AA thridf, orange dot), the baseline burstiness weighting (brstidf, blue dot), and the Fisher vector representations (FV, black dots). The numbers beside the black dots indicate the dimension of each Fisher vector (reduced by PCA).

We note that the memory requirements can be further reduced for both our adaptive soft-assignment and the Fisher vector representations. Our adaptive weights (Equations ( 5) and ( 6)) can be mapped to a small set of integers when a small α max is used (α max = 3 in all our experiments). This reduces the memory requirements for storing our adaptive weights by a factor of 8. In addition, the inverted files can be compressed (without a loss of performance) which further reduces the required memory, typically by a factor of 4 [START_REF] Jegou | Packing bag-of-features[END_REF]. When combined, the required memory for our adaptive soft-assignment can be reduced by a factor of 32 with no loss in place recognition performance. For Fisher vectors, searching with product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] in a standard setting (m = 16, k ′ = 1, 024) typically reduces the memory requirements by a factor of 50 with a marginal loss in recognition performance. However, by inspecting Figures 12(a) and (b) we note that the Fisher vector performance consistently saturates for high dimensions. As a result, we do not expect the difference in the typical compression factors (32 for our method vs. 50 for FV) to affect the observed pattern of results.

Re-ranking by geometric verification

Here we evaluate the benefits of geometric verification. We re-rank the initial shortlist of top 50 images by the number of verified matches (inliers). We compare results of the proposed geometric verification method (Section 5) with standard baselines: the nearest neighbor matching using the raw descriptors with Lowe's ratio test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] (threshold= 0.9) and visual word matching [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

We evaluate separately the different components of the proposed method for obtaining tentative matches: (i) visual word matching with multiple assignments to different visual words (multi-assign), (ii) asymmetric ratio test (ratio test) (threshold= 0.9) and (iii) removing highly repetitive features (repttile removal). For the geometric verification of the input tentative matches, we use the LO-RANSAC [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], [START_REF] Chum | Enhancing RANSAC by generalized model optimization[END_REF]. We also tested the standard RANSAC [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] and PROSAC [START_REF] Chum | Matching with PROSAC -progressive sample consensus[END_REF] but observed no significant difference in performance. Tables 3 and4 show the percentage of correctly recognized queries (Recall) after geometric verification, the average number of tentative matches, and the average time to perform geometric verification for all the top 50 candidate images in the shortlist. The last column indicates the total memory footprint required to store the descriptors and other feature information to perform the geometric verification. We report recall at top 1 and top 3 as only the very top retrieved images are important for practical place recognition applications. On both datasets, the proposed visual word matching with multiple assignment combined with repttile removal and asymetric ratio test (last row in the table) significantly improves the recall compared to the standard visual word matching [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] while keeping similar memory footprint and slightly higher but still reasonable (under 1.5s) computation time.

Note that the reported computation time includes only the time to perform geometric verification using LO-RANSAC not the time to obtain the tentative matches. This explains the low reported timings for raw descriptor matching. In practice, raw descriptor matching is dominated by computing the tentative correspondences. In contrast, virtually no additional computations are required for visual word matching. Also note that the asymmetric ratio test does not always increase recall compared to repttile removal but further reduces the number of tentative matches and computation time.

Inspecting the memory footprint in more detail, we note that visual word matching [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] requires only the coordinates of keypoints, 4 bytes (single precision) × 2 (dimension), which amounts to 1.52 GB on the Pittsburgh and 5.36 GB on the San Francisco datasets, respectively. The raw descriptor matching in addition requires storing the raw SIFT descriptors (128 × 1 byte for each feature) that amounts, in total, to 24.43 GB and 85.76 GB for the two datasets, respectively. In comparison, the proposed multiple visual word matching with repttile removal requires only storing the repttile labels α i (Equation ( 7), 1 byte for each feature) that amounts only to additional 0.19 GB and 0.67 GB compared to the standard visual word matching [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Examples of place recognition results demonstrating the benefits of the proposed re-ranking method are shown in Figures 13 and14. The proposed method is more successful than the standard visual word matching because it generates more tentative matches on distinctive features while suppressing ambiguous matches on repetitive structures.

Evaluation on standard image retrieval datasets

We have also evaluated the proposed method for retrieval on the standard INRIA Holidays [START_REF] Jegou | On the burstiness of visual elements[END_REF] and Oxford Buildings datasets [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], where performance is measured by the mean Average Precision (mAP). Here we consistently use 200, 000 visual vocabulary built from Root-SIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] features and T = 5 (different choices of T had small effect on the result). Results are summarized in Table 5 and demonstrate the benefits of the proposed Here we use 200K visual vocabulary built from RootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] features and T = 5 (different choices of T had small effect on the result).

tf-idf [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] brst-idf [START_REF] Jegou | On the burstiness of visual elements[END_REF] SA tf-idf [ approach over the standard BoVW baseline methods.

However, the improvements by our method are less pronounced on this data. We believe this is because these datasets contain fewer repetitive structures than the place recognition imagery from urban areas (San Francisco, Pittsburgh) that is the main focus of this work.

CONCLUSION

In this work we have demonstrated that repeated structures in images are not a nuisance but can form a distinguishing feature for many places. We treat repeated visual words as significant visual events, which can be detected and matched. This is achieved by robustly detecting repeated patterns of visual words in images, and adjusting their weights in the bag-of-visual-word representation. Multiple occurrences of repeated elements are used to provide a natural soft-assignment of features to visual words. The contribution of repetitive structures is controlled to prevent dominating the matching score. We have shown that the proposed representation achieves consistent improvements in place recognition performance in urban environments. In addition, the proposed method is simple and can be easily incorporated into existing large scale place recognition architectures. The open source implementation of the proposed method is available at [60].

Fig. 1 .

 1 Fig. 1. Overview of visual place recognition with repetitive structures. Left: We detect groups of repeated local features (overlaid in colors). Middle: Repetitive features (shown in red) implicitly provide soft-assignment to multiple visual words (here A and C). Right: Truncating large weights (shown in red) in the bag-of-visual-word vectors prevents repetitions from dominating the matching score.

Fig. 2 .Algorithm 1

 21 Fig. 2. Examples of detected repetitive patterns of local invariant features ("repttiles"). The different repetitive patterns detected in each image are shown in different colors. The detection is robust against local deformation of the repeated element and makes only weak assumptions on the spatial structure of the repetition.

Figures 2 and 3

 3 show a variety of examples of detected patterns of repeated features. Only connected components with more than 20 image features are shown as colored dots. Note that the proposed method makes

Fig. 3 .

 3 Fig. 3. Examples of detected repetitive patterns of local invariant features ("repttiles") in images from the INRIA Holidays dataset [8]. The different repetitive patterns detected in each image are shown in different colors. The color indicates the number of features in each group (red indicates large and blue indicates small groups). Note the variety of detected repetitive structures such as different building facades, trees, indoor objects, window tiles or floor patterns.

4 :

 4 for k = 1, . . . , α i do 5:p := w k i ∈ W K i .%Retrieve the k-th visual word.6:

Fig. 4 .

 4 Fig. 4. Examples of adaptive soft-assignment with "repttile" detection in images from the Pittsburgh dataset. (Top) The repttiles composed from more than 20 image features are shown in different colors (red indicates large and blue indicates small groups, similarly to Figure 3). (Bottom)The number of visual word assignments of each feature is adaptively defined by the number of features in the repttile as in Equation (7). The color indicates the number of multiple assignments, red = 1, green = 2 and blue= 3. Features belonging to larger repttiles are assigned to fewer visual words (red) but discriminative features (blue and green) are assigned to multiple visual words (up to 3).

Fig. 5 .

 5 Fig. 5. Examples of adaptive soft-assignment with "repttile" detection in images from the San Francisco dataset. See the caption of Figure 4 for details.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Evaluation on the Pittsburgh dataset. (a) Locations of query (blue dots) and database (gray dots) images. (b-c) The fraction of correctly recognized queries (Recall, y-axis) vs. the number of top N retrieved database images (x-axis) for the proposed method (AA thr-idf) compared to several other methods.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Examples of place recognition results on the Pittsburgh dataset. Each figure shows the query image (left column) and the three best matching database images (2nd to 4th column) using the baseline burstiness method [8] (top row) and the proposed repttile detection and adaptive assignment (bottom row). The green borders indicate correctly recognized images. The orange dots show the visual word matches between the query image (1st column) and the best matching database image (2nd column). The visual word matches are also displayed on the 2nd and 3rd best matching images. Please note that for improved clarity, the matching visual words in the query are not shown for the second and third match. f5a Query image Top 3 ranked images Query image Top 3 ranked images

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Sensitivity to different parameters on the Pittsburgh dataset. The fraction of correctly recognized queries (Recall, y-axis) vs. the number of top N retrieved database images (x-axis) for different parameter setup.

  ) and11(a) show the evaluation of place recognition performance for different values of T . We use T = 1 (unless stated otherwise).• The number of visual word assignments K. Figures 10(b) and 11(b) show the method is fairly insensitive to the choice of the number K of visual word assignments for repttile detection, where values of 20 (AA thr-idf (K = 20)) and the standard 50 (AA thr-idf (K = 50)) result in a similar performance. We use K = 50 (unless stated otherwise).

Fig. 12 .

 12 Fig.[START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. Memory complexity vs. place recognition performance. The memory footprint of the database (x-axis) vs. the fraction of correctly recognized queries (Recall, y-axis) at the top 1 rank by the proposed method (AA thridf, orange dot), the baseline burstiness weighting (brstidf, blue dot), and the Fisher vector representations (FV, black dots). The numbers beside the black dots indicate the dimension of each Fisher vector (reduced by PCA).

Fig. 13 .Fig. 14 .

 1314 Fig. 13. Examples of re-ranking by geometric verification on the Pittsburgh dataset. Each figure shows the query image (left column) and the three best matching database images (2nd to 4th column) using the proposed adaptive soft-assignment (top row), re-ranked by visual word matching with geometric verification [11] (middle row), and re-ranked by the proposed visual word matching taking into account detected repttiles (bottom row). The green borders indicate correctly recognized images. The orange and cyan dots show the visual word matches and the inlier matches verified by the geometric verification, respectively, between the query image (1st column) and the best matching database image (2nd column). The matches are displayed on the 2nd and 3rd best matching images but their corresponding features are not shown in the query. Query image Top 3 ranked images Query image Top 3 ranked images

TABLE 1

 1 Scalability and place recognition performance on the Pittsburgh dataset.

	Method	Memory		Recall
		(GB)	top 1	top 5	top 50
	AA thr-idf	3.17	60.97	73.83	85.85
	tf-idf	1.21	26.52	40.66	67.85
	brst-idf	1.21	43.93	59.64	79.36
	SA tf-idf	3.54	35.46	50.45	74.77
	FV 512	0.52	50.41	64.73	80.56
	FV 4096	4.16	57.78	70.20	82.51

TABLE 2

 2 Scalability and place recognition performance on the San Francisco dataset.

	Method	Memory		Recall
		(GB)	top 1	top 5	top 50
	AA thr-idf	12.89	65.38	72.10	80.57
	tf-idf	4.94	23.16	32.50	55.04
	brst-idf	4.94	46.45	57.53	72.98
	SA thr-idf	14.38	33.25	44.08	61.02
	FV 512	2.18	48.07	57.78	70.49
	FV 4096	17.41	60.77	69.49	78.08

TABLE 3

 3 Re-ranking with geometric verification on the Pittsburgh dataset.

	Method	Multi-	Ratio test	Repttile	Recall	Recall	# of tent.	Computation	Total memory
		assign		removal	(top 1)	(top 3)	matches	time (sec)	(GB)
	Initial ranking (AA thr-idf)				60.97	70.14	-	-	3.17
	Raw descriptor		x		76.68	80.86	64.10	0.91	29.12
	Visual word matching [11]				60.84	70.63	29.40	0.41	4.69
		x			66.93	75.68	252.99	4.94	4.69
	Visual word matching	x	x		67.23	76.78	146.06	1.34	4.69
	with the proposed method	x		x	71.44	78.14	108.40	1.03	4.88
		x	x	x	70.41	77.41	83.14	0.64	4.88

TABLE 4

 4 Re-ranking with geometric verification on the San Francisco dataset.

	Method	Multi-	Ratio test	Repttile	Recall	Recall	# of tent.	Computation	Total memory
		assign		removal	(top 1)	(top 3)	matches	time (sec)	(GB)
	Initial ranking (AA thr-idf)				65.38	69.74	-	-	12.89
	Raw descriptor		x		76.09	78.58	69.99	2.77	104.01
	Visual word matching [11]				68.62	72.73	29.66	0.82	18.25
		x			73.47	77.09	227.72	8.29	18.25
	Visual word matching	x	x		73.35	77.83	102.01	3.00	18.25
	with the proposed method	x		x	75.47	77.83	134.75	2.06	18.92
		x	x	x	74.22	77.96	78.08	1.43	18.92

TABLE 5 mAP

 5 on INRIA Holidays and Oxford Building datasets.

ACKNOWLEDGMENTS

We thank Relja Arandjelovic for discussions on descriptor compression. The authors were supported by JSPS KAKENHI Grant Number 24700161, EU FP7-SPACE-2012-312377 PRoViDE, TACR TA02011275 ATOM, the MSR-INRIA laboratory, EIT-ICT labs, the ANR project Semapolis, CityLabs@Inria and the ERC project LEAP.