Herveé Jégou

Matthijs Douze

Cordelia Schmid

H Jégou

Keywords: image search, image retrieval, nearest neighbor, reciprocal nearest neighbors proches voisins, graphe de plus proche voisins

This report addresses precise image search based on local descriptors. Our approach extends a k-NN voting scheme in several ways. First, we introduce a query-adaptive criterion that is shown effective to weight the descriptor matches. Second, we exploit the distances between SIFT descriptors and the reciprocal neighbors to further refine the similarity measure between descriptors.

Each of these two complementary strategies leads to a significant improvement over the usual voting baseline, and significantly outperforms bag-of-features, at the cost of a very high computational and memory complexity due to the exact computation of distances and reciprocal nearest neighbors. In order to make our method tractable, we exploit an approximate search method which, in addition to returning nearest neighbors with high probability, provides precise distance estimates without accessing the full raw vectors, which is critical to avoid memory issues.

Experimental results show that our method outperforms the state of the art on four challenging datasets. Although our method is not as efficient as bag-offeatures, we show that it can handle a database of up to 1 million images with reasonable query times.

Introduction

Content based image search is a very active field. In recent years, the size of databases that could be handled increased dramatically. In this context, the bag of visual words (BOVW) framework [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] and its recent extensions were shown to provide a good precision with high efficiency. In particular, precision was improved by adding binary codes [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] or by using soft-assignment in combination with large visual vocabularies [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. Another way to improve matching within a BOVW framework is to learn descriptor projections adapted to the data [START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF][START_REF] Winder | Learning local image descriptors[END_REF]. Probabilistic connections between visual words are advantageously learned to improve the image similarity in the context of large visual vocabularies [START_REF] Mikulik | Learning a fine vocabulary[END_REF].

The goal of this paper is to improve the precision by extending descriptor matching methods [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF]. High precision is required in applications such as grasping a limited set of objects [START_REF] Kang | Image matching with distinctive visual vocabulary[END_REF], robot localization [START_REF] Se | Vision-based mobile robot localization and mapping using scale-invariant features[END_REF] or for re-ranking the results output by a large scale indexing system. Improving precision is especially necessary in the case of clutter and cropping, where the standard BOVW does no longer correctly measure the distance between images due to the small number of inliers and likewise the high rate of incorrect matches. In particular, recognizing locations or particular object instances on cropped images remains a challenging task. Although BOVW coupled with geometrical verification in a re-ranking stage partially addresses this issue, for large datasets a large proportion of images has to be verified, which severely impacts the efficiency and requires additional geometrical information 1 . In order to limit the number of images to be spatially verified, it is worth having a stronger matching system for the first stage. An image search system seeking high precision includes, in general, a geometric post-verification scheme [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], which can be combined with query expansion [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], if multiple relevant images are expected.

In this paper, we exploit the information provided by the distances between local descriptors. Except a few systems that perform feature selection [START_REF] Kang | Image matching with distinctive visual vocabulary[END_REF][START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF], the descriptor matches are usually assumed equal. Considering a k-NN voting framework, we first investigate how to use the distances to nearest descriptors to improve the voting quality, and propose a query-adaptive criterion extracted for the k-NN list. It is obtained by comparing the distance of the k -1 first neighbors with that of the k-th nearest neighbor. The informativeness of this criterion is validated by a mutual information analysis, which shows that the proposed quantity conveys more information about the correct image than ranks or absolute distances. This criterion is further combined with re-weighting techniques originally introduced in the BOVW framework [START_REF] Jégou | On the burstiness of visual elements[END_REF] to improve precision.

As a second contribution, we exploit the distances associated with the reciprocal nearest neighbors (RNN). These RNN are the k-NN of the database descriptors within the database itself. These distances are exploited to further improve the quality of the score associated with each query. Indeed, the k-NN neighborhood is asymmetric: x being a k-NN of y does not necessarily mean that y is a k-NN of x. If a database vector y is a k-NN of the query x, then it is more likely to be a reliable match if x is also a k-NN of y if x would be added to the database.

A related work is the contextual dissimilarity measure [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF], which proposes to regularize the distance between BOVW vectors by improving the reciprocality of the neighborhood of BOVW vectors. Similarly, reciprocal nearest neighbors were exploited in [START_REF] Danfeng | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF], again on BOVW vectors.

In contrast to these works, our method exploits the reciprocal nearest neighbors of SIFT descriptors to improve the reliability measure of each individual match. This leads to a significant improvement when this confidence measure is used to adjust the voting weights. Both aforementionned methods assume that exact distances to nearest neighbors are available, as well as pre-computed nearest neighbors of each database vector. Moreover, they make use of raw descriptors, and require a lot of memory. These methods are therefore limited to relatively small datasets (a few thousands of images).

For these reasons, we propose an approximation of our method to trade precision against efficiency. It consists in first using the approximate search technique of [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF], which, in addition to returning reliable nearest neighbors, produces distance estimates with sufficient precision. Second, we estimate based on an external dataset the typical distances associated with the RNN, which is the only information required by our scheme.

To the best of our knowledge, no other technique could handle nearestneighbor searches of local descriptors with the required memory compactness, precision and search speed, and in addition providing exploitable distance estimates: LSH [START_REF] Andoni | Near-optimal hashing algorithms for near neighbor problem in high dimensions[END_REF] and kNN trees [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF] both require access to the raw descriptors of the whole dataset in a costly re-ranking stage.

The paper is organized as follows. Section 2 introduces the datasets and the image description scheme used in the evaluation. Section 3 presents the voting framework, introduces our query-adaptive criterion and our RNN method. Section 4 shows how to obtain a scalable approximation of our method, which is evaluated in Section 5 in terms of precision and efficiency and compared with the state of the art.

Datasets and image description

This section briefly presents the datasets and descriptors used for evaluating our approach. We use the descriptors/software available on-line, such that our results are directly comparable to those reported in the literature.

Oxford and Paris

The Oxford dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] consists of 5062 images of building and 55 query images corresponding to 11 distinct buildings in Oxford. All queries are defined by a rectangle delimiting the building and are in "upright" orientation. The search quality is measured by the mean average precision (mAP) computed over the 55 queries, as defined in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Images are annotated as either relevant, not relevant, or junk, which indicates that it is unclear whether a user would consider the image as relevant or not. These junk images are removed from the ranking before computing the mAP. The Paris dataset [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] consists of 6412 images collected from Flickr by searching for particular Paris landmarks. The definition of positives, their statistics, and the evaluation protocol is the same as for Oxford.

We use the Paris dataset to learn the parameters used for the Oxford dataset, and vice versa. Although learning the parameters on the dataset itself is reported to significantly improves the results [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF][START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], this does not reflect the INRIA performance of the system on a large scale because it is prone to over-fitting. We have used the image descriptors available on-line2 . They were obtained by extracting interest regions with the Hessian-affine detector [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF] and describing them with SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

Holidays and Flickr

The Holidays dataset [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] is composed of 1491 high resolution personal photos of different locations and objects, 500 of them being used as queries. The search quality is measured by mAP, with the query removed from the ranked list. For determining the parameters, we have used an independent dataset provided together with Holidays, denoted by Flickr60K. Large scale evaluation is performed by adding a set of 1 million images collected from Flickr referred to by Flickr1M and also used in [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] for large scale evaluation.

For all three datasets we have used the pre-computed features available online3 . These features have been extracted with the Hessian-affine detector [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF] and described by SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Note that the features are rotation invariant.

University of Kentucky dataset (UKB)

The UKB object recognition benchmark consists of a dataset of 10200 images representing 2550 objects or scenes (4 images per object). All images are used as queries, and the standard performance measure reported in the literature is the average number of images that are correctly ranked in the first four positions. As for the Holidays dataset we used the Hessian-affine detector to extract features and characterize them by rotation invariant SIFT descriptors. We used the same descriptors as in [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF], which gives better results than using those of [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] (only the cornerness threshold is different, because the images are smaller).

Beyond majority vote

In this section, we consider a voting approach, where an indexing system returns a set of k-NN hypotheses for each query descriptor. We analyze how to better exploit this k-NN short-list to improve search precision, i.e., how to go beyond a simple majority vote.

For the purpose of analysis, we consider in this section that the k-NN search is exact: the true Euclidean nearest neighbors of the query descriptors are used. The way we leverage the use of exact nearest neighbors is presented in Section 4, where we introduce our approximate strategy and evaluate the trade-off between precision, memory and efficiency.

Voting criteria

We consider a set of m database images, each described by n j descriptors (j = 1 . . . m). The set of vectors for the whole database is denoted by Y = {y 1 , ..., y i , ...y n }, where n = j n j . The image associated with descriptor y i is

N k (x) = k-arg min yi∈Y d(x, y i ), (1)
where d(., .) here refers to the Euclidean distance, without loss of generality. The r-th NN of x is denoted by

N r (x), thus N k (x) = {N 1 (x), . . . , N k (x)}.
Figure 1 shows, for 20 descriptors extracted from the same query image, the distances d(x, N r (x)), r=1..100, associated with the 100-NN as a function of the rank r. We indicate the descriptors which belong to the corresponding images in the dataset, i.e., which may be correct and should be taken into account. On this small scale example we can make several observations, which are shown in the following to generalize to larger sets based on a quantitative evaluation:

• The absolute distance information is not reliable to distinguish query descriptors which obtain best matches.

• There is a concentration of true matches in the first ranks, but keeping only these first matches, for instance keeping the 10-NN only, ignores many matches associated with the more difficult images.

Once the nearest neighbors are retrieved, several voting strategies are possible to exploit the information provided by the ranked list of neighbors and their distances to query descriptor. In the following, we distinguish several types of voting schemes:

• C m : majority vote, i.e., count the total number of votes for the image, independently of rank/distance information ; • C r : exploiting the rank information ;

• C d : exploiting the absolute distance information.

More complex treatments exploiting the distance information of the ordered short-list of k-NN have also been proposed. For instance the distance ratio criterion [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] is used to discard unreliable votes [START_REF] Kang | Image matching with distinctive visual vocabulary[END_REF][START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF]. We observed that it does not significantly improve on Holidays.

Proposed criterion: We introduce a query adaptive criterion C a derived from the distances to neighbors. For a fixed reference rank r * ≤ k, a query descriptor x and a descriptor y of the database, it is defined by

δ r * (x, y) = max d (x, N r * (x)) -d (x, y) , 0 , (2)
where d (x, N r * (x)) is the distance between the query descriptor x and its r * -th NN match. The value δ r * (x, y) is more comparable across queries than the absolute distance d(x, y). It exploits the regularity of the NN distance distribution shown in Figure 1: The criterion amounts to aligning the curves by a translation based on the distance to the reference r * -th NN. As a result, our query adaptive criterion is better at distinguishing reliable matches from unreliable ones. We typically choose r * = k, in which case the criterion is denoted δ k .

Mutual information analysis

In this section we quantitatively measure the amount of information contained in the different voting criteria. To obtain an accurate measure of precision, all statistics presented in this subsection are computed from the 100-NN list of each descriptor of the Holidays dataset. This corresponds to the 1.45 million query descriptors extracted from the 500 query images, exhaustively computed by a linear scan on Holidays, or equivalently to a total of 145 million nearest neighbors.

We will consider descriptor matches as correct iff the images from which they come correspond. Figure 2 shows the empirical probability distribution functions of correct and incorrect retrieved descriptors as a function of a) the rank, b) absolute distance, and c) our query-adaptive criterion. These distributions give an intuitive idea of the properties of these criteria. For instance, the rank is reliable for the first ranks, but for k > 5 the distribution of correct and incorrect matches is not distinguishable. Absolute distances give a slight prior on whether the match is correct or not. The distributions associated with our query-adaptive criterion significantly differ for true and false matches, suggesting a more reliable selection rule.

criterion k I(G, C r ) I(G, C d ) I(G,
To quantitatively measure the informativeness of each criterion, we use mutual information [START_REF] Mackay | Information Theory Inference and Learning Algorithms[END_REF], which measures the amount of information shared by two random variables, either discrete (for the rank) or continuous (for absolute distances or our criterion). Let's consider the random variable of quantity C x (X, Y ) (C x =C a , C r or C d ) computed between query descriptor X and database descriptor Y . Denote by G = (im(X), im(Y )) ∈ {0, 1} the random variable which indicates whether (X, Y ) is a correct match or not. The conditional mutual information between the correctness of the match and the criterion C x is computed as

I (G, C x ) = G C x P (G, C x ) log 2 P (G, C x ) P (G)P (C x ) . (3)
Here, we are only interested in extracting some measures from the k-NN shortlist, i.e., Y is assumed to be k-nearest neighbor of X. Therefore all probabilites are conditional probabilities knowing Y ∈ N k (X). The values of the C x =C r and C a are quantized for the estimation.

Table 1 reports the mutual information measured for C r , C d , and C a . This mutual information is a decreasing function of k, as this measure is averaged over all k nearest neighbors: the additional neighbors are less reliable when k increases.

The informativeness of absolute distances is greater than that provided by the ranks for k < 20. This is not surprising, because what is measured is the conditional mutual information knowing that the descriptors are ranked in top k positions: the absolute distance provides a more complementary information. Overall, the query-adaptive criterion convey significantly more information about the correctness of the match than the other two.

INRIA

Image similarity

Weighting method. We consider the following simple voting strategies. For the majority vote, the score of image b for query q is obtained as

s m (q, b) = x∈D(q) y∈N k (x)∩D(b) 1, (4)
where D(a) denotes the set of descriptors extracted from image a. Similarly, we consider a simple linear decreasing rank weighting method:

s r (q, b) = x∈D(q) y∈N k (x)∩D(b) k -rank(y), (5)
where rank(y) refers to the rank of y in N k (x). Our query-adaptive criterion is simply summed over matches of images b:

s a (q, b) = x∈D(q) y∈N k (x)∩D(b) δ k (x, y). (6)
It is possible to introduce a soft voting scheme exploiting the probabilities represented in Figure 2. However, we do not adopt such weights because they depend on the dataset and require ground-truth annotations.

Image score normalization: The score obtained by the voting scheme is not regularized. The images with many descriptors are, therefore, favored compared to those with fewer descriptors. Different normalization schemes have been evaluated [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], some of which are applicable in a BOVW framework only, such as the L2 normalization of the BOVW vector. In our voting framework, we evaluate:

• N0: normalization by the number of descriptors,

• SRN: the score is divided by the square root of the number of descriptors, i.e., the normalized similarity s * x (a, b) is obtained as

s * x (a, b) = s x (a, b) 1 √ n a √ n b , (7)
where n a and n b correspond to the number of descriptors in image a and b, respectively.

SRN has the desirable property that s * m (a, a) = 1 if each descriptor of a is matched with itself only, in which case s m (a, a) = n a . It is, equivalent in our voting framework, to the L2 normalization combined with the cosine similarity in a BOVW framework. However to our knowledge this has not been proposed in the k-NN framework, where the most used metrics are either the number or the rate of inliers.

Figure 3 shows the mAP results measured on Holidays for different combinations of scoring and normalization methods. The proposed criterion C a is significantly better than the majority vote or ranked-based weighting for all tested k. This confirms the findings of the mutual information analysis. The SRN normalization is also consistently better for all weighting schemes. Based on the exact Euclidean NNs, the mAP outperforms the state of the art by 7% of mAP: To our knowledge the best result without geometrical information is the mAP score of 77.5% reported in [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. In the next sections, we will show that our approach still works when considering an approximate strategy using quantized descriptors.

Burstiness: As observed in [START_REF] Jégou | On the burstiness of visual elements[END_REF], the visual elements are "bursty" by nature, which means that query descriptors may receive abnormally many votes from the same image. This phenomenon is observable in Figure 1: for the same query descriptor, several descriptors from the same image (same color and point type) are returned in the k-NN list. A simple strategy consists in using multiple match removal [START_REF] Jégou | On the burstiness of visual elements[END_REF][START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF][START_REF] Mikulik | Learning a fine vocabulary[END_REF] to avoid counting multiple times matches obtained for the same query image and the same query descriptor: only the best one is considered. A more advanced strategy is the "intra-burstiness" method proposed in [START_REF] Jégou | On the burstiness of visual elements[END_REF]. It is related to multiple match removal, since the scores associated with multiple matches are down-weighted. As shown in Table 2, this strategy slightly improves the results on Holidays for the best SRN +C a variant, especially for large values of k where multiple matches are expected.

Term-Frequency and Inverse Document Frequency: In a BOVW framework, the inverse document frequency is a popular way of down-weighting the contribution of visual elements that appear more frequently. This strategy is not applicable and unnecessary in our voting framework because for all query descriptors the same number k of database descriptors are retrieved, thereby limiting the effect of unbalanced inverted lists in BOVW.

Reciprocal nearest neighbors

Unlike descriptor matching based on visual words, k-nearest neighbors are by nature asymmetric: y is a k-NN of x does not imply that x is a k-NN of y. In a BOVW framework, the paper [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF] links this property with the observation that some images are very often returned while being irrelevant, and modifies the BOVW comparison metric to make the neighborhood more symmetric, showing that this improves the results.

To our knowledge the problem of neighborhood asymmetry has never been tackled for SIFT features in the context of image search, probably because it raises an important complexity issue: the full graph of k-nearest neighbors of the database must be pre-computed, which is feasible for small datasets only. Nevertheless, when aiming at very precise matching for small datasets, it is interesting to evaluate a reciprocal rule (denoted by reci ) symmetrizing the descriptor comparison. For this purpose, we consider the NNs associated with the database image. The voting strategy is modified as follows:

• for each y ∈ Y the distance to the k * -NN is computed off-line • the score is made symmetric by using the weight δ k (x, y)+δ k (y, x) instead of δ k (x, y) (note that δ k (., .) is not symmetric)

• in case the quantity is negative4 , the match is ignored.

As shown in Table 2, the results are further improved on Holidays, and the sensitivity to the parameter k is remarkably reduced. Using larger values of k is useful when geometric constraints are used to improve precision [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], in which case more matches are required. Using a simple implementation of the efficient weak geometric consistency (WGC) check proposed in [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], we obtain a mAP of 86.8% which significantly outperforms the state-of-the-art mAP=84.8% reported in [START_REF] Jégou | On the burstiness of visual elements[END_REF] by using a full geometrical verification [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The mAP score of 85.2% obtained without any geometrical information significantly outperforms the best score of 77.5% reported in [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. However, this state of the art performance is obtained using exact matching. The next section addresses both the underlying CPU and memory issue by making use of approximate strategies.

Scaling the approach

Although the main objective of this paper is to improve the precision of image search without focusing on larger datasets such as those considered in [START_REF] Perronnin | Large-scale image retrieval with compressed Fisher vectors[END_REF][START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], the approach remains too costly to be applied even on a few thousands images. In this section, we adapt our method to improve its memory and CPU efficiency.

Approximate nearest neighbors

To improve the efficiency of our scheme, we use an approximate nearest neighbor (ANN) search algorithm, trading accuracy against efficiency. One of the most popular method is the FLANN algorithm [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF]. However this package requires to access the full vectors for post-verification, which limits the number of descriptors and therefore of images that can considered without accessing disk storage. Instead, we use a recent extension [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF] of the IVFADC method [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] to index local descriptors. It is based on inverted lists and quantization codes associated with the indexed vectors. The key parameters of this approach are:

• The total number of inverted lists. It is fixed to 20000 in our case;

• The number M of inverted lists visited per query descriptor. This parameter has the most impact on efficiency. We use M =1, 10 and 100.

• The number of bytes per descriptor in the inverted file system, which is fixed to 8 in our case (+4 bytes for the image identifier).

b M k=10 k=20 k=50 k=100 2 with the same setting (C a +NRS+burst), but using exact search are duplicated for reference.

Although the approach of [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] returns mostly correct neighbors, we observe that the distance estimates obtained from the codes are not very accurate. The extension of [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF] leverages this issue by using a vector re-ranking stage that improves the distance estimation. In contrast with most ANN methods, the re-ranking is done using quantized codes instead of using raw SIFT descriptors. The idea consists in encoding the error vector using quantization codes, which introduces an additional memory cost of 0, 8, 16 or 32 bytes, per descriptor, depending of the desired precision. This parameter has an important impact on memory, but little impact on efficiency, as the re-ranking is performed on a short-list of 10k neighbors only.

Overall, each descriptor is represented by b = 12, 20, 28 or 44 bytes, depending on the refinement parameters.

Table 3 shows the impact of the approximate nearest neighbor search technique. We consider different trade-offs in terms of memory (the b parameter) and efficiency (essentially related to parameter M , although parameter b has a slight impact as well). Timings measured on a large dataset of one million images will be given in Section 5. One can observe that for the best k, the method converges gracefully to the results obtained with exact search.

Reciprocal nearest neighbor

The main obstacle for using the reciprocal method of Subsection 3.4 on a large scale is the difficulty to obtain the full graph of k-NN. Although some methods (e.g., [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]) provide approximate strategies to break the complexity, this problem remains intractable when considering more than 100 million descriptors.

However, the key quantity exploited by our RNN method is not the full k-NN graph, but the typical distance of each descriptor to its k-th nearest neighbor. To estimate this quantity, our strategy considers an independent dataset of limited size (1 to 10 million descriptors) to estimate a typical k * nearest neighbor distance associated with each database descriptor. The quantity k * is not necessarily equal to k because the indexed database and the external dataset may have different sizes. It is set to k * =20 for all external datasets (Flickr1M, Paris and Oxford).

This external dataset is fixed, and the typical distances associated with a database image are computed when adding it to the index. rocal distance information takes 2 bytes per descriptor 5 . The Flickr60K dataset is used to compute the typical k-NN distance associated with the database descriptors of Holidays. Paris is used for Oxford and Oxford for Paris.

Experiments with approximate neighbors

This section is dedicated to the performance analysis of the more scalable approximate version of our approach presented in Section 4. Unless specified, our results are obtained using M = 100 and b = 44 bytes per descriptor (+2 bytes if the reciprocal NN rule is used), without using any geometrical information.

Our SRN normalization is used in all experiments, as it is consistently better results than N0. Hereafter, we discuss the respective merits of our methods and compare it with the state of the art.

The proposed criterion C a significantly and consistently improves the results over the majority vote C m on all datasets, see Table 4. The gain in mAP is +8.3% for Oxford, +5.1% for Paris, +5.1% for Holidays. Using the weighting strategy for multiple matches adapted from [START_REF] Jégou | On the burstiness of visual elements[END_REF] further improves the results to +10.1%, +6.2% on Oxford and Paris. On Holidays there is no apparent gain for k=10, but this method reduces the sensitivity to k, see Table 3.

The reciprocal k-NN distance brings a significant improvement on both Oxford and Paris. In contrast to Table 2, the results are not improved on Holidays. Our explanation is that the Flickr60K database used to find the reference distances associated with reciprocal neighbors is very different from Holidays and UKB, while the dataset Oxford and Paris are more similar (both includes photos of building downloaded from Flickr).

Impact of k:

The main parameter of our approach is the number k of nearest neighbors. The sensitivity of the search quality to this parameter can be judged from Figure 4 and Table 3 for Oxford and for Holidays, respectively. One can observe that the best variant SRN +C m +burst+reci is not very sensitive to the parameter k, which depends on the number m of images in the databases and of the number m c of correct images. An empirical value like k = m c log m is a satisfactory choice on the 4 datasets considered. concurrent approaches occasionally reports some better results on a particular dataset, but overall our results are more consistently high are all datasets. Interestingly, without using any geometry, our results on Oxford and Paris (76.4% and 72.8%, respectively) are better than those reported in [START_REF] Philbin | Descriptor learning for efficient retrieval[END_REF] with full raw descriptors (linear scan), distance ratio testing, and spatial verification performed on all images (+0.9% on Oxford and +5.6% on Paris). Finally, we mention that by increasing the number of descriptors, our approach improves further: we obtain on Holidays a mAP of 91.5% with geometry (88.8% without spatial verification) by using 16M instead of 4.5M descriptors.

Timings. We have measured the average time per query when querying the entire Flickr1M dataset merged with Holidays, i.e., 1,001,491 images in total.

For this experiment, we allocate 28 bytes per descriptor, so that the structure fits on a server with 64 GB of memory. The corresponding mAP is 70.5%, against mAP=62% in [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] [4] (See [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]- Fig 15, which requires at at least 25GB of memory) and mAP=34% with a BOF representation. The search takes 12s using 20K inverted lists. This timing is obtained for k=20 on an 8-core machine. It does not include descriptor extraction.

Remarks:

1. For reference, exact search on Holidays only (1491 images) takes 710 seconds on the same machine with an optimized linear scan. Our method is therefore four orders of magnitude faster than this linear scan baseline.

2. Due to the relatively high amount of memory used to achieve a significantly improved precision, our approach is more intended to be used on smaller scales than those typically considered in the BOVW framework. However, it easily scales up to 100K images per machine, in which case a query takes about 1s. The evaluation we performed on 1 million images requires a powerful server (64GB of RAM).

INRIA 6 Conclusion

This paper shows that exploiting distances between local descriptors significantly improves the accuracy of image search. Firstly, we introduce a distance criterion that provides additional information about correct matches. Secondly, we show that reciprocal nearest neighbors efficiently favor the correct matches and further improve the results. Although our approach is not as scalable as some BOVW methods of the literature, it significantly improves precision, outperforming methods that use geometrical information extensively. An interesting open question is how to better approximate the reciprocal nearest neighbor method proposed in this paper.

Figure 1 :

 1 Figure 1: Illustrating descriptor distances. Left: a query (top-left) and corresponding images in the Holidays dataset (below). Right: distances of the 100-NN for 20 query descriptors (one curve per query). The true matches associated with one of the 6 database images are represented by bigger points (one color and point type per image). A filtering or weighting method based on absolute distances is unreliable, as these significantly vary across query descriptors. The rank information seems more informative, but useful for the first ranks only. The NN distance curves are remarkably similar in shape: a vertical translation approximately aligns them. Best viewed in color.

Figure 2 :

 2 Figure 2: Empirical distribution function of true (TP) and false (FP) matches for three criteria: the rank C r , the Euclidean distance between descriptors C d , and the proposed query-dependent distance criterion C a .

Figure 3 :

 3 Figure 3: Impact of the scoring and normalization methods on the search accuracy. The line style and color represents the criterion used (C m , C r or C a ). The point type represents the kind of normalization (circle=N0, square=SRN). Results are presented for Holidays.

Table 1 :

 1 Mutual information between the correctness G of a match ranked in k nearest neighbors and the rank C r , the absolute distance C d and the proposed criterion C a . Note that this information is given per match (averaged over k nearest neighbors). It has been measured using the entire Holidays dataset.

	C a )

Table 2 :

 2 ). Results are presented for Holidays. Impact of the "burstiness" score update[START_REF] Jégou | On the burstiness of visual elements[END_REF], of our reciprocal nearest neighbor rule (C a +SRN) and of a simple geometric check (WGC)[START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. Results are measured by mAP for Holidays.

	INRIA

Table 3 :

 3 Impact of the approximate nearest neighbor approach on search quality. Results are presents for Holidays. Values from Table

	12	1 76.4	75.6	73.0	70.2
	12	10 79.0	79.2	77.0	74.9
	20	5 82.1	80.2	77.1	74.5
	28	10 83.0	81.8	79.2	76.3
	44	100 84.3	83.6	81.3	79.0
	Exact	-84.4	83.9	83.1	82.3

Table 4 :

 4 Retrieval results for the four considered evaluation datasets. We set k = 10 for all results of Holidays and k = 100 for Oxford, Paris and UKB.

	Storing this recip-

  The comparison with the state of the art is performed by considering the most comparable setups, in particular without considering spatial verification. Our approach clearly outperforms the state of the art in search quality. The Precision of the proposed approaches on Oxford, depending on the number of neighbors per query point. The results are all provided for SRN normalization and using the approximate ANN method of[START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF], using 44 bytes per descriptor (raw descriptors are not used during search).

	0.6 0.65 0.7 0.75 0.8 Mikulík [16], geometry 10 Philbin [23], no geometry Philbin [23], geometry Philbin [23], +raw SIFT Jégou [9] Jégou [6], no geometry Jégou [5], geometry Figure 4: dataset → Oxford Paris UKB Holidays 100 mAP k C m : simple count C a + burst + reci + spatial verification 74.2 74.9 74.9 66.2 67.8 70.7 68.9 75.5 67.2 3.68 56.1 3.42 77.5 68.5 3.64 84.8 ours, no geometry 76.4 72.8 3.60 84.4	1000

Table 5 :

 5 Comparison between the state of the art and our method used with approximate search (without using raw descriptors). Bold: best results reported without geometry. Italics: results reported with spatial verification (without query expansion). These results are obtained using descriptors used in the literature. When using more descriptors with our method, we get further improved results (88.8% on Holidays without geometry, 91.5% with spatial verification).

This representation may be compressed to a few dozen bits, as shown in[START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF].RR n°7656

http://www.robots.ox.ac.uk/~vgg/data/oxbuildings and http://www.robots.ox.ac.uk/~vgg/ data/parisbuildings

http://lear.inrialpes.fr/~jegou/data.php RR n°7656

RR n°7656

This may happen if the query descriptor is not a k-NN of the database descriptor if being inserted in the database vector set: in this case δ k (y, x) < 0 is negative and the sum δ k (x, y) + δ k (y, x) may be negative as well.

It could probably fit in 1 byte with sufficient precision, but since its memory usage is small compared to the descriptor representation, we store the exact distance.INRIA


Nadjet Belblidia
email: nadjet.belblidia@lip6.fr

Evaluating the Spatial Dimension of Contacts in Opportunistic Networks [Extended Abstract]

Keywords: C.2.1 [Computer-Communications Networks]: Network Architecture and Design-Store and forward networks Measurement, Experimentation Delay tolerant networks, capacity, interference. 1. CONTEXT AND PROBLEM DEFINITION

Is temporal dimension knowledge alone sufficient to characterize contacts in opportunistic networks? Several studies analyze the temporal aspect of contacts with significant results concerning the contact and inter-contact duration. Nevertheless, only the temporal dimension does not give a complete overview of contact characterization. We propose the surround indicator as a metric to exhibit the contact connectivity in opportunistic networks. We evaluate the surround indicator on two existing datasets. Our preliminary results reveal that contacts have too heterogeneous surrounds to be considered only in terms of duration.

One challenging issue in opportunistic networks concerns data transmission optimization. To increase the data delivery probability, it is fundamental to characterize the contact capacity. Providing fine contact capacity characterization is difficult because it depends on a number of parameters that are related to the technology used, the signal propagation laws of the environment, and the traffic demands between source-destination pairs. It is important, however, to take into account any available knowledge to characterize a contact capacity.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MobiOpp '10, February 22-23, 2010, Pisa, Italy. Copyright 2010 ACM 978-1-60558-925-1/10/02 ...$10.00. A contact has two dimensions: temporal and spatial. The temporal dimension concerns the contact and intercontact distributions and has been the subject of several studies [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF][START_REF] Karagiannis | Power law and exponential decay of inter contact times between mobile devices[END_REF]. The spatial dimension is related to the contact's surrounding environment. This dimension can have a real impact on the contact capacity and has been surprisingly underexplored in the literature. Fig. 1 illustrates two completely different situations where contacts last for the same duration. Contacts can be considered as having the same capacity when only considering the temporal dimension. Clearly, although the contacts have the same duration, the one in Fig. 1(a) is much more prone to interference as it happens in a denser zone. We argue that additional information which provides simple indication on the contact surrounding conditions can bring a complementary knowledge for a better contact capacity characterization.

We propose to exhibit the spatial dimension of contacts with information about nearby contacts that are potential sources of interference with the contact under consideration. We define the notion of surround indicator and evaluate its distribution using two datasets with different inherent contact properties. Our preliminary analysis reveals that opportunistic networking is much more dynamic than it is traditionally handled as. Besides the intermittent characteristic of connectivity, nodes observe huge surround variability.

SPATIAL DIMENSION OF CONTACTS

Let V be the set of nodes in the network and xy be the directional contact between x and y, with x, y ∈ V. We refer to it as the target contact. N + x (t) and N - x (t) are respectively the sets of out-neighbors and in-neighbors of node x at time t. Loosely speaking, we define the surround indicator Sxy(t) of the target link xy at time t as the number of outgoing links of all y's in-neighbors except x :

Sxy(t)= X ∀z∈N - y (t)-{x} |N + z (t)|. (1)
From the notation above, it becomes clear that the surround indicator points out how many sources of interference (i.e., collocated contacts) might have an influence on the reception quality of the target contact.

The surround indicator is likely to vary during the interval [t1,t2], as some neighbors appear while others leave during the contact. We propose to decompose the contact into as many necessary sub-contacts with a stable surround indicator. Each sub-contact represents the temporal view of a surround. We define the expansion as the number of sub-intervals associated to the same original contact. This representation allows not only characterizing neighborhood density through the surround indicator, but also to have a clue on the network dynamics. Indeed, the expansion reflects the contact surround instability.

PRELIMINARY EVALUATION

We evaluate the spatial dimension of contacts in the Infocom [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF] and RollerNet [START_REF] Tournoux | The accordion phenomenon: Analysis, characterization, and impact on dtn routing[END_REF] datasets. These datasets are publicly available to the community through the Crawdad repository [START_REF]CRAWDAD[END_REF].

Fig. 2 shows the distribution of the contacts according to the expansion value. In RollerNet, about 50% of the contacts have an expansion larger than 12. Similarly, in Infocom, about 50% of the contacts have an expansion larger than 16. Furthermore, the expansion reaches extreme values in both cases. In RollerNet, the most instable surround contact has an expansion equal to 173, while it reaches 1,436 in Infocom.

Fig. 3 shows the cumulative distribution function of subcontacts according to the surround indicator. For both datasets, the percentage of contacts with a null surround indicator does not exceed 0.55% for RollerNet and 0.59% for Infocom. Therefore, it is very rare that a contact happens in an isolated environment. Moreover, in extreme cases, the surround indicator reaches 212 in RollerNet and 378 in Infocom. Even if the surround indicator is just an indication of potential parallel communications, such a high number of surrounding contacts clearly shows that some zones are likely to have a limited number of working links, if any, due to mutual interference (if only because of exchanged control messages).

CONCLUSION AND FUTURE WORK

In this abstract, we introduce the surround indicator as a metric to exhibit the spatial dimension of contacts in opportunistic networks. The surround indicator provides explicit information of the environment in which contact takes place. Our preliminary analyse on two different datasets shows that the surrounding environment of a contacts is more dynamics than indicated by solely contact and intercontact times.

Although the proposed metric is merely indicative, the surround indicator can be useful in a number of research problems. As future work, a routing protocol might decide to avoid a path that traverses a node that has a too high surround indicator value (thus prone to competitive flows). Similarly, the same node might be a good starting point of an epidemic dissemination algorithm.

  Contact in a sparse zone.

Figure 1 :

 1 Figure 1: Two situations. The same duration.

Figure 2 :

 2 Figure 2: Repartition of contacts according to the expansion.

Figure 3 :

 3 Figure 3: Repartition of sub-contacts according to the surround indicator.

ACKNOWLEDGMENTS

This work is being done under the supervision of my advisors Marcelo Dias de Amorim and Serge Fdida from UPMC Paris Universitas in collaboration with Jérémie Leguay and Vania Conan from Thalès Communications and Jon Crowcroft from Cambridge University. This work is partially supported by the ANR project Crowd under contract ANR-08-VERS-006.