Giorgos Tolias

Jégou Hervé

Inria

Visual query expansion with or without geometry: refining local descriptors by feature aggregation

Keywords: image retrieval, query expansion, hamming embedding

This paper proposes a query expansion technique for image search that is faster and more precise than the existing ones. An enriched representation of the query is obtained by exploiting the binary representation offered by the Hamming Embedding image matching approach: The initial local descriptors are refined by aggregating those of the database, while new descriptors are produced from the images that are deemed relevant.

The technique has two computational advantages over other query expansion techniques. First, the size of the enriched representation is comparable to that of the initial query. Second, the technique is effective even without using any geometry, in which case searching a database comprising 105k images typically takes 79 ms on a desktop machine. Overall, our technique significantly outperforms the visual query expansion state of the art on popular benchmarks. It is also the first query expansion technique shown effective on the UKB benchmark, which has few relevant images per query.

Introduction

This paper considers the problem of image and object retrieval in image databases comprising up to millions of images. The goal is to retrieve the images describing the same visual object(s) as the query. In many applications, the query image is submitted by a user and must be processed in interactive time.

Most of the state-of-the-art approaches derive from the seminal Video-Google technique [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. It describes an image by a bag-of-visual-words (BOVW) representation, in the spirit of the bag-of-words frequency histograms used in text information retrieval. This approach benefits from both the powerful local descriptors [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF]3] such as the SIFT, and from indexing techniques inherited from text information retrieval such as inverted files [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF]5]. Exploiting the sparsity of the representation, BOVW is especially effective for large visual vocabularies [6,[START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

This analogy with text representation is a long-lasting source of inspiration in visual matching systems, and many image search techniques based on BOVW have their counterparts in text retrieval. For instance, some statistical phenomenons such as burstiness or co-occurrences appear both in texts [START_REF] Katz | Distribution of content words and phrases in text and language modeling[END_REF]9] and images [10, [START_REF] Chum | Unsupervised discovery of co-occurrences in sparse high dimensional data[END_REF][START_REF] Cinbis | Image categorization using fisher kernels of non-iid image models[END_REF] and are addressed in similar ways.

One of the most successful techniques in information retrieval is the query expansion (QE) principle [13], which is a kind of automatic relevance feedback. The general idea is to exploit the reliable results returned by an initial query to produce an enriched representation, which is re-submitted in turn to the search engine. If the initial set of results is large and accurate enough, the new query retrieves some additional relevant elements that were not present in the first set of results, which dramatically increases the recall.

Query expansion has been introduced to the visual domain by Chum et al. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], who proposed a technique implementing the QE principle and specifically adapted to visual search. Several extensions have been proposed to improve this initial QE scheme [15,16,[START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF]. Although these variants have improved the accuracy, they suffer from two inherent drawbacks which severely affect the overall complexity and quality of the search:

• First, they require a costly geometrical verification step, which provides the automatic annotation of the relevant set and is typically performed on hundreds of images.

• Second, the augmented query representation contains significantly more non-zero components than the original one, which severely slows down the search. It is reported [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF] that typically ten times more components are non-zeros. Since querying the inverted file has linear complexity in the number of features contained in the query vector, the second query is therefore one order of magnitude slower than the first.

Expansion methods that do not use any costly geometrical verification are typically based on an off-line stage with quadratic complexity in the number of database images [START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF]19,[START_REF] Zhang | Query specific fusion for image retrieval[END_REF]. They are thus limited to collections of small and fixed size.

In another line of research, several techniques address the loss in quantization underpinning BOVW, such as the use of multiple assignment [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF] or soft quantization [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. In a complementary manner, the Hamming Embedding (HE) technique [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] dramatically improves the matching quality by refining the descriptors with binary signatures. HE is not compatible with existing QE techniques because these assume a vector representa-→ Figure 1: Query image (left) and the features selected (yellow+cyan) from the retrieved images to refine the original query. The features in red are discarded. Cyan features correspond to visual words that appear in the query image, and yellow ones to visual words that were not present in it. The selection of the depicted images and features has not involved any geometrical information. tion of the images. A noticeable exception is the transitive QE, which does not explicitly exploit the underlying image representation. However, this variant is not satisfactory with respect to query time and performance.

This paper, for the first time, proposes a novel way to exploit the QE principle in a system that individually matches the local descriptors, namely the HE technique. The new query expansion technique is both efficient and precise, thanks to the following two contributions:

• First, we modify the selection rule for the set of relevant images so that it does not involve any spatial verification. The images deemed relevant provide additional descriptors that are employed to improve the original query representation. Unlike other QE methods, it is done on a per-descriptor basis and not on the global BOVW vector. Figure 1 depicts an example of images and features that are selected by our method to refine the original query.

• The second key property of our method is that the set of local features is aggregated to produce new binary vectors defining the new query image representation. This step drastically reduces the number of individual features to be considered when submitting the enriched query.

To our knowledge, it is the first time that a visual QE is successful without any geometrical information: The only visual QE technique [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] that we are aware of performs poorly compared with other variants such as the average query expansion (AQE). In contrast, our technique used without geometry reaches or outperforms the state of the art. Interestingly, it is effective even when a query has few corresponding images in the database, as shown by our results on the UKB image recognition benchmark [6]. Incorporating geometrical information in the pipeline further improves the accuracy. As a result, we report a large improvement compared to the state of the art. We further demonstrate the superiority of our method compared to a simple combination of HE with QE: The property of feature aggregation not only reduces the expanded query complexity, but further improves performance.

The paper is organized as follows. Section 3 introduces our core image system and Section 7 a post-processing technique for SIFT descriptors that is shown useful to improve the efficiency of the search. Section 4 introduces our Hamming Query Expansion (HQE) method and Section 5 describes our key aggregation strategy of local features. Section 6 describes how to exploit geometrical information with HQE. The experimental results presented in Section 8 demonstrate the superiority of our approach over concurrent visual QE approaches, with respect to both complexity and search quality, on the Oxford5k, Oxford105k and Paris benchmarks.

Related work

Chum and colleagues [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] were the first to translate the query expansion principle to the visual domain. Most of the variants they propose rely on a spatial verification method, which filters out the images that are not geometrically consistent with the query. The authors investigate several methods to build a new query from the images deemed relevant. The average query expansion is of particular interest and usually considered as a baseline, as it is the most efficient variant [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] and provides excellent results. It is conceptually simple: A new term-frequency inverse document frequency (TFIDF) vector is obtained as the average of the results assumed correct and spatially back-projected to the original image.

Following this first work, a number of QE variants and extensions have been proposed [15,16,[START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF]. Using incremental spatial re-ranking, the query representation is updated by each spatially verified image and extended out of the initial query region [16]. Another extension is to learn, on-the-fly, a discriminative linear classifier [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF] to define the new query instead of the average in AQE.

Other kinds of expansion have been proposed for fixed image collections [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Turcot | Better matching with fewer features: the selection of useful features in large database recognition problems[END_REF]. They rely on the off-line pairwise matching of all images pairs and aim at identifying the features coming from the same object using spatial verification, which is rather costly as the complexity is quadratic in the number of images. They also assume that the image collection is fixed:

The selection depends on a given set of images. These methods are also related to other methods exploiting the neighborhood of the images within a given collection [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF][START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF], in particular by updating the comparison metric or by employing reciprocal nearest neighbors as a filtering rule. For instance, Qin et al. [START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF] constructs a graph that links related images, and uses k-reciprocal nearest neighbors at query time to define a new similarity function that re-orders the images. Again, the cost of constructing and storing the graph in memory is impracticable for large datasets. In a similar spirit, Shen et al. [19] exploit the ranked lists of independent queries issued with top-ranked images. Query time increases significantly as it is linear to the number of those queries. A recent graph-based method combines multiple similarity measures to perform re-ranking [START_REF] Zhang | Query specific fusion for image retrieval[END_REF]. The cost of such an offline procedure can be undertaken only for small collections. In the work of Chum and Matas [START_REF] Chum | Large-scale discovery of spatially related images[END_REF], the quadratic cost is addressed by starting from seed query images, yet their method requires a costly spatial verification stage.

The query expansion method of Kuo et al. [26] is also related to our work. They also use a set of binary vectors for an image representation and try to identify database image regions which are similar to the query. The initial representation is not enhanced, but new independent queries are rather issued and a final fusion is performed on the ranked lists. Li et al. [START_REF] Li | Query expansion enhancement by fast binary matching[END_REF] straightforwardly use binary descriptors but only to select the relevant matches. As in other QE methods, their method relies on geometry and produces a larger set of features.

The core image system

This section describes the image search system based on Hamming Embedding upon which our query expansion techniques are built. This baseline method follows the guideline of the existing HE technique [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], which proceeds as follows. An image is represented by a set P of local SIFT descriptors [3] extracted with the Hessian-Affine detector [28].

BOVW and Hamming Embedding. The descriptors are quantized using a flat k-means quantizer, where k determines the visual vocabulary size. A descriptor p ∈ P is then represented by a quantization index, called a visual word v(p). Computing and normalizing the histogram of visual words produces the BOVW representation. It can also be seen as a voting system in which all descriptors assigned to a specific visual word are considered as matching with a weight related to the inverse document frequency [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF].

In order to refine the quality of the matches and to provide more reliable weights to the votes, the HE technique [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] further refines each descriptor p by a binary signature b(p), providing a better localization of the descriptor by subdividing the quantization cell v(p). HE compares two local descriptors q and p that are assigned to the same visual word v(p) = v(q) by computing the Hamming distance h(q, p) = b(q)b(p) 1 between their binary signatures. If the Hamming distance is above a predefined threshold h t , the descriptors are considered as non matching and zero similarity is attached. A significant benefit [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]10] in accuracy is obtained by weighting the vote as a decreasing function of the Hamming distance. In this paper, we adopt the Gaussian function used in [10] with σ equal to one fourth of the binary signature size.

The burstiness phenomenon in images was first revealed and tackled by Jegou et al. [10]. It takes into account descriptors that individually trigger multiple matches between specific pairs of images, which is often the case because of repetitive structures, or features which are abnormally common across all database images. Several normalizations have been proposed, from which we adopt the one that down-weights a given match score by the square root of the number of matches associated with the corresponding query descriptor [10]. This strategy is similar to the successful component-wise power-law normalization later proposed for BOVW or Fisher Kernels [29], but here applied to a voting technique.

Multiple assignment (MA). BOVW and HE handles descriptors assigned to the same visual word. However quantization losses are introduced when truly matching descriptors are assigned to different visual words. This has been addressed by assigning multiple visual words to each descriptor [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. We apply MA on the query side only in order to keep memory requirements unchanged [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. In the rest of the paper, the initial method that assigns a descriptor a single visual word is denoted by SA (single assignment) to distinguish it with MA.

HE with query expansion

This section defines a query expansion technique based on HE and not involving any geometrical information. We revisit the different stages involved in the QE principle. We first describe how reliable images are selected from the initial result set. Then we detail the way an enriched query is produced from the images deemed relevant. The key subsequent aggregation step and the use of geometry will be introduced later in Sections 5 and 6, respectively.

Selection of reliable images

As in all query expansion methods [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]15,16,[START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], the core image search system processes an initial query. The resulting set is analyzed to identify a subset of reliable images that are likely to depict the query object, and therefore to provide additional features that will be subsequently exploited in the augmentation stage.

In the following, we will denote the local features of the query image by Q, and those of a given database image by P, respectively. As a criterion to determine the relevant images, we count the number C(Q, P) of "strict" feature correspondences between the query and images in the short-list. It is given by

C(Q, P) = |{(q, p) ∈ Q × P : h(q, p) ≤ h ⋆ t }| , (1)
where the threshold h ⋆ t is lower than the Hamming embedding threshold h t used for initial ranking. Such a lower threshold allows for a higher true positive to false positive ratio of matches [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. It provides a strict way to count correspondences in a manner that resembles the number of RANSAC inliers commonly used to verify the images [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. It is less precise than RANSAC, yet it has the advantage of not using any geometry. It is therefore much faster.

Figure 2 illustrates, for a pair of images, the matching features obtained using BOVW and HE. We consider two different thresholds for HE to show the impact of the strict threshold h ⋆ t = 16 on selected features. Observe that HE matching filters out many false matches compared to BOVW. With a lower threshold value, the filtering is not far in quality from that of a spatial matching method.

An image is declared reliable if at least c t correspondences are satisfied, which formally leads to define the set of reliable images as

L Q = {P : C(Q, P) ≥ c t }. (2)
In practice, only the images short-listed in the initial search are considered as candidates for the set of reliable images. In our experiments, we count the number of correspondences with Equation 1 only for the top 100 images. Figure 3 shows examples of queries and the corresponding reliable images. Although some negative images are selected and some positive ones are not, the result is not far from what spatial verification would produce. This suggests that selecting reliable images with HE and a low threshold is sufficient for the purpose of QE, as proposed in this section. The proposed procedure for detecting reliable images gives a rate of 92.4% true positive instances in L Q . Note, this is achieved without any geometry information.

Feature set expansion

First, let us recall that a feature descriptor is described by both a visual word and a binary signature. Our augmentation strategy, i.e., how we introduce new local features in the representation, is partly based on the selection of visual words that are not present in the original query.

Since a large proportion of the reliable images depicts the same object, the visual words frequently occurring in the images of the reliable set L Q are likely to depict the query object rather than the background. Our selection strategy is simple and consists in selecting the most frequent visual words occurring in L Q . More precisely, we sort the visual words contained in the images of L Q by the number of reliable images in which they appear. The top ranked words are selected and define the set of reliable visual words V, which may include both visual words that are present or absent in the query image. The latter are referred to as the augmented visual words. Their count is controlled by a parameter α to ensure that the number of reliable visual words in the new query is proportional to that of the original query, as

|V \ V Q | = α • |V Q |, (3)
where V Q is the set of visual words occurring in the query. A typical value of parameter α is 0.5 (see Section 8).

The initial query set is enriched with the features of the reliable images assigned to the reliable visual words. Define as

G = {p ∈ P : P ∈ L Q ∧ v(p) ∈ V} (4)
the union of all features of reliable images assigned to some reliable words. It defines the set of database features used to augment the initial query. In other terms, this set is merged with the initial query feature set to construct the augmented query as

Q E = Q ∪ G. (5)
Figure 4 depicts some features from reliable images assigned to reliable visual words. Observe that, even without any spatial information, selected visual words are detected on the foreground object. Moreover, each visual word corresponds not only to similar image patches, but often to the exact same patch of the object, as if spatial matching was used. This appears to be the case for either visual words which appear (top) or miss (bottom) in the query.

A simple way to construct an enriched query is to use the expanded set of features as the new image representation. However, similar to existing QE strategies, such an approach leads to a high complexity because the number of features explodes. We observe that it is typically multiplied by a factor ranging from 10 to 20 for typical values of α, as analyzed in the experimental section 8. This drawback is shared by other effective techniques on query expansion [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], for which this problem leads to produce a BOVW vector having 10 times more non-zero components than the initial one. In the next section, we address this issue by proposing an aggregation strategy that drastically reduces the number of features.

QE with feature aggregation

The average query expansion technique [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] averages BOVW vectors to produce the new query. In this section, we explain how local descriptors are individually refined or created from binary signatures of the set of reliable features. At this stage, the augmented set contains multiple instances representing the same visual patches, either in the initial query or not. Descriptors associated to the same patch are expected to have similar binary signatures. The strategy presented below implicitly exploits this underlying property to produce the new set of query descriptors which is less redundant.

First, note that the selection strategies for images and features presented in the previous subsections introduce a few false positives in the augmented feature set. This is the cost to pay for not performing the selection with a stringent spatial matching technique: Our inliers are not selected as reliably as in other query expansion methods. The aggregation operation proposed hereafter comes as a complement on our selection method, as it is robust enough to false positives. In contrast, averaging over normalized TFIDF vectors of similar images [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], as done in AQE, is sensitive to background and noisy features.

Our aggregation scheme is inspired by methods [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF] such as the VLAD technique, which aggregates the descriptors per visual word to produce a vector representation of an image. In our method, we aggregate the features of Q E that are assigned to the same visual word. Therefore, our technique produces exactly one binary signature per visual word occurring in Q E . Our motivation is that the true matching patches are likely to overrule the false positives. This actually happens in practice because the true correspondences are more numerous and are associated with more consistent binary signatures.

Our aggregation scheme is related to the recent work of Tolias et al. [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF], where descriptors are aggregated per visual word for query and database images individually. A selectivity function is employed to appropriately weight the similarity scores. Our approach differs in that we rather aggregate descriptors collected from many images instead of a single one. In their work, aggregation consistently improves the performance in all cases. It is attributed to the way burstiness is handled. As a result, the voting scheme ensures that at most one correspondence is established for each visual word, and therefore at most one for each descriptor.

For each visual word v appearing in Q E , a new binary signature b(v) is obtained by computing the median values over all the bit vectors occurring in Q E and assigned to v. If the numbers of 0 and 1 are equal for a particular bit component, the tie is arbitrarily resolved by assigning either 0 or 1 with equal probabilities. This new set of descriptors comprises exactly one binary signature per visual word and serves as the new query, which is then submitted to the system.

In the remainder of this paper, we refer to the method described in this section as Hamming Query Expansion (HQE).

Remark. HQE differs from a simple combination of HE with QE. Firstly, our QE scheme is the first not to use any geometrical information in order to identify relevant images. Secondly, only the most frequent visual words appearing among relevant images are collected, avoiding the inclusion of false matches to the expanded query. Finally, the proposed feature aggregation, in addition to drastically reduce the expanded query size, further improves the performance. As shown in our experiments.

Geometrical information

This section proposes a variant of our method to further eliminate some incorrect matches by including some spatial information in the loop. For this reason and as shown later in the experimental section, it is not as fast as the HQE strategy proposed in Sections 4 and 5. However, this approach further improves the performance and is therefore interesting in some situations where one would trade an interactive time against any improvement in accuracy.

It proceeds as follows. The matches are collected with the regular HE technique, i.e., they are returned by the first query. Instead of calculating the number of correspondences with Equation 1, we rely on the number C g (Q, P) of inliers found with a spatial matching technique. For this purpose, we have used the spatial verification procedure proposed by Philbin et al. [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Similar to other QE techniques, this procedure is applied on the top ranked images only. An image is declared reliable if the number of inliers is above a pre-defined threshold. The estimation of the affine transformation is then further exploited to filter the expanded feature set. As first suggested by Chum et al. [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF], the matching features associated with the reliable images are projected back to the query image plane. Those falling out of the query image borders are filtered out.

The remaining steps of this variant then become similar to the HQE method of Sections 4 and 5. The only difference is that the input set of reliable features is different. Therefore, we first select the reliable visual words and perform the feature set expansion. The aggregation is similarly applied to produce one binary vector per visual word. Note that, the reliable images, as detected by spatial matching, are ranked in top positions.

Figure 5 depicts the descriptors selected for the HQE expanded set with and without geometry. Notice that even without geometry, most of the selected features are localized on the target object. The geometry effectively filters out the remaining features that do not lie on the query object.

Implementation details

In this section we introduce a new post-processing stage for SIFT descriptors, which interest is evaluated in different setups.

Root-SIFT. It was recently shown [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] that square rooting the components of SIFT descriptors improves the search performance. This is done either by L 1 -normalizing the SIFT descriptor [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF] prior to the square-rooting operation or, equivalently, by [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] square-rooting the components and normalizing the resulting vector in turn with respect to L 2 . This operation amounts to computing the Hellinger distance instead of the Euclidean one. The impact of this scheme is evaluated in Table 1 on the Oxford5k building benchmark [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] for both BOVW and HE, without the burstiness processing. Following the standard and shifting (denoted by -µ). Post-processed descriptors are used to create the codebook, perform assignment to visual words and create the binary signatures used in HE. We have performed 10 independent experiments on Oxford5k with distinct vocabularies (k=16k) to report mean performance and standard deviations.

evaluation protocol, we measure the mean average precision (mAP). In order to cope with the variability of the results due to the sensitivity of k-means to the initial random seeds, we average the results over 10 runs with different vocabularies and report the standard deviation. We observe an improvement provided by square-rooting the components, which is statistically significant when used with HE.

However, as a side-effect of this processing, we observe that Root-SIFT introduces an unexpected complexity overhead, resulting from less balanced inverted lists. The undesirable impact of uneven inverted lists was first noticed by Nister et al. [6] and is commonly measured by the imbalance factor (IF) [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], which is a multiplicative factor reflecting the deviation from perfectly balanced lists. For instance, IF=2 means that, on average, two times more individual descriptor comparisons are per-formed compared to the case where the lists have equal lengths. Table 1 shows that this negative effect, which was not reported for this RootSIFT variant [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Jain | Hamming embedding similarity-based image classification[END_REF], is statistically significant.

Shift-SIFT.

In order to reduce this undesirable effect, we introduce another processing method for SIFT descriptors referred to as shift-SIFT. It is inspired by the approach proposed for BOVW vectors [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF], which aims at handling "negative evidences" by centering the descriptors and L 2 normalizing them in turn. It gives more importance in the comparison to the components which are close to 0, and improves the performance in the case of BOVW vectors.

Table 1 shows the interest of this shifting strategy applied to SIFT descriptors. We have use SA and no burstiness normalization in this experiment (conclusions are similar in other setups). Performance is mainly unaffected. Yet, this approach provides more balanced lists and therefore reduces the search complexity by about 4% at no cost, as reflected by the IF measure. We use this shifting strategy combined with L 2 Root-SIFT [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] in all our experiments.

Experiments

This experimental section first introduces the datasets, gives details about the experimental setup, and evaluates the impact of the parameters and variants. Our technique is then compared with the state of the art on visual query expansion before a discussion on the complexity.

Datasets and experimental setup

Datasets and measures. Query expansion techniques are only effective if the dataset consists of several relevant images for a given query. We evaluate the proposed method on two publicly available datasets of this kind, namely Oxford5k Buildings [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF], but also on a dataset where queries have only few corresponding images, that is UKB [6]. Following the standard evaluation protocols, we report mean Average Precision (mAP) for the two first and use the score definition associated with UKB: the average number of correct images ranked in first 4 positions (from 0 to 4). As for other QE works, the large scale experiments are carried out on the Oxford105k dataset, which augments Oxford5k with 100k additional distractor images.

Features and experimental setup. For Oxford5k and Paris, we used the modified Hessian-Affine detector proposed by Perdoch et al. [START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF] to detect local features. The extracted SIFT descriptors have been subsequently post-processed by using the L 2 Root-SIFT and shift-SIFT procedure, as described in Section 3. For UKB, we have used the same features provided by the authors of the papers [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF][START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF]. We follow the more realistic, less biased approach, of learning the vocabulary on an independent dataset. That is, when we use Oxford5k for evaluation, the vocabulary is learned with features of Paris and vice versa. Similarly, learning the medians of Hamming Embedding is carried out on the independent dataset.

Unless otherwise stated, we use a visual vocabulary comprising k = 65, 536 visual words, binary signatures of 64 dimensions, and apply HE with weights and burstiness normalization. In all our experiments, the reliable images for our approach, either without or with spatial matching, are selected among top 100 ones returned by the baseline system. When using MA, it is applied on the query side using the 3 nearest visual words to limit the computational overhead of using more.

MA produces more correspondences than single assignment (SA), therefore the probability of finding a false positive match is increased even with spatial matching and the matching parameters should be stricter [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF]. We set the minimum number of correspondences to c t = 4 with SA and to c t = 5 with MA.

Two factors introduce some randomness in the measure with our approach: The random projection matrix (in HE) and the random decision used to resolve ties when aggregating binary signatures. Therfore, each experiment is performed 5 times using distinct and independent parameters. We report the average performance and standard deviation to assess the significance of our measurements.

Impact of the parameters

Thresholds. The strict threshold h ⋆ t is constant and set to 16 in all our experiments. Figure 6 shows the impact of the parameter h t . The performance is not very sensitive around the optimal values attained at h t = 22 or h t = 24, depending on the setup. Note already that HQE gives a significant improvement compared to the HE baseline. In the rest of our experiments, we set h t = 24 in all cases, similar to most works based on HE. We have fixed α = 0.5 for this preliminary experiment, which implies that the size of the new query is at most 1.5 times larger than the initial one. In practice, it is much smaller thanks to the descriptors aggregation. See, for instance, Table 3 to compare the average number of descriptors used in the original and augmented queries.

The parameter α (see Section 4) controls the size of the augmented query. Figure 7 presents its impact on the performance. HQE without spatial matching rapidly attains its maximum in performance and then decreases. This suggests that not too many visual words should be selected because the additional ones will introduce many outliers compared to inliers. In contrast, spatial matching filters out most of the outliers: Using more descriptors is better because the added ones are inliers in their majority. As a compromise between performance and complexity, we set α = 0.5 and 1.0 without and with spatial matching, respectively.

The vocabulary size k is critical in most methods based on pure BOVW. Figure 8 that it is not the case with HE and our techniques, which achieves excellent performance for all the sizes. This confirms observations in prior work [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF][START_REF] Sattler | Image retrieval for imagebased localization revisited[END_REF].

Weights, burstiness and HQE. Table 2 summarizes the respective contributions of the different elements of our search engine. First note the large gain already achieved by weighting the Hamming distances in HE, using MA and applying the burstiness procedure [10]. Note also the even larger improvement obtained by using our HQE technique, either with or without spatial matching.

Aggregation. Detailed performance on Oxford5k. Table 4 presents some detailed performances and statistics we have collected on Ox-ford5k for HE and HQE. Our selection strategy for reliable images, even without spatial matching, does not suffer from the variability of the number of true similar images in the database, with an exception on Cornmarket, where HQE without spatial matching selects a few false positives as reliable images. Also observe that HQE notably outperforms HQE-SP for the Bodleian queries. It is because HQE-SP is stricter and does not select enough reliable images. This suggests that a weaker spatial matching model [START_REF] Tolias | Speeded-up, relaxed spatial matching[END_REF] could offer a good compromise to select these images.

More features. All our experiments are conducted with features extracted using the default threshold for the Hessian-Affine detector [START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF] to allow for a direct comparison with the literature. Using a lower threshold for the "cornerness" value produces a larger set of features. It might be useful for image matching but might also add noisy features and therefore arbitrary matches. Table 5 investigates the impact of cornerness on both our methods and existing BOVW and HE baselines. With the default threshold, the software produces a total number of 12.53M features on Oxford5k. By using two smaller thresholds, we produced two other sets of features comprising 21.92M and 27.59M features, respectively. performance increases with the medium-sized set, but its performance drops with the larger one. In contrast, HE benefits from having more features. The performance of the two larger sets is comparable, which suggests that HE better handle noisy matches in a better way and can use more features. As a consequence, HQE performs in a similar way. The performance increases up to mAP=89.4 for HQE with geometry and MA, which is a large improvement over the state of the art.

Comparison with the state of the art

Oxford5k, Paris6k and Oxford105k. Table 6 compares the QE proposed method with previously published results on the same datasets. For a fair comparison, we have included the scores of QE methods that use the same local feature detector [START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF] as input and learned the vocabulary on an independent dataset. In this table, we also include the scores for our method when using 128-bit signatures for HE, which are better at the cost of higher memory usage and a slightly larger complexity.

Interestingly, even without spatial matching, our method outperforms all methods in Oxford105k and Paris6k dataset. HQE-SP outperforms them in all three datasets. All of the compared methods rely on spatial matching to verify similar images and expand the initial query. Moreover, the work of Mikulik et al. [START_REF] Mikulík | Learning a fine vocabulary[END_REF] requires a costly off-line phase and assigns the descriptors with a very large vocabulary of 16M, thereby impacting the overall efficiency.

To our knowledge, the performance of our method is the best reported to date on Oxford5k, Paris6k and Oxford105k, when learning the vocabulary on an independent dataset (89.1 was reported [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF] by learning it on the Oxford5k comprising the relevant images). In addition, all these techniques are likely to be complementary, as they consider orthogonal aspects to improve the performance. not expected to perform well, and accordingly we are not aware of any competitive result reported with a QE method on this dataset. For this set only, we reduce the short-list of images selected in the short-list to reflect the expected result set. Table 7 shows that HQE improves the performance significantly compared to the HE baseline and is therefore effective even with few relevant images. It performs similar to other state-of-theart techniques that perform well on this dataset. Note that these best techniques all require to cross-match (off-line) the whole image collection with itself, which may be infeasible on a large scale (quadratic complexity).

Complexity: timings and query size

First, note that the initial query includes a binary signature per local feature and several features can be assigned to the same visual word for a given image, especially with MA. In addition, the expanded query set, as defined before aggregation, is much larger as several images contribute to it with their reliable features, as previously shown in Table 3. Thanks to HQE, only one binary signature per visual word is kept. This favorably impacts the complexity of the enriched query in terms of the number of signatures. On average, the total number of features increases only by a small factor after aggregation, to be compared with queries which are one order of magnitude larger for other QE techniques.

Table 8 reports the average search times when querying Ox-ford105k. They have been measured on a single core desktop machine (3.2 Ghz). The spatial matching has been estimated by an external software and is included in the query time, unlike the SIFT extraction and quantization times. As expected, the search times are competitive for HQE without geometry, even when MA is used. As a reference, best time reported for QE with spatial matching [START_REF] Perdoch | Efficient representation of local geometry for large scale object retrieval[END_REF] is 509ms on Oxford105k on a 4 × 3.0Ghz machine. In addition, the cost of assignment to visual words is much smaller for our method with 65k visual words compared to the one of their method which needs up to 1M visual words to obtain optimal performance.

Conclusion

This paper makes several contributions related to visual query expansion. First, we introduce a query expansion method which is effective without using any geometry. While the general belief is that spatial verification is required to select the relevant images used to build the augmented query, exploiting the Hamming Embedding technique with a stringent selection rule and an aggregation strategy, we already achieve state-of-the-art performance. This method has a low complexity. We then show that combining our Hamming query expansion with geometry further improves the results and significantly outperform the state of the art.

In future work, we will investigate how to incorporate weak spatial matching models [START_REF] Tolias | Speeded-up, relaxed spatial matching[END_REF][START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] in our query expansion method, in order to find a compromise between a costly spatial verification or not using geometry at all.

Figure 2 :

 2 Figure 2: Matching features using BOVW (top), HE with ht = 24 (middle) and HE with ht = 16 (bottom).

Figure 3 :

 3 Figure 3: Examples of query images (left) and the corresponding top ranked lists by the baseline retrieval system. Images (not) selected as reliable are marked with (gray) green border.

Figure 4 :

 4 Figure 4: Sample reliable images and features assigned to reliable visual words, when geometry is not used. Left: Query image. Top: Features assigned to reliable visual words that appear in the query image. Bottom: Features in the set of augmented visual words. Note: we only show a subsample of the actual reliable visual words. Each color represents a distinct visual word.

Figure 5 :

 5 Figure 5: Features selected for the expanded set of a particular query image (left) without (middle) and with spatial matching (right). With spatial matching: features back-projected out of the bounding box are rejected (red), while the rest (blue and green) are kept. Those assigned to reliable visual words are shown in green. Without spatial matching: features assigned to reliable visual words are shown in cyan or yellow, with yellow being the ones assigned specifically to augmentation visual words and cyan the ones assigned to visual words that appear in the query. Rejected are shown in red. Best viewed in color.

Figure 6 :

 6 Figure 6: Impact of ht on the performance of HE and HQE.

Figure 7 :Figure 8 :

 78 Figure 7: Impact of α. Performance of HQE when varying the number of new visual words in the expanded query.

Table 1 :

 1

Evaluation with respect to mAP (performance) and IF (efficiency) of several post-processing procedures for SIFT: RootSIFT

[START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Jain | Hamming embedding similarity-based image classification[END_REF]

(denoted by √ )

Table 2 :

 2 Mean average precision for separate components comprising the proposed method. Initial method is the original Hamming Embedding without weights. W=weighting similarities. MA=multiple assignment.

	W burst MA HQE SP Oxford5k	Paris6k Oxford105k
		66.9	65.7	55.5
	× × × × × × × × × × × × × × × BOVW	70.4 71.7 75.4 83.0 86.8 53.3	68.4 70.2 72.0 80.6 81.5 54.8	59.6 62.9 68.0 79.0 82.6 44.2

  Table3reveals the double benefit of the local feature aggregation method proposed in Section 5 with respect to performance and query efficiency. Merging the binary signatures reduces the expanded query size and has a positive impact on complexity, as quantitatively measured in Table3: The aggregation step reduces by about one order of magnitude the size of the enriched query, which becomes comparable to that of the initial query.In addition, Table3also shows that this step significantly and consistently improves the performance. To demonstrate

	Dataset	Method	mAP SA MA	SA	|Q|	MA
		HE	71.7	75.4	1,362		4,088
	Oxford5k	HQE/b.a. 79.0	82.0	11,937		27,345
		HQE	80.7	83.0	1,810		5,030
		HE	70.2	72.0	1,460		4,382
	Paris6k	HQE/b.a. 76.6	77.3	35,982		66,665
		HQE	80.2	80.6	1,843		5,045
		HE	62.9	68.0	1,362		4,088
	Oxford105k	HQE/b.a. 73.5	76.5	12,176		28,699
		HQE	75.6	79.0	1,810		5,030

Table 3 :

 3 Performance and average query size |Q| for the baseline HE, HQE and the use of the same expanded query before aggregation (HQE/b.a.). Note that the aggregation procedure is a key step: not only it significantly reduces the complexity (number of features), but it also improves the performance.

	this, we have compared HQE (i.e., with aggregation) to a method
	which issues the expanded query defined by Equation 5, i.e.,
	prior to aggregation. As already discussed in Section 5, our
	interpretation is that aggregating binary signatures filters out
	noisy features and removes the redundant features at the same
	time. Merging the features derived from the reliable images can
	also give rise to multiple matches per descriptor, yet those are
	effectively handled by aggregation [32].

Table 4 :

 4 Oxford5k dataset: Summary of the number of ground truth images, the number of reliable images and the performance for HE, HQE and HQE with spatial matching. We report the average value of |L Q | per building, i.e., the number of automatically detected reliable images in the short-list of 100 top-ranked ones.

	# features		12.53M 21.92M 27.59M
	method	MA		mAP
	BOVW		54.9	58.7	55.2
	HE		74.2	78.6	78.3
	HQE		81.0	84.8	84.4
	HQE-SP		85.3	88.1	88.5
	HQE-SP	×	88.0	89.4	89.3

Table 5 :

 5 More features: Performance comparison on Oxford5k using lower detector threshold values, i.e., larger sets of local features. Binary signatures of 128 bits are used.

Table 5

 5

	shows that BOVW's

Table 6 :

 6 Performance comparison with state-of-the-art methods on Oxford5k, Paris6k and Oxford105k. The standard deviation is obtained from 5 measurements.

Table 7 :

 7 UKB [6] is a dataset with few corresponding images per query (4, including the query image). QE techniques are therefore Jégou [10] Jégou[START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF] Qin[START_REF] Qin | Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[END_REF] HE-MA HQE-MA UKB: comparison with state-of-the-art methods.

	3.64	3.68	3.67	3.59	3.67
	Method	HE	HQE		HQE-SP
	SA	30 ms	79 ms		731 ms
	MA	76 ms	204 ms		955 ms

Table 8 :

 8 Average query times for the HE baseline and our technique with and without spatial matching, measured on Oxford105k when using a single processor core. These timings do not include the description part (extracting and quantizing the SIFT descriptors), which does not depend on database size.

Acknowledgments

This work was done in the context of the Project Fire-ID, supported by the Agence Nationale de la Recherche (ANR-12-CORD-0016). We also thank the reviewers for their valuable comments and effort to help us improving the manuscript.


Benjamin Roustan

Marion Dohen

Co-Production of Contrastive Prosodic Focus and Manual Gestures: Temporal Coordination and Effects on the Acoustic and Articulatory Correlates of Focus

Speech, and prosody in particular, is tightly linked to manual gestures. This study investigates the coordination of prosodic contrastive focus and different manual gestures (pointing, beat and control gestures). We used motion capture on ten speakers to explore this issue. The results show that prosodic focus "attracts" the manual gesture whichever its type, the temporal alignment being stricter for pointing and mainly realized between the apex of the pointing gesture and articulatory vocalic targets. Moreover, it appears that the production of a gesture, whichever its type, does not affect the acoustic and articulatory correlates of prosodic focus.

Introduction

The production of speech and manual gestures are tightly bound (see e.g. [START_REF] Mcneill | Hand and Mind: What Gestures Reveal about Thought[END_REF][START_REF] Kendon | Gesture[END_REF]). In particular, [START_REF] Bolinger | Intonation and gesture[END_REF][START_REF] Nobe | Representational gestures, cognitive rhythms, and acoustic aspects of speech: A network/threshold model of gesture production[END_REF][START_REF] Mcclave | Pitch and manual gestures[END_REF][START_REF] Boyer | Rôle de la voix et des gestes dans la focalisation[END_REF][START_REF] Loehr | Gesture and intonation[END_REF][START_REF] Duncan | Gesture and speech prosody in relation to structural and affective dimensions of natural discourse[END_REF] underline the link between manual gestures and prosody.

Deixis is the ability to draw attention. In the concrete space, it can be achieved through index finger pointing. In speech, it can be achieved through the use of focus. In particular, prosodic contrastive focus is used to emphasize a word or group of words as opposed to another. In this sense, prosodic focus and pointing are strongly linked (see [START_REF] Loevenbruck | Pointing is special[END_REF] for discussion). The literature provides several clues on how the different unimodal realizations of deixis are coordinated in time. de Ruiter [START_REF] De Ruiter | Gesture and speech production[END_REF] found that the position of lexical stress within a single word did not affect the temporal realization of the concomitant pointing gesture. However, he also found that the onset of the pointing gesture was influenced by the location of contrastive stress within a noun phrase (adjective + noun). Rochet-Capellan et al. [START_REF] Rochet-Capellan | The speech focus position effect on jaw-finger coordination in a pointing task[END_REF] used a pointingnaming task (2-syllable non-word target with lexical stress on one or the other syllable) and found that the stressed syllable is always included in the part of the gesture that shows (from the apex to the return of the index finger toward a rest position). There thus seems to be a link between the temporal realization of deixis in speech (expressed through prosody) and manual pointing but it remains unclear. Moreover, these studies analyzed simple speech productions (isolated words, non-words or phrases). [START_REF] Mcneill | Hand and Mind: What Gestures Reveal about Thought[END_REF][START_REF] Mcclave | Pitch and manual gestures[END_REF] also put forward the potential link between prosody and beat gestures (or batons; small up and down flicks of the hand).

Another crucial question is the influence of the production of manual gestures on speech. Krahmer and Swerts [START_REF] Krahmer | The effects of visual beats on prosodic prominence: Acoustic analyses, auditory perception and visual perception[END_REF] found that the production of a "visual beat" (manual beat gesture, head nod or rapid eyebrow movement) has a significant effect on duration and F 2 formant in the same direction as the effect of the production of a pitch accent. This suggests that the production of a manual or facial gesture has an effect on the acoustic and articulatory correlates of the simultaneously produced speech.

The aim of this study is to analyze the coordination between contrastive prosodic focus in French and several types of manual gestures in entire utterances using motion capture. The questions addressed are the following: 1. how are prosodic focus and manual gestures coordinated in time? 2. is this potential coordination influenced by the type of gesture and its functional link to speech? 3. does the production of a manual gesture affect the acoustic and articulatory correlates of prosodic focus?

Methodology

Experimental design

Corpus

The corpus used consisted of four subject (S) -verb (V)object (O) sentences in French (ex: Mumu tient le bébé. 'Mumu holds the baby.') with the following syllable structure: S=2 syl (first name); V=1syl (action verb, present tense); O=1+2syl (article + common noun). All target word syllables (S and O) were CV syllables and the first consonant of the word was a bilabial consonant.

Experimental design

Two narrow focus conditions were elicited: focus on the subject (SF) and on the object (OF). Four gesture conditions were explored: no gesture (speech alone), indexfinger pointing (deictic communicative), beat gesture (nondeictic communicative) and control gesture (button press; non-deictic non-communicative).

A correction task was used to naturally elicit the pro-duction of prosodic contrastive focus. Participants heard an audio prompt in which two speakers were talking and were instructed to correct the sentence uttered by the second speaker as in the following example (capital letters signal focus):

Prompt S1 Mumu tient le bébé. S2
S1 a dit : Baba tient le bébé? 'S1 said: Baba holds the baby?' Answer Participant MUMU tient le bébé.

Two images were then displayed (for the latter example: images of Baba and Mumu). The participants were instructed to gesture at the same time as they performed the correction task. In the pointing condition, they had to point at the image corresponding to the correction performed. In the beat condition they were instructed to produce a rapid up-down flick of the hand (gesture often used in spontaneous speech when focusing). In the control condition, participants had to press a button on the table. No further indication was given on when to gesture.

The experiment was divided into 4 blocks (one for each gesture condition). Participants briefly trained before each block The order of the blocks was varied across participants. Within each block, the order of the sentences and focus conditions was random and varied across participants. Each block consisted of 16 trials (4 sentences, 2 focus conditions, 2 repetitions).

Experimental setup

The participants sat in a chair facing a screen on which visual targets appeared. A rest position was marked on a table on their right-hand side. They were instructed to place their index finger on this mark and always depart from this position to gesture and come back to it after the gesture. The movements of their lips and right hand were tracked using a 3D motion capture device (NDI Optotrak). Four markers were positioned on the lips (2 on each lip corner, 1 in the middle of the upper and 1 in the middle of the lower lip) and three on their right hands (index finger: 1 on the tip and 1 on the first phalanx; back of the hand: 1). The acoustic speech productions were recorded using a microphone (synchronized with Optotrak recording).

Participants

Ten adults (8 women, 2 men; age: mean: 30.2, s.d.: 8.94) participated in the experiment. All were native speakers of French and right-handed.

Measurements

All the stimuli were acoustically validated by two independent judges The acoustic production errors were excluded from analysis. Utterances in which participants had omitted to produce or had misproduced the manual gesture were also excluded from analysis.

The acoustic boundaries of syllables were labeled using Praat [START_REF] Boersma | Praat: doing phonetics by computer[END_REF]. The fundamental frequency (F 0 ) and intensity (Int) peaks of the focused constituent (S or O) were detected. The duration of the focused constituent (Dur) was computed. Lip opening (distance between upper and lower lip markers) and protrusion (forward movement of upper lip marker) were extracted from the motion data. The two articulatory vocalic targets (VT 1 and VT 2 ) corresponding to the two vowels of the focused constituent were also detected (peaks of amplitude of lip opening or lip protrusion depending on the vowel). For the finger movement data, the apex (P A ) and beginning of the return stroke (P R ) of the gesture were labeled. For the pointing gesture, the apex corresponds to the complete extension of the index finger pointed at the target. For the control gesture, it corresponds to the point at which the index finger reaches the button. For the beat gesture, it was identified as the end of the downbeat. The timing corresponding to the realizations of the above mentioned events were normalized against the acoustic duration of the sentence (beginning of the sentence: 0; end: 1). This was done in order to compensate for effects of semantic content or response time.

All dependent variables were tested using two-way ANOVAs with two within subject factors: focus condition (2 levels: SF, OF) and gesture condition (for gesture variables i.e. P A and P R : 3 levels: pointing, beat and control gestures; for acoustic and articulatory variables i.e. Dur, F 0 , Int, VT 1 and VT 2 : 4 levels: speech only + 3 gesture types).

Results

3.1. Timing: Speech/gesture temporal coordination

General results

Table 1 provides the results of the statistical analyses on the normalized times of occurence of the different events measured (notation t event ). Manual gesture time variables -We found significant main effects of focus condition on both apex (t PA ) and return (t PR ) times. The gesture tends to occur later within the utterance for OF: focus "attracts" the gesture. We found a significant main effect of gesture type on apex but not on return time. This suggests that the different gestures are not produced in the same manner.

Speech time variables -We found significant main effects of focus condition on all variables (t F0 , t Int , t VT1 and t VT2 ). This corresponds to the fact that the acoustic and articulatory correlates were measured on S for SF and O for OF. We found no significant effects of gesture condition. The production of a gesture (whichever its type) does not affect the internal temporal organization of the utterance (no difference with speech only condition).

Temporal alignments

Two points of interest are said to be aligned in time if the difference of their times of occurence is close to zero.

In order to examine the potential alignment of manual gestures and prosodic focus we computed the differences between the times of occurence of gesture variables (t PA and t PR ) and those of acoustic (t F0 and t Int ) and articulatory (t VT1 and t VT2 ) correlates for each utterance. A mean was computed over all utterances for each participant. Figure 1 shows the means and standard deviations of the time differences over all participants (if a box is close to zero, the variables considered are close in time). Table 2 provides the results of the ANOVAs on all time differences. We found significant main effects of focus condition on all time differences. Whichever the gesture type, temporal coordination between speech and manual gestures within the focused constituent differs from SF to OF. We also found significant main effects of gesture type on all time differences for P A but not for P R . Different manual gestures are thus coordinated with prosodic focus in different ways: P R is constant for all gestures relative to acoustic and articulatory correlates (consistent with the results presented in section 3.1.1) but not P A . Welch t-tests were used to compare the normalized time variables corresponding to the different gestures and acoustic and articulatory variables.

Apex -VT1 -0.5 0.0 0.5 1.0 • • • • • • • • • • • • • • • • • • SF OF Apex -VT2 -0.5 0.0 0.5 • • • • • • • • • SF OF Return -VT1 0.0 0.5 1.0 • • • • • • • • • • • SF OF Return -VT2 -
Pointing gesture -For SF, t PA is not significantly different from t F0 (t(9) = 1, p = .3) and t Int (t(9) = 1.5, p = .2) but this is not the case for OF (t F0 : t(9) = -3.11, p = .008; t Int : t(9) = -2.7, p = .02). For SF, t PA is not significantly different from t VT2 (t(9) = -0.8, p = .4) and for OF, t PA is not significantly different from t VT1 (t(9) = -1.5, p = .2). It thus appears that, for pointing, there is a clear tendency towards alignment of the apex with one of the articulatory targets of the focused constituent.

Beat gesture -For SF, there is no tendency towards any alignment between P A and any of the acoustic and articulatory correlates of prosodic focus. For OF, P A appears to be aligned with the F 0 and intensity peaks (F 0 : t(9) = 1.4, p = .2; Int: t(9) = 2, p = .08) and VT 2 (t(9) = .7, p = .5).

Control gesture -For SF, P A is aligned with F 0 and intensity peaks (F 0 : t(9) = -1.2, p = .3; Int: t(9) = -0.8, p = .4). However, this is not the case for OF. For SF, P A is aligned with VT 1 (t(9) = .8, p = .4). For OF, P R is aligned with VT 2 (t(9) = 1.2, p = .3).

Very interestingly, Figure 1 also shows that alignments are more precise and consistent across speakers for the pointing gesture (see standard deviations). This is especially true for the apex.

Amplitude: Effect of gesture production on acoustic and articulatory correlates

We analyzed the mean amplitudes of acoustic (duration of the focused element (Dur) and Int and F 0 peaks) and articulatory (VT 1 and VT 2 ) correlates. Table 3 provides the results of the ANOVAs on these variables.

We found significant main effects of focus condition on all five variables. Post-hoc analyses showed that the amplitudes of all acoustic and articulatory correlates of prosodic focus are unsurprisingly significantly smaller for OF than for SF (see [START_REF] Dohen | Pre-focal rephrasing, focal enhancement and post-focal deaccentuation in french[END_REF]). More interestingly, we found no significant main effect of gesture condition on any of the variables. It therefore appears that the production of a gesture does not affect the acoustic and articulatory correlates of prosodic focus (no difference between speech + gesture and speech only conditions).

Conclusions and discussion

The productions of ten speakers were recorded (motion capture on hand and mouth and acoustic recording) under two focus conditions (subject vs. object focus) and four gesture conditions (speech only vs. pointing vs. beat vs. control gestures). The aim was to address several questions: determine whether the productions of prosodic focus and manual gestures are coordinated and how this coordination can differ depending on the type of gesture produced; examine the effect of the production of a manual gesture on acoustic and articulatory correlates of speech.

The results show that focus and manual gestures are coordinated in the sense that focus "attracts" the manual gesture. Gestures' apices occur within or close to the focused element. Concerning pointing, in line with [START_REF] Rochet-Capellan | The speech focus position effect on jaw-finger coordination in a pointing task[END_REF], we found that the part of speech that shows (prosodic focus) and the part of the gesture that shows always overlap. Temporal coordination between focus and manual gestures is the most consistent for pointing. The apex of the pointing gesture is aligned with articulatory targets rather than acoustic correlates. It appears that temporal coordination between prosodic focus and manual gestures depends on the functional link between gesture and speech. Coordination is the most consistent for pointing which realizes the same function as prosodic focus i.e. deixis. Coordination is the least precise for the control gesture which is a non-communicative gesture even if their appears to be a coordination (we expected there would be none at all). This may be due to the fact that button pressing in this case was close to pointing (participants had to extend their index finger to press the button).

Concerning question 3, the results show that the production of a manual gesture (whichever its type) does not affect the acoustic and articulatory correlates of prosodic focus. There is indeed no significant difference in the amplitudes of these correlates from speech alone to combined speech and gesture conditions. These results are not in line with the findings of [START_REF] Krahmer | The effects of visual beats on prosodic prominence: Acoustic analyses, auditory perception and visual perception[END_REF] who found that producing a beat gesture (whether manual or facial) is likely to increase muscular activity related to articulation. We believe that the effects found by these authors are artefacts of their experimental paradigm. In some conditions, participants were asked to produce a beat gesture on a different word than the one bearing the pitch accent. This type of incongruent productions are quite unnatural and it is likely that the speakers tended to produce pitch accents on the word they were asked to produce a beat gesture on.

This study enabled a more precise characterization of the coordination between speech prosody and manual gestures. Gesture apices mainly seem to be aligned with articulatory targets especially for pointing which is functionally close to prosodic focus. During the recordings, it however appeared that it was quite difficult for speakers to produce manual beat gestures when instructed to do so. It would therefore be crucial to conduct motion capture recordings in natural conversation to confirm these findings.

Figure 1 :

 1 Figure1: Differences in timing between gesture apices (t PA ) and returns (t P R ) and acoustic (t F0 , t PInt ) and articulatory correlates (t V T1 , t V T2 ) for all focus conditions (SF, OF) and all gesture types (pointing, beat, control).

Table 1 .

 1 Two-way ANOVAs on all time variables.

		focus condition	gesture condition
	t P A	F (1, 9) = 114.4 , p < .001	F (2, 18) = 13.9, p < .01
	t P R	F (1, 9) = 99.5 , p < .001	F (2, 18) = 3.4 , p = .09
	t F 0	F (1, 9) = 1571.6, p < .001	F (3, 27) = 3.1 , p = .1
	t Int	F (1, 9) = 2478.6, p < .001	F (3, 27) = 7.6 , p = .01
	t VT 1	F (1, 9) = 3746.1, p < .001	F (3, 27) = .4 , p = .7
	t VT 2	F (1, 9) = 2655.7, p < .001	F (3, 27) = 1.2 , p = .4

Table 2 .

 2 Two-way ANOVAs on all time differences.

		focus condition	gesture condition
	t P A -t F 0	F (1, 9) = 47.8, p < .001	F (2, 18) = 14.1, p < .01
	t P A -t Int	F (1, 9) = 55.3, p < .001	F (2, 18) = 14.4, p < .01
	t P A -t CV 1	F (1, 9) = 57.5, p < .001	F (2, 18) = 14 , p < .01
	t P A -t CV 2	F (1, 9) = 55.6, p < .001	F (2, 18) = 14 , p < .01
	t P R -t F 0	F (1, 9) = 32.8, p < .001	F (2, 18) = 3.1 , p = .1
	t P R -t Int	F (1, 9) = 32.9, p < .001	F (2, 18) = 4.5 , p = .05
	t P R -t CV 1	F (1, 9) = 36.3, p < .001	F (2, 18) = 3.4 , p = .08
	t P R -t CV 2	F (1, 9) = 36.3, p < .001	F (2, 18) = 3.1 , p = .1

Table 3 .

 3 Two-way ANOVAs on all amplitude variables.

		focus condition	gesture condition
	Dur	F (1, 9) = 13.5, p = .05	F (2, 18) = .4 , p = .7
	F 0	F (1, 9) = 17 , p < .01	F (2, 18) = 2.7, p = .1
	Int	F (1, 9) = 76.2, p < .001	F (2, 18) = .5 , p = .2
	VT 1	F (1, 9) = 13.5, p < .01	F (2, 18) = 2.3, p = .2
	VT 2	F (1, 9) = 59.6, p < .001	F (2, 18) = 3.4, p = .08