{'fraction_non_alphanumeric': 0.029265003371544168, 'fraction_numerical': 0.008799730276466623, 'mean_word_length': 4.922723642172524, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Shrinkage Optimized Directed Information using Pictorial Structures for Action Recognition

In this paper, we propose a novel action recognition framework. The method uses pictorial structures and shrinkage optimized directed information assessment (SODA) coupled with Markov Random Fields called SODA+MRF to model the directional temporal dependency and bidirectional spatial dependency. As a variant of mutual information, directional information captures the directional information flow and temporal structure of video sequences across frames. Meanwhile, within each frame, Markov random fields are utilized to model the spatial relations among different parts of a human body and the body parts of different people. The proposed SODA+MRF model is robust to view point transformations and detect complex interactions accurately. We compare the proposed method against several baseline methods to highlight the effectiveness of the SODA+MRF model. We demonstrate that our algorithm has superior action recognition performance on the UCF action recognition dataset, the Olympic sports dataset and the collective activity dataset over several state-of-the-art methods.


Introduction
The ability to accurately model spatial and temporal dependencies plays a crucial role in representing human activities from videos. For example, an activity performed by a single actor (e.g., walk) can be characterized a specific spatial organization of body parts at each time stamp (a spatial dependency) as well as by the evolution of such body parts in time (a temporal dependency); an activity performed by two (or multiple) individuals (meeting and talking) can be characterized by a specific arrangement of the individuals in the scene (a spatial dependency) as well as by the movement of such individuals in time (a temporal dependency). Despite recent successes in activity recognition research, finding a suitable way for capturing both types of temporal and spatial dependencies still remains an open problem. In this paper we propose a new unified framework that can be used to simultaneously capture directional (causal) temporal dependencies and spatial (bidirectional) dependencies for complex activities recognition.
Inspired by a recent contribution in [3], we propose to capture temporal dependency using the concept of directed information. The directed information (DI) was first proposed by Massey in 1990 [16] as an extension of Shannon's mutual information. The DI provides a decomposition of the MI into its causal and anti-causal components. Different from MI, DI is a function of the time-aggregated feature densities extracted from a pair of sequences with strong temporal structure. In [3], directed information was introduced for multimodality video indexing. In that work, a Jame-Stein shrinkage regularization was applied to control the overfitting error called shrinkage regularized directed information assessment (SODA). SODA is completely data-driven; it is based on non-parametric estimation of feature distributions and their associated information divergences. As shown in Fig. 2 and described in [3], SODA is sensitive to the directional information flow for video sequences across frames. While successful in capturing the ordering of events when two video sequences are compared, it does not capture spatial dependencies within each time stamp.
As demonstrated in other approaches for modeling the human pose [12], a Markov random field formulation (MRF) is suitable for capturing the structural dependencies among elements in the scene. Our main idea in this paper is to integrate a MRF approach for modeling spatial dependencies (among body parts of individuals as well as among individuals themselves) with a SODA formulation for modeling the temporal dependencies of individuals in time. Our SODA+MRF framework combines in a principled fashion a model-free directed information estimator over time with a model-based Markovian parts model [4] over space.
In the following paragraph we summarize our SODA+MRF approach to action recognition. We emphasize that the integration of SODA and MRF is natural and can significantly enhance the detection and recognition performance in both of the spatial and temporal domains. As illustrated in Fig.1, by detecting the human body parts and characterizing the human body configurations as a tree model based on histograms of oriented gradient (HOG) features, the full joint part distribution in each frame can be inferred using a MRF. In the presence of multiple people interactions, the spatial dependency can be inferred using pairwise potentials as function of their distance and location. Once the joint part distribution in each frame is estimated, SODA is then used to compute a similarity measure between pairs of sequences. Finally, a nearest neighbor classifier is applied to the distances for action classification and recognition as shown in Fig.1.
Our SODA+MRF framework has the following advantages: i) it is robust to view point changes. Compared to the work by Junejo et al. [10], that uses self-similarity distance for view invariant recognition, we take advantage of the information theoretical measure of the flow of information between past frames to obtain robustness to view point changes. ii) it yields better or at least comparable performance in action recognition accuracy compared to several state-of-the-art approaches including those of Le et al. [21], Niebles et al. [17], Choi et al. [4] for the UCF sports action recognition dataset, Olympic dataset and Collective activity dataset. The proposed pictorial SODA+MRF model captures dependencies between human body parts and interactions between people for action recognition. We infer the joint probability distribution (PDF) of body parts using a MRF for each video frame. Then, directed information is calculated between pairs of PDFs across frames and it is used to train a nearest neighbor classifier for action recognition.

Related Work
Action recognition has been extensively investigated in computer vision. Computing correlations between spatiotemporal (ST) volumes (i.e., whole video inputs) is the most straightforward method. Various correlation methods such as cross correlation between optical flow descriptors [1] and a consistency measure between ST volumes from their local intensity variations [19] have been proposed. In the work by Gao et al. [9], the authors discretized the state space and use the loopy belief propagation algorithm (LBP) for estimating the body pose in 2D for specific views. In the work by Felzenszwalb et al. [7], a computationally efficient framework for part-based modeling and recognition of objects was presented. They represented an object by a collection of parts arranged in a deformable configuration and used the resulting models to locate the corresponding objects in novel images. Recently, Ramanan et al. [18] developed a system for tracking the articulations of people from video sequences by first building an appearance model of each person and then detecting these models in each frame. In [20], Sundaresan and Chellappa proposed a general approach using Laplacian Eigenmaps and a graphical model of the Figure 2. Illustration of the advantages of DI (red curves) as compared to MI (blue curves) for capturing similarities between causal activities in pairs of video sequences. Videos A and B contain similar "Gather-talk-leave" event sequences while video C is a time reversed version of video B. As it is a directional measure, DI is more sensitive than MI to the ordering of events and this can be seen from the greater contrast between the two red ∆DI trajectories in each panel as compared to the lesser contrast between the two blue ∆MI trajectories(∆DI is the temporal change of the DI similarity measure over successive frames and similarly for ∆MI).
human body to segment 3D voxel data of humans into different articulated chains. In [14], Laptev et al. utilized automatic collection of realistic samples of human actions from movies based on movie scripts for automatic learning. The recognition of complex action classes relies on space-time interest points and a multi-channel SVM classifier. More recently, in [10], Junejo et al. explored self-similarities of action sequences over time and developed an action descriptor that captures the structure of temporal similarities and dissimilarities within an action sequence. However, these works did not explore the directed temporal dependency and bidirectional spatial dependency in a unified framework.
As far as we know, this is the first time that a directed measure (SODA) coupled with a Markov Random Field (MRF) model has been proposed for action recognition. The work [15] by Liu and Shah applied Shannon's mutual information (MI) for selecting high level visual words for describing and classifying human actions from videos.

SODA+MRF Frame Work
Markov random fields (MRF) constitute a simple but powerful means to model interaction between nearby objects [4]. The basic idea of the SODA+MRF model is simple: we first infer the joint probability density distribution (PDF) of the graph connecting body parts within each frame using a Markov random field (MRF) and subsequently characterize the temporal dependencies across frames by calculating directed information between pairs of video sequences based on these PDFs using SODA. We integrate MRF and SODA into a unified framework for pictorial structure based action recognition as shown in Fig. 1.

MRF for Pictorial Structures
Part-based Understanding with MRF: In order to compute SODA between pairs of video sequences, we first estimate the joint probability density distribution of body parts within each frame using Markov random field for inference. Taking one person a as an example, we consider a threepart based model and also a five-part based model. The three-part based model includes the head and torso, left arm and right arm denoted by T a , L a , R a respectively. For the dependencies between different human body parts, as shown in [18], they can be characterized by a tree-or star-based model as shown in Fig.3 where only the dependencies between torsos and the rest of the body parts are consid- Figure 3. The proposed SODA+MRF pictorial structures for two video sequences for activities "Gather-Talk-Leave" where the proposed model successfully incorporates the strong interactions between two people in the activities "Gather" and "Talk" and the weak interaction between two people in the activity "Leave". Here T, R, L represent the torso, right arm and left arm, respectively, and the subscripts denote different people and the links characterize the dependencies. The recognition is achieved by determining whether X (unlabelled) is in the same action category as Y (labelled). ered. In a Markov random field, given a set of random variables a }, the joint density can be factorized over the cliques of the graph. For a single person, the joint probability density distribution of the mth frame can therefore be computed by the product of clique potentials over the maximal cliques f(T a ) capture the spatial dependencies between different human body parts, a ) represents the distance between the centers of the torso and the left arm. The parameter γ 1 weights the importance of the second type of potentials ψ 2 relative to the first potential terms ψ 1 . Interaction Detection: We extend our model to multiple people by considering the dependencies due to human interactions. Recent work in collective activity recognition [4] suggests that the interactions between human actions highly depend on the spatial distance of two people in the video frame and the temporal duration of the actions. In this work, the spatial interaction between people is automatically controlled by the pairwise potential term in the MRF. By considering the interaction between the body parts of two people, the joint probability density feature distribution of the mth frame can be computed as where the pairwise potential term in the mth frame is represented by Here ) represents the distances between the center of the torsos for two people.
) are defined similarly. The potential terms indicates that the interaction increases when the distance between two people decreases.
The proposed SODA+MRF for two video sequences "Gather-Talk-Leave" is shown in Fig.3 where both of the strong interaction between two people in "Gather" and "Talk" and the weak interaction between two people in "Leave" are incorporated into the model. Once the feature vector from the HOG descriptor is obtained, we perform estimation for the probability density function in MRF model using Gibbs Sampling (with 500 iterations for burn-in and 1000 iterations for sampling). The parameters γ 1 , γ 2 are estimated using maximum likelihood. The model can also be easily extended to the case of more than two people by considering all pair-wise interactions. SODA+MRF For Video Sequences: Once the feature probability density distribution is estimated from the MRF in each frame, the temporal dependence is estimated using shrinkage optimized directed information assessment (SODA). Consider two video sequences V x and V y with M x and M y frames, respectively. Denote by X m and Y m the joint distributions from MRF extracted from the m-th frames of V x and V y using MRF, respectively, and define . The time aligned directed information (DI) from V x to V y is a non-symmetric generalization of the mutual information (MI) defined as [16] ) is the conditional MI between X (m) and Y m given the past which gives the intuition that the DI is the cumulative reduction in uncertainty of frame Y m when the past frames Y (m − 1) of V y are supplemented by information about the past and present frames X (m) of V x . The DI prescribes a decomposition of the MI into a sum of causal and anti-causal DIs. It is for this reason that the MI masks directional information revealed by the DI. The SODA approach gives a DI estimator that is specifically adapted to the high dimension of video sources.
To apply SODA we first implement scalar quantization of the part-based PDF in each video frame. In order to implement the DI, the vector of multinomial parameters θ must be empirically estimated from the video sequences. However, since the feature dimension is large the number of unknown parameters greatly exceeds the number of feature instances. Substitution of maximum likelihood (ML) estimates in place of θ, will produce severe overfitting errors. SODA applies James-Stein shrinkage approach to improve the MSE of the plug-in estimator, as described in [3]. This approach is based on shrinking the ML estimator of θ towards a target distribution t with uniform distribution,θ λ where λ ∈ [0, 1] is a shrinkage coefficient used to optimize DI estimation performance. The James-Stein plug-in entropy estimator is defined as:Ĥθ λ (X) = −n p k=1θ λ k log(θ λ k ). The corresponding SODA plug-in estimator for DI is simply DI λ = DIθ λ (V x → V y ). The optimal value of λ that minimizes estimator MSE is [3]: , is a James-Stein DI estimate that yields the SODA estimate.

SODA+MRF-based pictorial structure recognition algorithm
SODA can be used for temporal localization of interactions by aligning the video sequences. Once the DI optimal shrinkage parameter has been determined, the local DI is defined similarly to the DI except that, for a pair of video sequences X and Y , the signals are time shifted and windowed prior to DI computation. Specifically, let τ  (2), defines a surface over τ x , τ y . We use the peaks of the local DI surface to detect and localize the interactions in the pair of video sequences. We summarize the algorithm below: 1. Detect and localize the articulated human body parts for each video frame using the object detection algorithm [8]. Extract HOG features from each detected human regions. Compute the joint distribution of the graph for each frame according to the graph structure using a MRF by equation (1).
2. Use SODA to calculate local DI for the pair of video sequences and use the optimal sliding window learned from the training phase to detect the local peaks in the DI surface. We define the local DI between video pairs X and Y as DI(Y i , X j ) where i, j is the time index in the video sequence. We generate a quantitative measure of the statistical significance of each p-value using the expression 1−Φ D ij −µij σij on these DI estimates where µ ij and σ ij stands for the mean and the variance, Φ here stands for the cumulative distribution function of Gaussian distribution. The p-values correspond to the probability that the observed DI peak values follow the null hypothesis that the mean DI is equal to zero. The test statistic is computed as T = DI(Y, X) = max i,j DI(Y i , X j ), (i, j ∈ Z + ) Threshold the DI and p-value matrices to find common activities exhibiting large and statistically significant DI.

Experimental Results
Dataset used: We evaluate the performance of SODA+MRF model on three datasets: the UCF50 action recognition dataset, the Olympic Sports Dataset and the Collective Activity Dataset. (i) UCF50 is an action recognition dataset with 50 annotated action categories, consisting of realistic videos taken from YouTube including: Baseball Pitch, Basketball Shooting, Bench Press, Biking, Billiards Shot, Breaststroke, Clean and Jerk, Diving, Drumming, Fencing, Golf Swing, Playing Guitar. For all the 50 categories, the videos are grouped into 25 groups, where each group consists of more than 4 action clips. The video clips in the same group may share some common features, such as the same person, similar background, similar viewpoint, and so on. (ii) The Olympic Sports Dataset contains videos of athletes practicing different sports with 16 sport classes and 50 sequences per class. (iii) The collective activity dataset contains 7 different collective activities: crossing, walking, waiting, talking, queueing, jogging and dancing and 60 video sequences with varying view point.
Whenever we report performance comparisons in the following experiments, a 5 part model is utilized. The five-part based model includes heads and torsos, left arms, right arms, left legs and right legs. The pairwise DI was computed using the aforementioned SODA+MRF method for all pairs of video clips in the database. The pairwise symmetrized DI's were then used to train a nearest neighbor classifier where the symmetrized DI is the sum of DI from the video sequence X to Y and Y to X. Half of the videos were randomly selected for training and the remainder were used for testing. Feature Representation: Our model of human actions can be applied over a variety of video descriptors. In this paper, the human body parts are detected using the method presented in [8] which is a complete learning-based system for detecting and localizing objects in images. The features within the detection windows for body part configurations are represented with histogram of oriented gradient (HOG) descriptors. The histogram of oriented gradient (HOG) descriptors [5] contain four main steps including gamma/color normalization, gradient computation, spatial/orientation binning and normalization and descriptor blocks. In practice this is implemented by dividing the image window into small spatial regions called cells, for each cell accumulating a local 1-D histogram of gradient directions or edge orientations over the pixels of the cell. The number of orientation bins is selected to be 9 bins spaced over 0 • -180 • . We utilize 3×3 cell blocks of 6×6 pixel cells for detection where detectors are based on rectangular bounding boxes. Competing Algorithm investigated: For the UCF action recognition dataset, the performance will be compared to several state-of-the-art approaches and baseline methods including: Le et al. [21], Wang et al. [22], Laptev et al. [14][13] and Klaser et al. [11]. We also compare to SODA without MRF [3] as a baseline method. In [21], Le et al. presented an extension of the Independent Subspace Analysis algorithm to learn invariant spatio-temporal features from unlabeled video data. The performance on Olympic sports dataset is compared to the method by Niebles et al. [17] and [14]. In [17], the authors presented a framework for modeling motion by exploiting the temporal structure of human activities. The performance on the collective activity dataset is compared to Spatial Temporal Volume representation (STV) and Randomized Spatial Temporal volume representation (RSTV) [4] where RSTV is constructed on a Random Forest structure which randomly samples variable volume spatial-temporal regions to pick the most discriminating attributes for classification.

Evaluation with UCF action recognition dataset
Localization of Common Activities: In order to gain more insight into the proposed method for part-based understanding, we show that SODA+MRF is capable of accurately recognizing single human actions independent of viewpoint. In Fig.4, we illustrate the local DI between a video pair, denote from X to Y was rendered as a surface over τ x , τ y for a FDR of 0.1 where the FDR is the expected proportion of false positives among all significant hypotheses, as explained in Section 2.2. The peaks on this surface were used to detect and localize common activities, i.e., activities in X that were predictive of activities in Y . SODA+MRF detects 10 interactions while SODA without MRF only detects 5 interactions. The bubbles (dots) in Fig.4 occur at the peaks of the pairwise DI using the window size T = 7 with the highest average precision and the size of each bubble inversely proportional to the corresponding p-value. The figure shows that the most similar actions "kick" occur at the 12th and 28th frames in X (front view) and the 22th and 43th frames in Y (side view) denoted by DI peaks. Since directed information calculates the accumulated information for the current frame given all of the past frames for the purposeful action "kick", although the appearances from two sequences have variations due to different views, the intrinsic distance based on DI is robust to the change of view. The performance continues to be significant over a range of practical FDR thresholds (0.1 to 0.05). Compared to the recognition result using SODA only [?], the SODA+MRF method significantly improves the recognition performance, as indicated by the more highly concentrated peaks of the inverse p-values in Fig.4. Since both SODA+MRF and SODA utilize directed information to capture the temporal structures, the superior performance can be mainly attributed to the use of the pictorial structures by coupling the Markov random field with SODA to model the spatial dependency between different human body configurations and interactions.
Interaction Detection: Moreover, we demonstrate that SODA+MRF can successfully discriminate different actions for multiple people with interaction. In these two sequences "walk-front" and "skateboarding-front", from the 1st to the 40th frames, the actions are similar since both of them contain two people walking side by side. From the 41st to 50th frames, in the sequence of "skate-boarding", two people start to chase each other where the action "chasing" is characterized with much stronger temporal directional dependency and larger spatial distances compared to the action "walk side by side". As shown in Fig.5, our scheme is sensitive in detecting such interaction changes by modelling the spatial and temporal dependencies accurately. The results indicate that the most similar two actions happen at the 12th and 40th frames in X and the 23th and 44th frames in Y . All of the 10 true positives are detected in the first 40 frames, where the positions of the true positives represents the frame indices for the most similar frames in two sequences. Compared to the use of the SODA method only, our SODA+MRF method also successfully removed two false positives (highlighted in green in Fig.5). Again, the advantage of our method is attributable to the coupling of MRF with SODA that allows it to capture complex interactions between people with significant background variation.
Comparisons: We first report the average accuracy of several baseline methods for recognition in order to demonstrate the superiority of the proposed method, as shown in Table 1. The baseline methods include: MRF+MI, 3D MRF and SODA+MRF without interaction where the MRF+MI method models the spatial dependency using a MRF and the temporal dependency using mutual information; the 3D MRF models both the spatial and temporal dependencies using a three dimensional MRF. The SODA+MRF model without interaction ignores all the interaction between people by setting the pairwise potential ψ 2 to be a constant. A thorough comparison of the mean average precision for UCF action recognition dataset with the state-of-the-art approaches is shown in Table 1. It can be seen that our SODA+MRF method not only achieves significant advantages over the three baseline methods but also outperforms a wide range of the state-of-the-art approaches. Furthermore, the table indicates that by considering the interaction between different human body configurations, SODA+MRF improves the recognition accuracy by 4.8%. Compared to the best published performance of [21] (86.5%), our SODA+MRF method has an improved mean average precision of 88.3% for the UCF action recognition dataset. We also compare computational complexity in Table 2 for a machine running Matlab with 2.26GHz CPU and 24Gb RAM. My τy ) between pairs of UCF videos using the same class of the activity from different views: X (kick-front-view) and Y (kick-side-view) using SODA+MRF model (black) and SODA model (red). Here the axes range over τ x and τ y , which denote time shift parameters of the respective video frames, and the sliding window width is T = 7 frames. The 10 most significant theoretical p-values (blue circles whose sizes are proportion to statistical significance of the DI peaks) are shown to indicate the most statistically reliable DI peaks. The SODA+MRF model achieves more significant statistical p-values compared to SODA only. The results indicate that the most similar two actions happen at the 12th and 28th frames in X and the 22th and 43th frames in Y . The size of the bubble is inverse proportional to the p-values.

Evaluation on Olympic sports dataset
Here we evaluate SODA+MRF on the Olympic sports dataset which includes strong temporal structures. We demonstrate improvements in average precision for the classification task in Table 3, where our method achieves average precision of 75.1% for all the 16 activities compared to 72.1% (Niebles et al. [17]) and 62.0% (Laptev et al. [14]). Our method achieves the best average precisions for 12 of the 16 activities.
These results indicate the efficacy of our SODA+MRF method in recognizing complex human actions. My τy ) between UCF videos using different activities: X (walk-front-view) and Y (skate-boarding-front-view) with similar setting as Fig.4 where in the 1st to 40th frames, the two sequences contain similar actions "walking side by side" and in the 41st to 50th frames, they have dissimilar actions with "walking" and "chasing" respectively. The top 10 true positives discovered by our methods are annotated with the corresponding p-values in black. The detections of false positives from SODA are highlighted with green bounding boxes. The results indicate that the most similar two actions happen at the 12th and 40th frames in X and the 23th and 44th frames in Y . We show results on the 6-category collective activity dataset in Fig.6. In Table 3, we demonstrate final classification accuracy for the 6-category dataset by comparing SODA+MRF with the RSTV method [4] which previously had the best reported performance for this dataset for activities of crossing, waiting, queueing, talking, dancing and jogging. As shown in Table 4, the SODA+MRF method achieves an average precision 0.847, which is slightly better than RSTV having average precision 0.82. However, if one excludes the "jog" activity for which RSTV is the top performer, SODA+MRF performs uniformly better than RSTV, achieving average precision of 0.846 (SODA-MRF) as compared with 0.796 (RSTV) overall. This demonstrates that the proposed method is effective in capturing the subtle spatial and temporal interactions between body configurations compared to RSTV which detects general interactions between people. We believe that SODA+MRF underperforms for the jogging activity is mainly due to its difficulty in detecting non-frontal faces and occlusions. A refined implementation of the MRF parts model that accounts for occlusions may overcome this difficulty. This is future work.

Conclusion
We proposed a novel framework called SODA+MRF for activity recognition. The spatial dependency between human body configurations and the interaction of these configurations are characterized by a Markov Random Field model. SODA+MRF combines the MRF model with a James-Stein shrinkage approach to DI estimation, resulting in minimum mean squared error to capture the temporal dependency across frames. We illustrated the SODA+MRF model for activity detection/localization with the UCF action recognition, the Olympic sports dataset and the collective activity databases. Our results indicate that the SODA+MRF model is able to discriminate video events that involve strong human interactions and demonstrates better action recognition performance as compared to several state-of-the-art approaches.