熊小勇 謝文強(qiáng) 張韌博 郭 斌 王文樂* 吳少智

1(江西師范大學(xué)軟件學(xué)院 江西 南昌 330022)2(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 四川 成都 611731)

0 引 言

隨著動(dòng)畫制作技術(shù)的發(fā)展，基于三維動(dòng)畫數(shù)據(jù)的應(yīng)用規(guī)模不斷增長(zhǎng)，三維動(dòng)畫數(shù)據(jù)也已成為虛擬現(xiàn)實(shí)技術(shù)應(yīng)用于教育、數(shù)字娛樂等領(lǐng)域的主要數(shù)據(jù)媒介之一[1-3]。與此同時(shí)，對(duì)三維動(dòng)畫數(shù)據(jù)的分析和處理技術(shù)的需求也不斷增長(zhǎng)。然而，由于三維動(dòng)畫通常具有較大的規(guī)模，現(xiàn)有的三維動(dòng)畫特征描述方式有限，使得處理三維動(dòng)畫依舊是計(jì)算機(jī)圖形學(xué)領(lǐng)域研究熱點(diǎn)課題之一[4]。為實(shí)現(xiàn)高效的三維動(dòng)畫分析、傳輸、存儲(chǔ)等操作，設(shè)計(jì)一種有效的三維動(dòng)畫壓縮算法顯得尤為重要。

近年，眾多研究工作專注于三維動(dòng)畫壓縮課題。主要概括起來有三類，包括基于空域[5-7]、基于時(shí)域[8-9]和基于時(shí)空一致性[10-12]。基于空域的方法在頂點(diǎn)軌跡上應(yīng)用主成分分析算法PCA[13-14]。如：文獻(xiàn)[5]中提供了一種聚類主成分分析算法，該算法可以將相似軌跡的頂點(diǎn)聚類，并且對(duì)于每一個(gè)分組都獨(dú)立運(yùn)用主成分分析算法進(jìn)行維度約簡(jiǎn)，從而實(shí)現(xiàn)壓縮。與空域方法相比，文獻(xiàn)[8]提供了一種將具有相同姿態(tài)的動(dòng)畫幀聚類并分別對(duì)每一個(gè)分類都運(yùn)用主成分分析算法進(jìn)行維度降解的壓縮方法。這兩種方法各有優(yōu)劣：時(shí)域類方法對(duì)于點(diǎn)軌跡同步好的動(dòng)畫數(shù)據(jù)壓縮效果更佳，而空域類方法對(duì)于重復(fù)性動(dòng)作多的動(dòng)畫數(shù)據(jù)壓縮效果更佳。就時(shí)空一致性而言，文獻(xiàn)[5]表述了一種時(shí)空混合預(yù)測(cè)模型用于預(yù)測(cè)頂點(diǎn)在壓縮后的位置。文獻(xiàn)[15]在近期提出了一種基于有效性分割的時(shí)空一致性模型，進(jìn)而對(duì)于每一個(gè)基于分割有效值的時(shí)空一致性都有大的變形幅度。文獻(xiàn)[17]中，運(yùn)用分割方法來實(shí)現(xiàn)運(yùn)動(dòng)估計(jì)，取得了較好的壓縮表現(xiàn)。文獻(xiàn)[18]實(shí)現(xiàn)了移動(dòng)的人體序列有效壓縮。

基于該聯(lián)合時(shí)-空域的跨域分割結(jié)果，本文進(jìn)一步提出一種新的基于三維模型的動(dòng)態(tài)行為計(jì)算跨域時(shí)空分割算法，實(shí)現(xiàn)區(qū)分三維模型的剛性分割和動(dòng)態(tài)時(shí)空域分割。在此三維模型的剛性分割和動(dòng)態(tài)時(shí)空域分割的基礎(chǔ)上，借助經(jīng)典的主成分分析算法分別實(shí)現(xiàn)對(duì)剛性區(qū)域和動(dòng)態(tài)分割區(qū)域的壓縮，獲得更好的壓縮結(jié)果。在此基礎(chǔ)上，本文進(jìn)一步提出了運(yùn)用維度劃分，分別劃分三維動(dòng)畫各個(gè)維度的數(shù)據(jù)后，再在各維度數(shù)據(jù)上分別運(yùn)用本文提出的壓縮算法，以進(jìn)一步提升壓縮效果。

1 主成分分析與三維動(dòng)畫時(shí)空分割算法

1.1 主成分分析算法

假設(shè)一個(gè)有m個(gè)n維數(shù)據(jù)的樣本矩陣X:

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

(1)

主成分分析算法原理簡(jiǎn)述如下[7]:

(2)

式中：

(3)

為矩陣X的矩陣均值；

(4)

為矩陣X中每一列的均值。

第二步:計(jì)算協(xié)方差矩陣C，即:

(5)

第三步:計(jì)算矩陣C的特征值D和特征向量V，其中，D∈Rm×m為對(duì)角矩陣其對(duì)角元素為矩陣C的特征值，V=[v1,v2,…,vm]∈Rm×n為特征值所對(duì)應(yīng)的特征矩陣，vi表示第i特征值所對(duì)應(yīng)的特征向量。

第四步:將特征向量根據(jù)特征值降序排序，得到前k個(gè)最大特征值所對(duì)應(yīng)的特征向量v1,v2,…,vi:

B=[v1,v2,…,vk]

(6)

第五步:計(jì)算原始數(shù)據(jù)X的降維表示，即如下:

Y=X×B

(7)

式中：

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

(8)

為矩陣X的低維主成分表示。

為充分發(fā)掘主成分分析算法在三維動(dòng)畫數(shù)據(jù)壓縮方面的應(yīng)用潛能，本文將探討主成分分析算法與三維動(dòng)畫時(shí)空分割算法的多種結(jié)合方式，并應(yīng)用于數(shù)據(jù)壓縮進(jìn)行算法性能評(píng)估。

1.2 三維動(dòng)畫的時(shí)空分割

首先，對(duì)于給定一個(gè)三維動(dòng)畫M，其由t幀動(dòng)畫矩陣(f1,f2,…,ft)組成，這些動(dòng)畫矩陣都是由個(gè)三角形和個(gè)頂點(diǎn)矩陣組成。然后，可以將這些由三角形和頂點(diǎn)組成的動(dòng)畫幀矩陣轉(zhuǎn)化為純頂點(diǎn)矩陣。每一幀的純頂點(diǎn)矩陣在時(shí)空可以表示為一個(gè)m×n的矩陣，我們可以將不同時(shí)間上的動(dòng)畫幀以列為標(biāo)準(zhǔn)合并在一個(gè)矩陣?yán)?，由此，可以將t個(gè)由三角形與頂點(diǎn)組成的動(dòng)畫幀矩陣集合轉(zhuǎn)換成為了(m×(n×t))的頂點(diǎn)矩陣D。

進(jìn)一步，通過對(duì)頂點(diǎn)矩陣D，運(yùn)用主成分分析算法，來對(duì)三維動(dòng)畫矩陣進(jìn)行壓縮，如圖1所示。文獻(xiàn)[8]中的實(shí)驗(yàn)結(jié)果表明該方法對(duì)三維矩陣進(jìn)行有效壓縮。

圖1 基于時(shí)空一致性的三維動(dòng)畫壓縮算法流程

然而，由于三維動(dòng)畫區(qū)域在時(shí)間和一定范圍內(nèi)的空間內(nèi)廣泛存在一致性，這些區(qū)域稱為剛性區(qū)域，如圖2黑色區(qū)域。而體現(xiàn)三維動(dòng)畫運(yùn)動(dòng)屬性在時(shí)空上的不一致性集中在一個(gè)很小的范圍內(nèi)，稱為動(dòng)態(tài)區(qū)域，如圖2灰色區(qū)域所示。值得注意的是，文獻(xiàn)[8]直接對(duì)三維動(dòng)畫頂點(diǎn)矩陣進(jìn)行PCA算法處理的方法并沒有考慮到剛性區(qū)域和動(dòng)態(tài)區(qū)域區(qū)別。由于大量離散的數(shù)據(jù)存在，對(duì)整個(gè)三維動(dòng)畫區(qū)域進(jìn)行處理將導(dǎo)致PCA算法的效果不佳。與此同時(shí)，這些離散的數(shù)據(jù)不僅存在于動(dòng)態(tài)區(qū)域同時(shí)還存在不同維度的剛性區(qū)域上，而且在相同維度上，數(shù)據(jù)相對(duì)集中的，不同維度的數(shù)據(jù)相對(duì)離散，可能會(huì)影響主成分分析算法的效果。

圖2 三維動(dòng)畫中剛性區(qū)域(黑色區(qū)域)和動(dòng)態(tài)區(qū)域(灰色區(qū)域)示意圖

2 基于時(shí)空分割的三維動(dòng)畫壓縮算法

針對(duì)以上基于時(shí)空一致性的三維動(dòng)畫壓縮算法的不足，本文設(shè)計(jì)出了一種基于跨域時(shí)空分割的三維動(dòng)畫壓縮算法。在本文提出的算法中，對(duì)于動(dòng)畫矩陣，先通過算法處理成為純頂點(diǎn)矩陣。同時(shí)，通過文獻(xiàn)[8]描述的算法，獲取三維動(dòng)畫數(shù)據(jù)中的動(dòng)態(tài)區(qū)域集，稱之為動(dòng)態(tài)分割塊。從而得到了動(dòng)態(tài)分割塊集合和剛性區(qū)域。對(duì)于剛性區(qū)域，仍采用主成分分析算法處理，而對(duì)于動(dòng)態(tài)分割塊，將采用不同的方法處理。本文方法的流程如圖3所示。

圖3 基于跨域時(shí)空分割的三維動(dòng)畫壓縮算法流程

同時(shí)，為了降低不同維度數(shù)據(jù)的離散性對(duì)主成分分析算法的影響，本文進(jìn)一步提出基于維度劃分的時(shí)空分割三維動(dòng)畫壓縮算法?；诰S度劃分的三維動(dòng)畫壓縮算進(jìn)一步對(duì)剛性區(qū)域，進(jìn)行維度分割，將空間三個(gè)不同維度的數(shù)據(jù)，分別組成三個(gè)對(duì)應(yīng)的時(shí)空分割矩陣。然后，對(duì)這三個(gè)不同的矩陣，分別運(yùn)用主成分分析算法處理。而動(dòng)態(tài)分割塊，可以采用主成分分析算法壓縮，也可以采用其他方法處理，如圖4所示。

圖4 基于維度劃分的時(shí)空分割三維動(dòng)畫壓縮算法

2.1 頂點(diǎn)矩陣的構(gòu)建

首先，將三維動(dòng)畫數(shù)據(jù)中的每一幀的三角形與頂點(diǎn)矩陣集合轉(zhuǎn)化為純頂點(diǎn)矩陣，記為vi。然后，根據(jù)三維動(dòng)畫幀在空間上的一致性，將動(dòng)畫幀拼接為矩陣V=(v1,v2,v3)。由此，可以計(jì)算本文壓縮方法的基礎(chǔ)矩陣，記為:

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

(9)

式中:

(10)

2.2 動(dòng)態(tài)分割塊的構(gòu)建

圖5為頂點(diǎn)矩陣示意圖，其中，橫坐標(biāo)“時(shí)域”表示時(shí)間維度，縱坐標(biāo)“空域”表示單個(gè)三維模型中的空間關(guān)系；灰色方塊表示動(dòng)畫幀數(shù)據(jù)，p1、p2、p3、p4分別表示對(duì)應(yīng)的時(shí)空分割塊?；趧?dòng)畫跨域分割算法，可以分析出動(dòng)態(tài)分割塊在基礎(chǔ)矩陣RS對(duì)應(yīng)的位置，記為StSi，矩陣StSi為基礎(chǔ)矩陣RS的子矩陣，如圖5中的白色分塊。StSi在時(shí)間上是跨域的。StSi可以是在一個(gè)動(dòng)畫幀之中，如圖5中p1、p4分塊；StSi可以跨域多個(gè)動(dòng)畫幀，如圖5中的p2、p3分塊；StSi也可能不滿一個(gè)動(dòng)畫幀，如圖5中的p4分塊。

圖5 頂點(diǎn)矩陣示意圖

2.3 剛性區(qū)域的頂點(diǎn)矩陣構(gòu)造

剛性區(qū)域的構(gòu)造，需要在三維動(dòng)畫的頂點(diǎn)矩陣RS中查找到動(dòng)態(tài)分割塊頂點(diǎn)矩陣StSi對(duì)應(yīng)的分塊，并使這些分塊的元素替換為一些更一致的值。由此，獲取了剛性區(qū)域的頂點(diǎn)矩陣，記為RS′。有：

(11)

(1) 動(dòng)態(tài)分割塊的判定標(biāo)準(zhǔn) 對(duì)于這個(gè)將靜止區(qū)域和活動(dòng)分割塊分開處理的方法，實(shí)現(xiàn)的基礎(chǔ)是，要判斷哪些數(shù)據(jù)是需要分割的。通常，與矩陣的整體相差比較大的就是活動(dòng)分割塊的數(shù)據(jù)。那么，有一個(gè)重要的因素就是，用何種標(biāo)準(zhǔn)確定為活動(dòng)分割塊。在這里，這個(gè)標(biāo)準(zhǔn)為一個(gè)考量動(dòng)態(tài)或靜態(tài)(剛性)的閾值τ，當(dāng)數(shù)據(jù)區(qū)別達(dá)到了這個(gè)閾值就可以確定為活動(dòng)分割塊。由于動(dòng)態(tài)分割塊的動(dòng)態(tài)特征明顯，與剛性模塊的分界區(qū)域狹窄，所以在確保正確判斷分割區(qū)域的前提下，閾值的選擇對(duì)于動(dòng)態(tài)區(qū)域的大小影響較小，從而使得對(duì)基于時(shí)空分割的壓縮效果影響有限。

(2) 數(shù)據(jù)填補(bǔ) 由于對(duì)三維動(dòng)畫動(dòng)態(tài)分割進(jìn)行分別的壓縮操作之后，對(duì)剩余的整體剛性模塊需要進(jìn)行壓縮計(jì)算。為填補(bǔ)去除的動(dòng)態(tài)區(qū)域，依據(jù)動(dòng)態(tài)PCA算法原理，數(shù)據(jù)的一致性越高，其主成分維度越低，也即達(dá)到更高的壓縮效率。據(jù)此，本文方法考慮對(duì)去除的動(dòng)態(tài)區(qū)域回填所有剩余剛性區(qū)域的均值，即:

(12)

(13)

(14)

(15)

3 仿真結(jié)果與分析

為便于對(duì)本文提出的三維動(dòng)畫壓縮方法進(jìn)行評(píng)估，本文選擇基于表一所列數(shù)據(jù)(如圖6所示)開展仿真實(shí)驗(yàn)。由左至右分別是“女人”、“表情動(dòng)畫1”、“表情動(dòng)畫2”、“駱駝”、“猩猩”、“馬”、“男人”。

圖6 仿真實(shí)驗(yàn)數(shù)據(jù)集

動(dòng)畫名稱頂點(diǎn)數(shù)面片數(shù)幀數(shù)“女人”43068590278“表情動(dòng)畫1”60811711473“表情動(dòng)畫2”66212721064“駱駝”218874381448“猩猩”150062999954“馬”84311684348“男人”150072999954

根據(jù)2.3節(jié)中的論述，在獲取穩(wěn)定的時(shí)空分割結(jié)果的基礎(chǔ)上，本文設(shè)定閾值τ=0.7。基于此，本文對(duì)表1數(shù)據(jù)分別開展以下四項(xiàng)仿真實(shí)驗(yàn):

(方法1) 直接應(yīng)用PCA于輸入動(dòng)畫。

(方法2) 基于時(shí)空分割，分別對(duì)動(dòng)態(tài)分割和剛性分割應(yīng)用PCA進(jìn)行壓縮。

(方法3) 基于時(shí)空分割，區(qū)分三個(gè)維度地應(yīng)用PCA分別對(duì)動(dòng)態(tài)分割和剛性分割進(jìn)行壓縮。

為便于對(duì)仿真結(jié)果進(jìn)行評(píng)估，引入壓縮比和誤差兩個(gè)因素。其中壓縮比為壓縮前后數(shù)據(jù)存儲(chǔ)位數(shù)比例，即：

(16)

式中:ni表示第i個(gè)分割(含動(dòng)態(tài)分割和剛性分割)中頂點(diǎn)個(gè)數(shù)，di表示壓縮保留的主成分個(gè)數(shù)?？梢?，壓縮比越低，壓縮效果更佳。

誤差評(píng)估采用經(jīng)典的KGError[15]，即:

(17)

對(duì)表1中的動(dòng)畫數(shù)據(jù)分別進(jìn)行上述四組仿真實(shí)驗(yàn)，結(jié)果如圖7、圖8和圖9所示。

圖7 “表情動(dòng)畫2”仿真結(jié)果

圖8 “表情動(dòng)畫1”(左)與“女人”(右)仿真結(jié)果

圖9 “駱駝”(左上)、“猩猩”(右上)、“馬”(左下)與“男人”(右下)仿真結(jié)果

首先，由圖7可見，隨著壓縮后使用的主成分維度的增加，壓縮比逐漸升高。但由于PCA算法的低維度(排列最前的幾個(gè)主成分)已經(jīng)保留了極高的原始信息，使得增加壓縮使用的主成分維度并不能顯著降低總誤差。同樣的規(guī)律在其他的六個(gè)仿真實(shí)驗(yàn)中也成立。

其次，兩個(gè)“表情動(dòng)畫”的長(zhǎng)度均遠(yuǎn)遠(yuǎn)大于“女人”動(dòng)畫，而方法2、方法3較方法1應(yīng)用于長(zhǎng)序動(dòng)畫均得到更低的壓縮誤差。這是因?yàn)閯?dòng)畫序列越長(zhǎng)，動(dòng)態(tài)冗余信息量更大，對(duì)提取的動(dòng)態(tài)分割提取并進(jìn)行壓縮得到更佳壓縮效果，充分體現(xiàn)了本文提出的壓縮方法的可行性。

第三，由“駱駝”、“猩猩”、“馬”和“女人”這四個(gè)仿真實(shí)驗(yàn)的結(jié)果可以發(fā)現(xiàn)方法2在壓縮比較低時(shí)誤差較方法3更低，但是在壓縮比高時(shí)誤差較方法3 更高。這是由于方法3高壓縮比的情況下，空間數(shù)據(jù)各個(gè)維度獨(dú)立進(jìn)行壓縮將得到充分的主成分維度需求，從而在各個(gè)維度的還原效果均佳，也使得誤差更低；反之，低壓縮比的情況下，方法3的誤差率更高。

4 結(jié) 語

綜合以上對(duì)三維動(dòng)畫的壓縮算法設(shè)計(jì)、實(shí)施與分析，實(shí)現(xiàn)了基于跨域時(shí)空分割和基于維度劃分對(duì)三維動(dòng)畫壓縮算法的效果評(píng)估。實(shí)驗(yàn)結(jié)果表明，對(duì)于基于時(shí)空分割的壓縮算法，無論是基于跨域時(shí)空分割還是基于維度劃分的時(shí)空壓縮算法，在應(yīng)用于長(zhǎng)序列動(dòng)畫時(shí)都取得了比直接對(duì)三維動(dòng)畫數(shù)據(jù)運(yùn)用主成分分析算法更好的效果。盡管兩種新的方法在應(yīng)用于短序列動(dòng)畫時(shí)表現(xiàn)欠佳，但長(zhǎng)序列數(shù)據(jù)在現(xiàn)實(shí)世界更具有普遍意義。

對(duì)于基于跨域時(shí)空分割和基于維度劃分的時(shí)空分割這兩種時(shí)空分割壓縮算法，實(shí)驗(yàn)結(jié)果表明，基于跨域時(shí)空分割的算法在低壓縮比的情況下略微優(yōu)于基于維度劃分的時(shí)空壓縮算法。而這兩種不同的基于時(shí)空分割的壓縮算法，都較明顯地優(yōu)于直接運(yùn)用主成分分析的算法。兩種方法可基于不同應(yīng)用場(chǎng)景，按需擇優(yōu)。

參考文獻(xiàn)

[1] 商柳,馮笑冰,朱登明,等.一種骨架驅(qū)動(dòng)的近岸涌浪動(dòng)畫合成方法[J].軟件學(xué)報(bào)，2016，27(10):2600-2611.

[2] 王鵬杰,潘志庚,李威.人體運(yùn)動(dòng)捕獲數(shù)據(jù)壓縮技術(shù)研究進(jìn)展[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2016,28(7):1037-1046.

[3] 陸焱,惠巧娟.改進(jìn)的統(tǒng)計(jì)模型三維人臉特征點(diǎn)標(biāo)定算法框架[J].計(jì)算機(jī)工程與應(yīng)用,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ī)交互中動(dòng)作在線發(fā)現(xiàn)與時(shí)域分割[J].計(jì)算機(jī)學(xué)報(bào),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] 張杰,吳劍章,湯嘉立,等.基于時(shí)空?qǐng)D像分割和交互區(qū)域檢測(cè)的人體動(dòng)作識(shí)別方法[J].計(jì)算機(jī)應(yīng)用研究,2017,34(1):302-305.

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

[14] 阮越,陳漢武,劉志昊,等.量子主成分分析算法[J].計(jì)算機(jī)學(xué)報(bào),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.