J A Dos Santos

O A B Penatti

R Da

S Torres

P-H Gosselin

S Philipp-Foliguet

A Falcão
email: afalcao@ic.unicamp.br

Improving Texture Description in Remote Sensing Image Multi-Scale Classification Tasks By Using Visual Words

Although texture features are important for regionbased classification of remote sensing images, the literature shows that texture descriptors usually have poor performance when compared and combined with color descriptors. In this paper, we propose a bag-of-visualwords (BOW) "propagation" approach to extract texture features from a hierarchy of regions. This strategy improves efficacy of feature as it encodes texture information independently of the region shape. Experiments show that the proposed approach improves the classification results when compared with global descriptors using the bounding box padding strategy.

Introduction

The use of high resolution images has allowed the extraction of texture features, in addition to the widely used spectral information. Although texture features are commonly extracted by using techniques developed to generic applications, its extraction on arbitrary-shaped regions obtained by segmentation algorithms is still a problem. Usually, the regions are extended to a rectangular area [START_REF] Li | Evaluation of spectral and texture features for object-based vegetation species classification using support vector machines[END_REF] which can be performed either by obtaining the inner rectangle from the region or by using the region bounding box. The first strategy cannot usually represent the property of the entire region well. The strategy using region bounding box consists of filling the outside area between the region and its box with a pre-defined value to reduce the interference of external pixels in the extracted texture pattern. This process is known as padding [START_REF] Li | Evaluation of spectral and texture features for object-based vegetation species classification using support vector machines[END_REF] and the most common approach is to assign zero to the external pixels (ZR-Padding). Liu et al. [START_REF] Liu | Study on texture feature extraction in region-based image retrieval system[END_REF] have tested different padding techniques. However, there is no analysis about the impact of using the padding strategy in the final classification results.

Recently, the use of different texture descriptors in remote sensing image (RSI) classification has been evaluated. In [START_REF] Santos | Evaluating the potential of texture and color descriptors for remote sensing image retrieval and classification[END_REF], an evaluation of seven successful global descriptors that encode texture information in RSI applications was performed. In another study [START_REF] Santos | Multiscale classification of remote sensing images[END_REF], three of those descriptors were used by employing a padding strategy. The objective was to evaluate a Multiscale Classification (MSC) approach used to combine texture-and color-based weak classifiers. Experiment results with global descriptors obtained in both works lead to two main conclusions: (1) texture features produce worse results than spectral information in our coffee crop recognition application; and (2) texture features have small contribution to the classification accuracy when combined with descriptors that encode spectral information. Although these conclusions are not surprising, we believe that texture information could be better exploited if its extraction is independent of segmentation.

In this paper, we propose a solution based on bag of visual words to extract features from regions independently of their shape. We have also extended this idea to deal with hierarchy of regions [START_REF] Guigues | Scale-sets image analysis[END_REF]. The strategy starts by extracting features from interesting points in the "image level". Then, starting from the finer scale to the coarser one, the features are propagated to all regions of the hierarchy without having to extract the low-level features again for each hierarchy level. The propagation is performed by grouping into histograms the features that belong to points inside the regions. This approach establishes a relationship between the features of the regions that belong to the same branch of the hierarchy.

Bag-of-Visual Words

In this article we use the notion of global and local descriptor that is normally employed in content-based image retrieval. Global descriptors consists in describing an object (image or region, for example) by using all available pixels. Local descriptors, in turn, are extracted from predefined points of interest in the object. Hence, if an object has more than one point of interest in its interior, it can be described by more than one feature vector. A very efficient way to combine the characteristics that describe an object is to group them through the visual word concept.

To create a visual dictionary and, then, an image representation based on visual words, the bag-of-visualwords (BOW), several steps need to be performed and many variations can be employed in each step. Initially, local low-level features are extracted from images. Interest-point detectors or simply a dense grid over the image are used to select images local patches. Literature presents better results for dense sampling in classification tasks [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. Each local pacth is described by an image descriptor, being SIFT the most popular one. The feature space is then quantized originating the visual words. In spite of the fact that k-means is still a common technique for feature space quantization, due to the curse of the dimensionality, a simple random selection generates dictionaries of similar quality [START_REF] Viitaniemi | Experiments on selection of codebooks for local image feature histograms[END_REF].

Given the visual dictionary, image representations are created using it. The feature vectors of images local patches are assigned to one or more visual words in the dictionary. Hard and soft assignment can be used, being soft assignment more robust to feature space quantization problems [START_REF] Van Gemert | Visual word ambiguity[END_REF]. While hard assignment assigns to a local patch the label of the nearest visual word in the feature space, soft assignment considers all the visual words near to a local patch, proportionally to their distance. Soft assignment of a local pacth p i to a dictionary of k words can be formally given by Equation 1 [START_REF] Van Gemert | Visual word ambiguity[END_REF]:

α i,j = K σ (D(p i , w j )) k l=1 K σ (D(p i , w l )) (1)
where j varies from 1 to k, K σ (x) = andD(a, b) is the distance between vectors a and b. We have used soft assignment in our experiments (σ = 60). The assignment step results in one k-dimensional vector α i for each point in the image. To summarize the set of image local descriptions into one single feature vector, a pooling step is applied. Average and max pooling are popular strategies employed, with an advantage to the latter [START_REF] Boureau | Learning mid-level features for recognition[END_REF]. Average pooling can be formally defined as follows:

1 √ 2π×σ × exp(-1 2 x 2 σ 2 ),
h j = ( N i=1 α i,j )/N .
Max pooling is given by the following equation: h j = max i∈N α i,j . In both equations, N is the number of points in the image and j varies from 1 to k.

Bag-of-visual-words (BOW) has been used to encode features in remote sensing applications in other recent works [START_REF] Chen | Evaluation of local features for scene classification using vhr satellite images[END_REF][START_REF] Feng | Bag-of-visualwords based on clonal selection algorithm for sar image classification[END_REF][START_REF] Sun | Automatic target detection in highresolution remote sensing images using spatial sparse coding bag-of-words model[END_REF]. However, our work differs from them as it considers the problem of extracting features in a hierarchy of regions. Another difference of our work is concerned with the evaluation of several different parameters related to the bag-of-words representation. Finally, we discuss the problems that concern the efficient extraction of texture information in arbitraryshaped regions.

Proposed Feature Extraction Model

The Multiscale Classification (MSC) approach [START_REF] Santos | Multiscale classification of remote sensing images[END_REF] aims to combine different features at multiple scales of segmentation to perform remote sensing image classification. The strategy is based on the paradigm of boosting, whose principle is to combine weak classifiers to build an efficient global one. MSC exploits a hierarchy of regions, obtained by using the Guigues algorithm [START_REF] Guigues | Scale-sets image analysis[END_REF].

Figure 1 illustrates the process of feature extraction using global descriptors, which is the approach initially adopted to extract texture from the hierarchy in the MSC. At the beginning, several partitions P λ of hierarchy H at various scales λ are selected. Then, at each scale λ, a set of features is computed for each region R ∈ P λ . To extract texture features, the bounding box is computed by using the "mean value padding", as suggested in [START_REF] Liu | Study on texture feature extraction in region-based image retrieval system[END_REF]. Figure 2 illustrates the strategy of feature extraction using visual words that we propose in this paper. The first step is to define points of interest in the image. Local features are computed for each point of interest. Therefore, the feature extraction is independent of segmentation. At the finer scale λ 1 , for each region R ∈ P λ1 we compute the histogram of visual words based on the features extracted from the interest points that belong to R. Then, from the finer scales to the coarser ones, the features are "propagated" to all regions in the hierarchy. We called "propagation" the process of computing histograms (i.e., bags) of visual words for each region R ∈ P λi by combining the histograms of its R children. The combination of histograms is performed by adapting the pooling strategies described in Section 2. In the case of max pooling, the histogram of the region R is composed by the maximum values present in the children histograms. Concerning average pooling, we have to keep the amount of points of interest used to compute the histogram of each child. The histogram of the region is a weighted average of its children histograms, where the weight is the amount of points of interest used to compute each child histogram. Note that the process of propagation produces the same histograms that if they are calculated directly from the points of interest. The propagation advantage is that is faster to combine children histograms than directly compute the histograms from the points of interest.

Experiments

We carried out experiments aiming to address the following questions: What is the impact of extracting features depending on the arbitrary-shaped regions? Which are the best set of parameters to encode texture information using visual words? Are bag-of-visualwords more suitable for RSI classification tasks than using successful global descriptors with padding?

Setup

RSI Data: The image used was captured by the SPOT satellite and corresponds to the Monte Santo de Minas county, in the State of Minas Gerais, Brazil, a traditional place of coffee cultivation. To evaluate the accuracy, we use a ground-truth mask that indicates all coffee crops in the image. We divided the image into a grid of 3 × 3, generating 9 subimages with dimensions equal to 1000×1000 pixels. We performed experiments with 10 different combinations of the 9 subimages used (3 for training, 3 for validation, and 3 for classification).

Classifiers: We use support vector machines with no kernels for each extracted descriptor.

Effectiveness measure: To analyze the results, we compute the overall accuracy (O. A.), Kappa index, and Tau index for the classified images.

Description: Every region in the RSIs is described by bags-of-visual-words (BOW). We have performed a large evaluation on the parameters of the BOW representation to verify their impact in the final classification. Details are provided in Section 4.2. We have also used QCCH, SID, and Unser as global descriptors baselines. They are selected based on previous results [START_REF] Santos | Evaluating the potential of texture and color descriptors for remote sensing image retrieval and classification[END_REF].

Study of BOW Parameters

We have performed experiments to evaluate the impact of BOW parameters. Results are shown in Table 1.

We have used dense sampling as it presents better results than interest point detectors in classification experiments [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. The dense grid samples every image part avoiding not taking points in homogeneous regions or in regions with low contrast, what usually happens with interest point detectors. We have used a very dense sampling in the experiments, by overlapping circles of radius 4 and 6 pixels [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF], as in the remote sensing images the use of some interest regions can be very small. The difference in classification is very small between the two sampling scales, however we have noticed that the number of regions represented in the finest regions scale is larger for the circles of radius 4. This happens because in our RSIs there are very small regions.

The SIFT features extracted from each region in the dense sampled images were used to generate the visual dictionary. We have used a random selection of points, instead of k-means, due to the curse of the dimensionality [START_REF] Viitaniemi | Experiments on selection of codebooks for local image feature histograms[END_REF]. We have tested dictionaries of 10 2 , 10 3 , and 10 4 visual words. If very few differences among feature vectors need to be encoded, a large visual dictionary is recommended. However, if some small differences in local textures must be ignored, smaller dictionaries can be useful. The results in Table 1 show that larger dictionaries are more representative, specially considering Kappa and Tau measures.

We have also evaluated the impact of different pooling strategies. Average pooling tends to smooth the final feature vector, because assignments are divided by the number of points in the image. If we have many points in the image strongly assigned to some visual words, this information is going to be kept in the final feature vector. However, if only a few points have large visual words associations, they can become very small in the image feature vector. This effect is good to remove noise, but it can also eliminate rare visual words, which could be important for the image description. Average pooling tends to work badly with very soft assignments and large dictionaries, due to the fact that points may have a low degree of membership to many visual words, and computing their average is going to generate a too soft vector. We can see this phenomenon in the low values of Kappa and Tau measures for the dictionary of 10 4 words in Table 1. Max pooling captures the strongest assignment of each visual word in the image. Therefore, if only one point has a high degree of membership to a visual word, this information will be hold in the image feature vector. Max pooling tends to present better

BOW ZR-Padding vs BOW Propagation

Table 2 presents the results comparing BOW with ZR-Padding and BOW with Propagation. The first approach is the well-known region bounding box with outside padding [START_REF] Liu | Study on texture feature extraction in region-based image retrieval system[END_REF]. We use zero padding because it uniforms the value used in all regions of the image. The other approach is the BOW "propagation that we propose in this paper (Section 3). Our objective is to investigate the impact of the segmentation in the feature extraction. As we can observe, the Propagation strategy yields better results than the ZR-Padding. We can say that in these experiments, the padding strategy caused a loss of 8.37% in the accuracy of the BOW descriptor. Regarding Kappa index, ZR-Padding produces results with almost no agreement when compared with the ground truth.

BOW vs Global Descriptors

Table 3 presents the classification results for the BOW and three successful global texture descriptors [START_REF] Santos | Evaluating the potential of texture and color descriptors for remote sensing image retrieval and classification[END_REF]. The BOW descriptor was used with the BOW-Propagation strategy while the global descriptors were extracted by using ZR-Padding. The BOW descriptor yields slightly better overall accuracy than global descriptors. The difference is more perceptible regarding the Kappa and Tau indexes. The BOW descriptor achieves 0.3289 of agreement while the best global descriptor (Unser) achieves Kappa index equals to 0.1636. Observing Tau index, BOW yields results almost 50% better than a random classification, while Unser produces classification 34% better than the random.

Conclusions

In this paper we proposed a new approach to extract texture features from arbitrary-shaped regions by using bag-of-visual-words (BOW) "propagation". We have carried out experiments: to analyze the BOW parameters in the context of remote sensing image classification; to investigate the impact of using zero-padding to extract texture features; and to compare the efficiency of BOW descriptor using the proposed strategy against successful global texture descriptors. Experiments showed that the proposed approach improves the classification results when compared with global descriptors using the bounding box padding strategy. Future work includes the investigation of the BOW strategy combined with other global descriptors.

Figure 1 .

 1 Figure 1. Feature extraction using global descriptors.

Figure 2 .

 2 Figure 2. Proposed approach to feature extraction using BOW propagation.

Table 1 . Classification results for BOW representation parameters (S=Sampling; DS=Dictionary Size; P=Pooling).

 1 avg 73.69 ± 2.77 0.25 ± 0.04 0.38 ± 0.04 max 72.71 ± 2.73 0.22 ± 0.04 0.37 ± 0.03 10 3 avg 71.24 ± 3.46 0.23 ± 0.06 0.42 ± 0.03 max 70.80 ± 3.19 0.25 ± 0.05 0.44 ± 0.03 10 4 avg 73.48 ± 3.00 0.18 ± 0.04 0.29 ± 0.03 max 73.40 ± 3.48 0.32 ± 0.06 0.48 ± 0.04 4 10 2 avg 72.93 ± 2.82 0.21 ± 0.04 0.35 ± 0.04 max 73.22 ± 2.53 0.21 ± 0.04 0.34 ± 0.04 10 3 avg 71.32 ± 2.96 0.23 ± 0.05 0.41 ± 0.03 max 71.68 ± 2.91 0.28 ± 0.05 0.45 ± 0.03 10 4 avg 73.74±2.73 0.20 ± 0.04 0.31 ± 0.03 max 72.66 ± 3.74 0.32 ± 0.06 0.49 ± 0.04

	S DS P	O.A. (%)	Kappa (κ)	Tau (τ )
	10 2
	6

Table 2 . Classification results comparing BOW-ZR-Padding and BOW-Propagation.

 2

	Method	O.A. (%)	Kappa (κ)	Tau (τ )
	ZR-Pad.	64.39 ± 1.78	0.0016 ± 0.02	0.2684 ± 0.02
	Propag.	72.66 ± 3.74 0.3289±0.06 0.4912±0.04

Table 3 . Classification results comparing "BOW-Propagation" with the best tested Global Descriptors using "ZR Padding".

 3 The overall analysis over the results in Table1is thatthe largest dictionary size with max pooling produced the best results, specially if we consider the Kappa and the Tau indexes.

	Method	O.A. (%)	Kappa (κ)	Tau (τ )
	BOW	72.66 ± 3.74 0.3289±0.06 0.4912±0.04
	QCCH	70.36 ± 2.71	0.1400 ± 0.03	0.3062 ± 0.02
	SID	69.35 ± 2.52	0.0092 ± 0.02	0.1336 ± 0.03
	Unser	69.77 ± 3.11	0.1636 ± 0.04	0.3387 ± 0.03
	performance for larger dictionaries with softer assign-
	ments. In our experiments, max pooling presents better
	performances with the largest dictionaries.

Acknowledgements

We thank FAPESP (2008/58528-2 and 2009/10554-8), CAPES, and CNPq for the financial support, and Cooxupé for the dataset.


Philippe-Henri Gosselin

ONLINE KERNEL LEARNING FOR INTERACTIVE RETRIEVAL IN DYNAMIC IMAGE DATABASES

Keywords: Image databases, Interactive systems, Machine learning algorithms, Boosting

In this paper, we propose a system for interactive image retrieval in dynamic databases, where images are regularly added or removed. In order to handle this, we propose a method that tunes itself according to user labels. The framework we propose is based on visual dictionaries, with the specificity that the dictionaries are built online, during retrieval sessions. In other words, each user has its own visual dictionary, as opposed to usual approaches where all users share the same visual dictionary. In order to create theses dictionaries, we propose a method based on kernel functions. This method iteratively selects base kernels from a large base kernel pool, where each base kernel is related to a low-level descriptor such as color or texture. This learning process is performed in real time, and the classification of the database is faster than usual techniques since only relevant features for the current query are used. Experiments are carried out on a generalist database, and show the ability of the method to build effective kernels with few labels.

INTRODUCTION

During the last decade, many retrieval methods have been proposed for interactive retrieval in multimedia database. In order to use these methods with effectiveness, a tuning step is usually required. In the case of static databases, this is easily handled. However, in the case of dynamic databases, where images are regularly added, a steady tuning of the retrieval method is necessary.

In this paper, we propose to focus on dynamic databases with retrieval methods which require minimal tuning, and in the ideal case no tuning at all. In order to reach this goal, we propose to work with kernel-based methods, a framework that has shown its effectiveness for many tasks including multimedia retrieval. In this context, a usual approach is to first extract low-level features and build a visual dictionary using for instance K-means, Gaussian Mixtures [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] or reconstruction [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF]. Visual dictionaries are then used to build a vector for each image in the database, like histograms, bag of words, densities, etc. Then a kernel function on these vectors is selected and tuned to the current database. Once these steps done, retrieval sessions can begin, usually using SVM for database classification and active learning for interaction with users [START_REF] Gosselin | Precision-oriented active selection for interactive image retrieval[END_REF].

As we can see, these methods have two main offline steps : dictionary/vectors building and kernel tuning. In this paper, we propose to perform these two steps online, during the retrieval. The idea is to use labels provided by the user to perform the tunings. A simple approach would be to run semi-supervised versions of dictionary methods, but this is intractable from a computational point of view. Instead, we propose to learn both the dictionary and the kernel in a single step. More specifically, we propose to learn a linear combination of base kernel, where each base kernel is related to a low-level feature or a codeword.

INTERACTIVE LEARNING

In this paper, we propose a method based on kernel functions, Support Vector Machines (SVM) and active learning to interact with the user [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF][START_REF] Gosselin | Active learning methods for interactive image retrieval[END_REF]. A retrieval session is performed in the following way: Initialization. A retrieval session is initialized from one image brought by the user. The kernel function is used to compute the similarity between this query image and all images in the database. The images with the highest similarities are then presented to user. Note that other initializations could be used, for instance with keywords. If the user is not satisfied by this initial result, he labels images as relevant or irrelevant. Classification. The images the user labeled are used to train a SVM classifier. This classifier is based on a kernel function, usually a static kernel function, like a Gaussian with a L 2 or a χ 2 distance. In this paper, we present a dynamic kernel function, that is learned from the current user labels. Relevance of images in the database are then evaluated using the hyperplane computed by the SVM trainer, and images with the highest relevance are presented to the user. Active learning. In the case where the user is not satisfied with the current result, an active learner is called to select (unlabeled) images the user should label. In the following experiments, we use the method proposed in [START_REF] Gosselin | Precision-oriented active selection for interactive image retrieval[END_REF]. Once this labeling is performed, the classification step is repeated, and so on.

PROPOSED METHOD

The method we proposed is based on Multiple Kernel Learning (MKL), a strategy which has a great success these last years [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Joutou | A food image recognition system with multiple kernel learning[END_REF]. The aim of our method is to find a linear combination K = t=1 βtkt of base kernels kt from a pool K. More specifically, we aim at finding a sparse combination (where most of βt equal zero), within a very large base kernel pool. The motivation of this choice is to be as generic as possible. Since we consider a very large base kernel pool, we can build many different final kernels. Furthermore, we consider "weak" base kernels, which focus on lowlevel features with very few parameters. For instance, if each base kernel is related to a visual codeword (a color, a keypoint, etc.), then we are able to consider a very large set of final kernels, each of these kernel possibilities being related to a different visual dictionary.

In the usual case where the base kernel pool is small, one has to work on "strong" base kernels, which must be built to fit the current database in order to be effective. When working on static databases and with some prior knowledge, this problem can be solved with Algorithm 1 Fast Iterative Selection. Given: kernel K, minor kernel k, centering matrix H, target kernel L.

Compute inner products:

a = tr(HKHK); b = tr(HkHk); c = tr(HKHk)

∆ = ab -c 2 if |∆| < ǫ then return "no solution" Compute weights which maximize A H L (βK K + β k k): wK = tr(HKHL); w k = tr(HkHL) βK = bw K -cw k ∆ ; β k = aw k -cw K ∆ if |βK | < ǫ then return "no solution" Compute weight β = β k β K if β < ǫ then return "no solution" Compute alignment A = w K +βw k √ tr(HLHL)(a+2cβ+bβ 2 )
Return weight β and alignment A cross-validation techniques. However, when working on dynamic databases, where images regularly change, "strong" base kernels must be re-tuned to keep the effectiveness of the system.

Kernel-Target Alignment

In order to find the linear combination, we use the Kernel-Target Alignment :

AL(K) = K, L F ||K||F ||L||F (1)
where K is the n × n kernel matrix to evaluate, L is the n × n target kernel matrix, K, L F the Frobenius inner product, and ||K||F the Frobenius norm.

A first target kernel is yy ⊤ , with yi ∈ {-1, 1} the label of document i. This choice is relevant for balanced training sets, where there is the same number of positive and negative labels. In other cases, such a kernel target focuses on the largest class. In the case of interactive retrieval, where the negative class is much larger than the positive one, optimization algorithms using this target kernel will learn more the negative class -the class the user is not interested in.

In order to deal with the unbalance of training data, one can use the target kernel ỹỹ ⊤ , with ỹi = 1/n + if yi > 0 and ỹi = -1/n - if yi < 0, where n + and n -are the sizes of the positive and negative classes, respectively. An even more interesting approach we use in this paper is the centered alignment [START_REF] Kawanabe | A procedure of adaptive kernel combination with kernel-target alignment for object classification[END_REF]:

A H L (K) = HKH, HLH F ||HKH||F ||HLH||F (2)
with Lij = 1 if yi = yj, 0 otherwise, and H = I -1 n 11 ⊤ , with I the identity matrix of size n, and 1 the column vector with all elements 1. Centered alignment deals with unbalanced data in the same way than target kernel ỹỹ ⊤ , but is also invariant to scale

(A H L (λK) = A H L (K)) and shift (A H L (K + λ11 ⊤ ) = A H L (K)).

Fast Iterative Selection

In order to deal with computational constraints of interactive retrieval, we propose a fast algorithm to find a good linear combination of base kernels. For each feedback step in the retrieval process, we start with kernel K0 = 0, and then select the base kernel k ⋆ 1 with weight β ⋆ 1 = 1 that maximizes centered kernel alignment with current user labels. Then, we iteratively select and add new base kernels until no solution is found:

K ⋆ t = Kt-1 + β ⋆ t k ⋆ t (3)
where

β ⋆ t , k ⋆ t = argmax β>0,k∈K A H L (Kt-1 + βk) (4)
The optimization problem of Eq. ( 4) can be solved using linear algebra (cf. [START_REF] Kawanabe | A procedure of adaptive kernel combination with kernel-target alignment for object classification[END_REF] for proof). Implementation details are presented in Algorithm 1. This method can be seen as an approximation of boosting-based kernel learning methods such as [START_REF] Crammer | Kernel design using boosting[END_REF]. The approximation we made in these processes is the removal of the training of base kernels (weak learner in boosting framework), because this is the most computational part of the learning process. This approximation changes the boosting assumption which states that, for any iteration of selection, it exists a weak learner (base kernel in our case) that enhances the optimization criterion. In our case, this assumption holds if the base kernel pool is infinite -which is obviously impossible in real applications. However, we can reach good performances if the pool is well made.

Base kernels

We propose to build base kernels that compare two images based on a low-level descriptor like color or texture.

Before any retrieval session, we extract and quantize the descriptors within an image using K-Means with Euclidean distance d. Let us note that quantization is performed independently on each image, as a trick to reduce the number of descriptors in each image. Then, we build for each image i a set Pi of features pri = (fri, hri, θri), where fri is the center of cluster r computed by K-Means, hri the number of vectors in cluster r, and θri the distance of fri to the closest cluster center r ′ = r. These image feature sets Pi = {pri}i are computed off-line.

Then, for each on-line retrieval session, we first build a new feature pool P = {p ∈ Pi|yi > 0} using features contained in positive labelled images. Then, we define the corresponding base kernel pool K = {k p|p ∈ P}. With such a definition, there is a base kernel k p for each descriptor p, and a feature pool for each base kernel pool, and vise versa. In the following, we mix the two concepts.

Base kernels are defined as:

k p(Pi, Pj) = δ χ 1 (e p(Pi), e p(Pj )) (5)
with

δ χ 1 (x, y) = 1 -|x-y| x+y if x > 0 and y > 0 0 otherwise (6) e p(Pi) = hr⋆i if d( f , fr⋆i) ≤ θ 0 otherwise (7) r ⋆ = argmin r d( f , fri) (8)
p = ( f , ĥ, θ)

Each of these base kernels can be seen as a triangle kernel with χ 1 distance computed on a single bin of a histogram. We first compute the descriptor fr⋆i of image Pi the closest to the base kernel descriptor f (Eq. ( 8)). Then, if this descriptor is in the hypersphere of center f and radius θ, we return the number of pixels hr⋆i in image Pi (Eq. ( 7)). The same computation is performed on image Pj, and finally numbers of pixels in each image are compared (Eq. ( 6)).

Evaluation Protocol

We set up an evaluation protocol to estimate the average performance one can expect when starting an interactive retrieval session with a random image. This is performed by the simulation of retrieval sessions for each category, where the user labels the images selected by the active learning technique. A Precision/Recall curve is computed at each feedback step, and then averaged over all retrieval sessions for the same category. Then, the average quality of the ranking is computed with the usual criterion of Average Precision, which is used for example in TRECVID evaluation campaign. At last, in order to have a global quality measure of our system, we compute the Mean Average Precision (MAP) on all categories. Labelling is only performed on the development set, and performance is computed on the test set.

Results

Average Precision per category are displayed in Fig. 2 for 51 labels, and Mean Average Precision according to feedback steps in Fig. 3. In all the following experiments, we use a SVM classifier for the classification of the database, and the active learning method is the one of [START_REF] Gosselin | Precision-oriented active selection for interactive image retrieval[END_REF].

Baseline. We first show baseline results using a usual learning strategy with static dictionaries that is effective and robust to tuning. In order to find such a method, we tested many techniques proposed in the literature. Most of them use large dictionaries of descriptors (more than 1000) and then compute a vector representation of images using the dictionaries. For instance, Bags of Words computes a dictionary of 4000 keypoint descriptors, and then creates an histogram of visual words occurrences for each image. Our experiments showed that this method leads to very unstable results in an interactive retrieval context. For instance, running another time the dictionary computation can lead to very different results, even with advanced K-Means algorithms. Let us note that is specific to the few number of labels (about 50) we have in interactive retrieval context, and this high instability does not appear with very large training sets. With more recent methods, such as the ones based on locally linear coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], results are better but still unstable. Among all methods we tested, we found an effective one in our interactive context which is based on small visual dictionaries. This method is called Vector of Locally Aggregated Descriptors (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], and is derived from the method based on bag of features and Fisher Kernels proposed in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. VLAD approach aggregates keypoint descriptors into a single vector in a more efficient way than bag of features. We integrated this aggregation scheme using keypoints detected with Harris-Laplace and rgSIFT descriptors. Note that we tested the same descriptors as the ones experimented in [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF], and rgSIFT turned to be the most effective. We tested several dictionary sizes (from 8 to 64), and it appears that a dictionary of 18 visual words provides the best results. Let us note that we experimented several indexing and learning techniques from the literature, and select this method for its robustness to tuning. For instance, with the worst dictionary size, we get a MAP of 14.7%, which is close to the best result (15.6%). Furthermore, since we need few codewords, the computation of the dictionary is always good, on the contrary to other dictionary base techniques where two K-Means can lead to two different dictionaries with very different performances. In other words, this method is a good candidate for interactive retrieval in dynamic database since performances seem to be quite stable, whatever the changes made in the database. About computational time, with an iCore7 processor and no shared cache between retrieval sessions, training requires less than 1ms, and classification of 5,000 images from 30ms (8 codewords) to 200ms (64 codewords).

Proposed method. We also show results with the proposed method using global descriptors (denoted as "Proposed/1x1" in Fig. 2 and3). We used L ⋆ a ⋆ b ⋆ colors (lab) and Quaternionic Wavelets coefficients (qw) for texture. For each image i, we extract lab and qw descriptors for each pixel, and then use K-Means to reduce their number to get sets Pi of R descriptors. We tune the value of R as a compromise between performance and computational time, knowing that fewer descriptors lead to lower performances (16.4% with R = 32 lab and qw), and more descriptors lead to higher performances (18.3% with R = 256 lab and qw). Using our method with these features, we get a MAP of 17.0% with 51 labels. This result is comparable to the baseline method (VLAD), and thus shows the ability of the method to learn effective kernels only using a few labels. About computational time, with an iCore7 processor and no shared cache between retrieval sessions, training requires about 250ms, and classification of 5,000 images about 25ms. When compared to the baseline method, the training is much slower, but does not depends on the size of the database. However, the classification of images is always faster, which means that the method we propose is more interesting for large databases.

We also show results with the proposed method using features extracted in 3 horizontal parts of images (denoted as "Proposed/1x1+1x3" in Fig. 2 and3). In that case, each part of images is used to build a different feature/base kernel pool. We extracted 21 lab and 21 qw descriptors in each part of image, and then get 8 different feature/base kernel pool (64 lab and 64 qw in whole image, 21 lab and 21 qw in upper part, 21 lab and 21 qw in middle part, and 21 lab and 21 qw in bottom part). With 25 positive labels (the usual case at the end of retrieval sessions), base kernel pools with 64 descriptors per image have 1600 elements, and base kernel pools with 21 descriptors per image have 525 elements. Furthermore, at the end of retrieval sessions, the method used to select from 27 to 38 base kernels from each base kernel pool. With this setup, we get a MAP of 20.3%, a good improvement that shows the ability of the method to benefit from more features.

CONCLUSION

In this paper, we introduced a method to learn a linear combination of base kernels in an effective and efficient way. The main advantage of this method is its high robustness to tuning, and thus its ability to handle interactive retrieval in dynamic databases. This method can be deployed and easily maintained on real image databases since no steady tuning is required to fit the current needs of users. Moreover, the classification of images is faster than comparable methods, since only relevant feature for the current labels are used for classification.

Fig. 1 .

 1 Fig. 1. Images from VOC 2007 database.

  We carried out experiments on VOC 2007 database which contains images belonging to 20 categories. It is split into 5,011 development images (train+val) and 4,952 test images. Images from this database are shown in Fig.1. Let us note that we do not follow any of the PASCAL evaluation protocols since we are interested in interactive image retrieval.

Fig. 3 .

 3 Fig. 3. Mean Average Precision(%) on the test set of VOC2007 database, according to each feedback step.


Romain Negrel
email: romain.negrel@ensea.fr

David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: gosselin@ensea.fr

COMPACT TENSOR BASED IMAGE REPRESENTATION FOR SIMILARITY SEARCH

Keywords: Image retrieval, Image databases, Machine learning

Within the Content Based Image Retrieval (CBIR) framework, one of the main challenges is to tackle the scalability issues. We propose a new compact signature for similarity search. We use an original method to perform a high compression of signatures while retraining their effectiveness. We propose an embedding method that maps large signatures into a low-dimensional hilbert space. We evaluated the method on Holidays database and compared the results with methods of state-of-the-art.

INTRODUCTION

Content Based Image Retrieval (CBIR) is now an as well established field in the image processing community. In search by similarity tasks, the main problem is to compute image signatures that reduce as much as possible the semantic gap. Efficient systems have been proposed thanks to the introduction of highly discriminative local descriptors [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] and powerful aggregation schemes to produce the signatures [START_REF] Wang | Localityconstrained linear coding for image classification[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. However, these methods are not compact and require a lot of storage and computational resources. Scalability issues are then the next challenge of image search by similarity.

In this paper, we propose a new method for fast similarity search using compact signatures with high discriminative capacity. Our approach is as effective as current ones, but with a much smaller computational cost and data size. Our signatures are obtained by compressing a tensor based aggregation of local descriptors.

This paper is organized as follows: the next section describes recent related work on image representation. Section 3 introduces our novel approach and gives insight on its soundness. We then present successful experiences on Holidays dataset, before we conclude.

IMAGE VECTOR REPRESENTATION

In the similarity search and automatic indexing popular techniques are based on bag of features. Among these ones, two main methods: kernels based technique [START_REF] Gosselin | Kernel on bags of fuzzy regions for fast object retrieval[END_REF] and explicit embedding methods. In this article we will focus on mapping functions. These methods consist in mapping a set of descriptors into a single vector.

Bag of Words

A first method to map the set of descriptors into a single vector is called "Bag of Words" (BoW) [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. This method involves a visual codebook composed of prototype descriptors (visual words), and count the occurrences of these prototypes within an image.

For some training set of images, the Visual codebook is usually computed using a clustering of descriptors (usually using K-means).

This method has many advantages: its implementation is very simple. The size of the signature generated by this method is small, as it depends only on the number of visual words in the visual codebook. However, nonlinear methods of similarity (e.g. Gaussian kernels with ℓ 2 -distance or χ2distance) are required to reach good performances.

Coding/pooling schemes

The Coding/pooling method is a generalisation of BoW. It divides the mapping in two steps. The first step is to map each descriptor of the image on the dictionary ("coding" step). The second step is to aggregate the mapped descriptors into a single signature ("pooling" step).

To compute BoW with these schemes, 1 is assigned to the closest visual word during the coding step (0 otherwise). The pooling step is the sum of all mapped vectors.

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

α ⋆ = argmin α b -Wα 2 + d • α 2 , (1)
with b being a descriptor, W the codebook matrix, α the projection coeficients and d a locality constraint. The output vector α ⋆ is thus optimized with respect to the 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. Unlike BoW, coding/pooling schemes give good performance with linear similarities, while retaining a small size. However this method is more complex to implement and it requires a fine tuning of the parameters to obtain good results.

Fisher Vectors -VLAD

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] have recently proposed a novel method called Fisher Vectors to map a set of descriptors in a single signature. Their model computes the deviation of each descriptor to a Gaussian Mixture Model of the distribution of all descriptors in the database. Then they sum these deviations for all descriptors of the image.

Jegou et al. [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] proposed a method to perform an approximation of Fisher vectors, called Vectors of Locally Aggregated Descriptors (VLAD). This method has two steps: first, a small codebook is generated by clustering. Then, the sum of all centered descriptors from image i and cluster c is computed:

ν c,i = r (b rci -µ c ) ; (2)
where b rci are the descriptors for image i in cluster c and µ c is the center of the cluster. The final signature ν i is obtained by concatenating ν c,i for all c, and is thus of size C × D, with C the size of codebook and D the size of features. Like the coding/pooling, this approach gives good performance with linear metric. The dimension of VLAD vectors is large and depends on the size of descriptors, however it can be significantly reduced using techniques like PCA [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF].

VLAT -A tensor based aggregation

The Vector of Locally Aggregated Tensors (VLAT) is an improvement of VLAD recently presented by Picard et al [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. In this method, the authors propose to aggregate tensor products of local descriptors to produce a unique signature.

First, they compute a visual codebook of C visual words over a sample image set using k-means.

Then, they compute the mean descriptor µ c and mean centered tensor T c of each cluster c:

µ c = 1 |c| i r b rci , (3)
T c = 1 |c| i r (b rci -µ c )(b rci -µ c ) ⊤ , (4)
with |c| the number of descriptors in cluster c and b rci the descriptors of image i belonging to cluster c.

For each image and each cluster, a signature T i,c is computed by aggregating the centered tensors of centered descriptors:

T i,c = r (b rci -µ c )(b rci -µ c ) ⊤ -T c . (5)
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 ) . (6)
The VLAT gives very good results in similarity search and automatic indexing of images with linear metric, but leads to large feature vectors. The size of the VLAT descriptor is C × D × D, with C the number of clusters and D the size of descriptors.

COMPACT VLAT

We propose to drastically reduce the size of VLAT features, while keeping their discriminative power. Our method uses the following scheme : first we preprocess the VLAT by performing a normalization step. Then, we compute the Gram matrix of normalized VLAT for some training set of images. We perform a low rank approximation of the Gram matrix and compute the set of projection vectors associated with the generated subspace. The compact VLAT signatures are the projections of normalized VLAT using the obtained projection vectors.

Normalization

First, we compute the set of VLAT signatures of the image database. Then, we perform a two steps normalization. we compute the power norm of v i to produce v ′ i :

∀j, v ′ i [j] = v i [j] α , (7)
With α typically set to 0.5. Then, we normalize the vector v ′ i with the ℓ 2 -norm:

x i = v ′ i v ′ i ( 8
)
x i is the normalized VLAT signature. We use the performance of normalized VLAT signatures for comparison with performance of the compact VLAT signatures. Normalization is necessary to obtain a Gram matrix with good properties (unitary diagonal, well-conditioned, etc).

Low rank approximation

We compute the Gram matrix G of centered normalized VLAT signatures:

G i,j = (x i -m x ) ⊤ (x j -m x ), (9)
with m x the mean of x i . Then, we compute the eigenvalues and eigenvectors of the Gram matrix:

(λ 1 . . . λ l . . . λ N ) = eigval(G), (10)
(u 1 . . . u l . . . u N ) = eigvect(G), (11)
with λ 1 ≥ λ 2 ≥ • • • ≥ λ N and u l the eigenvector associated the eigenvalue λ l . We compute a low rank approximation of the Gram matrix. We denote by L t the matrix with the t largest eigenvalues on the diagonal:

L t = diag(λ 1 . . . λ t ), (12)
and we denote by U t the matrix of the first t eigenvectors:

U t = [u 1 . . . u t ] . (13)
We can then define G t as an approximation of G:

G t = U t L t U ⊤ t . (14)
Then, we compute the projectors of VLAT signatures in approximated subspace:

P t = XU t L -1/2 t , ( 15
) with X = [x 1 -m x . . . x N -m x ]
is the matrix of centred VLAT signatures. This method is analog to Kernel-PCA using a dot product Kernel.

Projection vectors

For each image, we compute the projection of VLAT signature in the approximated space:

y i = L -1/2 t P ⊤ t x i . ( 16
)
y i contains an approximate and compressed version of x i . This method keeps the most informative directions of VLAT feature space. Moreover, the normalization by L -1/2 t produces axes of equal variance in the projected subspace. Let us compute the covariance matrix of projections Y = [y 1 . . . y N ]:

YY ⊤ = L -1/2 t P ⊤ t XX ⊤ P t L -1/2 t (17) = L -1 t U ⊤ t GGU t L -1 t . ( 18
)
Let us denote by Ū the matrix of remaining eigenvectors such that G = U t L t U ⊤ t + ŪL Ū⊤ , then YY ⊤ simplifies to:

YY ⊤ = L -1 t U ⊤ t (U t L t U ⊤ t + Ū⊤ L Ū) 2 U t L -1 t (19) = L -1 t U ⊤ t U t L t U ⊤ t U t L t U ⊤ t U t L -1 t (20) = I, (21)
since U ⊤ t U t = I and U ⊤ t Ū = 0. The size of y i is very small compared to the size of x i , as it directly depends on t (varying from 1 to N). The final step is a ℓ 2 -normalization of y i :

z i = y i y i . ( 22
)

EXPERIMENTS

We used the Holidays database to evaluate our compact VLAT signatures and compare them with VLAT and VLAD signatures. The Holidays dataset is a set of images drawn from personal holidays photos, created to test methods of similarity search. It contains 1491 images gathered in 500 subgroups, each of them represents a distinct scene or object (Figure 1). Images in this database are in high resolution color. The Holidays dataset includes set of SIFT descriptors.

Image Similarity

We used the same evaluation setup as Jegou et al. [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]. For all our experiments, we compute a set of codebook (64, 256, 1024 visual words) with all provided SIFT descriptors1 . For each experiment, we evaluate the influence of parameter t (number of selected eigenvalue and eigenvector) as a function of the size of the codebook. We compare our results with those obtained with VLAD and Compact VLAD. We used our method to build compact VLAD. Note that for all method and experiments, we used the same codebooks. First, we propose to examine the importance of normalization of VLAT and VLAD signatures. For this, we evaluate the compact signatures without the normalization step (section 3.1). We can see (Table 1) that the normalization step is essential to keep the performance after the of low rank approximation. Due to the large size of the VLAT descriptors, it is more sensitive to normalization. Table 2 is the comparison between the compact VLAT and standard VLAT descriptors. We see that, whatever the size of the codebook, there are values of t for which the compact VLAT signatures give better results than the standard VLAT signatures. When keeping fewer eigenvalues, noise is introduced by the normalization of the projection vectors in eq. 15. There is a optimal level of approximation where information is better represented in the compact VLAT than in the standard VLAT. We see that the compact VLAD (Table 3) has the same behavior as the VLAT compact, there is a optimal level of approximation which maximizes results. Comparing the results of the Compact VLAT with those of standard VLAD and compact VLAD, we can see that our method generally gives better results. With a codebook of size 1024, we have 12.1% of gain compared to standard VLAD.

Large Scale -Similarity search

In this section, we want to test the robustness of our method on large search sets. For our tests, we used the Holidays database artificially enlarged by subsets of different sizes (10k and 100k documents) from the Flickr10M database. We can then see how searching in the Holidays database is disrupted by the expansion of the database. Figure 2 shows the evolution of the mean Average Precision against the size of database, we see that our signatures have the same behavior as the VLAD feature. Our compact VLAT signatures always perform better than VLAD signatures. If we compare with the results of state-of-the-art [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] (on different codebook), we have a gain of about 11% mAP for 100k images.

CONCLUSION

In this paper, we proposed a compact image signature for similarity search in large databases. Our method consists in the projection of tensors based aggregation of local descriptors on a low dimensional subspace. This subspace is obtained by a low rank approximation of the Gram matrix on a training set. We provided experiments on the well known Holydays dataset showing that our approach gives very good results while being several orders of magnitude more compact than uncompressed signatures. Experiments on a larger dataset (100k images) lead to promising results regarding the scalability of the method.

Fig. 1 .

 1 Fig. 1. Images from Holidays dataset.

Fig. 2 .

 2 Fig. 2. Search mAP as a function of the database size (Codebook size : 64, t = 256).

Table 1 .

 1 Normalized VLAT 45.0 54.2 63.1 68.5 72.3 71.1 54.8 VLAD 35.7 43.5 49.0 51.2 50.3 47.1 21.6 Normalized VLAD 44.3 50.7 57.5 58.8 59.6 58.1 44.6 Comparison of mAP(%) between normalized or not normalized VLAD and VLAT descriptor.

						Compact VLAT
	t			16	32	64	128 256 512 1024
	VLAT		29.6 38.6 46.1 49.2 48.7 44.1 22.2
				Compact VLAT	Standard
	D. Size 16	32	64	128 256 512 1024 VLAT
	64	45.0 54.2 63.1 68.5 72.3 71.1 54.8	66.4
	256	44.6 53.6 62.4 68.2 74.6 74.2 56.7	71.8
	1024 40.1 52.0 62.3 69.2 74.2 76.0 57.1	75.7

Table 2 .

 2 Comparison of mAP(%) between compact VLAT and VLAT descriptor.

Table 3 .

 3 Comparison of mAP(%) between compact VLAD and VLAD descriptor.

http://www.vlat.fr/


Romain Negrel
email: romain.negrel@ensea.fr

David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: gosselin@ensea.fr

Using Spatial Pyramids with Compacted VLAT for Image Categorization

In this paper, we propose a compact image signature based on VLAT. Our method integrates spatial information while significantly reducing the size of original VLAT by using two pojection steps. we carry out experiments showing our approach is competitive with state of the art signatures.

Introduction

Content Based Image Categorization is a research field that has known a rapid development in the last years. The typical scheme is composed of the following steps: extraction of local image descriptors, aggregation of the descriptors in an image signature, and learning a classifier in signatures space. The most recent and successful methods are Coding/pooling [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], Fisher Vector [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF], VLAD [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], and VLAT [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. In this paper we present a new method for aggregating local descriptors based on VLAT [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. Our method improves significantly the classification results over of VLAT, while reducing its size. This paper is organized as follows: the next section describes recent related work on image representation and similarities. Section 3 introduces our novel approach. Finally we present successful experiments on the well known VOC2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF].

State of the art

In this section we present the most recent and efficient image signatures using local descriptors.

Coding/Polling Schemes

Coding/Polling methods proposed in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] by J. Wang et al. are a generalization of BoW methods [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. These methods are based on visual words dictionary. The visual words are computed using a clustering algorithm on a training set of descriptors. The Coding/Pooling schemes divide the problem into two steps. The first step maps each descriptor of the image on the codebook ("coding" step). The second step aggregates the mapped descriptors into a single signature ("pooling" step). For the Coding step in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], they compute a mapped vector α ⋆ as the result of the following reconstruction problem:

α ⋆ = argmin α ||b -Wα|| 2 + ||d • α|| 2 , (1)
with b being a descriptor, W the codebook matrix, α the projection coefficients and d a locality constraint. The output vector α ⋆ is thus optimized with respect to the reconstruction error and constrained to the projection on few nearby codewords. For the Pooling step, they propose 2 methods: Sum Pooling (sum of all codes) or Max Pooling (maximum value for each coding coefficient). Compared to BoW, the coding/pooling schemes give good performance with linear similarities, while retaining a small signature size. However this method is more complex to implement and requires a fine tuning of the parameters to obtain good results [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF].

Fisher Vector

Recently, Perronnin et al. [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] presented a new method called Fisher Vectors. The authors hypothesize the descriptors can be modeled by a probability density function denoted as u λ of parameters λ. To describe the image, they use the derivative of the log-likelihood of all image descriptors to the model. The key idea is to describe the contribution of the descriptors to the deviation of the model parameters. The model used is a GMM of parameters µ c and σ c . The elements of the Fisher Vector for each Gaussian c can be written as:

G B i µ,c = 1 T √ ωc r γ c (b ri ) bri-µ c σc , (2)
G Bi σ,c = 1 T √ ωc r γ c (b ri ) (bri-µ c ) 2 σ 2 c -1 , (3)
Where b ri are the descriptors of image i, (ω 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 final descriptor is obtained by concatenation of G Bi µ,c and G Bi σ,c for all Gaussians. The Fisher Vector method achieve very good results [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. However, Fisher Vectors are limited to the simple model of mixtures of Gaussians with diagonal matrices. Moreover, the GMM algorithm is computationally very intensive.

Vector of Locally Aggregated Tensors

In [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF], Picard et al. proposed an extension of Fisher vectors, called VLAT for Vector of Locally Aggregated Tensors. This method uses a codebook of visual words, computed with a clustering algorithm (typically: kmean). They compute the 1st and 2nd order moments for each visual word (cluster):

µ c = 1 |c| i r b rci , (4)
T c = 1 |c| i r (b rci -µ c )(b rci -µ c ) ⊤ , (5)
with |c| the number of descriptors in cluster c and b rci the descriptors of image i belonging to cluster c. For each image, the difference between image 2nd order moment and the cluster 2nd order moment is computed for each cluster c:

T i,c = r (b rci -µ c )(b rci -µ c ) ⊤ -T c . (6)
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 ) . (7)
It is advisable to perform a normalization step for best performance.

∀j, v ′ i [j] = sign(v i [j])|v i [j]| α , (8)
x i = v ′ i ||v ′ i || , (9)
with α = 0.5 typically. VLAT gives very good results in similarity search and automatic indexing of images with linear metric, but leads to large feature vectors. The size of the VLAT signature is C ×D×D, with C the number of clusters and D the size of descriptors.

Spatial pyramid binning

The spatial pyramid method [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] allows the introduction of spatial information in image signatures. The process consists in computing a set of p signatures for different regions of the image. To compute the similarity between images, the weighted sum of similarities for all regions is performed. It can be written as the following kernel function:

K(X i , X j ) = p m=1 α m k(X (m) i , X (m) j ), (10)
with k(•, •) the minor kernel function and

X (m) i ,X (m) j
the signatures of image i and j for region m.

Proposed method

We propose a new VLAT based signature that significantly reduces the size of the signature, while increasing their discriminative power. Our scheme is as follows: 1. We perform a Principal Component Analysis (PCA) within each cluster (We project the descriptors in the space of the eigenvectors of their cluster). 2. We compute VLAT signatures for different part of the spatial pyramid. 3. For some training set of images, we then compute the Gram matrix using Eq. ( 10) with a linear minor kernel. 4. We then perform a low rank approximation of the gram matrix and compute the set of projection vectors associated with the generated subspace. The final signatures are the projections of normalized pyramid VLAT using the obtained projection vectors.

Pre-projection: descriptors PCA by cluster

As for standard VLAT, we compute the 1st and 2nd order moments (Eq. 4 and 5) of each cluster. We perform a Takagi factorization of T c matrix:

T c = V c D c V ⊤ c , (11)
where D c is a diagonal matrix formed from the eigenvalues of T c and V c is a matrix of eigenvectors of T c . We denote by D c,pc the matrix with the p c largest eigenvalues on the diagonal:

D c,pc = diag(λ c,1 . . . λ c,pc ), (12)
with λ 1,pc ≥ λ 2,pc ≥ • • • ≥ λ c,pc and we denote by V c,pc the matrix of the first p c eigenvectors:

V c,pc = [v c,1 . . . v c,pc ] . (13)
We perform an approximation of the image descriptors by projection on the subspace spanned by the p c largest eigenvectors of T c :

b ′ rci = V ⊤ c,pc (b rci -µ c ). (14)
We can thus rewrite Eq. ( 6): Like in VLAT, we concatenate each cluster signature and do proper normalization. Due to the tensor product, the size of the new signature depends on the square of the number of eigenvector selected in each cluster

T ′ i,c = V ⊤ c,pc T i,c V c,pc . (15
C c=1 p 2 c .
We propose 2 strategies for selecting the eigenvectors in each cluster. The fixed dimension method is to arbitrarily set the number of eigenvalue that is kept for each cluster :

p 1 = • • • = p C .
The error threshold method is to set a threshold ε on the error introduced by the subspace projection:

p c = min p p s.t. 1 - p i=1 λ c,i D i=1 λ c,i ≤ ε. (16)

Spatial pyramid

To add spatial information, we compute the signature of Eq.( 15) for different region of spatial pyramid. The spatial regions are obtained by dividing image using 1× 1, 3 × 1, and 2 × 2 grids, for a total of 8 regions like in most image categorization setups [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. We use a linear metric for classification (e.g. the minor kernel of Eq. ( 10) is the dot product). Hence, the global signature for the image is the concatenation of weighted signatures for each region of the pyramid:

x i = ( √ α 1 x i,1 . . . √ α m x i,m . . . √ α 8 x i,8 ) , (17)
with x i,m is the signature of the image i computed in the area m of the pyramid.

Post-projection: Low rank approximation

Given a training set S of N images ,we compute the Gram matrix G of signatures defined in Eq. ( 17):

G i,j = x ⊤ i x j , x i ∈ S, x j ∈ S. (18)
Then, we perform the Takagi factorization of G :

G = ULU ⊤ , ( 19
) L = diag(λ 1 . . . λ i . . . λ N ), ( 20
) U = (u 1 . . . u i . . . u N ), (21)
with λ 1 ≥ λ 2 ≥ • • • ≥ λ N and u i the eigenvector associated with the eigenvalue λ i . We want to compute a low rank approximation of the Gram matrix. We denote by L t the matrix with the t largest eigenvalues on the diagonal:

L t = diag(λ 1 . . . λ t ), (22)
and we denote by U t the matrix of the first t eigenvectors:

U t = [u 1 . . . u t ] . (23)
Then, we compute the projectors in the approximated subspace:

P t = XU t L -1/2 t , (24)
with X = [x 1 . . . x N ] is the matrix of signatures for the training set S. This method akin to Kernel-PCA using the Spatial Pyramidal Kernel with a linear minor kernel.

Projection vectors

For some image i, we compute the projected signature in the approximated space:

y i = P ⊤ t x i , (25)
y i contains an approximate and compressed version of x i (from eq.( 17)). This method selects the most energy directions of signature space. The size of y i is very small compared to the size of x i , as it directly depends on t (varying from 1 to N). The final step is a ℓ 2 normalization of y i :

z i = y i ||y i || . ( 26
)

Experiments

In this section we describe our experimental setup and some results on the PASCAL-VOC 2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF]. This dataset consists in about 10,000 images and 20 categories, and is divided into 3 parts : train, val and test. We used an 1-vs-rest linear SVM classifier trained on train + val sets and tested on the test set. We used a fast stochastic gradient descent algorithm with C = . We used Mean Average Precision (mAP) over the 20 classes for performance measurement. We extracted HOG features with 4 different scales (4px, 6px, 8px and 10px cell size), every 3 or 6 pixels, depending on the test. We used a simple k-means clustering algorithm in order to obtain the codebook. For the low-order approximation of the post-projection step, we used the full dataset Gram matrix.

Pre-projection effect

In this section we study the action of the preprojection (section 3.1). We used a 6 pixels step for extracting HOG features, a codebook of 64 visual words, only the first level of the spatial pyramid (1 × 1) and no post-projection. To compare the two strategies for estimating p c , we measured the classification score against the signature size. For the fixed dimension strategy, we reduced the descriptor size to 32, 48, 64, 80, 112 and 128 dimensions. For the error threshold strategy, we tested 30%, 25%, 20%, 15%, 10%, 5% and 0% of reconstruction error rate ε. As we can see in Figure 2 the pre-projection significantly increases the performance relative to VLAT even if it greatly reduces the signatures size. We can also see that the thresholding strategy gives better results, which is consistent with the fact it balances the error among clusters.

Classification results

To compare our method to the state of the art, we used a similar setup to [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. We used a 3 pixels step for extracting HOG features, a codebook of 256 visual words, and all levels of the spatial pyramid. We set the threshold ε to 10% of reconstruction error (about 74 dimensions). We used all projectors in post-projection step (about 10k signature size). We can see from Table 1, our signature gives comparative results to the of state of the art methods. However, our signature is much smaller and we used HOG descriptors (simpler than SIFT used in [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]).

Conclusion

In this paper, we proposed a new image signature based on VLAT. Our representation increases discriminative power of VLAT by introducing a spatial information while reducing its size significantly. Tests on VOC 2007 dataset show that our signature gives results similar to state of the art methods, with simpler descriptors and smaller signature. The results are very promising, and we are looking forward to a full investigation of the influence of two projection steps.

Figure 2 .

 2 Figure 2. Effect of pre-projection10[START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF]. We used Mean Average Precision (mAP) over the 20 classes for performance measurement. We extracted HOG features with 4 different scales (4px, 6px, 8px and 10px cell size), every 3 or 6 pixels, depending on the test. We used a simple k-means clustering algorithm in order to obtain the codebook. For the low-order approximation of the post-projection step, we used the full dataset Gram matrix.

Images from PASCAL Visual Object Classes Challenge 2007.

	aeroplane bicycle	bird	boat	bottle	bus	car	cat	chair	cow
	table	dog	horse	bike	person	plant	sheep	sofa	train	tv
		Figure 1.
										)

Table 1 . Image classification results on Pascal VOC 2007 dataset compared to [2]

 1

				mAP aeroplane bicycle	bird	boat	bottle	bus	car	cat	chair cow
	Our method 61.5	80.3	72.2	51.4	71.4	28.1	72.1	81.6	63.1 54.4 47.5
			FV	61.7	79.0	67.4	51.9	70.9	30.8	72.2	79.9	61.4 56.0 49.6
			LLC	57.6	71.1	62.9	47.4	67.7	25.2	62.7	77.0	59.6 54.2 45.3
				Size	table	dog	horse bike person plant sheep sofa train	tv
	Our method	10k	57.8	46.5	81.1	70.3	86.8	30.8	41.2	54.0 84.1 54.9
			FV	320k	58.4	44.8	78.8	70.8	85.0	31.7	51.0	56.4 80.2 57.5
			LLC	200k	51.6	44.2	75.5	67.1	83.3	27.6	45.7	53.6 76.0 52.3
		58
		57
	mAP(%)	54 55 56			Error threshold method Fixed dimension method VLAT
		53
		52	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 •10 5 Signature size