Dynamic Spatial Verification for Large-Scale Object-Level Image Retrieval

Images from social media can reflect diverse viewpoints, heated arguments, and expressions of creativity, adding new complexity to retrieval tasks. Researchers working onContent-Based Image Retrieval (CBIR) have traditionally tuned their algorithms to match filtered results with user search intent. However, we are now bombarded with composite images of unknown origin, authenticity, and even meaning. With such uncertainty, users may not have an initial idea of what the results of a search query should look like. For instance, hidden people, spliced objects, and subtly altered scenes can be difficult for a user to detect initially in a meme image, but may contribute significantly to its composition. We propose a new approach for spatial verification that aims at modeling object-level regions dynamically clustering keypoints in a 2D Hough space, which are then used to accurately weight small contributing objects within the results, without the need for costly object detection steps. We call this method Objects in Scene to Objects in Scene (OS2OS) score, and it is optimized for fast matrix operations on CPUs. OS2OS performs comparably to state-of-the-art methods in classic CBIR problems, on the Oxford5K, Paris 6K, and Google-Landmarks datasets, without the need for bounding boxes. It also succeeds in emerging retrieval tasks such as image composite matching in the NIST MFC2018 dataset and meme-style composite imagery fromReddit.


Introduction
Image retrieval traditionally starts with the knowledge of what a user is looking for at query time and ends with a set of relevant results that match those initial expectations. This search regime must be transformed, however, in the age of social media. Nowadays, complex composite images like Internet memes are pervasive in the pools of content that are shared by users on social media [4]. Some of these i) ii) Figure 1. An example of a meme-style image from the subreddit /r/photoshopbattles. Internet memes are humorous messages that are spread on social media, often conforming to a set genre with a distinct style. In this paper, we provide spatial verification to find object-level correspondences between images, which assist in the retrieval of the donor images (highlighted in yellow) that contribute to composites like the one above.
images are of significant cultural value [37], while others represent odious extremist propaganda [10]. Both of these cases are important and timely topics of study, where the retrieval of the source content in reference image collections is paramount. The identification of near duplicate content shared between artistic images has received attention recently, and it can be solved using learned features that are both discriminative and invariant [35]. Further, the evolution of a meme can be traced by finding all of the related images, including images that contributed small donor objects ( Fig. 1), and referencing associated timestamps [24,5]. Similarly, one can debunk misleading or forged images being used for disinformation purposes by verifying identified source material [6]. In this paper we propose a new solution for spatial verification in image retrieval that supports these tasks by modeling object-level regions with the goal of retrieving the sources of small regions in large datasets. One of the major hurdles of image retrieval is the semantic gap [39,43], where a user's understanding of the content transcends the low-level representation and subsequent recall capabilities of a content-based search engine. Ideally, a good algorithm should return results that satisfy the user's higher-level intent, not just images with similar low-level features. However, retrieval approaches developed around this idea may not be sufficient for parsing composite imagery and retrieving relevant results, especially if there are aspects of an image that are not immediately apparent to the user at query time. In addition to the context of image creation and use, an image's extent is also shifted as it can be reused in composite images later on. And finally, given the free-form nature of composite imagery, an effective retrieval approach is expected to operate over a webscale database to maximize potential matching candidates.
With the above aspects in mind, we aim at adapting image retrieval to different contexts, such as composite images, especially those containing small spliced objects. For example, in Fig. 1, we see a composite image created from many smaller donor images. This type of image poses a significant challenge for existing image retrieval algorithms, because if the host (i.e., background) and donor images are matched globally, the latter group would not be highly scored since the content shared with the composite is very small. Nonetheless, tasks like meme analysis and disinformation debunking require the retrieval of each meaningful piece of content in an image under scrutiny. Because the image in question is a conglomeration from many sources, we can assume that the goal of a retrieval system should be to return instances of all images contributing to the composite.
To do so, we propose a new method of spatial verification that allows object-level instance scoring of retrieved results, without the need for costly object detection steps. We devise a feature-agnostic algorithm that utilizes a geometrically consistent voting measure inspired by Hough-based voting techniques, with the major difference of not requiring object regions of interest in the query to be known ahead of time, a manner to make the solution more appropriate to the current reality of unspecified retrieval context. As we show through experiments, the proposed method quickly and accurately localizes and ranks rigid objects contained within the query image to objects contained within a large image database. We call this method the Objects in Scene to Objects in Scene (OS2OS) score.
Through the rest of this paper, we will look at approaches that are related to the proposed OS2OS score, detail our methodology, and then perform experiments utilizing a number of relevant image retrieval datasets and features, including classic handcrafted and contemporary deep feature representations. In summary, the contributions are: • A new perspective on the problem of image retrieval, which aims at addressing the deficiencies in existing problem formulations for retrieval in cases of complex composites and other manipulated images.
• A new method called OS2OS score for spatial verification of matching objects between images, including very small objects that are important for understanding memes and other emerging Internet media. • A series of experiments showing the viability of the approach on the Oxford 5K [29], Paris 6K [31], Google-Landmarks [27], and NIST MFC2018 [25] datasets, as well as meme-style imagery from Reddit [24]. • A new experimental protocol for the Reddit Photoshop Battles dataset [33], preparing it to be used for benchmarking potential solutions to retrieve the donors of composite images.

Related Work
The typical CBIR solutions rely on multi-level representation of the images, to reduce the semantic gap between the pixel values and the system user's retrieval intent. In the lowest levels, typical methods use local features (a.k.a., keypoints) to obtain n-dimensional descriptions of the image content, ranging from handcrafted representations, such as SIFT [23] and SURF [3], to representations learned via neural networks, such as LIFT [22] and DELF [27].
In the subsequent levels, these local features are then used to index and compare, within the n-dimensional space they constitute (a.k.a., the feature space) and through euclidean distance or similar method, pairs of image localities (a.k.a., image patches). State-of-the-art large-scale indexing solutions comprise methods such as Optimized Product Quantization (OPQ) for approximate nearest neighbor (ANN) search [12], with Inverted File Indices (IVF) [20].
As proposed by Lowe [23], two features and their respective image patches are probably a match (i.e., they depict the same object or scene region in different configurations), if one is the nearest neighbor of the other within the feature space. Depending on the nature of the CBIR application, local features may be indexed in ways that use only the feature space and ignore or underutilize the scale, orientation, or (x, y) positions of the features within the images they belong to. That is the case for bag-of-features [38] and similar approaches [28,19], which are mostly useful for tasks such as retrieving semantically similar images. In the case of retrieving near-duplicates or finding spliced objects across a dataset, though, these techniques are not enough. Hence the need for additional spatial verification steps, such as the ones proposed in this work, to ensure that the local features being matched present a geometric coherence in either their scale, orientation, or (x, y) positions. Local-feature spatial verification methods can be organized into two categories, which are described below.
Hypothesis-oriented spatial verification. Methods in this category start with a set of spatial transformation hypotheses of one image towards the other (e.g., affine transformation). As originally proposed in the RANSAC [11] algorithm, these hypotheses are iteratively generated for random samples of feature matches, and are evaluated according to the overall number of matches that are inliers (i.e., matches that comply with the hypothesis). Aiming to make the process more accurate and deterministic, Philbin et al. introduced the Fast Spatial Measure (FSM) algorithm [29], which generates one hypothesis for every single feature match. Although very accurate, the major drawback of techniques from this category is the large runtime they demand, which is a quadratic function of the number of features (as we show through experiments in Fig. 4).
Hough transform-based spatial verification. Methods from this category start with Hough transforms [8,2] and the computation of histograms for their parameters, where each bin quantifies the number of agreeing feature matches. Lowe [23] proposed the adoption of four-parameter Hough transforms, computing bins with respect to the product of (i) x and (ii) y coordinates, (iii) scale, and (iv) orientation of the features. The largest histogram bin is then chosen to select a better and potentially reduced set of feature matches, prior to applying RANSAC on them. Aiming to speed up up the overall process, Avrithis and Tolias later introduced the Hough Pyramid Matching (HPM) strategy [1], which employs a hierarchical voting strategy to recursively split pairs of feature matches into bins in a top-down fashion (from coarser to finer correspondences), as a way to evaluate the pairwise affinities of matches without enumerating all pairs. Similar to HPM, Li et al. also suggested the evaluation of pairs of feature matches to develop their Pairwise Geometric Matching (PGM) strategy [21]. However, they proposed to use coarser (and therefore faster to verify) two-parameter Hough transforms, relying only on the orientation and scale change between the compared images. This indeed guarantees a significant speed-up in the spatial verification process, as we show through experiments reported in Fig. 4.
Another approach worth mentioning is the one proposed by Shen et al., namely Spatially Constrained Similarity Measure (SCSM) [36]. Although this one also makes use of four-parameter Hough transform quantization to enumerate candidate spatial transformations, its difference relies on the method to select the best transformation. By demanding the establishment of a bounding box over the features of the query object before performing the retrieval task, the algorithm uses the box center to measure the quality of the candidate transformations. Thus, the best transformation is the one that, after its application, best preserves the spatial relations among the feature positions and the box center.
Lastly, Schönberger et al. introduced the Vote and Verify (VaV) [34] method, where HPM is used to compute votes across the Hough transform hierarchy, prior to verifying transformation hypothesis for only the most voted bins.
Putting the proposed method in context with prior work. Our method belongs to the latter category of spatial verification techniques and is agnostic to the chosen local features and feature indexing approach. When compared to the literature, the novelty of this work comprises, besides the unique combination of strategies for the task at hand: • Inspired by SCSM [36], the use of match-set-wise centroids to evaluate the quality of the feature matches, without the need for selecting bounding boxes of interest in the query ahead of retrieval time. These centroids are calculated in a novel way (see Eq. 2). • Inspired by PGM [21], the use of a coarse, fast, but still accurate two-parameter Hough transform quantization, which contrary to PGM, relies on the x and y position coordinates of the matched features, instead of scale and orientation. • A novel image retrieval score (OS2OS score, see Eq. 11), which is based on two complementary measures of object-level image matching quality (namely, object centrality, and angle coherence), and allows for spatial verification while ranking images.
In the following, we detail each step of the proposed solution, as well as provide discussion on the reasons and advantages of adopting each one of the above novel aspects.

Objects in Scene to Objects in Scene (OS2OS) Score
Our proposed spatial verification method for image retrieval can be explained in five steps.
Step 1: Local feature affinity. Images are described through local feature vectors and their respective geometric data, namely (x, y) location, scale, and orientation angle. Let Q be the set of all features extracted from the query, as depicted in Fig. 2 (i), and D be the set of all features extracted from a target image database, as depicted in Fig. 2 (ii). For a particular query feature q i ∈ Q, with i = {1 . . . |Q|}, we compute the K nearest neighbors d j ∈ D in the feature space only, ignoring the images they come from. As a result, q i participates in K matches A score S for a given match m ij that can express the affinity between q i and d j is calculated via the L 2 -distance and the rank-adaptive scoring outlined in [18]: where φ is a fixed rank position of reference (usually K/2).
Step 2: Image-pairwise centroid calculation. Take an image P from the database that shares content with the query. There might be a set of feature matches between them, whose incident locations (x, y) onto the query should give a rough indication of the shared object's location within Q. Therefore, if we calculate the center of these P -wise match locations on the query, we find a point that is generally near a potential object of interest, serving as an estimation of its centroid c (see Fig. 2 (iv)). Let M be the set of feature matches m k shared between P and the query, with k = {1 . . . |M |}, and let Q m ⊆ Q be the set that contains only the query features that have a match to P . To obtain c, we apply the straightforward solution of using the Euclidean center of the query features q k ∈ Q m . Nevertheless, aiming to consider the quality of the matches while computing c, and to deal with spurious matches, we also weight the added features according to their affinity scores S(m k ) (see Eq. 1) associated with the features of P : where L(q k ) is the (x, y) location of the k-th feature q k ∈ Q m , and m k ∈ M is the respective k-th feature match between the query and P . The motivation for this is that the more similar two matched features are (i.e., the higher their value of S(.)), the more they contribute to the position of c. This strategy reduces the Hough voting noise problem described in [34], as shown via supplemental ablation experiments (see Supp. Mat.), where we report the decrease in performance due to the absence of centroid computation.
Step 3: Centroid-relative feature projection. Given the centroid c representing the query feature locations q k ∈ Q m , and their respective matched features p k ∈ P , we can estimate the translation, rotation and scaling transformation from the space of image P towards the query space, for each match m k = (q k , p k ), with k = {1 . . . |M |}: where θ(.) and σ(.) respectively provide the angle and the scale associated with the location L(.) of either q k or p k features. These transformations describe where each query feature expects the object region to be, similar to an "Rtable" of the general Hough transform [2], with the novelty that we only consider the (x, y) feature coordinates. The advantage of doing so is twofold: (i) the Hough space is twodimensional (given x and y) instead of four-dimensional, making computations faster; (ii) the Hough space maps directly to the query space, making the localization of shared objects straightforward. By applying each transformation to the (x, y) location of its respective matched feature L(p k ), we subsequently build a voting space V k for each p k ∈ P : The process of computing the voting space is shown in Fig. 3. Observe, through item (iii), that all p k features contribute to the centroid, except for the spurious p 5 one.
Step 4: Density-based feature clustering. We calculate a distinct centroid c for every image P from the database that presents matches with the query. This allows us to transform all matched feature vectors, regardless of the image they come from. After all matched feature locations have been transformed to their respective two-dimensional Hough vote space, as depicted in Fig. 2 (vi), a densitybased clustering determines which sets of feature matches are structurally consistent with the query. Instead of using a computationally intensive algorithm such as DBSCAN [9] for clustering millions of points, we apply a linear-time Figure 3. OS2OS voting space computation. (i) Translation vectors are calculated relative to a computed centroid c in Q. (ii) Translations are applied to matching features in P . (iii) Vectors are rotated by the angle differences a k to account for object rotation. Notice that the p5 spurious match votes incorrectly and therefore will not contribute to the score. (iv) Votes are binned using (x, y) coordinates only. (v) A density map is calculated, which conveniently coincides with the query space, providing visualization of matched object regions.
grid-based quantization to each V k , to find the approximate clusters of highest vote density. Because we assume, for simplicity sake, cluster morphologies to be roughly circular, we employ a square sliding window to quantize and bin V k values. The size ws of the quantization window varies according to the resolution w × h of image P : where b is a scaling factor, and 0 prevents ws from becoming too large. The magnitudes of projection vectors ||T k || are proportional to the resolution of image P . As ||T k || increases, small errors in the scale normalization and rotation transforms (Eq. 4) are amplified, resulting in lower density clustering. Unlike HPM [1], which accounts for this phenomenon by utilizing a hierarchy of window sizes for assigning votes to clusters, we employ a single window size determined by a sub-linear mapping of the image's resolution (Eq. 6). This is accomplished through : it constrains the maximum allowable vote cluster area to grow sub-linearly with the resolution of the image. The values of b and are empirically determined via an ablation study, included in the Supp. Mat.
Step 5: OS2OS filtering and scoring. By relying on the value of ws computed for an image P , the respective votes V k are quantized into cluster bins (see Fig. 3 (iv)): We consider that all V k values sharing the same bin(.) value belong to the same matched object. Let O be the set of transformed features from database image P , which participate in matches between P and the query, and whose respective votes happened to belong to the same bin according to Eq. 6. The meaning of this is that the O features likely belong to a unique object shared by the images. Subsequently, we enforce a strict one-to-one matching constraint within each O. Then, to express their affinity of features within the filtered O, we propose two novel main scoring mechanisms inspired by [41], each with a particular purpose. The first, called the Centrality Score (CS), measures the centrality of the features and is calculated as the sum of location differences between the elements o k ∈ O and their average (a.k.a., central) elementō, with k = {1 . . . |O|}: where L(.) is, again, the (x, y) location of the given feature, and pdf (.) is a function that augments the available data through a probability density function (see Fig. 3 (v)): In addition, CS is normalized by the cardinality of O, as a way to balance clusters of small objects containing few features with respect to large objects that contain many. The second mechanism is the Angle coherence Score (AS), which aims at measuring the uniformity of angles within the features of O. Consider the feature-wise difference of angles a k expressed in Eq. 4, and let A be the set of difference of angles a k computed for each feature of O. Features from keypoints belonging to a single rigid object are expected to present similar values of a k , while erroneously aggregated unrelated features are expected to present more diverse results. For that reason, we rely on the inverse of the standard deviation of A, stdv(A), to compute the angle uniformity (shifted to avoid division by zero): Finally, the OS2OS score is given by CS and AS: which lays between 0 and 1 and rewards only clusters in which each point has been transformed similarly. The logarithmic scalar log |O| penalizes clusters with very low numbers of votes, pushing their score towards zero.

OS2OS Score Evaluation
Datasets. Oxford 5k and Paris 6k. Oxford 5k [29] and Paris 6k [30] are smaller popular datasets for image retrieval performance evaluation. These two datasets contain hundreds of true positive matches per query, rather than similar sized datasets that contain only four or five [26,17].
Google-Landmarks. As a benchmark for DELF features [27], Google released the 2018 Google-Landmarks dataset [14] and subsequent evaluation protocol [13]. This dataset contains 1, 098, 461 images with 117, 703 queries in the testing protocol. While groundtruth data for the test set has not yet been released, 1, 212, 281 weak labels for the training set are available. The training set contains a total of 14, 951 unique landmarks, with each landmark having an average of 80 instances.
NIST Media Forensics Challenge 2018 (MFC2018). As part of the yearly Media Forensics Challenge run by NIST, the MFC2018 dataset [25] was constructed specifically for the task of finding related manipulated images in a forensics context. This is a large dataset, 3.1TB in size, containing 1, 031, 080 images and 3, 300 queries. Many of these queries are composites, with groundtruth results provided in the MFC2018 testing protocol. The dataset also provides groundtruth as to whether a database image contributes a majority of its content (e.g., Fig. 1 i), or only a particular object (e.g., Fig. 1 ii) to the query.
Reddit. The Reddit dataset [7] introduced by Moreira et al. [24] is collected from the Reddit Photoshop Battles [33] subreddit. Each case provides the original image and all subsequent manipulated versions of the original. This dataset contains 51, 245 images from 185 different Photoshop battles. To utilize this dataset for the OS2OS task, we generate a query set of one image chosen at random from each of the 185 cases. The rest of the images from the same battle thread are considered as the groundtruth for relevant images to these queries. We will make this new groundtruth available upon the publication of this paper.
Features. For each dataset, we report performance using both handcrafted SURF [3] and learned DELF [27] features. While other deep image representations have been proposed for image retrieval [16,42,15,32], some deep local feature  descriptors such as LIFT [22] are too slow (see Table 1) for practical use, as also observed in [27]. Other fast global descriptors such as MobileNet [16] are not applicable to the localization of multiple objects. Our region-wise matching approach requires local descriptors to match coherently within a certain spatial location, which cannot happen with a single global MobileNet descriptor.
SURF keypoints are detected in a distributed modality (DSURF), as proposed in [24]. Keypoint extraction of DSURF features automatically provides the location, scale, and rotation data needed for computing the OS2OS score. For all datasets, we extract a maximum of 5, 000 64dimensional DSURF features per image, along with their respective geometrical data. DELF features are used in similar way to DSURF. Because the DELF algorithm provides only feature scale information, we use the SURF keypoint angle algorithm [3] as an extension to provide feature angles for the DELF geometric data. We performed experiments using the default parameters and model to produce 40-dimensional local features, and cap the attention model at a maximum of 1, 000 features per image.
Indexing. For experiments on Oxford 5k and Paris 6k datasets, we keep a consistent indexing backbone among spatial verification methods. To index features, we use Optimized Product Quantization (OPQ) for Approximate Nearest Neighbor (ANN) search, with Inverted File Indices and Asymmetric Distance Computation (IVFADC) [20]. Following the vocabulary hold-out protocol suggested in [40], we utilize a randomized 1% subset of Google Landmark images to train the quantization table used for Oxford 5k, Paris 6k, and Reddit datasets. Due to the large volume of images available, a randomized 5% hold-out of the Google Landmarks dataset is used to train its own tables. These tables are obtained via OPQ matrix computation [12], and used for the IVFADC centroids. OPQ training runs for 25 epochs for 2 18

Experimental Results
Here we describe and analyze the results for a series of timing experiments, as well as the experiments for each of the five datasets described in Sec. 4.

Timing and Complexity
Feature extraction timings. Aiming to focus on largescale retrieval, we performed average timing experiments over a subset of 100 images from the Reddit dataset to analyze the tractability of different feature extraction methods on CPUs. Table 1 shows these results, justifying our selection of DSURF and DELF as candidate features for further experiments. MobileNet stands for the MobileNet-v2 architecture [16], whose features were extracted from its global pool layer. Although fast, local spatial information is not native to MobileNet, and is therefore incompatible with the task of spatial verification.
Spatial Verification Timings. We also performed timing experiments against other spatial verification and ranking methods for image retrieval. Here we compared the OS2OS score against HPM [1], PGM [21], FSM [29], SCSM [36], plain RANSAC [11], and VaV [34]. We extracted 5, 000 SURF features from a query image and varied the K retrieved nearest neighbors for each query feature from 0 to 400. For these experiments we averaged timings across 10 query images from the Google-Landmarks dataset. Standard deviations were calculated, but were too small to be plotted. While RANSAC is known to provide spatial verification for an arbitrary number of features in quadratic time [21], HPM and PGM are proven to be linear [1,21]. As can be seen in Fig. 4, OS2OS scoring is faster than HPM, PGM, and VaV, ranking nearly 400 images with 1.8 million features in only 10 seconds. All methods used Precision-recall curves for the Google-Landmarks dataset. As it can be observed, the usage of spatial verification through the OS2OS score boosts both SURF-and DELF-featurebased image instance retrieval. the same 2.7GHz single-core environment.

Image Retrieval
Oxford 5k and Paris 6k. The small-scale experiments performed on the Oxford 5k and Paris 6k datasets are meant to show that the OS2OS scoring algorithm, while designed for object-level spatial verification, is general enough to provide benefits for typical image retrieval. We compare our approach against HPM [1], PGM [21], VaV [34], and plain usage of SURF and DELF features (without spatial verification). Mean Average Precision (MAP) scores are reported in Table 2. We find that the OS2OS score significantly improves both DSURF and DELF features, suggesting that the provided spatial constraints work satisfactory for global geometric verification for instance retrieval. Additionally, we see a much larger performance improvement for DSURF, which suggests the OS2OS score helps mitigate erroneous matches from the bursty nature of SURF. Overall, the OS2OS approach is comparable to other approaches in the literature. Of noteworthy significance is the fact that the OS2OS algorithm required no bounding boxes, still performing comparably to other spatial methods. We additionally examined scores from RANSAC [11], SCSM [36], and FSM [29] for Oxford 5k, but the results were inferior to the better performing approaches in Table 2.
Google-Landmarks. This experiment shows that the OS2OS score generalizes to the instance retrieval task, as well as showcases the algorithm's scalability in the presence of many distractors. Because annotations for the index or test sets have not been released at the time of this writing, we performed our study utilizing the training set, which contains over 1 million images and provides landmark annotations. We selected 1, 000 landmarks at random for retrieval, sampling one query per landmark. Finally, we utilized the modified precision and recall measures described  in [27] to report results. Fig. 5 shows that DSURF augmented with the OS2OS score improves significantly, while also providing minor improvements to DELF.
NIST MFC2018. Unlike the experiments described thus far, the MFC2018 dataset is comprised of manipulated images. Query images from the dataset's retrieval protocol may or may not contain regions from multiple sources within the image database. We utilized the groundtruth relationship graphs to determine which images donate small objects to their respective queries. Using this data we can generate recall curves exclusively for donor image retrieval (namely, donor recall). We report both total recall scores and donor recall scores in Fig. 6. While the OS2OS score shows good boosts in total recall, we see that donor recall is more significantly improved, indicating that the OS2OS score is capable of balancing geometrically coherent matches of image regions from small donors with global matches from backgrounds.
Reddit. The Reddit provenance dataset has proven to be a difficult challenge [24]. In Table 3, we see a significant increase in retrieval performance (nearly 10% for SURF and nearly 5% for DELF) across the board, with vastly superior results when compared to VaV [34]. The near-baseline performance of VaV suggests that global spatial verification methods are not fully adequate to solve the OS2OS problem. Further, Fig. 7 shows qualitative retrieval results using OS2OS scoring, along with the object vote maps from each retrieved match. These results highlight the OS2OS score's ability to localize and appropriately weight small objects from a database image to small objects within the query, without the need for bounding boxes.

Parameter Ablation
To examine the contribution that different parameters from Sec. 3 provide for both total and donor recall metrics (see Fig. 6), we perform an ablation study using the MFC2018 dataset. We remove and re-introduce the CS score (Eq. 8), AS score (Eq. 10), logarithmic scaling (Eq. 11), and centroid calculation (Eq. 2), to empirically show that each component plays an important role in increasing the performance of the algorithm. As a consequence, the best configuration is indeed the one that uses all of these features. We also vary the bin size ws in Eq. 6, to illustrate its effect on filtering and scoring performance. These additional results are included in the Supp. Mat., due to space constraints.

Conclusions
Retrieving images that share small regions in a complex composite scene is a challenge for most image retrieval approaches. In this paper, we proposed an inexpensive scoring technique that is based on the better utilization of pretrained feature extractors and indexing techniques to yield geometrically consistent localized scores. An advantage of the technique is that it is learning-free, and works as an addon to existing feature description methods. It provides a way to include spatial verification while performing matching in a large feature space. It is optimized to be efficiently executed on CPUs without the need for high-end GPUs.
In experiments, the proposed approach improved recall for the retrieval of images for difficult emerging problems such as cultural analytics and image forensics. As with most computer vision algorithms, the proposed approach still struggles on challenging datasets obtained from the web with different styles of content correspondence. Although performance improves with the proposed scoring, retrieval for specific applications such as tracking memes on social media is worthy of additional research consideration -especially as such content grows in popularity.