Alexis Joly

Random Maximum Margin Hashing

Following the success of hashing methods for multidimensional indexing, more and more works are interested in embedding visual feature space in compact hash codes. Such approaches are not an alternative to using index structures but a complementary way to reduce both the memory usage and the distance computation cost. Several data dependent hash functions have notably been proposed to closely fit data distribution and provide better selectivity than usual random projections such as LSH. However, improvements occur only for relatively small hash code sizes up to 64 or 128 bits. As discussed in the paper, this is mainly due to the lack of independence between the produced hash functions. We introduce a new hash function family that attempts to solve this issue in any kernel space. Rather than boosting the collision probability of close points, our method focus on data scattering. By training purely random splits of the data, regardless the closeness of the training samples, it is indeed possible to generate consistently more independent hash functions. On the other side, the use of large margin classifiers allows to maintain good generalization performances. Experiments show that our new Random Maximum Margin Hashing scheme (RMMH) outperforms four state-of-the-art hashing methods, notably in kernel spaces. 1

Introduction

10 years after the first LSH [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF] version, hashing methods are gaining more and more interest in the computer vision community. Embedding visual feature spaces in very compact hash indeed allow to drastically scale up many computer vision applications (from 10 to 1000 times larger datasets). One advantage of hashing methods over trees or other structures is that they allow simultaneously effi-cient indexing and data compression. Hash codes can indeed be used either to gather features into buckets but also to approximate exact similarity measures by efficient hash code comparisons (typically a hamming distance on binary codes). Memory usage and time costs can therefore be drastically reduced. Hashing methods can be classified across three main categories: Data independent hashing functions: in these methods, the hashing function family is defined uniquely and independently from the data to be processed. We can distinguish the one based on randomized process, to which Locality Sensitive Hashing (LSH) functions belong (L p stable [START_REF] Datar | Locality-sensitive hashing scheme based on p-stable distributions[END_REF], min-hash [START_REF] Chum | Near duplicate image detection: min-hash and tf-idf weighting[END_REF], random fourier features [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF]), and the one based on a deterministic structuring, including grids [START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF], space filling curves [START_REF] Joly | Feature statistical retrieval applied to content-based copy identification[END_REF][START_REF] Poullot | Z-grid-based probabilistic retrieval for scaling up content-based copy detection[END_REF] or more recently, lattices [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF][START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF]. The randomized ones are usually considered as more adaptive to heterogeneous data distributions and are thus usually more efficient than deterministic hash functions. However, some recent works did show that using more complex lattices may be more effective [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF][START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF], at least under the L 2 metric and for the studied data distributions. Most recent research on randomized methods did focus more on new similarity measures, notably the work of Raginsky et al. who defined a hashing function sensitive to any Shift-Invariant Kernel [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF].

Data dependent hashing functions:

In that case, the hashing function family is defined uniquely only for a given training dataset and the hash functions usually involve similarity comparisons with some features of the training dataset. The objective of these methods is to closely fit the data distribution in the feature space in order to achieve a better selectivity while preserving locality as much as possible. Among the most popular methods, we can cite K-mean based hashing [START_REF] Paulevé | Locality sensitive hashing: A comparison of hash function types and querying mechanisms[END_REF], Spectral Hashing (SH) [START_REF] Weiss | Spectral hashing[END_REF] based on graph partitioning theory, subspaces product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] and Restricted Boltzmann Machine (RBM) [START_REF] Salakhutdinov | Restricted boltzmann machines for collaborative filtering[END_REF] based on the training of a multilayer neural network. KLSH [START_REF] Kulis | Kernelized locality-sensitive hashing for scalable image search[END_REF], is a slight different approach since its main objective was to generalize hashing to any Mercer kernel rather than outperforming data independent methods. In this last category, the training dataset contains additional supervised information, e.g. class labels [START_REF] Wang | Semi-supervised hashing for scalable image retrieval[END_REF][START_REF] Lin | Spec hashing: Similarity preserving algorithm for entropy-based coding[END_REF] or pairwise constraints [START_REF] Mu | Weakly-supervised hashing in kernel space[END_REF]. These methods usually attempt to minimize a cost function on the hash functions set, combining an error term (to fit training data) and a regularization term (to avoid over-fitting). Our method being fully unsupervised, we did not consider these methods in our experiments.

Efficiency improvements of data dependent methods over independent ones have been shown in several studies [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF][START_REF] Weiss | Spectral hashing[END_REF][START_REF] Salakhutdinov | Restricted boltzmann machines for collaborative filtering[END_REF]. But this acts only for limited hash code sizes, up to 64 or 128. Indeed, the drawback of data dependent hash functions is that their benefit degrades when increasing the number of hash functions, due to a lack of independence between the hash functions. This is illustrated by Figure 1 showing the performance of a standard LSH function compared to the popular Spectral Hashing method [START_REF] Weiss | Spectral hashing[END_REF], known to outperform several other data dependent methods. This conclusion is confirmed by [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF] who did show that their Shift-Invariant Kernel hashing function (data independent) dramatically outperforms Spectral Hashing for all hash code sizes above 64 bits. Our new method answers to the two limitations of previous data dependent methods: (i) It is usable for any Mercer Kernel (ii) it produces more independent hashing functions.

Hashing in kernel spaces

Let us first introduce some notations. We consider a dataset X of N feature vectors x i lying in a Hilbert space X. For any two points x, y ∈ X, we denote as x.y the inner product associated with X and x = √ x.x represents the norm of any vector x. We generally denote as H, a family of binary hash functions h : X → {-1, 1}. If we consider hash function families based on random hy-perplanes we have

h(x) = sgn (w.x + b) (1)
where w ∈ X is a random variable distributed according to p w and b is a scalar random variable distributed according to p b . When working in the Euclidean space X = R d and choosing p w = N (0, I) and b = 0, we get the popular LSH function family sensitive to the inner product [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF][START_REF] Kulis | Kernelized locality-sensitive hashing for scalable image search[END_REF]. In that case, for any two points q, v ∈ R d we have:

Pr [h(q) = h(v)] = 1 - 1 π cos -1 q.v q v (2)
Unfortunately, this hashing function family can not be generalized in arbitrary kernalized spaces. Let κ : X 2 → R denote a symmetric kernel function satisfying Mercer's theorem, so that κ can be expressed as an inner product in some unknown Hilbert space through a mapping function Φ such as κ(x, y) = Φ(x).Φ(y). We can still define a kernalized hashing function family as:

h(x) = sgn (κ(w, x) + b) = sgn (Φ(w).Φ(x) + b) (3)
But in that case, Φ being usually unknown, it is not possible to draw Φ(w) from a normal distribution. Recently, Raginsky et al. [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF], did introduce a new hashing scheme for the specific case of shift invariant kernels, i.e Mercer kernels verifying κ(x, y) = κ(xy). They notably define the following family sensitive to the RBF kernel:

h(x) = sgn (cos (w.x + b)) ( 4
)
where w is drawn from p w = N (0, γI), γ being the kernel band width, and b is uniformly distributed in [0, 2π].

Although it is proved that a unique distribution p w may be found for any shift invariant kernel, other shift invariant kernels have not been addressed for now. The proposed method is therefore limited to the RBF kernel.

The only method proposing a solution for any Mercer kernel is KLSH [START_REF] Kulis | Kernelized locality-sensitive hashing for scalable image search[END_REF]. In this work, the authors suggest to approximate a normal distribution in the kernel space thanks to a data dependent hashing function using only kernel comparisons. The principle is based on the central limit theorem which states that the mean of a sufficiently large number of independent random variables will be approximately normally distributed. The authors suggest to average p samples selected at random from X and to use a Kernel-PCA like strategy to whiten the resulting data. More formally, they define the following hashing function family:

h(x) = sgn p X i=1 w i κ(x, x i ) ! (5)
w = K -1 2 e t
where K is a p × p kernel matrix computed on the p training samples x i , and e t is a random vector containing t ones at random positions (in order to randomly select t indices among p). The authors show that interesting results may be achieved on diversified kernels. The performance of KLSH are however usually far from what we could expect with a real normal distribution. The convergence of the central limit theorem is indeed usually weak and depends on the input data distribution. A good way to show how this weak convergence affects the hashing quality, is to study KLSH in the linear case (i.e. by using κ(x, y) = x.y in KLSH algorithm) and to compare to a real normal distribution (or at least the normal distribution produced by a standard Gaussian generator). Figure 2 presents such result on ImageNet-BOF dataset (see section 5), by comparing the mean average precision of the exact 100-NN within the hash codes produced by both methods (see section 5 for details). It shows that the performance of KLSH is quickly degrading when the number of hash functions increases. For a hash code size of 256 bits, the mean average precision is several times lower.

Random Maximum Margin Hashing

Our claim is that the lack of independence between hash functions is the main issue affecting the performance of data dependent hashing methods compared to data independent ones. Indeed, the basic requirement of any hashing method is that the hash function provide a uniform distribution of hash values, or at least as uniform as possible. Non-uniform distributions do increase the overall expected number of collisions and therefore the cost of resolving them. For Locality Sensitive Hashing methods, we argue that this uniformity constraint should not be relaxed too much even if we aim at maximizing the collision probability of close points. More formally, let us denote as h p = [h 1 , ..., h p ] a binary hash code of length p, lying in B p = {-1, 1}

p , where the hash functions h i are built from a hash function family H. For data independent hashing methods, the resulting colli-sion probability follows:

Pr p (q, v) = Pr [h p (q) = h p (v)] = [f (d(q, v))]
p where f (.) is the sensitivity function of the family H for a given metric d(.), i.e the collision probability function of a single hash function. Data dependent hash functions usually aim at providing a better sensitivity function than data independent ones. They are indeed built to boost the collision probability of close points while reducing the collision probability of irrelevant point pairs. But when the hash functions are dependent from each other, we have:

Pr p (q, v) Pr p-1 (q, v) = Pr [h p (q) = h p (v)|h p-1 (q) = h p-1 (v)]
Without independence, the second term is usually increasing with p and more and more diverging from the initial sensitivity function. At a certain point, the number of irrelevant collisions might even be not reduced anymore. Following these remarks, we consider uniformity of produced hash codes as a primary constraint for building an efficient data dependent hash function family. For a dataset drawn from a probability density function p x defined on X, an ideal hash function should respect:

∀p ∈ N * , ∀h i ∈ B p h(x)=hi p x (x)dx = c ( 6
)
where c is a constant (equal to 1 2 p ). From this follows that (i) each individual hash function should be balanced (when p = 1):

h(x)=1 p x (x)dx = h(x)=0 p x (x)dx = 1 2 (7)
and (ii) all hash functions must be independent from each others.

In this work, we propose to approximate this ideal objective by training balanced and independent binary partitions of the feature space. For each hash function, we pick up M training points selected at random from the dataset X and we randomly label half of the points with -1 and the other half with 1. We denote as x + j the resulting M 2 positive training samples and as x - j the M 2 negative training samples. The hash function is then computed by training a binary classifier h θ (x) such as:

h(x) = argmax h θ M 2 j=1 h θ (x + j ) -h θ (x - j ) (8)
Now, the remaining question is how to choose the best type of classifier. Obviously, this choice may be guided by the nature of the targeted similarity measure. For non-metric or non-vectorial similarity measures for instance, the choice may be very limited. In such context, a KNN classifier might be very attractive in the sense that it is applicable in all cases. Using a 1-NN classifier for kernalized feature spaces would for exemple define the following hash function family:

h(x) = sgn max j κ(x, x + j ) -max j κ(x, x - j ) (9)
Interestingly, it is easy to show that such family is indeed sensitive to the expected number of shared neighbors. Shared neighbors information has already been proved to be a consistent similarity measure for clustering purposes.

Better classifiers may however be found for kernel spaces.

In this way, let us now consider the second main requirement of an ideal Locality Sensitive Hashing function family, that is preserving locality. Maximizing the collision probability of close points is indeed the primary principle of classical LSH methods. Within our balanced training strategy, we should thus minimize the probability that a point close to one of the training sample spill over the boundary between the two classes. In this context, maximizing the margin between positive and negative samples appear to be very well appropriated. This will indeed maximize the distance of all training samples to the boundary and guaranty that neighbors with a distance lower than the half margin do not spill over. This remark is closely related to Vapnik & Chervonenkis theory which states that large margin classifiers have low capacities and thus provide better generalization. We therefore propose to define our hash function family by the set of hyperplanes maximizing the margin between random balanced samples:

h(x) = sgn (w m .x + b m ) (10)
(wm, bm) = argmax w,b 1
w min » min j (w.x + j + b), min j (-w.x - j -b) - (11)
We refer to the proposed method as RMMH, for Random Maximum Margin Hashing. In practice, optimal hyperplanes w m can be computed easily by a Support Vector Machine (SVM). For kernel spaces, w m 's can only be expressed as a weighted sum over support vectors, so that the hash function becomes:

h(x) = sgn m i=1 α * i κ(x * i , x) + b m ( 12
)
where x * i are the m support vectors selected by the SVM (x * i ∈ x + j , x - j ).

Parameter M

The number M of samples selected for each hash function is the only parameter of RMMH. Deriving a theoretical optimal value for M unfortunately appears to be a tricky task. It would require to formally model the distribution p w of w m which is an open problem to the best of our knowledge. Some interesting logical guidelines can however be discussed according to three constraints: hashing effectiveness, hashing efficiency and training efficiency. Let us first discuss efficiency concerns. SVM training being based on quadratic programming, an acceptable training cost implies that M << N (even if it is an offline process). But hashing efficiency is even more critical: hash functions usually need to be computed online and the resulting cost is part of the overall search cost. In the linear case, this is obviously not a problem since a single projection on w m needs to be computed, making our method as efficient as normal projections. In kernel spaces however, the hashing cost is higher since we need to compute as much kernel values as the number of support vectors, for each of the p hash functions. Worst case hashing cost complexity is therefore O(pM ). So that an important requirement is that:

M << N p ( 13
)
Let us now discuss effectiveness concerns related to the two ideal objectives discussed above: uniformity and locality preservation. The larger the training size M and the better the uniformity. For an extreme value M = N (supposing that the capacity of the classifier is large enough to separate any training set of size N ), we would get a perfect uniformity and the probability of irrelevant collisions would be minimal. In other words, the data would be perfectly shattered, to re-use Vapnik-Chervonenkis terminology. But this would also lead to overfitting, since close pairs would be shattered as well. On the other extreme, too small training data would increase the error expectation of the classifier and thus degrade the expected uniformity. Data would be not shattered enough. The optimal value for M is thus guided by the a tradeoff between uniformity (data shattering) and locality preservation (generalization).

To estimate an approximate max bound on M , we can at least control the risk that close points might be split in the training data itself. Let us consider k-nearest neighbors as relevant matches and any other pair of point as irrelevant. In that case, the expected number of relevant pairs in a random training set of M points is equal to M 2 k N . If we want to have this expected number lower than 1, we get:

M < N k (14)
Interestingly, this value is sub-linear in dataset size N . With this max bound value, the hashing cost complexity O(pM )

becomes O(p N k ) which guaranties that it does not become preeminent for very large datasets.

Experiments

We used the 3 following datasets to conduce our experiments:

• SIFT: A set of about 11 M SIFT features [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] extracted from OxfordBuilding dataset2 (d=128).

• ImageNet-BOF: A set of 1.2 M Bags Of SIFT Features (d=1000) provided within Ima-geNet/PASCAL VOC Large Scale Visual Recognition Challenge (ILSVRC3 ).

• Wikipedia-DescX: X ∈ From these initial data we derived different subsets, either to study data size factor or to comply with implementation constraints of some of the state-of-the-art methods experimented in the paper. For example, SIFT-1M and BOF-100K correspond respectively to subsamples of 1M SIFT and 100K BOF.

All experiments are based on a leave-one-out procedure: 1000 queries are randomly selected from the dataset and removed one by one before being searched. Hash codes are compared with the Hamming distance and ranked accordingly. Performance is measured by the Mean Average Precision of the produced ranked list of results using the exact top k nearest neighbors as ground truth (k=100 when not specified). The metric used for generating the exact k nearest neighbors depends on the experiment and is discussed respectively. Quantization effects related to the Hamming space have to be considered when computing the Mean Average Precision: to compute the precision for a given neighbor v in the ground truth, we first compute the Hamming distance between its hash code and the query hash code. We then consider in the precision's calculation all items having a Hamming distance lower or equal to this value. For a better understanding of the results, we notice that low MAP values can still provide very interesting performances. Hash codes are indeed usually used only to filter the data, either within a hash table or by a direct scanning (as done in VA-file [START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF] for example). Retrieved results can still be refined or re-ranked afterwards with the original metric. For example, a map of 0.1 for k = 100 nearest neighbors means that on average 1000 points would need to be re-ranked.

Stability of parameter M

We first conduced an empirical study of M parameter. Figure 3 shows MAP curves when varying M value, for several data configuration. The first conclusion is that M always reaches an empirical maximum, which confirms our discussion of section 4 regarding the tradeoff between uniformity and locality preservation. It also shows that M is rather stable around its maximum and that it evolves only slightly for varying data sizes (from 10K to 1M) and varying number of neighbors (from 10 to 1000). The max bound we introduced in Equation 14is not always respected by the empirical optimum, but the order of magnitude is correct. In the following experiments of this paper, we used a fixed value M = 32.

Comparison to state-of-the-art

Euclidean space

We first evaluate RMMH in R d to allow comparisons to state-of-the-art methods. We used a dataset of 1 M SIFT features (SIFT-1M) normalized according to L2-norm, so that the exact k-nearest neighbors according to L 2 are equivalent to the exact top k items according to the inner product, the triangular L2 kernel or the RBF kernel. This allowed us to compare a quite large range of methods on this dataset: RMMH was experimented with 3 different kernels: linear, triangular L2 and RBF. For the RBF kernel, we estimated γ on real k-nn samples. We did compare RMMH to two data dependent methods (KLSH [START_REF] Kulis | Kernelized locality-sensitive hashing for scalable image search[END_REF] and spectral hashing [START_REF] Weiss | Spectral hashing[END_REF]) and two data independent methods (LSH and Random Fourier Features, the RBF-sensitive method of Raginsky et al. [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF] discussed in section 2). For Spectral Hashing and KLSH, we used the same number of training samples than the one required by RMMH (p × M ). For KLSH we used the L 2 triangular kernel, since we got the best performances with it. For LSH, we used the family sensitive to the inner product (equation 1). For Raginsky's method, we used the same RBF kernel parameter γ than for RMMH. Results are provided in Figure 4. They show that RMMH clearly outperforms the two other data dependent methods, whatever the used kernel, even the linear one. Thanks to the better independence of RMMH hash functions, the performance are indeed less degrading when increasing the hash code size. Comparisons to data independent methods show that RMMH performs better for a wide range of useful hash code sizes from 1 to about 800 bits which covers many hashing applications. Beyond the quite slight effectiveness gain, the most important point is that RMMH succeed in producing independent enough hash functions. This means that we can expect a good independence as well in kernel spaces (that cannot be addressed by data independent methods).

Kernel spaces

We now evaluate the performance of RMMH in other kernel spaces. We compare only to KLSH [START_REF] Kulis | Kernelized locality-sensitive hashing for scalable image search[END_REF], since it is the only one dealing with any Mercer kernel. We used a 10K subset of ImageNet-BOF with a Chi Square kernel and Wikipedia-HSV dataset with a Generalized Histogram Intersection kernel (GHI, [START_REF] Boughorbel | Generalized Histogram Intersection Kernel for Image Recognition[END_REF]). Results of Figure 5 confirm that RMMH outperforms KLSH.

Image retrieval performances

We now evaluate the performance of RMMH for image retrieval. The concern here is not to retrieve the k-nearest neighbors in the original feature space but the most relevant images. We therefore used the full ImageNet-BOF dataset with associated labels (1000 categories). We still used a leave-on-out procedure over 1000 random queries but we now run a k-nn classifier on the top k results retrieved by each evaluated method (i.e. the score of each category is determined by the number of instances retrieved in the top k hash codes. k was set up to 1000). As suggested in ILSVRC challenge, we relaxed the classification tolerance to the five best retrieved classes (recognition rate@5). We first did evaluate RMMH with 3 different kernels: Linear, Chi Square and Triangular L2. Results of table 1 show that the best kernel is the Chi Square one. However the gain over the linear kernel is very slight whereas the hashing complexity is much larger (as discussed in section 4). Overall, the linear kernel appears to be the best choice. Furthermore, it allows an interesting comparison between RMMH and the LSH family sensitive to the inner product (equ. 1). In this way, Figure 6

Indexing performances

We now evaluate RMMH in terms of indexing performances, using a multi-probe Locality Sensitive Hashing framework to reduce memory usage. We used the a posteriori multi-probe LSH method of Joly at al. [START_REF] Joly | A posteriori multi-probe locality sensitive hashing[END_REF] (AMP-LSH). It allows using any hash function whereas other multi-probe methods are focused on L 2 . In this experiment, we only used RMMH to construct the hash table and we kept the original data in the buckets. Of course, we can also replace the original features by RMMH hash codes to achieve even better speed-up and memory saving (as presented below). But our first goal here is to study the partition induced by RMMH for constructing hash tables. We present only the results on ImageNet-BOF which is more challenging than the SIFT dataset due to the higher dimension. It is important to notice that the sparsity of this dataset is rather weak (about 2/3 of null components), which means that an inverted list would fail to provide consistent efficiency gains (up to about 3 compared to exhaustive scan).

The used metric is the inner product and we did vary the dataset size from 100 features to 1 M features. We used the following AMP-LSH settings: quality control parameter α = 0.7, number of hash tables L = 1, number of searched nearest neighbors k = 100. The depth p of each table (i.e. the hash code size) depends on the dataset size thanks to the following empirical formula p = log 2 (N ) + 5 (values ranged from 11 to 25). RMMH was used with the linear kernel and M = 40. It was compared to the LSH family sensitive to the inner-product. For hardware independent comparisons, performances of the exhaustive scan are reported as well. Results are reported in Figure 7 and table 2. The plot shows that both LSH and RMMH achieve sub-linear search time in data size, providing consistent efficiency gains over the linear scan (which is not trivial with a dimension equal to 1000). But RMMH clearly outperforms LSH (as much as LSH outperforms the exhaustive scan). The sub-linearity coefficient of RMMH is indeed higher, leading to increasing efficiency gains when the size increases. That confirms again that RMMH closely fit the data distribution while keeping a good independence between the hash functions. For the full dataset of 1M BoF (see table 2), RMMH is finally 37 times faster than exhaustive scan and 5 times faster than LSH. In table 2, we finally report the performances obtained on the full dataset when replacing the original features by RMMH hash codes. We used 1024 bits for the hash codes and returned the 10K nearest hash codes (before re-ranking with the exact inner product). This combined strategy allows to divide the search time by 5 and the memory usage by 13.

Conclusion

We introduced a new hashing function family suitable for any kernel space and providing excellent performances in Euclidean space. Contrary to previous data dependent methods, we did not focus on boosting the collision probability of close points. We rather try to minimize the collision probability of irrelevant pairs by boosting the scattering of the data. We therefore suggest to train purely random splits of the data, regardless the closeness of the training samples or any kind of supervision. Experiments did confirm that the resulting hash functions are consistently more independent than other data dependent methods. On the other side, the use of large margin classifiers prevents from overfitting and provides good generalization capacities for neighboring data. Image retrieval experiments did show that no more than 64 bytes are enough to achieve similar performances than exact distances in a 1000-dimensional feature space. Indexing performances finally confirmed that RMMH produces better partitions than purely random projections.

In future works, we will continue investigating a theoretical modeling of RMMH. This would help defining accurate bounds for M parameter and provide a better understanding on how data structures are embedded (density, symmetry, etc.). We believe that RMMH could be useful for many other goals including dimensionality reduction, independent component analysis or feature selection.

Figure 1 .

 1 Figure 1. LSH vs Spectral Hashing for increasing hash code sizes

Figure 2 .

 2 Figure 2. LSH vs KLSH for increasing hash code sizes

[ 1 : 5 ]

 15 , 5 datasets of 237 K global visual features extracted from ImageClef wikipedia dataset 4 . The 5 global visual features are the following: Desc1=HSV histogram (d=120), Desc2=Fourier histogram ([5], d=49), Desc 3=Hough histogram ([5], d=40), Desc4=Weighted color histogram ([20], d=216).

Figure 3 .

 3 Figure 3. Impact of M parameter for various number of neighbors and various dataset sizes

Figure 4 .

 4 Figure 4. Comparison of RMMH to state-of-the-art methods (top) comparison to data dependent methods (bottom) comparison to data independent methods

Figure 5 .

 5 Figure 5. Comparison between RMMH and KLSH in 2 different kernel space: (top) GHI kernel (WIKIPEDIA-HSV dataset) (bottom) Chi2 kernel (ImageNet-BOF-10K)

Figure 6 .

 6 Figure 6. Classification performances on ImageNet-BOF

Figure 7 .

 7 Figure 7. search time vs data size -comparison of RMMH to LSH and exhaustive scan

  presents the classification rate of RMMH and LSH for varying hash code sizes. The horizon-

		Kernel		Linear Chi Square Triang L 2
	recognition rate@5	0.149		0.150		0.135
	Table 1. Classification performance of RMMH with 3 different
	kernels (ImageNet dataset, 128 bits)
	tal line corresponds to the classification rate obtained with
	the exact inner product in the original feature space. We
	can first remark that the gain of RMMH over LSH is much
	larger than previous experiments (when searching approx-
	imate k-nearest neighbors). That means that RMMH pro-
	vides a better embedding of the underlying data structure,
	whereas LSH only converges to the original metric. RMMH
	is even better than the exact distances for hash code sizes
	larger than 600 bits. Finally, with only 512 bits (64 bytes),
	RMMH hash codes provide equivalent performances than
	the original 1000 dimensional bag-of-features.
		0.20
		0.18
		0.16
	recognition rate@5	0.08 0.10 0.12 0.14
		0.06
		0.04				rmmh lsh
		0.02				exact
		0	200	400	600	800	1000	1200
				hash code size (#bits)

Table 2 .

 2 Indexing and Search statistics on ImageNet-BOF

	method	time (ms)	NN recall	Mem (Gb)
	Exhaustive	1777	1.0	5.05
	LSH index	247	0.67	5.11
	RMMH index	49	0.69	5.11
	RMMH index + sketch	10	0.62	0.39

Acknowledgement: This work was co-funded by the EU through the Integrated Project GLOCAL http://www.glocal-project.eu/ and by the French Agropolis foundation through the project Pl@ntNet http://www.plantnet-project.org/

http://www.robots.ox.ac.uk/ ˜vgg/data/oxbuildings/

http://www.image-net.org/challenges/LSVRC/2010/

http://www.imageclef.org/2010/wiki


Pierre Letessier
email: pierre.letessier@ina.fr

Olivier Buisson
email: obuisson@ina.fr

Alexis Joly
email: alexis.joly@inria.fr

Consistent Visual Words Mining with Adaptive Sampling

State-of-the-art large-scale object retrieval systems usually combine efficient Bag-of-Words indexing models with a spatial verification re-ranking stage to improve query performance. In this paper we propose to directly discover spatially verified visual words as a batch process. Contrary to previous related methods based on feature sets hashing or clustering, we suggest not trading recall for efficiency by sticking on an accurate two-stage matching strategy. The problem then rather becomes a sampling issue: how to effectively and efficiently select relevant query regions while minimizing the number of tentative probes? We therefore introduce an adaptive weighted sampling scheme, starting with some prior distribution and iteratively converging to unvisited regions. Interestingly, the proposed paradigm is generalizable to any input prior distribution, including specific visual concept detectors or efficient hashing-based methods. We show in the experiments that the proposed method allows to discover highly interpretable visual words while providing excellent recall and image representativity.

INTRODUCTION

State-of-the-art object retrieval systems have demonstrated impressive performances in very large image datasets. These methods, based on fine local descriptions and efficient matching techniques, can detect accurately very small rigid objects with unambiguous semantic such as logos, buildings, manufactured objects, posters, etc. Mining such small objects in large collection is a challenging task gaining more and more interest. Applying naively usual local queries methods might indeed be a tricky task. Constructing a full local matching graph with these methods would indeed require to probe all candidate query regions around each local feature leading to an intractable algorithm complexity.

To avoid querying all possible regions of interest while keeping a good coverage of the contents, we propose in this paper a weighted and adaptive sampling strategy aiming to select the most relevant query regions. Sampling is indeed a sim-ple yet efficient statistical paradigm allowing to yield some knowledge about a population without surveying it entirely. Adaptive weighted sampling is a more advanced paradigm allowing to iteratively update the sampling distribution according to the results obtained during previous iterations. This allows our mining method to progressively focus on unvisited image regions and consequently reduce the number of required probes for achieving a good completeness of the description. The resulting set of discovered objects can therefore be used as a new type of visual word vocabulary allowing to describe images with very compact global descriptions. We show in the experiments that better retrieval performances than those obtained with usual visual words might be achieved with extremely smaller vocabulary size (e.g. 3,000 visual words for the OxfordBuildings dataset). We therefore refer to the visual words generated by our method as Consistent Visual Words (CVW). A CVW is a set of image patches. These patches are described by local features sets. A CVW models a small rigid object, or a piece of a bigger object. A CVW is defined by the geometric consistency between the feature points of the considered patches.

Interestingly, the initial distribution used by our adaptive sampling method can be initialized with any prior knowledge, typically visual saliency measures or visual concepts detectors. The produced visual vocabularies might therefore be adapted to specific targeted objects or concepts. Besides Bag-of-Words description concerns, our method can simply be used for discovering instances of very small rigid objects in large datasets. We show as well in this context that our adaptive sampling matching method allows to reach high recall while being very flexible in terms of prior knowledge about the targeted objects.

RELATED WORKS

State-of-the-art object discovery and mining methods [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF][START_REF] Tuytelaars | Unsupervised object discovery: A comparison[END_REF] can be summarized by two main successive steps: matching graph construction, and analysis of this graph. The nodes of a matching graph typically represent images whereas edges correspond to common matching regions between the images. The first step to generate the matching graph is usually based on large scale object retrieval methods [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF][START_REF] Chum | Near duplicate image detection: min-hash and tf-idf weighting[END_REF][START_REF] Chum | Geometric min-hashing: Finding a (thick) needle in a haystack[END_REF]. The objectives addressed by the graph analysis methods are various and include: construction of the object models, objects linking or summarization. To discover or extract such information, most of these methods are based on Latent Topic Models such as probabilistic Latent Semantic Analysis (pLSA) [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] and Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF][START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF]. Most matching graph methods are based on Bagsof-visual-Words models (BoW), describing images from a set of quantized local features lying in a so called visual vocabulary. The visual vocabulary is usually generated by a K-means clustering algorithm [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] applied on the local features set of the considered corpus. Such representations are equivalent to standard vector-space models in text information retrieval allowing to efficiently measure similarity between items with classical operators (dot product, histogram intersection, etc.). It is important to notice that such similarities only consider global statistics of the image even if the sparsity of the vectors allows to somehow embed some local properties. This type of global strategies is therefore not adapted to discover very small objects representing small subparts of images. In [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF], for example, the objects having a size lower than 25% of the image area are not considered. So that usual BoW methods are mostly interesting for their excellent efficiency/effectiveness tradeoff not for their effectiveness in retrieving or mining objects.

When dealing with small objects, the most adapted methods to generate a matching graph are the one based on probing local query regions. This second type of strategies [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Jégou | Hamming Embedding and Weak Geometry Consistency for Large Scale Image Search[END_REF][START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF] independently consider each local feature of an image. They have been shown to be effective in retrieving small objects, such as trademark logos [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. To guarantee this quality level of precise objects retrieval, these methods stick on an accurate local description of the images. For a 10K image corpus, more than tens of millions local features are independently indexed. In these methods, the number of candidate local regions to be searched might thus be huge. Even with the most efficient indexing structures that drastically reduce the computational costs, the overall complexity remains too expensive to generate a full matching graph.

Instead of searching every candidate query regions, Chum et al. [START_REF] Chum | Near duplicate image detection: min-hash and tf-idf weighting[END_REF][START_REF] Chum | Geometric min-hashing: Finding a (thick) needle in a haystack[END_REF] propose to automatically select Regions Of Interest (ROI) with a very low computational cost. Their method combines BoW models with a Min-Hash hashing scheme [START_REF] Broder | On the resemblance and containment of documents[END_REF] and can be considered as a trade-off between global and local strategies. Min-Hash is an algorithm commonly used in text retrieval for finding near-duplicates [START_REF] Broder | On the resemblance and containment of documents[END_REF] and works by approximating the intersection between two sets of words. Applied on visual words, it allows to discover efficiently very discriminant candidate visual sketches that are likely to be parts of more reliable objects. But the recall of this method for small objects is far from sufficient as pointed out in further works of the authors [START_REF] Chum | Geometric min-hashing: Finding a (thick) needle in a haystack[END_REF]. The first Min-Hash/BoW method [START_REF] Chum | Near duplicate image detection: min-hash and tf-idf weighting[END_REF] was therefore only used to detect Image Near Duplicates. To reduce this drawback, [START_REF] Chum | Geometric min-hashing: Finding a (thick) needle in a haystack[END_REF] proposed a new Min-Hash based strategy called Geometric Min-Hash. In that method, the first Min-Hash value of the sketches is still generated from the whole image but the second and following hash values are randomly sampled in the spatial neighborhood of the first selected visual word. This version is able to discover more relevant local sketches and is therefore a very efficient way to discover candidate query regions that are likely to contain object instances. But the first global hashing step still makes it not robust to strong occlusions and the performances might therefore degrade in highly cluttered contexts. We also point out that this method might be used as an effective prior knowledge in our adaptive sampling matching method. To the best of our knowledge, our method is the first matching graph construction method directly based on probing local queries.

PROPOSED METHOD

Our proposed mining method is an iterative process composed of three main stages processed at each iteration: Adaptive Sampling of a query image region, Search of the selected local query region and Decision of whether this query region might be considered as a consistent visual word in the final output vocabulary. The full algorithm repeats these 3 steps T times until a fixed number of visual words has been found. More formally, let Ω be an input dataset of N images Ii, i ∈ 1, ..., N . Each image Ii is represented by a set of Ni local visual features Fi,j (typically SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF]) localized by their position Pi,j.

N F = P N-1 i=0
Ni is the total number of features Fi,j. Each local feature Fi,j is associated with a fixed candidate query region Ri,j defined as the bounding box centered around Pi,j, with height Hi,j and width Wi,j. In this paper, Hi,j and Wi,j are set up as fixed ratio of image width and height according to:

Hi,j = √ γ * Hi Wi,j = √ γ * Wi
where γ is a parameter of the method corresponding to the percentage of the image area covered by a candidate query region (Hi and Wi are respectively the height and width of image Ii). For example, a γ equals to 0.10 means that the query width will be equal to one third of the image width. This parameter is designed to adapt the query size and shape to those of the image. Now, the following three steps are processed at the t-th iteration :

1. Adaptive Sampling: This step proposes a candidate query region R t q , centered around a randomly selected feature F t q . The feature F t q is selected according to a probability mass function p t (i, j) over the set of all Fi,j. Such random sample can be generated easily from any distribution p t by using an inverse transformation method [START_REF] Devroye | Non-uniform random variate generation[END_REF] (also called Smirnov method). Such method consists in transforming a uniform random number by integrating the probability mass function up to an area greater than its value. The algorithm computing p t according to the results of the previous steps is detailed in section 3.1.

Local Region Search:

The candidate query region R t q (centered around F t q ) is processed by a three-step matching procedure described in section 3.2. It returns a set of geometrically verified matching regions in the dataset. We refer to any of these matched regions as R t m , m ∈ 1, ..., Mt.

Decision:

Matching scores are then normalized and thresholded according to the procedure described in section 3.3. If the final results set contains more than two images, it means that we have found a recurrent object in the database. This threshold can be adapted, depending on desired minimal frequency of retrieved objects. Then, the tentative query region R t q and the matching images R t m are kept to form a consistent visual word.

Finally, after T tentative probes, the algorithm outputs a vocabulary V of |V | T consistent visual words vt. Each visual word is associated with an image region R t q and represented by the set of local features belonging to R t q .

Adaptive Sampling

To avoid querying all possible regions of interest while keeping a good coverage of the contents, we propose a weighted and adaptive sampling strategy aiming at selecting the most relevant query regions. Sampling is a statistical paradigm concerned with the selection of a subset of individual observations within a population of objects intended to yield some knowledge about the population without surveying it entirely. If all items have the same probability to be selected, the problem is known as uniform random sampling. In weighted sampling methods [START_REF] Olken | Random Sampling from Databases[END_REF], the items might be weighted individually and the probability of each item to be selected is determined by its relative weight. In conventional sampling designs, either uniform or weighted, the selection for a sampling unit does not depend on the observations made during previous surveys. On the other side, adaptive sampling [START_REF]Adaptive sampling[END_REF] is an alternative strategy aiming at selecting more relevant sampling regions based on the results observed during the previous surveys. Our method starts with an initial probability mass function p 0 (i, j) over the whole set of candidate query regions Ri,j. This initial distribution might be either uniform or determined by some prior knowledge as discussed in Section 3.1.1.

Steps 1, 2 and 3 are then computed (see above) providing a selected query region R 0 q and a set of matching regions R 0 m , m ∈ 1, ..., M0. Further probability mass functions p t (i, j) are then updated in a recursive manner:

p t = f `pt-1 , R t-1 q , {R t-1
m } Ás done in conventional weighted random sampling methods [START_REF] Olken | Random Sampling from Databases[END_REF], the probability mass functions p t are in practice computed by normalizing a weighting function w t such as:

p t (i, j) = w t (i, j) P i,j w t (i, j) (1)
The recursive updates are thus rather computed on the weights:

w t = g `wt-1 , R t-1 q , {R t-1 m } Óur
proposed updating function g is defined as follows:

w t (i, j) = 8 > > > < > > > : 0 if Fi,j = F t-1 q α1 w t-1 (i, j) if Fi,j ∈ R t-1 q α2 w t-1 (i, j) if Fi,j ∈ ˘Rt-1 m ¯m w t-1 (i, j) otherwise (2)
The first condition means that the weights of already visited query region centers are set up to zero so that the probability to re-issue them as a new query is null (i.e. to guaranty a sampling without replacement).

The second condition aims at decreasing the weights of the features belonging to the previous query region R t-1 q , so that their probability to be re-issued as new query region centers is decreased. This avoids selecting new query regions that have too much overlap with previous query regions. The third condition aims at decreasing the weights of the features belonging to already matched regions, so that their probability to be re-issuing as new query region centers is also decreased. On the other side, the fourth condition keeps the weights of unmatched features unchanged. These three first conditions allow to iteratively focus the selected query regions on objects that were never found in previous steps. In practice, α2 is chosen to be greater than α1. Decreasing too much the weights of matched regions might indeed degrade the overall recall. This comment can be related to the success of query expansion methods [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF] aiming at boosting object retrieval recall by re-issuing different instances of the same object as new queries.

In our experiments we used:

α1 = 0.1 α2 = 0.5

Prior saliency measures

As discussed above, the initial probability mass function p 0 can be either uniform or determined by some prior knowledge. In this section we propose and discuss several prior distributions. A first group consists of generalist visual saliency measures that might be used in any case. The second group consists of specific priors aiming to focus on the discovered visual words on specific visual concepts. The core idea is that the visual vocabulary produced by our adaptive sampling method might be adapted to the user's query. We notice that the output score of any visual concept detector could be used as prior knowledge making our method widely generic (e.g. animals, plants, indoor/outdoor, etc.).

Generalist Saliency Measures The purpose of this group of priors is to guide the sampling process on informative regions according to some visual saliency measures. We describe here two saliency measures but any other of the literature might be used as well.

Spatial Density of Local Features:

The principle of this saliency measure is to emphasize centers of spatially dense regions since they are more likely to be the centers of interesting objects. Concretely, we measure for each local feature Fi,j the spatial density of its neighboring features with a Parzen window:

π D (i, j) = N i -1 X c=0 Kσ(Pi,j, Pi,c)
where Kσ is typically an RBF kernel. In our experiments, we chose two distinct values of σ for the vertical and horizontal coordinates (σx = W i 3 and σy = H i 3 ).

Feature Space Dispersion: One drawback of matching techniques is due to the degradation of performances on repeated structures (such as textured regions) because of an increasing probability of multiple matches [START_REF] Rabin | MAC-RANSAC: a robust algorithm for the recognition of multiple objects[END_REF]. To avoid such regions, we propose to measure the feature-space dispersion of the features belonging to a candidate region Ri,j. To estimate the dispersion, we simply average the variance along each dimension of the feature space:

π δ (i, j) = 1 d d-1 X l=0 VarR i,j (F [l])
where d is the dimension of the feature vector. A result of this saliency measure is illustrated in Figure 1.

Specific Saliency Measures

Figure 1: Feature space dispersion saliency measure -A hot color means that the center feature is different from its neighbors, a cold one means that it is likely to be in a texture region

Face saliency: In order to build face specific vocabularies of visual words, we implemented a prior distribution based on the OpenCV face detector 1 :

π F (i, j) = N f i -1 X l=0 K σ f i,l (Pi,j, P f i,l )
where K is the RBF kernel, N f i is the number of faces detected in image I i , P f i,l and σ f i,l are respectively the center and the scale of the l-th face in the current image i.

Image center saliency: In many applications, the assumption that the image center contains more objects of interest might be relevant. We therefore implemented the following saliency to boost the features closer to the image center:

π P (i, j) = Kσ(Ci, Pi,j)
where Ci is the center of image Ii and K the RBF kernel parameterized with σ x i = W i 8 , σ y i = H i 8 .

Transforming prior saliency measures into probability mass functions

We introduce here two generic schemes to transform any saliency measure into a probability mass function p 0 . Linear function: For a given saliency measure π, we define the initial weighting function w 0 as

w 0 (i, j) = π(i, j) -minπ maxπ -minπ
where minπ and maxπ are respectively the minimum and maximum values reached by the saliency measure on the whole dataset. p 0 is then obtained from w 0 with Equation 1.

Rank-based function:

For a given saliency measure π, we rank every value π(i, j) and use the resulting ranks as initial weights:

w 0 (i, j) = N F -ρ(i, j) N F
where N F is the total number of features and ρ(i, j) the rank of the feature Fi,j. p 0 is then obtained from w 0 with 1 http://sourceforge.net/projects/opencvlibrary Equation 1.

Our different experiments demonstrate that Linear function is adapted for π D (i, j), π F (i, j), π P (i, j) and Rankbased function is better for π δ (i, j).

Local Region Search

For local region search, we used the following retrieval framework proposed in [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. In this step, a region R t q is a local query Q represented by a set of nq features Fqi, with corresponding positions Pqi for i ∈ 1, ..., nq. The Local Region Search method works as follows:

STEP 1 -SIFT's matching Each query feature Fqi is matched to the dataset thanks to an efficient approximate similarity search technique. We used the recent A Posteriori Multi-Probe Locality Sensitive Hashing (APMP-LSH) method proposed by Joly et al. [START_REF] Joly | A Posteriori Multi-Probe Locality Sensitive Hashing[END_REF] that allows sublinear search time with reduced memory space costs. This Approximate Nearest Neighbor search method has a parameter α to control the search quality. This parameter allows to control the trade-off between search quality and efficiency. This control is very important to limit the computational costs in function of the desired performances. We study the effects of α in Section 4.3. To drastically improve the performances, we combine the APMP-LSH with Hamming Embedding [START_REF] Dong | Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces[END_REF][START_REF] Jégou | Hamming Embedding and Weak Geometry Consistency for Large Scale Image Search[END_REF]. This Embedding reduces the memory costs of the local descriptors and replaces the L2 distance with Hamming Distance.

STEP 2 -Filtering of potential matching images Then, we keep only the retrieved images which have more than a given number of matching features for the next step.

STEP 3 -Geometric consistency For each remaining image result, we compute a geometric consistency score by estimating an affine transformation model between the query and the retrieved images. An affine transformation model (Aj ,Bj) with 5 degrees of freedom is first estimated for each remaining image by a RANSAC algorithm. Finally, the similarity score of an image Ij for query Q is given by the number of inliers according to the affine transformation model:

SQ(Ij) = M j X m=1 δ( Pqm -AjPjm + Bj ≥ t) (3)
where δ(d ≥ t) equals 1 if d ≥ t and 0 otherwise. t is a fixed threshold setting the position error tolerance (t = 8). Mj is the number of matches kept in image Ij after step 2, Pqm and Pjm are the query and matched spatial coordinates of the p-th match in image Ij. The output is a list of images ranked in the decreasing order of the number of inliers SQ(I).

Decision

To decide if the tentative query region R t q is kept as a part of a consistent visual word, we filter the previous results by normalized scores which are obtained by an a contrario normalization technique [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. The a contrario normalization technique allows to accurately control the percentage of false alarms. This method involves a consistent visual word selection with a low level of false alarms. This technique is based on an estimation of the false alarms distribution Nfa (S) with respect to the discrete random variable S = SQ(I), I ∈ Ω. According to Equation 3, SQ depends only on the set of Mj spatial coordinates pairs corresponding to the np matches found in Step 1. High SQ scores are thus directly related to the statistical dependence between the spatial positions of the query and the matched features. We thus define our a contrario background model by the probability mass function pfa (S) of the variable S under the hypothesis H Q 0 that Pqm and Pjm are mutually independent random variables for all j:

pfa (S) = Pr[SQ(I) = S | H Q 0 ]
The cumulative distribution function Nfa (S) can be obtained by:

Nfa (S) = S X s=0 pfa (s)
We finally keep as the normalized score ŜQ(I) an estimation of the results precision according to Nfa (S):

ŜQ(I) = #{Ij ∈ Ω, SQ(Ij) > SQ(I)} -N. Nfa (SQ(I)) #{Ij ∈ Ω, SQ(Ij ) > SQ(I)}
In practice, we estimate the probability mass function pfa (S) for each query Q by a Monte Carlo simulation. We generate independent spatial positions of the query features Pqm and we keep the matched positions Pjm unchanged. More precisely, we affect to a given query feature Fqi a new spatial position Pqj randomly selected among the other points positions of the query. Compared to a purely uniform random generation of point positions, this method has the advantage to preserve some prior knowledge about the points distribution, such as bounds and principal orientations. We then simply recompute Step 3 and we estimate pfa (S) by counting the number of results having a score SQ equal to S. To limit the estimation bias due to the presence of correct images in the random results list, we only keep in the count the results having a score higher than the one obtained with the normal query.

EXPERIMENTS

Software Implementation

To reduce the main computational costs which is the Approximate Nearest Neighbor search of each query local feature, we developped a Thread Safe index structure based on A Posteriori Multi-Probe Locality Sensitive Hashing (APMP-LSH) [START_REF] Joly | A Posteriori Multi-Probe Locality Sensitive Hashing[END_REF] and Hamming Embedding [START_REF] Dong | Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces[END_REF][START_REF] Jégou | Hamming Embedding and Weak Geometry Consistency for Large Scale Image Search[END_REF]. The Thread Safe version of APMP-LSH provides a shared index structure between different threads, that avoids the duplication of data. Our tests of this version show that on two 4-cores processors (with HyperThreading), the optimum computational costs are obtained with 24 threads. These 8 cores and 24 threads provide a gain factor of 6 compared to 1 core and 1 thread. To drastically improve the performances, we combine the Thread Safe version of APMP-LSH with Hamming Embedding. This embedding reduces the memory costs of the local descriptors and replaces the L2 distance with Hamming Distance. Our different experiments in terms of object retrieval performances (mean Average Precision) has shown that the SIFT descriptors represented with 128 bits in the Hamming space provides equivalent performances than the 32 bits float precision version in the Euclidean space. In this case, the compression factor is 32. Moreover, the use of Hamming distance allows to reduce the computational costs compared to L2 distance. The fast Hamming distance implementation is composed of two steps: XOR operation between two descriptors and counting of number of bits set to 1 of the previous result. The standard version fast Hamming distance is based on a lookup table to count number of bits set to 1. Instead of using this version, we count number of bits set to 1 with a SSE4.2 instruction2 : popcnt. This instruction allows to divide by 4 the computational costs compared to the lookup table version.

Datasets

During our evaluations, we use the following image datasets:

-BelgaLogos (BEL): The BelgaLogos dataset [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF] 3 is composed of 10,000 news images. A manually annotated ground-truth for 26 logos and 55 queries where each query is a logo is provided with this dataset. This dataset is adapted to evaluate small objet retrieval performances. For the current evaluations, we describe this corpus with 38 millions of SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF].

-OxfordBuildings (OXF): The 5,000 images of Oxford Buildings dataset4 are composed of buildings from Oxford and miscellaneous images. A ground-truth is provided for 55 queries where each query is a piece of a building. For the current evaluations, we describe this corpus with 30 millions of SIFT.

To evaluate the objet retrieval performances, we mainly use the usual criterion: mAP (mean Average Precision) computed between our retrieval results and the provided groundtruth.

Parameters Tuning for Local Region Search

To evaluate the involvements of our Adaptive Sampling method, we need to choose the parameters of Local Region Search. Our different experiments of APMP-LSH coupled with Hamming Embedding allows us to use the following parameters: 128 bits for the Hamming Embedding representation of SIFT, 300 for the KNN size. We evaluated these parameters with the two considered datasets (with α = 90%) and we obtain: mAP = 0.30 for BEL and mAP = 0.72 for OXF. In [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF], the system without Query Expansion has a mAP = 0.20 with 11 millions of SIFT for BEL and a mAP = 0.608 with 12 millions of SIFT for OXF. The main difference of performances is due to the use of more SIFT descriptors than in the experiments of [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF].

The computational costs of each Tentative Probe mainly depend of the Local Region Search complexity. This complexity can be changed by the parameter α of the APMP-LSH which allows to control the trade-off between the KNN retrieval quality and the computational cost. Specifically, the value of α is the rate of KNN that we are statistically ensured to retrieve with the approximative search of APMP-LSH. To choose an adapted value for α, we tested a serie of α values for the Local Region Search applied on OXF dataset. We then observed the variation of the mAP depending of α (and by consequence the execution time) in Figure 2. This figure perfectly shows that it is not profitable in terms of mAP and computational cost to use an α value greater than 80%. Therefore we will use this value for the following experiments.

Adaptive Sampling and Priors Evaluation

The curves on the Figure 3 have been created with the BelgaLogos dataset, α = 80%, and un-weighting factors α1 = 0.1 and α2 = 0.5. They show that after 10,000 tentative probes, updating the sampling distribution allows to cover a greater surface. We can also see that using the prior spatial density speedsup the discovering process very early. For 70,000 tentative probes with the prior spatial density, we cover 10% more than without update.

Figure 4 illustrates the effect of updating the weighted distribution. We stopped our two tests (with and without update) when the same number of words has been created. The left image shows a lot of overlapping words, while the right image presents almost the same covered area, with Figure 5 shows that priors significantly improve the mAP. We demonstrate that adding a priori information based on our knowledge of the database ("objects of interest are often centered in the photography", or "the best described areas are more discriminant") can speed up the object discovery. We also see that focusing on non-texture areas gives better results.

The tests were made on OXF dataset with a low quality of feature retrieval (α = 40%), in order to gain time and to allow us to make 10 runs for each prior. We then computed the median curves.

Small object discovery

To observe the effect of the priors on the type of objects detected, we launched 3 runs per prior. Each run stopped after having generated 600 words. Then we manually counted the mean number of detections for each prior/type pair among the words having over 5 matching images.

As we can see in Table 1, without using a prior, we mostly detect textured objects, which are not often very interesting. We show that we can decrease this number of textures and therefore increase the number of objects of interest, like logos. The use of an appropriate prior allows to discover a minimum of 47 faces or 70 logos, among 600 visual words and 10,000 images, in less than 15 minutes.

Without prior Dispersion

Bags Of Consistent Visual Words Evaluation

We would like to illustrate that our consistent visual words are highly discriminant and robust. To demonstrate it, we propose to construct Bags-of-Consistent-Visual-Words to compare to the state-of the art methods based on BoW. Our proposal is a strategy equivalent to the BoW in [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF], but in our case, we replace the descriptor quantization by our consistent visual words. For OXF dataset, to our knowledge [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF] has the best performances in terms of mAP score: 0.825. In [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF], to get these performances, their proposal is based on BoW, Scalar Product as the similarity measure and Recursive Average Query Expansion method. With our Bags-of-Consistent-Visual-Words, we also used the Scalar Product and the Recursive Average Query Expansion method. Table 2: Comparison between the best BoW method (reproduced from [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF]) and our consistent visual words

In [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF], the size of their visual vocabulary is 1 million and each image is described with an average of 3,000 SIFT. As we can see in Table 2 and in Figure 7, we achieve our best mAP score (0.861) in less than 4 hours with only 5,576 words, and a mean of 9.14 words for each image. We can also notice in Figure 7 that we can reach a high mAP with a very few words. For example, a minimum of 2,500 words allows us to obtain a state-of-the-art score, while with only 250 words we got over 0.50 of mAP, in approximately 10 minutes. In the case of Bags-of-Words indexed by inverted lists, this low number of words involves a high degree of compression and a very fast similarity search.

CONCLUSION AND FUTURE WORKS

We have proposed the concept of consistent visual words and the experiments show that this type of words is very effective to describe and retrieve local visual contents. The experimentations with OXF demonstrate that these consistent visual words largely overcome the usual visual words. To generate consistent visual words, we developed a framework based on Adaptive Sampling and Priors.

The core idea is that the visual vocabulary produced by our adaptive sampling method might be adapted to what the user is searching for. We observe that any visual concept detector (e.g. animals, plants, indoor/outdoor, etc.) could be used as prior knowledge, which demonstrates that our method is widely generic.

This framework is very flexible and it is easy to integrate information by formulating a specific prior.

In future works, we plan to study the effects of the parameter γ which defines the maximum scale of consistent visual words. We could also propose to adapt this object scale in function of image contents and then the local region queries could be adaptive. To reduce the number of Tentative Probes, we would like to develop new types of priors, and to study the fusion of different priors. For example, we could fuse the priors by using the standard AND and OR Probabilistic Operators.

Figure 2 :

 2 Figure 2: Trade-off between precision and time (features retrieval quality)

Figure 3 :

 3 Figure 3: Comparison of the covered surface versus the number of tentative probes with or without using the update of the sampling distribution, and with the prior density

Figure 4 :

 4 Figure 4: Bounding boxes of the consistent visual words generated on the same image without update (left image) and with update (right image)

Figure 5 :

 5 Figure 5: Comparison of priors

Figure 6 :

 6 Figure 6: Examples of twelve generated CVW represented by one of their patches. The original images are cropped around the matching regions. 1 st row: Miscellaneous objects, 2 nd row: Logos, 3 rd row: Textures, 4 th row: Faces

Figure 7 :

 7 Figure 7: Test on OXF using α = 85% and image center prior

Table 1 :

 1 Number of detection per categories and priors

				Face
	Objects	31	53	20
	Logos	46	70	27
	Textures	72	26	23
	Faces	12	13	47

http://en.wikipedia.org/wiki/SSE4

http://www-rocq.inria.fr/imedia/belga-logo.html

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

ACKNOWLEDGEMENTS

This work was partially funded by the EU through the Integrated Project GLOCAL (http://www.glocal-project.eu), and by ANR (France) through the Project OTmedia (www.otmedia.fr).