基于時空分割的三維動畫壓縮算法研究

易 茹

(安徽工貿(mào)職業(yè)技術學院，安徽 淮南 232007)

0 引言

三維動畫的發(fā)展對三維動畫技術提出了更高要求，特別是三維動畫數(shù)據(jù)應用規(guī)模的不斷擴大，對三維動畫壓縮方法的研究成為許多學者關注的焦點。杜洪等在對主成分分析的基礎上提出了一種新的算法來提取圖像的主成分，并將其應用于圖像壓縮中，通過仿真試驗驗證了所提出的算法在求取主成分的時候迭代次數(shù)少、效率高[1]。羅國亮等對三維動畫數(shù)據(jù)結構化方法進行研究，提出了一種新的三維動畫數(shù)據(jù)壓縮算法，通過動畫數(shù)據(jù)結構化子塊尺寸優(yōu)化使得算法的時間性能大大提升，同時對圖像壓縮算法量化矩陣的優(yōu)化滿足了在相同壓縮比下對準確度的要求[2]。杜博等根據(jù)K-L變換的原理找到了用于圖像壓縮的投影矩陣，提出了基于張量主成分分析的人臉圖像壓縮算法，并通過在人臉數(shù)據(jù)庫中人臉圖像的壓縮，試驗驗證了該算法相對于常規(guī)的主成分分析法對人臉圖像的壓縮更具明顯優(yōu)勢[3]。主成分分析法作為一種有效地實現(xiàn)數(shù)據(jù)降維、去冗余的算法，在圖像壓縮中具有十分廣泛的應用，但是直接應用于三維動畫壓縮中效果并不理想[4]?；诖耍瑪M將時空分割與主成分分析相結合，以實現(xiàn)對三維動畫的有效壓縮。

1 理論基礎

1.1 主成分分析

主成分分析是通過正交變換將可能存在相關性的變量轉換為不相關變量的統(tǒng)計方法，通過進行主成分分析能夠達到降維、去冗余的目的。采用主成分分析進行圖像壓縮是將圖像分塊，每一塊作為一個樣本向量，計算樣本向量協(xié)方差矩陣C的前k個比較大特征值所對應的特征向量作為主成分，同時舍棄特征值比較小的，從而達到對圖像壓縮的目的[5]。設樣本矩陣為

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

(1)

(2)

式中：

(3)

計算協(xié)方差矩陣C，即[6]

(4)

計算協(xié)方差矩陣C的特征值和特征向量，并將特征值進行降序排序，獲得前k個最大特征值所對應的特征向量，分別為v1、v2、…、vk，將k個特征向量組成矩陣B，即

B=[v1,v2,…,vk]

(5)

那么原始數(shù)據(jù)X的降維矩陣Y表示為

Y=X×B

(6)

1.2 時空分割

設F為三維動畫，其包含t幀動畫矩陣(f1,f2,…,ft)。動畫矩陣由三角形與頂點矩陣所構成，先將三角形矩陣全部轉化為頂點矩陣，那么動畫矩陣就轉變?yōu)榧冺旤c矩陣。每一幀圖像的純頂點矩陣可以表示為一個m×n的矩陣，因此可以將三維動畫以列作為標準進行合并，最終得到(m×(n×t))的頂點矩陣D[7]。對頂點矩陣D進行主成分分析，提出主成分以達到對三維動畫進行壓縮的目的。圖1為三維動畫壓縮算法流程。

圖1 三維動畫壓縮算法流程

定義三維動畫區(qū)域在時間與空間范圍內(nèi)一致的為剛性區(qū)域，三維動畫區(qū)域在時間與空間范圍內(nèi)不一致的為動態(tài)區(qū)域。采用主成分分析進行三維動畫壓縮時必須要考慮剛性區(qū)域與動態(tài)區(qū)域的不同，否則會導致三維動畫壓縮的效果比較差。

2 時空分割的三維動畫壓縮

2.1 創(chuàng)建頂點矩陣

由于三維動畫矩陣由三角形矩陣和頂點矩陣所構成，需要將其全部轉化為純頂點矩陣vi。由于三維動畫幀在空間上是一致的，因此可以將動畫幀進行拼接，從而得到矩陣V=(v1,v2,v3)。對三維動畫進行壓縮的基礎矩陣RS為

(7)

2.2 創(chuàng)建動態(tài)分割塊

時空分割是時間域和空間域的分割，在獲得頂點矩陣之后，該矩陣的橫向為時域，豎向為空間域，頂點矩陣示意如圖2所示[8]。

圖2 頂點矩陣示意

在圖2中，灰色的方塊為動畫幀數(shù)據(jù)，p1、p2、p3、p4為時空分割塊。根據(jù)動畫跨域分割算法能夠得到動態(tài)分割塊在基礎矩陣RS中所對應的位置，記為StSi。很明顯，矩陣StSi為基礎矩陣RS的子矩陣，其為圖2中的白色方塊。StSi在時間上是跨域的，時空分塊p1和p4在同一個動畫幀，且p4不滿一個動畫幀，時空分塊p2和p3跨越多個動畫幀。

2.3 剛性區(qū)域

剛性區(qū)域頂點矩陣的構造需要在基礎矩陣RS中尋找到動態(tài)分割塊頂點矩陣StSi所對應的分塊，使得分塊元素被替換為一致性比較好的值。定義RS′為剛性區(qū)域頂點矩陣，那么分割靜態(tài)區(qū)和活動區(qū)的關鍵是判斷那些數(shù)據(jù)需要分割，活動區(qū)數(shù)據(jù)往往和矩陣的整體具有比較大的差別。

(8)

為了區(qū)分靜態(tài)區(qū)和活動區(qū)，設置考量活動區(qū)或者靜態(tài)區(qū)(剛性區(qū))的閾值τ。如果數(shù)據(jù)的區(qū)別超過了設定的閾值τ，那么就可以判定為活動區(qū)[9]。

三維動畫動態(tài)分割之后進行圖像壓縮，同時剩余的剛性區(qū)也需要進行圖像壓縮，而此時由于動態(tài)分割動態(tài)區(qū)是空白的，因此必須對動態(tài)區(qū)域進行填補。由主成分分析的原理可知，一致性高的數(shù)據(jù)，其主成分的維度小，可以大大提高壓縮的效率。因此采用剩余剛性區(qū)域均值來對動態(tài)區(qū)域進行填補，即

(9)

(10)

2.4 三維動畫壓縮流程

三維動畫劃分為活動區(qū)和剛性區(qū)，對剛性區(qū)采用主成分分析進行壓縮處理，活動區(qū)域進行動態(tài)分割。另外，考慮不同維度數(shù)據(jù)離散導致采用主成分分析對圖像壓縮性能的不利影響，對剛性區(qū)域進行維度分割，這樣就可以將空間3個不同維度的數(shù)據(jù)組成3個時空分割矩陣。采用主成分分析法對3個時空分割矩陣進行分析，同時對動態(tài)分割塊也采用主成分分析法，從而實現(xiàn)對三維動畫的壓縮?；跁r空分割的三維動畫壓縮算法流程如圖3所示。

圖3 基于時空分割的三維動畫壓縮算法流程

3 實例分析

3.1 試驗數(shù)據(jù)

選擇4個動畫進行三維動畫壓縮效果的仿真分析，4個動畫的頂點數(shù)、面片數(shù)、幀數(shù)信息如表1所示。

表1 4個動畫數(shù)據(jù)信息

設置考量活動區(qū)或者靜態(tài)區(qū)(剛性區(qū))的閾值τ=0.65，采用基于時空分割算法分別對動態(tài)分割與剛性分割應用主成分分析法(方法1)、基于時空分割區(qū)分3個維度應用主成分分析法采用動態(tài)分割與剛性分割壓縮法(方法2)對2種三維動畫壓縮，對比2種方法對三維動畫的壓縮性能。對三維動畫壓縮性能的評價指標為壓縮比γ和誤差Rrror，其數(shù)學表達式為[10]

(11)

三維動畫壓縮算法的壓縮比越低，其壓縮效果越好；壓縮比越高，其壓縮效果越差。三維動畫壓縮算法的誤差率越低，其壓縮效果越好；誤差率越高，其壓縮效果越差。

3.2 結果分析

采用2種算法對4個三維動畫進行壓縮仿真試驗，結果如圖4所示。

a) “人”三維動畫壓縮仿真結果

b) “駱駝”三維動畫壓縮仿真結果

c) “大猩猩”三維動畫壓縮仿真結果

d) “馬”三維動畫壓縮仿真結果

由圖4可知，動畫序列往往比較長，這使得其動態(tài)冗余信息量比較大，提取動態(tài)分割并進行壓縮往往能夠取得更好的壓縮效果。另外，當壓縮比較小時，方法2的誤差比方法1的誤差小，具有更好的壓縮效果。這是因為在壓縮比較大的情況下，空間數(shù)據(jù)不同維度獨立進行壓縮時往往能夠得到更加充分的主成分維度需求，從而使得各個維度具有更加良好的還原效果。

4 結論

針對三維動畫數(shù)據(jù)量大，冗余信息多導致三維動畫分析、傳輸、存儲困難等問題，對三維動畫壓縮算法進行了研究。對三維動畫進行跨域時空分割以及維度劃分，剛性區(qū)域采用主成分分析算法進行壓縮處理，活動區(qū)域進行動態(tài)分割，同時對動態(tài)分割塊采用主成分分析法。將其應用于4個三維動畫的壓縮仿真試驗中，結果表明，基于時空分割的三維動畫壓縮算法能夠對三維動畫取得良好的壓縮效果。