{'fraction_non_alphanumeric': 0.04222069910897875, 'fraction_numerical': 0.012679917751884852, 'mean_word_length': 4.510007552870091, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, '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}}
Human Motion Capture Data Tailored Transform Coding

Human motion capture (mocap) is a widely used technique for digitalizing human movements. With growing usage, compressing mocap data has received increasing attention, since compact data size enables efficient storage and transmission. Our analysis shows that mocap data have some unique characteristics that distinguish themselves from images and videos. Therefore, directly borrowing image or video compression techniques, such as discrete cosine transform, does not work well. In this paper, we propose a novel mocap-tailored transform coding algorithm that takes advantage of these features. Our algorithm segments the input mocap sequences into clips, which are represented in 2D matrices. Then it computes a set of data-dependent orthogonal bases to transform the matrices to frequency domain, in which the transform coefficients have significantly less dependency. Finally, the compression is obtained by entropy coding of the quantized coefficients and the bases. Our method has low computational cost and can be easily extended to compress mocap databases. It also requires neither training nor complicated parameter setting. Experimental results demonstrate that the proposed scheme significantly outperforms state-of-the-art algorithms in terms of compression performance and speed.

very high frequency, therefore, the generated mocap data is usually bulky, which poses a challenge to both storage and transmission. It is highly desirable to develop an efficient method for compressing mocap data.
The primary goal of data compression is to reduce the redundancy or correlation in the data. As an effective tool for data decorrelation, transform coding maps the original data into the transform domain, in which the transform coefficients have significantly less dependency than the original data. Since most of the energy concentrates on a small portion of the transform domain, compression can be achieved by discarding the less-important information (i.e., setting the smallest coefficients to be zeros). To recover the data, one simply applies the inverse transformation to the transform coefficients. Representative transform coding methods are the Karhunen-Loeve Transform (KLT), Principal Component Analysis (PCA) (or more generally, Singular Value Decomposition (SVD)), Discrete Wavelet Transform (DWT), and Discrete Cosine Transform (DCT). Among them, the 2D DCT and DWT methods are extremely successful in images/videos compression, e.g., JPEG-2000 and H.264/AVC, due to the locally smooth nature in images and/or videos, leading to most transform coefficients occupying low frequencies. Since human mocap data can be naturally represented by a 2D matrix, where each row corresponds to the trajectory of a marker, one may simply borrow the existing image-based transform coding methods to mocap data. Unfortunately, our analysis shows that mocap data have some unique characteristics that distinguish themselves from images and videos. Therefore, directly applying DCT or DWT does not work well. This paper presents a novel transform coding method for compressing human mocap data. Observing that a subset of a long mocap sequence exhibits stronger data dependency, we segment the input data into a set of clips, and represent each clip by a matrix, where each row is the trajectory of a marker. Note that mocap data is smooth in the dimension of time, since each marker's trajectory is a smooth curve in R 3 . See Fig. 1. However, the columns exhibit much less smoothness due to the complex nature of human motion. Based on these observations, our transform coding method adopts a data-dependent left transformation and a data-independent right transformation, where the former is to reduce redundancy among the non-smooth columns and the latter is to decorrelate the smooth rows. Our transform coding is very effective, since it produces only a small number of coefficients in the transform domain. Moreover, our method has low computational cost and can be easily extended for mocap database compression. Unlike the existing approaches to mocap data compression, our method requires neither training nor complicated parameter setting. Experimental results demonstrate that the proposed method significantly outperforms state-of-the-art algorithms in terms of speed and compression performance.
The rest of this paper is organized as follows: Section II briefly reviews previous work on mocap data compression.
Section III analyzes the human mocap data and shows its unique features, which distinguish themselves from natural images and videos. Then Section IV presents our tailored transform coding, which is further generalized to mocap database in Section V. Section VI evaluates our method and presents the experimental results. Finally, Section VII concludes this paper and points out some promising future direction as well as the potential of our scheme on other applications. Fig. 1. Marker-based motion capture device records the movement of a person by tracking the markers wore on his or her joints. Each marker trajectory is a smooth curve in R 3 . For better visualization, we only plot the x coordinate. The left photo is taken from http://nward. com/ict/blender/mocap.htm II. PREVIOUS WORK Compared to the widely-studied video/image compression, mocap data compression is a relatively young field.
Liu et al. [1] partitioned a mocap data sequence into subsequences, and then applied the PCA to keyframes of each subsequence separately. Fitting fixed-length short mocap clips using Bézier curves, Arikan [6] performed clustered PCA to reduce their dimensionality. Observing that human motion often exhibits repeated patterns, Lin et al. [11] applied the PCA to the repeated motion and interpolated the marker trajectories. Tournier et al. [10] proposed a principal geodesic analysis (PGA)-based approach, which stores only some poses manifolds, the end-effectors as well as root joint's trajectories and orientations. The motion can be recovered through Inverse Kinematics (IK) in a lossy manner.
Beaudoin et al. [3] applied 1D DWT to joint angles, and the WT coefficients were optimally selected by taking the visual artifacts into account. This method was futher improved by Firouzmanesh et al. [21]. Preda and Preteux [15] adopted temporal prediction and spatial 1D DCT in MPEG-4 bone-based animation (BBA) to remove redundancy.
Using fuzzy clustering, Chew et al. [9] reorganized mocap data into matrices with strong local correlation, and then adopted the JPEG-2000 (employing 2D DWT) to encode them.
Chattopadhyay et al. [2] proposed a novel model-based indexing method, which exploits structural information derived from the skeletal virtual human model. Gu et al. [12] compressed human mocap data by hierarchical structure construction and motion pattern indexing. They also built a mocap database for each meaningful body part and a sequence of mocap data can be efficiently represented as a series of motion pattern indices. Taking advantage of the sparsity of mocap data in the action domain and time domain, Li et al. [8] proposed a learning-based scheme to train a set of shift-invariant basis functions, on which the mocap sequences can be projected, leading to sparse coefficients. Lim and Thalmann [4], Xiao et al. [5] and Kim et al. [7] proposed keyframe-based methods, which extract a few representative frames, and then represent the whole mocap sequence by interpolating these keyframes.
Zhu et al. [13] represented human motion data in the quaternion space so that human rotational motion data can be decomposed into the dictionary part and the sparse weight part. Le et al. [16] computed optimized marker layouts for capturing facial expression as optimization of characteristic control points from a set of high-resolution, ground truth facial mesh sequences. Hou et al. [22] proposed a tensor representation, in which mocap clips were assembled into a third-order tensor. They applied the canonical polyadic decomposition to explore correlation Instead of using the standard application-independent transformations, our transform coding method is tailored to mocap data by taking advantage of their unique properties (see Section 3). As a result, our method outperforms the existing techniques in terms of both speed and compression performance. Moreover, our method has good scalability so that it works for both a single motion sequence and a set of mocap sequences, i.e., mocap database.

III. HUMAN MOCAP DATA ANALYSIS
As pointed in [1], [6], [11], compressing the position-based mocap data has advantages over the hierarchical angle-based representation, which exhibits intrinsic nonlinearity. Besides, the hierarchical structure results in the accumulation of errors along the chain of joint angles, resulting in significant jerkiness [9]. Therefore, we use the position-based human mocap data in this paper. We represent a human mocap sequence by a matrix M ∈ R 3n×f , i.e., x n,1 x n,2 · · · x n,f y n,1 y n,2 · · · y n,f where n and f are the numbers of markers and frames, respectively. (x i,j , y i,j , z i,j ) is the coordinate of the i-th marker in the j-th frame.
A typical human motion sequence has strong intra-/inter-trajectory correlation and clip correlation. It also exhibits a strong local structure. Although some of the properties were also empirically observed in [1], [3], [6], [11], [17], we did not find quantitative verification in the literature. In this section, we provide concrete analysis to justify these properties.

A. Trajectory Correlation
Each trajectory exhibits coherence (i.e., intra-correlation) since the positions of markers usually vary smoothly in time. Also, inter-correlation exists among trajectories, due to the highly coordinated and structured nature of human motions.
To verify the intra-correlation, i.e., small variation or smoothness of each trajectory, we compute v = 1 3nf ∇M ⊺ 1 , where ∇ ∈ R (f −1)×f is first order difference matrix, ⊺ is matrix transpose, and · 1 is the sum of absolute value  of all elements. Using σ = 3n i=1 σ i as a reference, where σ i is the standard deviation of the i-th row of M, Table  I shows the smoothness measurement on several sequences. See Table II for details of the test sequences. One can clearly see that v ≪ σ, indicating the small variation within each trajectory.
To verify the inter-correlation, we apply SVD to M. As shown in Fig. 2(a), the normalized singular values approach zero quickly, which demonstrates the approximate low-rank nature of M. As a result, the rows of M are strongly dependent.

B. Local v.s. Global
Motion in a short period tends to be more correlated than in a long period, indicating that short clips have stronger inter-correlation than the whole sequence.
To verify the local property, we randomly extract several clips from a sequence. Each clip has F (≪ f ) frames and is represented by a matrix M ∈ R 3n×F . Then, we compare their normalized singular values with those of the big matrix M. Fig. 2(b) shows that the singular values of M approach to zero more rapidly than M, meaning that the clips have stronger inter-correlation than the whole sequence M.

C. Clip Correlation
Intuitive speaking, a long motion sequence (such as walking, jogging, etc) has repeated motions. Thus, one clip or several markers' trajectories can be obtained by blending others. Such a property is more obvious in large mocap database. Similar to [18], we verify the clip correlation by partitioning M into J non-overlapping clips 1 represent them as a three dimensional matrix M ∈ R 3n×f /J×J . A new matrix M ∈ R J×3nf /J is formed by unfolding the matrices M along the third dimension. We then factorize M by SVD. Fig. 3(a) shows that the normalized singular values of M of all test mocap data approach zero rapidly, indicating that mocap clips have strong correlation. We also perform the test on natural videos, in which a clip is one video frame. As shown in Fig. 3(b), the clip correlation in natural videos is not as strong as the mocap data.

A. Motivation
As mentioned above, a key issue of compressing mocap data is to reduce data correlation described in Section III-A, as much as possible. A straightforward method is to directly apply 2D transform coding to M. However, our analysis in Section III-B suggests that compressing subsequences separately is more effective than that of the sequence as a whole. Similar observation can be found in [1], [6], [9] and image/video compression, where blockbased transform is widely used. Moreover, processing each clip separately is obviously more memory efficient than that of the whole sequence. Inspired by these observations, we propose a clip-based algorithm for compressing mocap data, in which one mocap sequences is segmented into N clips, and the i-th clip is denoted by with L i stands for the length.
Within the transform coding framework, one needs to transform the input data into the transform domain, in which the transformed coefficients exhibit sparsity so that some smallest ones can be discarded with little information loss. A possible solution is to apply SVD to each M i and then keep the top k i important components, i.e., where U i ∈ R 3n×ki and V i ∈ R Li×ki are the k i eigenvectors of M i M ⊺ i and M ⊺ i M i , corresponding to the k i largest eigenvalues, respectively, and S i ∈ R ki×ki is a diagonal matrix. The SVD-based transform coding uses knowledge of the application to choose information to discard. However, since one has to store all the transformation matrices Alternatively, one may adopt some application-independent transformations, such as 2D DCT or DWT. Take 2D DCT as an example.
where D l ∈ R 3n×3n and D ri ∈ R Li×Li are the standard 1D DCT basis matrices, S i ∈ R 3n×Li are the transformed coefficients. Compared to the SVD-based transform coding, the DCT-based approach stores only the transformed matrices S i , i = 1, · · · , N . Owning to the locally smooth (or small variation) nature of images, the DCT works extremely well in 2D image and video compression.  However, as discussed above, the columns in mocap data are not smooth. Therefore, it does not make sense to apply the left transform D l to mocap data. Motivated by the above discussions and observations, to develop an effective compression method for mocap sequences, one must take knowledge of mocap data into account and also keep the number of transform matrices as small as possible. Towards this goal, we propose a novel mocap tailored transform coding method. As shown in Fig. 6, after segmentation, we compute the data-dependent transformation matrix B ∈ R 3n×k ,  which can reveal the geometric structure of columns of M i to lead correlation removal, where D ri ∈ R Li×li is the truncated 1D DCT transform matrix and S i ∈ R k×li is dense coefficients.
It is worth noting that our method is able to adopt a single data-dependent left transform due to the strong correlation among mocap clips described in Section III-C. Our mocap tailored transform coding stores only k 3n + N i=1 l i scalars in the transform domain, whereas the SVD-based method (see Eqn. (1)) requires

B. Mocap Tailored Transform Coding
Computing the data-tailored transform matrix B and coefficient matrices S i is formulated as a least-square problem: where · F is the Frobenius norm defined as X F = i j X 2 i,j , and I k ∈ R k×k is the identity matrix. To minimize (4), the partial deviation of (4) with respect to S i must be equal to zero. So we obtain S i must satisfy where Tr is for the trace of matrix, i.e., Tr(X) = i X i,i , we can rewrite the objective function as The last equation comes from the fact Tr(XY) = Tr(YX) for compatible matrices X and Y.
The first term in Eqn. (5) is a constant, which is independent of B. Therefore, the minimization problem in (4) is equivalent to the following maximization problem, i.e., The optimal solution of (6) is given in Theorem 1. Since the number of markers n is usually small (e.g., a few tens), the dominating term in the time complexity is Theorem 1 ( [19]): Given a symmetric matrix X of dimension p × p and an arbitrary orthogonal matrix Y of dimension p × q, the trace of Y T XY is maximized when Y contains the q eigenvectors of X, which correspond to the q (algebraically) largest eigenvalues.

C. Quantization and Entropy Coding
Since the compression quality highly depends on the accuracy of the orthogonal matrix B, we represent each element of B using 16 bits. For each element of S i , we quantize its fractional part with Q i bits per entry, where Q i is automatically determined by our algorithm (see Section VI-A). Then we adopt the lossless coding scheme to encode the bitstream. Note that other advanced lossless entropy coding schemes can also be applied. The decoder is a straightforward process that computes decompressed clip by B S i D ⊺ ri , where B and S i are the decoded matrices.

V. GENERALIZATION TO MOCAP DATABASE
The previous section presents our algorithm for compressing a single human motion sequence. In this section, we consider a general scenario of human mocap database, which may consist of a large amount of motion sequences recorded from multiple performers. Due to diversity, a single transformation matrix B may not work for all clips.
Therefore, it is natural to consider multiple transformation matrices to improve the compression result. We formulate the problem as computing K transform matrices B j , j = 1, · · · , K, so that all clips can be selectively projected on them with the least distortion where W i,j is the (i, j)-th entry of W indicating whether the i-th clip is represented in the space spanned by the j-th transform matrix B j . Obviously, Eqn. (4) is a special case of Eqn. (7) with K = 1.
Note that the optimization problem (7) is not easy to solve due to the two types of variables involved. In this paper, we propose a deterministic annealing based method [20] that iteratively solves only one variable (B j or W ij ) at a time. In each iteration, we first update S i,j with other variables fixed Then we update W i,j using the centroid equation, where t is the temperature. By cooling the temperature slowly, the global optimal solution is obtained [20]. Next, and solve its eigensystem using SVD. Finally, we form matrix B j by taking C j 's k eigenvectors associated with the largest k eigenvalues. We repeat the above procedures until convergence, i.e., the change of matrices B j and W is less than a small tolerance . The above deterministic simulated annealing method is guaranteed to converge [20].
Computational results show that it usually converges in less than 30 iterations given a tolerance of 10 −6 .

A. Parameter Setting
The performance of our algorithm depends on the clip lengths L i , i = 1, 2, · · · , N , which are specified by either the user or a motion segmentation algorithm, and three parameters, i.e., k, l i , and Q i , which are determined by our algorithm automatically. For database, the user also specifies the number of transform matrices K.
and W Initialization: initialize B j with random orthogonal bases and D ri with DCT bases; set W i,j = 1/K and t > 0.
end for 6: for j ← 1 : K do 7: compute W i,j using (9) 8: end for 9: end for 10: for j ← 1 : K do 11: compute C j using (10) 12: B j ← C j 's k eigenvectors associated with the k largest eigenvalues 13: end for 14: t ← t 2 15: until convergence Throughout this paper, the compression ratio (CR) is defined as the ratio of the original data size to the compressed data size. We measure the distortion using average Euclidian distance (in cm), i.e., where p i,j = [x i,j y i,j z i,j ] and p i,j = [ x i,j y i,j z i,j ] are original and decompressed 3D coordinates of the i-th marker in the j-th frame, respectively.
Here, we show how the parameters k, l i , and Q i are automatically set in our scheme. To simplify the analysis, we simply take all clips equally, i.e., L i ≡ L, l i ≡ l and Q i ≡ Q for all i. The parameters k and l specify the number of retained important coefficients in transform coding. Taking more coefficients in the direction with weaker correlation can effectively reduce the distortion and improve the compression performance. The degree of correlation within each row of M i depends on the clip lengths, and computational results show that the ratio r = l/k that leads to the least distortion is linearly proportional to clip length L and we adopt the following empirical formula: where ⌈·⌉ is the ceiling function. See Fig. 7.
The quantization parameter Q determines the size of the fractional parts of the transformed coefficients. Increasing Q leads to more accurate results, but it reduces the compression ratio. Fig. 8 shows that smaller Q produces better results at high CRs and larger Q is preferred at low CRs. In our implementation, we adopt the following empirical formula:

B. Results
We implement our algorithm in MATLAB and evaluate its performance and quality on the CMU Mocap Database [35]. Table II shows the details of the test data. We use the MATLAB toolbox [36] to decode the .asf/.amc into 3-D marker coordinates, which are stored as 32-bit floating-points.
We test our method under two scenarios, i.e., equal segmentation and adaptive segmentation. Various CRs are obtained by changing the parameter k.

1) Equal segmentation:
In this scenario, we segment mocap data into clips with equal length, i.e., L 1 = L 2 = · · · = L N = L. Equal segmentation is easy to implement and it is often used when L is specified by the user, since it is tedious for the user to specify the length for each clip separately.
First, we test our method on mocap sequences by setting various Ls. We observe that increasing L can improve the compression performance, but the improvement becomes less significant when L ≥ 350. As Figs. 9 and 10 show, the distortion is less than 1cm when CR≥ 100. See also the accompanying video for more results.
Then, we apply our method to mocap databases. We specify one more parameter K for the number of transform matrices. Intuitively, the more the data-dependent transform matrices, the less the distortion. However, since the orthogonal matrices B i are difficult to compress, more spaces are required to store them, which reduces the compression ratio. Fig. 9 shows that we achieve the optimal compression performance for database 1 and database 2 when K is equal to 4 and 3, respectively. Table III shows the performance statistics of our method. Our unoptimized and serial MATLAB code is able to encode more than 10,000 frames per second for a single mocap sequence. It can also encode 2,000 fps for mocap databases. The decoding speed is even faster than encoding. It is worth noting that our method can be further sped up by parallel computation. For example, computing S i can be implemented in parallel on the GPUs.
To demonstrate the robustness of our method, we also test our method on sequences with low frame rates, which have weaker data correlation than the ones at full frame rates. Given the original sequences with 120 fps, we uniformly downsampled them to 60 fps. Correspondingly, their data size and number of frames halved. As Fig. 11 shows, our method still works very well, i.e., under the same distortion, the CRs is approximate 50% of those in Fig. 9. We also observe that the optimal range L ∈ [150, 200] is approximately half of the one in Fig. 9.
2) Adaptive segmentation: When advanced motion analysis tool (e.g., [25], [23], [24], [28]) is available, one can segment the input data to clips of physically meaningful actions, which have stronger correlation than fixed-length clips. In our implementation, we adopt the probabilistic principal component analysis (PPCA)-based segmentation algorithm [25] for its simplicity and effectiveness, in which a cut is made when the distribution of human poses changes. Other advanced and complicated motion segmentation algorithms, e.g., [23] and [28], can also be employed.
The parameters of the i-th clip, i.e., l i and Q i , are obtained by Eqns. (12) and (13)      L i . We also set various numbers of clips during the segmentation to investigate how it affects the compression performance. As shown in Fig. 12, the optimal number of clips (or segments) depend on the motion characteristics.
For example, the sequence 69 08 contains only walking and turning, so a small number of clips works well. In contrast, the sequences 56 07 and 86 05 contain complicated motions, such as climbing punching. As a result, a large number of clips produces smaller distortion. As expected, at relatively high CRs, adaptive segmentation can achieve higher compression performance than equal segmentation.

C. Comparison
We compare our method with several state-of-the-art techniques [6], [10], [11], [12], [13] in terms of compression performance and efficiency. The results of [6], [10], and [11] are taken from [11], and the results of [12] and [13] are taken from [13]. Note that only results with a single compression ratio were provided in both [11] and [13]. For fair comparison, our scheme is performed under the equal segmentation scenario. Fig. 13 shows our CR-distortion curves on some test sequences and mocap databases. We observe that our CR-distortion curves are consistently below the other methods, indicating that our method outperforms them in terms of compression performance. Table IV shows that our method is also much more efficient than the existing methods. Ours Method in [6] Method in [10] Method in [11] (a) Sequence 15 04 Ours Method in [6] Method in [10] Method in [11] (b) Sequence 17 08 Ours Method in [6] Method in [10] Method in [11] (c) Sequence 17 10 Ours Method in [6] Method in [10] Method in [11] (d) Sequence 85 12 Ours Method in [11] Method in [6] (e) database 3 Ours Method in [12] Method in [13] Method in [6] (f) database 4 (c) and (d), the results of [6], [10], [11] are taken from [11], where only a single CR was provided. For database 3, K = 4 and the results of [11] and [6] are taken from [11]. For database 4, K = 3 and the results of [6], [12] and [13] are taken from [13].

D. Limitation
The high compression performance of our method comes by significantly exploring the temporal correlation, that is, it requires the entire sequence or at least a sequence of sufficiently long period to compute the left transform matrix using Eq. (4). This will cause the latency problem, which also occurs in other approaches, e.g., [1], [6], [9], [21], [11]. Thus, it is not suitable for applications where data acquisition and compression have to be done simultaneously or within a very small time interval.

VII. CONCLUSION AND DISCUSSION
This paper has presented a mocap-tailored transform coding for compressing human mocap data. Our method is highly effective in that it takes advantage of the features of mocap data. Furthermore, it has low computational cost and can be easily extended to compress mocap databases. Unlike existing approaches, it requires neither training nor complicated parameter setting. Experimental results demonstrate that the proposed scheme significantly outperforms state-of-the-art algorithms in terms of compression performance and speed.
Owning to its high performance, we believe our method has potential to many mocap applications, such as retrieval [26], [27], [29], [30], where the clip dimensionality can be significantly reduced without comprising data quality, leading to low computational complexity. Besides mocap data, our method can be extended for compressing dynamic meshes [31], [32], in which each vertex is considered as a marker.
Our method can also inspire interesting future work. 1) We observed that the compression performance depends on the compressed transform matrices. Therefore, advanced matrix compression algorithms, e.g., sparse and redundancy representation, can improve our results.
2) Perception-based compression schemes [33], [34] have proven to be effective to natural images and videos, since they are adaptive to human vision system. It would be interesting to investigate the perceived-based methods for mocap data compression. For example, optimally allocating bits to clips guided by a perceptual distortion metric, that is, clips which can be significantly compressed with little perceptual distortion should be assigned fewer bits, and vice versa, so that the overall compression performance is higher.
3) In our implementation, we focus on human motion capture data. It is also interesting to check its performance on other types of mocap data, e.g., facial expressions.

4)
A possible solution to solve the latency problem is to apply machine learning techniques to pre-compute some left transform matrices from learning datasets. As a result, the compression can be carried out whenever a clip with small length is available. 5) Last but not least, it is desirable to develop a fully automatic algorithm for determining the optimal (or nearoptimal) parameter, i.e., the clip lengths for equal segmentation and the number of clips for adaptive segmentation.

ACKNOWLEDGMENTS
The test data is courtesy of the CMU Motion Capture Database [35].