Two-stage Discriminative Re-ranking for Large-scale Landmark Retrieval

Introduction

Image retrieval is a fundamental problem in computer vision where given a query image, similar images must be found in a large dataset. In the case of landmark images, the variation between points of view and different parts of the landmark can be extreme, proving challenging for humans without deep knowledge of the landmark in question. One such complicated example is shown in Fig. 1. The Scuderie del Quirinale is very visually similar to other structures such as the Vatican obelisk and the Inco Superstack, leading to erroneous retrievals. Our proposed re-ranking approach is able to exploit labeled information from the training dataset to improve the retrieval results, even when the correct images are very visually dissimilar such as drawings, different viewpoints, diverse illumination, etc.

Instance image retrieval can be seen as the task of converting the image information into an embedding where similar images are nearby. Similar to recent approaches, we focus on learning this embedding with a convolutional neural network (CNN). We adopt a cosine softmax loss to train the neural network for the retrieval task. Afterward, instead of simply using the distance in the embedding space to find related images, we exploit the label information to perform re-ranking. Our re-ranking is based on a two-step approach. In the sort-step, a discriminative model based on $k$-NN search with soft voting which allows us to sort the initial retrieved results such that results more label-similar to the query image are given higher priority. In the insert-step, images that were originally not retrieved are inserted into the retrieval results based on the same discriminative model. This combined approach shows a significant improvement over existing approaches.

Noh et al. has recently provided a challenging dataset named Google Landmarks Dataset v1 (GLD-v1) for instance-level landmark image retrieval. For each landmark, there is a diversity of images including both interior and exterior images. Being able to identify the images without context is very challenging, and in many cases, positive pairs have a very different visual appearance. More recently, the dataset has been expanded in a second version (GLD-v2) to be more complex and challenging. We focus on the retrieval task in this challenging setting which due to being recent has not been fully explored yet.

Although the GLD-v2 dataset is a significant improvement over the previous version, consistency and quality are still significant open issues that can be very detrimental to results in the retrieval task. For this purpose, we also propose an automatic data cleaning approached based on filtering the training data. Although this reduces the dataset size and training budget, it ends up being beneficial to overall performance of the model.

To summarize our contributions, (1) an effective pipeline for high quality landmark retrieval, (2) a re-ranking approach based on exploiting label information, (3) results that significantly outperform existing approaches on challenging datasets.

Related Work

Instance Image Retrieval. Image retrieval is usually posed as a problem of finding an image embedding in which similar images have small distance, and has been traditionally done based on local descriptor based methods , including the popular SIFT , RootSIFT , and SURF . Bag-of-Words model and its variants (VLAD , Fisher Vector ) have been popular in image retrieval previous to the advent of learning-based approaches, and construct image embeddings by aggregating local descriptors. More recently, DELF has been proposed as a deep learning-based local descriptor method, which uses the attention map of CNN activation learned by only image-level annotation. See for a survey of instance image retrieval.

After the emergence of deep learning, many image retrieval methods based on deep learning have been presented. Most recent image retrieval approaches are based on deep learning . Both utilizing off-the-shelf CNN activations as an image embedding and further fine-tuning to specific datasets are popular approaches. An extension of VLAD called NetVLAD which is differentiable and trainable in an end-to-end fashion has also been recently proposed . Gordo et al. proposed using a region proposal network to localize the landmark region and training a triplet network in an end-to-end fashion.

The current state-of-the-art local descriptor based method is D2R-R-ASMK along with spatial verification . D2R-R-ASMK is a regional aggregation method comprising a region detector based on ASMK (Aggregated Selective Match Kernels) . ASMK is one of the local feature aggregation techniques. The current state-of-the-art CNN global descriptor method is that of Radenović et al. which employs an AP loss along with re-ranking methods . We construct our pipeline mainly based on latter strategy and show that by using a two-stage discriminative re-ranking approach, we are able to obtain results favorable to the existing approaches.

Retrieval Loss Functions. Instance image retrieval requires image embedding that captures the similarity well, and the loss used during learning plays an important role. Using CNN off-the-shelf embeddings has been effective for image retrieval . Babenko and Lempitsky proposed using sum-pooling of CNN activation, and Lin et al. proposed max-pooling of multiple regions of CNN activation. However, training specifically for the task of instance retrieval has shown more effective with contrastive loss and triplet loss being some of the more used losses in image retrieval . Recently, the AP loss , which optimizes the global mean average precision directly by leveraging list-wise loss formulations, has been proposed and achieved state-of-the-art results. In face recognition field, recently cosine softmax losses have shown astonishing results and have become more favorable than other losses . Cosine softmax losses impose L2-constraint to the features which restricts them to lie on a hypersphere of a fixed radius, with popular approaches being SphereFace , ArcFace , and CosFace , using multiplicative angular margin penalty, additive angular margin penalty, and additive cosine margin penalty, respectively. While contrastive loss and triplet loss require training techniques such as hard negative mining , cosine softmax losses do not and easy to implement and stable in training. We show their successes are not only in face recognition but also in instance image retrieval by comparative experiments.

Re-ranking Methods. Re-ranking is a essential approach to enhance the retrieval results on the image embedding. Query expansion (QE)-based techniques are simple and popular ways of re-ranking for improving recall of retrieval system. AQE is the first work that applies query expansion in vision field, and is based on averaging embeddings of top-ranked images retrieved by an initial query, and using the averaged embedding as a new query. $\alpha$QE uses weighted average of descriptors of top-ranked images. Heavier weights are put on as the rank gets higher. DQE uses an SVM classifier and its signed distance from the decision boundary for re-ranking. Spatial verification (SP) is a method that checks the geometric consistency using local descriptors and RANSAC , can be combined with QE to filter images used for expansion . SP can be used as re-ranking to improve precision, but it has an efficiency problem. Therefore, it is performed generally on a shortlist of top-ranked images only. HQE leverages Hamming Embedding to filter images instead of SP.

Diffusion is major manifold-based approach, also known as similarity propagation, which can also be used for re-ranking. Many diffusion approaches are proposed for enhancing the performance of instance image retrieval . Diffusion can capture the image manifold in the feature space by random-walk on $k$-NN graph. Because diffusion process tends to be expensive, spectral methods have been proposed to reduce computational cost , and Yang et al. proposes decoupling diffusion into online and offline processes to reduce online computation. EGT is a recently proposed $k$-NN graph traversal algorithm, which outperforms diffusion methods in terms of performance and efficiency.

Conventional re-ranking methods are unsupervised, which means they do not consider label information even when label information is available. In contrast, our re-ranking method can exploit label information, commonly available in many problems, and shows excellent performance in landmark retrieval tasks.

Method

Our approach consists of training an embedding space using a cosine softmax loss to train a CNN. Afterward, retrieval is done based on $k$-NN search which is corrected and improved using two-stage discriminative re-ranking.

Our model is based on a CNN that embeds each image into a feature-space amenable for $k$-NN search. Our model is based on a ResNet-101 augmented with Generalized Mean (GeM)-pooling to aggregate the spatial information into a global descriptor.

The reduction of a descriptor dimension is crucial since it dramatically affects the computational budget and alleviates the risk of over-fitting. We reduce the dimension to 512 from 2048 by adding a fully-connected layer after the GeM-pooling layer. Additionally, a one-dimensional Batch Normalization after the fully-connected layer is used to improve the generalization ability.

Training is done using the ArcFace loss with $L_{2}$ weight regularization defined as follows

where $x_{i}$ is the input image with target class $y_{i}$, $N$ is the batch size, $W$ denotes the weights of the last layer, $W_{M}$ is the parameters of the whole network excluding the last layer, $f(x;W_{M})$ is the embedding of $x$ using $W_{M}$, $s$ is a scaling hyperparameter, and $m$ is a margin hyperparameter. We note that $\|W\|_{2}=1$ and $\|x_{i}\|_{2}=1$ is enforced by normalizing at every iteration.

2 Two-stage Discriminative Re-ranking

The diversity of images belonging to the same instance is one of the main problems in image retrieval. For example, an instance of church may contain diverse samples, such as outdoor and indoor images. These images are extremely hard to identify as the same landmark without any context. Furthermore, the visual dissimilarity makes it nearly impossible to retrieve them using only visual-based embeddings. To overcome this issue, we propose two-stage discriminative re-ranking that exploits the label information. An overview of our re-ranking approach is shown in Fig. 2.

Our proposed method is composed of an auxiliary offline step and two re-ranking stages. Suppose we have a query, an index set and a train set. The index set is a database for which we perform image retrieval and has no labels, only images. First, we predict the instance-id of each sample from the index set by $k$-NN search with soft-voting, where each sample from the index set is regarded as a query, and the train set as a database.

The score of each instance-id is calculated by accumulating the cosine similarities of the $k$ nearest samples as follows

When a query is given, its instance-id is also predicted in the same way described above. Index set samples that are predicted to be the same id of the query sample are treated as “positive samples”, and those of different id as “negative samples”, and play an important role in our re-ranking approach.

Our re-ranking method is illustrated in Figure 3 and consists of a sort-step and insert-step. The top row in the figure shows a query (in blue) and retrieved samples from the index set by $k$-NN search with positive samples shown in green and negative samples shown in red. Here, we consider images on the left to be more relevant to the query than the ones on the right. In the sort-step, positive samples are moved to the left of the negative samples in the ranking, maintaining the relative order of them. This re-ranking step can make results more reliable, becoming less dependent on factors such as lighting, occlusions, etc.

Discussion. Our re-ranking method can be applied when a train set exists and there are some overlaps of instances from the train set and a index set (database). Although conventional instance image retrieval datasets have no instance overlap between the train set and the index set to measure generalization performance of methods, it is natural to have instance overlap between them in most real situations. For example, in a potential landmark image search system, some users may upload their landmark photos with a landmark name, which can be a label. Thus, using these meta information is natural and essential to improve search results.

In the evaluation on the GLD-v2 dataset, the train set is not used. Since our re-ranking follows with the GLD-v2 evaluation criteria, we constructed the algorithm considering that the samples from the train set are not a target of retrieval. However, when considering the actual retrieval system, the train set can also be considered to be part of the database to be searched. Even in such cases, our re-ranking can be naturally expanded. Specifically, in our re-ranking, it is necessary to predict the instance-id of each sample of the index set in advance. However, the instance-ids of samples from the train set are known. Thus, we can use these instance-ids of train set samples by setting the prediction score 1.0. By doing so, our re-ranking can be executed without changing in other steps, no matter whether retrieved samples are from the index set or the train set.

Dataset

The Google Landmarks Dataset (GLD) is the largest dataset of instance image retrieval, which contains photos of landmarks from all over the world. The photos include a lot of variations, e.g., occlusion, lighting changes. GLD has three versions: v1, v2, and v2.1 and we overview their differences in Table 1. GLD-v1 which is the first version of GLD has released in 2018. This dataset has more than 1 million samples and around 15 thousand labels. GLD-v1 was created based on the algorithm described in , and uses visual features and GPS coordinates for ground-truth correction. Simultaneously, the Google Landmarks Challenge 2018 was launched and GLD-v1 was used at this challenge. Currently, we can still download the dataset, but cannot evaluate with it since ground-truth was not released. GLD-v2 https://github.com/cvdfoundation/google-landmark, used for the Google Landmarks Challenge 2019, is the largest worldwide landmark recognition dataset available at the time. This dataset includes over 5 million images of more than 200 thousands of different landmarks. It is divided into three sets: train, test, and index. Only samples from the train set are labeled.

Since GLD-v2 was constructed by mining web landmark images without any cleaning step, each category may contain quite diverse samples: for example, images from a museum may contain outdoor images showing the building and indoor images depicting a statue located in the museum. In comparison with the GLD-v1, there is significantly more noise in the annotations. The GLD-v2.1 is a minor update of GLD-v2. Only ground truth of test set and index set are updated.

Automated Data Cleaning. The train set of GLD-v2 is very noisy because it was constructed by mining web landmark images without any cleaning step. Furthermore, training with the entire train set of GLD-v2 is complicated due to its huge scale. Therefore, we consider to automatically remove noises such as mis-annotation inspired by , leading to reduction of dataset size and training budget, while avoiding adverse effects of the noise for deep metric learning.

To build a clean train set, we apply spatial verification to filtered images by $k$-NN search. Specifically, cleaning the train set consists of a three-step process. First, for each image descriptor $x_{i}$ in the train set, we search its 1000 nearest neighbors from the train set. This image descriptor is obtained by our embedding model learned from the GLD-v1 dataset. Second, spatial verification is performed on up to the 100 nearest neighbors assigned to the same label as $x_{i}$. For spatial verification, we use RANSAC with affine transformation and deep local attentive features (DELF) . If an inlier-count between $x_{i}$ and nearest neighbor image descriptor is greater than 30, we consider the nearest neighbor as a verified image. Finally, if the count of verified images in the second step reaches the threshold $\tau_{\text{freq}}$, $x_{i}$ is added to the cleaned dataset. We set $\tau_{\text{freq}}=3$ in our experiment.

This automated data cleaning is very costly due to the use of spatial verification, however, it only has to be run once. Table 1 summarizes the statistics of the dataset used in our experiments. We show the effectiveness of using our cleaned dataset through our experiments in the following sections.

Experiments

We train each network for 5 epochs with commonly used data augmentation methods such as brightness shift, random cropping, and scaling. In particular, images are randomly scaled between 80% and 120% of their original size and then either cropping or zero-padding is used to return the image to the original resolution, depending on whether the image was downscaled or upscaled. Brightness is randomly modified by 0% to 10%. When constructing mini-batches for training, the images are resized to be the same size for efficient training. This might cause distortions to the input images, degrading the accuracy of the network . To avoid this, we choose mini-batch samples so that they have similar aspect ratios, and resize them to a particular size. The size is determined by selecting tuple of width and height from $[\;(512,352),(512,384),(448,448),(384,512),(352,512)\;]$ depending on their aspect ratio.

Model training is done by using the stochastic gradient descent with momentum, where initial learning rate, momentum, and batch size are set to 0.001, 0.9, and 32, respectively. The cosine annealing learning rate scheduler is used during training.

For other approaches we compare to, we follow the settings described in their respective papers. However, we have changed some hyperparameters which would found to give non-competitive results. In particular, spatial verification (SP) follows the procedure from except for using DELF trained with GLD-v1 as the local descriptor. In AQE and $\alpha$QE , the number of retrieved results used for query expansion are set to 10 including the query itself. The $\alpha$ of $\alpha$QE is set to 3.0. SP is not used to filter samples for the construction of a new query in QE different from . For Iscen et al.’s diffusion (DFS) and Yang et al.’s diffusion (DFS) , the default hyperparameters are used. The threshold $t$ of EGT is set to $inf$. Hyperparameters of each method are tuned using the GLD-v2 Public split.

We use multi-scale feature extraction described in during test time in whole experiments. The resulting features are finally averaged and re-normalized.

2 Evaluation Protocol

We use the Google Landmarks Dataset (GLD) , $\mathcal{R}$Oxford-5K , and $\mathcal{R}$Paris-6K for experiments. GLD-v1 and GLD-v2 have three data splits: train, index and test set. The train set of GLD-v1 and GLD-v2 is used for training. Additionally, the train set of GLD-v2 is used as a train set for re-ranking. The index set and the test set of GLD-v2 and GLD-v2.1 are used for our evaluation. The index set and the test set of GLD-v1 are not used for our evaluation since we cannot obtain ground-truth of GLD-v1 and use evaluation server. Note that evaluation on GLD-v2 are performed on evaluation server of the competition page https://www.kaggle.com/c/landmark-retrieval-2019/submit and it shows only mAP@100. We report two split results, “Private” and “Public”. The Private split accounts for 67% and the Public split accounts for 33% of GLD-v2 and GLD-v2.1 respectively.

Additionally, $\mathcal{R}$Oxford-5K , and $\mathcal{R}$Paris-6K are also used for the evaluation of loss functions and dataset comparison. $\mathcal{R}$Oxford-5K , and $\mathcal{R}$Paris-6K are the revisited version of Oxford and Paris . We follow the Hard evaluation protocol .

3 Comparison with Other Re-ranking Methods

We evaluate our re-ranking method and other state-of-the-art re-ranking methods on top of our baseline in Table 2, evaluating on the GLD-v2 and GLD-v2.1 datasets. Baseline is the retrieved results by $k$-NN search using descriptors extracted by our trained model. Surprisingly, spatial verification (SP) harms the performance drastically in contrast to the common sense of instance image retrieval. After visual inspection of the results of SP, we hypothesize that this is likely caused by a large number of instances that are very similar. There are many cases where the RANSAC inlier count increases artificially due to geometrical consistency of partial region between even different instances, degrading accuracy as a result.

Experimental results show that our approach outperforms the previous re-ranking approaches on the challenging GLD dataset. Furthermore, a combination of ours and $\alpha$QE boosts the performance, and it suggests that our re-ranking method can be combined with existing re-ranking methods to further improve performance. A qualitative comparison with other approaches is shown in Fig. 4. We can see that our re-ranking can retrieve samples that have no visual clue to query. These samples are failed to be retrieved with $\alpha$QE and EGT.

4 Ablation Study

We perform an ablation study and report the result in Table 3 to validate each step in our re-ranking approach. We can see that both the sort-step and insert-step significantly improve results with respect to the $k$-NN search-only baseline.

Additionally, we show the top-3 ranked results of each step in Fig. 5. We can see that the baseline of $k$-NN search retrieves visually similar images no matter if it shows the same landmark as the query image or not. After each step, the correct images not retrieved as top rank samples due to the visual dissimilarity are more emphasized and ranked higher.

5 Comparison of Loss Functions

Table 5 shows the comparison results among loss functions when trained with GLD-v1. ResNet-101 is used as backbone network in all loss function experiments. In the triplet loss and AP loss, we use an implementation described in , and offers a state-of-the-art global descriptor model. In CosFace and ArcFace , we use a model described in Section 5.1 with a margin of 0.3. Note that we do not use supervised whitening in CosFace and ArcFace experiments for the sake of simplicity. We set the dimension of the global descriptor to 2048 in triplet loss and AP loss following the setting of , and 512 in CosFace and ArcFace.

Although it is hard to compare the loss functions fairly due to the implementation differences, CosFace and ArcFace seem to outperform triplet loss and AP loss in multiple benchmarks. CosFace outperforms to ArcFace in Private and Public set of GLD-v2. ArcFace outperforms to CosFace in the other metrics.

6 Datasets

We perform experiments to validate the influence of the training dataset. Table 6 shows the results of comparison with various dataset combination. “v1” denotes the train set of GLD-v1, and “v2” denotes the train set of GLD-v2. “v2-clean” is the GLD-v2 train set cleaned by the automated way described in Section 4. We find that training with v2 significantly increases performance with respect to v1. The result using v2-clean for training outperforms the result using v2 either with and without v1 pre-training, in spite of reducing the sample size by three. Using v2-clean with v1 pre-training gives the best results overall.

Conclusion

We have presented an efficient pipeline for retrieval of landmark images from large datasets. Our work leverages recent approaches and we propose a discriminative two-step re-ranking method that shows significant improvements with respect to existing approaches. In-depth experimental results corroborate the efficacy of our approach.

References