李順意,侯 進,2,甘凌云

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,成都610031;

2.南京大學(xué)計算機軟件新技術(shù)國家重點實驗室,南京210093)

基于幀間距的運動關(guān)鍵幀提取

李順意1,侯 進1,2,甘凌云1

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,成都610031;

2.南京大學(xué)計算機軟件新技術(shù)國家重點實驗室,南京210093)

運動捕獲數(shù)據(jù)中有大量的冗余數(shù)據(jù),不利于運動數(shù)據(jù)的壓縮、存儲、檢索以及進一步重用。為此,提出一種基于幀間距的運動關(guān)鍵幀提取方法,提取代表運動捕獲數(shù)據(jù)內(nèi)容的關(guān)鍵姿勢。利用四元數(shù)之間的距離表示人體姿態(tài)差異,將人體各個關(guān)節(jié)上的總變化作為幀間距,以運動數(shù)據(jù)首幀作為第一個關(guān)鍵幀。通過不斷計算當(dāng)前幀同最后一個關(guān)鍵幀之間的差異,消除差異小于閾值的幀,差異超過閾值的幀被當(dāng)作為新關(guān)鍵幀。對提取關(guān)鍵幀集合采用四元數(shù)球面插值方法重構(gòu)。為表現(xiàn)人體運動特征,在重構(gòu)誤差中引入關(guān)節(jié)速度分量,用人體姿勢誤差位置與人體關(guān)節(jié)運動速率之和表示原始運動與重建運動序列之間的重構(gòu)誤差。實驗結(jié)果表明,該方法對原始運動既有較高的壓縮率,又有較強的視覺概括效果。

運動捕獲;關(guān)鍵幀提取;幀間距;球面線性插值;重構(gòu)誤差;視覺概括力

1 概述

在計算機動畫中,人體角色動畫是很重要的組成部分,但也因人體包含自由度多、維數(shù)高,創(chuàng)建一個真實的和逼真的運動模型是非常困難的,人體角色動畫一直是計算機動畫技術(shù)中的難點[1]。目前人體角色動畫主要有基于關(guān)鍵幀的動畫、基于運動學(xué)的動畫、物理模擬動畫與基于捕獲數(shù)據(jù)的人體動畫技術(shù)。近年來,隨著運動捕捉設(shè)備的廣泛應(yīng)用,運動捕獲驅(qū)動的三維人體動畫替代傳統(tǒng)關(guān)鍵幀動畫[2]成為研究的熱點。運動捕獲驅(qū)動方法是利用運動捕捉設(shè)備實時記錄表演者肢體在空間中的運動,生成大量有真實感的人體運動數(shù)據(jù),然后將捕獲得到的真實感的角色運動數(shù)據(jù)映射到建立好的人體模型來生成動畫序列。運動數(shù)據(jù)驅(qū)動方法被廣泛地應(yīng)用到計算機交互游戲、電影廣告、體育訓(xùn)練以及醫(yī)學(xué)仿真等多個領(lǐng)域。

本文利用四元數(shù)之間的距離表示人體姿態(tài)差異,將人體各個關(guān)節(jié)上的總變化作為幀間距,以運動數(shù)據(jù)首幀作為第一個關(guān)鍵幀,不斷計算當(dāng)前幀同最后一個關(guān)鍵幀之間的差異,消除差異小于設(shè)定閾值的幀,差異超過設(shè)定閾值被當(dāng)作為新關(guān)鍵幀。對關(guān)鍵幀集合使用四元數(shù)球面插值方法重構(gòu)出原始序列幀數(shù)相同的重建序列,將原始幀與重建幀的平均幀間距離表示為重構(gòu)誤差,并在重構(gòu)誤差中引入速度誤差。

2 背景介紹

運動捕獲數(shù)據(jù)是以較高的采樣頻率獲得,平均每秒鐘幾十幀甚至上百幀,每一幀又包含了十幾個甚至幾十個關(guān)節(jié)點的旋轉(zhuǎn)信息,得到的數(shù)據(jù)量龐大且有大量的數(shù)據(jù)冗余,非常不利于運動捕獲數(shù)據(jù)的壓縮、存儲、檢索以及進一步重用,需提取出代表運動數(shù)據(jù)內(nèi)容的關(guān)鍵幀[3],關(guān)鍵幀提取技術(shù)被廣泛應(yīng)用于視頻分析與檢索領(lǐng)域[4]。運動關(guān)鍵幀提取主要有曲線簡化方法、基于聚類方法和幀消減方法。曲線簡化方法[5]將每一幀運動數(shù)據(jù)比作高維空間的一個點,運動序列看成是空一條運動軌跡,選擇曲線上一些凹凸點作為關(guān)鍵幀。但是該方法采用歐式距離作為幀間的相似度,無法真實地反映人體運動姿態(tài)之間的差異。文獻[6]改進了該算法,將人體的骨骼夾角作為運動特征表示,以此確定邊界姿態(tài)幀作為候選關(guān)鍵幀,然后采用分層曲線方法精選候選關(guān)鍵幀,最終獲得關(guān)鍵幀集合,該方法對邊界幀具有概括力。文獻[7]提出了基于聚類的關(guān)鍵幀提取方法,將相似運動數(shù)據(jù)聚類,每類選擇一個關(guān)鍵幀。該方法能夠提取表示原始數(shù)據(jù)內(nèi)容的關(guān)鍵幀,但是沒有考慮運動數(shù)據(jù)之間的時序相關(guān)性,容易導(dǎo)致對運動序列分析的失真問題。文獻[8]通過消減不可能為關(guān)鍵幀的幀而獲得的關(guān)鍵幀序列,用幀消減的方法計算消減幀的重構(gòu)誤差,從而得到一條重構(gòu)誤差曲線,根據(jù)曲線判斷出具有最優(yōu)壓縮率的關(guān)鍵幀,但其無法保證具有最佳壓縮率下得到關(guān)鍵幀的同時具有最小重建誤差,并且未考慮關(guān)鍵幀的運動表示能力。文獻[9]提出了一種基于運動分割的關(guān)鍵幀提取方法,將段與段之間的分割點作為關(guān)鍵幀點,其認為分割點最能表示運動變化最劇烈的姿態(tài),但是該方法未考慮誤差問題,不適合運動壓縮。文獻[10-12]提出一種基于混合遺傳算法的人體捕獲數(shù)據(jù)關(guān)鍵幀提取方法,將遺傳算法與單純行法相結(jié)合。文獻[13]提取一種預(yù)選策略與重建誤差優(yōu)化的運動關(guān)鍵幀提取方法,將關(guān)鍵幀提取分為幀預(yù)選和基于重建誤差優(yōu)化的2個階段。

基于以上分析,如何根據(jù)用戶需求使提取運動關(guān)鍵幀既能夠滿足大規(guī)模實時壓縮需要,又對原始運動具有很好的視覺概括力是關(guān)鍵幀的追求目標(biāo)。

3 人體結(jié)構(gòu)簡化與運動表示

人體有200多塊骨骼,600多個自由度,主要由骨架層、肌肉層和皮膚層組成,但為了降低人體運動復(fù)雜度,通常將關(guān)節(jié)運動簡化。層架骨架模型是一種常用的人體模型,是支撐人體運動最核心的部分,決定了人體運動的各種姿態(tài)。兩段剛體關(guān)節(jié)之間稱為關(guān)節(jié),連接相鄰2個關(guān)節(jié)的剛體是骨骼段,人體關(guān)節(jié)點的數(shù)目決定了運動的豐富性,關(guān)節(jié)點過多則包含運動信息更豐富,但也加大了編輯和計算復(fù)雜度,反之人體模型太簡單,則容易丟失重要運動細節(jié)信息,運動不夠細膩。本文將人體骨架模型簡化為29個關(guān)節(jié)點(含根節(jié)點,共計56個自由度)連接起來人體模型,人體樹形結(jié)構(gòu)拓撲如圖1所示。

圖1 人體樹形結(jié)構(gòu)拓撲

3.1 人體運動的描述

人體運動是由根節(jié)點的平移和其余各節(jié)點相對于其父節(jié)點的旋轉(zhuǎn)來實現(xiàn)的,根節(jié)點的平移決定了人體的運動軌跡,根節(jié)點的旋轉(zhuǎn)決定人體的運動方向。除根節(jié)點外,其他各節(jié)點的旋轉(zhuǎn)在以父節(jié)點為坐標(biāo)原點的局部坐標(biāo)系下進行,其他節(jié)點旋轉(zhuǎn)決定了人體旋轉(zhuǎn)狀態(tài),通過每一段骨架的長度和旋轉(zhuǎn)矩陣就能計算出各關(guān)節(jié)點在世界坐標(biāo)系中的位置,關(guān)節(jié)點Jm+1在世界坐標(biāo)系下的位置可由公式求出:

3.2 四元數(shù)

四元數(shù)q可以記為:

其中,w,x,y,z為實數(shù),四元數(shù)可以寫成抽象形式:

3.3 旋轉(zhuǎn)的表示

表示將向量r繞向量v旋轉(zhuǎn)θ角。

3.4 四元數(shù)球面線性插值與線性插值

四元數(shù)球面插值是2個單位四元數(shù)在單位超球面上插值,假設(shè)有單位四元數(shù)q1和q2,從q1到q2的球面線性插值記為Slerp(q1,q2,t),則有:

設(shè)相鄰2幀t1和t2根節(jié)點位置分別為P1和P2,t時刻跟關(guān)節(jié)所處的Pt(t1＜t＜t2),則兩者線性插值為:

3.5 四元數(shù)之間的距離

圖2 四元數(shù)距離

若q1,q2為2個單位四元數(shù)且q2q-1=[ω,x,y,z],2個四元數(shù)之間的距離表示為:

在四元數(shù)表示法中,人體可以表示為離散時間向量函數(shù):

其中,p(t)∈R3表示根關(guān)節(jié)平移運動;qi(i=1, 2,…,m)表示關(guān)節(jié)i旋轉(zhuǎn)運動,在一個運動序列中不同時刻t1,t2上的2幀,它們之間的距離D(t1,t2)表示為:

d(qi(t1),qi(t2))表示在t1,t2時刻關(guān)節(jié)i旋轉(zhuǎn)的四元數(shù)距離,wi(i=1,2,…,m)為各關(guān)節(jié)對運動姿勢影響程度大小。

如果有不同的運動序列A與運動序列B,A的每一幀到B的每一幀之間的距離也可以用兩者之間四元數(shù)的距離表示:

表1 各關(guān)節(jié)點對應(yīng)權(quán)值

4 運動關(guān)鍵幀提取與運動重構(gòu)

數(shù)組keynum[j]用來記錄提取的關(guān)鍵幀集合,lastkey表示當(dāng)前為止搜索到最后的關(guān)鍵幀,n為運動序列長度,δ為事先設(shè)定的閾值,主要根據(jù)用戶針對不同運動對壓縮率需求確定,keynum為提取關(guān)鍵幀數(shù)目,算法步驟如下:

Step 1將第一幀作為關(guān)鍵幀加入到keynum,并使lastkey=1,初始化循環(huán)變量t=2。

Step 2若t≥n,則算法停止;否則計算幀間距離d=D(t,lastkey)。

Step 3若d≥δ,第t幀作為關(guān)鍵幀被提取保存在keynum[j],并使lastkey=t。

Step 4t=t+1,返回Step2;直到算法結(jié)束,keynum[j],j∈[1,2,…,keynum]記錄了所有關(guān)鍵幀。

運動重構(gòu)是在提取關(guān)鍵集合后,對相鄰關(guān)鍵幀之間的非關(guān)鍵幀進行插值重構(gòu),從而重構(gòu)出與原始序列相同幀數(shù),重建算法步驟如下:

Step 1初始化循環(huán)變量j=0。

Step 2若j≥keynum-1,則算法結(jié)束;否則取相鄰關(guān)鍵幀T1=keynum[j],T2=keynum[j+1]。

Step 3對T1與T2之間的非關(guān)鍵幀進行插值重建,根關(guān)節(jié)采用一般線性插值,其他關(guān)節(jié)采用四元數(shù)球面插值。

Step 4j=j+1,返回Step2。

真實的人體運動具有較強的真實感,為較好地捕捉人體動態(tài)特征,考慮運動數(shù)據(jù)時序性與運動特性。用人體姿勢誤差位置與人體關(guān)節(jié)運動速率差來表示原始運動與重建運動序列之間的誤差(重構(gòu)誤差),重構(gòu)誤差用原始幀與重建幀的平均幀間距離表示。重構(gòu)誤差與關(guān)鍵幀提取數(shù)目、人體關(guān)節(jié)運動速率密切相關(guān),一般來說往往越少關(guān)鍵幀提取,重構(gòu)誤差越大。

設(shè)m1為原始運動序列,m2為關(guān)鍵幀集合插值重構(gòu)序列,長度均為n,重構(gòu)誤差E(m1,m2)表示為:

D表示人體姿勢加權(quán)距離,主要用以衡量人體姿勢的位置誤差,表示為:

5 實驗結(jié)果及分析

5.1 實驗結(jié)果

本文在Windows7操縱系統(tǒng)下,選擇Microsoft Visual Studio 2010作為開發(fā)平臺,使用OpenGL和卡耐基梅隆大學(xué)運動捕獲數(shù)據(jù)庫,以MFC框架搭建了虛擬人運動編輯平臺,在該平臺上實現(xiàn)對運動捕獲數(shù)據(jù)關(guān)鍵幀的提取功能。選擇骨架文件是asf(acclaim skeleton file)格式,運動數(shù)據(jù)是amc(acclaim motion capture data)格式,實驗在英特爾core i3M380, 2.53 GHCPU,2 GB內(nèi)存上的PC上進行。

實驗選取行走、騰空跳躍、翻筋斗3種運動類型來測試本文算法的有效性,采樣頻率均為40 f/s。實驗1對運動長度為150 f的行走走路運動分別采用文獻[5]方法、文獻[7]方法、文獻[9]方法與本文方法進行關(guān)鍵幀提取,關(guān)鍵幀提取效果如圖3～圖6所示。實驗2對運動長度為144幀的騰空跳躍運動分別采用文獻[5]方法、文獻[7]方法、文獻[9]方法與本文方法提取關(guān)鍵幀,關(guān)鍵幀提取效果如圖7～圖10所示。實驗3對運動長度為296幀的翻筋斗運動分別采用文獻[5]方法、文獻[7]方法、文獻[9]方法與本文方法提取關(guān)鍵幀,關(guān)鍵幀提取效果如圖11～圖14所示。

圖3 文獻[5]方法提取的行走關(guān)鍵幀集合

圖4 文獻[7]方法提取的行走關(guān)鍵幀集合

圖5 文獻[9]方法提取的行走關(guān)鍵幀集合

圖6 本文方法提取的行走關(guān)鍵幀集合

圖7 文獻[5]方法提取的騰空跳躍關(guān)鍵幀集合

圖8 文獻[7]方法提取的騰空跳躍關(guān)鍵幀集合

圖9 文獻[9]方法提取的騰空跳躍關(guān)鍵幀集合

圖10 本文方法提取的騰空跳躍關(guān)鍵幀集合

圖11 文獻[5]方法提取的翻筋斗關(guān)鍵幀集合

圖12 文獻[7]方法提取的翻筋斗關(guān)鍵幀集合

圖13 文獻[7]方法提取的翻筋斗關(guān)鍵幀集合

圖14 本文方法提取的翻筋斗關(guān)鍵幀集合

5.2 實驗分析結(jié)果

從圖3～圖5提取關(guān)鍵幀集合視覺效果來看,本文方法較好地對行走運動進行概括,而文獻[5]方法提取的關(guān)鍵幀無法反映運動幀之間的真實差異,文獻[7]方法與文獻[9]方法雖然也能概括行走運動序列,一些關(guān)鍵幀仍然丟失且可能導(dǎo)致運動序列分析的失真。

從圖7～圖10提取關(guān)鍵幀視覺效果可以看出,本文提出的方法對騰空跳躍運動提取沒有丟失重要關(guān)鍵幀,文獻[5]方法提取幀數(shù)過少,無法概括運動內(nèi)容,文獻[7]方法與文獻[9]方法雖然也能概括行走運動序列,但是其一些關(guān)鍵幀仍然丟失且?guī)g距過大。

從圖11～圖14提取關(guān)鍵幀視覺效果來看,本文方法提取關(guān)鍵幀集合能較好地對翻筋斗運動進行概括,文獻[5]方法關(guān)鍵幀與文獻[7]方法無法反映運動幀之間的真實差異,丟失在關(guān)鍵時刻的過度幀,容易造成對運動序列內(nèi)容分析的失真,文獻[9]方法雖然也能概括行走運動序列,但視覺效果上不如本文方法。

運動重建部分采用使用四元數(shù)球面插值方法進行了重建,選用四元數(shù)插值算法原因是其能保證提取相鄰關(guān)鍵幀鍵幀姿態(tài)差異較大時,也能插值生成較平滑的中間幀動畫。重構(gòu)誤差大小與關(guān)鍵幀提取數(shù)目有關(guān),對150幀行走運動的重建誤差曲線如圖15所示。

從圖15可以看出提取關(guān)鍵幀數(shù)目越少,重構(gòu)誤差越大。u為加權(quán)擬合參數(shù),主要調(diào)節(jié)速率差與位置差的加權(quán)比例。圖16繪制的是144幀騰空跳躍運動的重建誤差曲線,可以看出騰空跳躍運動特性更加明顯,當(dāng)然其加權(quán)擬合參數(shù)u越大,重構(gòu)誤差也比步行運動大。

圖15 行走運動重建誤差曲線

圖16 騰空跳躍重建誤差曲線

6 結(jié)束語

本文提出的方法在重構(gòu)誤差中引入速度分量,充分考慮了人體運動節(jié)奏性強的特點,從視覺上看,提取關(guān)鍵幀對原始運動數(shù)據(jù)具有較好的視覺概括能力。針對不同運動類型都壓縮率較高(小于7%)且能代表運動內(nèi)容,滿足了大規(guī)模實時壓縮的需要,大大降低了運動編輯的復(fù)雜度。今后工作是研究一種自動評價指標(biāo),甚至引入語義信息,從而更加精確地提取人體邊界姿勢,更好地致力于大規(guī)模運動捕捉數(shù)據(jù)的合成、檢索與編輯。

[1] 劉賢梅,張巧生.數(shù)據(jù)驅(qū)動的人體動畫合成研究綜述[J].計算機工程與設(shè)計,2010,31(18):4054-4057.

[2] 劉賢梅.數(shù)據(jù)驅(qū)動的人體動畫的關(guān)鍵幀技術(shù)研究綜述[J].計算機工程與設(shè)計,2011,32(3):1006-1009.

[3] 潘志庚,呂 培,徐明亮,等.低維人體運動數(shù)據(jù)驅(qū)動的角色動畫生成方法綜述[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2013,25(12):1775-1785.

[4] 孫淑敏,張建明,孫春梅.基于改進K-means算法的關(guān)鍵幀提取[J].計算機工程,2012,38(23):169-172.

[5] 楊 濤,肖 俊,吳 飛,等.基于分層曲線簡化的運動捕獲數(shù)據(jù)關(guān)鍵幀提取[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2006,18(11):1691-1697.

[6] 潘 紅,肖 俊.基于關(guān)鍵幀的三維人體運動檢索[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2009,21(2):214-222.

[7] Zhang Qiang,Yu Shaopei.An Efficient Method of Keyframe Extraction Based on a Cluster Algorithm[J]. Journal of Human Kinetics,2013,39(1):5-14.

[8] 劉云根,劉金剛.重建誤差最優(yōu)化的運動捕獲數(shù)據(jù)關(guān)鍵幀提取[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2010, 22(4):670-675.

[9] 朱登明,王兆其.基于運動序列分割的運動捕獲數(shù)據(jù)關(guān)鍵幀提取[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2008,20(6):787-792.

[10] 劉賢梅,郝愛民,趙 丹.基于混合遺傳算法的人體運動捕獲數(shù)據(jù)關(guān)鍵幀提取[J].模式識別與人工智能, 2011,24(5):619-628.

[11] Liu Xianmei,Hao Aimin,Zhao Dan.Optimization-based Key Frame ExtractionforMotionCaptureAnimation[J].The Visual Computer,2013,29(1):85-95.

[12] 劉賢梅,趙 丹.四元數(shù)樣條插值的人體運動數(shù)據(jù)重構(gòu)[J].計算機工程與應(yīng)用,2012,47(36):151-154.

[13] 蔡美玲,鄒北驥,辛國江.預(yù)選策略和重建誤差優(yōu)化的運動捕獲數(shù)據(jù)關(guān)鍵幀提取[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2012,24(11):1485-1492.

編輯 顧逸斐

Extraction of Motion Key-frame Based on Inter-frame Pitch

LI Shunyi1,HOU Jin1,2,GAN Lingyun1
(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China;
2.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093,China)

To solve the problem that the motion capture data has a large number of data redundancy,this paper proposes a key frame extraction method based on inter-frame pitch.In order to compress,storage,reconstruct and further reuse motion data,key-frame is needed to be extracted which represents the content of the motion.Quaternion is introduced to represent the difference between two rotations.The distance between two frames is defined by the total rotation differences and first frame is regarded as the first key frame.Then,calculate the difference between the current frame and the last key frame continuously.The frame is eliminated when the difference is smaller than the set threshold or the opposite is reserved for the new key frame.Spherical linear interpolation is used to reconstruct the sequence.To express the characteristics of human motion,the joint velocity is introduced.Reconstruction error is defined by the human body posture error of position and the motion speed error between the original frame and the reconstructed frame.Experimental result demonstrates that the original motion capture can be compressed in a high ratio and gives a good visual summary performance.

motion capture;key-frame extraction;inter-frame gap;spherical linear interpolation;reconstruction error; visual summary performance

李順意,侯 進,甘凌云.基于幀間距的運動關(guān)鍵幀提取[J].計算機工程,2015,41(2):242-247.

英文引用格式:Li Shunyi,Hou Jin,Gan Lingyun.Extraction of Motion Key-frame Based on Inter-frame Pitch[J]. Computer Engineering,2015,41(2):242-247.

1000-3428(2015)02-0242-06

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.046

國家自然科學(xué)基金資助面上項目(61371165);浙江大學(xué)CAD&CG國家重點實驗室開放課題基金資助項目(A1416);計算機軟件新技術(shù)國家重點實驗室開放課題基金資助項目(KFKT2013B22);四川省動漫研究中心2012年度科研基金資助項目(DM201204)。

李順意(1988-),男,碩士研究生,主研方向:人體動畫;侯 進(通訊作者),副教授;甘凌云,碩士研究生。

2014-03-24

:2014-05-05E-mail:jhou@swjtu.edu.cn