Arnaud Dapogny

Kevin Bailly

Séverine Dubuisson

Dynamic facial expression recognition by joint static and multi-time gap transition classification

published or not. The documents may come

Dynamic facial expression recognition by joint static and multi-time gap transition classification

I. INTRODUCTION

Affective computing and more specifically automatic analysis of facial expressions from video sequences is a key to human-machine interactions. Applications are multiple, ranging from computer graphics animation to social monitoring or e-learning.

However, performing static facial expression classification from separate images is a challenging task as we observe large variability of lighting conditions as well as in subjects' morphology. Moreover, important pose variation may occasionally result in facial occlusions. Such difficulties can be alleviated by applying normalisation w.r.t. a neutral face representation of a specific subject [START_REF] Senechal | Automatic facial action detection using histogram variation between emotional states[END_REF], but expressions such as sadness or anger usually involve subtle face deformations that are hardly noticeable using only static information.

These subtle expressions are generally better understood by analysing the evolution of the facial deformation over time. In order to do so, the so-called dynamic approaches work under the assumption that specific facial expression video sequences are pre-segmented and that the expression evolves from a neutral face representation to the peak of a particular facial expression [START_REF] Yang | Boosting encoded dynamic features for facial expression recognition[END_REF], [START_REF] László | High quality facial expression recognition in video streams using shape related information only[END_REF], [START_REF] Rudovic | Multi-output laplacian dynamic ordinal regression for facial expression recognition and intensity estimation[END_REF]. However, such prior does not hold in more realistic scenarios, where one has to jointly address the problem of temporal segmentation and expression recognition.

In this work, we propose a new method for facial expression recognition from video sequences, that uses static and transition classifications. Both static and transition classifiers are built upon geometric and appearance features in order to robustly estimate facial expression probabilities. Transition classification probabilities are estimated from multiple time This work has been partially supported by the French National Agency (ANR) in the frame of its Technological Research CONTINT program (JEMImE, project number ANR-13-CORD-0004). gaps in the sequence then fused along with static probabilities in order to provide an expression prediction. The contributions of this work are thus three-fold:

1) A method for constructing a transition classifier from a set of image pairs that can be sampled from popular facial expression datasets. 2) A fusion model that efficiently combines static and transition information from different time gaps to recognize facial expression using both static and dynamic information. 3) A complete system that performs real-time facial expression classification from video sequences without the need of any explicit segmentation of the facial expression sequence.

To the best of our knowledge, this is the first time that such an approach is proposed that uses transition information between video frames from different time gaps to provide expression classification without requiring any prior segmentation or preprocessing of the sequences.

The rest of the paper is organized as follows: in Section II we review some existing works covering the field. In Section III we discuss the proposed method for building static and transition classifiers and combining these to apply multi-time gaps expression recognition on a video sequence. In Section IV we report evaluation results for two popular benchmarks. Finally, in Section V we present our conclusions and future works.

II. RELATED WORK

Methods that exist in the literature for automatic facial expression recognition generally belong to either static or dynamic classification systems, as highlighted in [START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions[END_REF].

On the one hand, static methods aim to recognize the expressions on each image in a separate way, without considering the relationship between the video frames. For instance, Shan et al. [START_REF] Shan | Robust facial expression recognition using local binary patterns[END_REF] introduce a static facial expression recognition system that consists of SVM classifiers built upon LBP features. Senechal et al. [START_REF] Senechal | Facial action recognition combining heterogeneous features via multikernel learning[END_REF] propose to combine AAM coefficients and LGBP histograms. Zhi et al. [START_REF] Zhi | Facial expression recognition based on graph-preserving sparse non-negative matrix factorization[END_REF] use a graph-preserving sparse NMF in order to develop an image representation that is well-suited for the classification task. Such approaches offer the advantage not to require any temporal pre-segmentation of the video sequences. However, they generally suffer from the inherent limitation of not using dynamic information to disentangle subtle emotions such as anger and sadness. Fig. 1. Flowchart of the proposed facial expression recognition framework. For each new frame, facial feature points are extracted using the algorithm from [START_REF] Xiong | Supervised descent method and its applications to face alignment[END_REF]. Geometric and appearance features for both static and transition classifiers are computed for the current frame and between this current frame and the previous ones respectively. Static and transition classification probabilities sampled at multiple time gaps are then fused to provide the final expression prediction.

On the other hand, dynamic methods either use spatiotemporal features or temporal classifiers. Spatio-temporal features capture the motion of feature points or the evolution of a texture descriptor over time. For example, Zhao et al. extend LBP features [START_REF] Shan | Robust facial expression recognition using local binary patterns[END_REF] to spatio-temporal volumes [START_REF] Zhao | Dynamic texture recognition using local binary patterns with an application to facial expressions[END_REF]. Yang et al. [START_REF] Yang | Boosting encoded dynamic features for facial expression recognition[END_REF] learn haar-like features from video cuboids using a boosting algorithm. Shojaeilangari et al. [START_REF] Shojaeilangari | Multi-scale analysis of local phase and local orientation for dynamic facial expression recognition[END_REF] compute histograms of phase and orientation as local video descriptors used for classification. Such approaches generally sample image features from a rigid time window which supposes a constant dynamic of the expression. Temporal classifiers describe the evolution of the expression from segments of a sequence. Jeni et al. [START_REF] László | High quality facial expression recognition in video streams using shape related information only[END_REF], as well as Rudovic et al. [START_REF] Rudovic | Multi-output laplacian dynamic ordinal regression for facial expression recognition and intensity estimation[END_REF], use SVM and ordinal regression from geometric features respectively. Lorincz et al. [START_REF] Lorincz | Emotional expression classification using time-series kernels[END_REF] compute dynamic programming kernels from facial feature point motion. Wang et al. [START_REF] Wang | Capturing complex spatio-temporal relations among facial muscles for facial expression recognition[END_REF] propose an interval-based temporal model to capture temporal relations between primitive facial events. However, these methods work under the assumption that the facial expression sequences are pre-segmented. Furthermore, sequence-level approaches have fewer training and testing samples as compared to frame-level methods.

Recently, some methods have been introduced that investigate temporal transitions for facial Action Unit (AU) recognition. Ding et al. [START_REF] Ding | Facial action unit detection by cascade of tasks[END_REF] introduce a three-levels cascade of tasks where dynamic information is used to learn temporal segments of AU occurrence on a fixed-size window. Transition information is thus used for the purpose of refining the AU occurence boundaries. Khademi et al. perform relative AU recognition [START_REF] Khademi | Relative facial action unit detection[END_REF] using classifiers trained upon transition features from neighbouring frames. However, they do not consider static information and use the transitions as a reference in order to estimate AU intensity for current frame.

Overall those two methods specifically aim to estimate AU activation over time. As compared to AUs which are more local in space and time, expressions describe a more global representation. As such, they generally last longer than AUs and involve larger facial deformations. For those reasons, expression recognition is often performed as a multiclass problem as compared to AUs which are evaluated separately.

III. STATIC AND MULTI-TIME GAPS TRANSITION JOINT CLASSIFICATION

A. Overview

In this section we describe our static and multi-time gaps transition joint classification method. The framework involves the following steps: first, facial feature points are extracted using the algorithm from [START_REF] Xiong | Supervised descent method and its applications to face alignment[END_REF], then we perform a static probability estimation (Section III-B) upon separate video frames along with a transition probability estimation (Section III-C) between image pairs sampled at multiple time gaps. Those transition probabilities are then combined with past predictions to give rise to a dynamic estimation of expression class probabilities (Section III-D). Finally, the system performs a fusion of static and dynamic probabilities from multiple time-gaps (Section III-E).

B. Static probability estimation

Static facial expression classification is performed as a 7class problem (the six universal expressions, plus the neutral one) using the Random Forest (RF) framework. RFs [START_REF] Breiman | Random forests[END_REF] are classifiers that are naturally suited for multiclass classification tasks. Their performance is on par with the most popular machine learning methods such as SVM or Neural Networks [START_REF] Breiman | Random forests[END_REF]. Furthermore, the RF framework provides the use of parallel implementation for the training step, as well as an easily computable error estimate for an efficient testing procedure [START_REF] Breiman | Out-of-bag estimation[END_REF].

More specifically, a set of M decision trees is built upon the training dataset by a classic greedy procedure for RF classification:

• for m from 1 to M :

1) Generate a bootstrap by randomly sampling the dataset. 2) If the class repartition of the different classes among the bootstrap subset is imbalanced, a simple downsampling procedure is applied: samples of the majoritary class are randomly drawn out of the bootstrap until an acceptable imbalance level is reached. 3) If the data at current node (initially at the tree root) is homogeneous with class c i , then a terminal node is set, and terminal probabilities p m (c i ) of facial expression are set to 1 for c i and 0 for other classes. 4) If the classes are not homogeneous, we randomly generate a set of F s binary features. 5) For each binary feature, the induced data split is simulated and the corresponding entropy is computed. The split at current node is then set according to the feature that minimizes the entropy criterion. 6) Go back to Step 3 for recursive application of the procedure on the induced subtrees. Finally, static estimation of the probabilities of expression class c i are computed as the average probability among the M trees of the forest, as shown in Equation [START_REF] Senechal | Automatic facial action detection using histogram variation between emotional states[END_REF].

p sta (c i ) = 1 M . M m=1 p m (c i ) (1)
It is worth noting that, according to [START_REF] Breiman | Random forests[END_REF], the strength of the final classifier is a trade-of between the strength of each individual tree as well as the independence among the trees. Hence the downsampling step 2 allows the construction of individually weaker but more independent trees that, in our experiments, leads to better classification rates that we attribute to a better exploration of the feature space.

At Step 4, we generate

F s = F 1 s + F 2 s + F 3 s features with: 1) F 1
s distance features between two fiducial points provided by the SDM tracker [START_REF] Xiong | Supervised descent method and its applications to face alignment[END_REF]. Those distances are normalized w.r.t. inter-ocular distance to generate features that are invariant from face scaling. 2) F 2 s angle features between three fiducial points. 3) F 3 s HoG features sampled at any position of the face that is localized by its barycentric coordinates w.r.t. three fiducial points.

Each of the F s features is associated with a threshold randomly sampled from a uniform distribution to produce binary features. For HoG features, we associate a threshold to one bin of the descriptor.

C. Transition probability estimation

In this subsection, we review how we use the dynamic information from pairs of images to classify transitions between two facial expressions. To this end, we use the same restricted transition model as in [START_REF] Cohen | Facial expression recognition from video sequences: temporal and static modeling[END_REF], where each facial expression state can only be reached by itself or via the neutral state (Figure 2). In this model, we merge all the transitions that stay in a specific state into a nochange class because from the perspective of classifying transitions it seems hard to determine in which static class the system lies when the two images are very close to each other. Hence, transition recognition is solved as a 13-label classification problem: ne → exp the transition class between neutral and a facial expression class among the six universal expression classes, exp → ne the transition class between an expression class and the neutral state, as well as the nochange class.

Note that this model could be easily adapted to an ergodic expression transition model. However, as it is, it allows us to easily construct an image pair dataset by sampling specific expression sequences from the datasets, to which we associate the corresponding transition class. for instance, a record session with static expression class happiness provides examples of transition classes nochange, ne → ha and ha → ne.

As in Section III-B, transition classification is performed using RF classifiers from image pairs. However, as will be discussed in the following subsections, the transition classifier will be applied several times for each new frame of a video stream. Thus, in order to ensure a very fast evaluation, we use a restricted set of F d = F 1 d + F 2 d features generated from only two feature templates for splitting tree nodes:

1) F 1 d differences of normalized point distances between the two images. 2) F 2 d intensity differences of pixels localized by barycentric coordinates w.r.t. three fiducial points. Benchmarks were conducted that shows that using this different set of feature templates for transition modeling leads to very similar video classification results, although using simple pixel comparisons instead of HoG features leads to a much lower CPU load.

In what follows, we refer to p t-τ →t trans (c i → c j ) as the transition probability from expression class c i to class c j between images sampled at time t-τ and t of a sequence respectively. As it was done for static classification, we compute these probabilities by averaging the output probabilities among all the trees of the forest.

D. Dynamic estimation of class probabilities

We denote p t-τ dyn (c i ) the dynamic estimation of facial expression class c i probability at time t given only the observations at times t-τ and t. This probability is computed as the most probable path between the two frames using past predictions p t-τ f us at time t -τ as well as the output of the transition classifier p t-τ →t trans applied for images at time t -τ and t. (Equation ( 2)).

p t-τ dyn (c i ) = max cj {p t-τ →t trans (c j → c i ).p t-τ f us (c j )} (2)
In practice, as we use the simplified transition model from Figure 2, for each expression class we only need to compare the probabilities of a transition of type ne → exp and nochange. For the neutral class, we have to examine the nochange case, as well as any transition coming from an expression class.

E. Fusion of static and dynamic probabilities from multiple time-gaps

Static (Section III-B) and dynamic estimations (Section III-D) at multiple time gaps τ 0 , τ 1 , ..., τ k-1 are fused to give rise to the final prediction of class probability p t f us (c i ) of expression class c i at time t. In what follows, we refer to the number of time gaps k as the model order. A 0 order model is thus merely a static classifier that is applied separately on each video frame.

The prediction of class probability p t f us (c i ) at time t can thus be computed from static and dynamic estimations in two different ways:

1) By averaging the probabilities p t-τ dyn (c i ) obtained for every time gap τ along with static estimation of class probability p t sta (c i ) (Equation ( 3))

p t f us (c i ) = p t sta (c i ).(1 + λ τ p t-τ dyn (c i )) ( 3
)
where λ is a cross-validated constant that regulates the influence of dynamic information. The predictions p t f us are then renormalized to unit L 1 norm. 2) By having static estimation and each dynamic estimation "vote" for the maximum probability class.

Probabilities p t f us are then computed by averaging these votes. A comparison between the average and the vote approaches can be found in Section IV-A.

IV. EVALUATION

In order to validate our approach, we report accuracy on two broadly used facial expression recognition datasets for models of order 0 (static), 1 (with time gap T = {6}, i.e. we only look at one time gap six frames before the current one), 2 (T = {6, 12}), 3 (T = {6, 12, 24}) and 4 (T = {6, 12, 24, 48}), showing that dynamic estimations provided by our method allows to substantially enhance the recognition accuracy. Also note that the same benchmarks were conducted with different time gap values (e.g. T = {5, 10, 20, ...}, leading to similar conclusions.

The Extended Cohn-Kanade (CK+) database [START_REF] Lucey | The extended cohn-kanade dataset (ck+): A complete dataset for action unit and emotion-specified expression[END_REF] includes 118 subjects for each of which from 1 to 11 expression recording sessions are associated. Some of these sessions do not belong to a specific expression class or are annotated with nonbasic label contempt and will thus be discarded for further processing. Videos presents acted expressions only and contains very few head pose variations. Table I shows the performance comparison on the CK+ database. For comparison purposes, results are reported for static/dynamic classification on the last frame of the videos.

The BU-4DFE database [START_REF] Yin | A 3d facial expression database for facial behavior research[END_REF] contains 101 subject, each one displaying the 6 facial expressions. As in CK+, these records include few facial pose variations and the expressions are still acted, but the variability for facial expression is larger. Furthermore, video sequences in BU-4DFE do not necessarily end on a peak frame of an expression. Thus, we aknowledge correct classification for a video if the greatest sum of predicted probabilities greatest among the six expression correspond to the ground truth label. Table II displays the classification accuracies for the different expression classes obtained for BU-4DFE database.

Both static and transition classifiers are evaluated using the Out-Of-Bag (OOB) error estimate [START_REF] Breiman | Random forests[END_REF]. More specifically, during training bootstraps for static and transition classifiers are generated at the subject level so that, for the test, each tree is used only for subjects that do not belong to the corresponding bootstrap. OOB error, albeit being an unbiased estimate of the true generalization error, is easier to compute than traditional Leave-One-Subject-Out (LOSO) or k-fold cross-evaluation procedures. Also, it has been shown to be generally more pessimistic than traditional error estimates [START_REF] Tom | Estimating generalization error on two-class datasets using out-of-bag estimates In Machine Learning[END_REF], further empathizing the quality of the proposed approach.

Last but not least, we also conducted a CPU load benchmark so as to evaluate the real-time capacities for our system.

A. Video sequence classification

Figure 3 shows the evolution of classification accuracies versus the model order respectively for CK+ and BU-4DFE databases. Table I shows the performances obtained using the fourth order model, as well as a comparison with static classification for CK+ database. analyse even for a human eye. Furthermore, the fear class is particularly difficult to act, and the facial expression sometimes look very similar to surprise or happy.

The addition of transition information allows to substantially increase the performance on those expression classes, as well as to help discriminate between happiness, disgust and surprise. Overall recognition percentages rises from 92.7% to 96.1% for CK+ database, and from 68.3% to 72.2% for BU-4DFE database for the average fusion method. Overall accuracy rises up to 75.8% on BU-4DFE database when using the voting fusion scheme. Interestingly enough, the voting approach seems to perform slightly worse on CK+, which we believe is due to the shortness of the sequences in this database.

However, taking into account time steps beyond τ = 24 does not typically add much to the classification results. This is specially true on the CK+ database where the recording sessions are rather short. Moreover, in less constrained benchmarks, it could very well decrease the accuracy as larger variations in face pose are to be observed for such large time steps, as well as transitions between different facial expression classes that may not be expected in the transition model shown in Figure 2.

Accuracy seems to be on par with state-of-the-art methods, as shown in Tables III andIV, although comparisons are to be put into perspective as the selected subsets and evaluation protocols are not exactly the same between the different approaches. Our static classifier gives similar results as LBP features with SVM classification [START_REF] Shan | Robust facial expression recognition using local binary patterns[END_REF], and classification accuracy for the fourth order model is also quite similar to LBP-TOP with SVM [START_REF] Zhao | Dynamic texture recognition using local binary patterns with an application to facial expressions[END_REF] as well as SVM from shape information [START_REF] Rudovic | Multi-output laplacian dynamic ordinal regression for facial expression recognition and intensity estimation[END_REF]. As for BU-4DFE dataset, Our approach clearly outperforms other dynamic approaches that does not apply manual pre-segmentation of the sequences [START_REF] Liefei | Automatic Facial Expression Recognition using Bags of Motion Words[END_REF], [START_REF] Sun | Facial expression recognition based on 3D dynamic range model sequences[END_REF]. Performances are also nearly equivalent to those reported by Rudovic et al. [START_REF] Rudovic | Multi-output laplacian dynamic ordinal regression for facial expression recognition and intensity estimation[END_REF] and Jeni at al [START_REF] László | High quality facial expression recognition in video streams using shape related information only[END_REF], although these methods imply manual truncation of the videos and/or normalization w.r.t. the first frame of the sequence [START_REF] László | High quality facial expression recognition in video streams using shape related information only[END_REF], from which the provided accuracy values seems to be highly dependant.

B. Real-time capacities

Figure 4 shows the evolution of classification accuracy for the static and transition classifiers versus the number of trees, for both CK+ and BU-4DFE datasets. It can be seen that overall accuracy reaches 95% of the maximum classification rates with only 50 trees. Using such setting, the proposed system runs at more 60 than fps. This evaluation includes facial alignment, feature extraction and expression classification steps. Facial alignment is the bottleneck of the system as the feature extraction and classification pipeline can be performed at more than 500 fps, although there is still room for code optimization and efficient parallelization. This benchmark was conducted on a Intel Core I7-4770 CPU with 32 Go RAM using a multithreaded C++/OpenCV environment.

V. CONCLUSION AND FUTURE WORK

In this paper we have introduced a real-time, automatic facial expression recognition system that combines static and transition information from different time gaps. We propose a framework to train a transition classifier upon image pairs that can be extracted from popular datasets. The classifiers employ basic geometric and appearance features that provide robustness against variation in pose or in lighting conditions. The algorithm works in real time on a standard computer even for higher order models, without extensive code optimization.

Future work will involve applying our framework to realcase scenarios such as spontaneous facial expression datasets. For that matter we might have to adapt our transition model to efficiently take into account transitions from one expression state to another one, which may happen in such unconstrained scenarios. Furthermore, it will also be necessary to incorporate pose handling into the facial expression learning framework.

Fig. 2 .

 2 Fig. 2. Restricted transition model

Fig. 4 .

 4 Fig. 4. Static and transition classification accuracy vs number of trees

  Table II displays the classification accuracies for the different expression classes obtained for the BU-4DFE database.

	Fig. 3. Average accuracy vs model order for BU-4DFE and CK+ datasets
	Expression Order 0 (%)	Order 4 (avg)(%) Order 4 (vote)(%)
	Happiness	97.1	98.6	98.6
	Anger	86.7	95.6	93.3
	Sadness	92.9	92.9	92.9
	Fear	88.0	92.0	88.0
	Disgust	94.9	100.0	98.3
	Surprise	96.4	97.6	97.6
	Average	92.7	96.1	94.8

TABLE III CLASSIFICATION

 III ACCURACY COMPARISON WITH STATE-OF-THE-ARTMETHODS ON CK+ DATASET Classically, anger and fear are the facial expression classes for which the static classification accuracies are the lowest on both databases. Respective accuracies for these classes are 86.7% and 88.0% for CK+, and 70.0% and 36.0% for BU-4DFE. This is mainly due to the fact that the facial deformation can be quite subtle, and sometimes hard to

	Work	#Subjects Preprocessing	Acc(%)
	BoMW [21]	101	None	63,9
	Dynamic 2D [22]	101	None	67,0
	LSH-CORF [4]	30	segmentation	77,1
	Shape [3]	101	segmentation + neutral	70,5
			normalization
	Shape [3]	101	segmentation + personal	78,2
			mean normalization
	Ours, order 4 (avg)	101	None	72,2
	Ours, order 4 (vote)	101	None	75,8

TABLE IV CLASSIFICATION

 IV ACCURACY COMPARISON WITH STATE-OF-THE-ART METHODS ON BU-4DFE DATASET


Arnaud Dapogny
email: arnaud.dapogny@isir.upmc.fr

Kevin Bailly
email: kevin.bailly@isir.upmc.fr

Séverine Dubuisson
email: severine.dubuisson@isir.upmc.fr

Pairwise conditional random forests for facial expression recognition

come

Introduction

In the last decades, automatic facial expression recognition (FER) has attracted an increasing attention, as it is a fundamental step of many applications such as humancomputer interaction, or assistive healthcare technologies. A good survey covering FER can be found in [START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions[END_REF]. There exists many impediments to successful deciphering of facial expressions, among which the large variability in morphological and contextual factors as well as the subtlety of lowintensity expressions. Because using dynamics of the expression helps disentangle those factors [START_REF] Cohn | Foundations of human computing: facial expression and emotion[END_REF], most recent approaches aim at exploiting the temporal variations in videos rather than trying to perform recognition on still images.

Nevertheless, as a matter of fact, the semantics of acted Figure 1. Flowchart of our PCRF FER method. When evaluating a video frame indexed by n, dedicated pairwise trees are drawn conditionally to expression probability distributions from previous frames n -m1, n -m2, .... The subsequent predictions are averaged over time to output an expression probability distribution for the current frame. This prediction can be used as a tree sampling distribution for subsequent frame classification.

facial events is composed of successive onset, apex and offset phases that may occur with various offsets and at different paces. Spontaneous behaviors can however be much more difficult to analyse in terms of such explicit sequence. Hence, there is no consensus on either how to effectively extract suitable representations from those high dimensional video patterns, or on how to combine those representations in a flexible way to generalize to unseen data and possibly unseen temporal variations. Common approaches employ spatio-temporal descriptors defined on fixed-size windows, optionally at multiple resolutions. Examples of such features include the so-called LBP-TOP [START_REF] Zhao | Dynamic texture recognition using local binary patterns with an application to facial expressions[END_REF] and HoG3D [START_REF] Klaser | A spatio-temporal descriptor based on 3D-gradients[END_REF] descriptors, which are spatio-temporal extensions of LBP and HoG features respectively. Authors in [START_REF] Shojaeilangari | Multiscale analysis of local phase and local orientation for dynamic facial expression recognition[END_REF] use histograms of local phase and orientations. However, such representations may lack the capacity to generalize to facial events that differ from training data on the temporal axis.

Other approaches aim at establishing relationships between high-level features and a sequence of latent states. Wang et al. [START_REF] Wang | Capturing complex spatiotemporal relations among facial muscles for facial expression recognition[END_REF] integrate temporal interval algebra into a Bayesian Network to capture complex relationships among facial muscles. Walecki et al. [START_REF] Walecki | Variable-state latent conditional random fields for facial expression recognition and action unit detection[END_REF] introduce a variablestate latent Conditional Random Field that can automatically select the optimal latent states for individual expression videos. Such approaches generally require explicit dimensionality reduction techniques such as PCA or K-means clustering for training. In addition, training at the sequence level considerably reduces the quantity of available training and testing data as compared to frame-based approaches.

In early work [START_REF] Dapogny | Dynamic facial expression recognition by static and multi-time gap transition joint classification[END_REF] we obtained promising results for acted video FER by learning a restricted transition model that we fused with a static one. However, this model lacks the capacity to generalize to more complex spontaneous FER scenarios where one expression may quickly follow another one. Furthermore, because the transition and static classifiers are applied as two separate tasks, it can not integrate low-level correlations between static and spatiotemporal patterns. In this paper, we introduce the Pairwise Conditional Random Forest (PCRF) algorithm, which is a new formulation for training trees using low-level heterogeneous static (spatial) and dynamic (spatio-temporal derivative) features within the RF framework. Conditional Random Forests were used by Dantone et al. [START_REF] Dantone | Real-time facial feature detection using conditional regression forests[END_REF] as well as Sun et al. [START_REF] Sun | Conditional regression forests for human pose estimation[END_REF] in the field of facial alignment and human pose estimation, respectively. They generated collections of trees for specific, quantized values of a global variable (such as head pose [START_REF] Dantone | Real-time facial feature detection using conditional regression forests[END_REF] and body torso orientation [START_REF] Sun | Conditional regression forests for human pose estimation[END_REF]) and used prediction on this global variable to draw dedicated trees, resulting in more accurate predictions. In our case, we propose to condition pairwise trees upon specific expression labels to reduce the variability of ongoing expression transitions from the first frame of the pair to the other one (Figure 1). When evaluating a video, each previous frame of the sequence is associated with the current frame to give rise to a pair. Pairwise trees are thus drawn from the dedicated PCRFs w.r.t. a prediction for the previous frame. Finally, predictions outputted for each pair are averaged over time to produce a robust prediction for the current frame. The contributions of this work are thus three-fold:

• A method for training pairwise random trees upon high-dimensional heterogeneous static and spatiotemporal derivative feature templates, with a conditional formulation that reduces the variability.

• An algorithm that is a natural extension of the static RF averaging, that consists in averaging over time pairwise predictions to flexibly handle temporal variations.

• A framework that performs FER from video that can work on low-power engines thanks to an efficient implementation using integral feature channels.

The rest of the paper is organized as follows: in Section 2 we describe our adaptation of the RF framework to learn expression patterns on still images from high-dimensional, heterogeneous features. In Section 3 we present the PCRF framework to learn temporal patterns of facial expressions. In Section 4 we show how our PCRF algorithm improves the accuracy on several FER datasets as compared to a static approach. We also show how our method outperforms the state-of-the-art approaches and report its ability to run in real-time. Finally, in Section 5 we give concluding remarks on our PCRF for FER and discuss perspectives.

Random Forests for FER

Facial expression prediction

Random Forests (RFs) [START_REF] Breiman | Random forests[END_REF] is a popular learning framework introduced in the seminal work of Breiman [START_REF] Breiman | Random forests[END_REF]. They have been used to a significant extent in computer vision and for FER tasks in particular due to their ability to nicely handle high-dimensional data such as images or videos as well as being naturally suited for multiclass classification tasks. They combine random subspace methods for feature sampling and bagging in order to provide performances similar to the most popular machine learning methods such as SVM or Deep Neural Networks.

RFs are classically built from the combination of T decision trees grown from bootstraps sampled from the training dataset. In our implementation, we downsample the majority classes within the bootstraps in order to enforce class balance. As compared to other methods for balancing RF classifiers (i.e. class weighting and upsampling of the minority classes), downsampling leads to similar results while substantially reducing the computational cost, as training is performed on smaller data subsets.

Individual trees are grown using a greedy procedure that involves, for each node, the measure of an impurity criterion H ϕ,θ (which is traditionally either defined as Shannon entropy or Gini impurity measurement) relatively to a partition of the images x with label l ∈ L, that is induced by candidate binary split functions {ϕ, θ} ∈ Φ. More specifically, we use multiple parametric feature templates to generate multiple heterogeneous split functions, that are associated with a number of thresholds θ. In what follows, by abuse of notations we will refer to ϕ (i) as the i th feature template and k (i) as the number of candidates generated from this template. The "Best" binary feature among all features from the different templates (i.e. the one that minimizes the impurity criterion H ϕ,θ ) is set to produce a data split for the current node. Then, those steps are recursively applied for the left and right subtrees with accordingly rooted data until the label distribution at each node becomes homogeneous, where a leaf node can be set. This procedure for growing trees is summarized in Algorithm 1.

Algorithm 1 Tree Growing algorithm treeGrowing input: images x with labels l, root node n, number of candidate features {k (i) } i=1,2,3 for templates {ϕ (i) } i=1,2, [START_REF] Bylander | Estimating generalization error on two-class datasets using out-of-bag estimates[END_REF] if image labels are homogeneous with value l 0 then set node as terminal, with probabilities p t to 1 for l 0 , 0 elsewhere else generate an empty set of split candidates Φ for all feature templates i do, generate a set Φ (i) of k (i) candidates {ϕ (i) , θ} Φ ← Φ ∪ Φ (i) end for for {ϕ, θ} ∈ Φ do compute the impurity criterion H ϕ,θ (x) end for split data w.r.t. arg min {ϕ,θ} {H ϕ,θ (x)} in left and right subsets x l and x r create left n l and right n r children of node n call treeGrowing(x l ,n l ,{k

(i) } i=1,2,3 ) call treeGrowing(x r ,n r ,{k (i) } i=1,2,3 ) end if
During evaluation, an image x is successively rooted left or right of a specific tree t according to the outputs of the binary tests, until it reaches a leaf node. The tree thus returns a probability p t (l|x) which is set to either 1 for the represented class, or to 0. Prediction probabilities are then averaged among the T trees of the forest (Equation ( 1)).

p(l|x) = 1 T T ∑ t=1 p t (l|x) (1)
Note that the robustness of the RF prediction framework comes from (a) the strength of individual trees and (b) the decorrelation between those trees. By growing trees from different bootstraps of available data and with the random subspace algorithm (e.g. examining only a subset of features for splitting each node) we generate individually weaker, but less correlated trees that provide better combination predictions that standard CART or C4.5 procedures.

Heterogeneous feature templates

Feature templates ϕ (i) include both geometric (i.e. computed from previously aligned facial feature points) and appearance features. Each of these templates have different in-put parameters that are randomly generated during training by uniform sampling over their respective variation range. Also, during training, features are generated along with a set of candidate thresholds θ to produce binary split candidates. In particular, for each feature template ϕ (i) , the upper and lower bounds are estimated from training data beforehand and candidate thresholds are drawn from a uniform distribution in the range of these values.

We use two different geometric feature templates which are generated from the set of facial feature points f (x) aligned on image x with the SDM tracker [START_REF] Xiong | Supervised descent method and its applications to face alignment[END_REF]. The first geometric feature template ϕ

(1)
a,b is the euclidian distance between feature points f a and f b , normalized w.r.t. intraocular distance iod(f (x)) for scale invariance (Equation 2).

ϕ (1) a,b (x) = ||f a -f b || 2 iod(f ) (2)
Because the feature point orientation is discarded in feature ϕ (1) we use the angles between feature points f a , f b and f c as our second geometric feature ϕ

(2)
a,b,c,λ . In order to ensure continuity for angles around 0, red we use the cosine and sine instead of the raw angle value. Thus, ϕ (2) outputs either the cosine or sine of angle f a f b f c , depending on the value of the boolean parameter λ (Equation ( 3)):

ϕ (2) a,b,c,λ (x) = λ cos( f a f b f c ) + (1 -λ) sin( f a f b f c ) (3)
We use Histogram of Oriented Gradients (HoG) as our appearance features for their descriptive power and robustness to global illumination changes. In order to ensure fast feature extraction, we use integral feature channels as introduced in [START_REF] Dollár | Integral channel features[END_REF]. First, we rotate the image x in order to align the inter-ocular axis on the horizontal axis. We then compute horizontal and vertical gradients on the rotated image and use these to generate 9 feature channels, the first one containing the gradient magnitude. The 8 remaining channels correspond to a 8-bin quantization of the gradient orientation. Finally, integral images are computed from these feature maps to output 9 channels. Thus, we define the appearance feature template ϕ

(3) τ,ch,s,α,β,γ as an histogram computed over channel ch within a window of size s normalized w.r.t. the intra-ocular distance. Such histogram is evaluated at a point defined by its barycentric coordinates α, β and γ w.r.t. vertices of a triangle τ defined over feature points f (x). Also, storing the gradient magnitude within the first channel allows to normalize the histograms as in standard HoG implementation. Thus, HoG features can be computed very efficiently by using only 4 access to the integral channels (plus normalization).

Learning temporal patterns with PCRF

Learning PCRF with heterogeneous derivative feature templates

In this section we explain how we adapt the aforementioned RF framework to take into account the dynamics of the expression. We now consider pairs of images (x ′ ,x) to train trees t that aim at outputting probabilities p t (l|x ′ , x, l ′ ) of observing label l(x) = l given image x ′ and subject to l(x ′ ) = l ′ , as illustrated in Figure 2.

More specifically, for each tree t among the T trees of a RF dedicated to transitions starting from expression label l ′ , we randomly draw a fraction of subjects S ⊂ S. Then, for each subject s ∈ S we randomly draw images x ′ s that specifically have label l ′ . We also draw images x s of every label l and create as many pairs (x ′ s , x s ) with label l. Note that the two images of a pair do not need to belong to the same video. Instead, we create pairs from images sampled across different sequences for each subject to cover all sorts of ongoing transitions. We then balance the pairwise bootstrap by downsampling the majority class w.r. Candidates for splitting the nodes are generated from an extended set of 6 feature templates {ϕ (i) } i=1,..., [START_REF] Dapogny | Dynamic facial expression recognition by static and multi-time gap transition joint classification[END_REF] , three of which being the static features described in Section 2, that are applied to the second image x of the pair (x ′ , x), for which we want to predict facial expressions. The three remaining feature templates are dynamic features defined as the derivatives of static templates ϕ (1) , ϕ (2) , ϕ (3) with the exact same parameters. Namely, we have:

                   ϕ (1) a,b (x ′ , x) = ϕ (1) a,b (x) ϕ (2) a,b,c,λ (x ′ , x) = ϕ (2) a,b,c,λ (x) ϕ (3) τ,ch,s,α,β,γ (x ′ , x) = ϕ (3) τ,ch,s,α,β,γ (x) ϕ (4) a,b (x ′ , x) = ϕ (1) a,b (x) -ϕ (1) a,b (x ′ ) ϕ (5) a,b,c,λ (x ′ , x) = ϕ (2) a,b,c,λ (x) -ϕ (2) a,b,c,λ (x ′ ) ϕ (6) τ,ch,s,α,β,γ (x ′ , x) = ϕ (3) τ,ch,s,α,β,γ (x) -ϕ (3) τ,ch,s,α,β,γ (x ′ ) (4
) As in Section 2, thresholds for the derivative features ϕ (4) , ϕ (5) , ϕ (6) are randomly drawn from uniform distributions with new dynamic template-specific ranges estimated from the pairwise dataset beforehand. Also note that, as compared to a static RF, a PCRF model is extended with new derivative features that are estimated from a pair of images. When applied on a video, predictions for several pairs are averaged over time in order to produce robust estimates of the probability predictions.

Model averaging over time

We denote by p n (l) the prediction probability of label l for a video frame x n . For a purely static RF classifier this probability is given by Equation ( 5):

p n (l) = 1 T T ∑ t=1 p t (l|x n ) (5)
In order to use spatio-temporal information, we apply pairwise RF models to pairs of images (x m , x n ) with {x m } m=n-1,...,n-N the previous frames in the video. Those pairwise predictions are averaged over time to provide a new probability estimate p n that takes into account past observations up to frame n. Thus, if we do not have prior information for those frames the probability p n is:

p n (l) = 1 N T n-N ∑ m=n-1 T ∑ t=1 p t (l|x m , x n ) (6)
In what follows, Equation ( 6) will be refered to as the full model. Trees from the full model are likely to be stronger that those of the static one since they are grown upon an extended set of features. Likewise, the correlation between the individual trees is also lower thanks to the new features and the fact that they will be evaluated on multiple, distinct pairs when averaging over time. However, spatio-temporal information can theoretically not add much to the accuracy if the variability of the pairwise data points is too large.

In order to decrease this variability, we assume that there exists a probability distribution p m 0 (l ′ ) to observe the discrete expression label l ′ at frame m. Note that probabilities p 0 can be set to purely static estimates (which is necessarily the case for the first video frames) or dynamic predictions estimated from previous frames. A comparison between those approaches can be found in Section 4.3. In such a case, for frame m, pairwise trees are drawn conditionally to distributions p m 0 , as shown in Figure 2. More specifically, for each expression label l ′ we randomly select N (l ′ ) trees over a PCRF model dedicated to transitions that start from expression label l ′ , trained with the procedure described in Section 3.1. Equation ( 6) thus becomes:

p n (l) = 1 N T n-N ∑ m=n-1 ∑ l ′ ∈L N (l ′ ) ∑ t=1 p t (l|x m , x n , l ′ ) (7)
Where N (l ′ ) ≈ T.p m 0 (l ′ ) and T = ∑ l ′ ∈L N (l ′ ) being the number of trees dedicated to the classification of each transition, which can be set in accordance with CPU availability. In our experiments, we will refer to Equation [START_REF] Dhall | Acted facial expressions in the wild database[END_REF] as the conditional model. This formulation reduce the variability of the derivative features for each specialized pairwise RF. Section 4 shows that using PCRF models leads to significant improvements over both static and full models.

Experiments

In this section, we report comparisons between different classification models on two well-known FER databases, the Extended Cohn-Kanade and BU-4DFE databases. Furthermore, in order to evaluate the capabilities of the learned models to generalize on new, potentially more complicated FER scenarios, we report classification results for crossdatabase evaluation on two spontaneous databases, namely the FG-NET FEED and BP4D databases. We highlight that our conditional formulation of dynamic integration substantially increases the recognition accuracy on such tasks. Finally, we show the real-time capacitbility of our system.

Databases

The CK+ or Extended Cohn-Kanade database [START_REF] Lucey | The extended cohn-kanade dataset (CK+): A complete dataset for action unit and emotion-specified expression[END_REF] contains 123 subjects, each one associated with various numbers of expression records. Those records display a very gradual evolution from a neutral class towards one of the 6 universal facial expressions (anger, happiness, sadness, fear, digust and surprise) plus the nonbasic expression contempt. Expressions are acted with no head pose variation and their duration is about 20 frames. From this dataset we use 309 sequences, each one corresponding to one of the six basic expressions, and use the three first and last frames from these sequences for training. We did not include sequences labelled as contempt because CK+ contains too few subjects performing contempt and other expressions to train the pairwise classifiers.

The BU-4DFE database [START_REF] Yin | A highresolution 3d dynamic facial expression database[END_REF] contains 101 subjects, each one displaying 6 acted facial expressions with moderate head pose variations. Expressions are still prototypical but they are generally exhibited with much lower intensity and greater variability than in CK+, hence the lower baseline accuracy. Sequences duration is about 100 frames. As the database does not contain frame-wise expression annotations, we manually select neutral and apex of expression frames for training.

The BP4D database [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF] contains 41 subjects. Each subject was asked to perform 8 tasks, each one supposed to give rise to 8 spontaneous facial expressions (anger, happiness, sadness, fear, digust, surprise, embarrassment or pain). In [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF] the authors extracted subsequences of about 20 seconds for manual FACS annotations, arguing that these subsets contains the most expressive behaviors.

The FG-NET FEED database [START_REF] Wallhoff | Database with facial expressions and emotions from technical university of munich (feedtum)[END_REF] contains 19 subjects, each one recorded three times while performing 7 spontaneous expressions (the six universal expressions, plus neutral). The data contain low-intensity emotions, short expression displays, as well as moderate head pose variations.

Experimental Setup

7-class RF (static) and PCRF (full and conditional) classifiers are trained on the CK+ and BU-4DFE datasets using the set of hyperparameters described in Table 1. These parameters were obtained by cross-validation. Note however that extensive testing showed that the values of these hyperparameters had a very subtle influence on the performances. This is due to the complexity of the RF framework, in which individually weak trees (e.g. that are grown by only examining a few features per node) are generally less correlated, still outputting decent predictions when combined altogether. Nevertheless, we report those settings for reproducibility concerns. Also, for a fair comparison between static and pairwise models, we use the same total number of feature evaluations for generating the split nodes. Moreover, for all the models the maximum accuracy was reached for T ≈ 100 trees. However, we generated large numbers of trees so that the variance in prediction accuracy for the following benchmarks becomes very low over all the runs. Table 1. Hyperparameters settings Hyperparameters value(static) value(dynamic) Nb. of ϕ (1) features 40 20 Nb. of ϕ (2) features 40 20 Nb. of ϕ (3) features 160 80 Nb. of ϕ (4) features -20 Nb. of ϕ (5) features -20 Nb. of ϕ (6) features -80 Data ratio per tree 2/3 2/3 Nb. of thresholds 25 25 total nb. of features 6000 6000 Nb. of trees 500 500

During the evaluation, the prediction is initialized at the first frame using the static classifier. Then, for the full and conditional models, probabilities are estimated for each frame using transitions from previous frames only, bringing us closer to a real-time scenario. However, although it uses transitional features, our system is essentially a framebased classifier that outputs an expression probability for each separate video frame. This is different from, for example, a HMM, that aims at predicting a probability related to all the video frames. Thus, in order to evaluate our classifier on video FER tasks, we acknowledge correct classification if the maximum probability outputted for all frames corresponds to the ground truth label. This evaluates the capabil-ity of our system to retrieve the most important expression mode in a video, as well as the match between the retrieved mode and the ground truth label.

For the tests on CK+ and BU-4DFE databases, both static and transition classifiers are evaluated using the Out-Of-Bag (OOB) error estimate [START_REF] Breiman | Random forests[END_REF]. More specifically, bootstraps for individual trees of both static and pairwise classifiers are generated at the subject level. Thus, during evaluation, each tree is applied only on subjects that were not used for its training. The OOB error estimate is an unbiased estimate of the true generalization error [START_REF] Breiman | Random forests[END_REF] which is faster to compute than Leave-One-Subject-Out or k-fold cross-evaluation estimates. Also, it has been shown to be generally more pessimistic than other error estimates [START_REF] Bylander | Estimating generalization error on two-class datasets using out-of-bag estimates[END_REF], further empathizing the quality of the proposed results.

Evaluation of PCRF

In order to validate our approach, we compared our conditional model to a purely static model and a full model, for a variety of dynamic integration parameters (the length of the temporal window N and the step between those frames

Step) on the BU-4DFE database. We also evaluated the interest of using a dynamic probability prediction for previous frames (i.e. the output of the pairwise classifier for those frames) versus a static one. Average results are provided in Figure 3. For CK+ database, sequences are generally too short to show significant differences when varying the temporal window size or the step size. Thus we only report accuracy for full and conditional models with a window size of 30 and a step of 1. Per-expression accuracies and F1-Scores for both Cohn-Kanade and BU-4DFE databases are shown in Figure 4. We observe that the conditional model significantly outperforms the static model on both CK+ and BU-4DFE databases. This is due to the extra dynamic features that provide both robustness and decorrelation of the individual decision trees, further enhancing their prediction accuracy. Figure 4 shows that the conditional model also outperforms the full model on both databases, which is probably due to the fact that using only a restricted set of ongoing expression transitions for training allows to better capture the variabil-Figure 4. Per-class recognition accuracy rates and F1-scores on CK+ and BU-4DFE databases ity of the spatio-temporal features for the dedicated pairwise forests. This is particularly true on the CK+ database, where the number of pairwise data points is not enough for the full model to capture the variability of all possible ongoing transitions, hence justifying the lower accuracy. This seems particularly relevant for expressions such as fear or sadness which are the less represented ones in the dataset. Table 3 also shows that it is better to look backward for more frames in the sequence (N = 60) with less correlation between the frames (Step = 3 or 6). Again, such setting allows to take more decorrelated paths in the individual trees, giving a better recombination after averaging over time.

A compilation of comparisons to other state-of-the-art approaches for FER from video sequences can be found in Table 2. On the CK+ dataset, we compare our algorithms with recent work results for FER from video on the same subset of sequences (i.e. not including contempt). However the comparisons are to be put into perspective as the evaluation protocols differ between the methods. PCRF provides results similar to those reported in [START_REF] Walecki | Variable-state latent conditional random fields for facial expression recognition and action unit detection[END_REF] as well as in [START_REF] Shojaeilangari | Multiscale analysis of local phase and local orientation for dynamic facial expression recognition[END_REF][START_REF] Khan | Human vision inspired framework for facial expressions recognition[END_REF][START_REF] Dapogny | Dynamic facial expression recognition by static and multi-time gap transition joint classification[END_REF], although the latter approaches explicitly consider the last (apex) frame. We also consistently outperform HMM and interval-based DBN presented in [START_REF] Wang | Capturing complex spatiotemporal relations among facial muscles for facial expression recognition[END_REF], although the evaluations protocols are not the same. Furthermore, to the best of our knowledge, our approach gives the best results on the BU-4DFE database for automatic FER from videos using 2D information only. Our approach provides better results than the dynamic 2D approach [START_REF] Sun | Facial expression recognition based on 3D dynamic range model sequences[END_REF], as well as the frame-based approach presented in [START_REF] Xu | Automatic facial expression recognition using bags of motion words[END_REF]. Recently, Meguid et al. [START_REF] Dubuisson | Fully automated recognition of spontaneous facial expressions in videos using random forest classifiers[END_REF] obtained impressive results using an original RF/SVM system, from training upon the BU-3DFE database which is a purely static database. They employ a post-classification temporal integration scheme, which we believe may be weaker than using dynamic information at the feature level. Finally, the restricted transition model introduced in our early work [START_REF] Dapogny | Dynamic facial expression recognition by static and multi-time gap transition joint classification[END_REF] face difficulties on spontaneous FER tasks where one expression can quickly succeed to another. Conversely, we show that the method proposed in this paper translates well to such spontaneous scenarios. For that matter, Table 2 also reports results for cross-database evaluation (with training on the BU-4DFE database) on the FEED database. In order to provide a fair comparison between our approach and the one presented in [START_REF] Dubuisson | Fully automated recognition of spontaneous facial expressions in videos using random forest classifiers[END_REF], we used the same labelling protocol as them. One can see that the performances of their system are better than those of our static RF model, which can be attributed to the fact that they use a more complex classification and posterior temporal integration flowchart. Nevertheless, our PCRF model provides a substantially higher accuracy, which, again, is likely to be due to the use of spatio-temporal features as well as an efficient conditional integration scheme.

We also performed cross-database evaluation on the BP4D database. Again, for a fair comparison, we used the same protocol as in [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF], with training on the BU-4DFE database and using only a subset of the tasks (i.e. tasks 1 and 8 corresponding to expression labels happy and disgust respectively). However, we do not retrain a classifier with a subset of 3 expressions as it is done in [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF], but instead use our 7-class static and PCRF models with a forced choice between happiness (probability of class happiness) and disgust (probability sum of classes anger and disgust). Such setting could theoretically increase the confusion in our conditional model, resulting in a lower accuracy. However, as can be seen in Table 2, using dynamic information within the PCRF framework allows to substantially increase the recognition rate as compared to a static RF framework. We also overcome the results reported in [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF] by a significant margin, further showing the capability of our approach to deal with complex spontaneous FER tasks. Also note that in [START_REF] Zhang | BP4D-spontaneous: a high-resolution spontaneous 3D dynamic facial expression database[END_REF], the authors used the so-called Nebulae 3D polynomial volume features which are by far more computationally expensive than our geometric and integral HoG 2D features. All in all, we believe our results show that the PCRF approach provides significant improvements over a traditional static classification pipeline that translates very well to more complicated spontaneous FER scenarios, where a single video may contain samples of several expressions.

Complexity of PCRF

An advantage of using conditional models is that with equivalent parallelization they are faster to train than an hypothetical full model learnt on the whole dataset. According to [START_REF] Louppe | Understanding Random Forests: From Theory to Practice[END_REF] the average complexity of training a RF classifier with M trees is O(M KN log 2 N ), with K being the number of features to examine for each node and N the size of (2/3 of) the dataset. Thus if the dataset is equally divided into P bins of size Ñ upon which conditional forests are trained (and such that N = P Ñ ), the average complexity of learning a conditional model now becomes O(M KN log 2 Ñ ).

Same considerations can be made concerning the evaluation, as trees from the full model are bound to be deeper than those from the conditional models. Table 3 shows an example of profiling a PCRF on one video frame with an averaging over 60 frames and a step of 3 frames. Thus the total number of evaluated trees is 20M with M being the number of trees dedicated to classifying each frame. This benchmark was conducted on a Intel Core I7-4770 CPU with 32 Go RAM within a C++/OpenCV environment, without any code parallelization. As such, the algorithm already runs in real-time. Furthermore, evaluations of pairwise classification or tree subsets can easily be parallelized to fit real-time processing requirements on low-power engines such as mobile phones. In addition, the facial alignment step can be performed at more than 300 fps on a smartphone with similar performances using the algorithms from [START_REF] Ren | Face alignment at 3000 fps via regressing local binary features[END_REF].

Conclusion and perspectives

In this paper, we introduced the PCRF framework, which integrates high-dimensional, low-level spatio-temporal information through averaging over time pairwise conditional trees. These trees are drawn by considering previous predictions. We showed that our model can be trained and evaluated efficiently, and leads to a significant increase of performances compared to a static RF. In addition, our method works on real-time without specific optimization schemes, and could be run on low-power architectures such as mobile phones by using an appropriate paralellization. Future works will consist in employing conditional models for pose and occlusion handling to adapt the proposed PCRF framework for "in the wild" FER datasets such as the one in [START_REF] Dhall | Acted facial expressions in the wild database[END_REF]. Furthermore, we would like to investigate applications of PCRF for other video classification/regression problems such as Facial Action Unit intensity prediction or body and hand gesture recognition.

Figure 2 .

 2 Figure 2. Expression recognition from pairs of images using PCRF. Expression probability predictions of previous images are used to sample trees from dedicated pairwise tree collections (one per expression class) that are trained using subsets of the (pairwise) training dataset, with only examples of ongoing transitions from a specific expression towards all classes. The resulting forest thus outputs an expression probability for a specific pair of images.

Figure 3 .

 3 Figure 3. Average accuracy rates obtained for various temporal integration parameters on the BU-4DFE database

  t. the pairwise labels. Eventually, we construct tree t by calling algorithm 1. Those steps are summarized in Algorithm 2.

	end for
	balance bootstrap pairs with downsampling
	create new root node n
	call treeGrowing(pairs,n,{k (i) } i=1,...,6 )
	end for
	end for

Algorithm 2 Training a PCRF input: images x with labels l, number of candidate features {k (i) } i=1,...,6 for templates {ϕ (i) } i=1,...,

[START_REF] Dapogny | Dynamic facial expression recognition by static and multi-time gap transition joint classification[END_REF]

for all l ′ ∈ L do for t = 1 to T do randomly draw a fraction S ⊂ S of subjects pairs ← {} for all s ∈ S do draw samples x ′ s with label l ′ draw samples x s for each label l create pairwise data (x ′ s , x s ) with label l add element (x ′ s , x s ) to pairs

Table 2 .

 2 Comparisons with state-of-the-art approaches. § 7-class expression recognition with contempt label. † results respectively reported for two methods (average-vote) from the paper.

	Ck+ database	Protocol	Accuracy
	Wang et al. [19]	15-fold	86.3 §
	Shojaeilangari et al. [14]	LOSO	94.5
	Walecki et al. [17]	10-fold	94.5
	Khan et al. [9]	10-fold	95.3
	Dapogny et al. [6]	OOB	96.1 -94.8 †
	This work, RF	OOB	93.2
	This work, PCRF	OOB	96.4
	BU-4DFE database	Protocol	Accuracy
	Xu et al. [21]	10-fold	63.8
	Sun et al. [16]	10-fold	67.0
	Dapogny et al. [6]	OOB	72.2 -75.8 †
	Meguid et al. [1]	Cross-db	73.1
	This work, RF	OOB	70.0
	This work, PCRF	OOB	76.1
	FEED database	Protocol	Accuracy
	et al. [6]	Cross-db 53.0 -53.5 †
	Meguid et al. [1]	Cross-db	53.7
	This work, RF	Cross-db	51.9
	This work, PCRF	Cross-db	57.1
	BP4D database	Protocol	Accuracy
	Dapogny et al. [6]	Cross-db 72.2 -66.2 †
	Zhang et al. [24]	Cross-db	71.0
	This work, RF	Cross-db	68.6
	This work, PCRF	Cross-db	76.8

Table 3 .

 3 Profiling of total processing time for one frame (in ms)

	Step	time (ms)
	Facial alignment	10.0
	Integral HoG channels computation	2.0
	PCRF evaluation (M = 50)	4.8
	PCRF evaluation (M = 100)	7.8
	PCRF evaluation (M = 300)	19.0

Acknowledgments

This work was partially supported by the French National Agency (ANR) in the frame of its Technological Research CONTINT program (JEMImE, project number ANR-13-CORD-0004), and by the Labex SMART (ANR-11-LABX-65) the Investissements d ′ Avenir program, under reference ANR-11-IDEX-0004-02.