Sébastien Poullot
email: spoullot@nii.ac.jp

Shunsuke Tsukatani
email: tsukatani@nii.ac.jp

Anh Phuong Nguyen

Hervé Jégou
email: herve.jegou@inria.fr

Ichi Satoh
email: satoh@nii.ac.jp

Temporal Matching Kernel with Explicit Feature Maps

This paper proposes a framework for content-based video retrieval that addresses various tasks as particular event retrieval, copy detection or video synchronization. Given a video query, the method is able to efficiently retrieve, from a large collection, similar video events or near-duplicates with temporarily consistent excerpts. As a byproduct of the representation, it provides a precise temporal alignment of the query and the detected video excerpts.

Our method converts a series of frame descriptors into a single visual-temporal descriptor, called a temporal invariant match kernel. This representation takes into account the relative positions of the visual frames: the frame descriptors are jointly encoded with their timestamps. When matching two videos, the method produces a score function for all possible relative timestamps, which is maximized to obtain both the similarity score and the relative time offset.

Then, we propose two complementary contributions to further improve the detection and localization performance. The first is a novel query expansion method that takes advantage of the joint descriptor/timestamp representation to automatically align the first result set and produce an enriched temporal query. In contrast to other query expansion methods proposed for videos, it preserves the localization capability. Second, we improve the localization trade-off between quality and representation size by using several complementary temporal match kernels.

We evaluate our approach on benchmarks for particular event retrieval, copy detection and video synchronization. Our experiments show that our approach achieve excellent detection and localization results.

INTRODUCTION

T his paper addresses the problem of content-based search in large collections of video clips. Our goal is twofold:

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions@acm.org. MM'15, October 26-30, 2015, Brisbane, Australia. (i) identify the content of interest (ii) localize the content of interest within the video clip. We essentially focus on tasks such as particular event retrieval [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF], copy detection [START_REF] Law-To | Video copy detection: a comparative study[END_REF][START_REF] Yeh | Video copy detection by fast sequence matching[END_REF][START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF] and video synchronization, for which the temporal consistency is important. Because we want to handle large datasets, the complexity is regarded as a key factor, both in terms of CPU and memory. This disqualifies the numerous approaches that store local image descriptors or spatialtemporal points [START_REF] Law-To | Video copy detection: a comparative study[END_REF], which are too costly for big datasets.

In contrast, following some recent works for particular event retrieval and video copy detection [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF][START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF], the input of our approach is a set of compact frame vectors produced from local descriptors. A visual frame descriptor is obtained by first encoding the local descriptors of the image with the Fisher vector [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] or another alternative coding approach [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF][START_REF] Arandjelovic | All about VLAD[END_REF][START_REF] Jégou | Triangulation embedding and democratic kernels for image search[END_REF], such as those recently proposed for image classification or search tasks. These vectors are then projected to a few hundreds or thousands components [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF][START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF] with dimensionality reduction.

With such frame vectors as the initial video representation, the most common options are the following ones:

1. adopt a "bag of frames" shift-invariant representation [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF],

whose major advantage is to be computationally cheap.

The main drawback is that this class of method looses the temporal consistency of the frames, therefore the method is not able to provide the temporal alignment 2. compare videos by matching all the frames of the query video with all the frames of each database video. The potential matching frames are then fed to a Hough temporal matching ensuring that the matches are temporally consistent [START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF]. However, the complexity of this strategy is quadratic in the length of video clips and is therefore very costly.

To alleviate the quadratic term, the circulant temporal encoding (CTE) of Revaud et al. [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] exploits a simple assumption (time translation) on the temporal model to evaluate efficiently, i.e., in the Fourier domain, the cross-correlation of two series of vectors representing two videos. This strategy is inspired by recent works by Henriques et al. for efficient detection [START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF] and tracking [START_REF] Henriques | High-speed tracking with kernelized correlation filters[END_REF], who obtained top performances in the VOT2014 object tracking challenge [START_REF]The visual object tracking VOT2014 challenge results[END_REF]. This approach has the capability of finding the near-duplicates and provides the temporal offset between the videos. Indeed, CTE considers the temporal shift-invariant matching as matching sequences with all possible shifts, then regards matching sequences with all possible shifts as a convolution. However, this strategy has several shortcomings, the main one being that this method is tailored to a measure of crosscorrelation, which is a strong assumption on the time model best fitted to compare videos.

We mention that video recognition based with CTE is outperformed by the recent stable hyper-pooling approach [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF]. However hyper-pooling is more costly and, as mentioned previously, does not provide any localization capability, such as the estimation of the temporal offset.

In this paper, we propose a class of temporal match kernels which are able to match and align videos efficiently. It can be seen as a generalization of CTE, yet compared to this representation it offers two advantages: (i) the design of the kernel offers degrees of freedom likely to better suit to the particular recognition task ; (ii) the representation has a fixed size and is independent from the video length.

The idea is to encode a set of vectors (the frame descriptors associated with a given video) into a single vector so that the comparison of two videos is performed with dot products, in the spirit of the kernel descriptors of Bo [START_REF] Bo | Kernel descriptors for visual recognition[END_REF], but here specifically adapted to the case of time vector sequences. The design of this encoding strategy, amenable to incorporate the shift-invariance and the capability of finding the temporal offset, relies on explicit feature maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF]. Compared to kernel descriptors, the main advantage is that we do not have a single score. Instead the comparison outputs a score function for all time-shift hypotheses, in the form of a trigonometric polynomial.

Our paper makes the following contributions:

• We adapt the kernel descriptor framework of Bo [START_REF] Bo | Kernel descriptors for visual recognition[END_REF] to sequences of frames. More specifically, we propose a class of shift-invariant temporal match kernels by gathering the formalism of explicit feature maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] and circulant encoding [START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF][START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. This strategy is a generalization of CTE, which gives more room to adapt the properties of the matching kernel and limits the approximation artifacts inherent to CTE.

• We propose a query expansion (QE) technique that automatically aligns the videos deemed relevant for the query. The new query is constructed in the Fourier domain and does not require the original frame descriptors. Most importantly and as opposed to possible concurrent QE techniques proposed with compact representations, our method preserves the localization capability of our temporal match kernel.

• We propose a strategy to combine several match kernels into a single one to further improve the trade-off between memory and localization accuracy.

The paper is organized as follows. Section 2 introduces the notation and some preliminary works from which we derive our approach. Section 3 introduces the temporal matching kernels, which is extended to multiple periods to improve the localization in Section 5. Section 4 introduces an original query expansion method for improving the accuracy of the method. The experiments described in Section 6 demonstrate the interest of our approach on public benchmarks for copy detection and particular event retrieval.

PRELIMINARIES: FEATURE MAPS

This section briefly introduces a key ingredient of our method, namely the explicit feature maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF]. It was originally introduced to produce an approximation of a shiftinvariant kernel with an explicit mapping, that is, such that the inner product in the embedded space approximates the kernel in the original space. In our case, we employ it to define a class of temporal kernel between set of visual frames.

Embedding of the kernel function

The idea is to approximate a non-linear kernel k(•, •) : R × R → R by using a mapping function ϕ : R → R 2m+1 as

k(u, v) ≈ ϕ(u)|ϕ(v) . (1)
This is done for shift-invariant kernels, i.e., such that the kernel can be expressed as k(u, v) = g(uv), by first considering the Fourier approximation of g as

g(z) = m i=0 ai cos 2π T iz , (2)
which approximates g assuming that it is a T -periodic function. Now, let us consider that z = uv. By employing the elementary trigonometric property

cos(u -v) = cos u cos v + sin u sin v (3) = cos u sin u cos v sin v , (4)
and further assuming that the coefficients of the Fourier series are all positive, i.e., ∀i ai > 0, the approximation (2) is written as

g(u -v) ≈          √ a0 √ a1 cos 2π T u √ a1 sin 2π T u . . . √ am cos 2π T mu √ am sin 2π T mu          ⊤ ϕ(u) ⊤          √ a0 √ a1 cos 2π T v √ a1 sin 2π T v . . . √ am cos 2π T mv √ am sin 2π T mv          ϕ(v) , (5)
where the interesting property is that ϕ(u) is independent of v. Therefore, it is possible to construct the mapping ϕ to approximate the shift-invariant kernel as proposed in [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF]. The approximation quality depends on the quality of the approximation of k by Fourier series [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF].

Application to frame time stamps

Considering two videos Vx and Vy that are temporally perfectly aligned, the distance between their time stamps is txty = 0. In this ideal case, the distance is coded by a Dirac delta function:

if tx = ty then D(tx, ty) = 1 else D(tx, ty) = 0 (6)
The Fourier transform of a Dirac is a constant function, meaning that all ai are equal in [START_REF] Arandjelovic | All about VLAD[END_REF]. Using the corresponding embedding function is what implicitly done in the circulant encoding technique of Revaud et al. [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. The Dirac's approximation is the best Fourier expansion, w.r.t. square loss, when the function is evaluated at certain positions (2πiz/T, i = 0 . . . m -1). However, this choice has two drawbacks in our application scenario:

-0.2 0 0.2 0.4 0.6 0.8 1 -π -π/2 0 -π/2 -π k t (∆t 2π/T) ∆t 2π/T k t ≈ Von Mises k t ≈ dirac
Figure 1: Approximate Dirac and Von Mises: response as a function of the temporal difference when approximating these kernels with finite Fourier series (m = 16 frequencies here). As one can observe, the Dirac approximation [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] suffers from oscillations.

1. To get a compact representation, we approximate the temporal kernel with a limited number of frequencies, that is, much smaller that the number of frames to be encoded. The Fourier series we consider are truncated and therefore the approximation obtained when keeping the first components is noisy, suffering strong oscillations around 0, as shown by Figure 1.

2. We want to offer tolerance in time for matching frame by designing a specific shape of the match kernel.

For these reasons, we consider other choices, like the modified Von Mises distribution, a.k.a. the periodic Gaussian, and considered in recent papers [START_REF] Bo | Kernel descriptors for visual recognition[END_REF][START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF]. Its Fourier expansion is determined in a close-form manner by the Fourier coefficients

a0 = B0(β) -e -β 2 sinh(β) ai = Bi(β) sinh(β) for i ≥ 1 (7)
where Bn(β) is the modified Bessel function of the first kind of order n. Figure 1 clearly shows that the approximate Von Mises temporal kernel gives a flat response out of the target bandwidth, meaning that there are significantly less interferences in the match kernel than with the circulant temporal encoding technique [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF].

TEMPORAL MATCH KERNELS

This section introduces the class of match kernels proposed in this paper. We first detail the class of kernels that we want to approximate and then show how to approximate them with feature maps encoding. Finally, we show that we can decode them efficiently for any temporal shift. For notation, we denote in bold vectors, tuples and sequences.

Temporal match kernels with feature maps

Modulating descriptors with timestamps. We consider that each image/frame fx is associated with a tuple (x, tx), where x ∈ R d is a d-dimensional vector and tx is a scalar timestamp. We define a kernel between such tuples that is of the form:

k (fx, fy) = k f (x, y) kt(tx, ty) (8) = x|y kt(tx, ty) (9)
≈ x|y ϕ(tx) ⊤ ϕ(ty).

where we assume that the frame descriptors are normalized and compared with cosine similarity, i.e., k f (x, y) = x|y . This kernel is further linearized as

k (fx, fy) ≈ x ⊗ ϕ(tx)|y ⊗ ϕ(ty) , (11)
where ⊗ denotes the Kronecker product. In this case, we stress that the tuple (x, tx) is represented by a single vector x ⊗ ϕ(tx), that serves as the frame descriptor, and which is compared with the inner product. Another way to interpret this joint encoding is to view x as being modulated by the timestamp tx in a continuous manner, so that only frames with the same timestamp can receive a significant contribution: |k(x, y)| is bounded by |kt(tx, ty)|.

Temporal match kernels with feature maps. The expansion in ( 11) is inspired by the kernel descriptors of Bo et al. [START_REF] Bo | Kernel descriptors for visual recognition[END_REF], however it is here based on explicit feature maps instead [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] of efficient match kernels [START_REF] Bo | Efficient match kernel between sets of features for visual recognition[END_REF]. Following this work, we now consider the context of match kernels. In our case, the goal is to compare two sequences of descriptors x = (x0, . . . , xt, . . . ) and y = (y 0 , . . . , y t ′ , . . . ), where the indices implicitly encode the timestamps 1 . We aim at approximating a kernel on sequences of the form

K0(x, y) = α(x)α(y) t k f (xt, y t ) (12) ∝ ∞ t=0 x ⊤ t y t , (13)
where the proportionality factors α(•) are such that K0(x, x)= K0(y, y)= 1. By convention, we also assume that xτ = 0 (τ > t) if the sequence is shorter that t. This kernel is equivalent to

K0(x, y) ∝ ∞ t=0 ∞ t ′ =0 x ⊤ t y t ′ δ(t, t ′ ), (14)
where δ(t, t ′ ) = 1 if t = t ′ , otherwise δ(t, t ′ ) = 0. Replacing δ(•, •) by any temporal kernel kt(•, •) shows that the circulant temporal embedding [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] is a particular case of our more general formulation, corresponding to the case kt = δ. Using [START_REF] Henriques | High-speed tracking with kernelized correlation filters[END_REF], the kernel is then factorized as

K0(x, y) ∝ ∞ t=0 xt ⊗ ϕ(t) ψ 0 (x) ⊤ ∞ t ′ =0 y t ′ ⊗ ϕ(t ′ ) ψ 0 (y) , (15)
where ψ 0 (x) is the vector representation of the sequence x.

The video representation is a (1+2m)×d dimensions matrix, where m is the number of coefficient kept from the Fourier series (a1 to am) and d is the initial dimensionality of the frame vectors. It can also be written as

ψ 0 (x) = [V0 ⊤ , V1,c ⊤ , V1,s ⊤ , ..., Vm,c ⊤ , Vm,s ⊤ ] ⊤ (16)
where:

V0 = a0 ∞ t=0 xt (17) Vi,c = ai ∞ t=0 xt cos 2π T t Vi,s = ai ∞ t=0 xt sin 2π T t
Regularization. The temporal linearity in videos induces a strong self-similarity, and results in interferences when matching two similar videos. Such noise degrades the alignment between two videos. In order to limit this undesirable effect we regularize the kernel descriptors to limit the interferences due to self-similarity in videos. Derived from Winener-Khinchin Theorem, the regularization is done by updating ψ 0 (x) as follows:

ψ 0 (x) := ψ 0 (x) 1 m N i=1 (V 2 i,c + V 2 i,s ) (18)
This regularization is close to the one introduced in [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF]. The main difference is that our regularization is symmetric, applied to both query and database descriptors. In what follows, we use the regularized version for better performance.

Matching with different timestamps

The temporal similarity in [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF] assumes that the sequences are temporally aligned, which prevents from retrieving excerpts that are not synchronous with the query video. We now consider the evaluation of a kernel parametrized by a latent variable ∆ controlling the relative offset of two sequences x and y. The match kernel definition becomes

K∆(x, y) ∝ ∞ t=0 x ⊤ t y t+∆ , (19)
which, similar to [START_REF] Law-To | Video copy detection: a comparative study[END_REF], is approximated by

K∆(x, y) ∝ ∞ t=0 xt ⊗ ϕ(t) ⊤ ∞ t ′ =0 y t ′ ⊗ ϕ(t ′ + ∆) ψ ∆ (y) , (20)
where ψ ∆ (y) indicates that the timestamps of the sequence y are incremented by the constant ∆. Note that the vector ψ ∆ (y) corresponds to a translation in the Fourier domain and is therefore obtained from ψ 0 (y) by incrementing the phase by the quantity ∆. However, we don't need ψ ∆ (y) to compute the similarity of the two sequences for any relative time-shift ∆. Instead, similar to Tolias et al. [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF], we exploit the fact that K∆(x, y) is a trigonometric polynomial in ∆, denoted by Kx,y(∆) for clarity, when x and y are fixed. The comparison of two videos proceeds in two steps: (i ) computation of the coefficients of the polynomial, (ii) evaluation of the score at different frame-shifts. Using equations ( 16) and [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] this trigonometric polynomial of video descriptors V(x) and V(y) is written as

Kx,y(θ) = V0| V0 + N n=1 cos(n∆)( Vn,c| Vn,c + Vn,s| Vn,s ) + N n=1 sin(n∆)(-Vn,c| Vn,s + Vn,s| Vn,c ) (21)
The coefficients of this polynomial are obtained at the cost of (1 + 2m) × d elementary operations, i.e., about twice the cost of an inner product in R d .

Evaluating the values taken by this score function for all valid frame-shifts ∆ has a negligible cost. Figure 2 illustrates the trigonometric polynomials of scores obtained for matching and non-matching sequences. The max peak gives the score Sxy = max∆ Kx,y(∆) and the time offset δxy =arg max∆Kx,y(∆) between the sequences x and y. For each query, the candidates in the database are ordered by decreasing scores.

TEMPORAL QUERY EXPANSION

Query expansion (QE), a technique initially introduced in text, is an effective mechanism that improves the recall when matching documents can be reliably identified to build an augmented query. In particular object retrieval, it is commonly combined with spatial re-ranking [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Chum | Total recall II: Query expansion revisited[END_REF]. The most popular is average query expansion (AQE), which constructs the augmented query by averaging the vectors associated with the images deemed positive after spatial verification is applied on an initial short-list. Other variants were recently proposed, such as discriminative query expansion [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF].

Triplet time consistency

In our case, we consider short vector representations of frames that are incompatible with spatial verification based on local descriptors [START_REF] Chum | Total recall II: Query expansion revisited[END_REF][START_REF] Tolias | Visual query expansion with or without geometry: refining local descriptors by feature aggregation[END_REF]. Therefore we propose a strategy to first check whether the videos returned in the short-list are temporally consistent or not.

Consider a query q and a database video x, our temporal match kernel returns a temporal offset δqx. Within the short-list N1 of length |N1| returned by the ranking strategy, we check the temporal consistency of each result by considering triplets of offsets. The offsets δqx and δqy between the query q and two videos x and y are byproducts of the initial ranking stage. Additionally, we compute the extra offsets δxy between all pairs (x, y) of videos in the shortlist of candidates. These offsets are requested to satisfy the constraint

|δqx + δxy + δyq| ≤ ε, ( 22
)
where ε is a temporal tolerance related to T . It should be small enough to filter inconsistent matches (ε ≫ T ) but large enough to tolerate small errors on the estimated offsets. The method is not sensitive to the exact tolerance value. We set ε = 100 frames. Having computed the consistency of each couple of candidates ((|N1| -1)/2 in total), we produce a per-video consistency measure to partition the short-list as

N1 = N C 1 ∪ N U 1 , (23)
where N C 1 is the set of consistent candidates and its supplementary set N U 1 .

Figure 3: This figure shows how query expansion can retrieve database video clips originally not reachable: in the database video clip 4 is not temporally consistent (and most likely not visually) with any query, however if query c returns the database video clip 3 and a new query is generated, based on c and 3 then 4 may be reached.

Temporally aligned QE. As discussed in Section 3.2, we compute the descriptor ψ ∆ (y) to measure the score between x and y assuming a time-shift of ∆. We use this property to align the descriptors of N C 1 in the temporal coordinate system of the query. In other terms, we modify the phase of the candidate i such that its similarity to the query is maximized with time-shift 0 instead of δqy. This is done by computing ψ -δqy (y) from the stored vector ψ 0 (y). The rationale is that we can now add these vectors to produce an augmented query that still offers localization capabilities. In contrast, we do not align the vectors of N U 1 , as they do not offer any temporal consistency.

Fusion strategy

We now consider several ways to produce an augmented query. They are inspired by other works on query expansion [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF][START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF]. The key differences are that we identify a time consistent subset with our triplet consistency and align these videos by performing a translation in the Fourier domain to take into account the relative time-shift with the query. We consider three fusion methods.

Average Query Expansion (AQE). The top |N1| results

associated with a query are aligned if time-consistent, and then averaged to produce the augmented query, as

ψ C AQE = ψ C (q) + x∈N 1 ψ C (x) 1 + |N1| (24)
ψ T AQE = ψ T (q) + x∈N C 1 ψ T -δqx (x) 1 + |N1| (25)
where ψ C (x) is for the constant part of the kernel feature x and ψ T (x) is for the trigonometric part of the kernel feature x. The final augmented query is the concatenation of these two features:

ψ AQE = [ψ C AQE , ψ T AQE ]. ( 26
)
2. Difference of Neighborhood (DoN). We combine our automatic alignment with an alternative QE method [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF].

It is a variant of AQE where the average vector of close to far |N2| neighbors is subtracted to the AQE vector.

ψ DoN = ψ AQE - x∈N 2 ψ 0 (x) |N2| (27)
3. DoN iterative. The DoN is iteratively applied I times. Each time the new augmented query replaces the previous one. The score for one candidate for one iteration is averaged with the score at previous iteration.

DESIGN WITH MULTIPLE PERIODS

In this section, we propose an approach to improve the localization accuracy while keeping a reasonable size for the video representation. Our motivation is twofold:

• The localization can be done up to a period modulo T only. If a video is longer than this period, our method based on explicit feature maps can not disambiguate the relative offset.

• The localization accuracy depends on the period T (scale dependency). Increasing the modulation period dramatically reduces the localization accuracy for a given number of frequencies (i.e., for a given size of the representation). In other terms, the localization is more precise for a shorter period.

We address these two problems by defining a temporal kernel constructed from multiple explicit feature maps, each being associated with a different period. As opposed to other contexts where the signal is inherently periodic, like angles [START_REF] Tolias | Orientation covariant aggregation of local descriptors with embeddings[END_REF], the choice of the period is a parameter of the method. We want to reduce it to achieve better localization. The main idea in this section is to use multiple elementary match kernels (with different periods), in order to still able to infer the correct time localization for long video.

About periodicity. The property motivating our proposal is that the sum of a T1-periodic and of a T2-periodic function is T1 × T2-periodic if T1 and T2 are relatively prime. More generally, the period is T1 × T2/gcd(T1, T2), where gcd is the greatest common divisor of T1 and T2. Said otherwise, if δt is a time shift such that |δt/2| ≤ (T1 × T2)/gcd(T1, T2), we can determine δt if we know δt mod T1 and δt mod T2. This property can be generalized to more than two decompositions, which allows us to estimate time shifts for very long videos while keeping a small number of frequencies.

We apply this idea to the temporal match kernels introduced in the previous section to generate very long periods. Figure 4 shows a toy example with two temporal match kernels having distinct periods T1 and T2. We consider two synthetic vector sequences of 600 frames each having 100 similar frames in common: the subsequence [100 : 200] in the first sequence corresponds to the subsequence [400 : 500] in the second, which means a 300 frames temporal shift. We first present match kernels with periods (T1 = 100, T2 = 200) to show that we obtain almost identical peaks due to resonance (top right figure). Unfortunately the higher peak happens at an offset of -500 frames. This is a pathological case that should be avoided because the induced period is only T1 × T2/gcd(T1, T2) = 200. In contrast, a proper choice of periods in the other example (T1 = 103, T2 = 227) does not overlap and a single clear peak appear at 300 frames.

In practice, we use four periods of modulation, T1 to T4, all being prime numbers and therefore relatively prime to each other, such that gcd(T1, T2, T3, T4) = 1. The combined kernel offers a long period. For each decomposition (each being associated with a different period), we compute the polynomial of score K∆,T for each integer value on the interval [-max(L1, L2), +max(L1, L2)], where L1 and L2 refer to the durations of the compared videos.

Two fusion operators are then considered to produce a global score function from the polynomial of scores associated with the temporal match kernel. The first is the sum of the polynomials, which itself can be written as a Fourier series. Other alternative are possible, such as taking minimum value of the different score functions. Experimentally, the "sum" and "min" fusion perform similarly for video localization. Therefore we use the sum operator for this Multi-Period Strategy (MPS) in the experimental section.

Figure 9 shows the score function between two matching videos from the EVVE Madonna video set, using a single period T = 65537 or four periods T = [2027, 3019, 5003, 7019] with the sum operator and two different settings m = 4 × 16 vs m = 1 × 64 and m = 4 × 32 vs m = 1 × 128. Observe that the multiple-periods strategy gives a better estimation of the offset. Although we do not have a precise temporal ground-truth on this dataset, we observe that this conclusion seems to be valid in most of the cases we checked: the multiple periods approach gives a better precision.

EXPERIMENTS

In this section, we evaluate the temporal match kernel introduced in Section 3, the multi-period variant of Section 5 and our temporally-aligned query expansion (Section 4) for recognition of particular events and for copy detection.

Event detection

Dataset. We consider the EVVE dataset [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] for particular event detection. The dataset contains videos from 13 particular events grabbed on Youtube TM (see in Appendix 9 the details of the events). They are professional or private contents with strong or poor temporal consistency (details are given at the end of this subsection). 620 videos serve as queries, 2375 ones are forming the database.

Frame descriptors and baseline. We use the frame 1024-dimensional multi-VLAD whiten descriptors described in [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF], available online, and compare with state-of-the-art methods that use the same input descriptors, namely CTE [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF], Mean-MultiVLAD (MMV) [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] and Stable Hyper Pooling (SHP) [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF]. CTE is able to provide localization, the two other ones can not. We also include the results achieved by MMV+CTE, which are obtained by adding the normalized scores from MMV and CTE for each query. Our method only involves three dependent parameters: β gives the steepness of the Gaussian approximated by the Fourier coefficient, T the period of modulation, and m the number of Fourier coefficients kept. This last parameter is the most important, as it induces the size of the representation. The method is not very sensitive to small variations of these values.

Event detection performance. Our method performs as well as CTE for the simple EVVE dataset, as shown in Table 1, while SHP remains higher but without alignment capability. Using a longer period of modulation, T = 65537 is preferable to a short one T = 659: a short period means that long videos will be "folded", consequently cumulated noise may create a peak in the polynomial score that overwhelms the true match. A longer period is safer but induces a less precise alignment for a fixed size of the description. When adding 100000 distractors to the database (+10K), our baseline is as good as MMV+CTE and very close to SHP. The checking of time consistency improves the precision of the method and makes it more robust in a noisy dataset.

Complexity. The modulation is done off-line for the collection. On average (over 10,000 videos, 30,000,000 frames), the modulation with m = 32 requires 0.3 s for a video clip comprising 3000 frames. Online, our Matlab implementation of the polynomial score computation requires 1 ms. For m = 16 the video descriptor dimensionality is 33792, twice bigger than SHP but still compact. The original CTE video representation depends on the video length [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF], leading to a memory footprint of 943 MB for the whole collection, while our method is about 3 times more compact (320 MB).

Query expansion. We evaluate the query expansion methods detailed in Section 4. For this purpose, we consider the baseline descriptors with a unique modulation period T = 65537 and m = 32 frequencies. The experiments confirm that the proposed phase modification is compatible with the QE framework and does not degrade the results, while preserving the localization ability of the generated queries.

Table 2 compares the three query expansion methods proposed in section 4 to the baseline. Experimentally, parameters are set to N1 = 5, N2 = 1000, AQE and DoN require one iteration of expansion while DoN iter requires three iterations. AQE gives a good improvement but DoN strongly outperforms it. The benefit of the iterative approach is only 0.3% of mAP but is consistent over almost all events. Our best score after three iterations of query expansion is 41.3%. SHP [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF] reported up to 44% on this dataset, CTE did not proposed any query expansion method, therefore no fair comparison can be provided (summary in Table 1).

In order to assess the scalability of the approach, 100000 distractors are added to the database (last line of 2: Query expansion results -in bold the most significantly improved results for event detection. N = 65537, m = 32, β = 32, N1 = 5, N2 = 1000. details in table 3). The mAP achieves 34.7% after 3 iterations, which is higher than the mAP=33.1% of SHP [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF]. This suggests again that the temporal consistency is important to improve the accuracy of the search in larger collections.

Discussion. The events can be separated in two categories, depending on whether they are highly temporally consistent or not. The first group, namely events #{5, 6, 8, 9, 10, 11, 13}, mainly contains short live events (concerts, a royal weeding, a political speech, etc), while the second one (#{1, 3, 4, 7, 12}) essentially contains edited footage of news (riots, floods, bombing, etc). The improvement of mAP using the iterative query expansion (column DoN iter ) is 9.5% (12.1% with the distractors) for the first group, 6.5% (7.6% with the distractors) for the second group, which clearly shows that our method takes advantage of the temporal consistency for generating more relevant expanded queries.

Localization by multi-period

We evaluate the quality of the localization on two benchmarks: 1) The video clip collection introduced for the copy detection task of the TRECVID 2011's evaluation campaign for which we find all its corresponding copies (5 transformations represented here). For this example, our technique finds the exact offsets (perfect temporal alignement).

[20] and 2) the Inria CLIMB dataset, which is specifically devoted to evaluate time synchronization in videos. The CTE [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] by Revaud et al. is used as the baseline. Recall that SHP [START_REF] Douze | Stable hyper-pooling and query expansion for event detection[END_REF] can not provide any localization.

TV CBCD 2011 dataset. This set was introduced for the copy detection task of the TRECVID 2011's evaluation campaign [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. It contains 16776 reference videos and 1608 queries, all extracted at 30 frames per second. The queries were artificially created from 201 videos undergoing 8 different transformations. Some query videos have no corresponding match in the database, while for 134 groups of 8 queries the system is expected to identify the correct video clip and estimates the localization in time.

To evaluate the localization capability of our approach, we match each query with its original reference video. The estimated offset is compared to the ground-truth. We mention than the ground truth is not precise (up to one or two seconds of errors in some cases), likely because of some video encoding errors. Consequently we do not expect a precision at frame level. An example of typical transformations considered in the dataset are presented in Figure 5. Frame descriptors. We extract dense PCA-ROOT-sift vectors (step of 5 pixels) and compute an improved Fisher vector [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] for each frame (using a 128 Gaussian Mixture). The 8192-dimensional frame descriptors are further whitened and normalized [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF] to produce vectors of 1024 components. As the longer database video clip contains 3694 frames, for the baseline we set T = 3695. For our multi-period approach we use the following periods: {1777, 2053, 2357, 2731}.

Localization performance. Figure 6 reports the localization performance for this copy detection task. Note that the frame rate is constant in this benchmark, which favors the temporal model assumed by CTE. Although for a few videos (about 15%), the localization accuracy is not good because the correct localization is only a local minimum of the score function and not the global one, overall, our multi-period approach clearly outperforms the single-period approach implemented in CTE, and this even when using a similar representation size. This is shown in the figure by comparing MPS with m = 16 frequencies against CTE with m = 64 frequencies. Using 4 times less frequencies compensates the fact that we use 4 periods w.r.t. complexity, yet gives much better localization accuracy. When manually looking at the alignment, we observe that our method often better aligns the videos than the ground-truth. The reader can also refer to figure 9, it shows how the multiple periods approach improves the localization for the EVVE dataset on a single real data example.

CLIMB dataset. This dataset has been created for the global video alignment task and is available online 2 . This dataset is also used for evaluating the precision of the alignment between pair of videos. The ground truth contains 89 videos at 30 fps. They have been shot, for each event, by different people moving around with different cameras. 452 temporal overlaps exist, however they are not necessarily visual overlaps. The ground truth is more precise than the TV CBCD 2011 one, here the location is at frame level.

The description is done as for the TV CBCD 2011 dataset. The videos of the dataset are longer than in the CBCD dataset, the longer one lasts 37771 frames. Consequently the single period search is set to T = 37772. The average video length being much longer than the CBCD dataset, for our MPS approach we set the periods to {2731, 4391, 9767, 14653}. The results for the localization are given in Figure 7 and illustrations of correctly aligned videos in Figure 8. The database is very challenging, yet the MPS approach clearly outperforms a single period approach and for a negligible extra computational cost (less than 10%). A direct comparison of CTE with m = 64 and our MPS method with m = 4 × 16 ensures that the memory footprint is equivalent. In this case, our method is better, especially on small localization errors. Importantly, the accuracy can further be improved by giving more memory budget to our method, as shown when setting m = 4 × 32 and m = 4 × 64.

Query expansion with multiple periods

Finally, as a concluding experiment, we assess the complementarity of our methods on a event detection task when using all our contributions: the multiple periods match kernel combined with query expansion. The experiments are carried out on the EVVE dataset to allow a direct comparison. The results are reported on Table 4. Observe that they are almost identical to those reported for the single period match kernel with query expansion (Table 2). This suggests that the best option is indeed to combine these methods, as we obtain a similar detection rate with a better alignment.

CONCLUSION

This paper proposes a temporal matching kernel for efficient search and localisation of temporally consistent videos. The features, very compact and fast to compute, are also compatible with the query expansion strategies and yet preserve their localization capability. We further propose a multi-period strategy to improve the localisation of the common excerpts at not memory cost and for a very low extra We visually estimate that the ground-truth offset is 17.5 seconds (+/-0.5 second). The multi-period approach clearly improves the precision of the localisation. computation burden. All these items make the method effective for many tasks, as diverse as event retrieval, copy detection or video synchronization, and outperform state of the art methods that can compete on this range.

ACKNOWLEGMENT

This work was partly supported by ERC project Viamass no. 336054, JSPS KAKENHI Grant Numbers 26240016 and 24-02712, and NII International Internship.

ANNEX

The events are numbered as follows (alphabetical order):

c

  2015 ACM. ISBN 978-1-4503-3459-4/15/10 ...$15.00. DOI: http://dx.doi.org/10.1145/2733373.2806228.

Figure 2 :

 2 Figure 2: Polynomial of scores K∆(x, y) for a matching pair of sequences (x, y) (blue) and two unrelated sequences (red).

Figure 4 :

 4 Figure 4: Top left: similarity matrix between two synthetic vectors of 600 frames. Top left plot: the elementary match kernels T = {100, 200} overlap relatively soon, producing a combined (sum, top right plot) match kernel having a relatively short period. In contrast, the other construction (bottom figures) is a better choice: the elementary match kernels T = {103, 227} are complementary.

  N = 65537, m = 32, β = 32, N1 = 5, N2 = 1000.

Figure 5 :

 5 Figure 5: Examples of one video clip (reference is top-left)for which we find all its corresponding copies (5 transformations represented here). For this example, our technique finds the exact offsets (perfect temporal alignement).

Figure 6 :

 6 Figure 6: Localization accuracy on CBCD'2011 for CTE and our multi-period strategy (MPS). We show the rate of queries localized better than a tolerance δ (high is better). Note that the size of the representation for CTE with m = 64 is similar to that of MPS with 4 periods and m = 16.

2

  http://pascal.inrialpes.fr/data/evve/index align.html

Figure 7 :

 7 Figure 7: Localization accuracy on CLIMB dataset for CTE and our multi-period strategy (MPS). We show the rate of queries localized better than a tolerance δ (high is better). Note that the size of the representation for CTE with m = 64 is similar to that of MPS with 4 periods and m = 16.

Figure 8 :

 8 Figure 8: Captions of couples of video clips well aligned. One column, one couple. On the bottom, first and second ones were initially shot vertically.

Figure 9 :

 9 Figure9: On the top row, on the first column the similarity matrix between two matching videos from the Madonna 2012 Roma concert event (4471 and 5441 frames), beside four captions of each video temporally aligned. It can be seen that it hard to evaluate a visual match between these videos: no clear ridge of high similarity appears in the matrix. On the second row, the first four figures represent the result of the polynomial for some offsets between the videos for different periods of modulation T = {2027, 3019, 5003, 7019} for m = 16. Their sum appear on the right figure in blue, while the result of the polynomial for a single period T = {65537} for m = 64. The multi-period maximal value is observed at 16.3 seconds, the single period one at 12.8 seconds. On the third row, are represented the same figures for T = {2027, 3019, 5003, 7019} for m = 32. Their sum appear on the right figure in blue, while the result of the polynomial for a single period T = {65537} for m = 128. The multi-period maximal value is observed at 17.1 seconds, the single period one at 12.8 seconds. We visually estimate that the ground-truth offset is 17.5 seconds (+/-0.5 second). The multi-period approach clearly improves the precision of the localisation.

table 1

 1

	and

Table 1 :

 1 Top: Results of our temporal embedding on the EVVE dataset, with two fixed periods of modulation T = {659, 65537}, two Fourier decompositions m = {16, 32}, with (β = 32). Bottom: state of the art methods VS ours (m = 32, T = 65537), with or without +10K distractors, with or without Query Expansion (simple DoN for SHP and phase modified DoN for Ours).

		baseline AQE	DoN	DoN iter	+/-
	#1	0.243	0.284	0.378	0.393	+ 0.15
	#2	0.201	0.201	0.193	0.192	-0.01
	#3	0.088	0.056	0.104	0.104	+ 0.02
	#4	0.120	0.116	0.151	0.156	+ 0.04
	#5	0.235	0.241	0.277	0.287	+ 0.05
	#6	0.340	0.406 0.497	0.497	+ 0.16
	#7	0.140	0.043	0.110	0.111	-0.03
	#8	0.257	0.258	0.263	0.266	+ 0.01
	#9	0.550	0.669 0.762	0.764	+ 0.21
	#10	0.468	0.530 0.588	0.581	+ 0.11
	#11	0.759	0.815 0.814	0.806	+ 0.05
	#12	0.363	0.422 0.484	0.494	+ 0.13
	#13	0.589	0.642 0.712	0.721	+ 0.13
	mAP	0.335	0.361	0.410	0.413	+ 0.08
	Table

Table 3 :

 3 Query expansion results with +10K -in bold the most significantly improved results for event detection.

		baseline	DoN	DoN iter	+/-
	#1	0.219	0.338	0.376	+ 0.15
	#2	0.178	0.173	0.184	+ 0.01
	#3	0.077	0.076	0.084	+ 0.01
	#4	0.070	0.090	0.093	+ 0.02
	#5	0.183	0.204	0.219	+ 0.04
	#6	0.248	0.424	0.445	+ 0.20
	#7	0.109	0.091	0.131	+ 0.04
	#8	0.228	0.234	0.250	+ 0.02
	#9	0.458	0.657	0.665	+ 0.21
	#10	0.451	0.612	0.617	+ 0.16
	#11	0.331	0.373	0.393	+ 0.06
	#12	0.206	0.343	0.362	+ 0.16
	#13	0.541	0.663	0.689	+ 0.16
	+10K mAP	0.254	0.329	0.347	+ 0.10

Table 4 :

 4 Combining multi-period and query expansion on EVVE dataset -in bold the most significantly improved results for each event. N = {2027, 3019, 5003, 7019}, m = 32, β = 32, N1 = 5, N2 = 1000.

		baseline	DoN	DoN iter	+/-
	#1	0.242	0.383	0.404	+ 0.16
	#2	0.200	0.194	0.193	-0.01
	#3	0.085	0.091	0.093	+ 0.01
	#4	0.120	0.148	0.153	+ 0.03
	#5	0.235	0.277	0.286	+ 0.05
	#6	0.340	0.502	0.498	+ 0.16
	#7	0.115	0.119	0.115	+ 0.00
	#8	0.257	0.264	0.268	+ 0.01
	#9	0.551	0.762	0.764	+ 0.21
	#10	0.469	0.587	0.580	+ 0.11
	#11	0.756	0.812	0.803	+ 0.05
	#12	0.363	0.484	0.494	+ 0.13
	#13	0.589	0.714	0.723	+ 0.13
	mAP	0.332	0.410	0.413	+ 0.08

  1. barcelona riots 2012 2. die toten hosen rock am ring 2012 3. dsk arrested 4. egypt Tahrir Square protestors 5. johnny stade de france 2012 6. kate william wedding 7. marrakech bomb attack 8. madonna rome 2012 9. obama speech victory 10. shakira live kiev 2011 11. strokkur geyser 12. thailand flood 2011 13. universal studios jurassic park ride

The timestamps are not necessarily integers, any real value is possible. We use integers for the sake of simplicity.