E Ramasso

C Panagiotakis

M Rombaut

D Pellerin

Belief Scheduler based on model failure detection in the TBM framework. Application to human activity recognition

Keywords: Sequence recognition, Belief finite state machine, Transferable Belief Model, Temporal Evidential Filter, Conflict, Human motion analysis

A tool called Belief Scheduler is proposed for state sequence recognition in the Transferable Belief Model (TBM) framework. This tool makes noisy temporal belief functions smoother using a Temporal Evidential Filter (TEF).

The Belief Scheduler makes belief on states smoother, separates the states (assumed to be true or false) and synchronizes them in order to infer the sequence. A criterion is also provided to assess the appropriateness between observed belief functions and a given sequence model. This criterion is based on the conflict information appearing explicitly in the TBM when combining observed belief functions with predictions. The Belief Scheduler is part of a generic architecture developed for on-line and automatic human action and activity recognition in videos of athletics taken with a moving camera. In experiments, the system is assessed on a database composed of 69 real athletics video sequences. The goal is to automatically recognize running, jumping, falling and standing-up actions as well as high jump, pole vault, triple jump and long jump activities of an athlete. A comparison with Hidden Markov

Introduction

Context

Human motion analysis is an important topic of interest in the Computer Vision and Video Processing communities. Research in this domain is motivated by the diversity of applications such as automatic surveillance [START_REF] Hu | A survey on visual surveillance of object motion and behaviors[END_REF], video indexing and retrieval [START_REF] Messer | A unified approach to the generation of semantic cues for sports video annotation[END_REF][START_REF] Ozer | A hierarchical human detection system in uncompressed domains[END_REF], human-computer interaction [START_REF] Jaimes | Multimodal human computer interaction: A survey[END_REF] and biometrics [START_REF] Green | Quantifying and recognizing human movement patterns from monocular video images -part II: Applications to biometrics[END_REF]. The analysis of human motions generally consists of human detection, tracking [START_REF] Munoz-Salinas | Multi-camera people tracking using evidential filters[END_REF] and activity understanding [START_REF] Moeslund | A survey of advances in visionbased human motion capture and analysis[END_REF] where detection and tracking aim at locating human limbs while activity understanding is a higher level task aiming at recognizing human actions and using ordered sequences of actions to recognize activities [START_REF] Shah | Understanding human behavior from motion imagery[END_REF].

Hidden Markov Models (HMM), initially proposed for speech processing [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] is the most common method used for human action and activity recognition. Like most approaches in human motion analysis, and more generally in sequence recognition, HMM rely on Probability Theory. Several drawbacks inherent to these usual methods can be mentioned [START_REF] Jaimes | Multimodal human computer interaction: A survey[END_REF][START_REF] Shah | Understanding human behavior from motion imagery[END_REF].

First, intensive learning of models is necessary, using large and representative databases representing actions and activities. In these models, adding new information is difficult and generally implies re-estimating the model parameters. Moreover, it is difficult to interpret the models and therefore, a user can barely understand action and activity models since the systems gen-erally appear as "black boxes". Lastly, actions and activities of humans can generally not be separated. Indeed, in the state of the art, one model is built for each activity and a log-likelihood is computed for the sequence. However, information on actions within activities is not available or not reliable.

Using the Transferable Belief Model for sequence recognition

Possibility, probability and belief functions are three alternative measures of uncertainty used for knowledge representation [START_REF] Klir | Uncertainty-based information[END_REF]. A belief function is a general measure that can encode and combine a variety of knowledge wider than probability measures and was the basis of Dempster-Shafer's theory of evidence and of the Transferable Belief Model (TBM) [START_REF] Shafer | A mathematical theory of Evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF][START_REF] Smets | Advances in the Dempster-Shafer Theory of Evidence -What is Dempster-Shafer's model ?[END_REF]. Recently, new tools were proposed for pattern recognition that showed the efficiency of approaches based on belief functions [START_REF] Denoeux | Classification using belief functions: The relationship between the case-based and model-based approaches[END_REF][START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF][START_REF] Quost | Pairwise classifier combination using belief functions[END_REF][START_REF] Masson | ECM: An evidential version of the fuzzy Cmeans algorithm[END_REF]. In this paper, we consider the general and sound framework of the TBM proposed by Smets and Kennes [START_REF] Smets | The Transferable Belief Model[END_REF] as an alternative to probability methods for temporal sequence modeling and recognition.

The TBM applications in the context of state sequence recognition and in human motion analysis from video is just in its infancy, partially because the TBM is a recent theory compared to Probability Theory. Human motion analysis based on the TBM was pioneered by Hammal et al. [START_REF] Hammal | Belief theory applied to facial expressions classification[END_REF][START_REF] Hammal | Facial expression classification: An approach based on the fusion of facial deformations using the transferable belief model[END_REF] and Girondel et al. [START_REF] Girondel | Belief theory-based classifiers comparison for static human body postures recognition in video[END_REF]. However the authors focus on static recognition of human expressions and postures and thus the dynamic aspects of human motion were not modeled.

One of the first tools used for the analysis of state sequence in the TBM was proposed by Rombaut et al. [START_REF] Rombaut | State recognition in discrete dynamical systems using Petri nets and Evidence theory[END_REF] in 1999. The authors developed a generalization of a Petri Net to belief functions based on the Generalized Bayesian Theorem (GBT) [START_REF] Smets | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF]. This Belief Petri Net is, however, not robust to noise because links between states at successive times are given by an evolving and sparse transition matrix depending on sensor measurements. Moreover, no classification criterion was proposed.

The second tool is the generalized HMM proposed in 2000 by Mohamad and Gader [START_REF] Mohamed | Generalized hidden Markov models -part i: Theoretical frameworks[END_REF] where the generalization is narrowed down to possibility measures and thereby their framework is not able to manage belief functions. One advantage of their framework is the possibility of managing dependent observations by using fuzzy operators but the authors used the product, thereby assuming statistical independence.

The third tool is the generalized Kalman filter [START_REF] Smets | Kalman filters for tracking and classification and the Transferable Belief Model[END_REF] proposed by Smets and Ristic in 2004 for joint tracking and classification in the TBM framework.

The Kalman equations in the tracking step are quite similar to the probabilistic version but the TBM showed better results for the classification step on a military problem using implication rules. The first problem with the generalized Kalman filters for the application concerned on human motion analysis is that they rely on linear dynamic systems that must be identified.

However, human motions can be highly non-linear and depend on the camera view-point and thus are not known in advance, except in specific situations. Moreover, as presented in Section 2, five features are extracted and twenty actions are detected in four types of jumps, thus the number of parameters can be high. In [START_REF] Munoz-Salinas | Multi-camera people tracking using evidential filters[END_REF], the authors propose an alternative to a Kalman Filter using particle filter. The second problem is that Kalman filters are used when the states are continuous while we are interested in detecting human actions which are discrete. Moreover, in the classification step, the implication rules used in [START_REF] Smets | Kalman filters for tracking and classification and the Transferable Belief Model[END_REF] also require parameters that can be given by experts in some applications. Actually, HMM are preferred to Kalman filters for human motion analysis [START_REF] Hu | A survey on visual surveillance of object motion and behaviors[END_REF][START_REF] Messer | A unified approach to the generation of semantic cues for sports video annotation[END_REF][START_REF] Jaimes | Multimodal human computer interaction: A survey[END_REF][START_REF] Moeslund | A survey of advances in visionbased human motion capture and analysis[END_REF] because HMM are suitable for discrete states and one can use any type of distribution, while a Kalman filter assumes every distribution to be Gaussian.

Contributions and paper overview

The goal of the system is to determine the most likely activity defined as a sequence of actions. An activity can be described by a graph where each node corresponds to an action. At anytime, using the features extracted from the videos, the system determines what the current action is. The transition is made when the current action becomes false and the next action becomes true. All the other actions of the graph are false.

The extracted features are noisy and cannot be directly used for activity recognition. The temporal belief functions associated with the actions are made smoother by the Temporal Evidential Filter. The main contribution of this paper is a tool called Belief Scheduler [START_REF] Ramasso | Belief Scheduling for the recognition of human action sequence[END_REF], developed in the TBM framework, which recognizes states (representing actions) and sequences of states (representing activities) in an on-line manner. This tool is a deterministic state machine where transitions between states are controlled by additional parameters (experiments showed that only two parameters are really sensitive). An original inference criterion based on conflict is also proposed for sequence classification. The other contribution is the design of a generic architecture for human action and activity recognition based on the TBM. Lastly, we propose several experiments and a comparison with HMM on athletic videos.

The paper is organized as follows. Section 2 presents the components of the architecture for human motion analysis. Background on the TBM and presentation of the Temporal Evidential Filter [START_REF] Ramasso | State filtering and change detection using TBM conflict -application to human action recognition in athletics videos[END_REF] (used in the Belief Scheduler) are given in Section 3. The Belief Scheduler is then described in Section 4. Finally, Section 5 provides results of experiments on human action and activity recognition.

Architecture for human motion analysis

Human action and activity recognition requires several steps that can be represented as in the architecture presented in Fig. 1. The proposed architecture is built so as to be generic enough to add new features and new actions. The low level part provides relevant features concerning actions that are extracted from the video stream. The high level part starts with the conversion of the feature values into beliefs on actions which are then filtered by the Temporal Evidential Filter (TEF) [START_REF] Ramasso | State filtering and change detection using TBM conflict -application to human action recognition in athletics videos[END_REF] to make action detection more reliable. Then, in order to infer activity, sequences of actions are recognized using the Belief Scheduler. A quality criterion is computed on-line to assess the confidence of actions and activities.

Robust shape/motion features are automatically extracted each time from the video using a camera motion estimator and a tracking algorithm. The camera motion estimator [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF] provides horizontal (P hm ) and vertical (P vm ) motions as well as divergence (P div ). The dominant motion image is obtained from the camera motion estimation where the intensity of a pixel depends on its membership of the dominant motion that is assumed to be the motion of the background. Fig. 2 to running, jumping, falling and standing-up actions in a high jump sequence.

(b) depicts dominant motion for images corresponding

The second source of features is a human detection/tracking algorithm which provides human head, center of gravity and end of legs position (Fig. 2(c)) from the dominant motion images. The variation of the center of gravity (P vcg ), the angle between horizon and human axis (P swing ) are then computed.

The feature vector is denoted O t = [P hm P vm P div P vcg P swing ].

Models of actions

At anytime, only the truth of the current action and the next action is addressed. At this time, the other actions have no influence on activity recognition. The focus on these two actions can be done early by directly modeling their truth from the extracted features (graph theory approach), or can be done late after a global fusion process on all the actions (fusion theory approach). Following previous works [START_REF] Rombaut | State recognition in discrete dynamical systems using Petri nets and Evidence theory[END_REF], we have chosen the early focus for its efficiency.

We present below two evidential methods ("likelihood" and "distance" models) that link numerical features O t to belief on actions.

Basic belief assignment

As in the graph theory, the Frame of Discernment (FoD) for each action A k ∈ {running, jumping, falling, standing-up} is binary (either true or false) and denoted as Ω t k = {T t k , F t k } where time t is explicit, since we consider that belief actions evolve over time.

The power set features can be stated as a problem of pattern recognition [START_REF] Denoeux | Classification using belief functions: The relationship between the case-based and model-based approaches[END_REF], i.e. we need to build a mapping from the feature space R F to action space Ω t k . The mapping can be obtained automatically using:

2 Ω t k = {{T t k }, {F t k }, {T t k , F t k }, ∅ t k }
• The model of likelihood (MLGBT1 ) which consists in applying the Generalized Bayesian Theorem (GBT) [START_REF] Smets | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF] to likelihood conditional of action states [START_REF] Appriou | Probabilités et incertitudes en fusion de données multisenseurs[END_REF][START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF][START_REF] Denoeux | Classification using belief functions: The relationship between the case-based and model-based approaches[END_REF].

• The model of distance (EDC2 ) of Denoeux et al. [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF][START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF]. This method is interesting when the models of classes are not known and/or difficult to obtain.

In order to define the basic belief assignment (BBA) directly on Ω t k , it is necessary to build a learning set composed of two sets of features: one where action A k is true and one where action A k is false. Feature intervals where action A k is true are easy to find (using the ground truth) but the problem is to choose intervals where action A k is false. That is why we choose to model knowledge by a (BBA) named m Ω t s on the FoD Ω t s = {Run, Jmp, F al, Stu} (standing for running, jumping, falling, standing-up respectively) which is the set of the four actions. Then the BBA m Ω t k on the two actions concerned (current and next) is computed by a coarsening process, seen as a focus process.

Model of likelihood (MLGBT)

We first estimate conditional probability densities of observed features O t given each action A k . For example, the densities can be modeled by Gaussian mixtures where means and variances are estimated using an Expectation-Maximization algorithm. For each action, a learning set corresponding to 30% of the database is used (with a 3-fold cross-validation). The number of Gaussians is set using the method proposed in [START_REF] Figueiredo | Unsupervised learning of finite mixture models[END_REF]

m Ω t s [O t ](S t ) = A k ∈S t pl R F [A k ](O t ) • A k / ∈S t 1 -pl R F [A k ](O t ) (1)
where m Ω t s is a BBA defined on the set of actions Ω t s = {Run, Jmp, F al, Stu}.

The model of distance (EDC)

A learning set with D samples is available as

L = {O d , m Ωs d } where d ∈ {1, 2 . . . D} is a sample index 3 . Each sample e d
is categorical (m Ωs d (A k ) = 1, A k ∈ Ω s ) whereas if the class is unknown then m Ωs d (Ω s ) = 1.
For a given observed feature vector O t , we need to assess the BBA m Ωs [O t ] that reflects the type of action (this BBA is identical to m Ω t s but the superscript t is not used for the sake of simplicity). Using the Denoeux's distance model [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], the BBA is given by the conjunctive combination of the BBA of the K nearest neighborhoods O t determined by the Euclidean distance.

For that, let {O j , m Ωs j } ∈ L the subset of the K nearest neighborhoods. The BBA m Ωs j [O j ] for sample e j in this subset is then obtained by:

m Ωs j [O j ]({A k }) = ζ • φ q (dist(O j , O t )) m Ωs j [O j ](Ω s ) = 1 -ζ • φ q (dist(O j , O t )) m Ωs j [O j ](B) = 0, B ∈ 2 Ωs \{Ω s , {A k }} (2)
where

A k ∈ Ω t s , φ q (dist(O j , O t )) = exp(-γ q • dist(O j , O t )), the function dist(O j , O t ) is the Euclidean distance between O j and O t , γ q ≥ 0 and ζ is such that 0 < ζ < 1. The K BBA are then conjunctively combined Smets' conjunctive rule of combination (CRC) to estimate m Ωs [O t ]: m Ωs * [O t ] = m Ωs 1 [O 1 ] ∩ • • • ∩ m Ωs j [O j ] ∩ • • • ∩ m Ωs K [O K ] (3)
where the CRC ∩ is defined by:

(m Ωs 1 ∩ m Ωs 2 )(D) = B∩C=D m Ωs 1 (B) • m Ωs 2 (C) (4)
At this step, the mass m Ωs (∅) on the empty set can be different than zero.

That can correspond to a transition between two actions where they seems together true. Then we normalize the CRC as follows:

m Ωs (B) = m Ωs * (B) 1-m Ωs * (∅) , ∀B ⊆ Ω s , B = ∅.
We have set K = 5 and ζ = 0.99 using heuristics attached to the application through several tests. The value of γ q is optimized using a gradient-based method proposed in [START_REF] Zouhal | An evidence-theoretic K-NN rule with parameter optimization[END_REF] 4 . The learning set represents 30% of the whole dataset (as for the MLGBT model).

Coarsening process

In both modeling methods (MLGBT and EDC), the FoD is Ω t s . Because we have chosen to focus early on the current action and the next action, the BBA m Ω t s is then coarsened onto one m Ω t k for these actions. The coarsening process is then:

m Ω t k (T t k ) ← m Ω t s (A k ) m Ω t k (F t k ) ← A k ∩B k =∅ B k ⊆Ω t s m Ω t s (B k ) m Ω t k (T t k ∪ F t k ) ← A k ∩B k =∅ B k =A k ,B k ⊆Ω t s m Ω t s (B k ) (5)
where A k is the current and next actions and B k is the other actions known as false. Fig. 9 depicts some results (output of the modeling process).

Another alternative could be to directly carry out a coarsening process from Ω t s to the frame of discernment Ω t i,i+1 where A i is the current action and A i+1 is the next action. The effect of that alternative is similar to the previous one.

Temporal Evidential Filter for action state filtering

Because the features extracted from the videos are noisy, not perfectly reliable and conflicting, it is necessary to filter the BBA m Ω t k obtained previously. The Temporal Evidential Filter (TEF)

proposed in [START_REF] Ramasso | State filtering and change detection using TBM conflict -application to human action recognition in athletics videos[END_REF] makes belief on actions temporally consistent (the resulting belief has no conflict and is made smooth). On the other hand, this filter is used to detect when the states (false or true) of actions change. This filter is relatively easy to work out because the BBA m Ω t k concerned are binary. That is not the case of m Ω t s .

The TEF works on-line on each action A k independently taking as input the BBA obtained from feature fusion and the previous TEF output (Fig. 3).

In this section, the eight steps of the TEF process are recalled [START_REF] Ramasso | State filtering and change detection using TBM conflict -application to human action recognition in athletics videos[END_REF]. The F if the current model is F. These BBAs are given by:

   mΩ t k T (T t k ) = γ T • m Ω t-1 k (T t-1 k ) mΩ t k T (Ω t k ) = γ T • m Ω t-1 k (Ω t-1 k ) + 1 -γ T (6)    mΩ t k F (F t k ) = γ F • m Ω t-1 k (F t-1 k ) mΩ t k F (Ω t k ) = γ F • m Ω t-1 k (Ω t-1 k ) + 1 -γ F (7)
In this paper we always have set parameters γ T and γ F to 0.9. It is important to note that the masses sum to one because of the redistribution rule proposed in step 6 that compels the mass at t -1 to be a simple belief function.

2-Fusion of prediction and measure:

mΩ t k M ∩ m Ω t k [O t ] combines the
available information (prediction and observation), where the operator ∩ is the conjunctive rule of combination defined in equation 4.

3-Conflict:

ǫ t k = mΩ t k M ∩ m Ω t k [O t ] (∅ t k
) quantifies the contradiction between model of belief evolution and data. The higher the conflict, the higher the necessity to change the current model (true or false). We thus introduce the concept of unlikelihood in order to give a semantic to the conflict value.

4-Cusum: CS

k (t) = λ × CS k (t -1) + ǫ t
k builds the cumulative sum of conflict along time where λ ∈ [0, 1] is a fader coefficient to cope with low/high variation of conflict (smoothing).

5-Decision on model change: when the cumulative sum is too high, i.e. if CS k (t) > T k s (stop threshold) at time t s , the model is changed. The other model is applied from t s and belief on interval of times [t s -W, t s ] is compelled to be vacuous (i.e. m Ω t k (Ω t k ) = 1) to emphasize action state transition (W = 3 is one window size representing transition size).

The threshold T k s can be easily estimated in four steps. These steps are described in the following (and each step is pictorially described in Fig. 4):

a) The ground truth is in the form of an interval of times where the action is really true. For instance, on Fig. 4, the ground truth appears as a bold black line on the time axis between time 48 and 61. The vertical dashed line represents the true beginning of the action. From the O t vector, the temporal belief functions are computed and represented in the first plot of Fig. 4. The blue, red and green curves represent the

evolution of m Ω t k [O t ](T t k ), m Ω t k [O t ](F t k ) and m Ω t k [O t ](T t k ∪ F t k ) respec- tively.
b) First, we set the value of T s to a unreachable value (infinity for example) and we apply the filter. Initially, the current model is the false one (F).

We thus obtain the second plot on Fig. 4. As expected, the belief on

m Ω t k [O t ](T t k
) is always zero (blue curve) due to the unreachable value of the stop threshold (no model change is possible and F is always the current one).

c) The cusum is represented in the third plot of Fig. 4. We choose a time in the ground truth where the cusum is high, for instance at t = 52 we have CS k (52) = 2. This time should obviously be chosen so as to be close enough to the beginning of the true action. So choosing T k s = 2 in this example could allow the proper detection of the action. d) We set T k s = 2 and apply the filter with this new threshold. This leads to the fourth plot on Fig. 4 where the action is correctly detected (a change correctly occurs from model F to model T model).

This estimation technique (which does not take the sequence into account) enables a rough value of the stop threshold to be estimated, that can then be refined by experiments.

6-TEF output: if the current conflict ǫ t

k is low then the output is the fusion result of prediction and observations, otherwise we maintain the prediction (cautious approach). Formally:

m Ω t k = mΩ t k M ∩ m Ω t k [O t ] if ǫ t k ≤ δ ∅ and mΩ t k
M otherwise where δ ∅ is a threshold reflecting a tolerance to the conflict adaptively computed using the mean of conflict over a window (size N = 5) of a number of times: δ ∅ = 1/N • t t i =(t-N -1) ǫ t i k . In order to remain coherent with the model of evolution that is used, the belief mass is modified as follows: if the model used is T then the belief on the empty set (m Ω t k (∅ t k )) and the belief on

F t k (m Ω t k (F t k )) are transfered onto T t
k and Ω t k respectively. The redistribution rule when the model is "T : the state is true" is given by:

m Ω t k (T t k ) ← m Ω t k (T t k ) + m Ω t k (∅ t k ) m Ω t k (Ω t k ) ← m Ω t k (Ω t k ) + m Ω t k (F t k ) m Ω t k (∅ t k ) ← m Ω t k (F t k ) = 0 (8)
A similar redistribution rule is used for the case "F : the state is false" replacing T t k by F t k . This redistribution is empirical and suitable for the TEF but one can also use other rules defined for instance in [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF][START_REF] Lefèvre | Belief function combination and conflict management[END_REF].

7-Local Quality criterion: It reflects how we can be confident in an action. This criterion is said to be "local" because it concerns only one action within a sequence. Given a model of evolution (M), we compute:

LQ ts:t i [M](T t k ) = 1 - 1 t -t s × LQ ts:(t-1) i [M](T t k ) + m Ω t k (T t k ) t -t s • (1 -ǫ t k ) (9)
for each action A k within each activity S i . This criterion represents a sliding weighted average (thus computed on-line) which uses past events and innovation. It uses conflict to weigh the current belief on T t k : the lower the conflict, the higher the confidence (or the plausibility) in the hypothesis "the true state is T t k ". The weighted sum generates a smooth evolution of the criterion over time.

8-Transition and false alarm detection:

Let say that at t 0 , an action A k in a sequence S i is true and thus filtered by the model T . When the stop threshold is reached at a given time t 1 , we compare the Local Quality criterion LQ ts:t i [M](T t k ) (of action A k in sequence S i ) with a threshold δ FA . The threshold is the minimal quality value required to make a model change valid. Thus, if the criterion is higher than δ FA , then the model change is declared to be valid. Otherwise, a false alarm occurs. In the latter case, the TEF is run again on the interval of time [t 0 , t 1 ] with a model compelled to be false (i.e. model F) and with the cusum detector shunted (i.e. it does not take into account the stop threshold on this interval).

Belief Scheduler

Activity recognition is done when the K understandable actions The models F or T are considered as resources to which actions attempt to access. To access a model, an action has to ask for it and the Belief Scheduler manages this access. Ideally, the actions are synchronized (in this case, a simple state machine can be used) but, in real cases they can be either overlapping or unconnected as is represented in Fig. 5. Using particular rules, the Belief Scheduler overcomes these problems.

Description

In the sequel, we call natural state the belief provided by the fusion process without filtering or scheduling. We call constrained state the belief provided by the scheduling process (it is constrained by the sequence).

preemption process

This process manages overlapped actions (Fig. 5

If the two successive actions are disconnected with a gap smaller than a fixed threshold ∆ F , the constrained state of A k is forced to the true state until A k+1 becomes true. However, sometimes, the gap between successive actions can be large, i.e, with a size greater than ∆ F . In this case, the action requiring a forcing, e.g. constrained state of A k , keeps on being true until the time "t F + ∆ F ". At this time, the constrained state of A k+1 is forced to be true and constrained state of A k becomes false (Fig. 5).

False alarm detection

If actions A k+1 and A k+2 are too unconnected and if A k+1 had previously preempted A k , then A k+1 can be interpreted as a false alarm (see Fig. 6).

It appears when an action becomes true instead of staying false. This false alarm procedure is applied to validate a preemption. In order to decide whether action A k+1 is a false alarm or not, we assess the recognition performance of this action. The criterion chosen is the Local Quality recognition performance LQ t P :t F +∆ F i

[T ](T t k ) (action k in sequence i) defined in equation 9 and computed on interval of times [t P , t F + ∆ F ] (the bounds are the time of preemption and of forcing). As in Section 3.5, the following rule is applied to make an action valid or not:

if LQ t P :t F +∆ F i [T ](T t k ) < δ FA then A is a false alarm
where δ FA is a crisp threshold corresponding to a severity degree on the quality. When a false alarm is detected, the context of actions at time t P (such as values of the cusum) is restored and the previous action (true before preemption), e.g. A k , becomes true again. If LQ t P :t F +∆ F i

[T ](T t k ) > δ FA then the quality is sufficient and therefore A k+2 becomes true and A k+1 and A k+2 are both validated.

When several actions perform consecutive preemption, a validation must be performed to ensure that they are not false alarms. They are stored in a FIFO queue to wait for their validation. The number of actions in the queue is limited, e.g. two actions, so when the queue is full then the oldest queued action is validated.

Activity inference

The problem is to determine which activity (sequence of actions) is the best one at a given sequence. One approach is to assign a score to each potential activity. For example, in Hidden Markov Models, inference is performed using the forward-backward algorithm which provides a log-likelihood for each activity. In this paper, we propose a criterion for on-line inference within the Belief Scheduler that is computed from the Local Quality recognition performance criterion. For that, each LQ ts:t i [T ](T t k ) (only for model true and the true hypothesis), for all actions A k in a particular activity S i (composed of K i actions) is aggregated into a Global Quality recognition performance criterion GQ t i to represent the confidence in activity S i from time t s (a given start time) to t (the current time). The aggregation is simply the arithmetic mean:

GQ t i = 1 K i n∈{1..K i } LQ ts:t n [T ](T t k ) (12)
In order to find the best activity S t * at the current time t, we maximize GQ t i over all possible sequences. Then, a threshold is applied to decide whether the recognition is satisfactory. Formally:

S t * = argmax i GQ t i > θ ( 13
)
where θ is a degree of severity on activity recognition quality which can be used for a class of rejections (if all activities are not well recognized). Its value can be the same as the false alarm threshold δ FA .

Experiments

This part concerns the testing of the action/activity recognition architecture. The goal is to assess 1) the modeling using MLGBT (Model of Likelihood based on Generalized Bayesian Theorem) and EDC methods (Evidential Distance-based Classifier) before scheduling, and 2) the performance of the belief scheduler (BS) after filtering by the TEF (Temporal Evidential Filter) and scheduling. Because the Hidden Markov Models (HMM) are a reference in such applications, we have compared the results of the proposed approach to HMM approach.

Settings

The system was tested for action and activity recognition in athletics jumps. The database5 is composed of 69 videos acquired with a moving camera and several unknown view angles. There are 26 pole vaults, 15 high jumps, 12 triple jumps and 16 long jumps equivalent to about 12620 images (with 5600 images for running, 2700 for jumping, 2550 for falling and 1770

for standing-up). The database is characterized by its heterogeneity (Fig. 7)

with a panel of view angles as well as environments and athletes (out/indoor, male, female, other moving people). The parameters of the TEF and the Belief Scheduler were tuned using 5-fold cross validations: 1) we selected 80% of the database, 2) made an estimation of the parameters so as to maximize recognition performance and 3) tested on the remaining 20%. We did it 5 times and computed the average of the performance. The best set of parameters is given in Tab. 1. 1: TEF and scheduler parameter settings for T s and ∆ F . The other parameters (λ = 0.9, γ T = 0.9, γ F = 0.9, W = 3 and δ F A = 50%) are set at the same value for all actions and all activities.

Activity Highjump Longjump Polevault Triplejump T s ∆ F T s ∆ F T s ∆ F T s ∆ F Running 3.1 10 3.1 5 3

Tests and evaluation protocol

For quantitative evaluation, an action is said to be true if its pignistic probability (BetP) [START_REF] Smets | Decision making in the TBM: The necessity of the pignistic transformation[END_REF] defined by BetP(T

t k ) = 1 (1-m(∅)) (m(T A ) + m(T A ∪F A ) 2
) is greater than 0.5 (since an action can be true or false), where m is the belief mass provided by the output of the modeling process or by the scheduler.

We then compared these decisions with the ground truth (the database was manually annotated). Recall (R) and precision (P) criteria were used [START_REF] Makhoul | Performances measures for information extraction[END_REF].

They were computed as R = C∩R From top to bottom: horizontal motion (P hm , in pixels by image), vertical motion (P vm , in pixel by image), zoom (P div ), angle (P swing , in degree) and vertical variation of center of gravity (P vcg , in pixel by image). correct images obtained by expert annotations, R is the set of retrieved images provided by the recognition module using the BetP-based criterion, and C ∩ R is the number of correctly retrieved images. In order to assess the method by only one criterion, the F 1 -measure defined as F 1 = 2×R×P R+P combines R and P.

Fig. 8 provides the noisy features measured on the video sequence and from which beliefs are computed. Action detection (Fig. 9), scheduling (Fig. 10) and the GQ evolution (Fig. 11) are illustrated for a high jump video using MLGBT (top figures) and EDC (bottom figures). On Figures 9 and10, blue curves, red curves and green curves represent respectively the evolution of the beliefs

m Ω t k (T t k ) (action A k is true), m Ω t k (F t k ) (action A k is false) and m Ω t k (T t k ∪ F t k ) (action A k is true or false) all along time.

Illustration of the belief scheduler

Let us consider that the beliefs for each action are provided by the model of distance (EDC) [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]. An example of beliefs is depicted in Fig. 9 (before scheduling) and in Fig. 10 (after scheduling). One can clearly see the differences between both modeling methods: MLGBT provides much more noisy observations but the transitions are quite gradual while EDC provides less noisy observations but the transitions are much more abrupt. The ground truth is represented as a bold black line on the time axis. The goal of the BS is to filter these beliefs, separate actions and recognize activities. The scheduler and the filter make these beliefs smoother and ensure good recognition performance (GQ = 74%).

In order to analyze the scheduler behavior, let us consider two consecutive actions, e.g. running and jumping, that correspond to the first two lines of figures 9 (input) and 10 (output). We consider the case of EDC-modeling We recall that MLGBT stands for "Model of Likelihood based on Generalized Bayesian Theorem", EDC stands for "Evidential Distance-based Classifier" and BS stands for "Belief Scheduler". In the sequel, we present action detection performance using: a1) MLGBT modeling alone, a2) MLGBT modeling coupled with BS, b1) EDC modeling alone and b2) EDC modeling coupled with BS. Tests a1) and a2) enable MLGBT to be compared with and without BS (Section 5.4), tests b1) and b2) enable EDC to be compared with and without BS (Section 5.5), tests a2) and b2) enable BS performance to be quantified with two different modelings (Section 5.6). Three sets of tables are then presented:

(
• The first set of 4-by-3 tables where four rows concern one type of "gaps".

Results of scheduling with EDC modeling

The same study as previously was done using EDC modeling. Tables 6,7, 8 and 9 present the performance of the detection of each action in each activity before (Tables (a)) and after (Tables (b)) scheduling based on EDC modeling.

Comparison between EDC and MLGBT modeling with scheduling

Table 10 presents the differences of performance of the detection of each action (action names are not recalled for better readability) in each activity after scheduling between both EDC and MLGBT modeling. When the difference is positive, EDC+BS detection is better MLGBT+BS.

It can be observed that better results are obtained with EDC which is a method that directly computes belief functions (whereas, in MLGBT, beliefs are indirectly computed using a transformation of likelihoods into beliefs using the GBT). The difference is highly significant for high jumps and triple jumps but less significant for long jumps and pole vaults. In the last two types of jumps, running action is better detected with MLGBT because, on the one hand, it is much more highly represented in the learning set and, in the other hand, MLGBT is a probabilistic method, thus sensitive to frequent patterns.

Comparing the Belief Scheduler and Hidden Markov Model for classification

As previously, four models of activities are built (for high jumps, long jumps, pole vaults and triple jumps). Previously, transition matrix and observation mixtures of Hidden Markov Model (HMM) were learned using the BNT toolbox [START_REF] Murphy | Dynamic Bayesian networks: Representation, inference and learning[END_REF]. Each state was modeled by a mixture of Gaussians (using settings in Section 3.2).

For the comparison, we used the same mixtures of Gaussians for both systems (and only MLGBT modeling). Likelihoods provided by the tures of Gaussians are transformed into belief functions using the Generalized Bayesian Theorem (Eq. 1). To assess both systems, we used the Viterbi algorithm for HMM [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] and the GQ criterion for the Belief Scheduler. The Viterbi algorithm was applied given each model of jumps providing four loglikelihoods, one for each sequence retrieved. The video was classified as a particular jump if the log-likelihood of this jump is the highest one. For the same video, we applied the Belief Scheduler and we chose the model that maximizes the Global Quality recognition performance criterion. The experiments on a first real dataset have shown good performance of human motion analysis architecture and in particular of the BS used for the detection of actions and the recognition of activities. This performance is obtained without adding explicit duration of actions or activities. We have proposed a thorough comparison of two modeling methods that generate beliefs from features: the Generalized Bayesian Theorem coupled with likelihood and the distance model. The latter seems better suited to the application concerned in this paper. The difference comes from the fact that the distance model directly generates a belief function while the former generates a probabilistic result that is then transformed into a belief function. The comparison of the BS with probabilistic HMM proved the efficiency of the approach proposed. This approach has also shown limitations in detecting actions in triple jumps. Actually, triple jumps are generally the longest and, above all, the noisiest activities (due to the poor quality of the videos coming from analogical TV). The challenge was thus to detect (in noisy data) jumping and falling actions which are very short (less than 10 frames, compared to more than 160 frames for running). Therefore, when action durations are short and, at the same time, beliefs contain a lot of noise then it is difficult to set the Belief Scheduler parameters in order to extract the sequence. Some improvement can be made for instance by using the caution rules of combination instead of conjunctive rules as in equation 4. Experiments have also emphasized that the inference criterion of the BS can be used to create a class of rejections. This can improve the classification results but, above all, can point out new sequences. Since the classification criterion is bounded between 0% and 100%, it can be easily thresholded to create a class of rejections. This class is a first step toward adaptation since it gathers the cases for which the system of recognition could not take a decision. Work is under progress to pursue pattern discovery and adaptation which are promising in many applications.

Figure 1 :

 1 Figure 1: System architecture for human motion analysis.

  (a) Original video sequence. (b) Dominant motion images. (c) Human point detection and tracking.

Figure 2 :

 2 Figure 2: Original video sequence (a), dominant motion images (b) and human point detection and tracking results (c) for a high jump (with running, jumping, falling and standing-up actions).

  is made up of observations O d labeled by a belief function m Ωs d defined on the set of actions Ω s = {Run, Jmp, F al, Stu}. When the class of e d is known then the belief function

Figure 3 :

 3 Figure 3: The Temporal Evidential Filter principle.

Figure 4 :

 4 Figure4: Estimation of T s . Explanations are given in the text (in the fifth step of section 3.5. The blue, green and red curves are respectively the evolution of belief on T t k (i.e. action A k is true), on F t k (i.e. action A k is false) and on T t k ∪ F t k (i.e. action A k is true or false). Bold and black lines on the time axis represent ground truth for this video.

A

  k of the corresponding sequence have been true in the correct order. At any time, only the current action and next action states are taken into account. In the early focus process presented in this paper, the knowledge about these actions is given directly by the active models T and F, and by the BBAs m Ω t k . The method called Belief Scheduler [25] proposed for activity recognition based on the TBM is a state machine which exploits the results of the TEF to synchronize actions. It is built on the classical rules of such a machine: only the current action is assumed to be true at the given time and the other (K -1) actions are thus false. Therefore, only one action uses the model T (in its associated TEF) whereas the other (K -1) actions use the model F (in their associated TEF). The transition is passed when the current action becomes false and the next action becomes true.

Figure 5 :

 5 Figure 5: Due to data imperfection, overlapping (a) and unconnection (b) generally appear between current action A k and the next action A k+1 .

Figure 6 :

 6 Figure 6: False alarm processing. a) Natural states of A k and A k+1 . b) A k+1 is forced to be in a true state. c) A k+2 does not become true and the quality of A k+1 is bad, thus A k+1 is forced to be false.

Figure 7 :

 7 Figure 7: Heterogeneous database used for testing.

CFigure 8 :

 8 Figure 8: Features observed on the video sequence and used to compute beliefs of Fig. 9.From top to bottom: horizontal motion (P hm , in pixels by image), vertical motion (P vm , in pixel by image), zoom (P div ), angle (P swing , in degree) and vertical variation of center of gravity (P vcg , in pixel by image).

  for MLGBT the same reasoning can be applied). The scheduler starts by filtering belief on running using model T (natural true state) and uses the model F for each of the other three actions (natural or constrained false state). Then at time t ≈ 100, running becomes false and forces jumping action to become true. The natural state of running is false and the filter on running uses naturally the model F while jumping action is constrained to be true and the filter on this action uses the model T . At time t ≈ 130, the falling action makes a preemption on jumping. Then at t ≈ 155, standing-up makes a preemption on falling, and since the quality of falling is sufficient (GQ ≈ 0.95, third figure on the left of fig. 11 where GQ stands for Global Quality recognition performance), standing-up is allowed to use the model T (natural true state) while the others use model F. Finally at t ≈ 184, the sequence ends and the global quality reaches ≈ 75%.

  Log-likelihoods in HMM.

  GQ criterion in Belief Scheduler (red: errors, blue: rejection).

Figure 12 :

 12 Figure 12: Recognition criteria evolution for (a) HMM and (b) Belief Scheduler of the four jump models applied on 26 pole vault video sequences. The blue bold line represents results for pole vault model, generally better than the other ones.

Figure 13 :

 13 Figure13: Evolution of a Global Quality recognition performance criterion over time in the Belief Scheduler for a pole vault video sequence (2nd video of Fig.12). The bold curve represents the criterion evolution for the polevault model while the three other curves are highjump, triplejump and longjump.

Fig. 12

 12 Fig.12presents the evolution of log-likelihoods for HMM and of the GQ criterion for the Belief Scheduler for 26 pole vaults videos analyzed by the four models (high jump, pole vault, triple jump and long jump). The GQ criterion (Fig.12(b)) provides a more reliable decision than HMM's log-likelihoods (Fig.12(a)) since the relative difference between jumps is high, whereas loglikelihoods are sometimes very close (it is difficult to decide). The dotted line in Fig.12(b) represents the threshold on quality (50%) which was used for adaptation (class of rejections). Big blue points in Fig.12(b) represent rejection cases, whereas big red points concern recognition errors (decide high jumps instead of pole vaults). Interestingly, the system indicates that a specific model must be learnt for videos 9 and 10 (which were acquired with a distant view making the recognition difficult) and for video 19, 22 and 24 (for which the athlete motion was perpendicular to the image plane making

  In this case, the natural state of A k+1 is temporarily true (true state) from time t P and the constrained state of A k is temporarily false (false state) until validation (see Fig.5). The validation is enabled when the quality of the action A k+1 recognition (which asks for preemption) is satisfactory (Section 4.1.3 focuses on this process). Information at t = t P concerning actions (cusum, belief . . . .), i.e. the context, is stored. This allows us to restore the context in case the preemption is not enabled. Note that, at the beginning of scheduling, all actions are in the false state. An artificial initial true state action is added to the sequence (first state) that allows the Belief Scheduler to wait for a preemption of the first action.

	threshold T k+1 s	:
		if CS k+1 (t) > T k+1 s	and CS k (t) < T k s	(10)
		then preemption and t P = t (current time)

.a). At t = t P , A k is still true while A k+1 becomes true, thus two actions are true at the same time: it is said that A k+1 wants to preempt A k . This process occurs at time t = t P when the cusum CS k+1 (t) of the next action A k+1 is greater than its stop

4.1.2. forcing process

This process manages disconnected actions (Fig.

5

.b). At t = t F , the current action A k is false as well as the next action A k+1 . This process occurs at time t F when the cusum CS k (t) of the current action A k is greater than its stop threshold T k s :

if CS k (t) > T k s and CS k+1 (t) < T k+1 s then forcing and t F = t (current time)

Table

						.1 10 1.7	2
	Jumping	3.1	15	4.1	5	3.9 30 1.7	2
	Falling	3.1	5	4.1	15	4.5 30 1.7	2
	Standing-up 2.1	15	3.1	10	4.1 10 1.7	2

Table 4 :

 4 Recall (R), precision (P ) and F 1 -measure for four actions in long jumps with (a) MLGBT without scheduler and (b) MLGBT with scheduler. Table (c) is the difference of detection (for the F 1 -measure only) with and without the scheduler.

		R	P	F 1	R	P	F 1	∆(F 1 )
	Running	0.3917 0.9165 0.5488	0.5122 0.7272 0.6010	+0.0522
	Jumping	0.3212 0.8476 0.4658	0.3490 0.7694 0.4801	+0.0143
	Falling	0.3569 0.8339 0.4956	0.3945 0.7486 0.5167	+0.0210
	Standing-up 0.2058 0.9350 0.3373	0.3404 0.8576 0.4873	+0.1500
		(a)MLGBT			(b)MLGBT+BS	(c)Diff.

Table 5 :

 5 Recall (R), precision (P ) and F 1 -measure for four actions in triple jumps with (a) MLGBT without scheduler and (b) MLGBT with scheduler. Table (c) is the difference of detection (for the F 1 -measure only) with and without the scheduler.

Table 9 :

 9 Recall (R), precision (P ) and F 1 -measure for four actions in triple jumps with (a) EDC without scheduler and (b) EDC with scheduler. Table (c) is the difference of detection (for the F 1 -measure only) with and without the scheduler.

Table 10 :

 10 Differences of detection between EDC+BS and MLGBT+BS for the four actions (one line per table) in each jump (one table per jump).

Table 11 :

 11 Classification results. Left: Belief Scheduler classification using the Global Quality recognition performance. Right: HMM classification using log-likelihood. Legends: pv, lj, tj, hj and "rej " stand for pole vault, long jump, triple jump, high jump and class of rejections respectively.

Stands for Model of Likelihood based on Generalized Bayesian Theorem.

Stands for Evidential Distance-based Classifier.

We do not use t here but d since time is not important for the modeling process. Time will be explicitly taken into account during sequence recognition.

Matlab code available at http://www.hds.utc.fr/ ∼ tdenoeux/.

Some videos and results are available on the author's website: http: //www.femto-st.fr/ ∼ emmanuel.ramasso/actionActivityRecognition.htm and www. csd.uoc.gr/ ∼ cpanag/DEMOS/actionActivityRecognition.htm. Some codes for the TBM operations can be found in the TBMlab toolbox of Smets available at http: //iridia.ulb.ac.be/ ∼ psmets.

jump and the three tables represent respectively EDC performance, EDC+BS performance and difference between both. Thus, there is one set of three tables for each jump and each table presents action detection performance (Section 5.4, Tables 2,3, 4 and 5).

• The second set of 4-by-3 tables is similar to the previous but concerns the MLGBT (Section 5.5, Tables 6,7, 8 and 9).

• The last set of four tables compares MLGBT+BS and EDC+BS performances with one table for each jump (Section 5.6, Tab. 10). Performance is assessed using recall (first column named R), precision (second column named P) and F 1 measure (third column named F 1 ).

The reader may refer to the latter one (F 1 ) in each table for quick performance assessment.

Results of scheduling with MLGBT modeling

Tables 2, 3, 4 and 5 present recall, precision and F 1 -measure of action detection in each activity using MLGBT before (Tables (a)) and after (Tables (b)) scheduling using the BS. The BS performance is demonstrated on this dataset by greatly improving the detection in all jumps. The differences before and after applying the BS are explicitly given in Tables (c): if a difference is positive then it means that the belief scheduler improves the criterion. Fig. 13 depicts the evolution of a Global Quality recognition performance criterion along time (it is an on-line criterion) for a pole vault. This curve is useful for monitoring. The system indicates that the decision is "pole vault" with high quality (about 78%) and reliability (high gap with the second which is high jump). Fig. 14 describes results of action and activitie recognition for a triple jump described by eight states using the Viterbi decoder and the Belief Scheduler. Interpretation is clearly much easier using the latter.

Conclusion and future work

The generic architecture for sequence recognition applied to human motion analysis tested on real athletics videos shows the performance of the higher level part called Belief State Scheduler (BS) which carries out action (state) and activity (sequence) recognition. The BS finite state machine