Year: 2022

Abstract:
Methods that combine local and global features have recently shown excellent performance on multiple challenging deep image retrieval benchmarks, but their use of local features raises at least two issues. First, these local features simply boil down to the localized map activations of a neural network, and hence can be extremely redundant. Second, they are typically trained with a global loss that only acts on top of an aggregation of local features; by contrast, testing is based on local feature matching, which creates a discrepancy between training and testing. In this paper, we propose a novel architecture for deep image retrieval, based solely on mid-level features that we call Super-features. These Super-features are constructed by an iterative attention module and constitute an ordered set in which each element focuses on a localized and discriminant image pattern. For training, they require only image labels. A contrastive loss operates directly at the level of Super-features and focuses on those that match across images. A second complementary loss encourages diversity. Experiments on common landmark retrieval benchmarks validate that Super-features substantially outperform state-of-the-art methods when using the same number of features, and only require a significantly smaller memory footprint to match their performance. Code and models are available at: https://github.com/naver/FIRe.

heading: 1 INTRODUCTION
text: Image retrieval is a task that models exemplar-based recognition, i.e. a class-agnostic, fine-grained understanding task which requires to retrieve all images matching a query image over an (often very large) image collection. It requires learning features that are discriminative enough for a highly detailed visual understanding but also robust enough to extreme viewpoint/pose or illumination changes. A popular image retrieval task is landmark retrieval, whose goal is to single out pictures of the exact same landmark out of millions of images, possibly containing a different landmark from the exact same fine-grained class (e.g. ‘gothic-era churches with twin bell towers’).
While early approaches relied on handcrafted local descriptors, recent methods use image-level (global) or local Convolutional Neural Networks (CNN) features, see Csurka & Humenberger (2018) for a review. The current state of the art performs matching or re-ranking using CNN-based local features (Noh et al., 2017; Cao et al., 2020; Tolias et al., 2020) and only learns with global (i.e. image-level) annotations and losses. This is done by aggregating all local features into a global representation on which the loss is applied, creating a discrepancy between training and inference.
Attention maps from modules like the ones proposed by Vaswani et al. (2017) are able to capture intermediate scene-level information, which makes them fundamentally similar to mid-level features (Xiao et al., 2015; Chen et al., 2019). Unlike individual neurons in CNNs which are highly localized, attention maps may span the full input tensor and focus on more global or semantic patterns. Yet, the applicability of mid-level features for instance-level recognition and image retrieval is currently underwhelming; we argue that this is due to the following reasons: generic attention maps are not localized and may fire on multiple unrelated locations; at the same time, object-centric attentions such as the one proposed by Locatello et al. (2020) produce too few attentional features and there is no mechanism to supervise them individually. In both cases, methods apply supervision at the global level, and the produced attentional features are simply not discriminative enough.
In this paper, we present a novel image representation and training framework based solely on attentional features we call Super-features. We introduce an iterative Local feature Integration Trans-
former (LIT), which tailors existing attention modules to the task of image retrieval. Compared to the slot attention (Locatello et al., 2020) for example, it is able to output an ordered and much larger set of features, as it is based on learned templates, and has a simplified recurrence mechanism. For learning, we devise a loss that is applied directly to Super-features, yet it only requires imagelevel annotations. It pairs a contrastive loss on a set of matching Super-features across matching images, with a decorrelation loss on the attention maps of each image, to encourage Super-feature diversity. In the end, our network extracts for each image a fixed-size set of Super-features that are semantically ordered, i.e., each firing on different types of patterns; see Figure 1 for some examples.
At test time, we follow the protocol of the best performing recent retrieval methods and use ASMK (Tolias et al., 2013), except that we aggregate and match Super-features instead of local features. Our experiments show that the proposed method significantly outperforms the state of the art on common benchmarks like ROxford and RParis (Radenović et al., 2018a), while requiring less memory. We further show that performance gains persist in the larger scale, i.e. after adding 1M distractor images. Exhaustive ablations suggest that Super-features are less redundant and more discriminative than local features.
Contributions. Our contribution is threefold: (a) an image representation based on Super-features and an iterative module to extract them; (b) a framework to learn such representations, based on a loss applied directly on Super-features yet only requiring image-level labels; (c) extensive evaluations that show significant performance gains over the state of the art for landmark image retrieval. We call our method Feature Integration-based Retrieval or FIRe for short.

heading: 2 BACKGROUND: LEARNING LOCAL FEATURES WITH A GLOBAL LOSS
text: Let function f : I Ñ RWˆHˆD denote a convolutional neural network (CNN) backbone that encodes an input image x P I into a pW ˆH ˆDq-sized tensor of D-dimensional local activations over a pW ˆ Hq spatial grid. After flattening the spatial dimensions, the output of f can also be seen as set of L “ W ¨ H feature vectors denoted by U “ tul P RD : l P 1 .. Lu; note that the size of this set varies with the resolution of the input image. These local features are then typically whitened and their dimension reduced, a process that we represent by function op¨q in this paper. Global representations, i.e. image-level feature vectors, are commonly produced by averaging all local features, e.g. via global average or max pooling (Babenko & Lempitsky, 2015; Tolias et al., 2016; Gordo et al., 2016).
A global contrastive loss for training. Tolias et al. (2020) argue that optimizing global representations is a good surrogate for learning local features to be used together with efficient match kernels for image retrieval. When building their global representation gpUq, they weight the contribution of
each local feature to the aggregated vector using its l2 norm:
gpUq “ ĝpUq}ĝpUq}2 , ĝpUq “
L ÿ l“1 }ul}2 ¨ opulq, (1)
where }¨}2 denotes the l2 norm. Given a database where each image pair is annotated as matching with each other or not, they minimize a contrastive loss over tuples of global representations. Intuitively, this loss encourages the global representations of matching images to be similar and those of non-matching images to be dissimilar. Let tuple pU,U`,V´1 , . . . ,V´n q represent the sets of local features of images px,x`,y´1 , . . . ,y´n q, where x and x` are matching images (i.e. a positive pair) and none of the images y´1 , . . . ,y ´ n is matching with image x (i.e. they are negatives). Let r¨s` denote the positive part and µ a margin hyper-parameter. They define a contrastive loss over global representations as:
Lglobal “ › ›gpUq ´ gpU`q › › 2
2 `
n ÿ
j“1
“ µ´ › ›gpUq ´ gpV´j q › › 2
2
‰` . (2)
In HOW, Tolias et al. (2020) employ the global contrastive loss of Eq.(2) to learn a model whose local features are then used with match kernels such as ASMK (Tolias et al., 2013) for image retrieval. ASMK is a matching process defined over selective matching kernels of local features; it is a much stricter and more precise matching function than comparing global representations, and is crucial for achieving good performance. By learning solely using a loss defined over global representations and directly using ASMK over local features U, HOW achieves excellent image retrieval performance.

heading: 3 LEARNING WITH SUPER-FEATURES
text: Methods using a global loss for training but local features for matching have a number of disadvantages. First, using local activations as local features leads to high redundancy, as they exhaustively cover highly overlapping patches of the input image. Second, using ASMK on local features from a model trained with a global loss introduces a mismatch between training and testing: the local features used for ASMK are only trained implicitly, but are expected to individually match in the matching kernel. To obtain less redundant feature sets, we propose to learn Super-features using a loss function that operates directly on those features, and to also use the latter during retrieval; the train/testing discrepancy of the pipeline presented in Section 2 is thus eliminated.
In this section, we first introduce the Local feature Integration Transformer (LIT), an iterative attention module which produces an ordered set of Super-features (Section 3.1). We then present a framework for effectively learning such features (Section 3.2) that consists of two losses: A contrastive loss that matches individual Super-features across positive image pairs, and a decorrelation
loss on the Super-feature attention maps that encourages them to be diverse. An overview of the pipeline is depicted in Figure 2. We refer to our approach as Feature Integration-based Retrieval or FIRe for short, an homage to the feature integration theory of Treisman & Gelade (1980).

heading: 3.1 LOCAL FEATURE INTEGRATION TRANSFORMER (LIT)
text: Inspired by the recent success of attention mechanisms for encoding semantics from global context in sequences (Vaswani et al., 2017) or images (Caron et al., 2021), we rely on attention to design our Local feature Integration Transformer (LIT), a module that outputs an ordered set of Super-features.
Let LIT be represented by function ΦpUq : RLˆD Ñ RNˆd that takes as input the set of local features U and outputs N Super-features. We define LIT as an iterative module:
ΦpUq “ QT , Qt “ φpU;Qt´1q, (3) where φ denotes the core function of the module applied T times, and Q0 P RNˆd denotes a set of learnable templates, i.e. a matrix of learnable parameters. Super-features are progressively formed by iterative refinement of the templates, conditioned on the local features from the CNN.
The architecture of the core function φ is inspired by the Transformer architecture (Vaswani et al., 2017) and is composed of a dot-product attention function ψ, followed by a multi-layer perceptron (MLP). The dot-product attention function ψ receives three inputs, the key, the value and the query1 which are passed through layer normalization and fed to linear projection functionsK, V andQ that project them to dimensions dk, dv and dq , respectively. In practice, we set dk“dv“dq“d“1024. The key and value inputs are set as the local features ul P U across all iterations. The query input is the set of templates Qt “ tqtn P Rd, n “ 1 .. Nu. It is initialized as the learnable templates Q0 for iteration 0, and is set as the previous output of function φ for the following iterations. After projecting with the corresponding linear projection functions, the key and the query are multiplied to construct a set ofN attention maps over the local features, i.e., the columns of matrixα P RLˆN , while the L rows αl of that matrix can be seen as the responsibility that each of the N templates has for each local feature l, and is given by2:
α “
»
—
– α1 ... αL
fi
ffi
fl P RLˆN , αl “ α̂l
řL i“1 α̂i
, α̂l “ eMl
řN n“1 e
Mln , Mln “ Kpulq ¨ Qpqtnq? d . (4)
The dot product between keys and templates can be interpreted as a tensor of compatibility scores between local features and templates. These scores are normalized across templates via a softmax function, and are further turned into attention maps by l1 normalization across all L spatial locations. This is a common way of approximating a joint normalization function across rows and columns, also used by Locatello et al. (2020). The input value is first projected with V , re-weighted with the attention maps and then residually fed to a MLP3 to produce the output of function φ:
Qt “ φpU;Qt´1q, φpU;Qq “ MLPpψpU;Qqq ` ψpU;Qq, ψpU;Qq “ V pUq ¨α` Q. (5) Following standard image retrieval practice, we further whiten and l2-normalize the output of ΦpUq to get the final set of Super-features. Specifically, let ΦpUq “ rŝ1; . . . ; ŝN s P RNˆd be the raw output of our iterative attention module, we define the ordered set of Super-features as:
S “ ! sn : sn “ opŝnq }opŝnq}2 , n “ 1, .., N ) , (6)
where, as in Section 2, op¨q denotes dimensionality reduction and whitening. Figure 2 (right) illustrates the architecture of LIT. Note that all learnable parameters of φ are shared across all iterations.
What do Super-features attend to? Each Super-feature in S is a function of all local features in U, invariant to permutation of its elements, and can thus attend arbitrary regions of the image.
1The term ‘query’ has a precise meaning for retrieval; yet, for this subsection only, we overload the term to refer to one of the inputs of the dot-product attention, consistently with the terminology from seminal works on attention by Vaswani et al. (2017).
2The attention maps presented in Eq.(4) are technically taken at iteration t, but we omit iteration superscripts for clarity. For the rest of the paper and visualizations, we use attention maps to refer to the attention maps of Eq.(4) after the final (T -th) iteration of the iterative module.
3The MLP function consists of a layer-norm, a fully-connected layer with half the dimensions of the features, a ReLU activation and a fully-connected layer that projects features back to their initial dimension.
To visualize the patterns captured by Super-features, Figure 1 shows the attention maps of the same five Super-features for three images, including two of the same landmark (first two rows). The type of patterns depends on the learned initialization templates Q0; this explains why the Super-features form an ordered set, a property which allows to directly compare Super-features with the same ID. We observe the attention maps to be similar across images of the same landmark and to contain some mid-level patterns (such as a half-circle on the second column, or windows on the third one).

heading: 3.2 LEARNING WITH SUPER-FEATURES
text: We jointly fine-tune the parameters of the CNN and of the LIT module using contrastive learning. However, departing from recent approaches like HOW (Tolias et al., 2020) or DELG (Cao et al., 2020) that use a global contrastive loss similar to the one presented in Eq. (2), we introduce a contrastive loss that operates directly on Super-features, the representations we use at test time, and yet only requires image-level labels. Given a positive pair (i.e. matching images of the same landmark) and a set of negative images, we select promising Super-feature pairs by exploiting their ordered nature and without requiring any extra supervision signal. We then minimize their pairwise distance, while simultaneously reducing the spatial redundancy of Super-features within an image.
Selecting matching Super-features. Since we are only provided with pairs of matching images, i.e. image-level labels, defining correspondences at the Super-feature level is not trivial. Instead of approximating sophisticated metrics (Liu et al., 2020; Mialon et al., 2021)–see Section 5 for a discussion–, we leverage the fact that Super-features are ordered and we select promising matches and filter out erroneous ones only relying on simple, nearest neighbor-based constraints.
For any s P S, let ipsq be the function that returns the position/order or Super-feature ID, i.e. ipsiq “ i, @si P S. Further let function nps,Sq “ arg minsiPS }s´ si}2 be the function that returns the nearest neighbor of s from set S. Now, given a positive pair of images x,x`, let s P S, s1 P S1 be two Super-features from their Super-feature sets S,S1, respectively. In order for Super-feature pair ps, s1q to be eligible, all of the following criteria must be met: a) s, s1 have to be reciprocal nearest neighbors, b) they need to pass Lowe’s first-to-second neighbor ratio test (Lowe, 2004) and c) they need to have the same Super-feature ID. Let P be the set of eligible pairs and τ the hyper-parameter that controls the ratio test; the conditions above can formally be written as:
ps, s1q P P ðñ " s “ nps1,Sq s1 “ nps,S1q and
" ipsq “ ips1q }s´ s1}2 { }s1 ´ nps1,Sztsuq}2 ě τ . (7)
We set τ “ 0.9. Our ablations (Section 4.1) show that all criteria are important. Note that the pair selection step is non-differentiable and no gradients are computed for Super-features not in P. We further discuss this in Appendix B.4 and empirically show that all Super-features are trained.
A contrastive loss on Super-features. Once the set P of all eligible Super-feature pairs has been constructed, we define a contrastive margin loss on these matches. Let pair p “ ps, s`q P P be a pair of Super-features, selected from a pair of matching images x,x`, and let Npjq “ tnkj : k “ 1 .. nu for j “ 1 .. N be the set of Super-features with Super-feature ID j extracted from negative images py´1 , . . . ,y´n q. The contrastive Super-feature loss can be written as:
Lsuper “ ÿ
ps,s`qPP
”
› ›s´ s` › › 2
2 `
ÿ
nPNpipsqq rµ1 ´ }s´ n}22s
` ı
, (8)
where µ1 is a margin hyper-parameter and the negatives for each s are the Super-features from all n negative images of the training tuple with Super-feature ID equal to ipsq. Reducing the spatial correlation between attention maps. To obtain Super-features that are as complementary as possible, we encourage them to attend to different local features, i.e. different locations of the image. To this end, we minimize the cosine similarity between the attention maps of all Super-features of every image.
Specifically, let matrix α “ rα̃1, . . . , α̃N s now be seen as column vectors denoting the N attention maps after the last iteration of LIT. The attention decorrelation loss is given by:
Lattnpxq “ 1
NpN ´ 1q
ÿ
i‰j
α̃ᵀi ¨ α̃j }α̃i}2 }α̃j}2 , i, j P t1, .., Nu. (9)
Table 1: Ablation on matching constraints: Impact of removing constraints on reciprocity, Lowe’s ratio test and the Super-feature ID.
reci- ratio same SfM-120k ROxford RParis proc. test ID val med hard med hard
68.3 64.3 39.8 74.1 52.4 X 79.6 69.2 44.3 79.2 60.9 X X 80.8 70.7 45.1 80.3 61.9 X 75.9 63.8 35.1 77.3 56.5 X X X 89.7 81.8 61.2 85.3 70.0
In other words, this loss minimizes the off-diagonal elements of theNˆN self-correlation matrix of α̃. We ablate the benefit of this loss and others components presented in this section in Section 4.1.
Image retrieval with Super-features. Our full pipeline, FIRe, is composed of a model that outputs Super-features, trained with the contrastive Super-feature loss of Eq.(8) and the attention decorrelation loss of Eq.(9). As our ablations show (see Section 4), the combination of these two losses is required for achieving state-of-the-art performance, while adding a third loss on the aggregated global features as in Eq.(2) does not bring any gain.

heading: 4 EXPERIMENTS
text: This section validates our proposed FIRe approach on standard landmark retrieval tasks. We use the SfM-120k dataset (Radenović et al., 2018b) following the 551/162 3D model train/val split from Tolias et al. (2020). For testing, we evaluate instance-level search on the ROxford (Philbin et al., 2007) and the RParis (Philbin et al., 2008) datasets in their revisited version (Radenović et al., 2018a), with and without the 1 million distractor set called R1M. They both contain 70 queries, with 4993 and 6322 images respectively. We report mean average precision (mAP) on the Medium (med) and Hard (hard) setups, or the average over these two setups (avg).
Image search with Super-features. At test time, we follow the exact procedure described by Tolias et al. (2020) and extract Super-features from each image at 7 resolutions/scales {2.0, 1.414, 1.0, 0.707, 0.5, 0.353, 0.25}. We then keep the top Super-features (the top 1000 unless otherwise stated) according to their L2 norm and use the binary version of ASMK with a codebook of 65536 clusters. Note that one can measure the memory footprint of a database image x via the number of non-empty ASMK clusters, i.e. clusters with at least one assignment, denoted as |Cpxq|. Implementation details. We build our codebase on HOW (Tolias et al., 2020)4 and sample tuples composed of one query image, one positive image and 5 hard negatives. Each epoch is composed of 400 batches of 5 tuples each, while hard negatives are updated at each epoch using the global features of Eq.(1). We train our model for 200 epochs on SfM-120k using an initial learning rate of 3.10´5 and random flipping as data augmentation. We multiply the learning rate by a factor of 0.99 at each epoch, and use an Adam optimizer with a weight decay of 10´4. We use a ResNet50 (He et al., 2016) without the last convolutional block as backbone (R50´). For LIT, we use D “ dk “ dq “ dv “ d “ 1024. Following HOW, we reduce the dimensionality of features to 128 and initialize op¨q using PCA and whitening before training and keep it frozen. We pretrain the LIT module with the backbone on ImageNet-1K for image classification, see details in Appendix B.6. We use µ1 “ 1.1 in Eq.(8) and weight Lsuper and Lattn with 0.02 and 0.1, respectively.

heading: 4.1 ANALYSIS AND ABLATIONS
text: In this section, we analyze the proposed FIRe framework and perform exhaustive ablations on the training losses and the matching constraints. The impact of the number of iterations (T ) and templates (N ) in LIT is studied in Appendix A.1. For the rest of the paper, we set T “ 6 and N “ 256. Matching constraints ablation. Table 1 reports the impact of the different matching constraints: nearest neighbor, reciprocity, Lowe ratio test and constraint on Super-features ID. Adding reciprocity
4https://github.com/gtolias/how
Table 2: Ablation on loss components: Impact of removing Lattn, using either a global loss Lglobal or a loss directly on Super-features Lsuper or a combination of both.
Lglobal Lattn Lsuper SfM-120k ROxford RParis
val med hard med hard
X 79.0 64.3 38.0 75.4 51.7 X X 87.7 75.8 51.2 79.0 57.0 X X X 88.4 79.0 57.2 83.0 65.6
X 61.7 59.3 32.8 69.9 47.3 X X 89.7 81.9 61.5 85.3 70.1
1 256 1
256
1 256 1
256
Correlation
high
low
Figure 4: Impact of Lattn on the correlation matrix between attention maps (the darker, the lower is the correlation) at the last iteration of LIT when training with (left) and without (right). This is averaged over the 70 queries of ROxford.
0 500 1,000 1,500
60
65
70
1000
2000
1000
average |Cpxq|
ROxford (avg)
FIRe HOW
0 500 1,000 1,500
65
70
75
1000
2000 1000
average |Cpxq|
RParis (avg)
FIRe HOW
Figure 5: Performance versus memory for HOW and FIRe. The x-axis shows the average number of clusters per image used in ASMK (proportional to memory usage). We vary the number of features extracted per image before aggregation in t200, . . . , 2000, 2500, . . . , 5000u; solid markers denote the commonly used settings (1000/2000). FIRe has at most 1,792 features (256 per scale).
and Lowe’s ratio test significantly improves performance, which indicates that it reduces the number of incorrect matches. Keeping all pairs with the same ID yields lower performance: the ID constraint alone is not enough. One possible explanation is that two images from the same landmark may differ significantly, e.g. when some parts are visible in only one of the two images. In that case, the other constraints allow features attending non-overlapping regions of a positive image pair to be excluded from P. Finally, combining the selective ID constraint with the others yields the best performance.
In order to better understand the impact of the Super-feature ID constraint, a constraint only applicable for Super-features due to their ordered nature, we measure the quality of selected matches during training with and without it. Since there is no ground-truth for such localized matches on landmark retrieval datasets, we measure instead the ratio of matches coming from the positive pair, over all matches (from the positive and all negatives). Ideally, a minimal number of matches should come from the negatives, hence this ratio should be close to 1. In Figure 3 we plot this match ratio for all epochs; we observe that it is significantly higher when using the Super-features ID constraint.
Training losses ablation. We study the impact of the different training losses in Table 2. We start from a global loss similar to HOW (first row). We then add the decorrelation loss (second row) and observe a clear gain. It can be explained by the fact that without this loss, Super-features tend to be redundant (see the correlation matrices in Figure 4). Adding the loss operating directly on the Super-features further improves performance (third row). Next, we remove the global loss and keep only the loss on Super-features alone (fourth row) or with the decorrelation loss (last row). The latter performs best (fourth vs last row). Figure 4 displays the correlation matrix of Superfeatures attention maps with and without Lattn. Without it, we observe that most Super-features have correlated attentions. In contrast, training with Lattn leads to uncorrelated attention maps. This is illustrated in Figure 1 which shows several attention maps focusing on different areas.
Varying the number of features at test time. Figure 5 compares HOW (Tolias et al., 2020) with our approach, as we vary the number of local features / Super-features. The x-axis shows the average number of clusters used in ASMK for the database images, i.e., which is proportional to the average memory footprint of an image. We observe that our approach does not only significantly improve
accuracy compared to HOW, but also requires overall less memory. Notably, FIRe matches the best performance of HOW with a memory footprint reduced by a factor of 4. For both methods, performance goes down once feature selection no longer discards background features. The gain in terms of performance is even larger when considering a single scale at test time (see Appendix B.1).
Statistics on the number of selected features per scale. The left plot of Figure 6 shows the percentage of the 1000 selected features that comes from each scale, for HOW and FIRe. For HOW most selected features come from the higher resolution inputs; by contrast, selected Super-features are almost uniformly distributed across scales. Interestingly, Figure 6 (middle) shows that HOW keeps a higher percentage of the features coming from coarser scales. Yet, the final feature selection for HOW is still dominated by features from higher scales, due to the fact that the number of local features significantly increases with the input resolution (see Figure 6 right).

heading: 4.2 COMPARISON TO THE STATE OF THE ART
text: We compare our method to the state of the art in Table 3. All reported methods are trained on SfM-120k for a fair comparison.5 First, we observe that methods based on global descriptors (Tolias et al., 2016; Revaud et al., 2019a) compared with a L2 distance tend to be less robust than methods based on local features (Noh et al., 2017; Tolias et al., 2020). DELG (Cao et al., 2020) shows better performance, owing to a re-ranking step based on local features, at the cost of re-extracting local features for the top-ranked images of a given query, given that local features would take too much memory to store. Our FIRe method outperforms DELF (Noh et al., 2017) as well as HOW (Tolias et al., 2020) by a significant margin when extracting 1000 features per image. Importantly, our approach also requires less memory, as it uses fewer ASMK clusters per image, as shown in Figure 5: for the whole R1M set, HOW uses 469 clusters per image while FIRe uses only 383, on average.

heading: 5 RELATED WORK
text: Image descriptors for retrieval. The first approaches for image retrieval were based on handcrafted local descriptors and bag-of-words representations borrowed from text retrieval (Sivic & Zisserman, 2003; Csurka et al., 2004), or other aggregation techniques like Fisher Vectors (Perronnin et al., 2010), VLAD (Jégou et al., 2010) or ASMK (Tolias et al., 2013). First deep learning techniques were extracting a global vector per image either directly or by aggregating local activations (Gordo et al., 2016; Radenović et al., 2018b) and have shown to highly outperform handcrafted local features, see (Csurka & Humenberger, 2018) for a review. Methods that perform matching or re-ranking using CNN-based local features are currently the state of the art in the area (Noh et al., 2017; Teichmann et al., 2019; Cao et al., 2020; Tolias et al., 2020). They are able to learn with global (i.e. image-level) annotations. Most of them use simple variants of attention mechanisms (Noh et al., 2017; Ng et al., 2020) or simply the feature norm (Tolias et al., 2020) to weight local activations.
Low-level features aggregation. Aggregating local features into regional features has a long history. Crucial to the success of traditional approaches, popular methods include selecting discriminative patches in the input image (Singh et al., 2012; Gordo, 2015), regressing saliency map scores
5The GLDv2-clean dataset (Yokoo et al., 2020) is sometimes used for training. Yet, there is significant overlap between its training classes and the ROxford and RParis query landmarks. This departs from standard image retrieval evaluation protocols. See Appendix B.8 for details.
at different resolutions (Jiang et al., 2013), aggregating SIFT descriptors with coding and pooling schemes (Boureau et al., 2010), or mining frequent patterns in sets of SIFT features (Singh et al., 2012). More recently, Hausler et al. (2021) introduced a multi-scale fusion of patch features.
Supervision for local features. Several works provide supervision at the level of local features in the context of contrastive learning. Xie et al. (2021) and Chen et al. (2021) obtain several views of an input image using data augmentations with known pixel displacements. Similarly, Liu et al. (2020) train a model to predict the probability for a pair of local features to match, evaluated using known displacements. Wang et al. (2020) and Zhou et al. (2021) obtain local supervision by relying on epipolar coordinates and relative camera poses. Positive pairs in image retrieval depart from these setups, as pixel-level correspondences cannot be known. To build matches, Wang et al. (2021) use a standard nearest neighbor algorithm to build pairs of features, similarly to our approach, but without the use of filtering which is critical to our final performance. Using the current model predictions to define targets is reminiscent of modern self-supervised learning approaches which learn without any label (Caron et al., 2021; Grill et al., 2020). The additional filtering step can be seen as a way to keep only the most reliable model predictions, similar to self-distillation as in e.g. Sohn et al. (2020).
Attention modules. Our LIT module is an iterative variant of standard attention (Bahdanau et al., 2015; Vaswani et al., 2017), adapted to map a variable number of input features to an ordered set of N output features, similar to Lee et al. (2019). The Perceiver model (Jaegle et al., 2021) has demonstrated the flexibility of such constructions by using it to scale attention-based deep networks to large inputs. Our design was heavily inspired by slot-attention (Locatello et al., 2020), but has some key differences that enable us to achieve high performance in more complex visual environments: a) unlike the slot attention which initializes its slots with i.i.d sampling, we learn the initial templates and therefore define an ordering on the output set, a crucial property for selecting promising matches; b) we replace the recurrent network gates with a residual connection across iterations. These modifications, together with the attention decorrelation loss enable our module to go from a handful of object-oriented slots to a much larger set of output features. For object detection, Carion et al. (2020) rely on a set of learned object queries to initialize a stack of transformer layers. Unlike ours, their module is not recurrent; Appendix A.1 experimentally shows substantial benefits from applying LIT T times, with weight sharing, to increase model flexibility without extra parameters.

heading: 6 CONCLUSIONS
text: We present an approach that aggregates local features into Super-features for image retrieval, a task that has up to now been dominated by approaches that work at the local feature level. We design an attention mechanism that outputs an ordered set of such features that are more discriminative and expressive than local features. Exploiting their ordered nature and without any extra supervision, we present a loss working directly on the proposed features. Our method not only significantly improves performance, but also requires less memory, a crucial requirement for scalable image retrieval.

heading: Appendix

heading: Table of Contents

heading: A Additional ablations 14
text: A.1 Impact of the iteration and the number of templates hyper-parameters . . . . . . 14 A.2 Impact of hard negatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 A.3 Impact of the update function . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.4 Extended ablation on matching constraints . . . . . . . . . . . . . . . . . . . . 15 A.5 Impact of the template initialization . . . . . . . . . . . . . . . . . . . . . . . . 15

heading: B Analysis and discussions 16
text: B.1 Single-scale results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B.2 Consistency of attention maps across scales . . . . . . . . . . . . . . . . . . . . 16 B.3 Redundancy in Super-features . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B.4 Are all Super-features trained? . . . . . . . . . . . . . . . . . . . . . . . . . . 17 B.5 Using the Super-feature loss with local features . . . . . . . . . . . . . . . . . . 17 B.6 Pretraining the backbone together with LIT . . . . . . . . . . . . . . . . . . . . 18 B.7 Computational cost of Super-features extraction . . . . . . . . . . . . . . . . . 18 B.8 Is Google Landmarks v2 clean an appropriate training dataset for testing on
ROxford and RParis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

heading: C Application to visual localization 18
text: In this appendix, we present additional ablations (Appendix A), a deeper analysis of our framework (Appendix B) as well as results of the application of our FIRe framework for image retrieval to the task of visual localization (Appendix C). We briefly summarize the findings in the following paragraphs.
Ablations. We study the impact of some hyper-parameters of our model, namely the size N of the set of Super-features, and the number of iterations T in the LIT module, in Appendix A.1. We show that 256 Super-features and 6 iterations offer the best trade-off between performance and computational cost. We also show in Appendix A.2 that we obtain further performance gains of over 1% by increasing the number of negatives to 10 or 15. We then study the impact of replacing the residual connection inside the LIT module by a recurrent network (Appendix A.3). In Appendix A.4 we present an extended version of Table 1 with further matching constraints and we finally study the impact of the template initialization on performance in Appendix A.5.
Properties of Super-features. We show single-scale results in Appendix B.1. In Appendix B.2, we display the attention maps of Super-features, at different scales for a fixed Super-feature ID. We further study the amount of redundancy in Super-features, compared to local features, in Appendix B.3. Next, we verify in Appendix B.4 that all Super-features receive training signal, as a sanity check. We discuss the case of applying a loss directly on local features in Appendix B.5 and give details about the pretraining on ImageNet in Appendix B.6. In Appendix B.7 we report the average extraction time for the proposed Super-features, while in Appendix B.8 we discuss the fact that there is an overlap between the queries from the common ROxford and RParis datasets and the Google Landmarks-v2-clean dataset that is commonly used as training set for retrieval on ROxford and RParis.
Application to visual localization. We further evaluate our model using a visual localization setting on the Aachen Day-Night v1.1 dataset (Sattler et al., 2018) in Appendix C. To do so, we leverage a retrieval + local feature matching pipeline, and show that it is beneficial to use our method, especially in hard settings.

heading: A ADDITIONAL ABLATIONS
text: A.1 IMPACT OF THE ITERATION AND THE NUMBER OF TEMPLATES HYPER-PARAMETERS
In this section, we perform ablations on the number of Super-featuresN and the number of iterations T in the Local feature Integration Transformer. We first study the impact of the number N of Superfeatures extracted for each scale of each image in Figure 7a. We observe that the best value is 256 on both the validation and test sets (ROxford and RParis). We then study the impact of the number of iterations T in Figure 7b. While the performance decreases when doing 2 or 3 iterations compared to just 1, a better performance is reached for 6 iterations, after which the performance saturates while requiring more computations. We thus use T “ 6.
A.2 IMPACT OF HARD NEGATIVES
Each training tuple is composed of one image pair depicting the same landmark, and 5 negative images (i.e. from different landmarks). We plot the performance when varying this number in Figure 8. We observe that adding more negatives improves overall the performance on all datasets, i.e. by more than 1% when increasing it to 10 or 15 negatives, but at the cost of a longer training time as more images need to be processed at each iteration. This is why we use 5 negatives in the rest of the paper as it offers a good compromise between performance and cost.
A.3 IMPACT OF THE UPDATE FUNCTION
The formula for ψ in Equation (5) sums the previous Q with the output of the attention component V pUq ¨ α, i.e., with a residual connection. This is a different choice than the one made in the object-centric slot attention of Locatello et al. (2020), which proposes to use a Gated Recurrent Unit: ψpU;Qq “ GRUpV pUq ¨ α,Q ). We thus compare the residual connection we use to a GRU function and report results in Table 4 with T “ 3. We observe that the residual connection reaches a better performance in all datasets while having the interest of not adding extra parameters.
In summary, we propose the LIT module to obtain a few hundred features for image retrieval while slot attention handles a handful of object attentions. Technical differences to the slot attention include: a) we use a learned initialization of the templates instead of i.i.d. sampling, which allows to obtain an ordered set of features, and thus to apply the constraint on the ID for the matching, leading to a clear gain, see Table 1 and Figure 3, b) to handle a larger number of templates, we also add a decorrelation loss on the attention maps, which has clear benefit, see Table 2 and Figure 4, c) we use a residual connection with 6 iterations instead of a GRU, leading to improved performance for our task (see Table 4).

heading: A.4 EXTENDED ABLATION ON MATCHING CONSTRAINTS
text: We show in Table 5 an extended version of Table 1 of the main paper, where we evaluate all possible combinations of constraints among reciprocity, Lowe’s ratio test and the Super-feature ID. We observe that the reciprocity constraint and the Super-feature ID constraint are the two most important ones, while the Lowe’s ratio only only brings a small improvement.
A.5 IMPACT OF THE TEMPLATE INITIALIZATION
In the LIT module, initial templates Q0 P RNˆd are learned together with the LIT module. We can therefore assume that they are adapted to the task at hand. To explore the sensitivity to the initial templates, we run a variant of FIRe where the initializations are not fine-tuned, but instead frozen to the values after pretraining on ImageNet. We report performance in Table 6. We observe that the two variants perform overall similarly. This ablation suggests that the initial templates are up to some point transferable to other tasks.

heading: B ANALYSIS AND DISCUSSIONS

heading: B.1 SINGLE-SCALE RESULTS
text: Similar to Figure 5 of the main paper, we perform the same ablation in Figure 9 when extracting features at a single scale (1.0). We observe that FIRe significantly improves the mAP on the two datasets compared to HOW. The average number of clusters, i.e. the memory footprint of images, remains similar for both methods at a same number of selected features. This stands in contrast to the multi-scale case where our approach allows to save memory (about 20%), which we hypothesize is due to the correlation of our features across scales that we discuss below.

heading: B.2 CONSISTENCY OF ATTENTION MAPS ACROSS SCALES
text: At test time, we extract Super-features at different image resolutions. We propose here to study if the attention maps of the Super-features across different image scales are correlated. We show in Figure 10 the attention maps at the last iteration of LIT for the different image scales. We observe that they fire at the same image location at the different scales. Note that the attention maps are larger/smoother at small scales (right columns), as for visualization, we resize lower resolution attention maps to the original image size.

heading: B.3 REDUNDANCY IN SUPER-FEATURES
text: To evaluate the redundancy of Super-features versus local features, Figure 11 displays the average cosine similarity between every local feature / Super-feature and its K nearest local features / Super-features from the same image, for different values of K. We observe that Super-features are significantly less correlated to the most similar other ones, compared to local features used in HOW.

heading: B.4 ARE ALL SUPER-FEATURES TRAINED?
text: The loss in Equation (8) only operates on a subset of the Super-feature pairs that pass the criteria of Equation (7); if a Super-feature ID is not matched, it receives no training signal. To investigate if all of the IDs contribute to the loss, we monitored how many times each ID is matched at each epoch and report the percentage over all 2000 training tuples per epoch. In Figure 12 we report mean, standard deviation and minimum number of matches for the N Super-feature ID. We clearly observe that all Super-features receive training signals regularly and each Super-feature is matched about one quarter of the time on average.

heading: B.5 USING THE SUPER-FEATURE LOSS WITH LOCAL FEATURES
text: It is worth noting that the loss in Equation (8) could also theoretically be used over local feature activations. It could be computed on pairs of local features that pass the conditions described in Equation (7), after removing the constraint on having the same Super-feature ID. Unfortunately, we were unable to get any gains over HOW (Tolias et al., 2020) when appending such a loss side-byside with the global loss over local features. Empirically, our ablations (see Section 4.1) show that adding the constraint on the Super-features ID, which is only possible with ordered feature sets, is key to the success of our approach, and significantly improves the quality of the matching.

heading: B.6 PRETRAINING THE BACKBONE TOGETHER WITH LIT
text: Before training on landmark retrieval, we pretrain the backbone network, with the proposed LIT module appended after the last layer, for image classification on ImageNet-1K. Given that we remove the last convolutional block similar to HOW, to avoid overfitting we further append a classification head composed of one fully-connected layer, batch norm, leaky ReLU, dropout and another fully-connected layer at the end of the network and train it for 80 epochs using a standard crossentropy loss and in addition the decorrelation loss Lattn weighted by 0.1, the same weight as during fine-tuning. We start with a learning rate of 0.01 and divide it by 10 every 20 epochs. This new architecture reaches a top-1 (resp. top-5) accuracy of 73.48% (resp. 91.54%) on the ImageNet validation set. Note that this performance is a bit lower than a standard ResNet-50: this is because we have removed the last convolutional block which contains most parameters in the ResNet architecture.

heading: B.7 COMPUTATIONAL COST OF SUPER-FEATURES EXTRACTION
text: We report the time required for extracting multi-scale features for 5000 images, for HOW and FIRe. On our server, it took 157 seconds for HOW and 172 for FIRe, i.e. extraction for Super-features only requires 10% more wall-clock time.
B.8 IS GOOGLE LANDMARKS V2 CLEAN AN APPROPRIATE TRAINING DATASET FOR TESTING ON ROXFORD AND RPARIS?
In the comparison to the state of the art (Table 3), all reported methods are trained on the SfM120k dataset. Several recent works have also released a model trained on the Google Landmarks v2 dataset (Weyand et al., 2020) or its clean version (Yokoo et al., 2020) with excellent performance on RParis. However, we find out that several of the query landmarks from RParis and ROxford were present in the training set of the cleaned version of Google Landmarks v2, such as ‘La Defense’, ‘Eiffel Tower’, ‘Sacré Coeur’ or ‘Hotel les Invalides’ for RParis or such as ‘Mary Madgalen’, ‘Bodleian Library’, ‘All Souls College’ or ‘Radcliffe’ for ROxford.

heading: C APPLICATION TO VISUAL LOCALIZATION
text: In this section, we evaluate FIRe for the task of visual localization, where retrieval is used as a first-stage filtering and before more precise, local feature-based geometric matching. To this end, we follow the pipeline proposed by Kapture6 (Humenberger et al., 2020) on the Aachen Day-Night v1.1 dataset (Sattler et al., 2018). In this scenario, a global Structure-from-Motion map is built
6https://github.com/naver/kapture-localization
from the training images using R2D2 local descriptors (Revaud et al., 2019b). At test time, given a query image to localize, image retrieval is used to retrieve the top-50 nearest images. On these retrieved images, R2D2 local features are extracted and matched with the ones on the query image, and this is used to estimate the position of the camera. The percentage of successfully localized images within three levels of thresholds is then reported on the day or night images, following the visual localization benchmark protocol7, the latter ones being more challenging as training images are taken during daytime.
We compare our retrieval method to AP-GeM (Revaud et al., 2019a) and HOW (Tolias et al., 2020) and report results in Table 7. AP-GeM is the default method used in Kapture (Humenberger et al., 2020). We observe that using FIRe leads to better visual localization, specially in the most challenging scenario of night image localization and the strictest localization threshold: Performance improves by 2% compared to AP-GeM and by 1.5% compared to HOW on night images at a threshold of 0.25m and 2°. Overall, for either day or night images, FIRe either improves or performs on par to both methods compared.
7https://www.visuallocalization.net/

Review summaries:
This paper introduces the concept of super features into image retrieval. The whole framework is named FIRe. The idea is to aggregate a set of features on the feature maps at different scales according to a set of query vectors representing different latent concepts. Hence, the proposed model somehow implements a transformer, which is called LIT in this paper.  To train this model, the authors define two losses. The first one is a triplet-like one executed on the super-feature granular. Some empirical criteria are established to select positive and negative super features. The second one decorrelates the super features from a single image.  ASMK becomes the measurement to compare two images when testing, which is a conventional option in comparing two groups of local features.  We see experiments on ROxford and RParis. The results are quite promising.

The paper proposes Local Feature Integration Transformer (LIT), a new architecture to extract mid-level local features from images that are used for image retrieval. The resulting features are called SuperFeatures and are shown to yield state-of-the-art performance on two standard image retrieval benchmarks. The paper further proposes a learning framework, called Feature Integration-based Retrieval (FIRe), to train LIT using a contrastive loss with only image-level supervision. In contrast to other deep learning based image features that apply the loss on the image embedding or aggregated local features, FIRe applies the loss on the local features directly. An interesting property of SuperFeatures is that they are ordered, meaning a SuperFeature with the same index i in two matching images will be localized on similar structures.

The paper proposes a novel model, denoted as super-features, for image retrieval, with the following specific contributions: 1) features are extracted using an iterative attention module (the Local Feature Integracion (LIT) Transformer). Although similar modules have been proposed before in the literature [Locatello 2020], the authors reference them properly and their proposal have several modifications (decorrelation loss, learning the initial templates, residual connections). 2) The model is trained using contrastive losses on the local features, opposed to the more spread training procedure using constraints on the global embeddings. The paper presents solid experimental results in public datasets and compare them against reasonably chosen baselines. 

Authors describe an architecture for deep image retrieval. For this, they use mid-level features that they call super-features (SF). They construct thes SF by an iterative attention module. They build them as an ordered set in which each element focuses on a localized yet discriminant image pattern. Auhtors show that for training, only image labels suffice. Authors present a set of experiments on common landmark retrieval benchmarks to validate that their SF substantially outperform state-of-the-art methods when using the same number of features. They also show that this requires a significantly smaller memory footprint to match their performance.