Pr Martial

Rapporteur Pr Patrick Pérez

Dr Ivan Laptev

Dr Zaid Harchaoui

Pr Cordelia Schmid

Andrew Zisserman

Patrick Pérez

Jean Ponce

Andrew Blake

Jakob Verbeek

Matthijs Douze

Hervé Jé- Gou

Rémi Ronfard

Matthieu Cinbis

Hedi Guillaumin

Alexander Harzallah

Kläser

Dr Matt Destruction

Diane Larlus

Jörg Liebelt

Thomas Mensink

Alessandro Prest

The Kläsers' Very Own

Nicko Mcbrain

Arnau Ramisa

Gaurav Sharma

Heng Wang

Keywords: Action Recognition, Video Analysis, Computer Vision, Machine Learning. v Reconnaissance d'Actions, Analyse Vidéo, Vision par Ordinateur, Apprentissage Statistique

This dissertation introduces novel models to recognize broad action categories like "opening a door" and "running" in real-world video data such as movies and internet videos. In particular, we investigate how an action can be decomposed, what is its discriminative structure, and how to use this information to accurately represent video content. The main challenge we address lies in how to build models of actions that are simultaneously information-rich in order to correctly dierentiate between dierent action categories and robust to the large variations in actors, actions, and videos present in realworld data. We design three robust models capturing both the content of and the relations between action parts. Our approach consists in organizing collections of robust local features into structured action representations, for which we propose ecient kernels. Even if they share the same underlying principles, our methods dier in terms of the type of problem they address and the structural information they rely on. First, we propose to model a simple action as a sequence of meaningful atomic temporal parts, termed "actoms", which are obtained by manual annotation. Our action model represents the temporal structure of actions as a sequence of histograms of actom-anchored visual features. We show how to learn a exible model of an action's temporal structure in order to automatically localize actions in long unsegmented videos. Second, we extend our ideas to the spatio-temporal structure of more complex activities. We describe a large-scale unsupervised learning algorithm used to hierarchically decompose the motion content of videos. We leverage the resulting tree-structured decompositions to build hierarchical action models, and provide an action kernel between unordered binary trees of arbitrary sizes. Third, we directly compare models of the structure instead of structuring action models. We view short-duration actions as high-dimensional time-series, and propose to model an action's temporal dynamics with its auto-correlation. We design an ecient kernel to compare the temporal dependencies between two actions, and show that it provides useful complementary information to the state-of-the-art unstructured models for action classication.

In all three cases, we conducted thorough experiments on real-world videos from challenging benchmarks used by the action recognition community. We show that our methods outperform the related state of the art, thus highlighting that using structure information allows for more accurate and robust action recognition in real-world videos.

iv Résumé Cette thèse décrit de nouveaux modèles pour la reconnaissance de catégories d'actions comme "ouvrir une porte" ou "courir" dans des vidéos réalistes telles que les lms. Nous nous intéressons tout particulièrement aux propriétés structurelles des actions : comment les décomposer, quelle en est la structure caractéristique et comment utiliser cette information an de représenter le contenu d'une vidéo. La diculté principale à laquelle nos modèles s'attellent réside dans la satisfaction simultanée de deux contraintes antagonistes. D'une part, nous devons précisément modéliser les aspects discriminants d'une action an de pouvoir clairement identier les diérences entre catégories. D'autre part, nos représentations doivent être robustes en conditions réelles, c'est-àdire dans des vidéos réalistes avec de nombreuses variations visuelles en termes d'acteurs, d'environnements et de points de vue.

Dans cette optique, nous proposons donc trois modèles précis et robustes à la fois, qui capturent les relations entre parties d'actions ainsi que leur contenu. Notre approche se base sur des caractéristiques locales notamment les points d'intérêts spatio-temporels et le ot optique et a pour objectif d'organiser l'ensemble des descripteurs locaux décrivant une vidéo. Nous proposons aussi des noyaux permettant de comparer ecacement les représentations structurées que nous introduisons. Bien que nos modèles se basent tous sur les principes mentionnés ci-dessus, ils diérent de par le type de problème traité et la structure sur laquelle ils reposent.

Premièrement, nous proposons de modéliser une action par une séquence de parties temporelles atomiques correspondant à une décomposition sémantique. De plus, nous décrivons comment apprendre un modèle exible de la structure temporelle dans le but de localiser des actions dans des vidéos de longue durée. Deuxièmement, nous étendons nos idées à l'estimation et à la représentation de la structure spatio-temporelle d'activités plus complexes. Nous décrivons un algorithme d'apprentissage non supervisé permettant de dégager automatiquement une décomposition hiérarchique du contenu dynamique d'une vidéo. Nous utilisons la structure arborescente qui en résulte pour modéliser une action de manière hiérarchique. Troisièmement, au lieu de comparer des modèles structurés, nous explorons une autre alternative : directement comparer des modèles de structure. Pour cela, nous représentons des actions de courte durée comme des séries temporelles en haute dimension et étudions comment la dynamique temporelle d'une action peut être utilisée pour améliorer les performances des modèles non structurés formant l'état de l'art en reconnaissance d'actions. Dans ce but, nous proposons un noyau calculant de manière ecace la similarité entre les dépendances temporelles respectives de deux actions. Does a horse lift all four feet completely o the ground during the gallop? The answer to this question is often considered as the rst step towards the development of video. In 1872, the photographer Eadweard Muybridge was commissioned by Leland Stanford to give a denitive answer to this long debated question. At this pace around 58 kilometers per hour, or 36 miles per hour a horse's hooves move too fast for the human eye to break down the action: a scientic proof using photographs was required. After several preliminary experiments, Muybridge brought an armative answer to the question through his famous study called "Sallie Gardner at a Gallop" (cf. Figure 1.1). The main challenge was to create a set-up able to take a sequence of pictures capturing the details of fast motions. Muybridge managed to take a series of photos on June 19, 1878 at Stanford's Palo Alto stock farm by placing 24 cameras in a line along the track. The shutter of each camera was triggered by a trip wire as the horse passed. This work was a prelude to the development of visual motion analysis, which consists in scientically and precisely investigating the visual properties of dynamical systems, e.g., uids and humans. Muybridge's work showed that the technological evolution of photography allowed to take sequences of pictures to display a real-world dynamic scene. Image sequences such as Etienne-Jules Marey's chronographs in Figure 1.2 allow the scientist to analyse complex motions, e.g., actions, by looking at the temporal evolution of the participating actors and objects.

The development of video analysis is inseparable from the improvement of recording and projection devices. A plethora of apparatus showing movement through sequences of drawings have existed for a long time. They rely on the optical illusion discovered in 1912 by Max Wertheimer called Beta movement, whereby a succession of still images are combined by the brain to form the perceptual impression of motion. The Zoetrope meaning wheel of life in Greek is an example of a popular device producing the illusion of motion from the rapid succession of still pictures xed on the interior of a spinning cylinder with vertical slits acting as a shutter.

Early video projectors combined the same ideas with the improvements of photography credited to Daguerre and Niépce (1839). For instance, Muybridge invented the rst moving picture projector the Zoopraxiscope (1879) in order to showcase his stop-action photographies. It relied on rapidly projecting a succession of images from rotating glass disks. Shortly after, Auguste and Louis Lumière patented the Cinématographe a lm camera, projector, and developer in 1895 and started producing some of the rst movies ever made.

Since then, video has become one of the most popular visual media for communication and entertainment. In 2010, 441 billion videos were accessible online, which corresponds to approximately 10 21 pixels1 . In 2011, the Youtube website had more than one trillion views and over 800 million unique visitors watched over 3 billion hours of videos per month. Content creation is also booming as one hour of new video content is uploaded to Youtube every second2 . By the end of 2012, video will account for over 50% of internet trac, with a 48% compound annual growth rate3 .

Video spans a wide range of sources and applications: video surveillance, industrial control, robotics (e.g., autonomous vehicles), building automation and domotic, human computer interaction systems, gaming (e.g., Microsoft's Kinect device for the Xbox gaming console), internet content platforms (e.g., Youtube and DailyMotion), TV shows, and movies. The common goal of these applications is to convey or capture some visual information about a real-world scene over some period of time.

The main challenge currently faced by users of these technologies is how to nd the meaningful content they are looking for. Due to the overwhelming quantity of videos, answering this question calls for tools that can automatically analyze, index, and organize video content.

Our work focuses on recognizing actions, one of the important visual information present in video data. Computer vision has recently made signicant progress in action recognition especially for specic tasks such as videosurveillance. Nevertheless, the current state-of-the-art methods are still far from being able to understand every possible action in every type of video.

This can be measured by the low performance of the systems involved in the Multimedia Event Detection (MED) task of TRECVID [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF] a challenging automatic video interpretation competition. For the 2011 edition [START_REF] Over | Trecvid 2011 an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF]], the submitted systems had an average of 6% false alarms with 54% missed detections on actions like making a sandwich and grooming an animal. dataset [START_REF] Marszalek | Actions in context[END_REF]] used in our experiments.

Goals

The goal of our work is to recognize generic actions performed in real-world videos (cf. Figure 1.3 for an illustration). We aim at designing robust models that can represent a broad range of action categories, while accounting for the visual variability of uncontrolled video conditions. Action recognition under uncontrolled conditions faces numerous diculties inherent to the complexity of both actions and videos. Several challenges are related to intra-class variability: actions in the same category may signicantly dier in terms of both appearance and motion content. The sources of variation include noise, lighting conditions, scale and shape of the participating entities, background clutter, wide range of viewpoints, occlusions, fast, complex, and articulated movements, motion blur, camera motion, variability in duration, and execution style. These variations make it dicult for action models to rely on simplifying assumptions such as the full body of the actor being always visible. We account for this variability by using robust local features and by capturing essential structural properties of an action category. Another set of challenges results from between-class confusion: there are often subtle distinctions between actions of dierent classes. For instance, the running and walking actions share similar motions and discriminating between these categories calls for careful motion analysis. Accurately modeling the specicities of an action is especially important in uncontrolled conditions, where a recognition algorithm has to distinguish between the actions of interest and all other possible events some observed during learning, some not. Again, we tackle this issue by using structure information to build and compare more detailed action models. Action recognition encompasses two main tasks: classication and localization. On the one hand, classication aims at assigning a semantic label to an entire video focused on an action. On the other hand, the purpose of localization is to provide both a semantic label and its spatio-temporal extent in videos that may contain more than just one action. In practice, these two problems are closely related, as localization methods often consist in applying a classier at multiple candidate locations to determine the most likely ones. In both cases, we perform category-level recognition, and study supervised learning algorithms to tackle these problems: given a list of action categories, we learn a model using a set of video examples for each category.

As stated previously, we assume that an action is characterized by spatiotemporal relationships between sub-events. We claim that capturing this structural information and in particular the temporal structures is especially important for action recognition in order to achieve robustness under uncontrolled video conditions and to disambiguate between similar categories. Our main goal is to learn better action models by discovering and using this structure. The major diculty lies in how to identify, represent, and integrate in a learning framework the relevant structural aspects of actions. We explore dierent possibilities: sequences of atomic actions, hierarchical motion decompositions, and temporal dependencies between frames.

Context

Automatic video understanding is a fundamental goal of computer vision.

As mentioned previously, actions convey important information needed to understand a dynamic visual scene such as the one depicted in Figure 1. 4.

Even though the actions of some characters may be inferred from this single image, it is more dicult to determine what the person in the middle is doing.

The nature of the objects and the pose of the actors are dicult to understand and by themselves not sucient to determine what actions are being performed: using motion information over a range of frames is necessary. Furthermore, analysing the relations between these movements is necessary to recognize this scene as a Kung-Fu ght. This frame alone is not enough to understand the content of the scene.

Only after looking at the temporal evolution of the dierent actors can we nd out that this is a ghting scene where the character in the center of the frame is being attacked while drinking wine from a bottle.

For computers to be capable of such a high-level interpretation, they need models to represent the various inter-related motions caused by the temporal evolution of the participating entities, e.g., objects and body parts, over the course of an action. For instance, the Motion History Images (MHI) of [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF] is an early and inuential model used to represent an action as the temporal evolution of a silhouette (cf. Figure 1 .5). This approach and other closely related ones e.g., the spatio-temporal shapes of [START_REF] Gorelick | Actions as space-time shapes[END_REF] or the Motion History Volumes (MHV) of [START_REF] Weinland | Free viewpoint action recognition using motion history volumes[END_REF] are, however, not robust and limited to constrained scenarii, such as videosurveillance [START_REF] Hu | A survey on visual surveillance of object motion and behaviors[END_REF], or optical human-computer interfaces [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF]]. They, indeed, rely on information that is dicult to obtain under uncontrolled video conditions, e.g., background subtraction, silhouette extraction, or parametric models of the human body.

Recently, the computer vision community has investigated more challenging videos. Uncontrolled video data is characterized by a great variability and the lack of available prior knowledge applicable to (i) the recording process (e.g., the viewpoint, the camera motion, the video quality, and the resolution), (ii) the scene (e.g., indoors or outdoors, crowded or not, moving and cluttered backgrounds, occlusions, lighting conditions), and (iii) the actions performed (e.g., fast or slow motions, interactions). It spans a large spectrum of videos coming from a wide range of potential sources including amateur videos, news reports, sports broadcasts, TV shows, and movies. There is also an expanding variety of action categories present in the related action recognition benchmarks: simple actions (e.g., running), more complex ones (e.g., getting out of a car), interactions (e.g., kissing), and activities (e.g., eating). of [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF].

In order to address the aforementioned issues, several researchers [START_REF] Chomat | Probabilistic recognition of activity using local appearance[END_REF][START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Laptev | On space-time interest points[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF][START_REF] Zelnik-Manor | Event-based analysis of video[END_REF] proposed to use local features. These are in general spatio-temporal extensions of the 2D detectors and descriptors successfully used in images for object recognition (see for instance the results of the PAS-CAL VOC challenges [START_REF] Everingham | The Pascal Visual Object Classes (VOC) Challenge[END_REF]). Local video features such as spatio-temporal interest points [START_REF] Laptev | On space-time interest points[END_REF]] describe the appearance (e.g., with histograms of oriented gradients [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) or motion (e.g., with histograms of optical ow [START_REF] Laptev | Learning realistic human actions from movies[END_REF]) of local spatio-temporal volumes. Thanks to the robustness of local descriptors and their lack of global assumptions (e.g., about geometrical relations), local features have been successfully applied to challenging action recognition tasks in real-world videos.

An action is then described by the collection of local features found in the corresponding video. The bag-of-features (cf. Section 2.2.3) is a popular model used to represent the set of local spatio-temporal descriptors. It consists in quantizing these local features by assigning each one of them to the closest visual word a prototypical feature and then building the histogram counting the occurrences of each visual word in the video (cf. Figure 1.6 for an illustration). As this orderless model ignores the relations between local features, several extensions have been proposed to incorporate some structure information e.g., with spatio-temporal pyramids [START_REF] Laptev | Learning realistic human actions from movies[END_REF].

Action models based on local features are often high-dimensional (typically on the order of 10 4 dimensions). Furthermore, representations like the bag-of-features are data-driven and not easily interpretable by humans. Therefore, recognition approaches based on local features cannot be implemented in practice using manually dened rules. The machine learning eld provides principled tools that allow to overcome these diculties. Thanks to the large amount of available video data, supervised machine learning algorithms can automatically learn complex action models from annotated training examples. Machines [START_REF] Schölkopf | Learning with Kernels[END_REF] allows to generalise to any video the knowledge acquired from a few training ones.

Successful action recognition applications using machine learning algorithms have already emerged see for instance the development of automatic video-surveillance or Microsoft's Kinect sensor for the Xbox gaming console [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF]]. Nevertheless, at the time of writing (2012) and to the best of our knowledge, a mainstream application of action recognition in the wild (e.g., on Youtube or with autonomous robots) does not exist yet. This highlights the large amount of research that is still required in order to understand the fundamental properties of actions and how to represent them under real-world video conditions.

In this context, we believe it is necessary to build on both the early structured action models and on the recent orderless representations in order to progress towards better action models. Our goal is to nd the good level of details that will allow action models to be simultaneously more precise than bag-of-features and more robust than silhouette-based representations. Our work relies on local features and aims at structuring their aggregation to learn better high-level models of actions. We introduce both sequential representations for simple actions and hierarchical representations for more complex activities. We propose techniques to decompose on frames, temporal parts, and mid-level motion components the global spatio-temporal structure of actions. We exploit these structured representations by designing adapted kernels (similarity measures), which are then integrated in non-linear classiers. We provide experimental evidence validating our solutions concerning the following questions:

• what are good units to decompose actions on;

• what is the interesting structure of actions;

• how to extract and represent structure in a robust manner;

• how to learn and compare structured action models. Our contributions are described in the following paragraphs.

• To localize simple actions, e.g., opening a door, in long unsegmented videos, we introduce a temporally structured extension of bag-of-features: the Actom Sequence Model (ASM). We describe an action as a sequence of atomic action units, termed actoms, which are semantically meaningful temporal parts that are characteristic for the action. ASM represents the temporal structure of actions as a sequence of histograms of actom-anchored visual features (cf. Figure 1.7). Training requires the annotation of actoms for action examples. At test time, actoms are detected automatically based on a non-parametric model, which acts as a prior on an action's temporal structure. We propose a sliding central frame detection approach: every N frames, we evaluate the probability of an action being centered at a particular frame t by marginalizing over our temporal prior:

P(action at t) = s j=1
f ASM (t, ∆j ) P( ∆j )

(1.1)

where ∆j is the jth candidate sequence of actoms in our learned temporal model, P( ∆j ) is its estimated prior probability, and f ASM (t, ∆j ) is the posterior probability returned by our ASM classier. We present experimental results on the challenging Coee and Cigarettes [Laptev and 10 CHAPTER 1. INTRODUCTION Pérez 2007] and DLSBP [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] datasets. We also adapt our approach to a classication by detection set-up, and demonstrate its applicability on the Hollywood 2 dataset [START_REF] Marszalek | Actions in context[END_REF]]. We show that our ASM method outperforms the current state of the art in temporal action detection, as well as baselines that detect actions with a sliding window method combined with a bag-of-features. This work was published in [Gaidon et al. 2011a] and is presented in Chapter 3.

Actom Sequence Model

Actom models • Although simple actions can be represented as sequences of short temporal parts, longer activities, e.g., pole vaulting, are composed of a variable number of sub-events connected by complex spatio-temporal relations.

In Chapter 4, we learn how to automatically represent activities as a hierarchy of mid-level motion components. This hierarchy is a data-driven decomposition that is specic to each video. We introduce a spectral divisive clustering algorithm to eciently extract a hierarchy over a large number of tracklets (i.e., local trajectories, cf. Figure 1.8). We use this structure to represent a video as an unordered binary tree. This tree is modeled by nested histograms of local motion features. We provide an ecient positive denite kernel that computes the structural and visual similarity of two hierarchical decompositions by relying on models of their parent-child relations:

k(T 1 , T 2 ) = 1 |E 1 ||E 2 | • e 1 ∈E 1 e 2 ∈E 2 h(e 1 , e 2 ) (1.2)
where T i is our tree model with edges E i and h(e 1 , e 2 ) denotes the similarity between the histogram models of two edges e 1 and e 2 . We present experimental results on three recent challenging benchmarks: the complex activities from the Olympics Sports dataset [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF], the human-human interactions of the High Five dataset [START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF]], and the large set of simpler actions from the HMDB dataset [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF]. We show that per-video hierarchies provide additional information for activity recognition. Our approach improves over unstructured activity models, baselines using other motion decomposition algorithms, and the state of the art. This work was published in [START_REF] Gaidon | Recognizing activities with clustertrees of tracklets[END_REF]] and is presented in Chapter 4. • Finally, we propose to complement representations based on average statistics e.g., BOF or the two aforementioned approaches with a model of the temporal dependencies between frames: the auto-correlation operator. We address the problem of action recognition by describing actions as time series of per-frame models and introduce a kernel to compare their dynamical aspects (cf. Figure 1.9). The two previous contributions focus on the global structure of actions to organize sets of local features into high-level content representations reecting this structure. This part of our work investigates a dierent way to use structure information: instead of comparing structured video content, we compare the structure of video contents. Our main contributions are the following. First, we provide a principled kernel to compare the dynamics and temporal structure of actions by computing the Distance between their respective Auto-Correlation Operators (DACO):

k DACO ({x t } t=1:T , {y t ′ } t ′ =1:T ′ ) 2 = exp -1 2σ 2 ρ(y) τ -ρ(x) τ 2 HS (1.3)
where ρ(x) τ and ρ(y) τ denote the auto-correlation operators of the time series {x t } t=1:T and {y t ′ } t ′ =1:T ′ respectively. Second, we derive a practical formulation to compute DACO in any feature space deriving from a base kernel between frames. Third, we report experimental results on recent action recognition datasets showing that DACO provides useful complementary information to the average distribution of frames, as used in state-of-the-art models based on the bag-of-features representation. This work was published in [Gaidon et al. 2011b] and is presented in Chapter 5. In this chapter, we rst provide a broad overview of early structured action models based on global representations (Section 2.1), which include sequences of frame descriptors and models of the spatio-temporal volume spanned by an action. We then describe methods based on local features (Section 2.2), which model actions as collections of spatio-temporal patches or local trajectories represented with robust appearance and motion descriptors. We nally review the existing structured models (Section 2.3) that relate most closely to ours. These approaches aim at organizing collections of local descriptors, for instance by modeling their co-occurrence relations or by automatically grouping them into mid-level parts.

CHAPTER 2. RELATED WORK

Global representations

Global models represent an action using appearance and motion descriptors either of the whole body structure or of a region of interest tightly enclosing an actor. These representations typically depend on silhouette extraction or grid structured representations of the region spanned by the body over the execution of an action. In contrast to early gait analysis methods using parametric models of the human body (e.g., the locations and angles of body joints, cf. [START_REF] Moeslund | A survey of advances in visionbased human motion capture and analysis[END_REF]] for a review), global models are more widely applicable, as they do not rely on the identication and tracking of individual body parts. We rst describe action models based on sequences of global representations. We then review volumetric models that describe the shape or motion content of the video volume spanned by an action in space-time.

Sequential approaches

Inspired by techniques successfully applied on speech recognition problems, several works [START_REF] Brand | Coupled hidden Markov models for complex action recognition[END_REF][START_REF] Starner | Real-time American Sign Language recognition from video using Hidden Markov Models[END_REF][START_REF] Wilson | Learning visual behavior for gesture analysis[END_REF][START_REF] Yamato | Recognizing human action in timesequential images using hidden markov model[END_REF]] represent actions as sequences of states modeled by latent variables. They rely on dynamic probabilistic graphical models such as Hidden Markov Models (HMM) [START_REF] Rabiner | Introduction to digital speech processing[END_REF] to learn temporal transitions between these hidden states. An action is represented by a generative model over sequences of per-frame feature vectors, and recognition is performed based on the likelihood of an image sequence with respect to this model. For instance, [START_REF] Yamato | Recognizing human action in timesequential images using hidden markov model[END_REF] recognize tennis actions using HMMs on grid representations of silhouettes.

Since then, several approaches [START_REF] Chen | Modeling Human Activities as Speech[END_REF][START_REF] Hoai | Joint segmentation and classication of human actions in video[END_REF][START_REF] Kulkarni | An unsupervised framework for action recognition using actemes[END_REF][START_REF] Laxton | Leveraging temporal, contextual and ordering constraints for recognizing complex activities in video[END_REF][START_REF] Lv | Single view human action recognition using key pose matching and Viterbi path searching[END_REF][START_REF] Oliver | A Bayesian computer vision system for modeling human interactions[END_REF][START_REF] Shi | Human action segmentation and recognition using discriminative semi-Markov models[END_REF][START_REF] Zeng | Knowledge based activity recognition with dynamic bayesian network[END_REF] attempt to recognize actions in more challenging settings. In general, they use a Viterbi-like inference algorithm to temporally segment videos. For instance, [START_REF] Chen | Modeling Human Activities as Speech[END_REF] adapt speech recognition tools to model actions with a space-time-frequency representation of scores of boosted spatio-temporal interest point detectors. Their approach requires the localization and continuous tracking of the entire human body (not individual body parts) in order to compute a gure-centric descriptor. Dealing with long-term interactions with objects, [START_REF] Laxton | Leveraging temporal, contextual and ordering constraints for recognizing complex activities in video[END_REF] use Dynamic Bayesian Networks (DBN) with manually designed peractivity hierarchies of predened contextual cues and object detectors. Some other sequential approaches [START_REF] Hoai | Joint segmentation and classication of human actions in video[END_REF][START_REF] Shi | Human action segmentation and recognition using discriminative semi-Markov models[END_REF]] are related to HMMs, but instead learn a discriminative model from manually segmented training videos in order to perform action segmentation. Also operating on sequential representations, exemplar-based techniques [START_REF] Darrell | Space-time gestures[END_REF][START_REF] Gavrila | Towards 3-d model-based tracking and recognition of human movement: a multi-view approach[END_REF][START_REF] Niyogi | Analyzing and recognizing walking gures in XYT[END_REF][START_REF] Veeraraghavan | The function space of an activity[END_REF] directly compute an alignment score between an action and some template sequences. In general, these methods require less training data and provide more exibility, as they can handle non-linear speed variations with the Dynamic Time Warping (DTW) algorithm [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]. For instance, [START_REF] Darrell | Space-time gestures[END_REF] use DTW on a sequence of scores obtained by correlating a video with a set of per-view templates. More recently, [START_REF] Brendel | Activities as time series of human postures[END_REF] recognize actions as time series of a few snapshots of body parts obtained by video segmentation (cf. Figure 2.1). They use a template-based classication approach by aligning a video with training examples using DTW.

Despite their eciency on constrained video data and their encoding of temporal aspects, sequential methods suer from some limitations. For instance, they cannot represent actions involving concurrent sub-events, e.g., human interactions. Some extensions of HMMs, such as coupled HMMs [START_REF] Oliver | A Bayesian computer vision system for modeling human interactions[END_REF]] or more generic Dynamic Bayesian Networks [START_REF] Laxton | Leveraging temporal, contextual and ordering constraints for recognizing complex activities in video[END_REF], address this issue. Their complex domain-specic structure, however, needs to be manually specied by experts (see for instance Figure 2.2). In addition, spatio-temporal action localization requires higher-level probabilistic models, e.g., by combining multiple HMMs [Brand andKettnaker 2000, Lv and[START_REF] Lv | Single view human action recognition using key pose matching and Viterbi path searching[END_REF]. These models need a large amount of training examples in order to account for all events that might occur, including non-actions.

Volumetric approaches

In contrast to sequential recognition techniques, volumetric methods view actions as 3D (X-Y-T) objects in a spatio-temporal video volume, thus treating space and time in a unied manner. They extract global action models that capture structure information in the form of spatio-temporal shapes. Volumetric approaches mostly rely on template matching for recognition and are successful under restricted video conditions [START_REF] Gorelick | Actions as space-time shapes[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF], such as simple static backgrounds, actors with full body always visible, and restricted viewpoint variations and camera motions. Some models operate directly on the videos themselves. For instance, [START_REF] Kim | Canonical correlation analysis of video volume tensors for action categorization and detection[END_REF] directly compare video volumes using Tensor Canonical Correlation Analysis (cf. Figure 2.3). Alternatively, several approaches [START_REF] Blank | Actions as Space-Time Shapes[END_REF][START_REF] Bobick | The recognition of human movement using temporal templates[END_REF][START_REF] Gorelick | Actions as space-time shapes[END_REF][START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height lter for action recognition[END_REF] rely on silhouettes in order to obtain spatio-temporal templates. For instance, [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF] introduce motion history images (MHI), which are temporal templates representing the evolution of motion over time. [START_REF] Blank | Actions as Space-Time Shapes[END_REF] and [START_REF] Gorelick | Actions as space-time shapes[END_REF] use background subtraction techniques to model actions as space-time shapes. [START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height lter for action recognition[END_REF] learn spatiotemporal cuboid templates and perform template matching via correlation using the generalized Fourier transform. Silhouettes provide useful information for action recognition, but their use is limited to simple or controlled video conditions. They are, indeed, dicult to obtain in the presence of complex dynamic backgrounds, and do not account for self-occlusions.

Other volumetric approaches [START_REF] Efros | Recognizing action at a distance[END_REF][START_REF] Ke | Volumetric features for video event detection[END_REF][START_REF] Polana | Low level recognition of human motion[END_REF][START_REF] Schindler | Action snippets: How many frames does human action recognition require[END_REF], Shechtman and Irani 2005] focus on optical ow to obtain global action templates. For instance, [START_REF] Polana | Low level recognition of human motion[END_REF] represent periodic actions with spatio-temporal grids of optical ow. [START_REF] Shechtman | Space-time behavior based correlation[END_REF] use the correlation between motion ows. Finally, several researchers have investigated the combination of both appearance and motion information to represent the content of a video volume. For instance, [START_REF] Laptev | Retrieving actions in movies[END_REF] propose a boosted action classier over multiple motion and shape features (see Figure 2.5). Relying on spatio-temporal gradients and a generic human detector, Kläser et al. [2010b] introduce the HOG-Track descriptor to represent a segment of a human track.

A spatio-temporal volume spanned by a human is discretized with a spatiotemporal grid, and each cell of this grid is represented using a HOG3D descriptor [START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF]]. These methods have shown promising results on challenging video data such as movies.

Volumetric approaches rely on a similarity measure between video volumes, and typically localize actions by matching sub-volumes with a set of candidate templates. For instance, [START_REF] Ke | Volumetric features for video event detection[END_REF] use a sliding-window approach with part-based matching relying on pictorial structures, and Kläser et al. [2010b] localize actions using a sliding window approach restricted to human tracks. Note that sequential approaches can also be applied in a similar sliding window manner, such as in [START_REF] Darrell | Space-time gestures[END_REF] with DTW and in [START_REF] Wilson | Parametric Hidden Markov Models for gesture recognition[END_REF] with HMMs.

The aforementioned global approaches are particularly ecient when used to compare spatio-temporally aligned videos. As they focus on global structure, they are, however, not robust to occlusions (e.g., truncated actors), signicant viewpoint changes, and duration variations. Global approaches also assume the contiguity of the video volume spanned by an action. Consequently, they are not adapted to actions composed of spatio-temporally separated events such as interactions involving multiple actors (e.g., ghting). Finally, global representations are often restricted to constrained video scenarii, because they rely on accurate human localization or background subtraction, e.g., for silhouette extraction. This type of information is, indeed, dicult to obtain in the presence of camera motion, dynamic and cluttered backgrounds, lighting changes, and poor video quality.

Local features

Pioneered by [START_REF] Chomat | Probabilistic recognition of activity using local appearance[END_REF], [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF], [START_REF] Laptev | Space-time interest points[END_REF], [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF], [START_REF] Zelnik-Manor | Event-based analysis of video[END_REF], action recognition approaches based on local features represent videos as collections of local spatio-temporal regions. They rely on the automatic extraction of small video volumes, or sequences of image patches, directly from the pixel values or the optical ow eld. Local features make no assumptions about the global structure of actions, and yield representations that are remarkably robust under uncontrolled video conditions. These methods have demonstrated competitive performance on a wide range of challenging data, including movies [START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Marszalek | Actions in context[END_REF], TV shows [START_REF] Gaidon | Mining visual actions from movies[END_REF][START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF], Youtube clips [START_REF] Ikizler-Cinbis | Learning actions from the web[END_REF], Liu et al. 2009], and sports broadcasts [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF][START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height lter for action recognition[END_REF].

See [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF]] for a recent evaluation.

We rst describe the dierent types of local features. We then review the two main families of recognition techniques based on local features: local classiers, which deal with features individually, e.g., using voting strategies, and global approaches, which aggregate features over video sub-volumes, e.g., using a bag-of-features representation.

Types of local features

Local spatio-temporal features

Local spatio-temporal features are an ecient method to extract and represent the visual information from local video volumes. Indeed, they are easy to extract, as they often rely on well-known image interest point detectors generalized to the 3D spatio-temporal domain, and require neither video segmentation, nor human or object detection. For instance, [START_REF] Laptev | On space-time interest points[END_REF] proposes an extension of the Harris cornerness criterion [START_REF] Harris | A combined corner and edge detector[END_REF] to detect spatio-temporal interest points (see Figure 2.6). Other spatio-temporal feature detectors include the cuboids of [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] and Willems et al.

[2008]'s space-time extension of the Hessian blob detector [START_REF] Beaudet | Rotationally invariant image operators[END_REF]]. Spatio-temporal features are then described using robust local descriptors. For instance, [START_REF] Laptev | Learning realistic human actions from movies[END_REF] describe both local appearance and local motion in a small spatio-temporal volume using Histograms of Oriented Gradients (HOG) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and Histograms of Optical Flow (HOF). [START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF] also propose the extension of HOG to the spacetime domain.

CHAPTER 2. RELATED WORK

Point trajectories

The temporal evolution of spatial coordinates of tracked local image regions is another intuitive and ecient way to characterize the local motion content associated to actions. Approaches based on long-term spatio-temporal trajectories, e.g., [START_REF] Ali | Chaotic invariants for human action recognition[END_REF][START_REF] Campbell | Recognition of human body motion using phase space constraints[END_REF][START_REF] Junejo | View-Independent Action Recognition from Temporal Self-Similarities[END_REF][START_REF] Messing | Activity recognition using the velocity histories of tracked keypoints[END_REF][START_REF] Parameswaran | View invariance for human action recognition[END_REF][START_REF] Rao | View-invariant representation and recognition of actions[END_REF][START_REF] Sheikh | Exploring the space of a human action[END_REF], have been able to automatically recognize a variety of actions from trajectory and velocity information only. However, tracking pixels and their underlying parts across many frames is a challenging problem for complex articulated movements of humans in real-world videos essentially due to lighting changes, motion blur, compression artifacts, and occlusions. Furthermore, trajectory-based approaches often rely on the accurate detection or segmentation of body parts or objects, or require manually annotated training data that are expensive to obtain.

Tracklets local point trajectories, corresponding to pixels tracked across a xed small number of frames combine useful aspects of both trajectories and local spatio-temporal features. Similar to trajectories, tracklets dierentiate the time domain from the spatial one. They provide a structured and information-rich characterization of the motion of underlying parts. Similar to local features, tracklets can be easily and reliably extracted [Wang et al. 2011], for instance by simple interpolation in a motion eld computed using mature optical ow extraction algorithms [Farnebäck 2003, Lucas and[START_REF] Lucas | An Iterative Image Registration Technique with an Application to Stereo Vision[END_REF]. Their short duration also limits drifting problems, i.e., trajectories deviating from the underlying tracked object. This is in contrast to long-range trajectories [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Lezama | Track to the future: Spatiotemporal video segmentation with long-range motion cues[END_REF][START_REF] Sand | Particle video: Long-range motion estimation using point trajectories[END_REF], which are expensive to compute and face diculties in capturing fast and articulated motions due to their sensitivity to occlusions.

The modeling approaches used with local spatio-temporal features have been successfully adapted to tracklets, thanks to their limited spatio-temporal range and xed duration. For instance, [START_REF] Matikainen | Trajectons: Action recognition through the motion analysis of tracked features[END_REF] quantize trajectory snippets of key points over a vocabulary of prototypical tracks (see Figure 2.7a). In addition, the appearance and motion information of video volumes surrounding a trajectory can be represented with the aforementioned robust local descriptors (see Figure 2.7b). This yields state-of-the-art results as shown in [Wang et al. 2011]. Similarly to local spatio-temporal features, tracklets only describe local information. Furthermore, tracklet-based approaches often sample a large number of features obtained by dense sampling [Wang et al. 2011], which makes them more computationally expensive than sparse features like spatio-temporal interest points.

Local classiers

Amongst methods processing features individually, voting-based approaches [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF][START_REF] Mikolajczyk | Action recognition with motion-appearance vocabulary forest[END_REF][START_REF] Oikonomopoulos | An implicit spatiotemporal shape model for human activity localization and recognition[END_REF][START_REF] Willems | Exemplar-based action recognition in video[END_REF][START_REF] Yao | A hough transform-based voting framework for action recognition[END_REF][START_REF] Yuan | Discriminative video pattern search for ecient action detection[END_REF]] aim at measuring the importance of each feature for a particular action. They detect actions by extracting local features, each of which casts a vote for a particular action. For instance, [START_REF] Willems | Exemplar-based action recognition in video[END_REF] propose to prune quantized local features using an exemplar-based voting approach (cf. Figure 2.8). [START_REF] Yuan | Discriminative video pattern search for ecient action detection[END_REF] detect spatio-temporal interest points that cast votes based on their pointwise mutual information with the action category. They, then, use a spatiotemporal branch and bound algorithm to eciently localize actions.

Other approaches [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF][START_REF] Nowozin | Discriminative subsequence mining for action classication[END_REF] propose to select the most relevant local features. For instance, [START_REF] Nowozin | Discriminative subsequence mining for action classication[END_REF] use a sequence of individual local features assigned to a xed number of uniformly sized temporal bins. [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF] prune local spatio-temporal features using the PageRank algorithm [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], and combine static and motion features with an AdaBoost classier [START_REF] Freund | A desicion-theoretic generalization of on-line learning and an application to boosting[END_REF].

Figure 2.8: Voting approach of [START_REF] Willems | Exemplar-based action recognition in video[END_REF]. From left to right: (i) a video, (ii) spatio-temporal features, (iii) location hypotheses generated from the features, (iv) detections obtained by clustering the hypotheses.

Selecting local features allows to eciently localize the action in spacetime. Voting approaches can also detect multiple co-occurring actions and simple multi-actor interactions. However, these methods assume that each local feature can provide enough information to recognize an action. Therefore, they are not discriminative enough to dierentiate between complex actions sharing common motion or appearance primitives, e.g., sport activities.

Bag-of-features

An alternative family of models uses the global distribution of features over a video volume. In particular, one of the most common and ecient representation is the bag-of-features (BOF). Originally designed to represent textual documents as word frequencies, it was successfully adapted to model images as collections of local patches [Csurka et al. 2004, Cula andDana 2001, Sivic and Zisserman 2003] (see Figure 2.9) , and videos as bags of local spatio-temporal features [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF], Niebles et al. 2008[START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF], Wang et al. 2011]. In the BOF model, a vocabulary of prototype features called visual words is obtained by clustering, and a video is represented as a histogram of occurrences of local features quantized over this visual word vocabulary (see Figure 1.6 for an illustration). Statistical learning methods like Support Vector Machines (SVM) [START_REF] Schölkopf | Learning with Kernels[END_REF] can then be applied to learn a BOF classier. Localization can be performed by applying this classier in a sliding window manner [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF]].

Due to its eciency and popularity, we systematically compare our methods to this BOF approach, which we consider as a baseline to improve upon.

Note that the BOF model discards the global spatio-temporal information inherent to actions: it is an orderless representation. Therefore, it is not designed to discriminate between actions characterized by their structure e.g., opening and closing a door and can cause numerous high score false alarms during localization.

Figure 2.9: The bag-of-features image model (courtesy of Fei-Fei Li) Several works address the aforementioned shortcomings of the BOF representation. We rst describe methods computing statistics on the spatial and/or temporal relations between local features. We then review models that use groups of features as mid-level building blocks for structured action models.

Modeling relations between local features

As stated before, the BOF model disregards the position of the local features to build robust action models. This, however, is done at the expense of discriminative power. In order to alleviate this well-known issue, a signicant body of work has focused on augmenting BOF with the relations between the positions of co-occurring features, either at a global level i.e., in an entire video or at a more local one i.e., between neighboring features.

Global relations

Spatio-temporal pyramids [START_REF] Laptev | Learning realistic human actions from movies[END_REF] are a popular example of using the positions of the features to globally structure an action representation. Extending spatial pyramids [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]] to the spatio-temporal domain, [START_REF] Laptev | Learning realistic human actions from movies[END_REF] propose to divide a video into cells (sub-volumes) using a coarse spatio-temporal grid. Each cell is described by the aggregation of its local features. The full video is then described by the ordered concatenation of the per-cell BOF models, leading to a globally structured representation.

The main limitation of this approach lies in the rigidity and a priori denition of the coarse spatio-temporal layout, assumed to be shared by all videos: the actors and actions must be roughly aligned in the X-Y-T video space such that cells are in correspondence. Multiple grids can be combined at the expense of added computational complexity but the authors showed that, ultimately, the eciency of this technique depends on the videos and actions, while yielding only moderate improvements on average. [START_REF] Wong | Learning motion categories using both semantic and structural information[END_REF] propose a more exible way to encode the global relations between local features by extending the Implicit Shape Model (ISM) of [START_REF] Leibe | Pedestrian detection in crowded scenes[END_REF] to the space-time domain. Inspired by [START_REF] Fergus | Learning object categories from google's image search[END_REF][START_REF] Leibe | Pedestrian detection in crowded scenes[END_REF], they propose to combine probabilistic Latent Semantic Analysis (pLSA) [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF]] with an ISM in order to model both the appearance of local space-time cuboids [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] and their relative position with respect to the center of the action. The EM algorithm is used to learn the pLSA parameters from a large co-occurrence matrix between visual words and quantized relative positions. Note that the center of the action must be known in order to convert the absolute positions of local features to relative ones. If not available in advance, then this central location can be inferred automatically using the probabilistic Hough voting scheme from [START_REF] Leibe | Pedestrian detection in crowded scenes[END_REF]. This, however, strongly degrades performance with respect to the fully supervised case, i.e., with manually annotated centers. Even in this scenario, discriminative methods, e.g., SVMs, clearly outperform this generative model as reported in [START_REF] Wong | Learning motion categories using both semantic and structural information[END_REF]].

Our Actom Sequence Model presented in Chapter 3 builds on these approaches especially the spatio-temporal pyramids of [START_REF] Laptev | Learning realistic human actions from movies[END_REF] in order to integrate in a discriminative learning framework a exible model of the global temporal relations between local features. Instead of using a xed video subdivision, we propose to learn an action-specic decomposition from manual annotations of an action's most meaningful temporal parts.

Local relations

In contrast to the aforementioned global approaches, some methods [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF][START_REF] Kovashka | Learning a hierarchy of discriminative spacetime neighborhood features for human action recognition[END_REF][START_REF] Oikonomopoulos | An implicit spatiotemporal shape model for human activity localization and recognition[END_REF][START_REF] Savarese | Spatial-Temporal correlatons for unsupervised action classication[END_REF] focus on modeling the local relations between a feature and its spatio-temporal neighbors. In general, these methods explicitly count cooccurrences, and either build compound descriptors out of a feature and its neighborhood [Gilbert et al. 2010, Kovashka and[START_REF] Kovashka | Learning a hierarchy of discriminative spacetime neighborhood features for human action recognition[END_REF], or concatenate the usual content BOF with a relations BOF [START_REF] Matikainen | Representing pairwise spatial and temporal relations for action recognition[END_REF][START_REF] Savarese | Spatial-Temporal correlatons for unsupervised action classication[END_REF]]. For instance, [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF] use data mining techniques to nd frequent 2D corners of an action. They group a feature with its neighbors to build compound features. They then iterate this process by mining frequently co-occurring compound features to build higher-level compound features. Recognition is performed using a voting scheme on the local hierarchical structures of 2D corner neighborhoods. [START_REF] Kovashka | Learning a hierarchy of discriminative spacetime neighborhood features for human action recognition[END_REF] use a similar hierarchical process. They iteratively build increasingly complex compound features by vector-quantizing the cumulative co-occurrence histograms between a feature and its neighbors (cf. Figure 2.10a). A video is represented by the set of histograms of quantized features over the various levels of neighborhoods. Recognition is performed by a SVM and multiple neighborhood sizes and hierarchy levels are combined through Multiple Kernel Learning [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF]].

Separately modeling relations, [START_REF] Savarese | Spatial-Temporal correlatons for unsupervised action classication[END_REF] propose to describe the local neighborhood of a feature using spatio-temporal correlograms. These are the concatenation of co-occurrence histograms between visual words in a spatio-temporal neighborhood. These correlograms are then vector-quantized on a k-means-computed codebook of correlatons, and classication is per-formed using pLSA on histograms of correlatons. [START_REF] Matikainen | Representing pairwise spatial and temporal relations for action recognition[END_REF] also explicitly model pairwise relations between features using a Naive-Bayes model, which assumes conditional independence of features when knowing the action class (cf. Figure 2.10b). They avoid the performance issues of generative models by using the log-likelihoods with respect to their per-class probabilistic co-occurrence model as features fed to a discriminative classier. These co-occurrence based methods face several limitations. First, counting co-occurrences between local features yields very sparse models with a vast number of parameters, which leads to overtting and prevents these methods from generalizing. It is possible to mitigate this issue by relying on approximations and simplications of the considered relations e.g., [START_REF] Matikainen | Representing pairwise spatial and temporal relations for action recognition[END_REF] rely on a coarse orientation discretization. This, however, induces strong quantization eects and restricts the discriminative power of those representations. In addition, only relations between spatio-temporally close features can be captured due to the combinatorial nature of the problem.

Finally, all the aforementioned works have conducted experiments suggesting that co-occurrence models and compound features by themselves are performing signicantly worse than the simple BOF model. Nevertheless, they have also shown that the relations between features provide complementary information that, when used in conjunction with BOF, results in performance improvements.

Our DACO kernel between time series of frames presented in Chapter 5 builds on these results. However, instead of relying on co-occurrences between features, it accounts for an action's dynamics, i.e., the relations between its frames over time. We show that the auto-correlation between frames provides a model of the temporal dependencies, which complements the average statistics captured by BOF.

Structuring groups of local features

Instead of directly modeling relations between local features, some models rely on the relations between groups of local features. Contrary to human-centric models, these groups or parts do not necessarily map to semantically meaningful entities, e.g., a body part, but correspond to a data driven organization of the video content. They aim at robustly encoding the global structure of an action by studying the relations between mid-level descriptors of groups of local features.

In particular, the design of probabilistic part-based models is a popular direction of research to formalize high-level structural aspects of actions. For instance, [START_REF] Niebles | Hierarchical model of shape and appearance for human action classication[END_REF] model an action category by a constellation of parts (cf. Figure 2.11). Each part is associated to a distribution over positions and appearance of its constitutive local features. The content of a part is then represented as a BOF. The part layer of the generative model in Figure 2.11 encodes the geometrical relations between parts. This mixture model is learned using the EM algorithm and inference is done by maximizing an approximation of the likelihood for eciency reasons. [START_REF] Wang | Hidden part models for human action recognition: Probabilistic vs. max-margin[END_REF] propose another probabilistic part-based model that encodes the spatial pairwise relationships between features in a frame. Their model is based on the hidden conditional random eld (HCRF) [START_REF] Quattoni | Hidden conditional random elds[END_REF]]. These approaches, however, are limited to frame-by-frame recognition and only model spatial relations inside the same frame. [START_REF] Niebles | Hierarchical model of shape and appearance for human action classication[END_REF] where an action category is modeled by a constellation of bag-of-features.

Figure 2.12: Graphical activity model of [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF] obtained by hierarchical video segmentation. [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF] propose a more sophisticated graphical model which relies on hierarchical video segmentation (cf. Figure 2.12). They represent a video using a graph of spatial, temporal, and inclusion relations between spatio-temporal parts. A category is modeled by an average graph containing thousands of nodes learned by a robust least squares algorithm to account for spurious parts. Recognition is done by estimating the likelihood of a video with respect to each action graph. The resulting complex inference procedure involves approximately solving a NP-hard Quadratic Assignment Problem (QAP) to nd a subgraph isomorphism between the video's graph and an action's model. This powerful generative approach highlights the importance of representing hierarchal structure. However, [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF] make a strong spatio-temporal consistency assumption about the data. Indeed, as they search for a subgraph isomorphism between an action instance and the graphical model of a category, their approach assumes that all action instances of a category share the same parts in the same geometrical and temporal congurations. This method is also restricted to model spatio-temporal tubes. Their video segmentation, indeed, denes parts as continuous motions of color-consistent objects.

More discriminative approaches make use of the latent SVM of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. For instance, [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF] discover temporal parts and learn a SVM classier per video segment at temporal locations considered as latent variables. They use a loose hierarchical structure that is adapted to long duration activities by introducing a temporal displacement penaliza-tion factor in segment comparisons. In addition to discovering discriminative temporal segments, [START_REF] Tang | Learning latent temporal structure for complex event detection[END_REF] model the transitions between hidden states and their durations using a semi-Markov Model [START_REF] Hongeng | Large-scale event detection using semi-hidden markov models[END_REF], whose parameters are learned using a latent SVM.

Extending the previous approaches to handle not only temporal segments but spatio-temporal parts, [START_REF] Raptis | Discovering Discriminative Action Parts from Mid-Level Video Representations[END_REF] use clusters of long-term point trajectories [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF] as candidate parts. They also learn a latent SVM model, where latent variables determine which clusters are the most discriminative. MAP inference over the latent variables involves solving a complex subgraph matching problem. This method relies on bounding boxes for training and assumes that all actions from a category share the same a priori xed number of important parts.

Similar to the aforementioned models, our hierarchical action representation presented in Chapter 4 relies on modeling the content and relations between groups of local features. We, however, distance ourselves from existing work by directly comparing per video hierarchies instead of looking for a single global model of a category. Furthermore, both the content and the structure of our activity descriptors are specic to each video. This allows for models with a variable number of parts, which can, therefore, better model intra-class variability.

Introduction

Although early action recognition experiments in simple videos have shown promising results [START_REF] Blank | Actions as Space-Time Shapes[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF]], recent eorts have tried to address more challenging video sources like movies [START_REF] Laptev | Learning realistic human actions from movies[END_REF].

In this chapter, we target such sources and address the problem of temporal action localization : nding if and when an action is performed in a database of long and unsegmented videos. In particular, we focus on searching for actions of a few seconds, like sitting down, in several hours of real-world videos.

For such realistic data, many state-of-the-art action models are based on the popular bag-of-features (BOF) [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Duchenne | Automatic annotation of human actions in video[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF], Niebles et al. 2008[START_REF] Satkin | Modeling the Temporal Extent of Actions[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF], Wang et al. 2011], which suers from several limitations in the context of action localization. First, a BOF ignores the temporal ordering of the frames. Therefore, we propose to address the BOF's orderless nature by introducing a sequential action model that enforces a soft ordering between meaningful temporal parts. Our robust structured model can represent actions with only approximately ordered or partially concurrent sub-events of dierent durations. Second, BOF-based recognition methods assume that test videos are presented in the same temporally segmented fashion as the training examples, i.e., that they strictly contain only one action. Instead, we provide an algorithm to learn the global temporal structure of actions, which allows for ecient action localization in unsegmented videos.

Our approach is based on a simple observation: a large number of actions can be naturally dened in terms of a composition of simpler temporal parts. For instance, Figure 3.1 illustrates that the displayed actions are easy to recognize given a short sequential description. Obtaining such a decomposition is challenging, and its components are clearly action-specic.

Closest references

Our approach extends BOF and localizes actions with a sliding central frame technique. The most similar approaches are [Duchenne et al. 2009, Satkin andHebert 2010], which rely on multi-scale heuristics with manually dened window sizes. In contrast, our algorithm leverages a learned generative model of an action's temporal structure.

We also improve upon existing temporally structured extensions of BOF. [START_REF] Laptev | Learning realistic human actions from movies[END_REF] combine multiple BOF models extracted for dierent, manually selected, and rigid spatio-temporal grids. Multiple coarse grids are combined in a multi-channel Gaussian kernel. This approach improves over the standard BOF representation, but the temporal structure of actions is xed and not explicitly modeled. On the contrary, we learn a temporal structure adapted to the action, and show that, compared to a rigid grid, this results in more signicant gains in localization performance. Related to our work, [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF] discover motion parts based on the latent model from [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. They learn a SVM classier per motion segment at xed temporal locations, whereas we do not rely on an intermediate recognition step, and use our temporal decomposition to classify actions. In addition, they use a loose hierarchical structure that is tailored to the classication of long duration activities, e.g., triple-jump, but not adapted to short actions as illustrated by their results.

Our method is similar in spirit to the state-of-the-art approaches for facial expression recognition from videos. Facial expression recognition can be performed using label information dened by the Facial Action Coding System (FACS) [START_REF] Ekman | Facial Action Coding System[END_REF], which segments facial expressions into predened action units, complemented with temporal annotations such as onset, peak, and oset. Most approaches, however, only use peak frames for classication [START_REF] Cohn | Use of automated facial image analysis for measurement of emotion expression[END_REF], except [START_REF] Simon | Action unit detection with segment-based SVM[END_REF]]. Furthermore, as the complexity of generic human actions makes the construction of universal action units impractical, we investigate user-annotated, actionspecic training actoms.

Finally, we dier from popular sequential probabilistic models like Hidden Markov Models (HMM) [START_REF] Rabiner | Introduction to digital speech processing[END_REF]. Indeed, instead of using a generative model to measure the likelihood of transitions between latent states, we adopt a non-parametric discriminative approach that jointly models the content of temporally ordered parts without independence assumptions. Outline First, in Section 3.2, we introduce actoms and our temporally structured representation of actions in videos, called the Actom Sequence Model (ASM). Second, in Section 3.3, we describe our ASM classier, and propose a simple yet ecient algorithm to learn a generative model of the temporal structure of an action. Third, in Section 3.4, we show how to use these models to perform temporal action localization with a sliding central frame approach. In addition to localizing actions, our approach can also return the most likely actoms (cf. Figure 3.12). In Section 3.5, we show that our method outperforms the state of the art on two challenging benchmarks for action localization: the Coee and Cigarettes [START_REF] Laptev | Retrieving actions in movies[END_REF] and DLSBP [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] datasets. We also demonstrate the applicability of our approach in a classication by localization setup on a larger set of actions from the Hollywood 2 dataset [START_REF] Marszalek | Actions in context[END_REF]]. Finally, we investigate and quantify the importance of the dierent components of our method.

Actions as sequences of actoms

An action is decomposed into a few temporally ordered and category-specic actoms. An actom is a short atomic action, identied by its central temporal location around which discriminative visual information is present. It is represented by a temporally weighted aggregation of local features, which are described in Section 3.2.1. We model an action as a sequence of actoms by concatenating the per-actom representations in temporal order. We refer to our sparse sequential model as the Actom Sequence Model (ASM), which we dene in Section 3.2.2. Finally, we describe the process used to acquire training actom annotations in Section 3.2.3.

Local visual information in actoms

Following [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF], we extract sparse spacetime features [START_REF] Laptev | On space-time interest points[END_REF]] to represent video content. They provide a good compromise between representation power and sparsity, which allows for accurate models with a limited memory footprint a necessary property for action localization in long video streams. We use a multi-scale space-time extension of the Harris operator to detect spatio-temporal interest points (STIPs) [START_REF] Laptev | STIP: Spatio-Temporal Interest Point library[END_REF]]. They are represented with a concatenation of histograms of oriented gradients (HOG) and optical ow (HOF). Once a set of local features has been extracted, we quantize them using a visual vocabulary of size v. In our experiments, we cluster a subset of 10 6 features randomly sampled from the training videos. Similar to [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF], we use the k-means algorithm with a number of clusters set to v = 1000 for our localization experiments, while, similar to [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF]], we use v = 4000 for our classication-by-localization experiments. We then assign each feature to the closest visual word.

3.2.2

The Actom Sequence Model

We dene the time-span of an actom with a radius around its temporal location. We propose an adaptive radius that depends on the relative position of the actom in the video sequence. The adaptive radius r i , for the actom at temporal location t i , in the sequence of a actom locations

(t 1 , • • • , t a )
, is parametrized by the overlap ratio ρ between adjacent actoms:

r i = δ i 2 -ρ , δ i =      t 2 -t 1 if i = 1 t a -t a-1 if i = a min(t i -t i-1 , t i+1 -t i ) if 1 < i < a (3.1)
where ρ ranges between 0 and 1, and δ i is the distance to the closest actom. This denes a symmetric neighborhood around the temporal location specic to each actom of an action. Visual features are computed only within the forward and backward time range dened by the actom's radius. They are, then, accumulated in per-actom histograms of visual words cf. Figure 3.2.

Our model only assumes a weak temporal ordering of the actoms. In addition, dening the actom's time-span relatively to its closest neighbor has multiple advantages. On the one hand, it allows adjacent actoms to overlap and share features, while enforcing a soft temporal ordering. This makes the model robust to inaccurate temporal actom localizations and to partial orderings between concurrent sub-events. On the other hand, it also allows for gaps between actoms and can, therefore, represent discontinuous actions. Furthermore, an adaptive time-span makes the model naturally robust to variable action duration and speed.

We also introduce a temporally weighted assignment scheme. We propose to aggregate temporally weighted contributions of per-actom features. Each feature at temporal location t in the vicinity of the i th actom, i.e., if |t-t i | ≤ r i , is weighted by its temporal distance to the actom: Hence, features further from an actom's center vote with a smaller importance. See the actom models depicted in Figure 3.2 for an illustration.

w i (t) = 1 σ √ 2π exp - (t -t i ) 2 2σ 2 (3.2)
This scheme oers an intuitive way to tune the bandwidth σ of the weighting window using the Chebyshev inequality. For a random variable X of mean µ and nite standard deviation σ, we know that P(|X -µ| ≥ kσ) ≤ 1/k 2 , for any k > 0. Rewriting this with X = t, µ = t i and r i = kσ, we obtain:

P(|t -t i | < r i ) ≤ p, p = 1 - σ 2 r 2 i (3.3)
The probability p is the peakyness of our soft-assignment scheme and replaces σ as a hyper-parameter of our model. It allows to encode a prior on the amount of probability mass of features falling in an actom's time range. ASM encompasses a continuum of models, ranging from sequences of soft key-frames (upper left), to BOF-like models (lower right).

See Figure 3.3 for an illustration of the inuence of the overlap ρ and peakyness p on the actom-specic per-frame weights. In our experiments, we set the parameters ρ and p per-class by maximizing localization performance on a held out, unsegmented, validation video. We found that this hyperparameter optimization scheme yielded better results than cross-validation on the segmented training clips. Cross-validation, indeed, only maximizes window classication performance, which is an easier problem than localization, as the training videos are already segmented.

To summarize, we derive our ASM model from a sequence of a actom locations by (i) computing visual features only in the actoms's time-spans, parametrized by the ρ parameter (Eq. 3.1), (ii) computing the feature contributions to per-actom temporally weighted histograms (Eq. 3.2), and (iii) appending these histograms into a temporally ordered sequence, i.e., our ASM representation of videos

x = (x 1,1 , • • • , x 1,v , • • • , x a,1 , • • • , x a,v )
, where:

x i,j = t i +r i t=t i -r i w i (t)c j (t) (3.4)
In Equation 3.4, x i,j is the weighted sum of the number c j (t) of local features detected at frame t and assigned to visual word j, over the i th actom's timespan [t ir i , t i + r i ]. The ASM vector x is then L 1 -normalized.

Actom annotations

We now present how to obtain actom annotations and the advantages of this supervision over annotating beginning and ending frames of actions.

Obtaining annotations

An actom annotation is a time stamp in the corresponding video. This temporal location is selected such that its neighboring frames contain visual information that is representative of a part of the action. The number of actoms is xed depending on the action category. We observed that only a few actoms are necessary to unambiguously recognize an action from their sequence likelihood threshold (we use 2%). After these samples are re-annotated, we update the model of the temporal structure and re-estimate the likelihood of each annotation. We iterate this process up to three times.

Practical observations

Consistent actom annotations are easier to obtain than precise action boundaries. For instance, it is unclear whether a person walking towards a door before opening it is a part of the action Open Door. In contrast, the time at which the door opens can be unambiguously determined. [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] and [START_REF] Satkin | Modeling the Temporal Extent of Actions[END_REF] observed that temporal boundaries of actions are not precisely dened in practice. Furthermore, they show that inaccurate boundary annotations signicantly degrade the recognition performance. Therefore, they propose to improve the quality of annotated action clips by automatically cropping their temporal boundaries in a discriminative manner. They, however, only model the temporal extent of actions, not their temporal structure. On the contrary, actom annotations are well dened as a few frames of precise atomic events. Consequently, annotating actoms leads to smaller annotation variability.

Temporal action detector learning

In the following, we detail the training part of our localization algorithm.

First, we give details on the action classier operating on our ASM representation (Section 3.3.1). Then, we describe how we learn a generative model of an action's temporal structure in order to sample likely actom candidates at test time (Section 3.3.2). Finally, we show how to obtain negative training examples (Section 3.3.3).

ASM classier

Our localization method is similar to the sliding-window approach. It consists in applying a binary classier at multiple temporal locations throughout the video, in order to determine the probability that the queried action is being performed at a particular moment. We use a Support Vector Machine (SVM) [START_REF] Schölkopf | Learning with Kernels[END_REF] trained to discriminate between the action of interest and all other visual content. As ASM is a histogram-based representation, we can use a non-linear SVM with the χ 2 or the intersection kernel [START_REF] Hein | Hilbertian metrics and positive denite kernels on probability measures[END_REF]Bousquet 2005, Laptev et al. 2008]. For eciency reasons, we choose to use the intersection kernel [START_REF] Maji | Classication Using Intersection Kernel Support Vector Machines is ecient[END_REF]. It is dened for any

x = (x 1 , . . . , x v ) and x ′ = (x ′ 1 , . . . , x ′ v ) as K(x, x ′ ) = v j=1 min(x j , x ′ j ).
Note that, in our case, using a non-linear SVM does not prohibitively impact the localization speed, because the size of our training set is small.

In this set-up, the negative class spans all types of events except the action of interest. Therefore, more negative training examples than positive ones are necessary. We use a SVM with class-balancing [START_REF] Lin | Statistical Properties and Adaptive Tuning of Support Vector Machines[END_REF] to account for this imbalance between the positive and negative classes. Assume we have a set of labeled training examples (x 1 , y 1 ), . . . , (x n , y n ) ∈ X × {-1, 1}, where X is the space of ASM models. Let n + , resp. n -, denote the number of positive, resp. negative, examples, and n = n + + n -the total number of examples. The binary SVM classier with class-balancing minimizes the regularized cost function:

1 n n i=1 L(y i )ℓ(y i , f (x i )) + λ w 2 H (3.5) with f (x i ) = w T φ(x i )+b, w ∈ H, H
the feature space associated with the kernel K, φ : X → H the corresponding feature map, ℓ(y, f ) = max(0, 1yf ) the hinge loss, L(+1) = 1/n + , L(-1) = 1/n -, and λ a regularization parameter. In order to return probability estimates, we t a sigmoid function to the decision function f learned by the SVM [START_REF] Lin | A note on Platt's probabilistic outputs for support vector machines[END_REF][START_REF] Platt | Probabilistic outputs for support vector machines[END_REF]]. Our ASM classier evaluates the posterior probability of an action being performed, knowing its actoms. In practice, we have only few actom annotations, typically n + ≤ 100, which, in addition, can signicantly dier from one another. Therefore, using histograms to model the actom spacings yields a too sparse estimate with many empty bins. Instead, we make the assumption that there is an underlying smooth distribution, which we estimate via non-parametric Kernel Density Estimation (KDE) [START_REF] Rosenblatt | Remarks on some nonparametric estimates of a density function[END_REF][START_REF] Wasserman | All of statistics: a concise course in statistical inference[END_REF]]. This makes the assumption that there is a continuum of execution styles for the action of interest, and it allows to correctly interpolate unseen, but likely, temporal structures. We use KDE with Gaussian kernels whose bandwidth h is automatically set using Scott's factor [Scott 1992]: h = n

{∆ i = (t i,2 -t i,1 , . . . , t i,a -t i,a-1 ), i = 1 . . . n + },
-1 a+4 +
. We obtain a continuous distribution D over inter-actom distances ∆ = (t 2t 1 , . . . , t at a-1 ):

D ∼ 1 n + h a-1 √ 2π n + i=1 exp - ||∆ -∆ i || 2 2h 2 . (3.6)
As we deal with discrete time steps (frames), we discretize this distribution in the following way. First, we sample 10 4 points, randomly generated from our estimated density D. Second, we quantize these samples by clustering them with k-means. This yields a set of s centroids { ∆j , j = 1 • • • s} and their associated Voronoi cells that partition the space of likely temporal structures.

Third, we compute histograms by counting the fraction pj of the random samples drawn from D that belong to each cell j. This results in the discrete multi-variate distribution:

D = {( ∆j , pj ) , j = 1 • • • s}, pj = P( ∆j ).
(3.7)

Finally, we truncate the support of D by removing structures with a probability smaller than 2% (outliers), and re-normalize the probability estimates. In this section, we describe our temporal localization approach (Section 3.4.1), some post-processing steps (Section 3.4.2), and a strategy for action classication in approximatively pre-segmented videos (Section 3.4.3).

Sliding central frame localization

To localize actions in a test sequence, we apply our ASM classier in a sliding window manner. However, instead of sliding a temporal window of xed scale, we shift the temporal location of the middle actom t m , where m = ⌊a/2⌋, and a is the number of actoms for the action category. We use a temporal shift of 5 frames in our experiments. Given a central actom location t m , we compute the probability of the action occurring at t m by marginalizing over our generative model of inter-actom spacings D:

P(action at t m ) = s j=1 P(action at t m | ∆j ) P( ∆j ) = s j=1 f ASM ( tj,1 , • • • , t m , • • • , tj,a ) pj (3.8)
where f ASM is the a posteriori probability estimate returned by our SVM classier trained on ASM models (Eq. 3.5). See Figure 3.6 for an illustration. Alternatively, taking the maximum a posteriori allows to not only localize an action, but also its most likely temporal structure. We have experimentally observed that, for the goal of temporal localization, marginalizing yields more stable results than just taking the best candidate actoms. The temporal structures in D are indeed related. This is a consequence of our assumption on smoothly varying styles of execution (cf. Figure 3.5). Therefore, the redundancy in D makes marginalizing over actom candidates robust to inaccurate actom placements. Note that Equation 3.8 provides a way to perform multi-scale localization dierently than the usual multi-scale sampling heuristic. Both the sequential structure and the duration of the action is modeled by D, whereas traditional sliding-window approaches, e.g., [START_REF] Laptev | Retrieving actions in movies[END_REF], manually specify a xed set of window sizes.

Post-processing

Our algorithm estimates a probability of localization every N th frame. In order to localize the action, we also return an estimate of the temporal extent of each localization, i.e., a temporal window surrounding each high-scoring frame. As we deal with short actions with limited duration variation, we choose to use a single, xed, action-specic duration for our temporal windows. We use a temporal scale such that a localization window contains all frames used in the computation of the score of its central frame. As we marginalize over D, this denes a single scale per action category, which only depends on the largest actom spacings in D. In practice, we obtained the constant window sizes of 95 frames for drinking and smoking in the Coee and Cigarettes dataset, 85 frames for opening a door and 65 frames for sitting down in DLSBP.

In addition, as the temporal shift between two localizations can be small in practice, we use a non-maxima suppression algorithm to remove overlapping localization windows. We recursively (i) nd the maximum of the scores, and (ii) delete overlapping windows with lower scores. Windows are considered as overlapping if the Jaccard coecient the intersection over the union of the frames is larger than 20%.

Classication by localization

Although designed for temporal localization, our method is also applicable to action classication. In both cases, the training data and learning algorithms are the same. The test data, however, diers. For localization, we process continuous streams of frames. In contrast, unseen data for classication come in the form of pre-segmented video clips.

The classication goal is to tell whether or not the action is performed in an unseen video clip, independently of when it is performed. Consequently, after applying our sliding central frame approach to label every N th frame of a new test clip, we pool all localization scores to provide a global decision for the entire clip. Similarly to [START_REF] Satkin | Modeling the Temporal Extent of Actions[END_REF], we found that max-pooling i.e., taking the best localization score as classication score yields good results in our set up. Indeed, marginalizing over actom candidates limits the number and the score of spurious false localizations, thanks to the redundancy in the learned temporal structure.

Experimental evaluation

This section presents experimental results comparing our ASM-based approach with BOF-based alternatives and the state of the art. We, rst, introduce the datasets used in our experiments (Section 3.5.1). We, then, describe how we measure the localization performance (Section 3.5.2), and what baseline localization methods we compare to (Section 3.5.3). Our localization results are reported in Section 3.5.4, while our classication results are reported in Section 3.5.5. Finally, we quantify and discuss the inuence of the parameters of our method (Section 3.5.6).

Datasets

We use two challenging movie datasets for action localization: Coee and

Cigarettes [START_REF] Laptev | Retrieving actions in movies[END_REF] and DLSBP [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF]].

Note that they are currently among the largest public benchmarks for action localization in realistic settings. There are, indeed, only few action localization datasets, due to the high cost incurred by the manual annotation of the full test sequences. We also use the Hollywood 2 dataset [START_REF] Marszalek | Actions in context[END_REF] for our classication by localization experiments. These datasets are provided with annotations in the form of temporal boundaries delimiting actions.

Coee and Cigarettes [START_REF] Laptev | Retrieving actions in movies[END_REF]. This dataset is designed for the localization of two action categories in movie data: drinking and smoking (cf. Note that we use uniformly sampled actoms for the ghting category, as it could not be annotated with consistent actoms. Indeed, ghting scenes in movies are not short, sequentially dened actions, but involve various actions in no particular order, e.g., punching and kicking.

Figure 3.9: Some of the actions from the Hollywood 2 dataset

Evaluation criteria

For temporal localization, we use two evaluation criteria to determine if a test window is matching a ground truth action (cf. Figure 3.10). We rst consider the most commonly used criterion [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF], Kläser et al. 2010b[START_REF] Laptev | Retrieving actions in movies[END_REF], referred to as OV20: a window matches a ground truth action if the Jaccard coecient (intersection over union) is more than 20%. We use the original ground truth start and end frame annotations provided by the dataset authors. This criterion, however, does not guarantee that a localization will contain enough of the action to be judged relevant by a user. For instance, a localization relevant according to OV20 may contain a person walking towards a door, but not the door opening itself.

Therefore, in addition to OV20, we introduce a more precise matching criterion based on ground truth actom annotations. Referred to as OVAA, for overlap all actoms, it states that a test window matches a ground truth test action only if it contains the central frames of all ground truth actoms.

The OVAA criterion stems from the denition of actoms as the minimal set of sub-events needed to recognize an action. Hence, a correct localization must, by denition, contain all actoms. In consequence, we also annotate actoms for the positive test examples to assess ground truth according to OVAA. These annotations are not used at test time. Note that a single window covering the entire test sequence will always match the ground truth according to the OVAA criterion. This bias, however, is not present in our comparisons as all methods have comparable window sizes of approximatively 100 frames or less.

OVAA Figure 3.10: Overlap criteria used for localization OV20 (intersection over union of at least 20% with the ground truth) and OVAA (a match needs to contain all ground truth actom frames).

[ [ OV20 [ [ [ [ [ [ [ [ [ [ [ [ [ [
We use both criteria in our evaluation, because they provide complementary insights. If after non-maxima suppression there are multiple windows matching the same ground truth action, we only consider the one with the maximal score as a true positive, while the other localizations are considered as false positives. This is similar to the evaluation of object detection, e.g., in the Pascal VOC challenge [START_REF] Everingham | The Pascal Visual Object Classes (VOC) Challenge[END_REF]]. Note that, for classication by localization, no matching criterion is required as we return one score for each test video. In all cases, we follow the state of the art and measure performance in terms of precision and recall by computing the Average Precision (AP).

Bag-of-features baselines

We compare our approach to two baseline methods: the standard bag-offeatures (BOF), and its extension with a regular temporal grid. To make the results comparable, we use the same visual features, vocabularies, and kernel Like for our sliding central frame method, we use a stepsize of 5 frames for the sliding window approach in all of our experiments.

We, nally, apply a non-maxima suppression post-processing step similar to the one described in Section 3.3.2, and commonly used in the literature, e.g., in [Kläser et al. 2010b].

As mentioned previously, in addition to the global BOF baseline, we evaluate its extension with regular temporal grids [START_REF] Laptev | Learning realistic human actions from movies[END_REF]]. We use a xed grid of three equally sized temporal bins, which in practice gave good results, and is consistent with our number of actoms. First, the video is cut in three parts of equal duration: beginning, middle, and end. A BOF is then computed for each part, and the three histograms are concatenated. This method is referred to as BOF T3 in the following.

Localization results

We report temporal localization results in Table 3.1 for the Coee and Cigarettes dataset, and in Table 3.2 for the DLSBP dataset. We compare our method (ASM), two baselines (BOF and BOF T3), and recent state-of-the-art results. Where possible, we report the mean and standard deviation of the performance over ve independent runs with dierent random negative training samples.

Comparison to bag-of-features

We perform better than BOF according to both evaluation criteria. The improvement is signicant with OV20: +27% for Drinking, +23% for Smoking, +6% for Open Door, and +8% for Sit Down. BOF is also less precise than our approach. Indeed, the performance of BOF drops when changing the matching criterion from OV20 to the more restrictive OVAA, e.g., -26%

for Drinking. In contrast, our ASM model is more accurately localizing all action components, and the relative gap in performance with respect to the baseline increases even more when changing from OV20 to OVAA, e.g., from

+27% to +52% for Drinking, and from +8% to +16% for Sit Down. This conrms that the variable temporal structure of actions needs to be represented with a exible model that can adapt to dierent durations, speeds, and interruptions.

Comparison to the state of the art

The method of [START_REF] Laptev | Retrieving actions in movies[END_REF] is trained for spatio-temporal localization with stronger supervision in the form of spatio-temporally localized actions. We compare to the mapping of their spatio-temporal localization results to the temporal domain as reported in [Duchenne et al. 2009], cf. [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF]]. They use a similar set-up to our BOF baseline.

The dierences between their approach and our BOF baseline lies mostly in the negative training samples and, to a lesser extent, in the visual vocabulary. Our experiments show that ASM outperforms these state-of-the-art approaches, for all actions of the two datasets. Our method even outperforms methods trained with more complex supervision like bounding boxes, e.g., +14% with respect to LP-T [Laptev and Pérez 2007], or human tracks, e.g.,

+4% and +7% with respect to KMSZ-T [Kläser et al. 2010b]. This shows that modeling the temporal structure of actions is crucial for performance.

Classication-by-localization results

Figure 3.13 contains the per class classication by localization results on the Hollywood 2 dataset. As mentioned previously, the BOF baselines are using the same sliding window approach as in the previous localization results.

On average over all classes, ASM improves by +11% over both BOF baselines, which perform comparably (BOF T3 only marginally improves by +0.1% with respect to BOF). The improvement yielded by ASM is noticeable on the classes with a clear sequential nature such as Answer Phone, Hug Person, or Sit Down. Interestingly, ASM always improves performance, even when BOF T3 yields worse results than the orderless BOF, e.g., for Hand Shake and Stand Up. Once again, these results show that a exible model of the temporal structure is required in order to recognize real-world actions. Hollywood 2 dataset [START_REF] Marszalek | Actions in context[END_REF]]. BOF and BOF-T3 are sliding-window approaches using BOF and its temporally structured extension. Our approach is ASM. AVG contains the average performance over all classes (BOF: 38%, BOF-T3: 38%, ASM: 49%).

We also evaluate baseline classication methods similar to [START_REF] Laptev | Learning realistic human actions from movies[END_REF], where a single model is computed over the entire duration of each test video. On average over all classes, we obtained approximately the same results of 45% AP for three dierent models: BOF, BOF T3, and ASM with uniformly spread actoms and ρ = p = 75%. Note that the similar performance of these three global models shows that the benets of ASM do not only lie in its use of soft-voting. In comparison, ASM with classication by localization achieves 49% AP. This +4% gain is less signicant than for temporal localization, because classication of pre-segmented videos is an easier problem in this benchmark. Indeed, global models use context information, whereas the more local representations used for localization focus only on the action, at training time as well as at test time. As shown by the dataset authors [START_REF] Marszalek | Actions in context[END_REF]], using context improves action recognition. Our experiments conrm this, as classifying using a global model of the entire video improves by +9% (45%) over the BOF classication by localization results (36%).

3.5.6

Parameter study

We measured the impact of the dierent components of our approach: (i) the sliding central frame localization method compared to the sliding window technique, (ii) manual actom annotations compared to uniformly spread ones, (iii) the ASM parameters, (iv) the number of candidate temporal structures learned, and (v) the number of training negatives.

Sliding central frame

First, we found that our sliding central frame approach outperforms the sliding window one. Therefore, marginalizing over a generative model of the temporal 3.5. EXPERIMENTAL EVALUATION 51 structure is preferable to the commonly used scale sampling heuristics. This can be observed in Table 3.3, where we report the localization results using BOF models in conjunction with our sliding central frame approach.

In this case, we adopt the same method as described in Section 3.

Manual training actoms

Second, we computed the localization results using our ASM approach with training actoms spread uniformly between the manually annotated temporal boundaries. We observed that localization results are signicantly worse than when using manually annotated training actoms. Indeed, ASM with these uniform actoms yields results similar to BOF T3 with the sliding central frame approach. This shows that temporal boundaries do not provide enough information to model the temporal aspects of an action.

ASM parameters

Third, we studied the impact of the ASM parameters on performance. In

Temporal model complexity

In addition, we studied the impact of the complexity of the temporal structure model measured by the support size s of D, cf. Eq. 3.7 on the localization performance. This parameter controls a trade-o between the precision of the model and, as we marginalize over this distribution, the computational complexity at test time. We found that s = 10 candidate actom structures yields a good compromise for most classes cf. Figure 3.14 for an illustration using the Smoking action. On the one hand, if s < 5, then the model is too simple and the performance gap between the OV20 and OVAA results is large.

On the other hand, if s > 15, then results are equivalent to 5 ≤ s ≤ 15 but at a higher computational cost. Note that this parameter has the strongest impact on localization performance after the ASM hyper-parameters. We found that between one and ten times the number of positives was sufcient to reach satisfactory performance for all classes. We sampled twice more negatives than positives for the Coee and Cigarettes dataset, and eight times more for the DLSBP dataset. This choice allows to maintain a high true positive over false negative ratio, while limiting the imbalance factor between classes and speeding up localization.

Sampling only few training negatives, however, yields unstable results, as illustrated by the large standard deviation reported in our experiments. This instability can be controlled using a simple bagging approach i.e., averaging classiers over dierent negative training sets as suggested in [Mordelet and Vert 2010] at the expense of an increase in computational complexity. The x-axis is in log-scale.

Conclusion

In this chapter, we introduced the Actom Sequence Model (ASM). This model describes an action with a temporal sequence of actoms, i.e., meaningful temporal parts that are characteristic of the action. It is discriminative, as it represents an action by several components instead of one average representation as in the bag-of-features. It is exible, as our temporal representation allows for varying temporal speed of an action as well as interruptions within the action. Experimental results show that our approach outperforms the bag-of-features as well as its extension with a xed temporal grid. Furthermore, ASM improves over the state of the art, including more sophisticated models using spatial localization.

Introduction

Video content often relates to humans and their actions. Simple actions, e.g., running, rarely convey enough meaning to interpret a scene, but instead form the building blocks of more complex activities, e.g., pole vaulting. In this chapter, we aim at recognizing such high-level activities, which are spatiotemporal patterns composed of several related movements of actors, body parts, and objects. Automatically identifying those parts and exploiting both their contents and their relations is a challenging problem that is important for the recognition of complex activities. Therefore, we introduce an unsupervised approach to hierarchically decompose the complex motion content of an activity, and an ecient algorithm to compare two tree-structured videos.

Our method consists in, rst, extracting dense tracklets [Wang et al. 2011], which are short-term trajectories of densely sampled points that describe most of the interesting motion contained in a video. We, then, decompose the motion content of a video into a hierarchy of data-driven parts by using hierarchical clustering on the set of tracklets. Our main contribution is a hierarchical divisive clustering algorithm based on recursive bi-partitioning of an approximate multi-modal spectral embedding of tracklets. We use the resulting structure, called cluster-tree [START_REF] Duda | Pattern Classication and Scene Analysis[END_REF] (cf. Figure 4.1), to model a video as an unordered binary tree, called BOF-tree, which we represent by nested histograms of local motion features. Using this structured information presents several challenges. First, BOFtrees have a variable number of nodes (motion components), and a structure that is specic to each video. Second, there is no natural left-to-right ordering of the children of the same parent node. Therefore, we introduce a positive denite kernel on variable-size, unordered binary trees. It consists in eciently comparing all sub-trees by approximating them through simple edge models, and leveraging the additive structure of BOF-trees. We, then, use this kernel with a Support Vector Machine (SVM) [START_REF] Schölkopf | Learning with Kernels[END_REF] to learn powerful non-linear activity classiers.

Closest references

Our approach is weakly supervised: it relies neither on part annotations, nor on a predened action decomposition as in Chapter 3. In addition, we use neither video segmentation techniques [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF][START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Grundmann | 3D shape context and distance transform for action recognition[END_REF][START_REF] Lezama | Track to the future: Spatiotemporal video segmentation with long-range motion cues[END_REF], nor pre-trained object detectors [START_REF] Prest | Explicit modeling of human-object interactions in realistic videos[END_REF]]. We argue that clusters of tracklets provide a compromise between, on the one hand, detailed information available from segmentation, and, on the other hand, higher-level attributes, body part localizations, or object detections. Although our tracklets are of a short duration, the clusters obtained with our hierarchical decomposition capture complex and long-term motions of spatio-temporal parts, as well as their relations.

Our method is based on the Nyström approximation for spectral clustering [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]]. However, in contrast to the k-means algorithm used in [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]], we do not require the number of parts to be globally xed and known a priori, and our hierarchical decomposition provides useful structural information relating the motion parts together, instead of unrelated clusters. Furthermore, our divisive method can scale to videos with hundreds of thousands of tracklets, whereas bottom-up agglomerative algorithms have a computational complexity that is at least quadratic in the number of points [START_REF] Fradet | Clustering point trajectories with various life-spans[END_REF][START_REF] Hastie | The elements of statistical learning[END_REF]]. As we deal with tracklets, another dierence with existing trajectory clustering approaches [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Fradet | Clustering point trajectories with various life-spans[END_REF][START_REF] Lezama | Track to the future: Spatiotemporal video segmentation with long-range motion cues[END_REF]] is that we do not restrict trajectory comparisons to their common time span.

Related to our work, [START_REF] Niebles | Hierarchical model of shape and appearance for human action classication[END_REF] propose to represent an action as a constellation of parts represented by BOFs over shape and motion features. They model a category using a probabilistic mixture of a xed number of parts. They classify actions in controlled video conditions by maximizing the likelihood with respect to their generative model. [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF] propose another related generative model. They use a more general graphical model learned from hierarchical video segmentations.

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

Their approach, however, assumes that all actions of the same category share strong geometrical and temporal part relationships. Furthermore, their video segmentation algorithm and therefore the resulting action models can only account for smooth motions of color-consistent parts forming continuous spatio-temporal tubes. We do not make these restrictive assumptions on parts. Furthermore, we estimate and compare each video's specic structure, and learn a discriminative model instead of matching to a global action template. In our experiments, we show that we outperform their method.

Discriminative alternatives to these generative models are often based on the popular deformable part model of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. For instance, [START_REF] Liu | Recognizing human actions by attributes[END_REF] combine manually predened attributes with data-driven ones obtained by clustering local features. They use a latent SVM [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] to learn the importance of each part. [START_REF] Wang | Hidden part models for human action recognition: Probabilistic vs. max-margin[END_REF] use tracking and a Hidden Conditional Random Field (HCRF) to learn a discriminative model of latent parts for frame-by-frame recognition. Closest to our work, [START_REF] Raptis | Discovering Discriminative Action Parts from Mid-Level Video Representations[END_REF] extract clusters of long-term trajectories and learn a latent model over a xed number of parts. Their approach has a cubic time complexity in the number of trajectories, relies on bounding box annotations, and uses only a xed small subset of clusters for all videos. Furthermore, they explicitly model pairwise relationships between clusters using the trajectory, whereas we use the full hierarchical structure resulting from our clustering.

In contrast to all the aforementioned discriminative approaches, we do not assume that actions share a xed number of parts common to all training instances. Instead, each video has its own decomposition structure, and all parts including their relationships are used in our video comparisons. In addition, as we do not rely on latent parts, we do not need to solve a complex inference problem for each test video.

We also dier from methods using global hierarchies over local features [START_REF] Mikolajczyk | Action recognition with motion-appearance vocabulary forest[END_REF]Uemura 2008, Reddy et al. 2009] or shape-motion prototypes [START_REF] Jiang | Recognizing Human Actions by Learning and Matching Shape-Motion Prototype Trees[END_REF]]. These methods use global tree structures to speed up the computation of a matching score, where each feature casts a vote for an action category. In our approach, we account for all local features jointly, and leverage instance-level relationships without explicitly modeling neighborhoods and cooccurrences over the whole dataset [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF][START_REF] Kovashka | Learning a hierarchy of discriminative spacetime neighborhood features for human action recognition[END_REF][START_REF] Matikainen | Representing pairwise spatial and temporal relations for action recognition[END_REF] our hierarchical model for the motion content of a video, the BOF-Tree, and our kernel for such BOF-Trees. In Section 4.4, we evaluate our method on the complex activities from the Olympic Sports dataset [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF]] and on the human-human interactions from the High Five dataset [START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF]]. We show that our approach outperforms BOF-based baselines, decompositions obtained with other clustering algorithms, and the state of the art. We also show that our approach can be successfully applied on a large set of simple actions, the HMDB dataset [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF]], although the performance gains are smaller.

Clustering dense tracklets

In this section, we rst describe how we extract dense local point trajectories, called tracklets (cf. Figure 4.2) using dense optical ow elds. We then address the problem of eciently and accurately clustering a video composed of a large number of tracklets in order to obtain a hierarchical decomposition of its motion components. We describe the two steps of our clustering algorithm:

a non-linear projection of the tracklets on a multi-modal spectral embedding using the Nyström approximation, followed by a hierarchical divisive clustering algorithm. Note that the algorithm described in this section is applied to a single video at a time and does not require any other external data, such as other videos containing the same action. In order to track densely sampled points, we follow the approach described in [Wang et al. 2011]. First, we compute the dense optical ow eld of the video using Farnebäck's algorithm [START_REF] Farnebäck | Two-frame motion estimation based on polynomial expansion[END_REF]] as implemented in the OpenCV library [START_REF] Bradski | Learning OpenCV: Computer vision with the OpenCV library[END_REF]. This iterative multi-scale approach is based on approximating the neighborhood of pixels by quadratic polynomials using polynomial expansion. Second, we sample the pixels to be tracked on a dense spatial grid. Similar to [Wang et al. 2011], we observed that a sampling step-size of 5 pixels along both the x-axis and the y-axis is a good compromise between density and speed given the dimensions of our videos between 50 and 1000 frames for resolutions close to 640 × 480. As points in homogeneous regions cannot be reliably tracked, we lter them out following the criterion of [START_REF] Shi | Good features to track[END_REF]: if the smallest eigenvalue of the autocorrelation matrix of a point is lower than a threshold, it is removed from the set of points to be tracked.

Third, we use a multi-scale video representation over 8 spatial scales, spaced by a factor 1/ √ 2. We do not use multiple temporal scales i.e., we track points from frame t to t + 1 as we are only interested in local point trajectories. Each point P t = (x t , y t ) at frame t is robustly tracked in each scale by median ltering in the dense optical ow eld w = (u t , v t ):

P t+1 = (x t+1 , y t+1 ) = (x t , y t ) + (M * w)| xt,ȳt , (4.1)
where M is the median ltering kernel and (x t , ȳt ) is the rounded position of (x t , y t ). Note that this interpolation step is ecient once the dense optical ow eld is extracted. This approach, therefore, allows to eciently track points on a dense spatial grid.

The new frame t + 1 may then contain good regions void of points to be subsequently tracked. Indeed, points can be lost and new ones can appear due to a change in the scene. Therefore, and in order to maintain density, we ll these regions by adding new points re-sampled on the dense spatial grid.

Point trajectories interpolated from an optical ow eld are often deviating from the underlying tracked pixel after a certain number of frames. In order to limit this drifting problem, Wang et al. [2011] propose to track points only across a xed small number of frames L. In their experiments, they show that using tracklets of duration L = 15 frames can yield state-of-the-art action recognition results. We observed that, in our case, shorter tracklets yields better results and use L = 5 frames in our experiments. Indeed, when dealing with fast motions, the displacements of the underlying pixels are large, motion blur causes point tracks to drift faster, and self-occlusions make it often impossible to track interesting body parts for more than a few frames. This is especially frequent in sports videos, e.g., when an athlete spins on himself before throwing a discus. Furthermore, although such short duration tracklets convey less information, clusters of tracklets can encode mid-level information on par with variable-length longer-term trajectories. Finally, errors in longterm trajectories due to drift cannot be easily recovered from at later stages.

On the contrary, errors in short-term tracklets amount to noise that can be appropriately handled via some simple post-processing steps, as described in the following paragraphs. First, tracklets with static trajectories are deleted. They indeed convey no motion information and are often associated either with a static textured background (e.g., trees) or with noise. We also handle the other extremal case by removing tracklets containing large and sudden displacements.

Finally, we lter out tracklets that are in low-density regions. In more details, isolated but reliably tracked points e.g., due to block-like compression artifacts are considered as outliers and removed. We use a simple sliding window outlier estimation technique that has proven eective in our situation. For each tracklet P = (P t ) t=F -L+1,••• ,F ending at frame F , we rst estimate its approximate spatial k-nearest neighbors N k,r (P) restricted to tracklets ending between frames Fr and F + r. In our experiments, we used k = 30 neighbors, r = 5 frames, and the spatial distance between tracklets is estimated between their respective average positions P = (x, ȳ) = 1 L L t=1 P t . We then compute the local sparsity s P of a tracklet as the mean spatial distance to its neighbors in the temporal window [Fr, F + r]:

s P = 1 k P ′ ∈N k,r (P) P -P ′ (4.2)
We consider a tracklet with local sparsity s P as an outlier if s P > s + σs , where (s, σs ) is the mean and standard deviation of the spatial distance to the approximate spatial k-nearest neighbors of all tracklets in the entire video, irrespective of temporal position. The approximate k-nearest neighbors are computed via kd-trees, which are eciently built in the 2-D space of average spatial positions of tracklets.

4.2.2

Tracklet descriptors for intra-video clustering

Once the tracklets have been extracted, we model them using multiple features describing both their spatio-temporal position and shape. We use the following descriptors to represent trajectory information:

• x = (x 1 , • • • , x L ), x positions over time, • y = (y 1 , • • • , y L ), y positions over time, • z = (t, • • • , t + L -1), temporal positions,
• v x = (x k+1x k ) k=1:L-1 , velocities along x-axis,

• v y = (y k+1y k ) k=1:L-1 , velocities along y-axis.

Note that as our goal is to cluster tracklets to decompose the motion components inside a video, our descriptors need not be particularly robust as all comparisons are intra-video during this clustering stage. We also separate the trajectory information along the dierent spatio-temporal dimensions in order to allow for dimension-specic normalizations in the later stages of our algorithm. Another noteworthy point is the seemingly redundant use of both trajectory and velocity descriptors. This redundancy is important in practice, because velocity information tends to be unstable as taking derivatives along the trajectory amplies high frequency noise that results from small inaccuracies of the point tracking algorithm.

Our approach is, however, not specic to the set of features chosen to represent a tracklet. The only pre-requisite is the availability of a similarity function specic to each feature channel. We use Gaussian RBF kernels

k(f, f ′ ) = exp(-γd(f, f ′ ) 2 ), where the distance d(f, f ′ ) is the Euclidean dis- tance. The γ parameter of each kernel is automatically xed to γ = 1/(2 d),
where d is an estimate of the median of the distances between the corresponding tracklet features. This normalization ensures that all kernels are comparable across the dierent feature channels.

Multi-modal spectral embedding of tracklets

Once the features are extracted, the rst step of our clustering algorithm is to project tracklets onto a low-dimensional space. This embedding relies on spectral properties of a similarity matrix between tracklets.

Similarity between tracklets

In our case, as we have multiple features representing dierent useful characteristics of tracklets, we use as similarity the product of the per-feature similarities. As each feature-specic similarity is positive-denite, the product similarity is also a positive-denite kernel. It corresponds to a feature space that is the tensor product of the feature spaces induced by the individual kernels. Using this product kernel has the advantage of entailing an and eect, i.e., tracklets close according to this similarity are close with respect to all the features used. This behavior is desirable as all our feature spaces convey meaningful information representing our priors on tracklets, such as similar tracklets should be close and have similar shapes.

CLUSTERING DENSE TRACKLETS 63

In contrast, using an early fusion approach i.e., concatenating the descriptors into a single vector or summing the per-feature kernels has an or eect: tracklets are close according to at least one feature. In addition, early fusion mixes heterogeneous descriptors with various scales into a long vector, for which Euclidean distances are not adequate. Therefore, central grouping methods like k-means are not adapted to our set-up, as they search for clusters with a Gaussian distribution in the Cartesian product of the input spaces. These shortcomings are addressed by resorting to a spectral clustering method, which operates on an embedding of the data points.

Spectral embedding

The spectral embedding of our tracklets is based on projections onto the leading eigenvectors of the graph Laplacian corresponding to a similarity matrix between tracklets. Let W ∈ R N ×N be a symmetric similarity matrix between N tracklets. This matrix can be viewed as the weighted adjacency matrix of a graph, where the nodes are the tracklets and the edges are weighted by the pairwise anity between tracklets. The normalized Laplacian of this graph is dened as

L = I -D -1/2 W D -1/2
, where D is the diagonal matrix of row-sums of W . Thresholding the eigenvector of L with the second smallest eigenvalue yields an approximate solution to the NP-Hard Normalized Cut (NCut) bi-partitioning problem [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Note that the leading eigenvalue-eigenvector pair of L is (0, D 1/2 1).

In order to obtain a predetermined number of clusters, one can either apply this technique recursively on the next leading eigenvectors, or use a distortion-minimization clustering algorithm e.g., k-means on an embedding consisting of the projections on multiple leading eigenvectors.

For N data points, the N E -dimensional spectral embedding (N E ≪ N ) is obtained by computing the N × (N E + 1) matrix V of the N E + 1 leading eigenvectors and the (N E + 1) × (N E + 1) diagonal matrix Λ of eigenvalues of the system:

D -1/2 W D -1/2 V = V Λ. (4.3)
The j th embedding coordinate of the i th tracklet is given by:

E i,j = V i,j+1 D i,i , i = 1, • • • , N, j = 1, • • • , N E , (4.4)
where the eigenvectors are sorted by ascending eigenvalue. Thus, each tracklet is associated with a row of E and a clustering algorithm can be applied on the rows to partition the data.

64 CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS However, the spectral embedding cannot be directly computed this way in our case. Indeed, for N tracklets, solving equation 4.3 requires the computation and storage of a N × N similarity matrix. In addition, its computational complexity is in O(N 3 ) which seems to prohibit its use in our setup, where the number of data points can go up to 10 6 .

A mechanism to overcome this complexity is to use a sparse anity matrix e.g., by thresholding its entries and ecient sparse eigensolvers such as the Lanczos method [START_REF] Shi | Motion segmentation and tracking using normalized cuts[END_REF]]. With our dense tracklets, the anity matrix is not sparse and thresholding its entries still requires the evaluation of all similarities. Thresholding has also side-eects that are not well understood [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]]. For instance, thresholding a kernel matrix is known to not preserve its positive-deniteness. Therefore, we choose to use the Nyström method in order to eciently compute an approximate spectral embedding.

Nyström approximation

The Nyström method [START_REF] Nyström | Über die praktische auösung von integralgleichungen mit anwendungen auf randwertaufgaben[END_REF]] is a technique for nding numerical approximations to eigenfunction problems and has been introduced in the context of spectral clustering in [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]]. It allows to extend an eigenvector computed for a subset of points to any arbitrary point, while requiring only a subset of the columns (or rows) of the similarity matrix W (see Figure 4.3 for an illustration). As observed by [START_REF] Williams | Using the nyström method to speed up kernel machines[END_REF], it is related to kernel PCA [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF]].

Let A be the n × n similarity matrix between a subset of n randomly sampled tracklets, with n ≪ N , and let B be the n × (Nn) similarity matrix between this subset and all other tracklets. With no loss of generality, we assume the samples sorted such that we can rewrite the full N ×N similarity matrix W as: -n) , C being in general too expensive to compute as N ≫ n. Note that in our case W and A are positive-denite.

W = A B B T C (4.5) with A ∈ R n×n , B ∈ R n×(N -n) and C ∈ R (N -n)×(N
Let A = U A Λ A U T A be the eigendecomposition of A. The matrix form of the Nyström extension is B T U A Λ -1
A . The approximate eigenvectors Û of W given by the Nyström method are: Note that Û are also the eigenvectors of the approximation Ŵ of W :

Û = U A B T U A Λ -1 A (4.6)
Ŵ = Û Λ A Û T = A B B T B T A -1 B (4.7)
It shows that the Nyström method implicitly approximates C using B T A -1 B.

Thus, the quality of the approximation can be measured by the norm of the Schur complement C -B T A -1 B , which measures how well C is spanned by the rows of B. Consequently, the subset of rows of W must be chosen such that the corresponding tracklets span all underlying true clusters to be discovered. Therefore, to ensure good diversity and coverage, we randomly subsample p tracklets per cell of a spatio-temporal grid over the whole video (cf. Figure 4.3). The grid granularity and p can be adapted dynamically to the total number of tracklets and the available computational resources. Similarly to [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF], we observed that good results can be obtained with less than 1% of the total number of points.

As observed in [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]], the columns of Û are not orthogonal. However, as A is positive-denite in our case, we can apply the one-shot technique of [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF] and compute the orthogonalized approximate eigenvectors of W in one step as follows. Let S = A + A -1/2 BB T A -1/2 , where A -1/2 is a pseudo-inverse of a symmetric positive denite square root of A.

Let S = U S Λ S U T S be the eigendecomposition of S. As shown in [Fowlkes et al. 2004], Ŵ is diagonalized by V and Λ S , where:

V = A B T A -1/2 U S Λ -1/2 S (4.8)

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

Note that in the context of NCut, A and B must be normalized by the rowsums d of Ŵ beforehand. This can be done without computing the expensive B T A -1 B block of Ŵ by:

A i,j ← A i,j di dj , B k,l ← B k,l dk dl+n , (4.9) i, j, k = 1, • • • , n, l = 1, • • • , N -n where d = Ŵ 1 N = a r + b r b c + B T A -1 b r (4.10)
with 1 N the column vector of N ones, a r , b r ∈ R n the row-sums of A and B, and b c ∈ R N -n the column-sums of B. After normalizing A and B (eq. 4.9, 4.10) and computing V (eq. 4.8), the spectral embedding E is:

E i,j = Vi,j+1 Vi,1 , i = 1, • • • , N, j = 1, • • • , N E , (4.11)
As we are in a large scale, realistic set-up, special care must be taken with respect to numerical stability. Indeed, even though A is positive-denite, it is in general ill-conditioned. Therefore, we use a robust pseudo-inverse algorithm to compute A -1 by thresholding the lower-end of its spectrum. We also follow some useful guidelines from [START_REF] Foster | Stable and ecient gaussian process calculations[END_REF]]. Note that the overall computational cost of this approximate spectral embedding is in O(n 2 N ) time and O(nN ) space, which is a large improvement over the O(N 3 ) time, O(N 2 ) space complexity of the exact method.

Hierarchical divisive clustering

Using the computed spectral embedding, we cluster tracklets via an ecient hierarchical divisive algorithm. The pseudo-code of our approach is given in algorithms 1 and 2. We adopt a top-down approach that consists in recursively bi-partitioning the set of tracklets (cf. Figure 4.1). We split a set of tracklets in two by thresholding along an eigenvector, i.e., along a dimension of the spectral embedding. As the second smallest eigenvector is the realvalued solution to the Normalized-Cut (NCut) problem, it is composed of two clearly separated ranges of values that indicate the optimal partition of the tracklets. This argument is also valid for the next leading eigenvectors and, theoretically, one can optimally sub-partition the data by recursively thresholding one eigenvector after the other. However, several practical problems need to be taken into account while following such an approach.

Algorithm 1 spectral_division 1: Input: features of N tracklets (cf. section 4.2.2) 2: Output: the cluster-tree (hierarchical set of nodes) # Compute the spectral embedding 3: Compute the slice [A B] of W (cf. g. 4.3) 4: Normalize A and B (eq. 4.9, 4.10) 5: Compute the embedding E (eq. 4.8, 4.11) # Initialize priority queue over nodes to be split 6: to_split ← empty priority queue of nodes 7: Push the root of the cluster-tree on to_split # Recursively split nodes according to priority 8: while to_split is not empty do 9:

node ← pop highest priority node from to_split end if 15: end while First, the optimal bi-partition is often unclear in realistic conditions and the eigenvectors tend to reect this ambiguity by having smooth variations. Therefore, which threshold to use is in general unclear when looking only at eigenvector values. Furthermore, thresholding a smoothly varying eigenvector can lead to an unstable partition, as a small change in the threshold signicantly modies the partition.

The rst technique we use to address this stability problem is based on a criterion similar to the one mentioned in [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. If the variations of an eigenvector are below a small threshold, then we do not attempt to split along this eigenvector. We used 10 -10 as threshold in our experiments. More importantly, we propose to circumvent the diculties posed by smooth eigenvectors by nding the threshold that maximizes a model selection score based on spatio-temporal information (cf. Algorithm 2). We experimented with multiple spatio-temporal consistency criteria, such as inertia or label agreement amongst neighbors, but the one that yielded the best results in our experiments is the connectedness measure described in the following.

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

Connectedness score of a node

Let G = (V, E) be a spatio-temporal k-nearest neighbor graph over the tracklets V in a video: (v i , v j ) ∈ E if and only if v i , v j ∈ V are k-nearest neighbors according to their spatio-temporal positions. We dene the connectedness score c(V ′ ) of a subset of tracklets V ′ ⊂ V forming a node in the cluster-tree as: c(

V ′ ) = |C(V ′ )| -1 , where C(V ′ ) is the set of connected components of the subgraph G(V ′ ) of G.
Maximizing this connectedness score has a strong advantage over the minimization of distortion-based measures such as inertia: it does not constrain the shape of the clusters. Furthermore, it does not enforce tube-like clusters, but only encourages spatio-temporal contiguity of the tracklets in order to avoid clearly spatio-temporally disjoint parts in the same node. Connectedness is also not biased with respect to node size. In addition, it can be eciently obtained along the course of our divisive algorithm by pre-computing once during an initialization step the full spatio-temporal adjacency matrix of all tracklets in the video. We compute this sparse matrix using kd-trees on the average spatio-temporal position of tracklets to determine the graph of approximate k-nearest neighbors. As this is fast to compute, including for hundreds of thousands of tracklets, we select the smallest k such that the entire video has exactly one spatio-temporally connected component. This yields approximatively k = 10 neighbors on average over all videos. Once the neighborhood graph is built, computing the number of connected components of a subgraph is done in linear time by a depth-rst search. This connectedness score is specic to a node in the cluster-tree, and when deciding whether a split improves performance, we compare the score of the parent node with the lowest score of its children resulting from a candidate split (cf. Algorithm 2). The score of a node is also employed to determine the order used to choose the nodes to split. We use a priority queue to split nodes with the lowest score rst, as they are those with the maximum expected gain.

As outlined in Algorithm 1, at each iteration, we retrieve the highest priority (lowest score) node, attempt to split it, and, if it is not a leaf, we push its children to the priority queue. We observed that, in general, this choice of priority leads to a depth-rst construction of the cluster-tree, with occasional jumps to higher nodes (i.e., backtracking). Ties in priority are handled by picking the largest node, then the node closer to the root.

Note that we do not use the NCut value as score for two reasons. First, as we compute an approximate spectral embedding using the Nyström method, we do not have access to the full similarity matrix W , and computing the NCut value would therefore be prohibitively expensive. Second, smooth variations in an eigenvector yields smooth variations in the NCut value, which, consequently, cannot be used reliably to nd a good split.

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

The second issue faced when adopting a recursive thresholding approach, is that there is an accumulation of approximation errors that makes higher eigenvectors less reliable. We, therefore, use this natural ordering of the eigenvectors in order to nd a good split. We adopt a greedy strategy depicted in Algorithm 2. We rst try candidate thresholds along the leading eigenvector. In our experiments, we use nine adaptive thresholds corresponding to the 10 th , 20 th , . . . , 90 th percentile of the considered eigenvector values, in order to avoid severe imbalance between nodes at the same depth in the cluster-tree.

If the best split along this eigenvector improves with respect to the score of the parent node that we try to split, then the split is registered with this eigenvector-threshold pair. Otherwise, we iteratively try to split along the next leading eigenvector, until we reached the last one. We observed that less than 20 eigenvectors are generally used. For each node, we start again from the leading eigenvector, as suggested in [START_REF] Shi | Normalized cuts and image segmentation[END_REF], because it is the most reliable one, and we observed that, in practice, the leading eigenvectors might be decomposed over several approximately at plateaus. The only hyper-parameters of our divisive algorithm are the minimum and maximum leaf sizes: m and M . They are employed in order to avoid degenerate i.e., too large or too small leaves, a frequent problem faced by central grouping methods such as k-means. If a node to be split contains less than 2m tracklets, we automatically mark it as a leaf. If a node is larger than M , we force the split by using the best eigenvector-threshold pair, even if the scores of the children nodes are lower than the score of the parent (cf.

Algorithm 2). We used m = 200 and M = 2000 in our experiments.

Classication of cluster-trees

In this section, we rst explain how we represent each node in the cluster-tree as a histogram of quantized tracklet features. We then introduce a tree kernel to eciently compare cluster-trees for activity recognition.

Tracklet descriptors for classication

As described in Section 4.2.2, we use simple discriminative tracklet descriptors in the video-specic clustering stage, because all tracklet comparisons remain inside the same video. In the classication stage of our method, however, we compare the content of dierent videos. Therefore, recognition requires more robust features in order to build models that can handle the large intra-class variability of activities in real-world videos. Consequently, we choose to represent a tracklet using Motion Boundary Histograms (MBH) [Dalal et al. 2006, 4.3. CLASSIFICATION OF CLUSTER-TREES 71 Wang et al. 2011]. It consists of two histograms quantifying the gradients of the horizontal and vertical components of the optical ow. As shown in [Wang et al. 2011] for the bag-of-features model, using MBH to describe tracklets allows for better action recognition than when using trajectory information.

As MBH relies on the derivatives of the optical ow, it suppresses constant motion information and focuses on representing motion boundaries, i.e., local changes of orientation in the motion eld. Therefore, it can be robust to a certain amount of camera translation, but not to more complex movements such as rotations. In addition, MBH allows to robustly handle the noise in the spatial derivatives of the optical ow via quantization.

Note that we found that MBH is not adapted as a clustering feature for over-segmentation. Its robustness, indeed, can yield large clusters containing multiple distinct objects moving in the same manner, e.g., soccer players running on a soccer eld, which, in spite of their dierent spatio-temporal locations, cannot be separated according to MBH features.

Contrary to the clustering stage, we only use one descriptor here. Results presented in [Wang et al. 2011] have shown that further moderate classication improvements can be achieved by combining MBH with trajectory, HOG, and HOF information, at the expense of signicantly increased computational cost.

We use the same parameters as in [Wang et al. 2011] to eciently compute tracklet-aligned MBH descriptors directly from the dense optical ow eld used to obtain the tracklets.

BOF-Tree: tree of nested bag-of-features

As a node is a motion component composed of a diverse set of tracklets, we propose to eciently encode this diversity with a bag-of-features (BOF). Note that we could also represent a node's content with the average of its tracklets. However, this has several limitations in our situation. First, there is a potentially large number of points per node, which makes a node qualitatively dierent from a super-tracklet, especially at a low depth in the cluster-tree.

Second, as our clustering algorithm uses dierent features than the ones used for classication, there is, in general, a high variability of tracklet descriptors in a node, i.e., a large dispersion around the centroid. In addition, the spatiotemporal consistency of the nodes is not strictly enforced. Thus, the global shape of our nodes may not be discriminative, due to holes and noise caused by our approximate clustering algorithm. In contrast, the BOF representation has proven to be a reliable way to describe entire videos as well as smaller temporal action units [Gaidon et al. 2011a]. We adopt the common pipeline described in the following.

From the set of MBH descriptors and the cluster-tree obtained by our spectral divisive algorithm, we extract a hierarchical representation of a video called BOF-tree. Its structure is the same as its corresponding cluster-tree.

In addition, each node in the BOF-tree is modeled by a bag-of-features. See As a consequence of the clustering, the left-to-right order in the BOF-tree does not have any geometrical interpretation (the cluster-tree is unordered ).

The only semantic relation directly captured by our tree structure is the inclusion relation derived from the cluster-tree: the two children of a node correspond to a bi-partition of the tracklets of this parent node. This induces an additive property on the nodes of a BOF-tree: the BOF of a node in a BOF-tree is the sum of its children's BOFs (cf. Figure 4.4). We now show how to use this property to eciently compare BOF-trees, while leveraging the hierarchical structure information between nodes. Let T 1 = (V 1 , E 1 ) and T 2 = (V 2 , E 2 ) be two BOF-trees, dened from their set of vertices (nodes) V i and directed edges (parent-child relations

) E i . Each node v ∈ V i is represented by a BOF, noted b[v], over its constitutive tracklets. We model a directed edge e = (v p , v c ) ∈ E i by the concatenation b[e] = (b[v p ], b[v c ]
) of the BOF of the child node v c with the BOF of its parent node v p . Let h be a kernel between BOF. We use the intersection kernel [Maji et al. 2008] between L 1 -normalized histograms:

h(x, x ′ ) = j min( x j x 1 , x ′ j x ′ 1 ) (4.12)
Let r i ∈ V i be the root of T i , i ∈ {1, 2}. Our ATEP kernel is dened as:

k(T 1 , T 2 ) = w r • h(b[r 1 ], b[r 2 ]) + 1 -w r |E 1 ||E 2 | • e 1 ∈E 1 e 2 ∈E 2 h(b[e 1 ], b[e 2 ]) (4.13)
As the roots have no parents, they are handled separately in this kernel:

w r ∈ [0, 1] is a cross-validated parameter encoding a prior on the importance of the root-to-root comparisons. Note that the case w r = 1 corresponds to the standard global BOF model with the intersection kernel.

This kernel relies on hierarchical relations: a node only depends on its parent. It can be seen as a similarity between all sub-trees of two BOFtrees. Let a direct family (v, s(v), p(v)) denote, respectively, a non-root node v ∈ V i \r i , its only sibling s(v), and its parent p(v). The additive property of BOF-trees is formulated as b

[v] + b[s(v)] = b[p(v)]. Therefore, (b[v], b[p(v)])
completely characterizes a direct family. In addition, the BOF b[v] is the sum of all the BOFs of its descendants. Consequently, (b[v], b[p(v)]) can be seen as an approximation of the content of the sub-tree rooted at p(v). Therefore, the ATEP kernel eciently compares all sub-trees by using only one level of hierarchy at a time to compare two motion components. Note that if the node kernel h is positive denite, then our ATEP kernel is also positive denite (it is a sum of positive denite kernels). We can, therefore, use it directly in conjunction with a SVM classier [START_REF] Schölkopf | Learning with Kernels[END_REF]. For multi-class classication, we adopt the One v.s. Rest approach.

Experiments

In this section, we report the results obtained with our approach and compare it to both the state of the art and several baselines.

Activity datasets

We evaluate our method on two publicly available benchmarks: the High Five The Olympic Sports dataset [Niebles et al. 2010] contains 783 Youtube videos of athletes practicing 16 dierent sport activities such as springboard diving and weight lifting (cf. Figure 4.6). This dataset contains longer video sequences of fast and complex articulated human motions, possibly involving interactions with objects (e.g., a javelin). It presents several challenges, such as cluttered backgrounds, low quality videos, compression artifacts, and subtle distinctions between some categories (e.g., triple jump and long jump). In addition, the activities are composed of multiple simpler actions (e.g., running and jumping) that can be shared across categories, which is a great challenge for part-based recognition. Dierent actions might, indeed, contain the same parts, but arranged in a dierent manner. This justies the need to leverage the spatio-temporal structure of activities in order to better distinguish them. Although motion stabilization is not necessary with our approach, it allows to remove the camera motion bias of a dataset. Some video sources and sports videos in particular tend to be lmed in a manner that is strongly correlated with the action performed. For instance, in the stabilized frames of Figure 4.7 (bottom row), we can see the rapid downward tilt of the camera as it follows the landing of the jumper. Such camera motion biases are consistently present in the Olympic Sports dataset and characterize to some extent the action performed. When using dense tracklets, camera motion is directly encoded by the features. Furthermore, the background tracklets will share similar motion statistics as they mostly correspond to the movement of the camera. As can be seen in gure 4.8, in the non-stabilized case (top row), the camera motion yields many consistent tracklets on the background, while in the second case most motion is on the moving objects (the jumper and the referee). Thus, in the nonstabilized case, we observed that our clustering approach may result in hierarchical decompositions, of which discriminative, large sub-trees are formed by background tracklets. Therefore, we report results on stabilized video for the Olympic Sports dataset. That way, our evaluation is independent of any (positive or negative) camera motion bias and only quanties the eciency of our action model. Note that the High Five clips do not suer from camera motion bias. We, therefore, present results on the original non-stabilized video sequences for this benchmark. Camera motion stabilization under uncontrolled video conditions is a dicult task. Although ecient approaches exist for simple transformations, e.g., phase correlation [START_REF] Castro | Registration of translated and rotated images using nite Fourier transforms[END_REF] for translations, only few can address all kinds of complex, time-varying camera motions, such as camera shake in amateur videos, or out-of-plane rotations coupled with zooms in movies. Here, we follow [Ikizler-Cinbis and Sclaro 2010, [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF] i.e., we explicitly model the camera motion to generate stabilized videos. The optical ow in these videos corresponds to the full ow in the original video, from which the estimated background ow was subtracted (cf. Figure 4.8).

We use simple and ecient image-stitching techniques to compute the approximate motion of a background plane. First, we extract salient 2D Harris interest points in frames which we represent with SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]] descriptors. We, then, robustly match the interest points using RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model tting with applications to image analysis and automated cartography[END_REF] and estimate the transformation between all pairs of adjacent frames. Finally, we produce a stabilized video where all frames are warped according to the estimated transformation (cf. Figure 4.7). Note that the trajectories of points on the warped frame boundaries are ltered out and not included in our models.

Baselines

We rst compare to two simple baselines using a global BOF model over the entire video [START_REF] Laptev | Learning realistic human actions from movies[END_REF], Wang et al. 2011]. The approach of [START_REF] Laptev | Learning realistic human actions from movies[END_REF] uses sparse local Spatio-Temporal Interest Points (STIPS) [START_REF] Laptev | On space-time interest points[END_REF]] described by a concatenation of histogram of oriented gradients [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and optical ow, denoted HOG/HOF. The approach of Wang et al. [2011] uses dense tracklets represented by MBH descriptors. Note that this method corresponds to using only the model of the root node of our BOF-trees. In both cases, we use our own implementation of the method with the same vocabulary construction and size as mentioned previously.

In addition to these unstructured baselines, we compare our approach with decompositions obtained by alternative clustering methods. First, we compare to two standard at clustering algorithms that produce a set of unrelated clusters: k-means and spectral clustering. Due to the large amount of tracklets per video, we adopt an ecient on-line variant of k-means [Sculley 2010].

For spectral clustering, we adopt the approach of [START_REF] Fowlkes | Spectral grouping using the Nystrom method[END_REF]: we partition tracklets with (on-line) k-means on the same approximate spectral embedding used by our method. These two algorithms take as input a xed number of clusters. However, dierent videos contain dierent numbers of distinct motion components. Therefore, we use a number of clusters that depends linearly on the number of tracklets, such that the smallest videos have at least 2 clusters, whereas the largest ones have at most 1000 clusters.

We also compare our approach to a closely related baseline yielding a cluster-tree. Its steps are all similar to our method except for one: we replace the spectral divisive thresholding algorithm of Section 4.2.4 (noted SDT) by a recursive application of k-means. This amounts to splitting a node with (on-line) k-means (k = 2) on the spectral embedding. The algorithm is noted SDKM for Spectral Divisive K-Means. Like with our approach, we classify the resulting cluster-trees using a SVM with our BOF-tree kernel.

Note that in order to compare unrelated sets of clusters, we use a natural simplication of our ATEP kernel consisting in averaging all pairwise cluster comparisons between two videos. This baseline kernel is noted as ACP for All Cluster Pairs. It can be applied on the clusters resulting from the at clustering algorithms, the leaves of a BOF-tree, or on all nodes of a BOF-tree (including internal ones) in which case the hierarchical relations are ignored. [Wang et al. 2011] 53.5 BOF STIPS [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 36.9 Patron-Perez et al. [2010] 32.8 (b) High Five (AP in %) Table 4.2: Performance comparison on the Olympics Sports [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF] and High Five [START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF] datasets.

First, we found that our hierarchical ATEP kernel on SDT BOF-trees in conjunction with a SVM outperforms the state of the art on both datasets, including latent part models [START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF]] (+12.9%), complex graphical models resulting from video segmentation [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF] (+7.7%, cf. Figure 4.9 for per-class details), and interaction-specic structured learning [START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF]] (+23.7%). Second, our approach improves over the BOF baselines. This conrms the importance of leveraging structure information to recognize complex activities. Note, however, that only our method yields clear performance improvements, whereas other structured baselines are less accurate. This shows that decomposing activities is as challenging as it is critical for performance.

Third, using hierarchical relations between motion components with our ATEP kernel consistently improves over the at baselines, which rely on unrelated sets of clusters, e.g., the leaves of BOF-trees or clusters obtained by k-means. We also observe a similar improvement when comparing the performance of our ATEP kernel with its unstructured counterpart (ACP) on the full BOF-trees (cf. Finally, table 4.2 also shows that the BOF-trees produced by our SDT algorithm yield more powerful models than the SDKM ones obtained by bipartitioning k-means (+7.2% on Olympic Sports, +1.2% on High Five).

Discussion on the Olympic Sports results

Figure 4.11 is the confusion matrix of our method on Olympic Sports. We can see, for instance, that triple jump is often predicted as the similarly structured long jump (the only dierence between the two categories is the middle of the activity). In addition, high jump is often wrongly predicted as javelin throw due to their similar structure (running, then hopping, followed by a fast upwards motion). Another frequent confusion is between the tennis serve and discus throw actions, which both involve a long preparation time with only few movements, followed by a short and fast motion.

As can be observed in Figure 4.10, our hierarchical method yields the largest improvements on the bowling and basketball layup classes. Both of these activities involve a clear spatio-temporal structure that is captured by our cluster-trees. Furthermore, they contain large motions (e.g., running)

as well as fast and short motion parts that are characteristic for the category (e.g., the layup gesture, or the arm movement when throwing the bowling ball). Our model can separate these components, whereas averaging models like BOF will be dominated by the largest clusters of tracklets, thus losing the discriminative information present in the motion parts with less tracklets.

The vault (gymnastics) activity is the only category where our method degrades performance with respect to its unstructured counterpart (ACP kernel on SDT BOF-Trees, cf. Table 4.2 also shows that the performance improvements on the High Five dataset are less signicant than on the Olympic Sports benchmark. This can be explained by several factors. First, the interactions contained in the High Five dataset are shorter and are, therefore, decomposed over smaller trees with less structure. Second, all interaction categories are close and share both common motion parts and relations between them (some are visible in Figure 4.5). Note that the per-class improvements on the High Five dataset are all roughly equal. Third, the High Five dataset contains additional random negative videos both in the training and test splits that have no particular motion structure, and, thus, increase the noise level. When removing these random negatives from the test samples, our method reaches 66% in mean Average Precision, which represents a +27% improvement over the results of [START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF] in the same settings (39% mean AP).

Results for simpler actions

In addition to the previously described experiments on activity recognition, we investigated the performance of our method on simpler actions from the HMDB dataset [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF]] (cf. Figure 4.12 for frames extracted from some clips of the database).

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

This benchmark is composed of 6849 clips from dierent real-world sources such as Youtube videos, TV footage, and movies. It contains 51 action categories that entail general facial actions (e.g., smile, laugh, talk), facial actions with object manipulation (e.g., smoke, drink), general body movements (e.g., cartwheel, climb, walk, wave), interactions with objects (e.g., dribble, golf), and person-person interactions (e.g., hug, kiss, punch). Each action is performed in at least 101 clips. Performance is evaluated by the mean accuracy over all classes averaged over three xed dierent train/test splits provided by the authors. HMDB is a challenging dataset: the current state of the art [START_REF] Sadanand | Action bank: A high-level representation of activity in video[END_REF]] is of 26.9% accuracy only. This highlights the diculties of this dataset, which include poor video conditions (only 17% of high quality clips), partially visible actors (in 44% of the videos), camera motions, and a large variety of viewpoints. In addition, another diculty is caused by the presence of close pairs of classes such as chewing v.s. talking, shooting a gun v.s. shooting a bow, fencing v.s. sword exercise.

We use this dataset in addition to the previous ones because of their complementarity. On the one hand, the actions in the Olympic Sports dataset are longer, more complex activities with 230 frames per action on average. They are composed of multiple simpler actions (e.g., running and jumping) that can be shared across categories, which is a great challenge for part-based recognition and justies the need to leverage the spatio-temporal structure of actions. On the other hand, HMDB actions some of which are parts of the more complex Olympic Sports activities tend to be both simpler and shorter with 90 frames per action on average, but they are more numerous and varied. Note that we use the on-line available stabilized version of HMDB.

Our method (ATEP kernel on SDT BOF-Trees) obtains an average classication accuracy of 41.3%, which corresponds to a +14.4% improvement over the state of the art. This improvement is in large part due to our use of tracklets combined with the MBH descriptor. Indeed, the performance of our BOF baseline i.e., using only the root of our BOF-trees reaches 38.9% accuracy. Figure 4.13 contains the confusion matrix for our method. The classes are clustered by confusion, according to a 1D projection obtained by Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] on the rows of the confusion matrix. The actions most often confused are the facial actions visible in the top left corner of the confusion matrix: chew, smile, talk, and laugh. They all involve only few tracklets depicting consistent movements of the head and facial muscles that are too simple and too small to decompose. Other common confusions include smoke v.s. eat v.s. drink, draw sword v.s. sword exercise, and actions at the bottom-right corner of the confusion matrix (swing baseball, throw, jump, kick, kick ball, and fall oor), which generally involve a single, fast, uni-directional, translation movement.

Difference in accuracy

Improvement of ATEP on the full SDT trees over the BOF baseline (i.e. only roots)

Figure 4.14: Performance improvement of our method over the BOF baseline on the HMDB dataset [START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF].

CHAPTER 4. ACTIVITIES AS CLUSTER-TREES OF TRACKLETS

Figure 4.14 contains the per-class performance dierences between our method and the BOF baseline. We can observe that, although the improvement is limited on average over all categories (+2.4%), the majority of the actions clearly benet from our hierarchical decomposition. For instance, the push category is signicantly improved (+9%), because it consists in the interaction between a human and an object (a cart). Similarly, our method improves the recognition of the human-human interaction shake hands (+9%), and other interactions, e.g., shoot gun, pour, and kiss.

Some actions, on the other hand, are negatively impacted by our method.

However, as we cross-validate the per-class root weight w r in ATEP (Equation 4.13), and as the case w r = 1 corresponds to the BOF baseline, it should not be possible, in theory, for our method to perform worse than BOF. In practice, however, the limited training set size does not guarantee that the best parameters on the test set are those with maximum cross-validation performance. The performance degradation observed for some classes suggests that there is not a clear and stable value for the best root weight parameter of these actions. In particular, the performance on the walk action is smaller (-8%) with our model than with the BOF baseline. Indeed, the motions of the legs are sometimes either too close to each other to be separated, or are not visible. Furthermore, videos of this category often involve a wide array of contexts, most of which contain the unrelated motions of other objects or actors. These distractors result in spurious nodes in our cluster-trees, and negatively aect our kernel, as we rely on the full cluster-tree structure. Note that we did not observe such performance degradation on the activities of the Olympic Sports and High Five datasets: our ATEP kernel on SDT BOF-Trees performed equally or better than the BOF baseline on all activities.

Conclusion

We introduced an ecient hierarchical clustering algorithm on short duration point trajectories (tracklets). Our approach relies on recursive bi-partitioning using a spatio-temporal connectedness criterion to threshold the projection of tracklets on a multi-modal spectral embedding obtained with the Nyström approximation. A video is structured as a tree of nested motion components.

Each one of these data-driven parts is represented by a bag-of-features over local motion descriptors in order to form our BOF-Tree activity model. We also proposed a kernel on unordered binary trees, which can accurately compare activities with a variable number of hierarchically ordered parts. This kernel uses an additive property of our motion decomposition to eciently compare sub-trees and leverages structure information to rene part comparisons.

CHAPTER 5. TIME SERIES KERNELS FOR ACTIONS

Introduction

Action recognition in realistic videos has been previously addressed using kernel methods like SVMs. Most existing approaches, however, extract xedlength vector representations of video volumes (e.g., a bag-of-features of an entire video or of each part like in previous chapters), and compare them using generic kernels on vectors. In contrast, in this chapter we model actions as time series of per-frame representations, and propose a kernel specically tailored for the purpose of action recognition, which hinges upon distances between models of action dynamics. Dynamic aspects alone are likely to be insucient to describe some types of actions, especially when the scene or the nature of objects involved are discriminative. Therefore, our goal is to show that our kernel on dynamics complements orderless aggregation statistics (cf.

Figure 5.1), which have proved ecient in this context. We propose to encode the statistical dependency information of an action example by using its auto-correlation operator, i.e., the cross-correlation in a Reproducing Kernel Hilbert Space (RKHS) [START_REF] Schölkopf | Learning with Kernels[END_REF] of the signal of frames with a temporally shifted version of itself. The autocorrelation operator contains information pertaining to the temporal dependencies between frames and the temporal structure of actions, as it depends on the ordering of the frames. Hence, we propose to compare the dynamics of two actions by computing the distance between their respective auto-correlations.

This distance is dened as the Hilbert-Schmidt norm of the dierence between auto-correlations and we call the associated Gaussian RBF kernel the Dierence between Auto-Correlation Operators (DACO) kernel (see gure 5.2 for an illustration). Note that this is dierent from the cross-correlation between

Closest references

Though good results were achieved with models aggregating statistics of local features over the entire duration of an action (cf. [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF]] for a recent evaluation), these action models can be enhanced by treating the time dimension dierently from the spatial ones. For instance, Niebles et al.

[2010] propose a latent model of temporal parts for long duration activities, and Gaidon et al. [2011a] model the temporal structure and ordering constraints of actions as sequences of actoms. These methods only encode the coarse temporal structure, and, therefore, fail to capture dynamic aspects like the temporal dependencies between frames. Another limitation of volumetric approaches is that the temporal granularity is not taken into account. The visual dierence between two frames is, indeed, much more pronounced than the dierence between two pixels, as fast discriminative motions often occur in less than ten frames.

One of the simplest ways to represent actions and their temporal structure is just to concatenate, in the temporal order, per-frame feature vectors. [START_REF] Schindler | Action snippets: How many frames does human action recognition require[END_REF] show that such a simple technique can yield good results in simple video conditions. However, their approach assumes that videos are synchronized in time beforehand. Consequently, it is not robust to signicant variations in action speed.

A more sophisticated approach based on chaos theory is used by [START_REF] Basharat | Time series prediction by chaotic modeling of nonlinear dynamical systems[END_REF]. They model repetitive human actions and dynamic textures as nonlinear dynamical systems. They use strange attractors to represent the dynamics of time series for action and dynamic texture synthesis, yet do not provide a way to compare two series of observations.

Other approaches, inspired by speech and gesture recognition, represent actions as sequences of states [START_REF] Brendel | Activities as time series of human postures[END_REF][START_REF] Jung | Action video retrieval based on atomic action vocabulary[END_REF][START_REF] Kulkarni | An unsupervised framework for action recognition using actemes[END_REF][START_REF] Nowozin | Discriminative subsequence mining for action classication[END_REF]], or use dynamic probabilistic graphical models [START_REF] Brand | Coupled hidden Markov models for complex action recognition[END_REF][START_REF] Laxton | Leveraging temporal, contextual and ordering constraints for recognizing complex activities in video[END_REF][START_REF] Yamato | Recognizing human action in timesequential images using hidden markov model[END_REF][START_REF] Zeng | Knowledge based activity recognition with dynamic bayesian network[END_REF] to model the temporal aspects of the videos. These methods, however, only measure alignments between videos. Hence, they are not robust to temporal occlusions, and signicant duration variations. Furthermore, they generally involve a dicult intermediate recognition step, for instance by labeling each frame.

Both alignment-based approaches computing a matching score between videos and aggregation-based techniques discarding most temporal aspects by averaging over frames do not take into account characteristic dynamic information, such as repeating patterns, or the relationships between frames. In contrast to these previous works, we represent videos directly as time series of frames and propose to compare actions through models of their key dynamic aspects.

Note that our DACO kernel diers from existing kernels on time series. [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF] proposed a kernel based on Dynamic Time Warping, with applications to speech recognition tasks. However, this kernel does not compare the dynamics but measures alignments between time series. Another example of time series kernel is given by [START_REF] Lu | A reproducing kernel Hilbert space framework for pairwise time series distances[END_REF], with applications to synchronized EEG segments. However, their similarity between two time series corresponds to similarity between temporal regularity, in the spirit of the functional data analysis framework [START_REF] Ramsay | Functional Data Analysis[END_REF].

Outline

We introduce our time series representation of videos and our novel DACO kernel in Section 5.2. We give a practical formulation that can operate on any type of frame model, including high-dimensional ones like BOF, in Section 5.3.

KERNEL ON AUTO-CORRELATION OPERATORS

93

DACO only requires a kernel function on frames (e.g., the intersection kernel between histograms), and computes auto-correlation operators in the feature space induced by this kernel. Section 5.4 contains experimental results on recent action recognition datasets, showing that a simple linear combination of our DACO kernel and an aggregation-based kernel can improve recognition performance. In addition, we show the superiority of DACO over alternative kernels on time series.

Kernel on auto-correlation operators

Let X a space of frame representations (e.g., histograms of visual words). Let a video x = (x t ) t=1•••T of duration T frames represented as a time series where x t ∈ X . We dene the space of videos S = i>0 X i . Our goal is to design a kernel k S : S × S → R adapted to compare actions. In Section 5.2.1, we quickly recall the main properties of the auto-correlation, which is the base mathematical component of our approach. In Section 5.2.2, we give the denition of our auto-correlation-based kernel and some details.

Auto-correlation operators

We model the dynamics of an actions x = (x t ) t=1,••• ,T (a time series of frames) with its corresponding auto-correlation operator ρ(x) τ , i.e., the series's sampled auto-covariance, Σ(x) τ , normalized by its sampled covariance, Σ(x) :

ρ(x) τ = Σ(x) + γI -1 Σ(x) τ (5.1)
where γ is a regularization parameter, and τ is a time lag in frames. The autocovariance of a time series is simply dened as the cross-covariance between the series and a temporally shifted version of itself. For a time series (X t )

with mean E[X t ] = µ t , the auto-covariance at time t and lag τ is dened by

Σ (x) (t, t + τ ) = E [(X t -µ t ) ⊗ (X t+τ -µ t+τ )] = E [X t ⊗ X t+τ ] -µ t ⊗ µ t+τ (5.2)
where ⊗ denotes the tensor product operation. Note that Equation 5.1 makes the assumption that all time series are wide sense stationary, i.e., that rst and second order moments do not vary with time. We show in our experiments (Section 5.4) that this approximation yields reasonable results in practice for short actions.

We note the mean µ = µ t and the auto-covariance

Σ (x) τ = Σ (x) (t, t + τ ),
which only depends on the lag τ . Their sampled versions estimated from the observation of the frames are noted μ and Σ(x) τ .

The auto-covariance contains information pertaining to the temporal dependencies between frames, e.g., repeating patterns. It is a special case of cross-covariance, which has some interesting statistical properties. The Hilbert-Schmidt Independence Criterion (HSIC) [START_REF] Gretton | Measuring statistical dependence with Hilbert-Schmidt norms[END_REF] between two random variables X ∼ P X , Y ∼ P Y is a statistical dependency measure using the squared Hilbert-Schmidt norm of the cross-covariance operator between X and Y in some kernel-induced feature space: Σ (x,y) 2 HS . Gretton et al. [2005] prove that, under certain conditions, Σ (x,y) 2

HS is zero if and only if the random variables X and Y are independent. Furthermore, they show that it can be estimated using only kernel evaluations between i.i.d. sampled observations of X and Y .

However, contrary to [START_REF] Gretton | Measuring statistical dependence with Hilbert-Schmidt norms[END_REF], we are dealing with non-i.i.d.

observations of frames, and dierent actions might be statistically dependent (e.g., walking and running). Therefore, we propose to compare time series by computing the distance between their dynamics, modeled by their respective auto-correlation operators.

The DACO kernel

We dene our Dierence between Auto-Correlation Operators (DACO) kernel from the Hilbert-Schmidt norm of the dierence between auto-correlations:

k DACO (x, y) = exp - 1 2σ 2 d DACO (x, y) 2 where d DACO (x, y) = ρ(y) τ -ρ(x) τ HS (5.
3)

The Hilbert-Schmidt norm, noted • HS , is simply the extension of the Frobenius matrix norm to any separable Hilbert space, and can be dened for any bounded operator A as:

A 2 HS = Tr (A * A) (5.4) where Tr denotes the trace function and A * is the conjugate transpose of A.

It derives from the Hilbert-Schmidt inner product:

A, B HS = Tr (A * B) (5.5) This allows us to decompose the DACO distance in three terms:

d DACO (x, y) 2 = ρ(x) τ HS + ρ(y) τ HS -2 ρ(y) τ , ρ(x) τ HS (5.6)
As the norm of the auto-correlation operator measures the dependency between a series and a shifted version of itself, we can see from Equation 5.6 that the distance will tend to be smaller for time series with almost no temporal structure (e.g., for random sequences of frames), and bigger for actions with quasi-deterministic relationships between neighboring frames (e.g., a constant translation movement). In addition, the inner product in Equation 5.6 shows that if the dynamics of the two series x and y are dierent, then the distance will be bigger. Therefore, actions with strong but dierent temporal structures will tend to have large DACO distances.

Consequently, DACO is well suited to compare actions characterized by their dynamics, but needs to be combined with another kernel in order to deal with actions with little temporal structure. This shows that combining DACO with an aggregation-based kernel allows to eciently represent dynamics and orderless distribution aspects, which are both useful for action recognition.

The time-lag parameter

The main parameter of our DACO kernel is the lag τ in frames. For periodic actions, it is important that this parameter be dierent from a multiple of the period. Indeed, a periodic signal is always perfectly correlated with its version shifted by a period, and comparing two auto-correlations of two periodic signals with the same periodicity yields uninformative distances.

This problem can be avoided in practice by multiple techniques, for instance by detecting the period or by averaging the distances for multiple τ values. However, these methods are generally either expensive or unreliable in the absence of prior information, e.g., for periodic actions with variable period durations.

The alternative solution that we found to work best in practice is to simply take a τ which is small enough with respect to the action duration, such that it cannot be a multiple of a period. As we deal with short actions that include fast motions and potentially drastic changes in a few frames, we chose a τ of one frame in our experiments. This has the other advantage to not dilute temporal relations between the signal and its shifted version, hence ensuring the DACO distances are meaningful thanks to the preservation of strong temporal structures.

Another advantage of using a small lag value is to limit border eects when estimating the sampled auto-correlation operator. We, indeed, deal with the recognition of short videos, which have only a nite number of observations per time series. Hence, we need either to truncate them,

x = (x 1 , • • • , x T -τ ) and x τ = (x 1+τ , • • • , x T )
, or to have a cyclic representation (modulo T ). As the rst solution is reducing the number of observations and making our representations dependent on the size of τ , we choose the latter (cyclic) one.

1 T XX T +τ where X +τ = [φ F (x 1+τ ) • • • φ F (x T +τ )]
(5.8)

x τ = (x 1+τ , • • • x T +τ )
is the shifted version of x and X +τ is the corresponding time series representation in H F . Additionally, we dene the kernel matrix K (x τ ) between frames of x τ . Note, that this formulation assumes that our actions have zero mean

μx = 1 T T t=1 φ F (x t ) = 0.
This requires centering the frames in the feature space H F . As our computations use only kernel matrices, we directly center 5.3. PRACTICAL FORMULATION OF DACO 97 them [Harchaoui et al. 2008, Shawe-Taylor and[START_REF] Shawe-Taylor | Kernel methods for pattern analysis[END_REF]:

K(x) = XT X = Π T K (x) Π T , X = XΠ T , Π T = I T - 1 T 1 T 1 T T (5.9)
where I T is the T × T identity matrix and 1 T is the column vector of T ones. Π T is called the centering matrix, X are the centered frames and K(x) is the centered kernel matrix. In the following, we assume the series are centered in the feature space and use the notations K (x) and X instead of K(x) and X.

We can compute the DACO kernel using only kernel matrices:

d DACO (x, y) 2 = Tr N T KNK +τ (5.10) = Tr N (x) T K (x) N (x) K (x τ ) +Tr N (y) T K (y) N (y) K (y τ ) -2 Tr N (x) T K (x,y) N (y) K (y τ ,x τ )
where K +τ is the (T + T ′ ) × (T + T ′ ) kernel matrix between all frames of the shifted series x τ and y τ , and N is a matrix dened as: (5.11) Proof. First, we recall that Σ(x) = 1 T XX T and K (x) = X T X. We use the Sherman-Morrison-Woodbury formula to develop the normalization factors:

N = N (x) 0 0 -N (y) , N (x) = 1 γ 2 T γI -T I + γ -1 K (x) -1 K (x)
Σ(x) + γI -1 = γI + X 1 T IX T -1 = 1 γ I - 1 γ X T I + 1 γ X T X -1 X T 1 γ = 1 γ 2 γI -XQ (x) X T
(5.12)

where

Q (x) = T I + γ -1 K (x) -1 (5.13)
Using the fact that Σ(x) τ = 1 T XX T +τ , Equation 5.12 allows us to re-write the auto-correlation as:

Σ(x) + γI -1 Σ(x) τ = XN (x) X T +τ (5.14)
where

N (x) = 1 γ 2 T γI -Q (x) K (x)
(5.15)

CHAPTER 5. TIME SERIES KERNELS FOR ACTIONS

We then compute the Hilbert-Schmidt norm of the dierence between autocorrelation operators by expanding it from the Hilbert-Schmidt inner product (cf. Equation 5.6):

d DACO (x, y) 2 = XN (x) X T +τ 2 HS + YN (y) Y T +τ 2 HS -2 XN (x) X T +τ , YN (y) Y T +τ HS (5.16)
The Hilbert-Schmidt norm of the auto-correlation operator is computed from the trace denition by:

XN (x) X T +τ 2 HS = Tr XN (x) X T +τ T XN (x) X T +τ = Tr N (x) T X T XN (x) X T +τ X +τ (5.17) = Tr N (x) T K (x) N (x) K (x τ ) (5.18)
where Equation 5.17 results from the fact that the trace of products is invariant to circular permutations. The Hilbert-Schmidt inner product in Equation 5.16 is obtained using the same approach.

Advantages of the kernelized formulation

Our kernel is comparing time series using only between-frame kernel matrices as described in Equation 5.10. Therefore, its complexity depends only on the number of frames, instead of the number of dimensions of the frame features space. Consequently, this results in large speed-ups. Indeed, even when assuming the use of a linear kernel between frames, i.e., that the frame feature space and the input space of nite dimension d coincide, the complexity of directly evaluating the DACO distance between two time series using Equation 5.3 is in O(d 3 ). This is to expensive to be useful in practice, as frame representations are generally too high-dimensional, e.g., d = 4000 in our experiments. However, computing the DACO distance using the kernelized expression in Equation 5.10 leads to a much smaller complexity in O(T 3 ), where T is the duration of an action, typically of the order of 100 frames. Furthermore, [START_REF] Junejo | View-Independent Action Recognition from Temporal Self-Similarities[END_REF] observed that the diagonal blocks of K are matrices of temporal self-similarities. A self-similarity matrix has some interesting properties for action recognition, namely its stability with respect to view point changes and its action specic structure. However, Junejo et al.

[2010] propose to represent the structure of this matrix by viewing it as an image described using HOG features. Instead, we show that these temporal self-similarities are related to auto-correlation operators in the feature space associated with a frame kernel.

Experiments

In this section, we evaluate our approach using non-linear SVMs on standard video benchmarks for action classication. First, we introduce the datasets we use. Second, we detail how we model frames and the base kernel between these representations. Third, we describe how we combine a simple aggregationbased kernel with our DACO kernel. Finally, we give the classication results of our approach, and compare it to related and state-of-the-art methods.

Datasets

As dynamic aspects of actions might not be useful to classify every type of action, we investigate the use of our kernel on three state-of-the-art datasets.

The KTH dataset [Schüldt et al. 2004] is composed of six human action categories: three similar displacement ones (walking, jogging and running) and three others involving mostly arm motions (boxing, waving and handclapping). See Figure 5.3 for an illustration. Note that these actions are periodic. This dataset contains 2391 videos lmed with four dierent scenarios but with homogeneous and static backgrounds (in most sequences). We use the evaluation protocol of [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF]: accuracy averaged over all classes, for a xed train and test split. The UCF Sports dataset [Rodriguez et al. 2008] contains ten human ac- tions: bench swinging, diving, golf swinging, high-bar swinging, horse riding, kicking, running, skateboarding, walking, and weight-lifting (cf. For all experiments, predictions are obtained by learning non-linear SVMs with the standard one-against-rest multi-class approach.

Frame description and frame kernel

We use the state-of-the-art features recently proposed by Wang et al. [2011].

First, we compute densely sampled tracklets (local feature trajectories) from the dense optical ow eld between frames. Then, we compute a concatenation of trajectory-aligned local descriptors for each feature track. We use the best descriptor reported in [Wang et al. 2011]: Motion Boundary Histograms (MBH [START_REF] Dalal | Human Detection Using Oriented Histograms of Flow and Appearance[END_REF]], quantized spatial derivatives of the horizontal and vertical components of the optical ow). We use the same track and descriptor parameters as the ones mentioned in [Wang et al. 2011], namely feature tracks of 15 frames, with a dense sampling stride of 5 pixels.

We, then, represent each frame by a BOF. We compute a dictionary of 4000 visual words obtained with k-means clustering on a subset of 100,000 randomly sampled features (separately for each dataset). Each tracklet is assigned to a visual word. Each frame is then modeled with the histogram of occurrences of visual words corresponding to tracks passing through this frame. This strategy implies that each tracklet votes for multiple frames. This has a temporal smoothing eect, and makes our frame representations depend on neighboring ones.

We obtain a video representation as a time series of per-frame BOF (cf.

Figure 5.6). In the rare cases where the histogram of a frame is empty, we replace it by its linear interpolation obtained from neighboring frames. We use the intersection kernel between histograms [START_REF] Maji | Classication Using Intersection Kernel Support Vector Machines is ecient[END_REF] as base kernel between frames, as it provides a good compromise between accuracy and computational eciency.

k DME (x, y) = exp - 1 2σ 2 d DME (x, y) 2 , where d DME (x, y) = μy -μx H F (5.19)
This kernel is simply using the dierence between the means, μx and μy , of the frames in the feature space H F . This is related to the traditional BOF approach consisting of aggregating local descriptors computed over the entire video sequence as in [START_REF] Laptev | Learning realistic human actions from movies[END_REF], Wang et al. 2011], except that the aggregation is performed in the feature space. In practice, the DME kernel is computed using the same kernel matrix K (before centering) as DACO by:

d DME (x, y) 2 = m T Km , m = - 1 T , • • • , - 1 T T , 1 T ′ , • • • , 1 T ′ T ′ T (5.20)
In the following section, we report results for the DME kernel, the DACO kernel, and the linear combination of the two noted DME + DACO. Note, that in the latter case, a single mixing weight between DME and DACO is cross-validated per dataset (instead of per-action).

Results

Table 5.1, Table 5.2, and Table 5.3 contain per-class and average classication accuracies on the three datasets described in Section 5.4.1. We compare our approach to our implementation of a bag-of-features (BOF) baseline over MBH descriptors of tracklets, the state of the art, and the related works.

First, the good performance of DACO on the simple KTH dataset conrms that comparing auto-correlation operators is a valid approach for action recognition. Indeed, both our DACO kernel and the DME+DACO combination achieve a performance above 93%, which is comparable to most of the recently published results. Our approach is only outperformed by Sun et al.

[2011] on the KTH dataset. Interestingly, they also rely on self-similarity information, but at a local level. Note, however, that we outperform their approach by +3.4% on the UCF Sports.

Second, we can see that the simple combination of the aggregation-based DME kernel and our auto-correlation-based DACO kernel achieves comparable or better performance than the state of the art. We, indeed, improve by +0.2% Third, our experimental results suggest that the DME and DACO kernels complement each other for the purpose of action recognition. Their combination, indeed, improves performance with respect to just using one of the two kernels. Although the average improvement with respect to DME on the KTH dataset is small (+0.5%), it is more pronounced on the Youtube (+1.2%) and the UCF Sports (+3.3%) datasets. The actions that benet the most from this combination are:

• the running actions from both the KTH (+4.8% • jogging from KTH (-1.4% w.r.t. DME), whose global temporal structure is similar to both the running and walking actions;

• the golng actions (-5.5% w.r.t. DME on UCF Sports, -1.4% w.r.t. DME on Youtube), which are characterized by the fast local movement of a golf club instead of the temporal dependencies between frames.

• horse riding from UCF Sports (-8.3% w.r.t. DACO), which has a strong temporal structure (DACO alone outperforms DME by +8.3%); Individually, the averaging DME kernel tends to outperform our dynamicsbased DACO although not on all classes. Indeed, the average accuracies of DME and DACO on the UCF Sports are comparable (cf. Table 5.2). In addition, some actions are clearly better recognized based on their dynamics (e.g., kicking and running). This can be qualitatively assessed by looking at Figure 5.7 and Figure 5.8. On the one hand, Figure 5.7 displays the kernel matrix K containing the similarities between the frames of two actions from the same kicking category. The diagonal blocks are the temporal self-similarities K (x) and K (y) of the two actions. They clearly share similar temporal dependency patterns. The DACO distance between these videos (0.86) captures this structure information and is smaller than the DME distance (1.31). On the other hand, Figure 5.8 also contains a kernel matrix K, but for two dierent actions: walking and golf swing. In this case, the discrepancy between the two videos is better captured by DACO with a distance of 2.15, which is larger than the one obtained by DME (0.52). However, most categories are better described by their average local motion statistics, especially on Youtube videos. The results of DACO on this dataset (-7.6% w.r.t. DME on average) could be explained by the longer duration of actions in this dataset (approximatively 160 frames on average) compared to the duration of actions in UCF Sports (around 60 frames on average). This suggests that DACO is more suited to short duration, fast actions and is explained by: (i) the small value of the lag we use (τ = 1 frame), (ii) the diculty to estimate long range temporal dependencies between frames of non-periodic actions, and (iii) longer actions are less likely to be stationary, as they contain more dierent motions. This suggests a possible improvement of our method by applying the DACO kernel in a temporally localized manner, in order to detect correlated components with a strong temporal structure.

Finally, it seems from our results that the mixing weight between DME and DACO should be optimized independently per binary classication problem in our one-against-rest strategy, instead of jointly over all categories. As stated previously, some actions are, indeed, better characterized by their dynamics, while others are better modeled using average statistics.

5.4.5

Comparison with other kernels on time series

We performed additional experiments with alternative time series kernels and compared their performance to DACO.

Dierence between auto-covariances

First, we measured the importance of using the auto-correlation over just the auto-covariance. To that end, we compared DACO with a kernel using the Hilbert-Schmidt norm of the auto-covariance operators Σ(x) τ , instead of the auto-correlations ρ(x) τ = Σ(x) + γI -1 Σ(x) τ (Equation 5.1), where Σ(x) is the covariance operator. Using the same notations as in Section 5.3 and a similar proof to the one of Equation 5.10, we obtain:

Σ(y) τ -Σ(x) τ 2 HS = 1 T 2 Tr K (x) K (x τ ) + 1 T ′2 Tr K (y) K (y τ ) (5.21) - 2
T T ′ Tr K (x,y) K (y τ ,x τ ) Note that this expression is similar to the one for DACO in Equation 5.10, but without the normalization matrix N (Equation 5.11). We found that replacing auto-correlations with auto-covariances yields a noticeable decrease in recognition performance for all actions and across all datasets: -2% on KTH, -6% on UCF Sports, -1% on Youtube. Therefore, normalizing by the covariance of the series allows for more meaningful inter-series comparisons.

Dierence between auto-regressive models

Second, instead of using auto-correlation operators, we can directly model an action's temporal dependencies through an auto-regressive (AR) model in the RKHS H F associated with the frame kernel: (5.22) where p is the order of the AR model, W (x) i are operators in H F , and u t is a white noise process. Note that this assumes that the action x is stationary and centered in the feature space (like with DACO). This model can be used to predict (linearly in the feature space H F ) a frame x t from the preceding p frames by using the predictive codings W (x) i . These operators can be obtained by tting the AR model of x in Equation 5.22 using kernel ridge regression [Shawe-Taylor and Cristianini 2004], i.e., by minimizing the following cost with respect to the predictive codings W (x) i :

φ F (x t ) = p i=1 W (x) i φ F (x t-i ) + u t
1 T -p T t=p+1 φ F (x t ) - p i=1 W (x) i φ F (x t-i ) 2 H F + λ p p i=1 W (x) i 2 H F (5.23)
where λ is a regularization parameter. Solving the dual of this problem leads to the dual predictive codings A (x) :

A (x) = X S (x) + λ ′ I T -p -1
( 5.24) where λ ′ = λ(Tp)p -1 and S (x) is a kernel matrix between the sub-series of length p of action x:

{(x t-p , • • • , x t-1 ) , t = p + 1, • • • , T } .
As the order p of the AR model is xed, we use a simple frame alignment kernel, which yields:

S (x) t,t ′ = 1 p p k=1 k F (x t-k , x t ′ -k ) (5.25)
where k F is the previously dened frame kernel (Section 5.3). Note that the kernel matrix S (x) dened in Equation 5.25 can be obtained from the betweenframes kernel matrix K by simply convolving it with the identity I p .

We investigated an auto-regressive kernel based on the Hilbert-Schmidt distance between the dual predictive codings A (x) and A (y) of two actions x and y. Directly from the denition of the Hilbert-Schmidt norm (Equation 5.4) and from Equation 5.24, we obtain:

d AR (x, y) 2 = A (y) -A (x) 2 HS = T r L T K |p L
(5.26) where K |p is the kernel matrix between the frames of the series x and y truncated of their rst p frames, and L is dened as:

L = L (x) -L (y) , L (x) = S (x) + λ ′ I T -p -1
( 5.27) This distance compares dynamics explicitly modeled by the dual AR coefcients obtained with Equation 5.24. Equation 5.26 shows that it is related to DACO AR models, indeed, share strong connections with auto-correlations and that it also relies only on the kernel matrix K of frame similarities. Nevertheless, their practical formulation dier, and we observed that, in most cases, DACO outperforms the auto-regressive kernel based on the distance in Equation 5.26. Indeed, although this kernel obtains the highest accuracy (93.5%) on the short actions of the UCF sports dataset, it only reaches 86.5% on KTH (-6.9% w.r.t. DACO) and 55.1% on Youtube (-24% w.r.t. DACO). These results suggest that DACO is more robust to the violation of the stationarity assumption, and, thus, applicable to a wider range of actions.

Global alignment kernel

Finally, we evaluated recognition results with the global alignment kernel of [START_REF] Cuturi | Fast Global Alignment Kernels[END_REF], which extends the well-known Dynamic Time Warping algorithm by computing the soft-max of all possible alignments. It obtained the average accuracy of 90.1% on the UCF Sports dataset, which is comparable to the DME+DACO combination. This good performance can be explained by the fact that actions of the same category tend to be of very similar duration and time-synchronized in this dataset. However, the good performance of this alignment kernel did not transfer to the other datasets where it obtained a much lower performance than DACO (70.2% on KTH, 57.6% on Youtube). Two factors can explain these results. First, the videos in these datasets are clearly not synchronized, and there is a signicant intra-class duration variability. Second, some pairs of categories, e.g., running and jogging in KTH, can be aligned in spite of their dierences.

Conclusion

We introduced a new kernel on videos, the Dierence between Auto-Correlation Operators (DACO) kernel, specically designed for action recognition. It compares the dynamics of actions, represented as time series of frames, by using a distance between auto-correlations. It can be eciently computed using only inner products between frames. We show that, even if not all actions exhibit characteristic temporal relationships between frames, the dynamic information extracted by auto-correlations can complement state-of-the-art distribution-based kernels that average visual information over frames.

Chapter 6

Conclusion

Our work investigated structured collections of local spatio-temporal features in order to build action models that are both accurate and robust to realworld video conditions. Our experiments suggest that recognition performance on challenging video sources can be improved by bridging the gap between rigidly structured global representations and orderless aggregations of local descriptors. This dissertation has presented several structured models adapted for the recognition of both simple actions and more complex activities in uncontrolled scenarii.

In the following, we summarize our key contributions and the main observations derived from our experiments (Section 6.1). We also indicate some potential research directions that we deem interesting for future work on action recognition in real-world videos (Section 6.2).

Summary of contributions

Action detection with Actom Sequence Models

Our rst contribution is a temporally structured extension of bag-of-features for the task of action localization in long, real-world, unsegmented videos. We studied the decomposition of an action into a exible sequence of meaningful temporal parts termed actoms, and proposed a robust representation called the Actom Sequence Model. We also introduced a exible model of the temporal structure of an action. Relying on this generative model, we proposed a sliding-central frame detection approach, which is more principled and more accurate than traditional sliding window techniques. We validated our approach on movie data, showing that our method outperforms both unstructured and rigidly structured models, thanks to its exibility and robustness. In addition, our experiments highlighted that marginalizing over a learned prior of the temporal structure signicantly improves upon traditional multiscale sampling heuristics, even in a typical sliding window context where the structure is simply the action's temporal extent.

Activities as cluster-trees of tracklets

Our second contribution pertains to the modeling of complex activities using tree-structured video representations. We proposed a large-scale divisive spectral clustering algorithm able to automatically organize a collection of dense tracklets, i.e., local point trajectories. Our algorithm organizes the motion content of a video in a hierarchical representation, called cluster-tree. Contrary to existing methods, we neither select an arbitrarily xed number of spatio-temporal parts (nodes in the cluster-tree), nor build a global model of a category such as its average cluster-tree. Instead, we use the full decomposition of a video to represent an action with nested histograms forming our BOF-Tree model. We introduced a kernel that can eciently compare the content of two unordered binary trees of variable sizes by relying on the inclusion relations encoded by the tree's edges. We conducted experiments on challenging benchmarks for activity recognition and showed that our nonlinear classier on per-video hierarchies yields state-of-the-art results, improving upon structured learning methods and latent part models. We also showed that our clustering algorithm yields more discriminative decompositions than unrelated clusters obtained by k-means and spectral clustering, as well as decompositions from other hierarchical clustering algorithms.

Modeling action dynamics

Our third contribution consists in studying how action dynamics can complement the state-of-the-art models relying on average statistics about local features. We proposed to represent actions as time series of frame descriptors, and described a model of an action's temporal dependencies over time: the auto-correlation operator in a frame feature space. In addition to its statistical properties, we also motivated the choice of this operator as a model of action dynamics by showing its connection with temporal self-similarities. We formally derived this connection from the dual expression of the Hilbert-Schmidt distance between the auto-correlation operators of two actions. Furthermore, we relied on this dual formulation in order to provide an ecient kernel, called the Dierence between Auto-Correlation Operators (DACO) kernel. It compares action dynamics by computing the similarity between the respective auto-correlation operators of two actions. In order to evaluate our approach, we conducted experiments on a variety of datasets, ranging from short simple periodic actions to complex ones in Youtube videos. In all cases, we showed that the performance of methods averaging over frames is improved by the combination with our kernel on dynamics. This emphasized that, for action recognition, comparing content structure (e.g., an action's temporal dependencies) is complementary with comparing the contents themselves.

Perspectives for future research

In this section, we give some possible extensions of our work, which are suggested by our experiments and the recent progress of the computer vision and machine learning elds.

Extensions of ASM

A rst improvement of our ASM model and of our sliding central frame approach consists in adapting them for the task of spatio-temporal localization, i.e., returning a temporal window and a sequence of bounding boxes around the actors performing the action of interest. In order to localize when and where an action is performed, one could apply the temporal localization approach in Chapter 3 inside tracks obtained by pre-trained human and object detectors [Kläser et al. 2010a,b, Prest et al. 2011]. As mentioned above, instead of independently localizing rst and then classifying, one could jointly model spatio-temporal structure and appearance, for instance with the deformable part model of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. One of the main diculties, however, lies in how to incorporate geometrical aspects while maintaining the robustness of our models under real-world video conditions, especially when facing strong and time-varying viewpoint variations, or in the presence of occlusions. Poselets [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF] are an interesting approach to handle the aforementioned challenges in static images. These pre-trained detectors of local 3D poses have successfully been applied to action recognition in static images [START_REF] Maji | Action recognition from a distributed representation of pose and appearance[END_REF]]. Building on these ideas and our work on actoms, one could design detectors of actionlets, i.e., iconic local dynamic poses, which encode more information than just motion, e.g., the nature of the moving object or body part.

In Chapter 3, ASM models rely on a xed number of actoms per category. This limitation needs to be removed and our approach extended in order to handle sequence models with a variable number of parts.

Allowing action examples of the same category to have dierent numbers of actoms is, indeed, likely be necessary in order to model a wide range of actions, e.g., due to temporal occlusions, intra-class variability, or dierences between annotators on how to decompose the action. Comparing sequences with dierent numbers of actoms while preserving temporal ordering can be done by relying on dynamic programming strategies, e.g., by adapting string kernels to compute an actom edit distance, or with the Global Alignment Kernel [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF]. One can also use the Fisher kernel [START_REF] Jaakkola | Exploiting generative models in discriminative classiers[END_REF] with respect to a sequential generative model, e.g., a HMM, in order to obtain a xed-length representation based on a xed number of hidden states. In addition, estimating the variable-sized temporal structure of an action requires a more complex probability distribution than a histogram on inter-actom distances as done in Chapter 3. A straightforward extension of our approach would consist in using two temporal distributions instead: one for the number of temporal parts, and another conditional distribution on the actom placements knowing the number of actoms. However, this makes strong independence assumptions that may not hold in practice. Ideally, both the content, the number, and the positions of the actoms should be estimated jointly, instead of independently as done in Chapter 3. This is of particular importance when aiming to detect multiple actions simultaneously.

Weakly supervised training. In Chapter 3, we demonstrated that action models can be signicantly improved by learning from a meaningful manually labeled decomposition instead of just a temporal window. This supervision has, however, a cost that needs to be minimized in order to scale up to a large number of action categories. In addition to semi-supervised learning approaches, a promising direction of research consists in automatically rening inaccurate annotations (also called weak supervision) coming from cheap or readily-available additional sources of information, e.g., transcripts of movies and TV shows [START_REF] Gaidon | Mining visual actions from movies[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF]]. Promising results have been obtained in order to rene temporal extent using discriminative methods [Duchenne et al. 2009, Satkin andHebert 2010]. These approaches could be generalized to infer latent actom locations from rough temporal extent annotations. Note that the approach of [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] shares several similarities with recent approaches for image co-segmentation. For instance, Joulin et al. [2012a] rely on multiple images and their global category labels as weak supervision for segmentation via discriminative clustering. Therefore, one could adapt the related weakly supervised learning algorithms (e.g., [Joulin et al. 2012b]) in order to infer the latent spatio-temporal structure of actions from a set of loosely labeled videos.

Extensions of BOF-Trees

Our tree model of activities only accounts for inclusions between parts from a cluster-tree. This could be improved by modeling more complex structural relations between motion parts, e.g., spatial, temporal, and hierarchical relations as in [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF]. However, dening an overly complex latent structure leads to diculties in learning and inference, which eventually results in sub-optimal performance. Indeed, the additional exibility in the latent variables makes the parameter space too vast for it to be eciently explored, and may lead to overtting. Overcoming these issues e.g., by nding a good compromise between unconstrained structure learning and xed decompositions will improve recognition, thanks to the discriminative learning of the model, while ensuring greater robustness to real-world videos by modeling the uncertainty in the structure of the decompositions. Instead of only learning the parts, our decomposition method described in Chapter 4 could be improved by also modeling the latent importance of each part for a category. Our tree structure is, indeed, obtained without using the action category information. Furthermore, all nodes are treated equivalently in our ATEP kernel (Section 4.3.3), whereas some sub-trees might be unrelated to the action of interest (e.g., background motion). So far, these extraneous sub-trees are treated as noise, which is handled by the robustness of our kernel thanks to its averaging eect. Our method could be improved by taking a more explicit approach and learning category-specic importance of sub-trees based on their content, structure, and position in the cluster-tree. Node-specic importance factors can, indeed, be directly integrated in our ATEP kernel as simple multiplicative weights in the edge-to-edge comparisons. These weights could be learned by treating the importance of each node as a latent variable, and using adequate inference mechanisms. As mentioned previously, jointly co-clustering actions from the same category or from all categories at the same time could be used to leverage category labels in order to obtain better activity decompositions. Note that such part-based weighting might also be applicable to actoms, as some temporal parts are more important than others (e.g., the middle actom in our ASM models).

Finally, another extension consists in adapting our method to allow for spatio-temporal localization within BOF-Trees. The approach described in Chapter 4 is, indeed, specically tailored for videos focusing on a single activity. When the video is only temporally segmented and contains several co-occurring activities, we can adapt our method to operate only on parts of the video by individually matching sub-trees instead of comparing the whole cluster-trees. In addition to existing ecient sub-tree matching algorithms (cf. [START_REF] Valiente | Algorithms on Trees and Graphs[END_REF]]), we could also adopt a greedy coarse-to-ne matching approach in order to speed up computations. By relying on the additive property of BOF-Trees, we can indeed, approximate a sub-tree by its top-level (root, child) edge, as done in our ATEP kernel (Section 4.3.3). Therefore, we could match only the edges of BOF-Trees, and traverse the tree in a top-down fashion akin to a branch-and-bound strategy.

Applying our method to long video streams as those studied in Chapter 3 is, however, less straightforward. Indeed, as we build our tree using a divisive top-down strategy, our approach assumes that all tracklets are available at once. Therefore, it seems that our clustering algorithm must be preceded by an on-line temporal segmentation strategy e.g., using a shot detector for edited videos such as movies, or a more generally applicable change point detection algorithm such as [START_REF] Harchaoui | Kernel change-point analysis[END_REF]] in order to rst nd the roots of the cluster-trees to be built.

Extensions of DACO

Combining DACO with ASM. As suggested by our experiments in Chapter 5, our DACO kernel is particularly suited to short actions, and improves the performance of aggregation-based kernels. Therefore, we could improve the actom-to-actom comparisons in ASM by not only computing the similarity between actom contents, but also by comparing their dynamics using DACO. Indeed, the shorter duration of actoms means that they can be considered as almost stationary time-series of frames. Furthermore, the per-frame weights derived from the actom models can be directly integrated in DACO by weighting the projections of the per-frame BOFs in the RKHS associated with the frame kernel. Short-time DACO. As our results on the Youtube dataset seem to indicate (cf. Section 5.4.4), the main limitation of our DACO kernel pertains to its stationarity assumption, which is often violated for long and complex actions. Therefore, a natural extension of our approach consists in computing a short-time version of DACO, e.g., by successively convolving the frames with a temporal Gaussian window of a short duration. Shorter time series can indeed be considered as almost stationary, as there is simply less observations to notice a signicant change in the distribution of frames. The problem with this approach, however, is that the dynamics of the series is modeled by a sequence of local auto-correlation operators instead of single global one. Consequently, another sequence kernel must be used in order to pool the local window-to-window comparisons obtained with DACO. Note that applying this idea to compute a windowed version of the auto-regressive kernel described in Section 5.4.5, results in an interesting representation of the video signal, which shares similarities with the linear predictive codings that are widely used in audio and speech processing.

Time series analysis of actions. Most of the tools built to analyze time series are designed for univariate data such as audio signals or the evolution of stock prices. Videos, however, rely on high-dimensional representations. Therefore, the analysis of their temporal properties e.g., periodicity requires dierent techniques adapted to these complex multivariate signals. For instance, [START_REF] Cutler | Robust real-time periodic motion detection, analysis, and applications[END_REF], more than a decade before us, used timefrequency analysis on temporal self-similarities to detect periodic motion. In Chapter 5, we showed that the auto-correlation operator in a frame RKHS Ce travail fut un prélude au développement de l'analyse visuelle du mouvement, qui consiste à étudier les propriétés visuelles des systèmes dynamiques, comme les uides et les humains, de manière scientique et précise. Le travail de Muybridge montra que l'évolution de la photographie permettait de A.1 Ob jectifs L'objectif de notre travail est de reconnaître des actions génériques effectuées dans des vidéos réalistes (cf. Figure A.3 pour une illustration). Nous avons pour but de concevoir des modèles robustes, capables de représenter une grande variété de catégories d'actions, tout en tenant compte de la variabilité visuelle de vidéos réalisées dans des conditions non contrôlées.

La reconnaissance d'actions en conditions non contrôlées fait face à de nombreuses dicultés inhérentes à la complexité des actions et des vidéos.

Plusieurs challenges sont liés à la variabilité intra-classe : les actions d'une même catégorie peuvent diérer signicativement en terme d'apparence et de mouvement. Les sources de variation incluent le bruit, les conditions d'éclairage, l'échelle et la forme des entités participantes, le fouillis de l'arrièreplan, le large éventail de points de vue possibles, les occlusions, les mouvements rapides, complexes et articulés, le ou du mouvement, le mouvement de la caméra, la variabilité de durée, et le style d'exécution. À cause de ces variations, les modèles d'action peuvent dicilement se reposer sur des hypothèses simplicatrices, comme par exemple supposer que la totalité du corps des acteurs est toujours entièrement visible. Nous tenons compte de cette variabilité An que les ordinateurs puissent faire preuve d'un tel niveau d'interprétation, ils ont besoin de modèles qui représentent les diérents mouvements, leurs relations et l'évolution temporelle des entités participantes (objets, parties du corps) au cours d'une action. Par exemple, les Motion History Images (MHI) de Bobick and Davis [2001] sont un modèle précurseur utilisé pour représenter une action comme l'évolution temporelle d'une silhouette (cf. Figure A.5). Cependant, cette approche et ses extensions comme les formes spatio-temporelles de [START_REF] Gorelick | Actions as space-time shapes[END_REF] ou les Motion History Volumes (MHV) de Weinland et al. [2006] manquent de robustesse et sont limitées à des scenarii contraints, tels que la vidéosurveillance [START_REF] Hu | A survey on visual surveillance of object motion and behaviors[END_REF]] ou les interfaces homme-machine [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF]. En eet, elles reposent sur des informations diciles à obtenir pour des vidéos sous conditions non contrôlées, Depuis peu, la communauté de vision par ordinateur se penche désormais sur des vidéos plus diciles. Les données vidéo non contrôlées sont caractérisées par une grande variabilité et l'absence de connaissance a priori sur (i) le processus d'enregistrement (comme le point de vue, le mouvement de la caméra, la qualité de la vidéo et la résolution), (ii) la scène (en intérieur ou en extérieur, bondée ou non, arrière-plan en mouvement ou encombré, occlusions, conditions d'éclairage), et (iii) les actions réalisées (mouvements rapides ou lents, interactions). Ces données englobent un large éventail de vidéos issues d'un grand nombre de sources potentielles, comprenant les vidéos amateur, les reportages, les diusions sportives, les émissions télévisées et les lms. Les catégories d'actions présentes dans les données de test pour la reconnaissance d'actions sont elles aussi de plus en plus variées : elles comprennent des actions simples (comme courir) et plus complexes (comme sortir de sa voiture), des interactions (comme embrasser) et des activités (comme se battre).

An de résoudre les problèmes mentionnés précédemment, plusieurs chercheurs [START_REF] Chomat | Probabilistic recognition of activity using local appearance[END_REF][START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Laptev | On space-time interest points[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF][START_REF] Zelnik-Manor | Event-based analysis of video[END_REF] ont proposé d'utiliser des caractéristiques visuelles locales. Ce sont en général des extensions spatio-temporelles de détecteurs de points d'intérêt en 2D et de descripteurs utilisés avec succès pour la reconnaissance d'objets dans des images (voir par exemple les résultats des compétitions PASCAL VOC [START_REF] Everingham | The Pascal Visual Object Classes (VOC) Challenge[END_REF]). Les caractéristiques locales de vidéo, telles que les points d'intérêt spatio-temporels [START_REF] Laptev | On space-time interest points[END_REF]], décrivent l'apparence (comme avec les histogrammes de gradients orientés [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) ou le mouvement (comme avec les histogrammes de ot optique [START_REF] Laptev | Learning realistic human actions from movies[END_REF]) de volumes spatio-temporels locaux. Grâce à la robustesse des descripteurs locaux et à leur absence d'hypothèses globales (sur les relations géométriques par exemple), les caractéristiques locales ont

A.4 Perspectives

Dans cette section, nous donnons des extensions possibles à notre travail, suggérées par nos expériences et les récents progrès dans les domaines de la vision par ordinateur et de l'apprentissage statistique.

Extensions de notre approche de localisation Une première amélioration de notre modèle ASM et de notre approche de localisation par image centrale glissante consiste à les adapter pour les tâches de localisation spatio-temporelle, c'est-à-dire retourner une fenêtre temporelle et une séquence de boîtes englobantes autour des acteurs réalisant l'action. Pour pouvoir localiser quand et où une action est réalisée, il est possible d'appliquer l'approche de localisation temporelle utilisée pour ASM à des trajectoires obtenues à l'aide de détecteurs d'humains et d'objets pré-entrainés [Kläser et al. 2010a,b, Prest et al. 2011]. Alternativement, au lieu de commencer par localiser indépendemment pour ensuite classier, il est aussi possible modéliser conjointement la structure et l'apparence spatiotemporelles, avec par exemple le modèle par parties déformable de [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. Cependant, l'une des principales dicultés est de trouver comment incorporer des aspects géométriques tout en maintenant la robustesse de nos modèles aux conditions vidéos réalistes, notamment en présence d'occlusions ou de grandes variations de points de vue. Les poselets [START_REF] Bourdev | Poselets: Body part detectors trained using 3d human pose annotations[END_REF] constituent une approche intéressante pour gérer dans des images statiques les challenges cités précédemment. Ces détecteurs préentraînés de poses locales ont été appliqués avec succès à la reconnaissance d'actions dans des images statiques [START_REF] Maji | Action recognition from a distributed representation of pose and appearance[END_REF]. En se basant sur ces idées et sur notre travail sur les actoms, il est envisageable de concevoir des détecteurs de poses dynamiques locales emblématiques, qui contiendraient plus d'information que juste le mouvement, comme par exemple la nature des objets ou des parties du corps en mouvement.

Les modèles ASM reposent sur un nombre xe d'actoms par catégorie. Cette limitation pourrait être levée an que notre approche s'étende aux modèles de séquence avec un nombre variable de parties. En eet, il semble nécessaire de permettre à des exemples d'action d'une même catégorie d'avoir diérents nombres d'actoms, pour pouvoir modéliser un large éventail d'actions, en raison par exemple des occlusions temporelles, de la variabilité intra-classe ou des diérences entre les annotateurs sur la manière de décomposer une action. Il est possible de comparer des séquences avec diérents nombres d'actoms tout en préservant l'ordre temporel en se basant sur des stratégies de programamtion dynamique, comme par exemple en adaptant les noyaux sur chaînes de caractères au calcul d'une distance d'édition d'actom ou avec le Global Alignment Kernel [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF]]. Une autre piste potentielle consiste à utiliser le noyau Fisher [START_REF] Jaakkola | Exploiting generative models in discriminative classiers[END_REF] dans le but de passer à l'échelle avec un grand nombre de catégories. En plus des approches d'apprentissage semi-supervisées, une direction prometteuse de recherche consiste à aner automatiquement les annotations inexactes (également appelées supervision faible) venant de sources d'information bon marché ou facilement disponibles, comme des transcriptions de lms et de séries TV [START_REF] Gaidon | Mining visual actions from movies[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF]. Des résultats prometteurs ont été obtenus dans le but d'aner l'étendue temporelle en utilisant des méthodes discriminatives [Duchenne et al. 2009, Satkin andHebert 2010]. Ces approches pourraient être généralisées an de déduire les positions latentes des actoms depuis des annotations temporelles approximatives obtenues automatiquement. Notons que l'approche de [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF]

Extensions de nos modèles d'activités

Notre modèle arborescent d'activité modélise uniquement des relations d'inclusions entre parties du mouvement. Cette approche pourrait être augmentée par l'utilisation de relations supplémentaires spatiales, temporelles et hiérarchiques plus complexes, comme par exemple dans [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF]. Néanmoins, la dénition d'une structure latente trop complexe entraîne des dicultés d'apprentissage et d'inférence et, par conséquent, des performances sous-optimales. En eet, la exibilité supplémentaire au niveau des variables latentes d'un tel modèle fait que l'espace de paramètres exploré est sous-contraint et trop vaste pour permettre une exploration ecace et éviter le sur-apprentissage. Surmonter ces dicultés par exemple en trouvant des bonnes contraintes sur la structure à apprendre permettrait d'améliorer les modèles d'actions, grâce à l'apprentissage discriminatif de leurs paramètres, tout en développant leur robustesse, grâce à la modélisation de l'incertitude sur leur structure.

En plus de découvrir automatiquement les diérentes parties, notre méthode de décomposition pourrait être améliorée en modélisant également l'importance latente de chaque partie pour une catégorie. En eet, notre structure arborescente sur une action est obtenue sans utiliser l'information de son appartenance à une catégorie. De plus, tous les noeuds sont traités de manière équivalente dans notre noyau ATEP, alors que certains sous-arbres peuvent être sans rapport avec l'action (des mouvements à l'arrière plan par exemple). Pour l'instant, ces sous-arbres superus sont considérés comme du bruit auquel notre noyau est robuste dû à son eet de moyenne. Notre méthode pourrait être améliorée par une approche plus explicite, en apprenant l'importance des sous-arbres, pour chaque catégorie, à partir de leur contenu, de leur structure et de leur position dans le dendogramme. Des facteurs d'importance d'un noeud peuvent en eet être directement intégrés dans notre noyau ATEP comme de simples poids multiplicatifs dans les comparaisons entre arêtes. Ces poids pourraient être appris en considérant l'importance de chaque noeud comme une variable latente et en utilisant des méchanismes d'inférence adéquats. Comme mentionné précédemment, la segmentation conjointe d'actions (d'une même catégorie ou de toutes les catégories à la fois) pourrait être utilisée pour tirer prot des étiquettes de catégorie, an d'obtenir de meilleures décompositions d'activités. Notons qu'une telle pondération basée sur les parties pourrait également être applicable aux actoms puisque certaines parties temporelles sont plus importantes que d'autres a priori.

Enn, une autre extension consiste à adapter notre méthode pour permettre la localisation spatio-temporelle au sein des BOF-Trees. En l'état actuel, notre approche est spéciquement conçue pour des vidéos se

  . . . . . . . . . . . . . . . . . . . . . . 9

Figure 1

 1 Figure 1.1: Muybridge's "Sallie Gardner at a Gallop" study. It proved that, at one point in time, all four hooves of a galloping horse are o the ground.1

Figure

  Figure 1.3: Examples of actions and videos from the Hollywood 2

Figure 1 . 4 :

 14 Figure 1.4: Frame from Jackie Chan's movie The Legend of Drunken Master.

Figure 1 . 5 :

 15 Figure 1.5: The motion energy images (MEI) and motion history images (MHI)

Figure 1

 1 Figure 1.6: Bag-of-features: a robust model that aggregates local spatio-temporal features by quantizing them on a vocabulary of prototypical features called visual words by analogy with the bag of words text model.

Figure 1 . 7 :

 17 Figure 1.7: Illustration on three actoms for the sitting down action of our Actom Sequence Model (ASM): succession of temporal parts modeled by the aggregation of time-anchored local features.

Figure 1 Figure 1

 11 Figure 1.8: Illustration on a pole vaulting activity of our cluster-tree of tracklets: automatically learned hierarchical motion decomposition for complex activity recognition.

Figure 2 . 1 :

 21 Figure 2.1: Actions as time series of poses from [Brendel and Todorovic 2010].

Figure 2

 2 Figure 2.2: A hand-crafted Dynamic Bayesian Network from [Laxton et al. 2007] modeling the cooking French toast activity.

Figure 2

 2 Figure 2.3: Tensor CCA on video volumes [Kim and Cipolla 2009].

Figure 2 . 4 :

 24 Figure 2.4: Action localization with space-time templates from [Ke et al. 2010].

Figure 2 . 5 :

 25 Figure 2.5: Spatio-temporal descriptors of appearance (Histogram of Oriented Gradients) and motion (Histogram of Optical Flow) with dierent spatial and temporal subdivisions from [Laptev and Pérez 2007].

Figure 2

 2 Figure 2.6: Spatio-temporal interest points of a walking action [Laptev 2005]. The upside-down level surface of a leg pattern (left) shows that the detected interest points (the ellipsoids) correspond to corners in space-time.

Figure 2 . 7 :

 27 Figure 2.7: Trajectories as local features: (a) spatial interest point trajectories quantized over a vocabulary of prototypical trajectons [Matikainen et al. 2009]; (b) dense tracklets represented with track-aligned local appearance and motion descriptors [Wang et al. 2011].

Figure 2 .

 2 Figure 2.10: Approaches modeling relations between local features: (a) hierarchical compound features from local co-occurrence histograms [Kovashka and Grauman 2010], (b) explicit models of pairwise relations between trajectories [Matikainen et al. 2010].

Figure 2 .

 2 Figure 2.11: Geometric part-based model of[START_REF] Niebles | Hierarchical model of shape and appearance for human action classication[END_REF] where an

Figure 3

 3 Figure 3.1: Examples of actom annotations for two actions.

  , we propose to model an action as a small sequence of key atomic action units, which we refer to as actoms. These action atoms are an intermediate layer between motion primitives e.g., spatio-temporal interest points and actions. Composed of local video features, actoms are specic to each action class, and obtained by manual annotation, though only at training time. These annotations have the same cost as specifying start and end frames of actions, while being richer and more consistent across action instances.

Figure 3 . 2 :

 32 Figure 3.2: Construction of our ASM action model using actom-based annotations and a temporal weighting scheme for aggregating local features in a sparse temporally structured bag-of-features.

Figure 3

 3 Figure 3.3: Illustration of the actom models in ASM (a = 3) for the same actom locations, but dierent ASM hyper-parameters. This shows the inuence of the overlap (ρ) and peakyness (p) on the per-frame weights.

(

  cf. examples in Figure 3.1). We use three actoms per action example in our experiments. Note that only positive training examples are manually annotated. In general, this corresponds to a small fraction of the training data most action recognition benchmarks use in the order of 100 action examples per category. The initial noisy set of candidate training clips can be automatically obtained by using external data, e.g., with simple textual queries on movie transcripts [Gaidon et al. 2009].During the annotation process, semantic consistency in the choice of actoms across dierent video clips is necessary: the i th actom of an action should have a single interpretation, e.g., recipient containing liquid coming into contact with lips for the drinking action. This is ensured by giving precise guidelines to annotators, and by making multiple annotators label or correct each example. Note, however, that our approach is robust to the violation of this assumption, i.e., we can still model actions, even when an actom has a few possible meanings across training examples. After all the training examples are annotated once, we perform a simple outlier detection step using the temporal structure model described in Section 3.3.2. First, we learn a model of the temporal structure and estimate the likelihood of each annotation according to this model. We, then, resubmit for annotation the inconsistently annotated examples, i.e., those below a

  Figure 3.4 quantitatively illustrates this claim. It shows that the ground truth annotations for the action sitting down have a smaller duration variance when actoms are annotated insteadof beginning and ending frames. We also observed that the average annotation time per action is comparable for both of these annotation types we measured between 10 and 30 seconds per action. In addition, an actom is a visual phenomenon that is deemed semantically relevant by annotators, and not an automatically learned part of the action. It is, therefore, always possible to interpret a predicted actom sequence. Moreover, we show that it leads to discriminative representations for action recognition.

Figure 3 . 4 :

 34 Figure 3.4: Frequencies of action durations obtained from manual annotations for the action Sit Down. Boundaries depict the duration of ground truth annotations from [Duchenne et al. 2009], obtained by labeling beginning and end frames of the action. Actom-cropped represents the time interval between the rst and the last actom.

  , we do not know the temporal locations of the actoms.Therefore, we learn a generative model of the temporal structure allowing to sample likely actom candidates at test time. The temporal structure we estimate is the distribution of inter-actom spacings from the training sequences:

  where a is the number of actoms of the action category and n + is the number of positive training examples.

Figure 3 . 5 SmokingFigure 3 . 5 :

 3535 Figure 3.5: Temporal structure learned for smoking from the Coee & Cigarettes dataset. The candidate actom models ( ∆j , p j ) ∈ D are sorted by their estimated prior probability p j .

  Figure 3.6: Sliding central frame temporal localization. The probability of an action being performed at frame t m is evaluated by marginalizing over all actom candidates learned with our model of the temporal structure.

  Figure 3.7). Initially, Laptev and Pérez [2007] evaluated action localization for the drinking action only. Evaluation for the smoking category was later added by Kläser et al. [2010b]. The training sets contain 106 drinking and 78 smoking clips: 41 drinking and 70 smoking examples from six short stories with dierent actors and settings of the Coee and Cigarettes movie, 32 drinking and 8 smoking clips from the movie Sea of love, and 33 drinking examples recorded in a laboratory setting. The test set for the drinking action consists of two short stories (36, 000 frames) containing 38 drinking actions. The test set for the smoking action consists of three short stories (32, 000 frames) containing 42 smoking actions. There is no overlap between the training and test sets, in terms of both scenes and actors.

Figure 3

 3 Figure 3.7: Actions from the Coee and Cigarettes dataset

Figure 3

 3 Figure 3.8: Actions from the DLSBP datasetHollywood 2[Marszalek et al. 2009]. This classication dataset consists of 1707 video clips 823 for training, 884 for testing extracted from 69 Hollywood movies. There are 12 categories: answering a phone, driving a car, eating, ghting, getting out of a car, hand shaking, hugging, kissing, running, sitting down, sitting up, and standing up (cf. Figure3.9 for some examples).

  as the ones used for our ASM model. In addition, for the action localization experiments, we crop the original annotations of the positive training samples around the training actoms, which we further extend by a small oset half the inter-actom distances for each sequence in order to use an amount of frames comparable to what ASM uses. A similar, but automatic, cropping step was shown to improve performance by Satkin and Hebert [2010]. Furthermore, we use the same random training negative samples as the ones used by our ASM approach. This allows for a fair comparison between ASM and BOFbased methods. At test time, BOF-based sliding window approaches require the a priori denition of multiple temporal scales. We learn the scales from the positive training examples using a generative model similar to the one used for actoms (cf. Section 3.3.2).

  Figure 3.11 shows frames of the top ve results for drinking and open door obtained with our method. Some examples of automatically localized actoms with our ASM method are depicted in Figure 3.12. In the following, we discuss how our ASM model compares to both our bag-of-features baselines and the state of the art.

Figure 3 .

 3 Figure 3.11: Frames of the top 5 actions localized with ASM for Drinking (top row) and Open Door (bottom row, #2 is the only false positive).

Figure 3 .

 3 Figure 3.12: Automatically localized frames of actoms for 4 action sequences (from top to bottom): opening a door, drinking, smoking, and sitting down.

  Rigid v.s. adaptive temporal structureThe exible temporal structure modeled by ASM allows for more discriminative models than BOF T3. Using the xed temporally structured extension of BOF increases performance, but is outperformed by our model on all actions.

  Figure3.13: Classication by localization results in Average Precision (AP) on the Hollywood 2 dataset[START_REF] Marszalek | Actions in context[END_REF]]. BOF and BOF-T3 are sliding-window approaches using BOF and its temporally structured extension. Our approach is ASM. AVG contains the average performance over all classes (BOF: 38%, BOF-T3: 38%, ASM: 49%).

  Figure 3.14: Minimum, average, and maximum localization performance for action Open Door for varying sizes of the support of D (number of candidate temporal structures).

  measured the localization performance as a function of the number of random training negatives used (cf. Figure3.15 for the Drinking action).

  Figure 3.15: Minimum, average, and maximum localization performance for action Drinking for varying numbers of random training negatives.

Figure 4 .

 4 Figure 4.1: Example of a hierarchical motion decomposition obtained with our recursive bi-partitioning algorithm on dense tracklets.

  .

  the tracklets, and introduces our hierarchical divisive multi-modal clustering scheme. Section 4.3 details our second contribution:

Figure 4 .

 4 Figure 4.2: Tracklets of a weightlifting activity. Colors correspond to the most detailed clusters obtained with our hierarchical motion decomposition.

Figure 4 . 3 :

 43 Figure 4.3: Illustration of the Nyström approximation. We rst sample n ≪ Ntracklets by randomly choosing p points in each cell of a regular spatiotemporal grid. We then compute the similarity between the selected tracklets (in blue), yielding matrix A, as well as with all other Nn points (in red), yielding matrix B. The Nyström method allows to eciently compute the approximate leading eigenvectors Û of the large N × N matrix W of all similarities using only the small n × N slice of it, composed of blocks A and B.

  right = find_best_split(node) # cf. algorithm 2 # Add children to the queue 11: if lef t and right are not empty

Figure 4 .

 4 Figure 4.4 for an illustration. We rst pre-compute a vocabulary of trackaligned MBH features on a random subset of the training features. We use an on-line k-means algorithm [Sculley 2010] with k = 4000 to cluster 10 6 tracklets randomly sampled from the training videos. We then quantify all MBH features by assigning them to the closest visual word (centroid) in the learned vocabulary. Finally, each node is represented by a BOF, i.e., its histogram of occurrences of visual words. Although we use a high-dimensional representation for better accuracy, this does not pose computational or memory problems. In practice, per-node histograms are indeed sparse, thus can be represented eciently. Modeling a node with a BOF discards the intermediate geometry at the node level i.e., between neighboring tracklets while local geometry is still captured by the local tracklet features, and global spatio-temporal structure information is captured by the cluster-tree.

Figure 4 . 4 :

 44 Figure 4.4: (a) A cluster-tree of tracklets, where edges between nodes represent a strict inclusion. (b) Its corresponding BOF-tree, where the BOF of a node is the sum of its children's BOFs.

  hand, existing kernels on variable-size trees are inspired by string kernels, i.e., measure structural similarity by counting the number of common sub-structures[START_REF] Shawe-Taylor | Kernel methods for pattern analysis[END_REF]. In BOF-trees, however, these approaches are not directly applicable as siblings are unordered. In addition, our goal is to use the structure information to disambiguate comparisons between the content of the motion component hierarchies, not to directly compare the tree structures. On the other hand, summing over all pairwise node comparisons results in a valid kernel comparing the contents of BOF-Trees (which we use as a baseline, cf. Section 4.4.3), but it ignores their structure. Instead, we propose the All Tree Edge Pairs (ATEP) kernel, which consists in comparing the edges of BOF-trees.

  dataset[START_REF] Patron-Perez | High ve: Recognising human interactions in TV shows[END_REF]] and the Olympic Sports dataset[START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF]]. Both of these datasets focus on complex activities instead of more commonly investigated short actions such as running.The High Five dataset[Patron-Perez et al. 2010] consists of 300 video clips collected from 20 dierent TV shows (cf. Figure 4.5). The activity cate- gories are four human-human interactions: hand shakes, high ves, hugs, and kisses. Each activity is performed in 50 dierent clips, the remaining 100 negative clips containing other actions. These activities are of short duration and involve a simple combination of atomic actions. As the dataset authors propose a model relying on head orientations, annotations for discrete head orientation and upper body localization of actors are available. We do not use this additional supervision in our experiments. Evaluation on this benchmark is conducted like in [Patron-Perez et al. 2010], i.e., by computing the recognition performance in Average Precision using a 2-fold cross-validation with xed folds provided with the dataset.

Figure 4 . 5 :

 45 Figure 4.5: Frames from the High Five dataset [Patron-Perez et al. 2010]

Figure 4 . 6 :

 46 Figure 4.6: Activities of the Olympic Sports dataset[START_REF] Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classication[END_REF]

Figure 4 . 7 :

 47 Figure 4.7: An action of the Olympic Sport [Niebles et al. 2010] dataset, before (top row) and after (bottom row) camera motion stabilization.

Figure 4 .

 4 Figure 4.8: Tracklets from a video (top) and from its stabilized version (bottom).

  Figure 4.9: Performance improvement of our method over the method from [Brendel and Todorovic 2011] on the Olympic Sports dataset.

Figure 4 .

 4 10 for per-class details on the Olympic Sports dataset). This conrms that our method captures useful structure information, and that the improvement does not result only from the decomposition into parts, but also from the comparison of their relations.Improvement of ATEP over ACP on the full SDT trees

Figure 4 .

 4 Figure 4.10: Performance improvement obtained by using the hierarchical relations of the SDT BOF-trees on the Olympic Sports dataset.

Figure 4 .Figure 4 .

 44 Figure 4.11: Confusion matrix obtained with our method (ATEP on SDT BOF-Trees) on the Olympic Sports dataset.

Figure 4 .

 4 Figure 4.12: Stabilized videos of the HMDB dataset[START_REF] Kuehne | HMDB: a large video database for human motion recognition[END_REF]

Figure 4 .

 4 Figure 4.13: Confusion matrix obtained with our method (ATEP on SDT BOF-Trees) on the HMDB dataset [Kuehne et al. 2011].

Figure 5 .

 5 Figure 5.1: Our goal is to complement the robustness of the orderless bag-offeatures model of actions (left) with temporal dependency information (right) captured by our kernel on dynamics.

  which measures dependencies between frames of two dierent videos and is not suited to compare dierent actions with strongly related motions (e.g., running and walking).

Figure 5 . 2 :

 52 Figure 5.2: Computation of our DACO kernel. For two actions represented as time series of frames, x = (x 1 , . . . , x T ) and y = (y 1 , . . . , y T ′ ), the kernel compares their dynamics by using the dierence between their auto-correlations ρ(x) τ and ρ(y) τ , with a lag of τ frames.

Figure 5 . 3 :

 53 Figure 5.3: Frames from the 6 action categories of the KTH dataset.

Figure 5 .

 5 4). It consists of 150 video samples that show a large intra-class variability. To increase the amount of samples, the dataset is extended with horizontally ipped versions of each sequence. Videos of this dataset are of high resolution and good quality. The evaluation metric is the average leave-one-out accuracy (without considering the ipped versions at test time).

Figure 5 . 4 :

 54 Figure 5.4: Frames from the 10 action categories of the UCF Sports dataset.The Youtube dataset[START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF]] contains eleven action categories: basketball shooting, biking/cycling, diving, golf swinging, horse riding, soccer juggling, swinging, tennis swinging, trampoline jumping, volleyball spiking, and walking with a dog. See Figure5.5 for an illustration. This dataset is challenging due to large variations in camera motion, object appearance and pose, object scale, viewpoint, cluttered background and illumination conditions. Videos are of low resolution, contain shaky camera motion and actions are characterized not only by motion but also by the objects involved and the context in which they are performed. Performance is measured as in[START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF]] using leave-one-group-out average accuracy.

Figure 5 . 5 :

 55 Figure 5.5: Frames from 10 (out of 11) action categories of the Youtube dataset.

Figure 5 .

 5 Figure 5.6: Actions as time series of per-frame BOF over dense tracklets.

Figure 5 .

 5 Figure 5.7: Example of kernel matrix K (cf. Eq. 5.7) between the frames of two similar kicking actions with a small DACO distance (0.86).

Figure 5 .

 5 Figure 5.8: Example of kernel matrix K (cf. Eq. 5.7) between the frames of a walking and golng actions with a high DACO distance (2.15).

  Harzallah and C. Schmid and F. Jurie and A. Gaidon. Classication aided two stage localization PASCAL Visual Object Classes Challenge Workshop, in conjunction with ECCV, October 2008. • M. Douze, A. Gaidon, H. Jégou, M. Marszalek, C. Schmid. INRIA-LEAR's video copy detection system Proceedings of the TREC Video Retrieval Evaluation (TRECVID Workshop), December 2010. Annexe A Résumé Les quatre sabots d'un cheval au galop se retrouvent-ils à un moment donné tous en l'air? La réponse à cette question est souvent considérée comme la première étape du développement de la vidéo. En 1872, le photographe Eadweard Muybridge fut chargé par Leland Stanford de donner une réponse dénitive à cette question longtemps débattue. A cette allure environ 58 kilomètres par heure, soit 36 miles par heure les sabots d'un cheval sont trop rapides pour permettre à l'oeil humain de les suivre : une preuve scientique basée sur la photographie était nécessaire pour répondre. Après plusieurs expériences préliminaires, Muybridge apporta une réponse armative à la question, avec sa célèbre étude "Sallie Gardner at a Gallop" (cf. Figure A.1). La principale diculté fut d'élaborer une installation capable de prendre une succession d'images capturant les détails du mouvement malgré sa vitesse. Muybridge réussit à prendre une série de photographies le 19 juin 1878, à la ferme de Stanford à Palo Alto, en plaçant 24 appareils photo le long de la piste. L'obturateur de chaque appareil était déclenché par un l de détente au passage du cheval.

Fig

  Fig. A.1: Étude de Muybridge "Sallie Gardner at a Gallop" qui prouva qu'à un moment donné, les quatre sabots d'un cheval au galop sont tous en l'air.121

Fig. A. 3 :

 3 Fig. A.3: Exemples d'actions tirées de vidéos de la base Hollywood 2 [Marszalek et al. 2009] utilisé dans nos expériences.

Fig. A. 4 :

 4 Fig. A.4: Image du lm de Jackie Chan The Legend of Drunken Master. Cette image seule ne sut pas pour comprendre le contenu de la scène. Il est nécessaire de considérer l'évolution temporelle des diérents acteurs pour pouvoir déterminer qu'il s'agit d'une scène de combat dans laquelle le personnage central est attaqué alors qu'il boit du vin à la bouteille.

Fig. A. 5 :

 5 Fig. A.5: Les Motion Energy Images (MEI) et Motion History Images (MHI) de Bobick and Davis [2001].comme par exemple l'élimination d'arrière-plan, l'extraction de silhouettes ou l'estimation de modèles paramétriques du corps humain.Depuis peu, la communauté de vision par ordinateur se penche désormais sur des vidéos plus diciles. Les données vidéo non contrôlées sont caractérisées par une grande variabilité et l'absence de connaissance a priori sur (i) le processus d'enregistrement (comme le point de vue, le mouvement de la caméra, la qualité de la vidéo et la résolution), (ii) la scène (en intérieur ou en extérieur, bondée ou non, arrière-plan en mouvement ou encombré, occlusions, conditions d'éclairage), et (iii) les actions réalisées (mouvements rapides ou lents, interactions). Ces données englobent un large éventail de vidéos issues d'un grand nombre de sources potentielles, comprenant les vidéos amateur, les reportages, les diusions sportives, les émissions télévisées et les lms. Les catégories d'actions présentes dans les données de test pour la reconnaissance d'actions sont elles aussi de plus en plus variées : elles comprennent des actions simples (comme courir) et plus complexes (comme sortir de sa voiture), des interactions (comme embrasser) et des activités (comme se battre).An de résoudre les problèmes mentionnés précédemment, plusieurs chercheurs[START_REF] Chomat | Probabilistic recognition of activity using local appearance[END_REF][START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Laptev | On space-time interest points[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF][START_REF] Zelnik-Manor | Event-based analysis of video[END_REF] ont proposé d'utiliser des caractéristiques visuelles locales. Ce sont en général des extensions spatio-temporelles de détecteurs de points d'intérêt en 2D et de descripteurs utilisés avec succès pour la reconnaissance d'objets dans des images (voir par exemple les résultats des compétitions PASCAL VOC[START_REF] Everingham | The Pascal Visual Object Classes (VOC) Challenge[END_REF]). Les caractéristiques locales de vidéo, telles que les points d'intérêt spatio-temporels[START_REF] Laptev | On space-time interest points[END_REF]], décrivent l'apparence (comme avec les histogrammes de gradients orientés[START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) ou le mouvement (comme avec les histogrammes de ot optique[START_REF] Laptev | Learning realistic human actions from movies[END_REF]) de volumes spatio-temporels locaux. Grâce à la robustesse des descripteurs locaux et à leur absence d'hypothèses globales (sur les relations géométriques par exemple), les caractéristiques locales ont

Fig

  Fig. A.6: Bag-of-features : un modèle robuste qui agrège les caractéristiques spatiotemporelles locales en les quantiant sur un vocabulaire de caractéristiques prototypiques appelées mots visuels, par analogie avec le modèle de texte par sac de mots.

Fig. A. 7 :

 7 Fig. A.7: Illustration de trois actoms pour l'action s'asseoir de notre Actom Sequence Model (ASM) : succession de parties temporelles modélisées par l'agrégation de caractéristiques locales ancrées dans le temps.

  Fig. A.9: Combinaison entre bag-of-features non structuré (à gauche) et dépendances temporelles (à droite) modélisées par des opérateurs d'auto-corrélation dans le noyau DACO.

  associé à un modèle génératif séquentiel, comme un HMM, dans le but d'obtenir une représentation de longueur xe basée sur un nombre xe d'états latents. De plus, pour pouvoir estimer la structure temporelle de taille variable d'une action, cela nécessite une distribution de probabilité plus complexe qu'un histogramme de distances entre actoms comme utilisé dans ASM. Une extension directe de notre approche consisterait à utiliser à la place deux distributions temporelles : une pour le nombre de parties temporelles, et une autre distribution conditionnelle sur la position des actoms sachant le nombre d'actoms. Cependant, cela suppose de fortes hypothèses d'indépendance qui ne seraient pas nécessairement vériées en pratique. Idéalement, il faudrait estimer conjointement à la fois le contenu, le nombre et la position des actoms, au lieu de le faire indépendemment. Ceci est particulièrement important pour la localisation simultanée de plusieurs actions dans une même vidéo. Apprentissage faiblement supervisé. Nous avons démontré que des modèles d'action peuvent être nettement améliorés en apprenant à partir d'une décomposition signicative étiquetée manuellement, au lieu d'une simple fenêtre temporelle. Cette supervision a cependant un coût qui doit être minimisé

  partage plusieurs similarités avec les approches récentes de co-segmentation d'images. Par exemple, Joulin et al. [2012a] se base sur de multiples images et leurs étiquettes globales de catégories pour segmenter par un algorithme de partitionnement discriminatif. Il semblerait donc possible de pouvoir adapter ces algorithmes d'apprentissage faiblement supervisés (comme par exemple [Joulin et al. 2012b]) an de trouver la structure spatio-temporelle latente des actions à partir d'un ensemble de vidéos faiblement annotées.

  concentrant sur une seule activité. Lorsque la vidéo est seulement temporellement segmentée et contient plusieurs activités concurrentes, nous pouvons adapter notre méthode pour se restreindre à des sous-parties de la vidéo en mettant en correspondance des sous-arbres, au lieu de comparer la totalité de notre représentation hierarchique. En complément des algorithmes existants et ecaces d'appariement de sous-arbres, (cf.[START_REF] Valiente | Algorithms on Trees and Graphs[END_REF]), nous pourrions également adopter une approche d'appariement gloutonne coarse-to-ne an d'accélérer les calculs. En s'appuyant sur la propriété d'additivité des BOFtrees, nous pouvons en eet approcher un sous-arbre par une de ses arêtes supérieures (père, ls), comme dans notre noyau ATEP. C'est pourquoi nous pourrions seulement appairer les arêtes des BOF-trees, et parcourir l'arbre de haut en bas de manière analogue à une stratégie par séparation et évaluation.Appliquer notre méthode à des vidéos de longue durée comme celles étudiées/considérées par nos modèles ASM requiert une approche diérente. En eet, la construction descendante de notre modèle arborescent suppose que toutes les tracklets soient disponibles simultanément. Par conséquent, notre algorithme de segmentation doit être précédé d'une phase de segmentation temporelle à la volée par exemple en utilisant un détecteur de changement de plan pour des vidéos éditées telles que les lms, ou plus généralement un algorithme de détection de point de changement comme[START_REF] Harchaoui | Kernel change-point analysis[END_REF] an de dégager d'abord les racines des arbres à construire.Extensions du modè par séries temporellesCombinaison de DACO et de ASM. Nos résultats suggèrent que notre noyau DACO est particulièrement adapté aux actions courtes, et améliore la performance des noyaux par agrégation. Il semblerait donc possible d'améliorer les comparaisons entre actoms réalisées dans ASM en calculant non seulement la similarité entre le contenu des actoms, mais aussi en comparant leur dynamique avec DACO. En eet, la faible durée des actoms signie qu'ils peuvent être considérés comme des séries temporelles quasi-stationnaires. De plus, les poids des images dérivés des modèles d'actom peuvent être directement intégrés dans DACO en les appliquant aux projections des BOFs de chaque image dans le RKHS associé au noyau entre images. Version courte durée de DACO. Comme semblent le montrer nos résultats sur la base de données Youtube, la principale limitation de notre noyau DACO provient de son hypothèse de stationnarité, qui est souvent fausse dans le cas d'actions longues et complexes. C'est pourquoi une extension naturelle de notre approche consiste à calculer une version courte durée de DACO, par exemple en convoluant successivement les images avec une fenêtre temporelle Gaussienne de courte durée. Les séries temporelles de courte durée peuvent en eet être consiérées comme quasi-stationnaires, puisqu'il y a tout simplement moins d'observations pour remarquer un changement signicatif dans la distribution d'images. Cette approche pose cependant le problème suivant : la dynamique des séries est modélisée par une séquence d'opérateurs d'autocorrélation locaux au lieu d'un seul global. Par conséquent, un autre noyau doit être utilisé an de combiner les comparaisons locales de fenêtres obtenues avec DACO. Notons que l'application de cette idée au calcul d'une version fenêtrée du noyau d'auto-régression donne une représentation intéressante du signal vidéo, qui partage des similarités avec les codes linéaires prédictifs, très utilisés en traitement de signaux sonores et de la parole en particulier. Analyse de séries temporelles d'actions. La plupart des outils construits pour analyser des séries temporelles sont conçus pour des données univariées, comme des signaux sonores ou l'évolution de prix sur un marché nancier. Cependant, les vidéos reposent sur des représentations en haute dimension. C'est pourquoi l'analyse de leurs propriétés temporelles comme la périodicité nécessite des techniques diérentes, adaptées à ces signaux complexes et multivariés. Par exemple, Cutler and Davis [2000] plus d'une décennie avant nous utilisa des techniques d'analyse temps-fréquence sur des autosimilarités temporelles an de détecter des mouvements périodiques. Nous avons montré que l'opérateur d'auto-corrélation dans un RKHS d'image est un objet mathématique qui peut être utilisé pour étudier les propriétés temporelles des actions. Nous pensons que ce cadre formel, bien qu'embryonnaire, peut ouvrir la voie à une analyse plus sophistiquée des actions, en généralisant le grand nombre d'outils qui existent déjà pour des séries univariées, comme la nance ou le traitement de la parole et du son. Nous pourrions par exemple étendre la notion de corrélogramme et construire un corrélogramme d'action en utilisant la norme de Hilbert-Schmidt de l'opérateur d'auto-corrélation, an de mesurer le caractère aléatoire d'une action, pour la détection de comportements anormaux notamment.

  Sequential approaches . . . . . . . . . . . . . . . . . . 14

			Chapter 2 Related Work
	Contents
	2.1	Global representations	. . . . . . . . . . . . . . . . . .	14
	2.1.1

2.1.2 Volumetric approaches . . . . . . . . . . . . . . . . . . 16 2.2 Local features . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Types of local features . . . . . . . . . . . . . . . . . . 19 2.2.2 Local classiers . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 Bag-of-features . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Structuring collections of local features . . . . . . . . 23 2.3.1 Modeling relations between local features . . . . . . . 23 2.3.2 Structuring groups of local features . . . . . . . . . . . 26

Table 3 .

 3 1: Action localization results in Average Precision (in %) on the Coee and Cigarettes dataset. ASM refers to our method.

	Method	Open Door	Sit Down
	matching criterion: OV20
	DLSBP [Duchenne et al. 2009]	14	14
	BOF	8 (±3)	14 (±3)
	BOF T3	8 (±1)	17 (±3)
	ASM	14 (±3)	22 (±2)
	matching criterion: OVAA
	BOF	4 (±1)	3 (±1)
	BOF T3	4 (±1)	6 (±2)
	ASM	11 (±3)	19 (±1)

Table 3

 3

.2: Action localization results in Average Precision (in %) on the DLSBP dataset. ASM refers to our method.

table 3

 3 denoting clearly separated actoms, whereas for Sit Down we obtain ρ = 120% and p = 50%, denoting actoms sharing a signicant amount of frames.

	.4, we report localization results for ASM with learned parameters
	cf. an example in Figure 3.5 and for dierent parameter congurations
	corresponding to the four corners in Figure 3.3. These results show that
	learning action-specic ASM overlap and peakyness parameters yields the
	most accurate models, resulting in increased localization performance. Note

that the learned parameters change from one action to another. For instance, the learned parameters for Smoking are ρ = 25% and p = 70%, Table 3.4: Impact of the ASM parameters: ρ (overlap) and p (peakyness). Average of the localization results on Coee and Cigarettes (C&C) and DLSBP.

Table 4

 4

	.1 contains a summary of all notations used to describe the methods
	and kernels we compare in our experiments.

Table 4 .

 4 2 reports performance comparisons between our unstructured and structured baselines, the state of the art, and our method.

	SDT tree & ATEP SDKM tree & ATEP	85.0 77.8	SDT tree & ATEP	56.5
	SDT tree & ACP	79.3	SDKM tree & ATEP	55.3
	SDKM tree & ACP	70.6	SDT tree & ACP	51.3
	SDT leaves & ACP SDKM leaves & ACP spectral & ACP kmeans & ACP BOF tracklets	77.9 72.2 71.7 70.8 76.6	SDKM tree & ACP SDT leaves & ACP SDKM leaves & ACP spectral & ACP kmeans & ACP BOF tracklets	46.5 47.0 45.3 48.9 50.1
	BOF STIPS	61.3
	Brendel and Todorovic [2011] 77.3
	Niebles et al. [2010]	72.1
	(a) Olympics Sports (Accuracy in %)

Table 5 .

 5 on UCF Sports and by +3.7% on the Youtube dataset. 3: Accuracy on the Youtube dataset[START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF]].

				Schüldt et al. [2004]	71.7
	classes boxing handclapping 97.9 DME DACO DME+DACO 100 100 100 92.4 97.9 handwaving 92.4 91.7 91.7 jogging 95.8 92.4 94.4 running 80.6 84.0 85.4 walking 100 100 100	Laptev et al. [2008] Niebles et al. [2010] Brendel and Todorovic [2010] 94.2 91.8 91.3 Sun et al. [2011] 100 Wang et al. [2011] 94.2 BOF 94.8 DME 94.4 DACO 93.4 DME+DACO 94.9
	Table 5.1: Accuracy on the KTH dataset [Schüldt et al. 2004].
	classes bench diving golf high bar horse riding kicking running skateboarding 66.7 DME DACO DME+DACO 100 95.0 100 100 100 100 94.4 88.9 88.9 100 92.3 100 75.0 83.3 75.0 85.0 100 100 53.8 69.2 76.9 50.0 66.7 walking 95.5 95.5 95.5 weightlifting 100 100 100	Rodriguez et al. [2008] Wang et al. [2009] Kläser et al. [2010a] Kovashka and Grauman [2010] 87.27 69.2 85.6 86.7 Weinland et al. [2010] 90.1 Le et al. [2011] 86.5 Sun et al. [2011] 86.9 Wang et al. [2011] 88.2 BOF 86.5 DME 87.0 DACO 87.4 DME+DACO 90.3
	Table 5.2: Accuracy on the UCF Sports dataset [Rodriguez et al. 2008].
	classes	DME DACO DME+DACO
	basketball biking diving golf horse riding soccer swinging tennis trampoline volleyball walking a dog 74.8 66.7 92.4 82.1 51.4 98.1 95.5 96.5 95.1 88.3 84.8 84.0 80.1 86.9 87.6 79.6 66.5 92.4 89.9 94.0 85.3 52.0	72.5 91.7 98.1 95.1 90.4 84.6 86.9 82.0 95.8 75.6 94.0	Liu et al. [2009] Ikizler-Cinbis and Sclaro [2010] 75.21 71.2 Brendel and Todorovic [2010] 77.8 Le et al. [2011] 75.8 Wang et al. [2011] 84.2 BOF 84.4 DME 86.7 DACO 79.1 DME+DACO 87.9

  w.r.t. DME, +1.4% w.r.t. DACO) and the UCF Sports (+23.1% w.r.t. DME, +7.7% w.r.t. DACO) datasets, which have discriminative dynamics (DACO alone outperforms DME by +3.4%, resp. +15.4%, on KTH, resp. UCF sports); • the basketball shooting action from the Youtube dataset (+5.8% w.r.t. DME, +21.1% w.r.t. DACO), which is the most dicult category of Youtube (it has the lowest accuracy with DME), and, therefore, the largest margin for improvement. Actions that are not improved by the combination of DME and DACO include:

  Depuis lors, la vidéo est devenue un des médias les plus populaires pour la communication et le divertissement. En 2010, 441 milliards de vidéos étaient accessibles en ligne, ce qui correspond approximativement à 10 21 pixels 1 . En 2011, le site web YouTube avait plus de mille milliards de vues, et plus de 800 millions de visiteurs uniques regardaient plus de 3 milliards d'heures de vidéos par mois. La création de contenu est également en pleine explosion, avec une nouvelle heure de vidéo mise en ligne sur YouTube chaque seconde 2 .Fin 2012, la vidéo représentera plus de 50% du trac internet, avec un taux de croissance annuelle de 48% 3 .

	123
	appareil reposait sur la projection rapide d'une succession d'images depuis des
	disques en verre tournants. Peu après, Auguste et Louis Lumière brevetèrent
	le Cinématographe à la fois caméra, projecteur et révélateur de lm en
	1895 et commencèrent à produire les tous premiers lms jamais réalisés.
	Le principal challenge auquel les utilisateurs de ces technologies font actuel-
	lement face est de trouver le contenu qu'ils recherchent parmi la quantité
	massive de données disponibles. En raison de l'énorme quantité de vidéos
	existantes, répondre à cette question nécessite des outils pour automatiser
	l'analyse, l'indexation et l'organisation de leur contenu.
	Notre travail se concentre sur la reconnaissance d' actions, l'une des in-
	Le développement de l'analyse vidéo est indissociable du progrès des appa-formations visuelles les plus présentes dans les données vidéo. La vision par
	reils d'enregistrement et de projection. Pendant longtemps, un grand nombre ordinateur a fait récemment des progrès signicatifs dans le domaine de la
	d'appareils permettaient de montrer des mouvements à partir de séries de reconnaissance d'actions notamment pour des tâches particulières comme
	dessins. Ces appareils se basent sur l'illusion d'optique découverte en 1912 la vidéosurveillance. Néanmoins, les méthodes de l'état de l'art actuel sont
	par Max Wertheimer appelée Beta mouvement, par laquelle le cerveau encore loin de pouvoir comprendre toute action dans n'importe quel type de
	combine une succession d'images xes pour former une impression de mouve-vidéo. Ceci peut être mesuré par la faible performance des systèmes impliqués
	ment. Le Zoetrope roue de la vie en grec est un exemple d'un dispositif dans la tâche Multimedia Event Detection (MED) de TRECVID [Smeaton
	populaire produisant l'illusion de mouvement à partir d'une succession rapide et al. 2006] une compétition d'interprétation automatique de vidéo. Pour
	d'images placées à l'intérieur d'un cylindre tournant muni de fentes verticales l'édition de 2011 [Over et al. 2011], les systèmes soumis avaient une moyenne
	jouant le rôle d'obturateur. de 6% de faux positifs, avec 54% de détections manquées, sur des actions
	Les premiers vidéo-projecteurs combinaient les mêmes idées avec les pro-simples telles que préparer un sandwich et brosser un animal.
	grès de la photographie attribués à Daguerre and Niépce (1839). Par
	exemple, Muybridge inventa le premier projecteur de lm le Zoopraxi-
	scope (1879) dans le but de présenter ses photographies "stop-action". Cet

La vidéo comprend un large éventail de sources et d'applications : la vidéosurveillance, le contrôle industriel, la robotique (comme les véhicules autonomes), la domotique, les systèmes d'interaction homme-machine, les jeux vidéo (comme le Kinect de Microsoft pour la console de jeux Xbox), les plateformes de contenu internet (comme YouTube et DailyMotion), les séries TV et les lms.

Le but commun à toutes ces applications est de capturer et transmettre les informations visuelles d'une scène réaliste sur une certaine période de temps.

  .1. OBJECTIFS 125 en utilisant des caractéristiques locales robustes, et en capturant des propriétés structurelles des actions qui sont essentielles à leur reconnaissance. Un autre ensemble de challenges résulte de la confusion entre classes. En eet, la distinction est souvent subtile entre des actions de classes diérentes. Les actions courir et marcher partagent par exemple des mouvements similaires. Une analyse minutieuse du mouvement est donc nécessaire pour distinguer ces deux catégories. La modélisation précise des spécicités d'une action est particulièrement importante en conditions non contrôlées, où un algorithme de reconnaissance doit distinguer les actions intéressantes parmi tous les autres événements possibles. Une fois encore, nous nous attaquons à ce problème en utilisant la structure des actions pour construire et comparer des modèles d'action plus détaillés.La reconnaissance d'actions comprend deux tâches principales : la classication et la localisation. D'une part, la classication a pour but d'assigner une étiquette sémantique à une vidéo focalisée sur une action. D'autre part, l'objectif de la localisation est de proposer une étiquette sémantique ainsi que son étendue spatio-temporelle, pour des vidéos pouvant contenir plus d'une action. En pratique, ces deux problèmes sont étroitement liés, dans la mesure où les méthodes de localisation consistent souvent à appliquer un classieur à diérentes positions an de déterminer les plus probables. Dans les deux cas, nous reconnaissons des catégories d'action, et nous étudions des algorithmes d'apprentissage supervisé pour résoudre ces problèmes : étant donné une liste de catégories d'actions, nous apprenons un modèle en utilisant des exemples de vidéos correspondant à chaque catégorie.Comme dit précédemment, nous supposons qu'une action est caractérisée par des relations spatio-temporelles entre sous-événements. Nous armons et vérions expérimentalement qu'extraire cette information structurelle et notamment les structures temporelles est particulièrement important pour la reconnaissance d'action, an d'être robuste aux conditions non contrôlées des vidéos, et de pouvoir lever l'ambiguïté entre des catégories similaires. Notre objectif principal est d'apprendre de meilleurs modèles d'action en découvrant et en utilisant cette structure. La diculté majeure repose sur comment identier, représenter et intégrer avec des techniques d'apprentissage statistique, les aspects structurels pertinents d'une action. Nous étudions diérentes possibilités : des séquences d'actions atomiques, des décompositions hiérarchiques du mouvement, et des dépendances temporelles entre images.

A

  Nous validons expérimentalement les approches que nous proposons an de répondre aux questions suivantes : quelles sont les bonnes unités à considérer pour décomposer les actions ; quelle est la structure intéressante des actions ; comment extraire et représenter la structure de manière robuste ; comment apprendre et comparer les modèles structurés d'action. Nos contributions sont décrites dans les paragraphes suivants. Dans le but de localiser des actions simples, comme ouvrir une porte, dans de longues vidéos non segmentées, nous introduisons une extension temporellement structurée de bag-of-features : le Actom Sequence Model (ASM). Nous décrivons une action comme une séquence d'unités atomiques d'action, appelées actoms, qui sont des parties temporelles sémantiquement signicatives et caractéristiques de l'action. ASM représente la structure temporelle des actions comme une séquence d'histogrammes de caractéristiques visuelles ancrées sur les actoms (cf. Figure A.7). La phase d'apprentissage nécessite l'annotation des actoms pour les exemples d'action. A l'étape de test, les actoms sont détectés automatiquement à l'aide d'un modèle non paramétrique, qui agit comme une distribution a priori sur la structure temporelle d'une action. Nous proposons une approche de détection par image centrale glissante : toutes les N images, nous évaluons la probabilité qu'une action soit centrée à une image particulière t en marginalisant sur notre a priori temporel : la j ème séquence d'actoms candidate dans le modèle temporel que nous avons appris, P( ∆j ) est sa probabilité a priori estimée à partir des données, et f ASM (t, ∆j ) est la probabilité a posteriori retournée par notre classieur ASM. Nous présentons des résultats expérimentaux obtenus sur les bases de données réalistes Coee and Cigarettes [Laptev and Pérez 2007] et DLSBP [Duchenne et al. 2009]. Nous adaptons également notre approche au problème de classication par détection et démontrons son applicabilité sur la base de données Hollywood 2 [Marszalek et al. 2009]. Nous montrons que notre méthode ASM fait mieux que (i) l'actuel état de l'art en localisation temporelle d'action, ainsi que (ii) les méthodes classiques combinant bag-of-features avec une méthode de localisation par fenêtre glissante. Ce travail a été publié dans [Gaidon et al. 2011a].

	Actom models (time-dependent voting)
	t 1	r 1	r 2	t 2	t 3	r 3	t
	Actom Sequence Model
	Actom 1	Actom 2		Actom 3

P(action at t) =

s j=1 f ASM (t, ∆j ) P( ∆j ) (A.1) où ∆j est per-actom histograms of time-anchored visual words Quantized local spatio-temporal features

http://www.comscore.com

http://www.youtube.com/t/press_statistics

http://www.cisco.com

1.2. CONTEXT

1.3. CONTRIBUTIONS

4.2. CLUSTERING DENSE TRACKLETS

4.4. EXPERIMENTS

Σ(x)τ =

BOF tracklets bag-of-features with all tracklets as in [Wang et al. 2011], equal to the root of a BOF-tree BOF STIPS bag-of-features with spatio-temporal interest points as in [START_REF] Laptev | Learning realistic human actions from movies[END_REF]

Practical formulation of DACO

In the following section, we give a practical formulation of the DACO distance that is obtained by kernelizing Equation 5.3, i.e., expressing it using only inner products between frames, computed via a kernel function.

Kernelized DACO

Frame representations are in general high-dimensional (e.g., several thousands of dimensions for BOF) and can be of a non-vector type (e.g., graphs). Therefore, instead of making assumptions on the frame models, we only assume the availability of a symmetric positive-denite kernel between frames k F : X × X → R, such as the intersection kernel between per-frame BOFs.

We note H F the feature space, and φ F : X → H F the feature map associated with the kernel k F (x t , y t ′ ) = φ F (x t ), φ F (y t ′ ) H F between two frames x t and y t ′ of two series x and y. H F might be innite-dimensional, for instance when the Gaussian RBF kernel is used. Yet, using the kernel trick, our kernel can be computed only by using kernel evaluations between frames.

In the following, we adopt notations similar to those of Shawe-Taylor and Cristianini [2004]. Corresponding to the video x, we dene the time series X of frames in the frame feature space

where the column t of X is the projection φ F (x t ) of frame x t . For two time series x = (x t ) t=1•••T , y = (y t ′ ) t ′ =1•••T ′ and their representations X and Y, the matrix K of kernel evaluations between frames of both series is noted:

(5.7)

Using our previous notations, we dene the auto-covariance of action x at lag τ in the frame feature space H F as: is a mathematical object that can be used as a proxy to study the temporal properties of actions. We believe that this formal framework, although embryonic, can pave the way for more sophisticated analysis of actions by generalizing the numerous tools that already exist for such tasks in univariate settings such as in nance, or speech and audio processing. For instance, we could extend the notion of correlogram to build an action correlogram by using the Hilbert-Schmidt norm of the auto-correlation operator in order to measure the randomness of an action, e.g., for abnormal behavior detection.

Publications

This thesis has led to several publications summarized below.

International conferences