A Novel Feature Matching Strategy for Large Scale Image Retrieval

1 Introduction

Image retrieval has received increasing interests in recent years with the exponential growth of multimedia data on the web across the world, because there is an increasing demand in efficient indexing and retrieval of these data, especially image data. To this end, this paper considers the task of large scale image retrieval. Given a query image, our goal is to retrieve all the images containing the same object or scene from a large image dataset in real time. To perform such a research topic, a myriad of models have been proposed in the last decade. Among them, the Bag-of-Features (BoF) based method is the most popular and perhaps the most successful one. The core idea is to describe an image with a BoF representation, in the spirit of the Bag-of-Words (BoW) representation used in text retrieval [Sivic and Zisserman, 2003]. Generally, there are five basic steps in the BoF framework used for image retrieval illustrated as below, respectively:

1.1 Image Description

The BoF model starts from the extraction of salient local regions from an image and representing each local patch as a high-dimensional feature vector. For each image in the dataset, affine invariant interest regions are detected. Popular choices are MSER [Nister and others, 2006] or multiscale Hessian interest points [Philbin et al., 2007], and so on. Each detected feature determines an affine covariant measurement region, typically an ellipse defined by the second moment matrix of the region. An affine invariant descriptor is then extracted from the measurement regions, which is often described by SIFT [Lowe, 2004] or its variants rootSIFT [Arandjelovic and Zisserman, 2012].

1.2 Vocabulary Generation

Then the continuous high dimensional feature space is divided into a discrete space of visual words. This step is achieved by constructing a codebook through unsupervised clustering (e.g., k-Means algorithm [Sivic and Zisserman, 2003]). The BoF model then treats each cluster center as a visual word in the codebook. The time complexity of the k-Means algorithm is O(kN), where N is the number of feature points. Taking the time complexity into consideration, in the case of [Nister and others, 2006], a nested structure of Voronoi cells is introduced, known as Hierarchical k-Means (HKM), which reduces the time complexity to O(N log k). In [Philbin et al., 2007], it shows that this reduced time complexity could also be achieved by replacing the nearest neighbour search of k-Means by a kd-forest approximation. The experiments of [Philbin et al., 2007] demonstrate that vector quantization obtained by this Approximate k-Means (AKM) is superior to HKM. Other improved methods include building super-sized vocabulary [Zhang et al., 2013] and making use of the active points [Wang et al., 2012], etc.

1.3 Feature Quantization

Usually, hundreds or thousands of local features are extracted from an image. To reduce memory cost and speed up image matching, each SIFT feature is assigned to one or a few nearest centroids in the codebook via Approximating Nearest Neighbor (ANN) algorithms [Philbin et al., 2007]. However, this process suffers from significant information loss from a 128-D double vector to a 1-D integer. One of the crucial concerns of the BoF model lies in its feature matching between images, wherein two descriptors are assumed to match if they are assigned the same quantization index, that is, if they lie in the same Voronoi cell. This strategy is called Hard Assignment (HA), which reduces the discriminative power of the local descriptors greatly. To reduce quantization error, J´egou at al. propose Multiple Assignment (MA) in [J´egou et al., 2010], which assigns a descriptor not to only one but to several nearest visual words. And Soft Assignment (SA) is proposed by [Philbin et al., 2008], which maps a highdimensional descriptor to a weighted combination of visual words. MA and SA reduce the quantization error to some extent. Whilst, a large amount of similar approaches (e.g., Locality Constrained Linear coding (LLC) [Wang et al., 2010], the Fisher Vector (FV) [Perronnin et al., 2010] and Vector of Locally Aggregated Descriptors (VLAD) [Arandjelovic and Zisserman, 2013]) are also employed in large scale image classification. Another recent trend includes designing codebook-free methods [Zhou et al., 2014] for efficient feature quantization. In this work we present a novel feature matching strategy based on SA, called local-restricted Soft Assignment (lrSA), in which a new feature matching function γx↪y to reformulate SA instead of φx↪y is introduced.

1.4 Feature Fusion

Since the SIFT descriptor used in most image retrieval systems only describes the local gradient distribution, feature fusion can be performed to capture complementary information. For example, Zheng et al. [Zheng et al., 2014a] propose a coupled Multi-Index (c-MI) framework to perform feature fusion at indexing level. Wengert et al. [Wengert et al., 2011] embed local color feature into the inverted index to provide local color information. To perform feature fusion between global and local features, Zhang et al. [Zhang et al., 2012] combine BoF and global features by graph fusion and maximized weighted density, while co-indexing [Zhang et al., 2013] expand the inverted index according to global attribute consistency.

1.5 Indexing Search

Finally, images are ranked using various indexing methods and Term Frequency-Inverse Document Frequency (TF-IDF) weights in real time. The inverted index [Sivic and Zisserman, 2003] significantly promotes the efficiency of BoF based image retrieval. Motivated by text retrieval framework, each entry in the inverted index stores information associated with each indexed feature, such as image IDs [Qin et al., 2013] and binary features [J´egou et al., 2008], etc. Recent state-of-the-art works include [Zheng et al., 2014a] "couple" different features into a multi-index.

Of all the above five steps, feature quantization is the core component, which greatly influences image retrieval in terms of both accuracy and speed. Our work in this paper makes such a timely improvement. The rest of the paper is organized as follows. After a brief review of BoF framework, Hard Assignment, Multiple Assignment and Soft Assignment will be revisited in Section 2. Our contributions, the proposed local-restricted Soft Assignment strategy and image retrieval framework, will be introduced in Section 3. In Section 4, we demonstrate the experimental results of our method on five public datasets. Finally, conclusions are drawn in Section 5.

2 RelatedWork

In this section, we will provides a formal description of the Hand Assignment, Multiple Assignment and Soft Assignment strategies.

2.1 Hard Assignment Revisit

For a single vocabulary [Sivic and Zisserman, 2003; J´egou et al., 2010], a quantizer qh is formally a function as follows:

that maps a descriptor x 2 Rd to an integer index. The quantizer qh is often obtained by performing k-Means clustering on a learning set. The quantizer q(x) is then the index of the centroid closest to the descriptor x. In this scenario, we denote the matching function fqh between two features x and y as:

where q(·) denotes the quantization function mapping a local feature to its nearest centroid in the codebook, and δq(x)↪q(y) is the "Kronecker delta function":

Intuitively, two image descriptors are assumed identical if they are assigned to the same visual word, namely, if they lie in the same Voronoi cell. On the other hand, two features assigned to different Voronoi cells are considered totally different. In other words, infinite if assigned to the same visual word, and zero otherwise. There is one and only one nonzero coding coefficient as shown in Figure 1 (a). However, the quantizer significantly reduces the discriminative power of the local descriptors.

2.2 Multiple Assignment Revisit

To address the problem induced by Hard Assignment, Multiple Assignment is proposed by [J´egou et al., 2010], which assigns a descriptor to i nearest visual words. A quantizer qm is formally a function as follow:

that maps a descriptor x 2 Rd to i (i > 2) integer indexes which are nearest to x instead of only one integer index in [Sivic and Zisserman, 2003], where k is the number of visual words defining the quantizer. The quantizer qm is often obtained by performing k-means clustering on a learning set too. In this scenario, the feature matching function fqm is defined as:

where T is a predefined threshold value and N = card(A \ B), A and B is the collection of the i nearest visual words to the descriptor x and y, respectively. card(·) is a function to obtain the number of the collection. As shown in Figure 1 (b), descriptor is assigned to six nearest visual words, two descriptors x and y from different images are assumed to match if they satisfy N > T . We can obtain from Figure 1 (b) obviously, N = 4, namely, v1↪ v2↪ v3 and v4. If T is predefined 6 4, then we deem the two descriptors x and y is a good match.

2.3 Soft Assignment Revisit

Philbin et al. [Philbin et al., 2008] consider the distance dxvi from the descriptor point x to the cluster center vi. Then the quantizer qs is formally a function as follow:

the matching function of two descriptors x and y is now updated as fqs (x↪ y) = φq(x)↪q(y), and

where the distance dx0 and dy0 to the nearest centroid is used to filter centroids for which the distance to the descriptor is above ↵dx0 and ↵dy0 (typically, ↵ = 1.2 according to [J´egou et al., 2010]). This criterion removes improbable matches and reduces the number of cells to explore. Figure 1 (c) is the illustration of SA strategy. In Figure 1 (c), we define i = 6. While, 4 nearest neighbors are considered for descriptor x, and 6 nearest neighbors are considered for descriptor y. In this case, N = 2 is different from Figure 1 (b) where N = 4. SA strategy further reduce quantization error based on MA strategy.

3 The ProposedMethod

In this section, we will introduce the proposed local-restricted Soft Assignment strategy and the image retrieval pipeline.

3.1 Local-Restricted Soft Assignment Strategy

We also consider the distance dxvi between the descriptor x and the visual word vi. However, there is a little bit difference from [Philbin et al., 2008]. Note that all the i nearest visual words are used to compute Dxvi , so Dxvi is:

where σ is the smoothing factor controlling the softness of the assignment. N = card(A\B) is the number of elements in the intersection. A and B is the set of the i nearest visual words to the descriptor x and y, respectively. In this case, the quantizer qr is formally a function as follow:

Whilst, the matching function fqr (x↪ y) = γq(x)↪q(y) of two image descriptors x and y is also different from fqs (x↪ y),

where vN denotes the intersection of A and B (namely, A \ B). Dxv and Dyv are the corresponding weights to descriptors x and y from visual words v (v 2 vN), respectively. t is another predefined threshold value. The local-restricted Soft Assignment is illustrated in Figure 1 (d), two image descriptors are assigned to the 6 nearest visual words, respectively. The intersection set of the two visual words set is vN (i = 1↪ 2↪ 3↪ 4), namely, N = 4. Moveover, we define two methods to calculate Dxv ⊕Dxv, that is, average (Equation (11)) and maximum (Equation (12)) strategy,

In Figure 1 (d), in terms of the average case, if it meets the situation where 4 > T and Dxv+Dyv 2 6 t1, (v 2 v1↪ v2↪ v3↪ v4), then we deem descriptors x and y as a good match.

3.2 The Proposed Image Retrieval Pipeline

The query image Q with L descriptors x = ¶x1↪ x2↪ ▷▷▷↪ xL♦, where xL 2 Rd are SIFT descriptors of dimension d. Firstly, the SIFT codebook V = ¶v1↪ v2↪ ▷▷▷↪ vK♦ is generated by HKM [Philbin et al., 2007], where K is the codebook size. When building the index, all features x are quantized into i nearest centroids using codebook V by ANN algorithm. Then, in the inverted index, for each entry W, information (e.g., image ID and other meta data) associated with the current feature x is stored continuously in memory. In essence, the matching function fqr (·) of two local features xl and ym is formulated as:

where q(·) is the quantization function for SIFT features, and γ is the function as in Equation (10). As a consequence, a local match is valid only if the two features satisfy N > T and Dxv ⊕Dyv 6 t (v 2 vN) in Equation (10).

Furthermore, to enhance the discriminative power of visual words, we incorporate SIFT Hamming Embedding into SIFT feature. Two features are considered as a match if and only if (iff) Equation (10) is satisfied and the Hamming distance db between their binary signatures is below a predefined

threshold ⌧. The matching strength is defined as exp(- d2b β2 ). Therefore, the matching function in Equation (10) is updated

as γq(x)↪q(y) =

Then, in our framework, the similarity score between a dataset image I and query image Q is defined as

where idf is the inverse document frequency value in [Zheng et al., 2014a], kIk2 and kQk2 denote l2 norm of image I and Q, respectively. The pipeline of our image retrieval system is summarized in Algorithm 1.

In the offline steps, K vocabularies are trained by HKM and the corresponding K inverted files are organized. Given a query image Q with L descriptors, for each feature xl, we quantize it to i nearest visual words using codebook V by ANN algorithm (step 3). Identically, given a dataset image I with M descriptors, we quantize each feature ym to i nearest visual words using codebook V by ANN algorithm (step 4). Then, both the query descriptor and the dataset image descriptor, are represented by i nearest visual words and corresponding distances.

During online retrieval, we firstly find intersection sets A \ B, calculating N = card(A \ B) (step 5 and 6) and the distance between visual words to the descriptor using Equation (8) (step 7-9). Then we calculate feature matching strength using Equation (10) (step 10). For each descriptor we combine with Hamming distance restricted condition using Equation (14), which further reduce quantization error (step 11). Finally, vote for the candidate dataset image using Equation (15) (step 12). At the end of the iteration, is returned feature similarity strength score sim(Q↪ I) (step 15).

Algorithm 1 Image retrieval pipeline using lrSA strategy.

Require:

The query image Q with L descriptors and the descriptors are x = ¶x1↪ x2↪ ▷▷▷↪ xL♦;

The K vocabularies V = ¶v1↪ v2↪ ▷▷▷↪ vK♦;

The dataset image I with M descriptors and the descriptors are y = ¶y1↪ y2↪ ▷▷▷↪ yM♦;

The K inverted files W = ¶w1↪ w2↪ ▷▷▷↪ wK♦;

Ensure: sim(Q↪ I);

• 1: for l = 1 to L do
• 2: for m = 1 to M do
• 3: Quantize xl into i nearest visual words and obtain the set A = (v(1) x ↪ ▷▷▷↪ v(i) x );
• 4: Quantize ym into i nearest visual words and obtain the set B = (v(1) y ↪ ▷▷▷↪ v(i) y );
• 5: Find the intersection sets A \ B;
• 7: for v 2 vN do
• 6: Calculate N = card(A\B);
• 8: Calculate the distance using Equation (8);
• 9: end for
• 10: Calculate descriptor matching strength using Equation (10);
• 11: Combined with Hamming distance weight using Equation (14);
• 12: Vote for the candidate image using Equation (15);
• 13: end for
• 14: end for
• 15: return sim(Q↪ I).

4 Experiments

To evaluate the effectiveness of the proposed lrSA strategy and image retrieval pipeline, we have conducted experiments on five publicly available datasets: Ukbench [Nister and others, 2006], Oxford 5K [Philbin et al., 2007], Paris 6K [Philbin et al., 2008], Holidays [J´egou et al., 2008] and MIR Flickr 1M [Huiskes et al., 2010].

4.1 Datasets

The Ukbench dataset [Nister and others, 2006] contained a total of 10,200 images, which are divided into 2,550 groups. Each image is taken as the query in turn and is represented by four images taken from four different viewpoints. For this dataset only, the performance is measured by the average recall of the top four ranked images, referred to as N-S score (maximum 4).

The Oxford 5K dataset [Philbin et al., 2007] was collected from Flickr and a total number of 5,062 images have been obtained. This dataset has been generated as a comprehensive ground truth for 11 distinct landmarks, each containing 5 queries. In total there are 55 query images.

The Paris 6K dataset [Philbin et al., 2008] was generated in coupling with Oxford 5K. This dataset contains 6,412 high resolution (1024 ⇥ 768) images from Flickr by queries of Paris landmarks, such as "Paris Eiffel Tower" or "Paris Triomphe". Again, Paris dataset is featured by 55 queries of 11 different landmarks.

The Holidays dataset [J´egou et al., 2008] consists of 1,491

images from personal holiday photos. There are 500 queries, most of which have 1-2 ground truth images. For each query in the Oxford 5K, Paris 6K, and Holidays datasets, the mean average precision (mAP) is employed to measure the retrieval accuracy.

The MIR Flickr 1M [Huiskes et al., 2010] is a distractor dataset, with one million images randomly retrieved from Flickr. We add this dataset to test the scalability of our method.

4.2 The Baseline

In this paper, we adopt the image retrieval procedure proposed in [Philbin et al., 2007] as the baseline approach. During preprocessing, we extract salient key points in the images from which the 128-dimension SIFT descriptors are computed. We also implement the rootSIFT variant, due to its effectiveness in [Arandjelovic and Zisserman, 2012]. Then, a codebook is constructed by Approximate k-Means (AKM) method using an independent dataset, namely, the Flickr60k dataset, and the codebook size is set to 20k. We use the FLANN library [Muja and Lowe, 2014] to perform Approximate Nearest Neighbors (ANN) computations. The inverted file which indexes dataset images and allows efficient access is built. For online retrieval, SIFT features of the query image are quantized as a single visual word using the ANN indexing structure. For each query visual word, candidate images are found from the corresponding entry in the inverted file. Scores for these candidate images are calculated using TDIDF value.

4.3 Important Parameters

Five parameters are involved in the proposed lrSA strategy: the weight σ, multiple assignment i and T, threshold value t1 and t2. We set i and T the same as [J´egou et al., 2010] to 10 and 4, respectively. σ is set to p6250 similar to that in

[Philbin et al., 2008]. t1 and t2 are set as 0.6 and 0.4 according to the observation of experimental results, respectively. For HA, it has no parameters. MA has two parameters i and T (10 and 4, similar to lrSA). SA has four parameters i and T (similar to lrSA), and ↵ (set to 1.2 according to [J´egou et al., 2010]) and the weight σ (p6250 according to [Philbin et al., 2008]).

Two parameters are involved in Hamming Embedding: the Hamming distance threshold ⌧ and weighting factor β. We set ⌧ and β to 4 and 7, respectively, the same as those in [Zheng et al., 2014a].

4.4 Evaluation

Comparison of Five Quantization Methods. We discuss five quantization methods here, i.e., Hard Assignment (HA), Multiple Assignment (MA), Soft Assignment (SA), average lrSA and maximum lrSA. Figure 2 compares the retrieval accuracy of the five quantization methods. Results on the four benchmark datasets are reported, which lead to three major observations. First, Figure 2 shows that for each of the four datasets, lrSA is shown to be superior to HA, MA and SA methods. The reason is that lrSA explicitly considers adjacent visual words more strictly, thus making significant improvement over the other three approaches. Second, The most notable point is that avg-lrSA is a little bit better than max-lrSA on all four datasets. Third, we observe that lrSA generally works well on all the four datasets. In essence, the Oxford 5K and Paris 6K mainly contain images of buildings, while the Ukbench and Holidays consists of general objects and scenes. As a consequence, we can conclude that the lrSA has a wide application scope, thus beneficial on general datasets.

Combination with Post-processing Steps. In this paper, we add various post-processing methods to our system to test if they benefit from the introduction of lrSA. Specifically, for Oxford and Paris datasets, we add Spatial Verification (SP) using RANSAC [Philbin et al., 2007] and Query Expansion (QE) [Chum et al., 2007] , due to the fact that query images in both datasets are architectures with rigid spatial configurations and that the number of ground truth images is relatively large. Moreover, we also try two different feature detectors, the Hessian Affine detector (HesAff) and the DoG Affine detector (DoGAff) [Simonyan et al., 2012]. The results are shown in Table 1 and Table 2. On Holidays and Ukbench datasets, we implement the Graph Fusion (GF) technique [Zhang et al., 2012] to fuse global HSV histogram and BoW rank lists. Specifically, we extract a 1000-D HSV histogram each image, normalized it by its l2 norm, and scale each dimension by a square root operator like in [Zheng et al., 2014b].

Large Scale Experiments. To evaluate the scalability of the proposed strategy, we populate the Oxford 5K, Paris 6K, Holidays, and Ukbench datasets with various fractions of the MIR Flickr 1M dataset. Experimental results are demonstrated in Figure 3. It is notable that as the dataset gets scaled up, performance of our strategy drops much more slowly. That is to say, more significant improvement is obtained on larger dataset.

Comparison with State-of-the-Arts. We compare our results with the state-of-the-art methods in Table 3. First, as we can see, our method achieves competitive results on Oxford, Holidays and Paris datasets. Specifically, we achieve mAP = 88.1 % on Oxford, mAP = 86.5 % on Holidays and mAP = 86.9 % on Paris dataset. Second, for the comparison on Ukbench dataset, we achieve the state-of-the-art result (N-S = 3.86) after combining post-processing step.

5 Conclusion

We propose a novel feature matching strategy lrSA based on Soft Assignment, in which a new matching function is introduced to reformulate Soft Assignment. The proposed strategy is verified on five popular benchmarks, achieving competitive results compared with the state-of-the-art results.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (NSFC, No. 61340046), the National High Technology Research and Development Program of China (863 Program, No. 2006AA04Z247), the Scientific and Technical Innovation Commission of Shenzhen Municipality (No. JCYJ20120614152234873, JCYJ20130331144716089) and the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20130001110011). The authors wish to thank Wei Xiao and Liang Zheng for their helpful comments and suggestions in this paper.