Histogram of Oriented Displacements (HOD): Describing Trajectories of Human Joints for Action Recognition

1 Introduction

A trajectory is defined as the path of a point moving with time. For videos, these points can be low level visual features, or high level visual features like human skeletal joints. If we can extract these features with acceptable accuracy and adequately describe their trajectories, we can perform better video classification. One of the most popular video classification applications is human action recognition.

Human action recognition in videos has been an active research topic in computer vision. One of the problems in the recognition is the availability of data. Accurate data like MoCap, such as CMU MoCap 1 and HDM05 [M¨uller et al., 2007], is expensive to acquire. Recently, Microsoft Kinect and other low cost sensors provided the depth data with acceptable accuracy. [Shotton et al., 2011] developed a realtime approach to extract 3D joints positions from a single depth image. Despite requiring extensive training on synthetic data, extracting the joint locations in real-time became a doable task. With all these available data, interactive touchless games became tractable. However, researchers still have In this paper, we exploit these skeletal joint 3D locations to develop an efficient action recognition approach. We introduce a novel 2D trajectory descriptor: Histogram of Oriented Displacements (HOD). To construct HOD, each displacement in the trajectory votes with its length in an orientation angles histogram. We use HOD to describe the three projections of each 3D trajectory for each body joint. For temporal modeling, we apply a temporal pyramid that describes the trajectory as whole, halves and then quarters. We show how the proposed descriptor is efficient and discriminative on two popular datasets: MSR-Action3D [Li et al., 2010] and HDM05 [M¨uller et al., 2007]. For the two datasets, our descriptor outperforms the state-of-the-art using off-the-shelf classification approaches.

1 http://mocap.cs.cmu.edu/

The paper is organized as follows: In Section 2, we review the related work in both trajectory description and activity recognition. Our approach is described in Section 3. Section 4 introduces the datasets used with the experimental results. Section 5 concludes the paper.

2 RelatedWork

2.1 Trajectory Description

The problem of finding efficient and representative trajectory descriptors has many applications in robotics/human motion analysis and video copy detection. Most work in literature that tried to create a descriptor for the trajectories did not target a fixed-length descriptor.

[Wu et al., 2008] and [Yang and Li, 2010] introduced a variable-length descriptor using the curvature and torsion of each point on the trajectory and their derivatives. They developed a similarity measure to match their trajectory descriptors. In [Wang et al., 2011], they described each trajectory using the normalized displacement vector, but limited the trajectory length to a fixed value, instead of handling different lengths.

In their work on activity recognition in unconstrained videos, [Sun et al., 2009] used a fixed-length trajectory descriptor. They normalize and quantize the displacement vector D in terms of magnitude and orientation. Each displacement has a state between 1 to 25 (3 magnitude levels × 8 orientation levels + 1 for the zero level). After quantizing all displacement vectors along a trajectory, they translate the sequential relations between these vectors into a directed graph, which is similar to the state diagram of a Markov chain. Finally, they calculate the transition matrix P and the descriptor is the stationary distribution row vector π of P .

In their work on video copy detection, [Chen et al., 2010] used a fixed-length descriptor for a 2D trajectory. The descriptor was used to classify the trajectories into four categories: static, horizontal motion, vertical motion and complex motion. They quantize the displacement vector D and build a 5-bin histogram for them. They used 2 quantization levels for magnitude and 4 for orientation. Each histogram bin counts the number of displacements in the quantization range.

2.2 Action Recognition

The availability of skeleton joints locations at real-time [Shotton et al., 2011] was a great motivation for researchers to develop more efficient and powerful recognition approaches. [Yao et al., 2011] showed that pose-based features outperform low-level appearance features, even when heavily corrupted by noise, suggesting that pose estimation is beneficial for the action recognition task.

Researchers used generative models like Hidden Markov Model (HMM), or discriminative models, such as Conditional Random Fields (CRF) [Han et al., 2010]. These methods use the joint positions or histograms of the joint positions as observations. In [Xia et al., 2012] a histogram of 3D joints descriptor in a frame is computed, a dictionary is built and the temporal modeling is done via HMM. However, these complex generative models are easy to overfit due to the limited amount of training data. Moreover, the 3D joint positions that are generated from depth map sequences are noisy (compared to that of the MoCap data). That makes determining the accurate states from the observations very difficult, especially in similar actions.

[Wang et al., 2012] showed that the complex and nonlinear dynamics can be characterized by a Recurrent Neural Network [Martens and Sutskever, 2011]. However, the performance was not promising. Another applicable neural network method is the Conditional Restricted Boltzman Machines [Mnih et al., 2012]. Due to the large number of parameters to tune, the latter two models need lots of data and epochs to be able to estimate model parameters accurately.

For MSR-Action3D dataset, the state-of-the-art classification accuracy using joint positions was done by [Wang et al., 2012]. They used the 3D joints positions to construct a descriptor of relative positions between joints. The descriptor is then concatenated with Local Occupancy Patterns to capture the human-object interaction. To capture the temporal behavior, a Fourier Pyramid of this descriptor was introduced. Finally, they used this descriptor to mine a set of actionlets for each class. The weights of the actionlets are then learnt via Multiple Kernel Learning to perform the classification. We have proposed another descriptor in [Hussein et al., 2013], which describes the action using covariance of joint features. However, our simple descriptor here with linear SVM outperforms [Wang et al., 2012] sophisticated classification procedure. It also outperforms our other approach [Hussein et al., 2013] on the datasets tested here.

3 Approach

Our approach is to describe the 3D trajectory of each joint separately, as shown in figure 1. First, we replace the 3D trajectory of each joint with three 2D trajectories representing the three projections on the three orthogonal Cartesian planes (xy, yz, and xz). The 3D trajectory descriptor is the concatenation of the three. Temporal pyramid is built for each 2D trajectory to capture the temporal information. We describe each 2D trajectory using a Histogram of Oriented Displacements.

In the next subsections, we explain the 2D descriptor: HOD, temporal pyramid and the final descriptor for each joint. The final descriptor, for each video sequence is the concatenation of this descriptor among all available joints.

3.1 Histogram of Oriented Displacements (HOD)

We introduce a novel 2D trajectory descriptor, we call it HOD. The trajectory is described using a histogram of the directions between each two consecutive points. Given a trajectory T = {P1, P2, P3, ..., Pn}, where Pt is the 2D position at time t. For each pair of positions Pt and Pt+1, calculate the direction angle θ(t, t + 1), as the angle of the line with slope in equation 1.

Value of θ is between 0 and 360. A histogram of the quantized values of θ is created. If the histogram is of 8 bins, the first bin represents all θs between 0 and 45.

The histogram accumulates the lengths of the consecutive moves. For each θ, a specific histogram bin is determined using equation 2. The length of the line between Pt and Pt+1 is then added to the specific histogram bin. Figure 2 shows an example of a displacement when using a histogram of length 8.

To show the intuition behind the descriptor, consider the action of waving hands. At the end of the action, the hand falls down. When describing this down movement, the descriptor does not care about the position from which the hand started to fall. This fall will affect the histogram with the appropriate angles and lengths, regardless of the position where the hand started to fall.

HOD records for each moving point: how much it moves in each range of directions. HOD has a clear physical interpretation. It proposes that, a simple way to describe the motion of an object, is to indicate how much distance it moves in each direction. If the movement in all directions are saved accurately, the movement can be repeated from the initial position to the final destination regardless of the displacements order. However, the temporal information will be lost, as the order of movements is not stored-this is what we solve by applying the temporal pyramid, as shown in section 3.2. If the angles quantization range is small, classifiers that use the descriptor will overfit. Generalization needs some slack in directionswhich can be done by increasing the quantization range.

3.2 Temporal Pyramid

Dealing with the trajectory as whole misses the temporal information. In order to capture the temporal evolution, we apply a temporal pyramid approach. In the first level, the whole trajectory is used to construct a part of the descriptor. At the second level, the trajectory is divided into two halves and each one of them is used separately to obtain the second two parts of the descriptor. If the number of levels is 3, the descriptor is made of 7 parts: 1 for the first level, 2 for the second level and 4 for the third. The final descriptor is the concatenation of the seven parts. In other words, a histogram at a specific level will be split into two histograms in the next level. Similar spatial and temporal pyramids were used in [Lazebnik et al., 2009] and [Wang et al., 2012]. The values of the histogram at a specific level to be the summation of the two histograms that result from its splitting.

Figure 3 shows an example of the pyramid using 3 levels for the xy projection in figure 4. The figure shows how the pyramid catches the temporal variation. Most moves happened in the second part of the video as clear from second level. The third level captured the difference in movement between the third quarter and the forth.

3.3 3D Trajectory Descriptor

In order to describe the 3D trajectory of one joint, we use the HOD of the three 2D projections (xy, yz and xz). The final descriptor for the joint is the concatenation of the three 2D descriptors.

Figure 4 shows the projections of the Right Hand joint when the first subject int the MSR-Action3D dataset performs the action of High Arm Waving.

3.4 Discussion

The descriptor does not require any pre-processing for the joints positions. It is scale-invariant, given that the histograms are normalized. Our current implementation is not rotationinvariant. However, it can be made rotation-invariant by mapping all the positions such that two specific sticks become the x and y axes. For example, the stick between the two shoulders and the stick between head and spine.

Using the magnitude of the displacement to update the histogram makes the descriptor speed-invariant. If the linear movement between Pt and Pt+1 is performed between 2 frames, it will affect the histogram by the same amount as if it is performed over 20 frames.

One important advantage of HOD is the efficiency in computations. For each frame, the only computation required is: 1) calculate the displacements of positions. 2) calculate the angles. 3) update the appropriate histogram bins. Even when applying multiple levels for the pyramid, we do not need to compute all levels. Due to the dependency between levels, we only need to compute the deepest level, then the higher levels are computed in constant time(for a specific number of bins).

One of the main reasons why the proposed descriptor has the potential to be applicable to real world is the low number of parameters to tune. Section 4.2 shows that our weakest configuration competes favorably with some of the popular approaches in literature.

4 Experiments

In this section, we explain our experimental setup and show our experiments and experimental results. We used two datasets: MSR-Action3D and a subset of the HDM05 dataset used in [Ofli et al., 2012]. All experiments are done on the original raw data without any normalization before calculating the descriptor. After creating the descriptor, we apply L2 normalization on the descriptor to achieve scale-invariance. The used classification algorithm is a linear SVM using LIBSVM [Chang and Lin, 2011].

4.1 Datasets MSR- Action3D

We use the MSR-Action3D [Li et al., 2010] which has 20 action types, 10 subjects, each subject performs each action 2 or 3 times. There are 567 depth map sequences in total. We use the standard setup, which divides the data into three action sets. Each set has 8 actions with some overlap between action sets. The same setting has been used recently in [Wang et al., 2012]. We used the 20 joints locations as extracted in [Shotton et al., 2011]. The actions are high arm wave, horizontal arm wave, hammer, hand catch, forward punch, high throw, draw x, draw tick, draw circle, hand clap, two hand wave, side-boxing,bend, forward kick, side kick, jogging, tennis swing, tennis serve, golf swing, pickup & throw. The actions are divided into 3 action sets as shown in table 1. The available 20 joints are shown in figure 5.

HDM05

Similar to [Ofli et al., 2012], we applied our approach to a Motion Capture dataset, namely the HDM05 database [M¨uller et al., 2007]. There are three main differences between this dataset and the preceding dataset: First, it is captured using motion-capture sensors, which leads to much less noise than in the data acquired by a Kinect sensor. Second, the number of joints recorded is 31 instead of 20. This leads to a longer descriptor. Third, the frame rate is much higher, 120 fps instead of 15 fps as in the preceding dataset.

We used the same setup in [Ofli et al., 2012] with the same 11 actions performed by 5 subjects. We had 249 sequences in total. We used 3 subjects (140 action instances) for training, and 2 subjects (109 action instances) for testing. The set of actions used in this experiment is: deposit oor, elbow to knee, grab high, hop both legs, jog, kick forward, lie down floor, rotate both arms backward, sneak, squat, and throw basketball

4.2 Results and Discussion

MSR-Action3D

For the MSR-Action3D dataset, we compare our approach to the state-of-the-art classification results using skeletal joint positions at [Wang et al., 2012]. They use Multiple Kernel Learning to classify a testing example using different actionlets for each action.

The best classification accuracy they obtain is 88.2% using the ensemble and the accuracy is lower when they apply their descriptor directly to a linear SVM, they did not report the results of the latter case. However, they reported that removing ensemble from experiments on MSR-DailyActivity3D dataset, decreased their accuracy from 85.75% to 78%. This shows how the accuracy decreases considerably when the ensemble is removed.

Using 16-bin HOD and 2-level temporal pyramid, we get classification accuracy of 91.26% without using boosting nor ensemble methods. 2

Table 2 shows the classification accuracy using linear SVM and when using temporal pyramids of different number of levels and using 16-bin HOD. Results show that adding more levels enhances the classification accuracy. When the accuracy decreases upon increasing the levels, it means that the available frames in each histogram of the new level are too few to make a meaningful histogram. Even with only one level, our descriptor still outperforms the state-of-the-art. Table 3 shows the results reported in [Wang et al., 2012] in addition to our obtained accuracy.

The number of bins of the histograms affects the results. We studied this effect by changing the length of the histogram and repeating the experiments of table 2. Figure 6 shows the classification accuracy when using different lengths of histograms. We tried 4 histogram configurations: 4, 8, 12 and 16. The 4-bin histogram is the least accurate but still a lot better than a random classifier.

One of the interesting observations is that our weakest configuration (4-bin HOD with only 1-level temporal pyramid) outperforms Recurrent Neural Networks [Martens and Sutskever, 2011], Hidden Markov Model [Xia et al., 2012] and Action Graph on Bag of 3D Points [Li et al., 2010] as shown in table 3. This superiority is due to the physical meaning of the descriptor that we illustrated in section 3. It contains more information about the sequence, that is you may be able to recover more of the original data than from other descriptors. Moreover, the descriptor for this configuration is only 240 values for the complete video (3 projections × 20 joints × 4 bins of histogram × 1 histogram for the only level). This means that our descriptor is still discriminative even without careful parameter tuning. Requiring careful parameter tuning is a problem that decreases the applicability of any recognition method. For instance, [Wang et al., 2012] needs to choose the number of Fourier coefficients to use, confidence and ambiguity values to mine the actionlets.

One way to show the strength of the descriptor is to study the classification accuracy when using only one joint at a time. Table 4 shows that using the information of only one joint is much better than a random classifier. The descriptor's length is only 144 (3 projections × 1 joint × 16 bins of histogram × 3 histograms for the two levels). When using the right hand joint only the accuracy is 74.07%, this outperforms RNN and is very close to HMM and Action Graph on Bag of 3D Points, as shown in table 3. 3

2 We excluded 13 sequences with around 1/3 of each sequence with zero-measurements in actions bend and pickup & throw. When we include the corrupted sequences but remove the corrupted frames, we get 90.24%. In our method, removing the zeromeasurement frames means a linear interpolation for these frames. With the corrupted sequences and the corrupted frames, we get 88.11%.

These interesting results propose that, we may not need to detect all joints to recognize actions. Only a subset of these joints (possibly one joint only) can discriminate actions well. If the joint movement is similar in two actions, this joint won't be enough for discrimination. This is clear when observing right hand joint results. The right hand joint mainly failed to discriminate between high arm wave and two hand wave, because its movement is similar in the two actions. Only 30% of the testing examples of the high arm wave action are classified right, while 58% of them are mis-classified as two hand wave.

HDM05

For the HDM05 dataset, we compare our approach to [Ofli et al., 2012]. The best classification accuracy they get is 84.4%.

3 Subjects who recorded this dataset were informed to perform the action using their right hand, if it is done using only one hand.

We get 97.27% using 4-bin HOD and 3-level temporal pyramid. As shown in table 5, all our configurations outperform them except for the weakest one.

Using only the right elbow positions, we get classification accuracy of 82.72%. This is very close to the prior work of [Ofli et al., 2012] and with descriptor of length 168 (3 for the three projections × 7 for temporal pyramid × 8 for each histogram). The classification accuracy when using each joint separately are shown in table 6. We use the 31 available joints.

5 Conclusion

This paper addressed the problem of human action recognition using the skeletal joint locations. We introduced a novel 2D trajectory descriptor: Histogram of Oriented Displacements (HOD). We used HOD to efficiently describe the 3D joints trajectories. HOD is scale-invariant and speedinvariant. Recognition using this descriptor directly with linear SVM outperforms the best published results that use more elaborate classification procedures on two public datasets: MSR-Action3D and HDM05. The discrimination power of the descriptor allowed our weakest configuration to outperform three popular methods in literature: Hidden Markov Model, Recurrent Neural Networks and Action Graph on Bag of 3D Points.

Acknowledgment

This research was sponsored by a grant from the Microsoft Research Advanced Technology Lab Cairo. The project was hosted by Virginia-Tech-Middle East and North Africa (VTMENA) Research Center in Alexandria University, Alexandria, Egypt.