基于数据结构化的三维动画压缩方法研究

罗国亮，王 贺，赵 昕，曹义亲，黄晓生，邬昌兴，冼楚华

基于数据结构化的三维动画压缩方法研究

罗国亮1，王 贺1，赵 昕1，曹义亲1，黄晓生1，邬昌兴1，冼楚华2

(1. 华东交通大学软件学院，江西 南昌 330013； 2.华南理工大学计算机科学与工程学院，广东 广州 510641)

在三维动画应用日益广泛的背景下，研究三维动画数据压缩方法对其数据的存储、传播和渲染技术至关重要。基于图像数据的结构化特征，计算机视觉领域提出了一系列高效图像压缩技术。鉴于三维动画数据与图像数据结构的差异，探讨三维动画数据结构化方法，进而探索改进图像算法以实现一种新的三维动画数据压缩方法。具体而言，首先研究对三维模型顶点序列进行优化调整；进而基于图像压缩算法的模块研究动画数据的子块尺寸优化以及图像压缩算法量化矩阵优化方法；最后，通过采用不同类型动画数据进行测试，实验结果表明优化图像压缩算法在压缩比和时效均得到有效提升和保障。

压缩；三维动画；图像压缩算法；聚类；离散卷积变换系数

伴随着网络通信技术的发展，流媒体的广泛应用催生了众多新技术兴起。其中，决定了多媒体传播、存储效率的压缩技术是学者们长期关注的研究方向。目前，人们熟知的图像压缩方法包括JPEG，PNG，BMP，AVI和MPEG等。其中，有损的JPEG方法及其衍生的JPEG2000(可选无损)方法具有极高的运算效率，是当前使用最广泛的图像压缩方法之一。

近年来，虚拟现实技术发展方兴未艾，“工业4.0”同样成为国内外热门产业化方向。作为这些未来技术的共同数据基础，三维模型是相关产业发展不可或缺的重点，相关产业迅速崛起，随之而来的是针对三维模型数据高效处理技术的迫切需求。其中，三维压缩技术是涉及海量三维模型数据存储、传输的核心技术之一。然而，三维模型不同于传统的图像数据，不具备图像数据的矩阵存储几何结构，且对噪音极其敏感，也使得传统的图像压缩技术将不能直接应用于三维数据。

本文提出对传统图像压缩算法的改进方法和基于改进图像压缩算法的三维动画数据压缩框架，使图像压缩算法适应于三维数据，以实现对三维动画数据的高效压缩。

本文首先将图像压缩算法应用于三维动画数据，接着探索算法中各参数在三维动画数据上的表现，针对三维动画数据与二维图像数据的差别，对传统算法进行调整，在数据层面提出了对顶点顺序的调整方法，在算法层面通过改变输入DCT变换的分割子块大小以及量化矩阵的数据分布，兼顾时间效应，实现更好的压缩效果。

1 相关工作

自从1992年静止图像压缩(joint photographic experts group，JPEG)标准提出以来[1]，JPEG2000也应运而生[2-3]，其作为一个成熟的解决方案，在多媒体的传输、存储及其应用技术发展等方面做出重要贡献。JPEG算法也在图像质量评估方法、图像取证、产权保护、信息隐藏等领域起到关键作用。WANG等[4]提出了基于JPEG有损压缩误差的可视化实现图像质量评估的方法。LUO等[5]也通过类似的方法实现了图像取证的应用验证，这在当前天网高度密集部署情况下，图像的司法合理性论证具有现实意义。基于JPEG的信息隐藏也得到了广泛的研究[6-12]。文献[6]在2004年提出了基于特征提取的图像信息隐藏方法框架。随后，PEVNY和FRIDRICH[7]融合马尔科夫及离散卷积变换提出了多类的信息隐藏方法。而后人也在图像尺度等方向对信息隐藏方法提出了多种性能优化方案[8-10]，并进一步研究了可逆的信息隐藏方法[11-12]。近年来，随着深度网络方法及硬件计算性能的同步提升，学者们基于JPEG算法融合高性能深度网络方法，研发了一系列新的视觉应用。例如，在图像压缩领域，TODERICI等[13]联合回归神经网络提出了高性能的图像压缩方法。RIPPEL和BOURDEV[14]提出的自适应实时图像压缩方法对当前主流的直播等应用至关重要。REN和SHAKHNAROVICH[15]基于级联区域聚集的图像分割方法，对图像进行分层分割，其可应用于三维网格。最后，学者们提出的双JPEG算法通过不同的2个量化矩阵对图像进行2次压缩操作，通过观察离散卷积变换的双峰统计特性实现更丰富的图像特征提取[16]。

随着显示技术和数据捕捉方法的优化，三维数据得到了广泛应用。由于三维数据尺度大且容错性差等特点，三维数据压缩方法在近二十多年一直备受关注[17-18]。文献[17]对届时的压缩算法进行了系统梳理及性能评估。

JPEG算法的核心是离散余弦变换(discrete cosine transform，DCT)，以其为代表的频谱变换也经常出现在对三维模型的压缩中，如离散傅里叶变换、图傅里叶变换、小波变换等。三维模型根据结构差异，可分为网格模型和点云模型[19]。网格模型不仅包括空间点坐标数据，也包含了点间拓扑信息。针对网格模型的压缩，文献[20-21]提出了基于谱分析的压缩方法。KHODAKOVSKY等[22]提出了基于小波变换的渐进几何压缩算法(progressive geometry compression，PGC)。LEE等[23]则提出了综合压缩比和压缩质量的三维模型渐进式压缩方法，该方法对于基于网络传输的数据显示意义显著。YANG等[24]基于图傅里叶变换和多级树集合分裂算法对网格序列进行簇内压缩的方法。点云数据作为最自然和普遍的三维模型数据，针对该数据的压缩方法论述更为广泛[25-31]。学者们提出了一系列的压缩方法探索，包括经典的八叉树法[25]、图形自适应变换方法[26]、几何变形评估[27]和动作补偿[28]等方法。同时也对点云的属性开展了基于图形变换压缩方法研究[29-30]，以及点云模型的高性能实时压缩方法研究[31]。

2 JPEG的三维动画压缩应用

2.1 标准JPEG压缩算法

首先，将图像从RGB颜色空间转换为YCrCb颜色空间，对，和3个分量进行采样后分别存放到3张表中。然后将表分割成8×8的子块，对每个子块单独进行DCT变换，得到DCT系数矩阵，并对其进行量化。最后采用Huffman编码对量化结果进行熵编码[2]。

2.2 三维动画中运用JPEG压缩算法

使用JPEG算法压缩二维图像数据，可以获得很好的压缩效果。但鉴于三维动画数据和规则二维图像数据的结构性差异，这一优秀算法并不能直接使用在三维动画的压缩中。经过数据变换，本文借鉴标准的JPEG压缩算法，将其运用到三维动画压缩中。

首先，本文将三维动画的时间和空间对应图像的长度和宽度。然后，将其每个顶点的三维坐标(,,)对应图像每个像素点的3个颜色通道(,,)，如图1所示。

基于以上对应关系，本文将三维动画的顶点集当作图像的像素集进行JPEG压缩，并针对三维动画数据的特点，无需进行颜色模式转换及采样，具体流程如下：

(2) 对每个子块B进行DCT变换，得到DCT系数矩阵，将(0,0)称为DC系数，其余63个称为AC系数。变换公式为

其中

(3) 对DCT系数矩阵进行量化，将中每一个DCT系数除以量化表中对应位置的量化值并进行取整，得到量化后的DCT系数矩阵，即

(4) 使用JPEG标准推荐的哈夫曼表对量化后的DCT系数矩阵进行熵编码，其中，对DC系数和AC系数使用不同的哈夫曼表进行编码，得到压缩后的数据_。

压缩流程如图2所示。

图2 三维动画中运用的JPEG压缩流程图

3 三维动画数据结构化及压缩方法

3.1 基于eK-Means聚类算法的三维动画数据结构化

在对每个子块B进行DCT变换时，B中数据之间值差别越小，DCT系数矩阵的值越向左上角集中，右下角越多的值为零或接近零，在进行熵编码时可以更好的达到数据压缩的目的。

然而三维动画中每一帧的顶点排列顺序是没有规律的，即顶点集中列数据间的值差别是不可预料的。为了使列数据间的值差别尽量小，在进行压缩之前需要对顶点集的列数据进行重排序。本文拟使用聚类算法来达到这一目的。为匹配具有高性能的JPEG算法，本文使用了等簇大小的K-means算法，即eK-Means算法，对顶点集进行聚类。

虽然eK-Means算法会受到初始聚类中心和离群点的影响，导致结果不稳定，并且容易收敛到局部最优解，但是三维动画数据在时间和空间上均具有平滑性，使得这些缺陷对结果的影响很小。同时，算法中初始聚类中心随机选择，仅当所有初始点均在模型边界点，如均在马尾的尾端时，才会对结果造成影响，而这种情况很少。基于以上考虑，使用eK-Means算法进行顶点集聚类的结果具有可靠性。

计算聚类中心时可以采取2种策略：①使用对顶点集的第一列数据1聚类后的结果对进行重排序；②计算所有列的聚类中心后取平均值得到聚类结果。相对策略①，策略②需要取得所有帧数据后才能进行压缩，且只能进行离线压缩。为达到实时压缩的目的，本文使用策略①进行顶点集重排序，具体步骤如下：

步骤3.计算每个类的均值，作为新的聚类中心，即令=。

步骤4.依据式(4)判断是否收敛，收敛或达到最大迭代次数则结束聚类，否则重复进行步骤2和步骤3。

总体流程如图3所示。

图3 基于eK-Means聚类算法的三维动画数据重排序

Fig. 3 3D animation data reordering based on eK-Means clustering algorithm

本文将使用上述算法得到的个类合并为一个数组，作为索引值序列，使用对进行重新排序，得到新的顶点集_，即_new=V(i)。

3.2 结构尺寸及DCT系数矩阵扩大倍数的改变

针对DCT变换能量集中的特性，DCT系数矩阵左上角存储着变换前子块B的主要数据，尺寸越大存储主要数据所需的存储空间越小，因为与B尺寸相等，本文将B尺寸设置为×，同时修改量化表，并按图4所示的3种方式生成尺寸为×的量化表。

三维动画数据大多是浮点数，所需精度很高，而经过量化之后变成了整型数据，在进行数据还原时会损失浮点部分，导致三维动画产生形变。本文在数据扩大倍之后进行量化，使数据的浮点部分得到一定程度保留，以减少数据的损失，计算公式为

[b1]

反量化公式为

其中，(,)为还原后的DCT系数矩阵。

4 实验和讨论

4.1 样本数据简介

本文使用“Cloth”，“Chicken”，“Horse”，“Michael”等三维动画数据进行测试(表1)。

4.2 实验

针对本文提出的优化压缩模型，给出以下几个评估实验结果：

(1) 不同量化表数值变化方式(线性/抛物线/指数)对压缩效果的影响。实验结果展示不同量化表数值变化方式对数据的压缩效果，同时进行了不同子块尺寸的实验，说明在不同子块尺寸下，量化表数值变化方式对数据压缩的影响趋势均保持一致，如图5所示。

(2) 子块尺寸对压缩效果的影响。实验结果展示不同子块尺寸对数据的压缩效果及耗费时间，量化表的设置方式为线性，说明不同子块尺寸对数据压缩的影响趋势基本保持一致，如图6所示。

表1 三维动画模型数据

图5 3种量化表设置方式对数据的压缩性能影响评估((a) Cloth数据，子块尺寸为8×8；(b) Cloth数据，子块尺寸为16×16；(c) Chicken数据，子块尺寸为8×8；(d) Chicken数据，子块尺寸为16×16；(e) Horse数据，子块尺寸为8×8；(f) Horse数据，子块尺寸为16×16；(g) Michael数据，子块尺寸为8×8；(h) Michael数据，子块尺寸为16×16)

图6 子块尺寸对数据的压缩性能影响评估，量化表采用linear设置((a) Cloth，压缩效果；(b) Cloth，压缩时间； (c) Chicken，压缩效果；(d) Chicken，压缩时间；(e) Horse，压缩效果；(f) Horse，压缩时间； (g) Michael，压缩效果；(h) Michael，压缩时间)

(3) 与标准JPEG算法及Cascaded比较。上述实验兼顾了时间效率，选取子块大小为32，量化表的设置方式为线性，同时采用顶点重排的方式。对比使用如3.2节所述未经优化的JPEG算法流程以及Cascaded[15]进行压缩，优化后的JPEG算法在Horse上的表现如图7所示。

图7 优化JPEG算法针对horse的压缩性能评估，子块尺寸为32×32，量化表采用linear设置

4.3 实验评价

(1) 量化表对压缩效果的影响。不同量化表在Cloth，Chicken，Horse和Michael数据上的表现均相似。显然对量化表线性赋值或抛物线赋值，可以达到比指数赋值更好的压缩效果。同时，指数赋值的效果随着分割子块增大而更差。指数型分布的量化表相较另外2种，更强调DCT系数矩阵左上角的信息，对右下角的信息压缩更大。这种偏向随着尺寸的扩大而更为明显，使得压缩效果不尽如人意，因此，在量化表的选择上应注意不要过于忽视DCT系数矩阵右下角部分。

(2) 子块尺寸对压缩效果的影响。随着子块的增大，压缩所需时间减少，说明进行离散余弦变换的次数和压缩时间正相关。在bpvf小于5时，使用尺寸为32的子块能取得最好的压缩效果和时间效应，但当bpvf较大时，压缩效果不如较小尺寸如8，16时的效果好。因为对于每一个分块，尺寸增大意味着对DCT系数矩阵右下角的信息压缩更甚，所带来的误差也越大，考虑到压缩的实际需求，均衡误差、时间和存储空间的考量。尺寸设定在32是较优的选择。

(3) 压缩效果的影响。结合上述实验结果，采用尺寸为32的分割子块，对量化矩阵采用线性设置，防止对数据的过压缩，同时对动画顶点进行重排，增加顶点间的相关性，使得DCT系数矩阵左上角的数值包含更多的信息，右下角可以被压缩的概率增大，于传统的JPEG算法相比，改进后的算法明显优于原来算法，与同样是将图像的操作转移到模型压缩上的文献[15]方法相比，改进后的JPEG算法依旧可以取得较好的效果。

5 结 论

本文结合传统图像压缩算法，根据三维动画数据特征，提出基于优化图像压缩的动画压缩框架。对动画数据结构化的子块尺寸优化提升了算法的时间性能，对图像压缩算法量化矩阵优化方法实现了相同压缩比下对准确度的要求，修改三维模型顶点序列进行优化调整增大了数据子块内的相关性，使得后续DCT部分能发挥更大作用，优化后的图像压缩算法可以明显提升对三维动画数据的压缩效果。作为本文工作的延续，将继续针对JPEG算法中离散余弦的变换模块，如根据数据本身的结构化特性自适应选择子块尺寸，进一步开展优化三维动画压缩方法的探索研发工作。

[1] WALLACE G K. The JPEG still picture compression standard[J]. IEEE Transactions on Consumer Electronics, 1991, 34(4): 30-44.

[2] CHRISTOPOULOS C, SKODRAS A, EBRAHIMI T. The JPEG2000 still image coding system: an overview[J]. IEEE Transactions on Consumer Electronics, 2000, 46(4): 1103-1127.

[3] RABBANI M, JOSHI R. An overview of the JPEG 2000 still image compression standard[J]. Signal Processing: Image Communication, 2002, 17(1): 3-48.

[4] WANG Z, BOVIK A C, SHEIKH H R, et al. Image quality assessment: from error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2004, 13(4): 600-612.

[5] LUO W Q, HUANG J W, QIU G P. JPEG error analysis and its applications to digital image forensics[J]. IEEE Transactions on Information Forensics and Security, 2010, 5(3): 480-491.

[6] FRIDRICH J. Feature-based steganalysis for JPEG images and its implications for future design of steganographic schemes[EB/OL]. [2021-03-18]. http://citeseerx.ist.psu.edu/ viewdoc/summary?doi=10.1.1.160.1596&rank=4.

[7] PEVNY T, FRIDRICH J. Merging Markov and DCT features for multi-class JPEG steganalysis[C]//Conference on Security Steganography and Watermarking of Multimedia Contents. Washington: SPIE Press, 2007.

[8] LI F Y, WU K, QIN C, et al. Anti-compression JPEG steganography over repetitive compression networks[J]. Signal Processing, 2020, 170: 107454.

[9] ZENG J S, TAN S Q, LI B, et al. Large-scale JPEG image steganalysis using hybrid deep-learning framework[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(5): 1200-1214.

[10] CHEN M, SEDIGHI V, BOROUMAND M, et al. JPEG-phase-aware convolutional neural network for steganalysis of JPEG images[C]//Proceedings of the 5th ACM Workshop on Information Hiding and Multimedia Security - IHMMSec’17. New York: ACM Press, 2017: 75-84.

[11] QIAN Z X, ZHANG X P, WANG S Z. Reversible data hiding in encrypted JPEG bitstream[J]. IEEE Transactions on Multimedia, 2014, 16(5): 1486-1491.

[12] LI N, HUANG F J. Reversible data hiding for JPEG images based on pairwise nonzero AC coefficient expansion[J]. Signal Processing, 2020, 171: 107476.

[13] TODERICI G, VINCENT D, JOHNSTON N, et al. Full resolution image compression with recurrent neural networks[C]//2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). New York: IEEE Press, 2017: 5435-5443.

[14] RIPPEL O, BOURDEV L. Real-time adaptive image compression[EB/OL]. [2020-03-18]. http://proceedings.mlr. press/v70/rippel17a.html.

[15] REN Z L, SHAKHNAROVICH G. Image segmentation by cascaded region agglomeration[C]//2013 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2013: 2011-2018.

[16] BARNI M, BONDI L, BONETTINI N, et al. Aligned and non-aligned double JPEG detection using convolutional neural networks[J]. Journal of Visual Communication and Image Representation, 2017, 49: 153-163.

[17] MAGLO A, LAVOUÉ G, DUPONT F, et al. 3D mesh compression: survey, comparisons, and emerging trends[J]. ACM Computing Surveys, 2015, 47(3): 44.

[18] PENG J L, KIM C S, JAY KUO C C. Technologies for 3D mesh compression: a survey[J]. Journal of Visual Communication and Image Representation, 2005, 16(6): 688-733.

[19] DEERING M F. Geometry compression for regular and irregular mesh structures: US6525722[P]. 2003-02-25.

[20] KARNI Z, GOTSMAN C. Spectral compression of mesh geometry[C]//27th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH. New York: ACM Press, 2000: 279-286.

[21] BEN-CHEN M, GOTSMAN C. On the optimality of spectral compression of mesh data[J]. ACM Transactions on Graphics, 2005, 24(1): 60-80.

[22] KHODAKOVSKY A, SCHRÖDER P, SWELDENS W. Progressive geometry compression[C]//27th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH. New York: ACM Press, 2000: 271-278.

[23] LEE H, LAVOUE G, DUPONT F. Rate-distortion optimization for progressive compression of 3D mesh with color attributes[J]. The Visual Computer, 2012, 28(2): 137-153.

[24] YANG B L, ZHANG L H, LI F W B, et al. Motion-aware compression and transmission of mesh animation sequences[J]. ACM Transactions on Intelligent Systems and Technology, 2019, 10(3): 25.

[25] SCHNABEL R, KLEIN R. Octree-based point-cloud compression[EB/OL]. [2021-03-18]. https://xueshu.baidu.com/ usercenter/paper/show?paperid=806a63abd78d8f1be4e74d996f98ef9c&site=xueshu_se.

[26] COHEN R, TIAN D, VETRO A. Point cloud compression using prediction and shape-adaptive transforms: US20170214943[P]. 2017-07-27.

[27] TIAN D, OCHIMIZU H, FENG C, et al. Geometric distortion metrics for point cloud compression[C]//2017 IEEE International Conference on Image Processing (ICIP). New York: IEEE Press, 2017: 3460-3464.

[28] DE QUEIROZ R L, CHOU P A. Motion-compensated compression of dynamic voxelized point clouds[J]. IEEE Transactions on Image Processing, 2017, 26(8): 3886-3895.

[29] ZHANG C, FLORÊNCIO D, LOOP C. Point cloud attribute compression with graph transform[C]//2014 IEEE International Conference on Image Processing (ICIP). New York: IEEE Press, 2014: 2066-2070.

[30] COHEN R A, TIAN D, VETRO A. Attribute compression for sparse point clouds using graph transforms[C]//2016 IEEE International Conference on Image Processing (ICIP). New York: IEEE Press, 2016: 1374-1378.

[31] KAMMERL J, BLODOW N, RUSU R B, et al. Real-time compression of point cloud streams[C]//2012 IEEE International Conference on Robotics and Automation. New York: IEEE Press, 2012: 778-785.

Research on the structured 3D animation and the compression

LUO Guo-liang1, WANG He1, ZHAO Xin1, CAO Yi-qin1, HUANG Xiao-sheng1, WU Chang-xing1, XIAN Chu-hua2

(1. School of Software, East China Jiaotong University, Nanchang Jiangxi 330013, China; 2. School of Computer Science and Engineering, South China University of Technology, Guangzhou Guangdong 510641, China)

With the increasingly wide applications of 3D animation, the compression methods of 3D animation data have become significant for the technologies in data storage, transmission, and rendering. There are multiple efficient technologies for 2D image compression in the domain of computer vision. Based on the structural differences between t3D animation data and 2D image data, the improvement of the image compression algorithm was explored for a new method of 3D animation compression. Specifically, the optimal vertex sequence of the 3D model towards compression was first computed. Then, based on the classical image compression algorithm flow, the sub-block size optimization and the quantization matrix optimization was formulated to improve compression. Finally, with different types of animation, experimental results show that the optimized image compression algorithm can guarantee both effectiveness and efficiency for the compression.

compression; 3D animation; image compression algorithm; clustering; discrete convolution transform coefficients

TP 391

10.11996/JG.j.2095-302X.2021020182

A

2095-302X(2021)02-0182-08

2020-09-19；

19 September，2020；

2020-10-09

9 October，2020

国家自然科学基金项目(61962021)；江西省自然科学基金重点项目(20202ACBL202008)；中国博士后科学基金(2020T130264)；江西省研究生创新专项资金项目(YC2020-S353)

National Natural Science Foundation of China (61962021); Key Research Program of Jiangxi Province (20202ACBL202008); China Postdoctoral Science Foundation (2020T130264); Graduate Student Innovation Special Foundation of Jiangxi Province (YC2020-S353)

罗国亮(1985-)，男，江西南昌人，副教授，博士后。主要研究方向为计算机图形学。E-mail：luoguoliang@ecjtu.edu.cn

LUO Guo-liang (1985-), male, associate professor, postdoctoral. His main research interest covers computer graphics. E-mail：luoguoliang@ecjtu.edu.cn

冼楚华(1982–)，男，广东肇庆人，副教授，博士。主要研究方向为计算机图形学。E-mail：chhxian@scut.edu.cn

XIAN Chu-hua (1982–), male, associate professor, Ph.D. His main research interest covers computer graphics. E-mail：chhxian@scut.edu.cn