基于時空分割的三維動畫壓縮

熊小勇 謝文強 張韌博 郭 斌 王文樂* 吳少智

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.