Matthijs Douze

Jérôme Revaud

Jakob Verbeek

Hervé Jégou

Cordelia Schmid

Circulant temporal encoding for video retrieval and temporal alignment

published or not. The documents may come

Circulant temporal encoding for video retrieval and temporal alignment

or near duplicate clips or sub-clips from a large video collection. Examples of applications are automatic copyright enforcement, identification of advertisement videos or automatic organization of video collections. We show that our approach can retrieve different videos of the same event filmed from different viewpoints. For instance, CTE can recognize that several amateur videos shot by different persons attending the same concert do correspond. Indexing this type of video material on-line and in archives enables to mine video data in large archives that are often indexed with sparse and noisy keywords. CTE can also be applied to automatic temporal alignment of a set of videos of the same event, in order to play back the videos synchronously. For example, home users who have shot tens of videos of an event such as a wedding or a sports event would like to combine them into a single movie of the event. Professional users want to organize a collection of videos from different viewpoints of the same scene, shot under conditions that prevented them to gather appropriate metadata. Video collections of an event such as a theatrical performance retrieved from external sources such as YouTube or other video sharing sites, can be edited into a single movie.

A preliminary version of this work, introducing CTE for the purpose of large-scale video retrieval, appeared in [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. The core contribution of CTE is to jointly encode in a single vector the appearance information at the image level and the temporal sequence of frames, such that it enables an efficient search scheme that avoids the exhaustive comparison of frames. Extensive experiments on two video copy detection benchmarks in [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] have shown that CTE improves over the state of the art with respect to accuracy, search time and memory usage, and allows as well to retrieve video of specific instances of events despite important viewpoint changes in a large collection of videos.

Although we briefly mentioned in [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] the possibility of aligning multiple videos with CTE, we did not describe the approach in detail and there was no experimental evaluation. In this paper, we introduce a new dataset for global video alignment. It consists of temporally aligned videos of a rock climbing session, captured with different cameras including mobile phones, camcorders and head-mounted cameras. We also annotate the ground-truth for the temporal alignment of 163 clips of the Madonna in Rome event from the publicly available EVVE dataset [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. Furthermore, we present a robust temporal alignment algorithm that takes as input pairwise video matches and their estimated temporal shift, and produces a global temporal alignment of the videos. This alignment process is evaluated using the ground-truth alignment of the Madonna and Climbing datasets.

The rest of this paper is organized as follows. Section 2 reviews related work on video retrieval and alignment. Section 3 describes our temporal circulant encoding technique, Section 4 presents our indexing strategy and Section 5 introduces our robust video alignment method. Section 6 introduces the datasets used in the experiments and the related evaluation measures. Experimental results in Section 7 demonstrate the excellent performance of our approach for video retrieval and alignment. Finally, we present our conclusions in Section 8.

Related work

We review related work on video retrieval and alignment in Sections 2.1 and 2.2 respectively.

Video retrieval

Searching for specific events is related to video copy detection [START_REF] Law-To | Video copy detection: a comparative study[END_REF] and event category recognition [START_REF] Oneata | Action and event recognition with Fisher vectors on a compact feature set[END_REF], but there are substantial differences with both tasks. The goal of video copy detection is to find videos that are distorted versions of the query video, e.g., by compression, cam-cording or picture-in-picture transformations. Detecting event categories requires a classification approach that captures the large intraclass variability in semantically defined events like brush hair in HMDB51 [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF], birthday party in Trecvid MED [START_REF] Over | Trecvid 2014 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF], or high jump in UCF101 [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF]. Such datasets provide a large pool of positive and negative examples to train the classifier. In contrast, the method introduced in this paper is tailored to specific event retrieval, that is, finding videos of a particular event instance. It, thus, needs to be flexible enough to handle significant viewpoint changes, but should nevertheless produce a precise alignment in time. Retrieval is performed given one video query, i.e. without training data. This is substantially different from approaches aiming at discovering high-level correspondences between seman-tic actions in different videos [START_REF] Chu | Unsupervised temporal commonality discovery[END_REF][START_REF] Hoai | Maximum margin temporal clustering[END_REF][START_REF] Xiong | Coaction discovery: Segmentation of common actions across multiple videos[END_REF]. These methods discover common temporal patterns between videos in an unsupervised fashion, and allow the matched subsequences to have varying length. Both [START_REF] Hoai | Maximum margin temporal clustering[END_REF][START_REF] Xiong | Coaction discovery: Segmentation of common actions across multiple videos[END_REF] rely on high-level descriptors and flexible alignment methods based on discriminative clustering in order to match different instances of the same action classes. The discriminative clustering approach characterizes common subsequences of videos (clusters) using separating hyperplanes, which can only be reliably estimated from lager collections of videos, and cannot be readily used to measure the similarity between two videos. The branch-and-bound technique of [START_REF] Chu | Unsupervised temporal commonality discovery[END_REF] can in principle be adapted to force matching subsequences to be of the same length. The bounds used in their work, however, rely on representing a sequence by accumulating individual frame feature histograms. This temporal aggregation makes precise temporal alignment particularly problematic with their approach. Our goal is to retrieve videos of the same specific event instance as the query video. In this context, a precise temporal alignment is well-defined and feasible. We exploit this property to tackle difficult viewpoint changes with little discriminant motion.

Many techniques for video retrieval represent a video as a set of descriptors extracted from frames or keyframes [START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF][START_REF] Karpenko | Tiny Videos: A large data set for nonparametric video retrieval and frame classification[END_REF][START_REF] Song | Multiple feature hashing for real-time large scale near-duplicate video retrieval[END_REF]. Searching in a collection is performed by comparing the query descriptors with those of the dataset. Then, temporal constraints are enforced on the matching descriptors, by e.g., partial alignment [START_REF] Yeh | Video copy detection by fast sequence matching[END_REF] or classic voting techniques, such as temporal Hough transform [START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF], which was popular in the TRECVID video copy detection task [START_REF] Smeaton | Evaluation campaigns and Trecvid[END_REF]. Such approaches are costly, since all frame descriptors of the query must be compared to those of the database before performing the temporal verification.

In contrast, the technique proposed in this paper measures the similarity between two sequences for all possible alignments at once. Frame descriptors are jointly encoded in the frequency domain, where convolutions cast into efficient element-wise multiplications. This encoding is combined with frequency pruning to avoid the full computation of all cross-similarities between the frame descriptors. The comparison of sequences is improved by a regularization in the frequency domain. Computing a matching score between videos requires only component-wise operations and a single one-dimensional inverse Fourier transform, avoiding the reconstruction of the descriptor in the temporal domain.

Similar techniques have been used for registration or watermark detection. However, they are usually applied to the raw signal such as image pixels [START_REF] Brown | A survey of image registration techniques[END_REF][START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF] or audio waveforms [START_REF] Kalker | A video watermarking system for broadcast monitoring[END_REF]. Transforming a multi-dimensional signal to the Fourier domain was shown useful to speed up object detection [START_REF] Dubout | Exact acceleration of linear object detectors[END_REF][START_REF] Henriques | Beyond hard negative mining: Efficient detector learning via block-circulant decomposition[END_REF].

We optimize the tradeoff between search quality, speed and memory consumption using product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], which we extend to complex vectors in order to compare our descriptors in the compressed Fourier domain.

Precise video alignment

Existing temporal video alignment techniques for videos of the same specific event are limited to constrained environments, or impose strong requirements on the video capturing process. Below, we review the most important existing alignment techniques.

Genlocking cameras consists in triggering the shutter of the cameras by a common clock signal [START_REF] Petit | Multicamera real-time 3D modeling for telepresence and remote collaboration[END_REF]. This ensures that the frames are perfectly synchronized, which is useful for the 3D reconstruction of fast-moving scenes [START_REF] Franco | Efficient polyhedral modeling from silhouettes[END_REF]. A movie clapperboard or a light flash [START_REF] Jiang | 3D Reconstruction of dynamic scenes with multiple handheld cameras[END_REF] can be used to recognize a common time instant in the different videos. This approach also imposes constraints on the capturing process, even though the problem is simplified.

When the cameras have approximately the same viewpoint, the optimization of an error criterion between the image pixels can be used to compute a spatio-temporal model mapping one video to another [START_REF] Caspi | Spatio-temporal alignment of sequences[END_REF]. In another work [START_REF] Tuytelaars | Synchronizing video sequences[END_REF], the alignment is obtained by explicitly matching scene points and using geometrical constraints on the matches to spot consistent frames. This is extended in [START_REF] Evangelidis | Efficient subframe video alignment using short descriptors[END_REF] to a spatio-temporal model with a non-constant time shift, which can be used for example to match videos of different passages through the same street. Another work along the same lines is VideoSnapping [START_REF] Wang | Videosnapping: Interactive synchronization of multiple videos[END_REF], which focuses on adjusting the speed of one video to match that of a reference one. Similar to our method, VideoSnapping also addresses the alignment of multiple videos using a minimum spanning tree. In both [START_REF] Evangelidis | Efficient subframe video alignment using short descriptors[END_REF] and [START_REF] Wang | Videosnapping: Interactive synchronization of multiple videos[END_REF], the temporal model is more general than ours: instead of a constant time shift, they estimate a dynamic time warping (DTW). This is much harder because the number of parameters is proportional to the length of the movies, and restricts these methods to relatively high-quality footage with clean keypoints (e.g. strong corners on buildings, square objects). In contrast, our method can deal with less restrictive settings such as low-quality videos from YouTube or videos that are static for long periods, as shown on Figure 1.

The audio produced along with the different cameras can be aligned more easily, as it is a one dimensional signal [START_REF] Hasler | Markerless motion capture with unsynchronized moving cameras[END_REF][START_REF] Kennedy | Less talk, more rock: Automated organization of community-contributed collections of concert videos[END_REF]. However, this can be exploited only if the scene is sufficiently small to avoid a drift due to the relatively slow propagation of sound in the air. Moreover, audio may not be distinctive enough (e.g., if the audio track is dominated by motor sounds), or its quality may be too poor.

In contrast to these approaches, our approach does not impose constraints on the capturing process. Therefore, unlike genlocking or clapperboard-like techniques, our approach is applicable to videos of an event acquired in an uncontrolled and uncoordinated manner. Compared to audio-based approaches, our approach is more robust since we rely on the richer visual signal.

Video matching using circulant temporal encoding

This section describes the algorithm for video matching. We first present the video descriptors in Section 3.1, and the general matching formulation in Section 3.2. We then present the efficient circulant temporal encoding technique in Section 3.3, and a robust regularized version of it in Section 3.4 Finally, in Section 3.5 we discuss how the matching subsequences are extracted.

Video frame descriptors

We represent a video by a sequence of high-dimensional frame descriptors. The representation is obtained in the following three steps.

Pre-processing. All videos are mapped to a common format, by sampling them at a fixed rate of 15 fps and resizing them to a maximum of 120k pixels, while keeping the aspect ratio unchanged.

Local description. We compare two types of local descriptors that are aggregated in the same way. First, local SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] are extracted for each frame on a dense grid [START_REF] Nowak | Sampling strategies for bag-offeatures image classification[END_REF], every 4 pixels and at 5 scale levels. We use dense sampling of local descriptors rather than interest points, as this increases the accuracy without impacting the storage size after aggregation.

Alternatively, dense trajectory descriptors (DT) [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] are extracted around dense points tracked during 15 frames. We use the histogram of optical flow (HOF) descriptor for the trajectories, which was found to be most discriminant. We refer to these features as DTHOF. Note that for the last 15 frames of the video we do not extract additional trajectories, since tracks cannot be long enough.

We compute the square-root of the local descriptor components and reduce the descriptor to 32 dimensions with principal component analysis (PCA) [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].

Descriptor aggregation. The local descriptors of a frame are encoded using MultiVLAD [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF], a variant of the Fisher vector [START_REF] Sánchez | Image classification with the Fisher vector: Theory and practice[END_REF]. Two VLAD descriptors are obtained based on two different codebooks of size 128 and concatenated. Power normalization is applied to the vector, and it is reduced by PCA to dimension d (a parameter of our approach). The vector is normalized using the PCA covariance matrix and 2normalization.

Parameters of the frame descriptors. The parameters of the local descriptor extraction and VLAD aggregation were chosen on the image retrieval benchmark Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] to optimize the trade-off between descriptor size, extraction speed and performance. The Holidays dataset is an instance retrieval benchmark, which is closely related to the specific video event retrieval task addressed in this paper.

Because the descriptors are extracted from potentially large video sequences, they need to be fast to compute and compact. Our implementation extracts frame descriptors based on SIFT in real time (15 fps) on a single processor core, producing VLAD descriptors of size 512 or 1024. For the dense-trajectory descriptor DTHOF, we used the default parameters but only compute its histogram of flow (HOF) descriptor. Various other settings and descriptors of the densetrajectory descriptor [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] were tested but did not improve the results. Using trajectory descriptors is about ten times slower than SIFT. Therefore, we perform most large-scale evaluations using SIFT only.

Matching frame descriptors

Our goal is to compare two sequences of frame descriptors q = [q 1 , . . . , q m ] ∈ R d×m and b = [b 1 , . . . , b n ] ∈ R d×n corresponding to the query video and an item in the video database.

We first consider the metric

s δ (q, b) = ∞ t=-∞ q t , b t-δ , (1)
where the vectors q t (resp., b t ) are zero when t < 1 and t > m (resp., t > n). This is an extension of the correlation used for pattern detection in scalar signals [START_REF] Kumar | Correlation Pattern Recognition[END_REF]. The metric s δ (q, b) reaches a maximum in δ when the q and b are aligned if the following assumptions are satisfied:

Assumption 1: There is no (or limited) temporal acceleration. This hypothesis is assumed by the "temporal Hough transform" [START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF] when only the shift parameter is estimated.

Assumption 2: The inner product is a good similarity measure between frame descriptors. This is the case for Fisher and our MultiVlad descriptors (Section 3.1), but less so for other type of descriptors, eg. bag-of-words, to be compared with more general kernels.

Assumption 3: The sum of similarities between the frame descriptors at a constant time shift is a good indicator of the similarity between the sequences. In practice, this assumption may not be satisfied. Videos are often self-similar in time. In this case, two long nearly static sequences may -if their frame descriptors are somewhat similar-accumulate to a stronger response than shorter sequences of truly temporally aligned frames. Therefore, the similarity measure proposed in Equation ( 1) may favor an incorrect alignment. In our case, this problem will be addressed by a regularization of the metric in the Fourier domain which also makes the metric invariant to video duration, see Section 3.4.

We now present Circulant Temporal Encoding (CTE) to efficiently compute the s δ (q, b) for all possible values of δ at once. It relies on Fourier-domain processing. Section 3.4 presents the regularization techniques that address the limitations mentioned in Assumption 3.

Circulant encoding of vector sequences

Equation 1 can be decomposed along the dimensions of the descriptor. Introducing the per-row notations q = [q 1 , . . . , q d ] and b = [b 1 , . . . , b d ] , the scores for all possible values of δ is given by

s(q, b) = [. . . , s 0 (q, b), s 1 (q, b), . . . ] = d i=1 q i ⊗ b i , (2)
where ⊗ is the convolution operator. Assuming sequences of equal lengths (n = m), s(q, b) is computed in the Fourier domain [START_REF] Kumar | Correlation Pattern Recognition[END_REF]. Denoting by F the 1D-discrete Fourier transform and F -1 its inverse, the convolution theorem states that:

s(q, b) = d i=1 F -1 F(q i ) F(b i ) (3)
where is the element-wise multiplication of two vectors and F(q i ) is the complex conjugate of F(q i ). Using row vector notations

Q i = F(q i ) ∈ C m and B i = F(b i ) ∈ C n
, the linearity of the Fourier operator gives:

s(q, b) = F -1 d i=1 Q i B i , (4)
which is more efficient to compute than Equation 3 because it requires a single inverse FFT instead of d, while performing the same number of component-wise multiplications. In practice, we rely on the Fast Fourier Transform (FFT) and its inverse, which are very efficient, especially for sequences whose length is a power of two. As a common practice, the descriptor sequences are padded with zeros to reach the next power of two [START_REF] Kumar | Correlation Pattern Recognition[END_REF]. Unless stated otherwise, we consider hereafter that the sequences have been preprocessed to have the same length m = n = 2 .

Regularized comparison metric

As mentioned above, due to the temporal consistency and more generally the self-similarity of frames in videos, the values of the score vector s(q, b) are noisy and its peak over δ is not precisely localized, as shown in Figure 2(a). This is obvious when comparing the query to itself: s(q, q) consists of a relatively wide peak around δ = 0 whose magnitude directly depends on the query duration, as shown in Figure 2(b). Instead, one would ideally obtain a Dirac response, independent from the video content and duration, that is: s δ (q, q) = 0 for δ = 0, and s 0 (q, q) = 1. This behavior can be achieved through an additional filtering stage in the Fourier domain. We use a set of filters W = {W 1 , . . . , W d }, W i ∈ R n to redefine the score vectors as

s W (q, b) = F -1 d i=1 Q i B i W i , (5)
where the division is element-wise. We then aim to set the filters so that the score vector that compares the query with itself gives the desired Dirac response

s W (q, q) = F -1 d i=1 Q i Q i W i = [1, 0, . . . , 0] = e 1 . (6)
For the sake of simplicity, we compute W i assuming that the contributions are shared equally across dimensions:

F -1 Q i Q i W i = 1 d e 1 ∀i = 1 . . . d (7)
Hence

Q i Q i W i = 1 d F (e 1 ) = 1 d [1, 1, . . . 1], (8)
The closed-form solution of each filter W i is therefore obtained in the Fourier domain as

W i = d Q i Q i . (9)
The filters W i can be interpreted as a peak detectors in s(q, b).

In practice, its spectrum resembles that of a Laplacian filter. One drawback of this solution is that some elements of the denominator W i in Eqn. 5 may be close to zero, which magnifies the noise and de-stabilizes the solution. To tackle this issue, Bolme et al. [START_REF] Bolme | Visual object tracking using adaptive correlation filters[END_REF] average the filters obtained from independent samples (dimensions in our case). It is indeed unlikely that high-dimensional filters obtained independently have near-zero values at identical positions. In our case, we average the filters W i , since they are independent due to the decorrelation property of the PCA [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], see Section 3.1.

Unfortunately, averaging does not always suffice, as some videos contain only one shot composed of static frames: the components associated with high frequencies are near zero for all W i . Therefore, we incorporate a regularization term into Equation 6 and determine the W i minimizing

λ 1 W i 2 + F -1 Q i Q i W i - 1 d e 1 2 , (10)
where the regularization coefficient λ ensures the stability of the filter. Notice that setting λ = 0 amounts to solving Equation 8 and leads to the solution proposed in Equation 9.

A closed-form solution to this minimization problem in the Fourier domain [START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF], obtained by leveraging properties of circulant matrices, consists of adding λ to all the elements of the denominator in Equation 9. This leads to a regularized score vector between two video sequences q and b:

s λ reg (q, b) = 1 d F -1 d i=1 Q i B i Q i Q i + λ . ( 11
)
Both regularization techniques, i.e., averaging the filters and using a regularization term, are complementary. We have empirically observed that combining them gives more stable results than using either one separately. This yields the following regularized matching score, illustrated in Figure 2(c):

s λ (q, b) = F -1 d i=1 Q i B i Q den , (12)
with

Q den = d j=1 Q j Q j + λ. ( 13
)
The choice of λ is discussed in Section 7.

Temporal alignment and boundary detection

The strategy presented above produces a vector of matching scores, s λ (q, b) = [. . . , s λ δ (q, b), . . . ], between two video sequences q and b, for all possible temporal offsets δ. The optimal temporal alignment of the two videos is given by

δ * = arg max δ∈Z s λ δ (q, b), (14)
and s λ δ * (q, b) is their similarity score. In some applications such as video alignment (see Section 7), we also need the boundaries of the matching segments. For this purpose, the database descriptors are reconstructed in the temporal domain from F -1 (b i ). A frameper-frame similarity is then computed with the estimated shift δ * as:

S t = q t , b t-δ * . ( 15
)
The matching sequence is defined as a set of contiguous t for which the scores S t are high enough. In practice, we use a threshold equal to half the peak score max t S t . This also refines the matching score between videos, which is replaced by the sum of S t on the matching sequence. Note that, unlike the computation of s λ δ * (q, b), this processing requires d distinct 1D inverse FFT, one per component. Yet, on large datasets this does not impact the overall efficiency, since it is only applied to a shortlist of database videos b with the highest pairwise scores s λ δ * (q, b).

Indexing strategy and complexity

This section discusses the steps to efficiently encode the descriptors in the Fourier domain. The goal is to implement the method presented in Section 3 in an approximate manner. Beyond the complexity gain already obtained from our Fourier-domain processing, this considerably improves the efficiency of the method while reducing its memory footprint by orders of magnitude. As shown later by our experiments (Section 7), this gain is achieved without significantly impacting the retrieval quality.

Frequency-domain representation

A video b of length n is represented in the Fourier domain by

a complex matrix B = [B 1 , . . . , B d ] = [f 0 , . . . , f n-1 ],
with B ∈ C d×n . Our input descriptors are real-valued, so only half of the components are stored, as f n-i is the complex conjugate of f i .

Frequency pruning is applied to reduce the video representation by keeping only a fraction n = βn n of the low-frequency vectors f i , i = 0 . . . n -1 (in practice, β is a negative power of 2). We keep a fraction rather than a fixed number of frequencies for all videos, as this would make the localization accuracy dependent on the sequence length.

Descriptor sizes. The comparison of a query q video of length m and a database video b of size n in the Fourier domain requires them to have the same size. To handle the case m ≤ n, we precompute a Fourier descriptor for different zero-padded versions of the query, i.e., for all sizes 2 such that m ≤ 2 ≤ n max , where n max is the size of the longest database video.

We handle the case m > n by noticing that the Fourier descriptor of the concatenation of a signal with itself is given by [f 0 , 0, f 1 , 0, f 2 , 0, . . . ]. Therefore, expanded versions of database descriptors can be generated on the fly and at no cost. However, this introduces an ambiguity on the alignment of the query and database videos: δ * is determined modulo n, due to the repetition of the signal. In practice, the ambiguity is resolved when estimating the matching segment's boundaries, as described in Section 3.5.

Complex PQ-codes and metric optimization

In order to further compress the descriptors and to efficiently compute Equation 12, we propose two extensions of the product quantization technique [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], a compression technique that enables efficient compressed-domain comparison and search. The original technique proceeds as follows. A given database vector y ∈ R d is split into p sub-vectors y i , i = 1 . . . p, of length d/p, where d/p is an integer. The sub-vectors are separately quantized using k-means quantizers q i (.), i = 1 . . . p. This produces a vector of indexes [q 1 (y 1 ), . . . , q p (y p )]. Typically, q i (y i ) ∈ [1, . . . , 2 8 ].

The comparison between a query descriptor x and the database vectors is performed in two stages. First, the squared distances between each sub-vector x j and all the possible centroids are computed and stored in a table T = [t j,i ] ∈ R p×256 . This step is independent of the database size. Second, the squared distance between x and y is approximated using the quantized database vectors as

d(x, y) 2 ≈ p j=1 t j,qj (yj ) , (16)
which only requires p look-ups and additions.

We adapt this technique to our context in two ways. First, it is extended to complex vectors in a straightforward manner. We learn the k-means centroids for complex vectors by considering a d-dimensional complex vector to be a 2ddimensional real vector, and this for all the frequency vectors that we keep: C d ≡ R 2d and f j ≡ y j . At query time, the table T stores complex values.

Computing the score of Equation 12requires to produce the n scalar products between the corresponding columns of B and a matrix Q reg , which represent a database video and the query video respectively, with

Q reg = Q 1 Q den • • • Q d Q den . ( 17
)
Matrix B is approximated with a product quantizer, so for each d/p-sized subvector of the n columns of Q reg , we precompute the scalar products with the 256 possible subvectors of B.

As a result, our table T stores the partial sums for all possible centroids, including the processing associated with the regularization filter. As with the regular product quantization technique, a single comparison only requires pn look-ups and additions of complex numbers. The memory used for T (2 × 256 × p × n ) is a constant that does not depend on the database size.

Interestingly, the product quantization vocabularies do not need to be learned on representative training data: they can be trained on random Gaussian vectors in R (2d/p) . This is due to the fact that the PCA whitening applied to generate b j and the Fourier transform applied on b i normalize and decorrelate the signal spatially and temporally [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF][START_REF] Mallat | A wavelet tour of singal processing[END_REF]. We also L2-normalize each frequency vector f i so that they have unit variance. Empirically, we verified that the resulting vectors are close to a Gaussian distribution.

Summary of search procedure and complexity

Each database video is processed offline as follows:

1. The video is pre-processed, and each frame is described as a d-dimensional MultiVlad descriptor. 2. This vector is padded with zeros to the next power of two, and mapped to the Fourier domain using d independent 1-dimensional FFTs.

3. High frequencies are pruned: Only n = β ×n frequency vectors are kept. After this step, the video is represented by n × d-dimensional complex vectors. 4. These vectors are separately encoded with a complex product quantizer, producing a compressed representation of p × n bytes for the whole video.

At query time, the submitted video is described in the same manner, except that the query is not compressed with the product quantizer. Instead, it is used to pre-compute the look-up tables used in asymmetric PQ distance estimation, as discussed above. The complexity at query time depends on the number N of database videos, the size d of the frame descriptor, and the video length, that we assume for readability to be constant (n frames): 12is evaluated for all database vectors using the approximation of Equation 16, directly in the compressed domain using n × p look-ups from T and additions. This produces a n -dimensional vector for each database video. 4. O(N × n log n ) -This vector is mapped to the temporal domain using a single inverse FFT. Its maximum gives the temporal offset δ * and the score s λ δ * . As described in Section 4.1, the operations 1 and 2 are repeated for all sizes n = 2 found in the dataset. This doubles the runtime of the operations applied to n = n max . Only the steps 3 and 4 depend on the database size. They dominate the complexity for large databases.

1. O(d × n log n) -
Q reg is pre-computed 3. O(N × p × n ) -Equation

Global temporal video alignment

In this section we produce a global temporal alignment of a collection of videos. Aligning a set of videos requires to estimate the starting time of each video on a shared time line, so that the temporal offsets estimated between pairs of videos are best satisfied like in Figure 3-right. The estimated common time line enables synchronized playback of videos captured from different viewpoints, as depicted in Figure 5. We use the technique of Section 3.5 to match and estimate a temporal offset δ * for all possible videos pairs. Because of mismatches, edited input videos, etc, the global alignment needs to be robust to outliers.

The temporal alignment is applied either to all result videos for a given query, or to a set of videos that are known a-priori to correspond to a single event. In Section 5.1 we discuss how our approach can be applied to align singleshot videos (rushes), and Section 5.2 extends the method to edited videos.

Robust alignment from pairwise matches

We use the CTE method of Section 3 to find a collection of pairwise matches (i, j) among the N videos. Each match is characterized by (δ ij , s ij ), where δ ij gives the estimated starting time of video j in video i, and s ij is the confidence score s λ δ * associated with the match. We retain matches only if s ij is above a threshold. Aligning the videos consists in putting the videos on a common timeline by estimating the starting times t i for each video i ∈ {1, . . . , N } such that for all matches (i, j) we have t j ≈ t i + δ ij .

The input matches are noisy because the events may be similar but not the same (e.g., recurring similar motions observed in a sequences of a walking person), because the video content overlaps only in part of the videos (e.g., due to pan-tilt camera motions), or in case of edited videos where δ is valid only for part of the video. Therefore, in the alignment process we aim at finding a subset of matches that is as large as possible, while ensuring a consistent placement on a common timeline, up to a tolerance τ . More formally, given a set of N videos and a set of M matches M = {(i 1 , j 1 ), . . . , (i M , j M )}, the goal is to find a set C ⊆ M that is as large as possible such that

∃{t 1 , . . . , t N } ∀(i, j) ∈ C : |t i -t j -δ ij | < τ, (18)
where t i is the starting point of video i on the global timeline. See Figure 3 for an illustration. The pairwise matches induce a graph over the videos. Each node corresponds to a single video, and each match corresponds to an edge between two videos. The graph may contain several connected components if there are no edges between different groups of videos. For each connected component we produce a separate global alignment of the videos belonging to that component.

We use an approximate greedy strategy to solve this problem. As shown in the precision-recall plot of Figure 4, true matches often have higher scores than false matches. Therfore, the ordering of the match scores s λ δ * tends to be reliable, so we first select a maximum spanning tree in the match graph based on the match scores. Using this subset of matches and corresponding temporal offsets, we find an alignment that perfectly satisfies all the pairwise offsets, at least in the absence of additional constraints. We then iteratively add matches for which the temporal offset is consis- tent with the current alignment (up to a tolerance τ ), and find the global alignment that minimizes the sum of squared errors (t i -t j -δ ij ) 2 for all selected matches. The procedure is detailed in Algorithm 1.

Different connected components cannot be aligned automatically among each other due to the lack of matches. If they correspond to events that do overlap, manual alignment can be effective, since the number of connected components is typically much smaller than the number of input videos. Mismatches can also be corrected manually, see Section 7.4.

Algorithm 1 Find globally consistent temporal alignment

Input:

set of video matches M = {(i 1 , j 1 ), . . . , (i M , j M )}, scores associated with the matches s 1 , . . . , s M .

tolerance threshold τ , Output:

global temporal alignment t 1 , .., t N , subset of matches C ⊂ M consistent with alignment 1. Compute maximum spanning tree (MST) based on the scores s 1 , . . . , s M . 2. Initialize C as set of edges in the MST. 3. Solve for alignment using subset of edges

min {t 1 ,...,t N } (i,j)∈C (t i -t j -δ ij ) 2 (19) 4. Add matches (i, j) ∈ M with |t i -t j -δ ij | < τ to C 5.
If matches were added: go back to step 3, else return the estimated {t i } and the consistent set of matches C,

Alignment of edited videos

In order to align edited videos, we determine the temporal extent of the matches using the method of Section 3.5, which produces hypotheses about matching sub-sequences; we call these "anchor segments". The anchor segments replace videos as the basic units manipulated by Algorithm 1.

Note that two anchor segments from the same video, but defined by independent matches, can temporally overlap. Aligning the anchor segments instead of complete edited videos allows us to deal with cuts and non-monotonic timeline edits.

There are two types of links between anchor segments: matches produced by the CTE alignment matches (m-links), and links we add to ensure that overlapping anchor segments in a same video are kept together (o-links). Contrary to the non-edited case, here we use the scores computed from the matching sub-sequences for the m-links, as defined in Section 3.5. For the o-links we use the overlap length as score, and since the o-links are more reliable than the m-links, we add a constant that ensures that they are at least as high as m-link scores.

On output, the algorithm provides one time offset t i per anchor segment. In the parts of the video where anchor segments overlap, we select the offset of the anchor segment with highest associated matching score, so that each video frame has a unique location in the global timeline.

Datasets for video retrieval and alignment

In this section, we present the datasets used to evaluate our methods for large-scale video retrieval and for temporal video alignment. First, we describe the CCWEB and TRECVID 2008 copy detection datasets for large-scale video retrieval. Then we introduce the Climbing and Madonna datasets to evaluate the precision of temporal video alignment. These two datasets are publicly available for download. Table 1 sums up statistical information on all the datasets used in our experimental evaluation.

Content-based copy detection

We evaluate large-scale video retrieval (i.e. copy detection) on two public benchmarks, the CCWEB dataset [START_REF] Wu | Practical elimination of near-duplicates from web video search[END_REF] and the TRECVID 2008 content based copy detection dataset (CCD) [START_REF] Smeaton | Evaluation campaigns and Trecvid[END_REF].

CCWEB contains 24 query videos, mostly focusing on near-duplicate detection. The transformed versions in the database correspond to user re-posts on video sharing sites. Large-scale performance is evaluated on CCWEB+100K obtained by adding 100,000 video distractors taken from the EVVE dataset [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. Performance is reported as the mean average precision (mAP) over all queries.

The 2008 campaign of the TRECVID CCD task is the last for which video-only results were evaluated. We present results on the camcording subtask, which is most relevant to our context of event retrieval in the presence of significant viewpoint changes. We report results with the official normalized detection cost rate (NDCR) measure. The NDCR is a weighted combination of the costs of false alarms and missed detections, so lower values are better.

Video alignment: Climbing and Madonna

We introduce two challenging datasets to evaluate our alignment method in realistic conditions. 1 Figure 5 shows example frames for videos of the two datasets.

Climbing. The dataset is composed of video clips shot during an outdoor climbing session. The climbers as well as the people filming were all members of our lab.

We used eleven different cameras of several types, including digital cameras, mobile phones, camcorders, headmounted wide-angle cameras. The people filming were instructed to record sequences from several locations with different zooms, and to take relatively short clips ranging from 5 seconds to 5 minutes. The raw video rushes from the cameras was used, i.e., each clip represents a single shot. At each moment, there was at least one camera recording.

The 89 videos were manually aligned to produce the ground-truth. The precision of this ground-truth alignment is reliable to at least 0.5 second. Since each clip represents a single shot, there is a single time shift to estimate between each pair of clips.

Furthermore, there is additional metadata associated with the clips: the source camera and the ordering of the clips given by the clip's filename. This information is useful because a camera cannot shoot two clips at a time, which could be used as a constraint on the alignment. Such constraints can be taken into account in the alignment algorithm in the form of linear inequality constraints. In the case where the relative times of the videos are known, it suffices to estimate a single starting time, and the videos can be considered as a single one for the purpose of temporal alignment. In our experiments we do not exploit this metadata, however, in order to simulate more challenging conditions.

From the ground-truth we can derive all pairs of videos that temporally overlap, and their respective temporal offsets. To evaluate an alignment, we count the number of pairwise overlaps in the ground-truth for which the correct temporal offset is recovered by our algorithm, within a tolerance of 0.5 s. This produces the pairwise alignment score (PAS). We compare this number of correct overlaps to the total number of overlaps in the ground-truth.

We always set the tolerance parameter τ of the alignment algorithm to the same value (of 0.5 s.) that is used in the evaluation. This is a natural choice, since setting the tolerance in the alignment algorithm larger (smaller) than the tolerance in the evaluation would lead to many false positive (negative) alignments. Madonna. This dataset is composed of videos from the Madonna in Rome event defined in the publicly available EVVE dataset [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF]. It shows one particular Madonna concert, that was filmed by dozens of people who posted their clips on YouTube, often after editing them. There is a lot of stage action with distinctive motion, and recognition is facilitated by a large video screen on the side of the stage playing along with the concert.

The videos are shot with low-quality devices such as mobile phones in difficult shooting conditions: shaking cameras, large distance from the scene, poor lighting and image quality.

Since the videos are edited, we annotated ground-truth segments on each video. A segment can cover shot boundaries, as long as the real time of the end of a shot coincides with the beginning of the next one. Then we annotated the ground-truth alignment on these ground-truth segments.

Evaluation for edited videos. As discussed in Subsection 5.2, the alignment is defined on anchor segments. Therefore, the Video 1 Video 2 Fig. 6 A match between ground-truth segments of two videos (combined red and green area), aligned horizontally. Anchor segments that are overlapping in the alignment output are indicated in gray and with arrows. The sub-segments of the ground-truth segment are counted as positive for the PAS evaluation are in green, the negative ones in red. estimated time shift is not uniform over the intersecting range of ground-truth segments: on the example of Figure 6, considering the segment of Video 1, one part of the range has no matching section at all on Video 2, another one has, but with an incorrect time shift, and the last match is aligned correctly. In this case, we extend the PAS score by computing only the fraction of the range that is aligned correctly, up to a tolerance of 0.5 s. The fractions are summed up for all pairs of overlapping ground-truth segments, producing a non-integer PAS.

Experimental results

In this section we evaluate our approach, both for video copy detection and alignment of multiple videos belonging to the same event. To compare the contributions of the frame descriptors and of the temporal matching, we introduce an additional descriptor obtained by averaging the per-frame descriptors of Section 3.1 over the entire video. This descriptor that no longer carries temporal information is compared using the dot product and denoted by Mean-MultiVLAD (MMV).

Video copy detection

This task is evaluated on the CCWEB dataset [START_REF] Wu | Practical elimination of near-duplicates from web video search[END_REF] and the TRECVID 2008 content based copy detection dataset (CCD) [START_REF] Smeaton | Evaluation campaigns and Trecvid[END_REF].

Compression parameters. The spatial and temporal compression is parametrized by the dimensionality d after PCA, the number p of PQ sub-quantizers and the frame description rate β, which defines the ratio between the number of method p β mAP memory search usage time CCWEB HIRACH [START_REF] Wu | Practical elimination of near-duplicates from web video search[END_REF] 0.952 --MFH [START_REF] Song | Multiple feature hashing for real-time large scale near-duplicate video retrieval[END_REF] 0.954 0. frequency vectors and the number of video frames. As a general observation across all datasets and experiments, we notice that higher values of d yield better performance, for all values of p. Yet d should be kept reasonably small to avoid increasing the storage for the dataset (the memory usage we report is the size of the compressed dataset in RAM). We thus fix the PCA output dimension to d = 512 in all our experiments and vary the number of sub-quantizers p and the rate β.

Impact of the regularization parameter. The choice of λ depends on the task and the evaluation metric. For nearduplicate video retrieval, Figure 7 shows that intermediate values of λ yield the best performance. In contrast, we observe that small values of λ produce the best NDCR performance for the TRECVID copy detection task. This is probably due to the fact that the NDCR measure strongly favors precision over recall, whereas any matching tolerance obtained by a larger λ also produces more false positives. In all our experiments, we set λ=0.1 for the near-duplicate detection task, and λ=0.001 for the TV08 benchmark.

Comparison with the state of the art. Tables 2 and3 report our results for near-duplicate and copy-detection for different compression trade-offs, and compares our results to the state of the art. Search times are given for one core and are averaged across queries. See Section 4 for details on the parameters p and β.

On CCWEB, both the temporal and non-temporal versions of our method outperform the state of the art for comparable memory footprints. The good results of MMV establishes the quality of the image descriptors. CTE compresses the vector sequence by a factor 1024 along the temporal axis and by a factor 128 in the visual axis, which amounts to storing 4 bits per second of video. The results for the large-scale version of the dataset are not strictly comparable with those of the original paper [START_REF] Song | Multiple feature hashing for real-time large scale near-duplicate video retrieval[END_REF] because the distractor videos are different (they do not provide theirs).

On the TRECVID 2008 dataset, our approach is significantly more accurate than that of Douze et al. [START_REF] Douze | Compact video description for copy detection with precise temporal alignment[END_REF], while being faster and using less than half the memory when using PQ compression. MMV cannot be realistically evaluated on this dataset because it can not output temporal boundaries for video matches. To compute its NDCR score, we disregard the boundaries, which are normally used to assess the correct localization of the matching segment within a video clip. Despite this advantage, MMV performs poorly (NDCR close to 1), due to the small overlap between queries and database videos (typically 1%), which dilutes the matching segment in the video descriptor.

The results of CTE depend on the length of the subsequence shared by the query and retrieved videos. On Trecvid 2008, pairs with subsequences shorter than 5s are found with 62% accuracy, subsequences 10s with 80% accuracy and longer subsequences with 93% accuracy.

Timings. Even for the largest dataset, CCWEB with 100k distractors, the bottleneck remains the MultiVlad descriptor extraction, which is performed approximately in realtime on one processor core (i.e. 1-2 minutes per query on TRECVID and CCWEB). Table 2 shows that the search itself takes 23 ms and 75 ms on average for MMV and CTE, respectively, which is orders of magnitude faster than other methods with comparable accuracies.

Pairwise temporal alignment

We first evaluate the precision of our pairwise alignment on relatively simple video sequences with a very precise ground-truth alignment. We chose the "Juggler" sequences from [START_REF] Ballan | Unstructured video-based rendering: Interactive exploration of casually captured videos[END_REF], that are recorded from six different camera viewpoints. They represent a dynamic event filmed in a street by several people, with slowly moving cameras and highresolution images. The main challenge is the large change in viewpoint between individual sequences. To simulate our use case, we resize and compress the videos to "YouTube" 360p format, reducing each file from 1 GB to 15 MB. As the original videos span the same time range, and hence do not need alignment, we extract 5 random sub-videos of 15, 30, 60 and 120 seconds from each video, and measure the alignment accuracy of these w.r.t. the other original videos. We measure the fraction of correctly aligned videos, with an alignment tolerance of 0.2 seconds.

Results in Figure 8 show that pure content-based temporal alignment is possible despite strong viewpoint changes and the use of a global frame descriptor. Longer extracts help the alignment, and there is little difference between the alignment performance with a tolerance of 0.2 s and 0.04 s. This shows that if the alignment is correct, it is usually accurate to the frame. Furthermore, the DTHOF descriptors perform much better than SIFT, producing perfect alignments for all sequences when they are longer than 30 s. This is expected as the dataset consists of a juggling performance for which motion is essentially discriminative.

We compare CTE with an alignment method based on the Hough Transform. Figure 8 show that this results in about the same precision as with CTE. Nevertheless, it is much slower: aligning the 20 Juggler videos takes 745 s with Hough transform instead of 48 s for CTE.

To evaluate the impact of our local descriptor aggregation strategy, we tried to replace the MultiVlad frame descriptor with bag of words (BOW) aggregation. We used 1000 words, to match the MultiVlad descriptor size. similarly to an observation of [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF], the performance of BOW encoding is low. This demonstrates that having a frame descriptor both invariant and discriminative is crucial.

Global alignment

In the following, we evaluate our pairwise and global matching methods on the Climbing and Madonna datasets. Since the datasets are small, it is possible to use high-quality settings to compute the pairwise video matches: 1024-dimensional frame descriptors, no PQ compression and β = 1/4. We also set λ = 10 -2 , since it is closest to a copy detection task. Table 4 presents the results of the alignment evaluation on the Climbing and Madonna datasets.

The first three rows show the number of input anchors and matches produced by pairwise CTE matching, as well as the number of matches that are consistent with the groundtruth. For the Madonna dataset, we separate the number of regular matches (m-links) and the anchor overlaps (o-links), see Section 5.2. We observe that the pairwise matching is much harder for the Climbing than for the Madonna dataset. For Madonna, about 90 % of the overlap links are correct (incorrect ones are due to undetected shot boundaries), while about 25% of the between-video matches are correct, depending on the input descriptor. The reason for this discrepancy is that for Madonna there are more distinctive visual features, especially due to the large screen display on the back of the stage that shows fast moving videos. For Climbing there are more repeated features of rock and foliage textures, larger baseline between viewpoints and limited action, see Figure 5. Rows four and five show the number of consistent matches in C that was retained to produce the alignment, and the number of retained matches consistent with the ground-truth. For Climbing, only about 100 matches are retained, which contain 50 (of the 54 or 55) matches that are consistent with the ground-truth. For Madonna, all overlap links are retained and about 1800 real matches, 60 % of these correct.

Finally, the last two rows show the pair wise alignment score (PAS) obtained for the ground-truth, and using the produced alignment. For Madonna the alignment obtains a PAS of 54% relative to the ground-truth, while for Climbing this is only 23%. This is in-line with the much higher fraction of correct retained matches for the Madonna dataset.

The results with the DTHOF descriptor are significantly lower. A possible explanation is that, compared to the Juggler dataset, the matching must not only distinguish subtle motions (for which DTHOF performs well), but also identify different environments and background patterns (where SIFT is more appropriate). It is possible to combine both descriptors by concatenating them frame per frame. Since the descriptors are normalized, concatenating them produces a vector of norm 2, that can be indexed with CTE. The combination SIFT+ DTHOF significantly improves the PAS, which shows that they are complementary.

User evaluation of video alignment

We also performed a user study to evaluate the quality of our video alignment. For this evaluation we developed a tool, ALIGNGUI 2 , which allows to interactively align videos. The user manipulates anchor segments (potentially matching subsequences detected by the algorithm) extracted from several videos. In the interface, each video is displayed on a single line, and the anchor segments as a horizontal strip of frames, see Figure 9. Different from standard video editing tools, ALIGNGUI can display several videos simultaneously, and plays them synchronized with the current alignment hypothesis. Table 5 Timing of three users (A,B, and C), performing manual or interactive video alignment.

Anchor segments can be aligned manually or interactively. In the manual mode, the user drags anchor segments on the timeline until they are aligned. In the interactive mode, the user selects an anchor segment, and ALIGNGUI uses the matching method of Section 3 to generate a list of alignment hypotheses for the other anchor segments. The user then cycles through the hypotheses until the correct alignment is found.

Given four videos of the Climbing data, we evaluate how long it takes a user to align them with 48 already aligned clips. We compare two operating modes. In the manual mode, comparable to the workflow of conventional video editing tools, the user performs all alignments by hand. In the interactive mode the system suggests alignments to the user based on the pairwise matches, starting from the most confident one. The user then cycles between the different propositions, and validates the one that seems correct to him. Three users participated in this study: A is very familiar with both the data and software, B is less trained with the software but also knows the video collection, and C was not familiar with either. The results are given in Table 5.

We observe that a manual alignment is at least ten times slower than an interactive one, and even slower if the editor is not familiar with the software or the video collection. In both modes, the user has to play the videos synchronously to confirm each considered alignment. In the manual mode, however, the user must additionally first determine sub-sequences to match from a given video, search for potentially matching videos, and determine a pairwise temporal alignment. For user C that is unfamiliar with the video collection, the manual alignment becomes prohibitively slow.

Conclusion

The circulant temporal encoding technique proposed in this paper exploits the efficiency of Fourier domain processing to circumvent the usual frame-to-frame matching employed by most video matching techniques. This offers a very significant increase in efficiency, which is further magnified by the variant of product quantization that we introduce for complex-valued vectors. As a result, the matching time itself is faster than the query video duration by a factor 10 to 1000 (depending on the required matching accuracy), even for a collection of hundred thousands video clips. The bottleneck remains the (real-time) extraction of the frame descriptors associated with the video query, which suggests that our method is scalable to even larger video collections, thanks to the low memory footprint of our compressed descriptors.

Our approach is shown effective in the traditional copy detection scenario as well as in a more challenging case, when the same event is filmed from different viewpoints. Additionally, our approach produces an estimate of the relative time difference between two videos. Another contribution is our algorithm that exploits this information to align a set of matched videos on a global timeline. This allows us, in particular, to produce a synchronous playback of videos associated with a given event.

To evaluate a global temporal alignment, we introduced the Climbing and Madonna datasets, for which we provide ground-truth temporal alignments annotated manually, and the frame descriptors that can be used to evaluate the alignment algorithm separately. These datasets are challenging, as the videos are self-similar on both short and long time scales. This corresponds to a realistic video-editing scenario.

Fig. 1

 1 Fig.1Matrices of frame matching scores for pairs of videos to align. Each matrix element is the matching score between a query frame (line) and a database frame (column). Darker entries correspond to higher scores. Left: sequences with non-constant time shift (we do not consider this case); middle: constant time shift, strong signal; right: constant time shift, weak signal (the focus of this paper).

  Raw self-matching score s(q, q) (zero-padded query).

  Regularized matching score s λ (q, b).

Fig. 2

 2 Fig.2Matching score between a query q and a database video b as a function of the time shift δ.

Fig. 3

 3 Fig.3Illustration of the alignment process of multiple videos: some pairwise matches are removed to allow for a consistent global alignment.

Fig. 4

 4 Fig. 4 Precision-recall plot of the video anchor matches found by CTE, for SIFT descriptors of the Climbing and Madonna datasets. See Section 6 for details on the datasets.

Fig. 5

 5 Fig. 5 Examples of correctly aligned clips of the Madonna (top) and Climbing (bottom) datasets. Each row is a different video, and each column corresponds to temporally aligned frames (2 frames per second are represented).

Fig. 7

 7 Fig. 7 Impact of the regularization parameter λ on the performance.

Fig. 8

 8 Fig.8Fraction of correctly aligned video pairs from the "Juggler" sequence. The default alignment tolerance is 0.2 seconds, and the default CTE setting uses SIFT descriptors with MultiVlad encoding.

Fig. 9

 9 Fig. 9 ALIGNGUI interface showing two aligned clips selected by the user in red, and playing them synchronously for verification. The horizontal widget on top shows an overview of all aligned clips.

  The query frame descriptors are mapped to the frequency domain by d 1D FFTs of size n. 2. O(256 × d × n ) -The PQ table T associated with the regularized query

Table 1

 1 Statistics on the different datasets used in this paper.

			(a) Retrieval datasets
	dataset		query		database
			videos	videos	hours frames
	CCWEB		24	13129	551	29.7M
	CCWEB + 100k	24	113129	5921	320M
	TRECVID CCD 08	2010	438	208	11.2M
		(b) Alignment datasets
	dataset	# videos # g.t. segments # groups	length
	Juggler	6	N/A		1	14m18s
	Climbing	89	N/A		1	6h21m
	Madonna	163	230		29	10h12m

Table 2

 2 Results for video copy detection on the CCWEB dataset in mAP (higher is better).

	5 MB	-

Table 3

 3 Results for video copy detection on the TRECVID dataset in terms of NDCR (lower is better).

Table 4

 4 Alignment evaluation on the Climbing and Madonna datasets. The five first lines report statistics about the anchors (video fragments) input to the alignment algorithm, and their matches. The resulting Pairwise Alignment Score (PAS) is at the bottom of the table.

			Climbing			Madonna
		SIFT	DTHOF SIFT + DTHOF	SIFT	DTHOF	SIFT+DTHOF
	# input anchors		89		11120	10906	10758
	# input matches	788	842	713	83691 (o) + 5726 (m) 95629 (o) + 5695 (m) 86104 (o) + 5593 (m)
	# correct input matches	55	54	71	73263 (o) + 1495 (m) 86379 (o) + 1414 (m) 76274 (o) + 1518 (m)
	# matches retained	104	115	117	83691 (o) + 1711 (m) 95629 (o) + 1923 (m) 86104 (o) + 1922 (m)
	# correct matches retained	50	50	63	73263 (o) + 1142 (m) 86379 (o) + 1202 (m) 76274 (o) + 1245 (m)
	PAS for ground-truth		470			1153
	PAS for alignment	109.8	80.7	132.4	632.2	518.0	656.3

They are available at http://pascal.inrialpes.fr/ data/evve/index_align.html.

Publicly available at http://pascal.inrialpes.fr/ data/evve/index_align.html.

Acknowledgements

We are grateful to the team members who participated as cameramen or actors in the shooting of the Climbing dataset. This work was supported by the European integrated project AXES, the MSR/INRIA joint project and the ERC advanced grant ALLEGRO.


Thế Nguyễn

Cường

Homogeneous strict polynomial functors as unstable modules

Keywords: Steenrod algebra, strict polynomial functors, unstable modules

 where to each strict polynomial functor the author naturally associates an unstable module. We show that the restriction of Hai's functor to a sub-category of strict polynomial functors of a given degree is fully faithful.

Introduction

The search for a relation between Schur algebras and the Steenrod algebra has been a source of common interest between representation theorists and algebraic topologists for over thirty years. Functorial points of view, on unstable modules [START_REF] Henn | The categories of unstable modules and unstable algebras over the Steenrod algebra modulo nilpotent objects[END_REF], and on modules over Schur algebras [START_REF] Friedlander | Cohomology of finite group schemes over a field[END_REF], have given an efficient setting for studying such relation. For the Steenrod algebra side, [START_REF] Henn | The categories of unstable modules and unstable algebras over the Steenrod algebra modulo nilpotent objects[END_REF] uses Lannes' theory to construct a functor f , from the category U of unstable modules, to the category F of functors from finite dimensional F p -vector spaces to F p -vector spaces. This functor f induces an equivalence between the quotient category U /Nil of U by the Serre class of nilpotent modules, and the full sub-category F ω of analytic functors. The interpretation of modules over Schur algebras given by [START_REF] Friedlander | Cohomology of finite group schemes over a field[END_REF] uses an algebraic version of the category of functors, the category P of strict polynomial functors. The category P decomposes as a direct sum d≥0 P d of its sub-categories of homogeneous functors of degree d. The category P d is equivalent to the category of modules over the Schur algebra S(n, d) for n ≥ d [FS97, Theorem 3.2]. The presentation of P d as a category of functors with an extra structure comes with a functor P d → F. Nguyen D. H. Hai showed [START_REF] Dang | Foncteurs polynomiaux stricts et modules instables sur l'algèbre de Steenrod[END_REF] that this functor P d → F factors through the category U by a functor md : P d → U . These functors md induce a functor m : P → U . The functor m has remarkably interesting properties. In particular, it is exact and it commutes with tensor products and with the Frobenius twist. The relevance of this last property to computation will soon be apparent.

We observe that Hom-groups between unstable modules coming from strict polynomial functors via Hai's functor are computable: they are isomorphic to the Hom-groups of the corresponding strict polynomial functors in many interesting cases. The primary goal of this paper is to generalize these results to the whole category P d . The main theorem of the present work goes as follows:

Theorem 1.1. The functor md :

P d → U is fully faithful.
The theorem is proved by comparing corresponding Hom-groups in the two categories. We discuss an example of interest. Let n be a non-negative integer and V be an F 2 -vector space. The symmetric group S n acts on V ⊗n by permutations. Denote by Γ n (V ) the group of invariants (V ⊗n )

Sn and by S n the group of co-invariants (V ⊗n ) Sn . Fix p = 2, let A 2 be the Steenrod algebra. The free unstable module generated by an element u of degree 1 is denoted by F (1). It has an F 2 -basis consisting of u 2 k with k ≥ 0. Denote by Sq 0 the operation, which associates to a homogeneous element x ∈ M n of M ∈ U , the element Sq n x. An unstable module M is nilpotent if for every x ∈ M n there exist an integer N x such that Sq Nx 0 x = 0. An unstable module M is reduced if Hom U (N, M ) is trivial for every nilpotent module N . It is called Nil-closed if Ext i U (N, M ) , i = 0, 1, are trivial for every nilpotent module N . Let G be Γ 2 ⊗ Γ1 or S 3 . To G, Hai's functor m associates the unstable module G(F (1)). We now show that

Hom P3 Γ 2 ⊗ Γ 1 , S 3 ∼ = Hom U Γ 2 (F (1)) ⊗ Γ 1 (F (1)), S 3 (F (1)) .
The readers of [START_REF] Henn | The categories of unstable modules and unstable algebras over the Steenrod algebra modulo nilpotent objects[END_REF] might expect the latter Hom-group to be isomorphic to Hom F Γ 2 ⊗ Γ 1 , S 3 . However S 3 (F (1)) is not Nil-closed 1 then such an expectation fails. By classical functor techniques [FFSS99, Theorem 1.7], if C is P or F then:

Hom C Γ 2 ⊗ Γ 1 , S 3 ∼ = 3 i=0 Hom C Γ 2 , S i ⊗ Hom C Γ 1 , S 3-i .
It follows that:

Hom F Γ 2 ⊗ Γ 1 , S 3 ∼ = F ⊕2 2 , Hom P3 Γ 2 ⊗ Γ 1 , S 3 ∼ = F 2 .
The module S 3 (F (1)) is not Nil-closed but it is reduced. On the other hand, the quotient of the module Γ 2 (F (1)) ⊗ Γ 1 (F (1)) by its sub-module generated by u ⊗ u ⊗ u 4 is nilpotent. Therefore:

Hom U Γ 2 (F (1)) ⊗ Γ 1 (F (1)), S 3 (F (1)) ∼ = Hom U A 2 u ⊗ u ⊗ u 4 , S 3 (F (1)) ∼ = F 2 .
This example is the key to the proof of Theorem 1.1. We end the introduction by giving some further remarks on the result and stating the organization of the paper.

Theorem 1.1 implies that the category P d is a full sub-category of the category U . Unfortunately the category P itself cannot be embedded into U . Fix p = 2, let F (2) be the free unstable module satisfying Hom U (F (2), M ) ∼ = M 2 , then there is no non-trivial morphism in the category P from Γ 2 to Γ 1 but:

Hom U m Γ 2 , m Γ 1 ∼ = Hom U (F (2), F (1)) ∼ = F 2 .
The category P d is not a thick sub-category of U . Fix p = 2, let I (1) denote the Frobenius twist in P 2 , that is the base change along the Frobenius. It is proved [START_REF] Friedlander | Cohomology of finite group schemes over a field[END_REF] that

Ext i P2 I (1) , I (1) ∼ = F 2 if i = 0, 2, 0 otherwise.
The corresponding Ext-group in the category U is Ext i U (ΦF (1), ΦF (1)). As in [START_REF] Nguyen The | Some homological algebra computations in the category of unstable modules[END_REF]:

Ext i U (ΦF (1), ΦF (1)) ∼ = F 2 if i = 2 n -2, 0 otherwise.
Therefore, Ext i P2 I (1) , I (1) is not isomorphic to Ext i U md I (1) , md I (1) for i = 2 n -2, n ≥ 3.

Organization of the article

In Section 2 we recall basic facts on the even Steenrod algebra and unstable modules following the presentation in [START_REF] Dang | Foncteurs polynomiaux stricts et modules instables sur l'algèbre de Steenrod[END_REF]. When p > 2, this so-called Steenrod algebra is slightly different from that of [START_REF] Steenrod | Cohomology operations[END_REF] since we do not consider the Bockstein operation. We also recall Milnor's co-action on unstable modules and how it is used to determine the Steenrod action on certain type of elements.

The next section recalls strict polynomial functors. Main properties of Hai's functor are introduced and an easy observation on the existence of its adjoint functors is also given.

The structure of Γ λ (F (1)

) := Γ n1 (F (1)) ⊗ Γ n2 (F (1)) ⊗ • • • ⊗ Γ n k (F (1)
) is treated in Section 4. We show that there exists a monogeneous sub-module of Γ λ (F (1)) such that the quotient of Γ λ (F (1)) by this sub-module is nilpotent.

The last section deals with Theorem 1.1. The proof of this theorem is based on a combinatorial process followed by some Steenrod algebra techniques.

The even Steenrod algebra and unstable modules

In this section, we follow the simple presentation in [Hai10, Section 3] to define the even Steenrod algebra and unstable modules.

The letter p denotes a prime number. Let [-] be the integral part of a number. We denote by A the quotient of the free associative unital graded F p -algebra generated by the P k , k ≥ 0, of degree k(p -1) subject to the Adem relations

P i P j = [ i p ] t=0 (p -1)(j -t) -1 i -pt P i+j-t P t
for every i ≤ pj and P 0 = 1 [Hai10, Section 3]. An A -module M is called unstable if for every homogeneous element x ∈ M n , P k x is trivial as soon as k is strictly greater than n. We denote by U the category of unstable modules.

Let A p be the Steenrod algebra [START_REF] Steenrod | Cohomology operations[END_REF][START_REF] Schwartz | Unstable modules over the Steenrod algebra and Sullivan's fixed point set conjecture[END_REF]. If p = 2 then there is an isomorphism of algebras A → A 2 , obtained by identifying the P k with the Steenrod squares Sq k . The category U is equivalent to the category U of unstable modules in [START_REF] Schwartz | Unstable modules over the Steenrod algebra and Sullivan's fixed point set conjecture[END_REF]. If p > 2, A is isomorphic, up to a grading scale, to the sub-algebra of A p generated by the reduced Steenrod powers P k , k ≥ 0, of degree 2k(p-1). The category U is equivalent to the sub-category U of unstable A p -modules concentrating in even degrees [Sch94, Section 1.6].

We call A the even Steenrod algebra and P k the k-th reduced Steenrod power. Serre and Cartan [START_REF] Serre | Cohomologie modulo 2 des complexes d'Eilenberg-MacLane[END_REF][START_REF] Cartan | Sur l'itération des opérations de Steenrod[END_REF] introduced the notions of admissible and excess. A monomial

P i1 P i2 . . . P i k is called admissible if i j ≥ pi j+1 for every k -1 ≥ j ≥ 1 and i k ≥ 1.
The excess of this operation, denoted by e P i1 P i2 . . . P i k , is defined by e P i1 P i2 . . .

P i k = pi 1 -(p -1)   k j=1 i j   .
The set of admissible monomials and P 0 is an additive basis of A .

Let | -| be the degree of a homogeneous element. Denote by P 0 the operation, which associates to a homogeneous element x ∈ M n of M ∈ U , the element P |x| x. An unstable module M is nilpotent if for every x ∈ M n there exist an integer N x such that P Nx 0 x = 0. Denote by Nil the class of all nilpotent modules.

An unstable module M is reduced if Hom U (N, M ) is trivial for every nilpotent module N . It is called Nil-closed if Ext i U (N, M ) , i = 0, 1, are trivial for every nilpotent module N . Let n be a non-negative integer. We denote by F (n) the free unstable module generated by a generator ı n of degree n. These F (n) are projective satisfying Hom U (F (n), M ) ∼ = M n . When n = 1 such a generator is denoted by u rather than ı 1 . As an F p -vector space, F (1) is generated by u p i , i ≥ 0. The action of the reduced Steenrod power P k , k ≥ 0 is defined by:

P k u p i =      u p i if k = 0, u p i+1 if k = p i , 0 otherwise.
In our setting, there is an isomorphism of unstable modules F (n) ∼ = (F (1) ⊗n ) Sn where the symmetric group S n acts by permutations. Then we can identify F (n) with the sub-module of F (1) ⊗n generated by u ⊗n [LZ86, Sch94, Section 1.6].

Milnor [START_REF] Milnor | The Steenrod algebra and its dual[END_REF] established that A has a natural co-product which makes it into a Hopf algebra and incorporates Thom's involution as the conjugation. The dual A * of A is isomorphic to the polynomial algebra

F p [ξ 0 , ξ 1 , . . . , ξ k , . . .], |ξ i | = p i -1, ξ 0 = 1.
Let R = (r 1 , r 2 , . . . , r k , . . .) be a sequence of non-negative integers with only finitely many non-trivial ones. Denote by ξ R the product ξ r1 1 ξ r2 2 . . . ξ r k k . . .. These monomials form a basis for A * .

Definition 2.1 (Milnor's operations). Let M n r ∈ A denote the dual of ξ n r with respect to the monomial basis ξ R of A * .

If M is an unstable module, the completed tensor product M ˆ A * is the F p -graded vector space defined by:

M ˆ A * n = l-k=n M l ⊗ (A * ) k .
We recall how to use Milnor's co-action to determine the Steenrod action. There is Milnor's co-action λ : M → M ˆ A * for an unstable module M . We write λ(x) as a formal sum R x R ⊗ ξ R . Let θ be a Steenrod operation then

θx = R ξ R (θ)x R .
Milnor's co-action on a tensor product is determined as follows:

λ(x ⊗ y) = R I+J=R (x I ⊗ y J ) ⊗ ξ R .
Milnor's co-action on F (1) is defined by:

λ(u) = i≥0 u p i ⊗ ξ i , λ(u p s ) = i≥0 u p s+i ⊗ ξ p s i .
The following observation on the action of Milnor's operations is easy and is left to the reader.

Lemma 2.2. Let n be a non-negative integer then M n r (u ⊗n ) = u p r ⊗n . Let l 1 , . . . , l q be a sequence of non-negative integers. If k 1 , . . . , k m is a sequence of non-negative integers such that p kj > n for every m ≥ j ≥ 1 then:

M n r q i=1 u p l i ⊗ m i=1 u p k i = M n r q i=1 u p l i ⊗ m i=1 u p k i .
The following proposition is a strengthening of Lemma 2.2:

Proposition 2.3. Let M and N be two connected unstable modules. For all homogeneous element x ∈ M of degree n then M n r (x) = P r 0 (x). For all homogeneous elements y ∈ M and z ∈ N and all non-negative integer k such that p k > n, then:

M n r y ⊗ P k 0 (z) = M n r (y) ⊗ P k 0 (z).
Proof. Consider the morphism ϕ : F (n) → M , defined by ϕ (u ⊗n ) = x. Lemma 2.2 yields:

M n r (x) = M n r ϕ u ⊗n = ϕ M n r u ⊗n = ϕ P r 0 u ⊗n = P r 0 ϕ u ⊗n = P r 0 (x).
Let ψ : F (|y|) → M be the morphism defined by ψ u ⊗|y| = y. Similarly, by considering the morphism

ψ 1 : Φ k (F (|z|)) → N , defined by ψ P p k ı |z| = P p k z,
together with the product ψ ⊗ ψ 1 , we obtain the second equality.

Strict polynomial functors and Hai's functor

The main goal of this section is to recall Hai's functor and give an easy observation on the existence of its adjoint functors.

Following the simple presentation introduced in [Pir03], we first recall the category of strict polynomial functors. Fix a prime number p, denote by V the category of F p -vector spaces and by V f its full subcategory of spaces of finite dimension. Let n be a non-negative integer. Denote by Γ n (V ) the group of invariants (V ⊗n )

Sn . The category Γ d V f is defined by:

Ob Γ d V f = Ob V f , Hom Γ d V f (V, W ) = Γ d (Hom V f (V, W )).
A homogeneous strict polynomial functor of degree d is an F p -linear functor from Γ d V f to V f . We denote by P d the category of all these functors. The notation P stands for the direct sum d≥0 P d . A strict polynomial functor is an object of the category P.

We now recall the parameterized version of Γ d and S d . For each W ∈ V f , let Γ d,W be the functor which associates to an F p -vector space V the F p -vector space Γ d (Hom V f (W, V )), and let S d,W be the functor which associates to an F p -vector space V the F p -vector space S d (W ⊗ V ). Here, W stands for the linear dual of W . The Γ d,W are projective satisfying Hom

P d Γ d,W , F ∼ = F (W ) and the S d,W are injective satisfying Hom P d F, S d,W ∼ = F (W ) .
Let F denote the category of functors from finite dimensional F p -vector spaces to F p -vector spaces. Hai shows [START_REF] Dang | Foncteurs polynomiaux stricts et modules instables sur l'algèbre de Steenrod[END_REF] The following observation is easy and is left to the reader: [START_REF] Dang | Foncteurs polynomiaux stricts et modules instables sur l'algèbre de Steenrod[END_REF]). The functor md admits a left adjoint and a right adjoint.

Proposition 3.2 ([

The key lemma

As explained in the introduction, we prove Theorem 1.1 by comparing corresponding Hom-groups in the two categories P d and U . This computation can be reduced to a smaller class of strict polynomial functors. This class is described in the following proposition. Before formulating this proposition, we fix: Notation 4.1. Let λ = (λ 1 , . . . , λ k ) be a sequence of non-negative integers. We denote:

Γ λ := Γ λ1 ⊗ • • • ⊗ Γ λ k . Proposition 4.2 ([FS97]). If dim Fp W ≥ d then S d,W
is an injective generator of P d . The functors Γ λ , where λ runs through the set of all sequences of non-negative integers whose sum is d, form a system of projective generators of P d .

By abuse of notation, we denote by | -| the sum of a sequence of integers. Theorem 1.1 is equivalent to the following lemma.

Lemma 4.3. There are isomorphisms:

Hom U Γ λ (F (1)), S d,V (F (1)) ∼ = S λ1 (V ) ⊗ • • • ⊗ S λ k (V ) for every λ = (λ 1 , λ 2 , . . . , λ k ), |λ| = d.
In this section we show that there exists a monogeneous sub-module of Γ λ (F (1)) such that the quotient Γ λ (F (1)) by this module is nilpotent. The following lemma is a consequence of [Lan92, Lemma 2.2.5.3],[FS90, Lemma 1.2.6].

Lemma 4.4. Let M be a connected monogeneous unstable module. If n, q are non-negative integers such that p q > n then F (n) ⊗ Φ q M is monogeneous.

By a simple induction, we obtain the following lemma: Lemma 4.5. Let λ be a sequence (λ 1 , λ 2 , . . . , λ k ) of non-negative integers. If the numbers q 1 , q 2 , . . . , q k-1 satisfy p qi > λ i for all 1 ≤ i ≤ k -1, then

F (λ 1 ) ⊗ Φ q1 F (λ 2 ) ⊗ Φ q1+q2 F (λ 3 ) ⊗ • • • ⊗ Φ q1+q2+•••+q k-1 F (λ k ) is monogeneous.
Denote by Q the sequence (0, q 1 , q 1 + q 2 , . . . , q 1 + • • • + q k-1 ) and by ω λ,Q the element

ı λ1 ⊗ P q1 0 ı λ2 ⊗ P q1+q2 0 ı λ3 ⊗ • • • ⊗ P q1+q2+•••+q k-1 0 ı λ k .
Because M/Φ n M, n ≥ 1, is nilpotent for every unstable module M , an elementary induction yields:

Corollary 4.6. Let λ be a sequence (λ 1 , λ 2 , . . . , λ k ) of non-negative integers. If the numbers q 1 , q 2 , . . . , q k-1 satisfy p qi > λ i for all

1 ≤ i ≤ k -1, then the quotient Γ λ (F (1))/A (ω λ,Q ) is nilpotent. Because S d,V (F (1)) is reduced, hence Hom U Γ λ (F (1))/A (ω λ,Q ), S d,V (F (1)
) is trivial and then:

Proposition 4.7. The inclusion A (ω λ,Q ) → Γ λ (F (1)) induces an injection:

Hom U Γ λ (F (1)), S d,V (F (1)) → Hom U A (ω λ,Q ), S d,V (F (1)) .
We are thus led to the problem of determining the subspace of S d,V (F (1)) consisting of all possible images of ω λ,Q . Lemma 4.8 presents the desired determination. Before formulating this lemma, let us present an example of interest. There is an isomorphism of F p -vector spaces:

Hom U F (d), S d,V (F (1)) ∼ = S d,V (F (1)) d ∼ = S d V .
Therefore if ϕ is a morphism from F (d) to S d,V (F (1)) then the image ϕ(ı d ) is a sum of elements of the type Hom U F (λ j ), S λj ,V (F (1)) → Hom U F (λ), S d,V (F (1)) .

For 1

≤ i ≤ k, let f i be a morphism from F (λ i ) to S λi,V (F (1)). Then the image of ω λ,Q under ρ k i=1 f i is a sum of elements of the type k j=1   λj i=1 s i,j ⊗ u p q 1 +q 2 +•••+q j-1  
with s i,j ∈ V . We show that every morphism in Hom U F (λ), S d,V (F (1)) is of this simple form. Lemma 4.8. Let λ = (λ 1 , . . . , λ k ) be a sequence of non-negative integers whose sum is d. Let m be a number such that p m > d 2 . Denote by α the sequence (0, m, 2m, . . . , (k -1)m) and by ω α the element ω λ,α . If ϕ is a morphism from F (λ) to S d,V (F (1)) then ϕ(ω α ) is a sum of elements of the type

k-1 t=0   λt+1 i=1 v i,t ⊗ u p tm   where v i,t ∈ V .
Remark 4.9. Lemma 4.3 is a corollary of Lemma 4.8. Indeed since

k j=1 Hom U F (λ j ), S λj (V ⊗ F (1)) ∼ = k j=1 S λj (V ),
it suffices to check that the morphism ρ is a bijection. The morphism ρ is clearly injective. Following Lemma 4.8, the morphism ρ is surjective as well and hence it is bijective. Lemma 4.3 have been proved and we are left with Lemma 4.8.

Proof of the key lemma

As discussed in the previous section, we are left with Lemma 4.8. The proof of this lemma now goes as follows.

Proof of Lemma 4.8. The image of ω α is a sum of elements of the type

d i=1 v i ⊗ u p l i in S d (V ⊗ F (1)).
Therefore, the following equality holds:

k-1 i=0 p im λ i+1 = d j=1 p lj .
(5.1)

We now show that in d i=1 v i ⊗ u p l i , the element u p jm , 0 ≤ j ≤ k -1, appears λ j+1 times. Without loss of generality, we suppose that l 1 ≤ l 2 ≤ . . . ≤ l d . We prove by induction on 1 ≤ i ≤ k that there exist j 1 , j 2 , . . . j k such that for 0 ≤ i ≤ k -1,

p lj i+1 ≤ λ i+1 p im < p l1+j i+1 , im ≤ l t , 1 + j i ≤ t ≤ j i+1 , λ i+1 = ji+1 s=1+ji p ls-im .
(5.2)

Let j 1 be the index such that p lj 1 ≤ λ 1 < p l1+j 1 . Denote by S the set {l 1 , l 2 , . . . , l j1 } and by p S the sum i∈S p i . We show that p S = λ 1 .

Since both sides of (5.1) and λ 1 are congruent modulo p l1+j 1 , it is enough to prove that p S ≤ λ 1 . Suppose that this inequality does not hold. Then

λ 1 < p S ≤ λ 1 j 1 ≤ d 2 < p m .
Denote by r the sum d i=1 p li . It follows from Proposition 2.3 that:

M p S r (ω α ) = M p S r u ⊗λ1 ⊗ k-1 i=1 u p im ⊗λi+1 = 0.
On the other hand, we prove that the action of M p S r on the image of ω α is not trivial. In fact, the element

x := M p S r d i=1 v i ⊗ u p l i
is a sum of elements of the type

d i=1 v i ⊗ u p l i +r i
where ( 1 , 2 , . . . , d ) is a sequence of 0 and 1 such that

then v i ⊗ u p l i , 1 ≤ i ≤ d = w j ⊗ u p k j , 1 ≤ j ≤ d .
Therefore the action of M p S r on the image of ω α is non-trivial in this case. This contradiction implies:

j1 i=1 p li = λ 1
Suppose that there are j 1 , j 2 , . . . j t such that for 0 ≤ i ≤ t -1, = P tm 0 ω ((k-t)m,...,(k-1)m,0,m,...,(k-t-1)m) , (5.3)

p lj i+1 ≤ λ i+1 p im < p l1+j i+1 , im ≤ l n , 1 + j i ≤ n ≤ j i+1 , λ i+1 =
M λ1+p m λ2+•••+p (t-1)m λt km d i=1 v i ⊗ u p l i = P km 0 jt i=1 v i ⊗ u p l i • d i=1+jt v i ⊗ u p l i .
Because every morphism in Hom U F (λ), S d,V (F (1)) is A -linear, it follows from (5.3) that l i ≥ tm for all i ≥ 1 + j t . As S d,V (F (1)) is reduced, the image of ω ((k-t)m,...,(k-1)m,0,m,...,(k-t1)m) is a sum of

P (k-t)m 0 jt i=1 v i ⊗ u p l i • d i=1+jt v i ⊗ u p l i -tm
with other elements. By the same manner for the case of λ 1 , there exist j t+1 such that p lj t+1 ≤ λ t+1 p tm < p l1+j t+1 , λ t+1 = jt+1 s=1+jt p ls-tm .

The induction is then achieved. The lemma is now deduced from the equalities k i=1 λ i = d and (5.2).

  that the forgetful functor O : P d → F factors through U via a certain functor md : P d → U . Let m denote the induced functor from P to U . The functor m has nice properties. It is exact and it commutes with tensor products and with Frobenius twists [Hai10, see Sections 3 and 4]. Moreover: Proposition 3.1. We have md (Γ d ) = F (d).

d

  i=1 s i ⊗ u where s i ∈ V . The natural transformation k j=1 S λj ,V → S d,V , k j=1 λ j = d, induces a morphism ρ : k j=1

vv i ⊗ u p l i +r i = d i=1 w

 i=1 i ⊗ u p l i   is unique hence x is non-trivial. Suppose that there exist k 1 ≤ k 2 ≤ . . . ≤ k d such that i ⊗ u p k i +rτ i ,where (τ 1 , τ 2 , . . . , τ d ) is a sequence of 0 and 1 such thatd i=1 τ i p ki = j1 i=1 p li . Since r > max {l i , k i , 1 ≤ i ≤ d} ,

p

  ls-im .It follows from Proposition 2.3 thatM λ1+p m λ2+•••+p (t-1)m λt km ω (0,m,2m,...,(k-1)m) = ω (km,(k+1)m,...,(k+t-1)m,tm,(t+1)m...,(k-1)m)

The sub-module of S 3 (F (1)) generated by u.u.u 4 is concentrated in even degrees but this element does not has a square root.

thank NGUYEN Dang Ho Hai and PHAM Van Tuan for having offered many significative discussions. This work would not be presented properly without precious suggestions from Vincent Franjou.

† Partially supported by the program ARCUS Vietnam MAE, Région IDF.