David Picard

Philippe-Henri Gosselin

Efficient image signatures and similarities using tensor products of local descriptors

Keywords: Image retrieval, Image indexing, Image Similarity, Feature Vector

In this paper, we introduce a novel image signature effective in both image retrieval and image classification. Our approach is based on the aggregation of tensor products of discriminant local features, named VLAT (vector of locally aggregated tensors). We also introduce techniques for the packing and the fast comparison of VLATs. We present connections between VLAT and methods like kernel on bags and Fisher vectors. Finally, we show the ability of our method to be effective for two different retrieval problems, thanks to experiments carried out on similarity search and classification datasets.

Introduction

Content Based Image Retrieval (CBIR) has been a main topic of interest at the the crossroad of many research communities for the last 20 years. These communities include (but are not limited to) Image Processing, Computer Vision, Machine Learning and Data Mining. During these years, interesting results were obtained on image collections designed on purpose by the community. With the tremendous amount of available images, CBIR is now even more challenging. For instance, Flickr repository contains more than 6 billion images as of 2011. These amounts also increased the number of searched concepts, and raised the need for computational efficiency. In [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF], Smeulders et al. identify several main areas for CBIR, depending on what the user intends, like image search and image classification tasks.

In the search task, we are interested in the fast retrieval of a single image and its near duplicates within a very large collection [START_REF] Amsaleg | Content-based retrieval using local descriptors: problems and issues from a database perspective[END_REF]. For instance, let us consider a collection of images taken from Paris streets. A typical search query could be to retrieve all images of the front side of the Sacré Coeur. The query can be instantiated by presenting an example image to the system, or by typing a keyword. In such system, the collection is huge (up to several millions of images), and the resulting sets are small (usually less than ten images). The main challenges are threefold. The first one is to obtain a good recall, i.e. to retrieve almost all targeted images. The second challenge is to perform the retrieval with low computational complexity with respect to the collection size. In many cases, sub linear complexity is targeted [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF][START_REF] Akune | Monorail: A disk-friendly index for huge descriptor databases[END_REF][START_REF] Ólafsson | Dynamic behavior of balanced nv-trees[END_REF], but linear complexity can also be relevant if indexes are small and/or similarity can be computed very quickly [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. The third challenge is to lower the storage cost of the indexing method [START_REF] Lejsek | Nv-tree: Nearest neighbors at the billion scale[END_REF].

Email addresses: picard@ensea.fr (David Picard), gosselin@ensea.fr (Philippe-Henri Gosselin) In the classification task, the goal is to label a collection of images with respect to a set of predetermined semantic categories. The categories are well defined objects (such as persons, cars, etc) or more complex semantic grouping of images (such as indoor, landscapes, urban areas, etc). Recent methods make a heavy use of machine learning techniques, such as SVM [START_REF] Cortes | Support-vector networks[END_REF][START_REF] Tong | Support vector machine active learning with application to text classification[END_REF][START_REF] Gosselin | Combining visual dictionary, kernel-based similarity and learning strategy for image category retrieval[END_REF] or Boosting [START_REF] Freund | Experiments with a new boosting algorithm[END_REF][START_REF] Tieu | Boosting image retrieval[END_REF]. A classifier is trained for each desired concept on a separate image set where corresponding labels are available. These classifiers are then used to label the collection. In such systems, the main challenges are twofold: firstly, to produce accurate classifiers, and secondly to perform the labeling in reasonable time.

In this paper, we introduce a novel image signature for image search and image classification tasks. We first present in the second section the characteristics of these tasks, and an overview of state of the art approaches in these scopes. Then we detail our propositions based on tensors aggregation in the third section, and techniques to save memory and computations. In the fourth section, we present results for similarity search and classification tasks on Holidays and VOC2007 datasets. In the last section, we discuss the relationships between our propositions and current methods from the literature.

State of the art image signatures and similarities

As stated in the introduction, CBIR offers several challenging tasks. Thus, current retrieval systems often differ depending on which tasks they address. However, we can identify from all systems a significant number of similar processing stages. The first one is the automatic extraction of a set of highly discriminant local features from the images [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Bay | Surf: Speeded up robust features[END_REF]. This set can be the result of specifically detected or uniformly sampled regions of interest [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF]. In all cases, we assume in this paper that a set

B i = {b ri } r of vector descriptors b ri ∈ R D are extracted from image i.
The goal of the hereby studied step is to produce an image signature and the associated similarity measure. It that can ei-ther be used for database indexing in the case of the search task, or be taken as input by a learning machine in the case of the classification task. In this scope, two main approaches can be highlighted. The first consists in keeping all descriptors from each image, and then in designing complex similarity measures on these sets. The second approach produces a single vector from the aggregation of all descriptors and uses standard vector based similarities.

Kernels on Bags approaches

Given two sets (named bags) B i and B j of local descriptors extracted from image i and image j, and a similarity function k(•, •) on descriptors, a simple way of measuring the similarity K(•, •) over the bags is to compute the sum of similarity of all possible pairing between elements of B i and B j :

K(B i , B j ) = r s k(b ri , b s j ) ( 1
)
This approach is known as the kernel on bags method and has been widely studied in the machine learning community [START_REF] Shawe-Taylor | Kernel methods for Pattern Analysis[END_REF]. Providing k is a kernel, it is easy to prove that K is also a kernel and thus can be used with any kernel learning algorithm.

However, the sum kernel often offers low discriminative output, since it is the average similarity between elements of the bags. It is even more the case when the number and variety of descriptors in bags increase. To tackle this problem, Lyu proposed a refined sum kernel by increasing the discriminative power of the minor kernel k [START_REF] Lyu | Mercer kernels for object recognition with local features[END_REF]:

K lyu (B i , B j ) = r s k(b ri , b s j ) p (2)
Providing k has output in the range [0, 1], power parameter p ≥ 1 increases the discriminative ability of the minor kernel. Thus, only highly similar elements of the bags will be accounted for.

Gosselin et al. [START_REF] Gosselin | Kernel on bags for multiobject database retrieval[END_REF] further refined the power sum kernel by approximating a soft max function over the similarities between elements in the bags:

K so f tmax (B i , B j ) =        r s k(b ri , b s j ) p        1 p (3)
When p increases, k tends to the maximum similarity k(b ri , b s j ) among possible pairs (b ri , b s j ). It is however not known if this function is a Mercer kernel. In practice, it is observed to be semi-definite positive (sdp) on many datasets.

Further investigations on kernel on bags similarities have been proposed recently, which have been proven to be successful in many areas such as image retrieval, interactive search and graph matching [START_REF] Gorisse | Fast approximate kernel-based similarity search for image retrieval task[END_REF][START_REF] Lebrun | Inexact graph matching based on kernels for object retrieval in image databases[END_REF][START_REF] Haugeard | Kernel on graphs based on dictionary of paths for image retrieval[END_REF].

The main drawback of kernel on bags methods is their high computational cost. The average cost is O(T 2 D) where T is the average size of the bags and D the dimension of local features. For very large bags (several thousands of features), the cost becomes prohibitive, especially if the similarity is used intensively by the learning algorithm. Although acceleration schemes have been proposed [START_REF] Gorisse | Scalable active learning strategy for object category retrieval[END_REF], we believe this prohibitive cost is the main argument why kernels on bags have not been widely used in CBIR.

Aggregating approaches

A way of getting rid of the complexity of the bags is to find a mapping function encoding a set of descriptors into a single vector.

Bag of Words

Historical approaches for mapping the set of descriptors into a single vector compute a visual codebook composed of prototypes of descriptors, and then find the occurrences of these prototypes (denoted visual codewords or visual words) within an image [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Jurie | Creating efficient codebooks for visual recognition[END_REF][START_REF] De Campos | Images as Sets of Locally Weighted Features[END_REF]. The codebook is generally obtained by clustering a large set of descriptors. The approach is known as the "Bag of Words" (BoW) method, and has been adapted from text retrieval methods.

A simple way of mapping a set of descriptors into a vector is to compute a histogram of visual words. Further improvements consist in changing the value added to the related bin of the histogram. Gemert et al. [START_REF] Van Gemert | Visual word ambiguity[END_REF] propose various schemes based on visual word ambiguity, where the assigned value is related to the similarity of the descriptor to the selected visual word, and can be normalized with respect to its similarity to other visual words.

Coding/pooling schemes

In [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], the authors propose to decompose the BoW approach into two distinct steps. The first step, called the coding step, involves the mapping of a single descriptor onto the codebook. In the second step, called the pooling step, all mapped descriptors are aggregated into a single vector.

In first BoW approaches, the values of a mapped descriptor are all zeros, except for the dimension corresponding to the closest visual word. The pooling step is simply the sum of all mapped vectors.

In the coding scheme of [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], a mapped vector α is the result of a reconstruction problem :

α = argmin α ||b -Wα|| 2 + ||d • α|| 2 (4)
With b being a descriptor, W the codebook matrix, α the projection coefficients and d a locality constraint (e.g. farther visual words have a higher cost than closer words). The output vector α is thus optimized with respect to its reconstruction error and constrained to the projection on few nearby codewords.

They also propose an alternative to the sum pooling step by computing the maximum coefficient among descriptors of the set. The max pooling step is shown to have great impact on the classification performances [START_REF] Boureau | Learning mid-level features for recognition[END_REF].

Other pooling steps include taking into account the spatial distribution of visual words. In [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], the authors propose a spatial pyramid matching scheme (SPM) where descriptors are aggregated in a subarea of the image depending on scale parameters, inspired by the Pyramid Matching Kernel of [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF].

Fisher Vectors -VLAD

More recently, Perronnin et al. [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] proposed a novel approach to map a set of descriptors to a single vector. In this method, the authors assume that the bag of descriptors B i can be modeled by a Gaussian mixture, with a probability density function denoted as u λ of parameters λ. The derivative of the log-likelihood of B i with respect to the parameters describes each parameter contribution to the global likelihood:

G B i λ = 1 T ∇ λ log u λ (B i ) (5)
Using the Fisher information matrix, one can rewrite this derivative such that the dot product between rewritten vectors is an efficient kernel. The mapped vectors are thus the following for each Gaussian c:

G B i µ,c = 1 T √ ω c r γ c (b ri ) b ri -µ c σ c , (6)
G B i σ,c = 1 T √ ω c r γ c (b ri ) (b ri -µ c ) 2 σ 2 c -1 , (7)
Where (ω c , µ c , σ c ) are the weight, mean and standard deviation of Gaussian c, and γ c (b ri ) the normalized likelihood of b ri to Gaussian c. The output vector is obtained by concatenation,

G µ = c G B i µ,c and G σ = c G B i σ,c . The final feature vector is of size 2 × D × C,
where D is the dimension of input space and C the number of Gaussians.

To our knowledge, Fisher vectors and related methods obtain state of the art classification performances when using single SIFT descriptors with linear classifier and when properly normalized [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. These properties make them attractive for large scale classification challenges, as linear classifiers are almost costless compared to kernel based classifiers. Furthermore, the number of Gaussians needed to achieve good performances is far less than the typical size of the codebook in the BoW approaches. The clustering of high-dimensional spaces in many cluster being a difficult task, the Fisher vectors method is consequently more robust.

In [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], Jegou et al. propose an approximation of Fisher vectors by aggregating local descriptors (VLAD -Vectors of Locally Aggregated Descriptors). Given a codebook obtained by clustering a large set of descriptors, they compute the centered sum of all descriptors B ci = {b rci } r ⊆ B i from image i and cluster c:

ν c = r b rci -µ c (8)
The output vector is obtained by concatenating ν c for all c, and is thus of size D×N. Note that VLAD and FV are used with smaller codebook (from 16 to 4096) than BoW related techniques (from 4000 to millions). Consequently, the computation of the codebook is faster, and results are more stable from one codebook to another.

VLAT -A tensor based aggregation

Our approach extends VLAD by aggregating tensor products of local descriptors, hence the name Vector of Locally Aggregated Tensors (VLAT). Preliminary results were published in [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. We first compute a visual codebook of C visual words over a sample image set S using k-means. Let us denote µ c the center of cluster c and T c the mean tensor of centered descriptors belonging to cluster c:

µ c = 1 |c| i r b rci (9) T c = 1 |c| i r (b rci -µ c )(b rci -µ c ) , (10)
With |c| being the total number of descriptors in cluster c for the whole image sample set S , and b rci the descriptors of image i belonging to cluster c.

To compute the signature of an image i, and for each cluster c, we aggregate in T i,c centered tensors of centered descriptor:

T i,c = r (b rci -µ c )(b rci -µ c ) -T c ( 11
)
Each T i,c is flattened into a vector v i,c . The VLAT signature v i for image i consists in the concatenation of v i,c for all clusters c:

v i = v i,1 . . . v i,C (12)
The size of then VLAT is C × D × D, with C the number of clusters and D the dimension of descriptors. However, due to symmetry in the proposed tensors, half of the coefficients are discarded.

For each cluster c, v i,c can be seen as the difference between the covariance matrix of descriptors in B i belonging to cluster c and the covariance matrix T c of cluster c. VLAT thus measures deviations of second order statistics of image i with respect to a reference cluster c, whereas VLAD measures deviations of first order statistics only. Theoretically, higher order of tensors can be considered, measuring deviations of higher order statistics in B i with respect to cluster c.

As in [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF], we can further improve VLAT by applying proper normalization steps. First we compute the power norm of v i to produce vector v i , which is simply raising each coordinate j of v i to power α:

∀ j, v i [ j] = sign(v i [ j])|v i [ j]| α , (13)
With α = 0.5 as a typical parameter value. Then, we compute the signature x i of image i by applying 2 -norm to v i :

x i = v i ||v i || 2 (14)
It is worth noticing that VLAT is very easy to compute and does not require complex models of the feature space. Any method producing a clustering of the descriptors can be used to obtain the signatures. Moreover, VLAT is very fast to compute on current CPU and GPGPU, since most computations are performed with simple linear algebra.

Scalability issues -packing

The size in VLAT signature is quadratically increasing with descriptor space dimension D, and thus quickly leads to large feature vectors. A first and simple way of reducing this overhead is to apply principal component analysis (PCA) to visual descriptor space. Typically, SIFT descriptors can be reduced from D = 128 to D = 64 dimension with negligible lost of information. Furthermore, PCA can be used to perform a whitening step before VLAT computations.

In order to save memory use, we propose a packing procedure to reduce the size of VLAT indexes. The idea is to store the tensor of cluster c for image i in a format close to the original expression, i.e. a bag of virtual descriptors {p r ci } r ci . Similarly to Eq. ( 11), the approximate aggregated tensor is expressed using {p r ci } r ci :

P i,c = n ci r =1 λ r ci p r ci p r ci -n ci T c ( 15
)
where we chose the parameters {(λ r ci , p r ci )} r such as the error with the original tensor T ic is minimized. We evaluate this error as the relative Euclidean distance between the two tensors:

Err(P i,c , T i,c ) = ||T i,c -P i,c || ||T i,c || (16)
The parameters {(λ r ci , p r ci )} r are computed using an eigendecomposition of image descriptors B ci falling in cluster c:

B ci = P ci Λ ci P ci = n ci r=1 λ r p rci p rci ( 17
)
where P ci is an orthonormal matrix and Λ ci a diagonal matrix.

Next we select the n ci largest eigenvalues such as a target error is reached. Let us note that the error can be easily computed since the p rci vectors are orthonormal:

||T i,c -P i,c || 2 = || n ci r=1 λ r p rci p rci - n ci r =1 λ r p r ci p r ci || 2 = || n ci r=n ci +1 λ r p rci p rci || 2 = n ci r=n ci +1 λ 2 r
A first use of this packing procedure for the comparison of two images i, j is to reconstruct VLAT estimates Ti,c and T j,c using the packed VLATs P i,c and P j,c , and then compute the dot product Ti,c , T j,c . This is relevant for small codebooks, but with larger ones, it is much more efficient to compute a straight comparison of packed VLATs:

P i,c , P j,c = n ci r =1 λ r ci p r ci p r ci -n ci T c , n c j s =1 λ s c j p s c j p s c j -n c j T c = n ci r =1 n c j s =1 λ r ci λ s c j p r ci p r ci , p s c j p s c j + n ci n c j ||T c || 2 -n c j n ci r =1 λ r ci p r ci p r ci , T c -n ci n c j s =1 λ s c j p s c j p s c j , T c = n ci r =1 n c j s =1 λ r ci λ s c j p r ci , p s c j 2 + n ci n c j ||T c || 2 -n c j f ci -n c (18) with f ci = n ci r =1 λ r ci p r ci p r ci , T c .
Thanks to some index overhead to store f ci values, the computational complexity is O(C × D × n ci × n c j ). With larger codebooks, image descriptors are more and more spread into different clusters, and n ci × n c j tends to be negligible when compared to descriptors dimensions D. This context leads a complexity of O(C × D), which is far less than the O(C × D × D) complexity of unpacked VLATs.

Packed VLATs significantly reduce memory footprint, especially with larger codebooks. For instance, on the Holidays dataset [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] with 1024 clusters, standard VLATs needs about 8MB per image, whereas the packed VLATs with no reconstruction error need less than 1.5MB per image. This size can be reduced at the cost of some loss of performance. For instance with 20% reconstruction error, memory footprint drops to 0.8MB. This size can be compared to usual BoW signatures with 200.000 values, which also needs 0.8MB of storage using 32-bit float values. Furthermore, the size of packed VLATs is bounded by the number of extracted descriptors, whereas the size of standard VLAT always grows with the size of the codebook.

Let us note that this packing technique can be combined with other techniques. One can reduce the descriptors dimension though PCA, like we mentioned earlier. For instance, with the same example of 1024 clusters and descriptors reduced in size to 64 dimensions, the size of the standard VLAT is then about 2MB, and with a 20% reconstruction error, the size of a Packed VLAT is around 0.2MB. Size can be further reduced using postprocessing techniques, like Kernel PCA and/or Product Quantizer [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. In the former case, Packed VLAT can be used to speed up the processing, and signature of a few kB can be created. In the later case, very small signatures can be created (a few bytes).

Query image Similar images

Experiments

We carried out experiments of both image search and image classification CBIR tasks on well known datasets.

Search task -Holidays dataset

The Holidays dataset [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] consists in 1491 images of holidays photographs (cf. Fig. 1). This set contains 500 categories, each one depicting a specific scene or object. The first image of each category is considered as a query, and the correct answers are the remaining images of the category. We used the same descriptors and experimental setup as in [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]. All parameters of the method (dictionaries and mean tensors) were trained using the 10,000 first images of the Flickr60k dataset. Images and SIFT descriptors from this dataset are also available on the holidays website.

The first results are displayed in Table 1, where we present the mean Average Precision (mAP) according to different codebooks and error rates using Packed VLATs and power normalization. Let us first focus on the last column, where results without any reconstruction error are presented. As we can see, we obtain very good performances, and with 1024 or more clusters we obtain results close to 75% of mAP. This is comparable to results of Hamming Embedding in [START_REF] Jain | Asymmetric hamming embedding[END_REF] with the same descriptors. However, unlike [START_REF] Jain | Asymmetric hamming embedding[END_REF], we use a simple dot product metric and no geometric constraint based re-ranking techniques. Now if we observe the effect of packing with reconstruction error, mAP decreases a bit with 10% and 20% error rates, and starts to drop with more than 30% reconstruction error.

We present in Figures 2(a) and 2(b) curves that show relations between the memory size of features and the corresponding performance. Both figures (a) and (b) show the mAP according to the average memory footprint of a Packed VLAT index for one image. The only difference between the two figures is the use of the power normalization (cf Eq. ( 13)). Each curve in these figures is with the same codebook, but with different error rates. The first point to the left of each curve is the result with 50% error rate, the next one with 40%, etc. The last point to the right of each curve is the result without any error.

When error rate decreases, the size of indexes increases regularly before reaching a maximum. This maximum is related to the average size of extracted descriptors, which is around 1.35MB in these experiments (around 2,768 SIFT vectors per image using 32-bit float values). As we observed previously, there is a large mAP decrease with more than 30% of error (third dot from the left of each curve). We can also see that with 1024 clusters and higher, all parameters return close values: the mAP is about the same, the indexes size is near 1.45MB with no error and near 1MB with 10% error. If we consider power normalization, we observe a gain around 5%.

However, as one can see in Figures 3(c) and 3(d), the computational time is very different. These figures are similar to the previous ones, with the difference that mAP is presented according to the average computation time for the comparison of two image features in milliseconds. Without power normalization, we can use the computational trick we presented in section 3.1, Eq. ( 18) which saves a lot of computations, especially if we use large codebooks. However, with power normalization, we have to reconstruct the VLAT vector during image comparison, which leads to more computations. Let us note that these computational times are still very low when compared to kernels on bag computational times. For instance, the average computational time for the comparison of two images using the bag kernel of Eq. ( 1) with a Gaussian minor kernel is about 1000 ms.

Classification task -VOC 2007 database

The PASCAL-VOC challenge is one of the most used benchmark for the image classification task. In its 2007 revision, it consists in about 10,000 images and 20 categories [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF], as shown on figure 4. The parameters of the method (dictionaries and mean tensors) are trained using the canonical train subset. These parameters are the same for all categories. For each category, a classifier is trained on the canonical trainval subset, and evaluated on the test subset. The standart performance measurement for this dataset is mean Average Precision (mAP) over the 20 classes.

Experimental setup

We extracted dense simplified SIFT features on a 2 pixels grid. Our implementation is close to that of the software provided by [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. We used 4 different scales of SIFT with 4, 6, 8 and 10 pixels cell size respectively. We used a simple k-means clustering in order to obtain a codebook of 512 clusters. Prior to clustering, SIFT are compressed to 48 dimensions using PCA.

VLAT vectors are normalized using the power norm with α = 0.5, then further 2 normalization is applied. The classification was done using linear SVM trained with a fast stochastic gradient descent algorithm provided by [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF], for which the hyper-parameters (C and the number e of epochs) are set to default values (C = 10 and e = 100), regardless of the category.

Results

In table 2, we report results of Fisher Vectors (FK and IFK) taken from [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF], linear local coding (LLC), supervectors (SV) and improved Fisher vectors (FK) taken from [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF], and the winning method of VOC 2007 campain (VQ) along with our VLAT implementation. We also report in this table the presence of significant characteristics of compared methods, denoted by a × symbol. Namely, VQ and IFK from [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] used multiple features (e.g. sift and colors) to achieve these performances, whereas methods from [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] (FK, LLC and SV) use an ultra-dense SIFT sampling strategy (every 2 or 3 pixels) and a spatial pyramid scheme.

We achieve 60.8% mAP, which is less than FK, but better than recent methods like LLC and SV, which sounds promising for VLAT. In table 3, we report detailed comparison of VLAT with the bests methods of [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. The VLAT approach manages to obtain the best results on categories airplane, bicycle, bird, car, cat, dog, horse, person and train.

Discussion

In the hereby section we discuss the relationship of VLAT to well known approaches.

Relation to Kernels on Bags

Using the dot product as minor kernel for the power kernel of Lyu et al., and with parameter p = 2, leads to the following similarity function:

K(B i , B j ) = r s b ri , b s j 2 ( 19
)
This can be factorized as follows:

K(B i , B j ) = r s (b ri b s j ) 2 (20) = r s (b ri b ri ) b s j b s j (21) =        r b ri b ri               s b s j b s j        (22)
This factorization is indeed the dot product applied to the sum of tensors products of all {b ri } r . Hence, our method seems to be closely related to kernels on bags.

However, we observe two differences with our VLAT approach. Firstly, our approach splits the bag according to a clustering, and sums the contribution of each split. The equivalent kernel on bags would be the following:

K(B i , B j ) = c r s b cri , b cs j 2 (23)
The second difference lies in the centering applied to the tensors. This centering can be viewed as a affine transform in mapped space. Thus, VLAT appears to be a kernel on bags with the following explicit mapping:

K(B i , B j ) = c r s b cri b cri -T c , b cs j b cs j -T c ( 24
)
VLAT is thus the explicit linear writing of a highly non-linear kernel on bags. Although implicit mappings have been a major advantage allowing efficient learning algorithm with nonlinear similarities using the kernel trick, explicit mappings have a clear computational advantage. They transfer the highest part VQ [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF] IFK [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] FK [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] LLC [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] of the cost from the online similarity computation to the offline signature calculation. This relationship can explain the excellent behavior of VLAT in image search task, where descriptor matching methods achieve the best performances.

Relation to Fisher Vectors

In order to relate VLAT to Fisher Vectors (FV), let us consider the diagonal terms in equation 11:

T i,c [t, t] = r (b rci [t] -µ c [t]) 2 -σ c [t] 2 = σ c [t] 2 r (b rci [t]-µ c [t]) 2 σ c [t] 2 -1 (25)
With σ c being the standard deviation vector of cluster c. In these diagonal only terms, the main appearing differences with Fisher Vectors are the following: contributions are summed for all descriptors in FV, whereas they are summed only for the descriptors of the corresponding cluster in VLAT. Moreover, FV weight the contribution by the likelihood of descriptors to the corresponding cluster.

FV are also normalizing the resulting sum by the number of descriptors in the bags and the weight of the clusters, which is consistent with assigning descriptors to all clusters. In VLAT, as the assignment is only with respect to the corresponding cluster, there is no need to such normalization schemes. In fact, VLAT diagonal can be seen as a hard assignment variant of FV.

This close relationship between VLAT and FV can explain their comparative performances in image classification.

Conclusion

In this paper, we introduced a new efficient image signature in two different tasks on content based image retrieval, i.e. image search and image classification. Our scheme is based on the aggregation of tensor products of local descriptors named VLAT. We showed our VLAT approach to be closely related to kernels on bags methods which are known to be efficient for image search tasks. We also found relation between VLAT and Fisher vectors, which are known to be efficient in image classification tasks. We also carried out experiments on well known image datasets for these two tasks (namely VOC2007 and Holidays), and achieved near state of the art performances. These results highlight the ability of our signatures to be effective in similarity search and in classification. Moreover, we provide an easy generalization of our approach to higher order of tensors. Future works will investigate the extra information added by these higher orders.

Figure 1 :

 1 Figure 1: Images from Holidays database.

Figure 2 :

 2 Figure 2: Mean Average Precision (%) using Packed Vectors of Locally Aggregated Tensors on Holidays database, according to the average size of image indexes.

Figure 3 :

 3 Figure 3: Mean Average Precision (%) using Packed Vectors of Locally Aggregated Tensors on Holidays database, according to the average computational time for the comparison of two image features.

Figure 4 :

 4 Figure 4: Images from PASCAL Visual Object Classes Challenge 2007. *Categories where our method gives the best results.

Table 1 :

 1 Mean Average Precision (%) using Packed Vectors of Locally Aggregated Tensors on Holidays database, with different codebook sizes and reconstruction error rates.

				Error rate
	Dict. Size	50% 40% 30% 20% 10%	0%
	64	53.6	56.9	59.0	61.8	63.7	64.1
	256	57.7	62.2	65.1	67.9	70.3	71.5
	1024	58.7	64.3	68.5	72.7	74.7	74.8
	4096	61.2	65.7	69.6	72.3	74.1	76.1

Table 2 :

 2 Mean Average Precision (%) of different methods. Results are reported from respective papers. For the methods, VQ: vector quantization, IFK: improved fisher vectors, FK: fisher Vectors, LLC: Linear Local Coding, and SV: Supervectors. For the configurations, NLK: Non-linear Kernel, MF: Multiple Features, SP: Spatial Pyramid, and UDSS: Ultra-dense Sift sampling (i.e. every 2 or 3 pixels).

	SV[34]	VLAT

Table 3 :

 3 Mean Average Precision (%) for Fisher vectors (FK), Supervectors (SV) and VLAT on all categories of VOC2007 dataset. Results are reported from[START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF].