基于數據結構化的三維動畫壓縮方法研究

羅國亮，王 賀，趙 昕，曹義親，黃曉生，鄔昌興，冼楚華

基于數據結構化的三維動畫壓縮方法研究

羅國亮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]也通過類似的方法實現了圖像取證的應用驗證，這在當前天網高度密集部署情況下，圖像的司法合理性論證具有現實意義?；贘PEG的信息隱藏也得到了廣泛的研究[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