A Benchmark on Tricks for Large-scale Image Retrieval
Byungsoo Ko Minchul Shin Geonmo Gu HeeJae Jun Tae Kwan Lee Youngjoon Kim
cs.CV cs.IR cs.LG










A Benchmark on Tricks for Large-scale Image Retrieval
    Byungsoo Ko These authors contributed equally to the work. 

NAVER/LINE Vision

kobiso62@gmail.com
Minchul Shin 

Search Solutions Inc.

min.stellastra@gmail.com
Geonmo Gu  Heejae Jun  Taekwan Lee  Youngjoon Kim 

NAVER/LINE Vision

{geonmo.gu, heejae.jun, taekwan.lee, kim.youngjun}@navercorp.com

    December 30, 2023
==============================================================================================================================================================================================================================================================================================================

empty




Many studies have been performed on metric learning, which has become a key ingredient in top-performing methods of instance-level image retrieval.
Meanwhile, less attention has been paid to pre-processing and post-processing tricks that can significantly boost performance.
Furthermore, we found that most previous studies used small scale datasets to simplify processing.
Because the behavior of a feature representation in a deep learning model depends on both domain and data, it is important to understand how model behave in large-scale environments when a proper combination of retrieval tricks is used.


In this paper, we extensively analyze the effect of well-known pre-processing, post-processing tricks, and their combination for large-scale image retrieval.
We found that proper use of these tricks can significantly improve model performance without necessitating complex architecture or introducing loss, as confirmed by achieving a competitive result on the Google Landmark Retrieval Challenge 2019.







§ INTRODUCTION

With recent advances in metric learning techniques, there have been active studies <cit.> that aim to improve the model performance on image retrieval.
Most previous methods have focused on learning a good representation by carefully designing loss functions <cit.> and architecture <cit.>, and evaluated their performance against relatively small-scale datasets such as Oxford5k <cit.>, and Paris6k <cit.>.
These datasets are well-structured, reliable, and sufficiently small to be processed easily.
However, high performance on a small dataset does not guarantee that the discovered model is generalized.
Although a few studies <cit.> have attempted to investigate large-scale image retrieval using datasets such as Oxford105k <cit.> and Paris106k <cit.>, we found that most of the public large-scale datasets are not truly large; instead they typically consist of a small number of query and index images, and a large number of irrelevant images used as distractors.
Moreover, we have seen few works that evaluate performance against a dataset that includes more than 100K queries and is actually large-scale in terms of both query and index size.
The reason is simple: querying more than 100K images from among a large number of indexed images is extremely time-consuming and computationally expensive.

On the other hand, the tricks <cit.> used during pre-processing and post-processing also have a significant impact on retrieval performance.
F. Radenovic et al. <cit.> reported enormous improvement in performance by applying several retrieval tricks before and after the main processing.
Despite the importance of such tricks, we found few papers that discuss the best-performing pre-processing and post-processing tricks, particularly for large-scale environment.

In this paper, we aim to analyze how retrieval performance varies on large-scale datasets when different types of pre-processing and post-processing tricks are used in combination.
To do so, we design a very simple model that uses no difficult engineering (such as network surgery) and analyze the effect of the well-known retrieval tricks on the performance in a stepwise fashion.
Extensive experiments were conducted for all possible combinations of tricks and models with various hyper-parameters, as shown in Figure <ref>.
We found that proper usage of well-known retrieval tricks can significantly improve the overall performance even when using a simple inference model.





  
Main contributions. Our contribution is two fold:
(1) We analyze the effect of pre-processing, post-processing tricks, and their combination on large-scale image retrieval with extensive experiments.
(2) We show that competitive improvement can be achieved by properly combining well-known retrieval tricks. Our pipeline was ranked 8-th place in the Google landmark retrieval challenge 2019 <cit.>.









§ PRE-PROCESSING TRICKS

We used two large-scale datasets for the experiments: Google landmark dataset (GLD) v1 <cit.> and GLD v2 <cit.> from the 2018 and 2019 Google landmark challenges, respectively.
Detailed statistics for the datasets are shown in Table <ref>.
When dealing with large-scale datasets, several unexpected problems can arise.
The first issue is how to eliminate noise from such large-scale datasets.
As a dataset becomes larger, more noise which functions as distractors could be included.
Therefore, noise should be carefully eliminated because the quality of training data significantly affects the model performance <cit.>.
The second issue is how to quickly evaluate model performance through enough trials to perform a large number of experiments.
Different from other famous landmark datasets <cit.>, the GLD datasets contain both more than 0.7 million index images and more than 0.1 million query images.
This amount of data requires a significant amount of time and memory to conduct even a single evaluation.
In this section, we describe how to circumvent these issues by removing noise images and constructing a small-scale validation set.






 §.§ Dataset Cleaning for Training

By cleaning the noise from the training set, we aim to maximize inter-class variation and minimize intra-class variation.
To resolve this without supervision, we used a clustering technique, the density-based spatial clustering of applications with noise (DBSCAN) <cit.>, which can be replaced by any clustering algorithm <cit.>.
Based on the generated clusters, three different types of clean datasets (TR1, TR2, and TR3) were constructed.
The detailed procedures for constructing each dataset are described below.





  
TR1.
We noticed by visual inspection that the training set of GLD v1 is clean and reliable, so we used the dataset as is for training.
To obtain a semi-supervised learning effect <cit.>, we added virtual classes to the training set.
These virtual classes are the clusters from the test and index sets of GLD v1.
First, we trained a baseline model using GLD v1 and extracted features of the test and index set of GLD v1.
Then, DBSCAN was applied to generate clusters, where each cluster was assigned as a new virtual classes.
We call the result TR1 for clarity.





  
TR2.
In the index set of GLD v2, there are many distractor images that are not a landmark, such as documents, portraits, and nature scenes.
We aimed to use these noises for the training phase so that the model could increase the distance between real landmarks and noises in an embedding space.
For this, we performed the same procedure of clustering but also picked several distractor clusters as virtual classes.
These distractor classes were combined with TR1, and we call the combined dataset TR2.





  
TR3.
The training set of GLD v2 has more classes and images than GLD v1 does.
At the same time, it contains a large number of noise classes and images.
To address this, we first removed the nature scenes using a simple binary classifier trained on the Open Images Dataset <cit.> and the iNaturalists Dataset <cit.>.
Then, the images in each class were clustered so that the noise could be excluded as outliers.
When multiple clusters were found in a class, we chose the largest cluster and discarded the others.
Moreover, the classes from the training set of GLD v2 that were duplicated in TR2 were also excluded by querying the images of each training class.









 §.§ Small-scale Validation

Saving time for each evaluation run is important because it determines how many times we can run trials to validate our hypotheses.
Furthermore, the validation set should reflect the characteristics of the test data as much as possible to prevent misguided interpretation.
To obtain substantially smaller dataset, we sampled about 2% of the training images from GLD v2 and divided the sample into test and index sets.
We included a virtual class from a noise cluster because the test set of GLD v2 includes a number of distractor images.
In this way, we expect that the distribution of the validation set will be similar to the test and index set of GLD v2.
We report the validation score along with the submission score because the best performing hyper-parameters of each model were explored on the basis of the validation score.




 §.§ Experimental Results

The Figure <ref> shows an example of how the noisy ground-truth labels have become clean after the clustering.
The raw dataset includes images taken from inside, outside, and even partial viewpoints from within the same landmark.
These kinds of datasets with large intra-class variation may interfere with learning proper representations in the model, especially when a pair-wise ranking loss is used.
Moreover, images of nature scenes also make the training process hard as they have a little iter-class variation.
After refining the raw dataset by choosing a big cluster and removing distractors, we obtained a cleaned dataset.

We performed experiments with a N-pair + Angular model by differentiating the training set and validated each performance.
The input size was 256 × 256 px for the training phase, 416 × 416 px for the inference phase, with 1024-dimensional embedding.
As shown in Table <ref>, training with TR1, which contains virtual classes from the test and index sets, improves the model performance by using unlabeled data when the original training set is not helpful anymore.
The model trained with TR2 gives performance similar to the model trained with TR1 because the number of data and classes is not noticeably different.
Because the training set of GLD v2 is quite noisy, we could not train a model from the raw dataset.
Using TR3, which includes a cleaned training set from GLD v2, further improved the performance.
Overall, both validation and submission performance were improved by clustering the data more finely and including more images.
The experiments also showed that the validation set is suitable for use as the performance on validation and submission have similar patterns.



§ LEARNING REPRESENTATIONS

In many cases, state-of-the-art performance is obtained by using a novel design of architecture or loss function <cit.>.
Although such methods may show comparable results on GLD, we intentionally designed a very simple model because we are more interested in the effect of pre-processing and post-processing tricks on large-scale datasets than in the inference model itself.
Nevertheless, it is still interesting to figure out which combination of commonly used pooling methods and objectives work best for the task.
Therefore, we trained multiple models with different types of pooling methods and loss functions expected to be helpful for the feature ensemble in post-processing.



 §.§ Pooling

Despite the simplicity of implementation, the pooling method on the feature map from the last layer affects the model performance fairly strongly <cit.>.
For this reason, in <cit.> extensive experiments were performed to find the optimal combination of pooling methods.
However, here, we found that the best pooling method depends on the domain.
Ultimately, three different methods (SPoC <cit.>, MAC <cit.>, and GeM <cit.>) were used for training in this paper.








 §.§ Objectives

We designed two types of objectives by combining two well-known loss functions.
We expect that differentiating the objectives will enrich the variation of the model representation, which is helpful for the feature ensemble.





  
Xent + Triplet.
Triplet loss is one of the simplest ranking loss, but we found it offered comparable performance to other loss functions when combined with a classification loss such as cross-entropy (Xent) loss <cit.>.
In this case, the number of instances becomes the number of classes to classify, and the triplet pair is sampled from the given minibatch using hard example mining.





  
N-pair + Angular.
N-pair + Angular loss function is a combined form of pair-wise ranking losses: N-pair <cit.> and Angular <cit.>.
Angular loss can be easily integrated into N-pair loss, and we expect that combining the distance-based loss with the angle-based loss will renders the objective function more robust against large variations in feature maps <cit.>.



 §.§ Training a Single Model

On the basis of the aforementioned pooling methods and objective functions, we design a very simple model by replacing the components in Figure <ref>.
We used ResNet <cit.> applied tricks from Xie et al. <cit.>, SE-ResNet <cit.>, and SE-ResNext <cit.> as a backbone to enhance the structural variation.
A fully-connected layer and l2-normalization are used after pooling the output feature maps.
The number of possible combinations to produce a single model comes to backbone(6) × pooling(3) × objective(2)=36 in total.



 §.§ Experimental Results

We trained multiple models with various combinations of training data, input size, backbone, pooling method, and objective.
For the N-pair + Angular model, we used a 256 × 256 px input size for the training phase and a 416 × 416 px input size for the inference phase.
For the Xent + Triplet model, the input size was 320 × 320 px for the training phase and 640 × 640 px for the inference phase.
The output dimensionality for both models was 1024.
The performance of the top 9 models are reported in Table <ref>.





  
Pooling.
The performance of each pooling method can differ with the characteristics of dataset and model <cit.>.
Within the three pooling methods, MAC showed the worst performance among all model combination.
The best performing pooling methods differed with the objective.
SPoC showed the best performance for N-pair + Angular models, while GeM was the best pooling method for Xent + Triplet models.





  
Objectives.
As shown in Table <ref>, models with two different objectives had similar performances but different tendency when it comes to the training data.
Unlike the N-pair + Angular models, the Xent + Triplet models showed the best performance with TR1.
With TR3, the Xent + Triplet model could not be trained properly owing to fluctuation of the Xent loss.
This can be because the Xent loss is sensitive to the quality of the dataset, as it may obtain a small number of duplicated classes during the refinement process.





  
Input size.
We conducted experiments with an index-2 model in Table <ref> by varying input size at the feature extraction step.
The result is shown in the Figure <ref> (a).
It shows that performance rises as the input size increases as larger input sizes generate bigger feature maps in the convolutional neural network (CNN) models, which thus contain richer information.
However, the performance does not keep increasing indefinitely, starting to decrease at a certain point.






§ POST-PROCESSING TRICKS

In this section, we investigate well-known post-processing tricks for instance-level image retrieval, including feature ensemble, database augmentation (DBA), query expansion (QE), and reranking.
Even though the effectiveness of each trick itself is well-proven in many studies, we found few papers that have empirically studied how these techniques should be mutually combined to maximize the performance.
We aim to figure out the mutual influence of combining tricks in different ways, and the sections below describe the details.



 §.§ Multiple Feature Ensemble

The feature ensemble is a traditional method and the most representative technique for improving performance in many vision tasks <cit.>.
Although feature ensembles can be seen as a simple concatenation of multiple features, there exists a point that is worth to consider: what features would be the best to be combined?
Based on the single models we trained with various combinations of backbones, pooling methods, objectives, 1024-dimensional features were extracted, and a group of randomly chosen features was concatenated.
We examined how the performance varied according to the number of features concatenated.
In addition, we investigated whether the commonly used “best only” strategy, which picks the best performing features first, indeed guarantee better result in actual testing.





 §.§ DBA and QE

Database-side augmentation replaces every feature point in the database with a weighted sum of the point's own value and those of its top k nearest neighbors (k-NN) <cit.>.
The purpose of DBA is to obtain more robust and distinctive image representations by averaging the feature points with the nearest neighbors.
We perform the weighted sum-aggregation of the descriptors with weights W computed by,

    W=logspace(a, b, n),

where the logspace function generates n points between 10^a and 10^b.

Similar to DBA, query expansion, introduced by Chum et al. <cit.>, is a popular method of improving the quality of image retrieval by obtaining a richer representation of a query.
It retrieves top k nearest neighbors from the database for each query and combines the retrieved neighbors with the original query.
This process is repeated with the number of necessity, and the final combined query is used to produce the ranked list of retrieved images.
More precisely, the weighted sum-aggregation of each query is performed with weights W computed from Equation <ref>.









 §.§ PCA whitening

In the retrieval task, whitening CNN-based descriptors have been promoted <cit.> as they handle the problems arising from co-occurrence over-counting by jointly down-weighting co-occurrences <cit.>.
Typically, whitening is learned by a generative model in an unsupervised manner via principal component analysis (PCA) on an independent dataset.
We performed PCA whitening (PCA_w) with 4096-dimensional features from DBA and QE to produce 1024-dimensional features by using the implementation in the Scikit-learn API <cit.>; then, we applied l_2-normalization again.



 §.§ Reranking


Once the top k candidates were retrieved, reranking the order of the retrieved candidates could improve performance.
The influence of reranking tricks is relatively minor compared with the previously mentioned tricks in that reranking is effective only if the ground-truth images were found in the top k candidates.
Nevertheless, proper usage of reranking certainly improves performance.
We performed reranking using two distinctive methods: a graph search based on the global descriptor, and local matching based on the local descriptor.





  
Graph search. Diffusion (DFS) <cit.> is a mechanism that captures the image manifold in the feature space.
It searches on the manifold efficiently based on a neighborhood graph of the dataset constructed offline.
This method improves the retrieval of small objects and cluttered scenes in particular, which fits the dataset domain of the  Google Landmark Challenge.
The performance increase using DFS is huge, and many state-of-the-art image retrieval papers use it as the last step in maximizing the score on the benchmark dataset.





  
Local matching. We use the spatial information of images for reranking.
Given two images, The correspondence match is extracted, and the number of inliers are counted using RANSAC <cit.>.
Because performing geometric verification on all possible pairs of query and index images is expensive for large-scale data, we applied local matching to only the top kd candidates, which is the retrieved result for the global descriptor.
We used DELF <cit.> pre-trained on landmark dataset, and 1K local features were extracted from each image as described in the paper.
In the experiment, we found that unrelated images sometimes obtained more than 10 match score, which caused the performance drop.
To suppress this, we reranked the candidates only when the match score exceeded a certain threshold (σ = 50).




 §.§ Experimental Results

Based on the trained single models, we have examined the effect of the aforementioned post-processing methods.
The performance of the feature combination and each post-processing step can be found in Table <ref>.
Figure <ref> shows experiments for values of the hyper-parameters of the respective tricks.





  §.§.§ Multiple Feature Ensemble


Figure <ref> (a) shows how the performance varies according to the number of concatenated features.
We found a better result as the number of features was increased, but the gain becomes slighter with more features.
Considering the computational cost and the performance gain, we recommend using 4∼6 features for the concatenation.
We also investigated whether the “best only” strategy was an optimal way of finding the best combination of features for the ensemble.
To test this, more than 1,400 combinations of concatenated features were constructed and evaluated on the validation set, as shown in Figure <ref> (d).

The result shows that there is a correlation between the low-performance variation of the models and better performance (red line).
However, we should not entirely trust the “best only” strategy because the variance of the points (blue line) is not negligible.





  §.§.§ DBA/QE and PCA_w


For processing features with DBA, QE, and PCA, we can think of two methods, depending on which trick is used first: (i) performing PCA on the concatenated feature, followed by DBA and QE; or (ii) performing the DBA and QE on each feature first, concatenate the features, and then apply PCA.
We chose the latter as it consistently achieved better results.
Note that the result in Table <ref> are based on evaluation in this manner.

In the experiments, we found an interesting point: the tricks work differently depending on whether DBA and QE are applied to the feature earlier.
Table <ref> shows that all combinations of concatenated features show a consistent performance increase when PCA and whitening are applied after DBA and QE.
This result is incompatible with the result of not applying DBA and QE in Figure <ref> (b), which implies that dimensional reduction using PCA and whitening does worsen performance.
Similarly, we found conflicting results for the optimal feature dimensionality.
For PCA_w when DBA and QE were used, 1024 was the optimal dimensionality for output, but the same parameter value degraded the performance significantly when using features without DBA and QE, as seen in Figure <ref> (c).
Interestingly, DBA and QE enhance the quality of the feature representations, which also make them robust against dimensionality reduction.
As shown in Table <ref>, the gain from DBA and QE is largest among all tricks.
Iterative DBA and QE perform augmentation k times, but we used k=1 for both DBA and QE as it performed the best.








































  §.§.§ Reranking


Recently, the concept of detect-to-retrieve <cit.> (D2R) has been proposed, and we used the landmark detector of <cit.> to detect and crop the region of interest.
The cropped region is used for local feature extraction with DELF <cit.>, which is listed as DELF Rerank+D2R in Table <ref>.
Although DELF achieved a competitive result on the Oxford5k and Paris6k datasets, we observed very slightly increased or even worsened performance after reranking with DELF in large-scale datasets such as GLD.

We also explored DFS for reranking.
As shown in Figure <ref> (e), DFS reranking with DBA/QE improved the performance by the hyper-parameter kq, while DFS reranking without DBA/QE was not helpful.
This shows that the features found by applying DBA/QE can construct better image manifolds in the feature space for graph searches.
Furthermore, we conducted experiments by combining DFS with spatial verification (SV), which is denoted as DFS+SV.
DFS+SV replaces a pairwise similarity measure of the cosine similarity between the global descriptors with the spatial matching score of the local descriptors obtained by DELF reranking.
Table <ref> shows that DFS improves the performance, while it worsens with SV.
As the number k for k-NN graph construction was increased, the performance improved, but the additional computation slowed the process as a tradeoff.





  §.§.§ Google Landmark Retrieval Challenge


The Table <ref> shows the final result on the Google Landmark Retrieval Challenge 2019.
For the final submission, we chose combination J from Table <ref> and applied DBA and QE with k=1 on each features.
The features were then concatenated and PCA_w was applied with an output dimensionality of 1024.
Finally, the top 100 candidates were reranked using DFS+SV (NN=20K), which gave higher performance than using DFS only at this time.
Our pipeline ranked 8-th on the leaderboard by properly combining well-known retrieval tricks with simple inference models and proper use of hyper-parameters.
We did not use any complicated architecture or loss functions.
Note that our final submission score was improved after the challenge, as shown in Table <ref> and Table <ref>. 





§ CONCLUSION

In this paper, we have examined the effectiveness of pre-processing and post-processing tricks on the large-scale dataset.

The tricks such as dataset cleaning, feature ensembling, DBA/QE, PCA_w, and reranking by graph search and local feature matching were used for our pipeline.
We showed that both learning a good image representation and applying proper pre-processing and post-processing tricks are important, and those tricks can significantly boost the overall performance.

Finally, we could obtain up to 10.24 of mAP@100 increase compared to a baseline model.



ieee




