基于时空分割的三维动画压缩

熊小勇 谢文强 张韧博 郭 斌 王文乐* 吴少智

1(江西师范大学软件学院 江西 南昌 330022)2(电子科技大学计算机科学与工程学院 四川 成都 611731)

0 引 言

随着动画制作技术的发展，基于三维动画数据的应用规模不断增长，三维动画数据也已成为虚拟现实技术应用于教育、数字娱乐等领域的主要数据媒介之一[1-3]。与此同时，对三维动画数据的分析和处理技术的需求也不断增长。然而，由于三维动画通常具有较大的规模，现有的三维动画特征描述方式有限，使得处理三维动画依旧是计算机图形学领域研究热点课题之一[4]。为实现高效的三维动画分析、传输、存储等操作，设计一种有效的三维动画压缩算法显得尤为重要。

近年，众多研究工作专注于三维动画压缩课题。主要概括起来有三类，包括基于空域[5-7]、基于时域[8-9]和基于时空一致性[10-12]。基于空域的方法在顶点轨迹上应用主成分分析算法PCA[13-14]。如：文献[5]中提供了一种聚类主成分分析算法，该算法可以将相似轨迹的顶点聚类，并且对于每一个分组都独立运用主成分分析算法进行维度约简，从而实现压缩。与空域方法相比，文献[8]提供了一种将具有相同姿态的动画帧聚类并分别对每一个分类都运用主成分分析算法进行维度降解的压缩方法。这两种方法各有优劣：时域类方法对于点轨迹同步好的动画数据压缩效果更佳，而空域类方法对于重复性动作多的动画数据压缩效果更佳。就时空一致性而言，文献[5]表述了一种时空混合预测模型用于预测顶点在压缩后的位置。文献[15]在近期提出了一种基于有效性分割的时空一致性模型，进而对于每一个基于分割有效值的时空一致性都有大的变形幅度。文献[17]中，运用分割方法来实现运动估计，取得了较好的压缩表现。文献[18]实现了移动的人体序列有效压缩。

基于该联合时-空域的跨域分割结果，本文进一步提出一种新的基于三维模型的动态行为计算跨域时空分割算法，实现区分三维模型的刚性分割和动态时空域分割。在此三维模型的刚性分割和动态时空域分割的基础上，借助经典的主成分分析算法分别实现对刚性区域和动态分割区域的压缩，获得更好的压缩结果。在此基础上，本文进一步提出了运用维度划分，分别划分三维动画各个维度的数据后，再在各维度数据上分别运用本文提出的压缩算法，以进一步提升压缩效果。

1 主成分分析与三维动画时空分割算法

1.1 主成分分析算法

假设一个有m个n维数据的样本矩阵X:

X=[x1,x2,…,xn]∈Rm×n

(1)

主成分分析算法原理简述如下[7]:

(2)

式中：

(3)

为矩阵X的矩阵均值；

(4)

为矩阵X中每一列的均值。

第二步:计算协方差矩阵C，即:

(5)

第三步:计算矩阵C的特征值D和特征向量V，其中，D∈Rm×m为对角矩阵其对角元素为矩阵C的特征值，V=[v1,v2,…,vm]∈Rm×n为特征值所对应的特征矩阵，vi表示第i特征值所对应的特征向量。

第四步:将特征向量根据特征值降序排序，得到前k个最大特征值所对应的特征向量v1,v2,…,vi:

B=[v1,v2,…,vk]

(6)

第五步:计算原始数据X的降维表示，即如下:

Y=X×B

(7)

式中：

Y=[y1,y2,…,yn]∈Rk×n

(8)

为矩阵X的低维主成分表示。

为充分发掘主成分分析算法在三维动画数据压缩方面的应用潜能，本文将探讨主成分分析算法与三维动画时空分割算法的多种结合方式，并应用于数据压缩进行算法性能评估。

1.2 三维动画的时空分割

首先，对于给定一个三维动画M，其由t帧动画矩阵(f1,f2,…,ft)组成，这些动画矩阵都是由个三角形和个顶点矩阵组成。然后，可以将这些由三角形和顶点组成的动画帧矩阵转化为纯顶点矩阵。每一帧的纯顶点矩阵在时空可以表示为一个m×n的矩阵，我们可以将不同时间上的动画帧以列为标准合并在一个矩阵里，由此，可以将t个由三角形与顶点组成的动画帧矩阵集合转换成为了(m×(n×t))的顶点矩阵D。

进一步，通过对顶点矩阵D，运用主成分分析算法，来对三维动画矩阵进行压缩，如图1所示。文献[8]中的实验结果表明该方法对三维矩阵进行有效压缩。

图1 基于时空一致性的三维动画压缩算法流程

然而，由于三维动画区域在时间和一定范围内的空间内广泛存在一致性，这些区域称为刚性区域，如图2黑色区域。而体现三维动画运动属性在时空上的不一致性集中在一个很小的范围内，称为动态区域，如图2灰色区域所示。值得注意的是，文献[8]直接对三维动画顶点矩阵进行PCA算法处理的方法并没有考虑到刚性区域和动态区域区别。由于大量离散的数据存在，对整个三维动画区域进行处理将导致PCA算法的效果不佳。与此同时，这些离散的数据不仅存在于动态区域同时还存在不同维度的刚性区域上，而且在相同维度上，数据相对集中的，不同维度的数据相对离散，可能会影响主成分分析算法的效果。

图2 三维动画中刚性区域(黑色区域)和动态区域(灰色区域)示意图

2 基于时空分割的三维动画压缩算法

针对以上基于时空一致性的三维动画压缩算法的不足，本文设计出了一种基于跨域时空分割的三维动画压缩算法。在本文提出的算法中，对于动画矩阵，先通过算法处理成为纯顶点矩阵。同时，通过文献[8]描述的算法，获取三维动画数据中的动态区域集，称之为动态分割块。从而得到了动态分割块集合和刚性区域。对于刚性区域，仍采用主成分分析算法处理，而对于动态分割块，将采用不同的方法处理。本文方法的流程如图3所示。

图3 基于跨域时空分割的三维动画压缩算法流程

同时，为了降低不同维度数据的离散性对主成分分析算法的影响，本文进一步提出基于维度划分的时空分割三维动画压缩算法。基于维度划分的三维动画压缩算进一步对刚性区域，进行维度分割，将空间三个不同维度的数据，分别组成三个对应的时空分割矩阵。然后，对这三个不同的矩阵，分别运用主成分分析算法处理。而动态分割块，可以采用主成分分析算法压缩，也可以采用其他方法处理，如图4所示。

图4 基于维度划分的时空分割三维动画压缩算法

2.1 顶点矩阵的构建

首先，将三维动画数据中的每一帧的三角形与顶点矩阵集合转化为纯顶点矩阵，记为vi。然后，根据三维动画帧在空间上的一致性，将动画帧拼接为矩阵V=(v1,v2,v3)。由此，可以计算本文压缩方法的基础矩阵，记为:

RS=(v1,v2,…,vm)=

(9)

式中:

(10)

2.2 动态分割块的构建

图5为顶点矩阵示意图，其中，横坐标“时域”表示时间维度，纵坐标“空域”表示单个三维模型中的空间关系；灰色方块表示动画帧数据，p1、p2、p3、p4分别表示对应的时空分割块。基于动画跨域分割算法，可以分析出动态分割块在基础矩阵RS对应的位置，记为StSi，矩阵StSi为基础矩阵RS的子矩阵，如图5中的白色分块。StSi在时间上是跨域的。StSi可以是在一个动画帧之中，如图5中p1、p4分块；StSi可以跨域多个动画帧，如图5中的p2、p3分块；StSi也可能不满一个动画帧，如图5中的p4分块。

图5 顶点矩阵示意图

2.3 刚性区域的顶点矩阵构造

刚性区域的构造，需要在三维动画的顶点矩阵RS中查找到动态分割块顶点矩阵StSi对应的分块，并使这些分块的元素替换为一些更一致的值。由此，获取了刚性区域的顶点矩阵，记为RS′。有：

(11)

(1) 动态分割块的判定标准 对于这个将静止区域和活动分割块分开处理的方法，实现的基础是，要判断哪些数据是需要分割的。通常，与矩阵的整体相差比较大的就是活动分割块的数据。那么，有一个重要的因素就是，用何种标准确定为活动分割块。在这里，这个标准为一个考量动态或静态(刚性)的阈值τ，当数据区别达到了这个阈值就可以确定为活动分割块。由于动态分割块的动态特征明显，与刚性模块的分界区域狭窄，所以在确保正确判断分割区域的前提下，阈值的选择对于动态区域的大小影响较小，从而使得对基于时空分割的压缩效果影响有限。

(2) 数据填补 由于对三维动画动态分割进行分别的压缩操作之后，对剩余的整体刚性模块需要进行压缩计算。为填补去除的动态区域，依据动态PCA算法原理，数据的一致性越高，其主成分维度越低，也即达到更高的压缩效率。据此，本文方法考虑对去除的动态区域回填所有剩余刚性区域的均值，即:

(12)

(13)

(14)

(15)

3 仿真结果与分析

为便于对本文提出的三维动画压缩方法进行评估，本文选择基于表一所列数据(如图6所示)开展仿真实验。由左至右分别是“女人”、“表情动画1”、“表情动画2”、“骆驼”、“猩猩”、“马”、“男人”。

图6 仿真实验数据集

动画名称顶点数面片数帧数“女人”43068590278“表情动画1”60811711473“表情动画2”66212721064“骆驼”218874381448“猩猩”150062999954“马”84311684348“男人”150072999954

根据2.3节中的论述，在获取稳定的时空分割结果的基础上，本文设定阈值τ=0.7。基于此，本文对表1数据分别开展以下四项仿真实验:

(方法1) 直接应用PCA于输入动画。

(方法2) 基于时空分割，分别对动态分割和刚性分割应用PCA进行压缩。

(方法3) 基于时空分割，区分三个维度地应用PCA分别对动态分割和刚性分割进行压缩。

为便于对仿真结果进行评估，引入压缩比和误差两个因素。其中压缩比为压缩前后数据存储位数比例，即：

(16)

式中:ni表示第i个分割(含动态分割和刚性分割)中顶点个数，di表示压缩保留的主成分个数。可见，压缩比越低，压缩效果更佳。

误差评估采用经典的KGError[15]，即:

(17)

对表1中的动画数据分别进行上述四组仿真实验，结果如图7、图8和图9所示。

图7 “表情动画2”仿真结果

图8 “表情动画1”(左)与“女人”(右)仿真结果

图9 “骆驼”(左上)、“猩猩”(右上)、“马”(左下)与“男人”(右下)仿真结果

首先，由图7可见，随着压缩后使用的主成分维度的增加，压缩比逐渐升高。但由于PCA算法的低维度(排列最前的几个主成分)已经保留了极高的原始信息，使得增加压缩使用的主成分维度并不能显著降低总误差。同样的规律在其他的六个仿真实验中也成立。

其次，两个“表情动画”的长度均远远大于“女人”动画，而方法2、方法3较方法1应用于长序动画均得到更低的压缩误差。这是因为动画序列越长，动态冗余信息量更大，对提取的动态分割提取并进行压缩得到更佳压缩效果，充分体现了本文提出的压缩方法的可行性。

第三，由“骆驼”、“猩猩”、“马”和“女人”这四个仿真实验的结果可以发现方法2在压缩比较低时误差较方法3更低，但是在压缩比高时误差较方法3 更高。这是由于方法3高压缩比的情况下，空间数据各个维度独立进行压缩将得到充分的主成分维度需求，从而在各个维度的还原效果均佳，也使得误差更低；反之，低压缩比的情况下，方法3的误差率更高。

4 结 语

综合以上对三维动画的压缩算法设计、实施与分析，实现了基于跨域时空分割和基于维度划分对三维动画压缩算法的效果评估。实验结果表明，对于基于时空分割的压缩算法，无论是基于跨域时空分割还是基于维度划分的时空压缩算法，在应用于长序列动画时都取得了比直接对三维动画数据运用主成分分析算法更好的效果。尽管两种新的方法在应用于短序列动画时表现欠佳，但长序列数据在现实世界更具有普遍意义。

对于基于跨域时空分割和基于维度划分的时空分割这两种时空分割压缩算法，实验结果表明，基于跨域时空分割的算法在低压缩比的情况下略微优于基于维度划分的时空压缩算法。而这两种不同的基于时空分割的压缩算法，都较明显地优于直接运用主成分分析的算法。两种方法可基于不同应用场景，按需择优。

参考文献

[1] 商柳,冯笑冰,朱登明,等.一种骨架驱动的近岸涌浪动画合成方法[J].软件学报，2016，27(10):2600-2611.

[2] 王鹏杰,潘志庚,李威.人体运动捕获数据压缩技术研究进展[J].计算机辅助设计与图形学学报,2016,28(7):1037-1046.

[3] 陆焱,惠巧娟.改进的统计模型三维人脸特征点标定算法框架[J].计算机工程与应用,2016,52(24):166-170.

[4] Li H, Liu X, Cai Q, et al. 3D Objects Feature Extraction and Its Applications: A Survey[M]// Transactions on Edutainment XI. Springer Berlin Heidelberg. 2015: 3-18.

[5] Sattler M, Sarlette R, Klein R. Simple and efficient compression of animation sequences[C]// Proceedings of the 2005 ACM SIGGRAPH Eurographics symposium on Computer animation. ACM, 2005: 209-217.

[6] Karni Z, Gotsman C. Compression of soft-body animation sequences[J].Computers & Graphics, 2004, 28(1): 25-34.

[8] Luo G, Cordier F, Seo H. Compression of 3D mesh sequences by temporal segmentation[J]. Computer Animation and Virtual Worlds, 2013, 24(3-4): 365-375.

[9] 沈晴,班晓娟,常征,等.基于视频的人机交互中动作在线发现与时域分割[J].计算机学报,2015,38(12):2477-2487.

[10] Ibarria L, Rossignac J. Dynapack:space-time compression of the 3D animations of triangle meshes with fixed connectivity[C]// Proceedings of the 2003 ACM SIGGRAPH Eurographics symposium on Computer animation. Eurographics Association, 2003: 126-135.

[11] Stefanoski N, Ostermann J. Connectivity-guided predictive compression of dynamic 3d meshes[C]// Image Processing, 2006 IEEE International Conference on. IEEE, 2006: 2973-2976.

[12] 张杰,吴剑章,汤嘉立,等.基于时空图像分割和交互区域检测的人体动作识别方法[J].计算机应用研究,2017,34(1):302-305.

[13] Jolliffe I. Principal component analysis[M]. John Wiley & Sons, Ltd, 2002.

[14] 阮越,陈汉武,刘志昊,等.量子主成分分析算法[J].计算机学报,2014,37(3):666-676.

[15] Luo G, Cordier F, Seo H. Similarity of deforming meshes based on spatio-temporal segmentation[C]// Proceedings of the 7th Eurographics Workshop on 3D Object Retrieval, Eurographics Association, 2014: 77-84.

[16] Karni Z, Gotsman C. Compression of soft-body animation sequences[J]. Computers & Graphics, 2004, 28(1): 25-34.

[17] Hachani M, Zaid A O, Puech W. Segmentation-based compression scheme for 3D animated models[J]. Signal Image & Video Processing, 2016, 10(6):1-8.

[18] Nguyen H Q, Chou P A, Chen Y. Compression of human body sequences using graph Wavelet Filter Banks[C]// IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 2014:6152-6156.