基于時(shí)間扭曲圖快速搜索的運(yùn)動(dòng)融合方法

鄭利平， 夏新宇， 王玉培

（合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

隨著信息技術(shù)的飛速發(fā)展，三維動(dòng)畫正在逐漸成為繼聲音、圖像、視頻和三維模型之后的第5種多媒體類型［1］。作為三維動(dòng)畫的重要組成，角色動(dòng)畫在影視制作、計(jì)算機(jī)游戲等應(yīng)用領(lǐng)域占據(jù)越來越重要的地位。為了得到形象逼真的角色動(dòng)畫，藝術(shù)、設(shè)計(jì)與計(jì)算機(jī)等領(lǐng)域的專家提出了很多的方法［2］。當(dāng)前最流行的是一種骨骼動(dòng)畫制作方式，將角色抽象成具有層次結(jié)構(gòu)的虛擬骨架結(jié)構(gòu)，在角色網(wǎng)格和相應(yīng)骨架之間建立蒙皮約束關(guān)系，并通過運(yùn)動(dòng)數(shù)據(jù)驅(qū)動(dòng)骨架，產(chǎn)生角色動(dòng)畫［3］。

角色動(dòng)畫制作目前主要有手動(dòng)設(shè)置關(guān)鍵幀和基于運(yùn)動(dòng)捕捉設(shè)備2種方法［4］。這2種方法生成動(dòng)作序列都費(fèi)時(shí)費(fèi)力，因此如何能夠重用這些數(shù)據(jù)，并在此基礎(chǔ)上派生出更加豐富多樣的運(yùn)動(dòng)，是當(dāng)前計(jì)算機(jī)動(dòng)畫領(lǐng)域研究的重要內(nèi)容之一，運(yùn)動(dòng)融合是運(yùn)動(dòng)重用的一個(gè)重要手段之一，該技術(shù)能夠根據(jù)多個(gè)已經(jīng)存在的運(yùn)動(dòng)數(shù)據(jù)，通過一定的手段，將它們的數(shù)據(jù)疊加在一起［5］。融合運(yùn)動(dòng)繼承了原運(yùn)動(dòng)序列的主要特征，并且能夠在各個(gè)運(yùn)動(dòng)之間平滑過渡［6］。

本文提出一種基于時(shí)間扭曲圖快速搜索的運(yùn)動(dòng)融合方法，通過對動(dòng)態(tài)時(shí)間扭曲（Dynamic Time Warping，簡稱DTW）加以一定規(guī)則的約束，快速地找到對齊幀，構(gòu)造出運(yùn)動(dòng)序列之間的時(shí)間扭曲圖，實(shí)現(xiàn)不同運(yùn)動(dòng)序列的時(shí)間配準(zhǔn)以及對應(yīng)姿態(tài)的融合。實(shí)驗(yàn)結(jié)果表明，該方法提高了搜索的效率，有很好的視覺效果，而且具有很好的靈活性和實(shí)用性。

1 相關(guān)工作

從技術(shù)的角度，當(dāng)前對運(yùn)動(dòng)融合的研究主要可分為2類：

（1）信號處理方法。文獻(xiàn)［7］在頻域中采用傅里葉分析技術(shù)對運(yùn)動(dòng)數(shù)據(jù)進(jìn)行內(nèi)插和外插的方法，對真實(shí)的運(yùn)動(dòng)數(shù)據(jù)作傅里葉展開，來實(shí)現(xiàn)對運(yùn)動(dòng)的插值，其關(guān)節(jié)角的軌跡使用頻域中的傅里葉來表示。文獻(xiàn)［8］使用時(shí)空優(yōu)化的方法，最小化關(guān)節(jié)角的轉(zhuǎn)矩，實(shí)現(xiàn)一個(gè)運(yùn)動(dòng)片段到另一運(yùn)動(dòng)片段的過渡。文獻(xiàn)［9］將運(yùn)動(dòng)看成信號，采用多分辨率運(yùn)動(dòng)過濾、時(shí)間變形、多目標(biāo)運(yùn)動(dòng)插值、運(yùn)動(dòng)波形變換和偏移映射等運(yùn)動(dòng)信號處理方法，對運(yùn)動(dòng)數(shù)據(jù)進(jìn)行混合，生成各種多樣化的運(yùn)動(dòng)。

（2）參數(shù)化實(shí)例運(yùn)動(dòng)方法。該方法的主要思想是先使用權(quán)值計(jì)算函數(shù)量化運(yùn)動(dòng)實(shí)例，然后在此基礎(chǔ)上對運(yùn)動(dòng)庫中的運(yùn)動(dòng)序列混合、過渡等。該方法主要經(jīng)歷了2個(gè)階段：① 使用權(quán)值計(jì)算函數(shù)量化運(yùn)動(dòng)實(shí)例，來生成連續(xù)的運(yùn)動(dòng)序列［10］，并在此基礎(chǔ)上使用運(yùn)動(dòng)圖的方法實(shí)現(xiàn)運(yùn)動(dòng)的過渡。由于采用的權(quán)值計(jì)算函數(shù)較為隨意，計(jì)算出的權(quán)值與實(shí)際期望的權(quán)值可能有較大的差異，因此生成的運(yùn)動(dòng)不逼真；② 在以往研究工作的基礎(chǔ)上，文獻(xiàn)［11］采用改進(jìn)的權(quán)值計(jì)算函數(shù)，使得運(yùn)動(dòng)實(shí)例的權(quán)值計(jì)算更準(zhǔn)確，與實(shí)際期望的權(quán)值更接近。

動(dòng)態(tài)時(shí)間扭曲最早應(yīng)用在語音識別中，該算法基于動(dòng)態(tài)規(guī)劃（Dynamic Programming，簡稱DP）的思想，解決了發(fā)音長短不一的模板匹配問題，是語音識別中較為經(jīng)典的一種算法，一些研究學(xué)者將DTW算法應(yīng)用于運(yùn)動(dòng)融合領(lǐng)域。文獻(xiàn)［9］中創(chuàng)建一個(gè)距離矩陣柵格，采用全局優(yōu)化算法計(jì)算得到一條最優(yōu)路徑，但是該方法時(shí)間復(fù)雜度非常高，是輸入運(yùn)動(dòng)序列幀數(shù)的指數(shù)級。文獻(xiàn)［11］為了避免求解的復(fù)雜度，對DTW做了改進(jìn)，并通過固定一些較為重要的關(guān)節(jié)的權(quán)重值，生成了更加平滑的運(yùn)動(dòng)?？梢哉J(rèn)為將DTW算法應(yīng)用到動(dòng)作序列對齊就是要尋找一個(gè)最佳的時(shí)間規(guī)整函數(shù)，使運(yùn)動(dòng)片段A的時(shí)間軸i非線性映射到運(yùn)動(dòng)片段B的時(shí)間軸j，并使總的累積失真量最?。?2］。

如果源運(yùn)動(dòng)序沒有相似的周期性和對應(yīng)關(guān)系，比如騎馬和芭蕾2個(gè)動(dòng)作，則融合出新的運(yùn)動(dòng)序列是毫無意義的。因此，本文只考慮運(yùn)動(dòng)融合后能產(chǎn)生有實(shí)際意義的動(dòng)作，即具有一定相似性的源運(yùn)動(dòng)序列。相似運(yùn)動(dòng)可能會(huì)有不同的時(shí)間分布。例如，在行走運(yùn)動(dòng)中，連續(xù)2次腳著地的時(shí)間間隔明顯比跑步運(yùn)動(dòng)中的腳著地時(shí)間長得多。所以，對于2個(gè)運(yùn)動(dòng)序列必須進(jìn)行相應(yīng)的拉伸或縮短以使得對應(yīng)幀匹配。在運(yùn)動(dòng)融合過程中，幀對應(yīng)關(guān)系對于生成的最終融合運(yùn)動(dòng)效果十分重要，如果沒有建立合適的幀對應(yīng)關(guān)系，就無法得到自然協(xié)調(diào)的融合效果［13］。而時(shí)間扭曲（Time Warping）可使2段運(yùn)動(dòng)序列的幀之間建立一一對應(yīng)關(guān)系，且具有相同的持續(xù)時(shí)間，從而使融合后的運(yùn)動(dòng)更加協(xié)調(diào)、自然。

一般來說，使用DTW算法在尋找對齊幀時(shí)運(yùn)算量較大而且時(shí)間復(fù)雜度很高，因此提高對齊的效率是很有必要的。根據(jù)融合運(yùn)動(dòng)序列的特征，本文對DTW算法搜索對齊幀做了改進(jìn)，因?yàn)檫\(yùn)動(dòng)序列具有一定的相似性，可以采用局部搜索的方式，再給予一定的規(guī)則約束，構(gòu)造時(shí)間扭曲曲線，降低求解的時(shí)間復(fù)雜度。本文通過計(jì)算幀間距找出2段運(yùn)動(dòng)序列中的相似幀，再由相似幀構(gòu)造時(shí)間扭曲曲線C（v），建立幀對應(yīng)關(guān)系，對應(yīng)幀的姿態(tài)融合，并重構(gòu)根關(guān)節(jié)的運(yùn)動(dòng)軌跡。

2 動(dòng)態(tài)時(shí)間扭曲

2.1 計(jì)算幀間距

文獻(xiàn)［11］定義了一種幀間距計(jì)算公式，依此判斷兩幀的相似性，但是該距離公式以關(guān)節(jié)在世界坐標(biāo)系的位置為度量標(biāo)準(zhǔn)，因此受角色根關(guān)節(jié)運(yùn)動(dòng)軌跡的影響，從而使得計(jì)算誤差較大。為了克服以上不足，本文以關(guān)節(jié)旋轉(zhuǎn)變化計(jì)算幀間距，將幀間距計(jì)算局部化；而且本文的運(yùn)動(dòng)信息是以四元數(shù)表示的，因此可以很方便地用四元數(shù)夾角表示關(guān)節(jié)旋轉(zhuǎn)變化。

一個(gè)有m個(gè)關(guān)節(jié)的角色，計(jì)算其運(yùn)動(dòng)中2幀Μi、Μj的幀間距D（Μi，Μj），方法如下：

（1）分別以Μi、Μj為中心提取相鄰的2W＋1幀，即窗口大小為2W＋1，如果窗口中的幀數(shù)小于2W＋1，則以中心幀填充之。

（2）任意2幀Μi、Μj的姿態(tài)距離P（Μi，Μj）定義為：

其中，αs（s＝1，2，…，m）為相應(yīng)關(guān)節(jié)的加權(quán)系數(shù)，

（3）幀間距D（Μi，Μj）定義為窗口內(nèi)各個(gè)對應(yīng)姿態(tài)距離的加權(quán)之和，即

其中，ωk為窗口中各幀的權(quán)重值顯然位于窗口中心處的幀權(quán)重大于邊緣處的幀權(quán)重。

任意2幀的間距得到之后，就可構(gòu)造時(shí)間扭曲曲線，將運(yùn)動(dòng)序列對齊。

2.2 構(gòu)造時(shí)間扭曲曲線

假設(shè)待融合的運(yùn)動(dòng)序列為M1、M2，其采樣頻率相同，幀數(shù)分別為n1、n2，組成一個(gè)n1×n2的柵格矩陣，單元格（i，j）表示幀對（Μ1（i），Μ2（j））。對運(yùn)動(dòng)序列使用DTW算法，以幀間距為度量標(biāo)準(zhǔn)，在柵格矩陣中尋找出一條優(yōu)化路徑，使得路徑中所有對應(yīng)幀的間距之和最小。最簡單的做法是將其中一個(gè)運(yùn)動(dòng)中的一幀與另外一個(gè)運(yùn)動(dòng)序列中的每一幀計(jì)算幀間距，然后組合找出最優(yōu)解。這種方法可以找到一個(gè)全局最優(yōu)路徑，但是時(shí)間復(fù)雜度高。根據(jù)運(yùn)動(dòng)序列具有的特征，采用一種較為快速的路徑搜索方案，同時(shí)可以保證得到的路徑較為優(yōu)化。

為此，定義在路徑搜索中需遵循3條規(guī)則：

（1）連續(xù)性。路徑上的每個(gè)單元格必須與其相鄰的單元格共點(diǎn)或共邊。一條不滿足連續(xù)性的路徑如圖1a所示。

（2）非遞減性。為了保證路徑搜索能夠結(jié)束，規(guī)定路徑必須始終保持向右或向上延伸。一條不滿足非遞減性的路徑如圖1b所示。

（3）傾斜度限制。在水平或者垂直方向上最多只能連續(xù)有L個(gè)單元格。一條不滿足傾斜度限制（L＝3）的路徑如圖1c所示。

圖1 路徑規(guī)則示意圖

為了保證2個(gè)運(yùn)動(dòng)序列的所有幀均能被時(shí)間扭曲，規(guī)定路徑的起始點(diǎn)B為柵格矩陣的左下角單元格，終止點(diǎn)E為柵格矩陣的右上角單元格。設(shè)D（i，j）表示單元格（i，j）對應(yīng)的幀間距，且D（i，j）≥0，v（i，j）表示從起始點(diǎn)B到（i，j）的距離。顯然，只要D（i，j）＞0，在柵格路徑中，先水平向右，然后再垂直向上（或先垂直向上，然后水平向右）的代價(jià)比傾斜向上的路徑代價(jià)要大（最好的情況是兩者代價(jià)相等）。所以，在路徑搜索過程中，做如圖2所示的路徑優(yōu)化，進(jìn)一步縮小了路徑搜索的范圍。為了滿足以上定義的3條規(guī)則，單元格（i，j）的下一個(gè)可能位置最多有2L－1個(gè)。當(dāng)L＝4時(shí)，下一個(gè)可選單元格的位置分布情況如圖3所示。因此，可得出v（i，j）的計(jì)算公式為：

圖2 路徑優(yōu)化示意圖

圖3 下一個(gè)可選單元格

從起始點(diǎn)B開始，根據(jù)（3）式計(jì)算v（i，j），一直搜索到終止點(diǎn)E，即可構(gòu)造一條時(shí)間扭曲曲線C（v）。

3 運(yùn)動(dòng)合成

通過時(shí)間扭曲曲線建立了運(yùn)動(dòng)序列之間的幀對應(yīng)關(guān)系，依次將對應(yīng)幀的姿態(tài)進(jìn)行融合、插值，即可得到融合的運(yùn)動(dòng)。以幀數(shù)較大的運(yùn)動(dòng)序列作為模板運(yùn)動(dòng)，另一運(yùn)動(dòng)序列通過時(shí)間扭曲曲線與模板運(yùn)動(dòng)對應(yīng)。所以，融合后運(yùn)動(dòng)序列的幀數(shù)與模板運(yùn)動(dòng)的幀數(shù)一致。

即使找到了運(yùn)動(dòng)序列的相似幀，對于線性融合也可能會(huì)失敗。例如，2個(gè)行走運(yùn)動(dòng)的融合，其中一個(gè)運(yùn)動(dòng)是向左走動(dòng)，另一個(gè)是向右走動(dòng)，本來希望融合后的運(yùn)動(dòng)是向前行走，但通常的姿態(tài)融合方法會(huì)使得路徑坍塌，造成運(yùn)動(dòng)不連續(xù)。之所以會(huì)造成運(yùn)動(dòng)路徑的坍塌，是因?yàn)閷τ谕ǔ５男D(zhuǎn)角度插值方法（如球面線性插值），當(dāng)旋轉(zhuǎn)角度變化大于180°時(shí)會(huì)出現(xiàn)插值不連續(xù)。為了解決這一問題，本文使用一種簡便可行的方法，將運(yùn)動(dòng)的局部姿態(tài)與運(yùn)動(dòng)路徑（即角色根關(guān)節(jié)運(yùn)動(dòng)軌跡）分離，然后分別進(jìn)行融合，最后再通過后處理將其合成完整的角色運(yùn)動(dòng)。

3.1 局部姿態(tài)融合

忽略角色根關(guān)節(jié)的運(yùn)動(dòng)軌跡，局部姿態(tài)完全可用四元數(shù)集合表示。因此，局部姿態(tài)融合轉(zhuǎn)化為四元數(shù)的插值。經(jīng)典的四元數(shù)插值為球面線性插值，主要是在對四元數(shù)各個(gè)分量分別插值，然后重新規(guī)則化使其滿足約束條件i2＝j(luò)2＝k2＝－1。但是，重新規(guī)則化會(huì)造成扭曲和單一化的副作用，從而影響動(dòng)畫品質(zhì)。為了避免重新規(guī)則化，本文采用基于指數(shù)對數(shù)映射的四元數(shù)混合方法［14］。在四元數(shù)混合中，引入?yún)⒖妓脑獢?shù)q＊，定義為距離q1、q2最近的四元數(shù)，它又被稱之為四元數(shù)均值。通過對數(shù)映射將q轉(zhuǎn)換成線性向量v，若說明q＊與q不在同一半球面上，可令q＝－q。通過指數(shù)映射q＝q＊ev再將v轉(zhuǎn)換為相應(yīng)的四元數(shù)。依次對兩運(yùn)動(dòng)序列相似幀中的每個(gè)關(guān)節(jié)旋轉(zhuǎn)數(shù)據(jù)進(jìn)行四元數(shù)混合，合成連續(xù)的局部運(yùn)動(dòng)姿態(tài)。

3.2 重構(gòu)根關(guān)節(jié)運(yùn)動(dòng)軌跡

局部姿態(tài)融合過程中，沒有考慮角色運(yùn)動(dòng)路徑，忽略了根關(guān)節(jié)的位移，所以角色只是在原地運(yùn)動(dòng)。為了使角色隨著姿態(tài)的變化而不斷改變位置，需重構(gòu)角色根關(guān)節(jié)運(yùn)動(dòng)軌跡。本文采用文獻(xiàn)［14］提出的方法求解插值后的根關(guān)節(jié)位置。

4 實(shí)驗(yàn)結(jié)果與分析

以120幀的恐龍行走與100幀的恐龍跑步為例，如圖4a所示，將它們進(jìn)行運(yùn)動(dòng)融合。首先，計(jì)算2運(yùn)動(dòng)序列的幀間距，設(shè)定傾斜度限制L＝5，構(gòu)造一條時(shí)間扭曲曲線，如圖5所示，采用灰度圖表示運(yùn)動(dòng)序列的幀間距，顏色越暗其間距越小，反之就越大。融合運(yùn)動(dòng)序列中的若干幀姿態(tài)如圖6所示。

圖4 恐龍的2個(gè)運(yùn)動(dòng)序列

圖5 幀間距的灰度圖表示及時(shí)間扭曲曲線

圖6 融合運(yùn)動(dòng)序列中的若干幀姿態(tài)

5 結(jié)束語

本文提出了一種基于時(shí)間扭曲圖快速搜索的運(yùn)動(dòng)融合方法，實(shí)現(xiàn)角色不同運(yùn)動(dòng)序列之間的融合，通過局部搜索和約束制約計(jì)算運(yùn)動(dòng)序列幀間距，構(gòu)造時(shí)間扭曲曲線，并對對應(yīng)姿態(tài)進(jìn)行局部融合，重構(gòu)角色根關(guān)節(jié)運(yùn)動(dòng)軌跡，合成角色最終的運(yùn)動(dòng)。本文提出的運(yùn)動(dòng)融合方法，適用于頻率不同的角色運(yùn)動(dòng)，融合生成的運(yùn)動(dòng)效果較好，滿足一定的視覺要求。但是在運(yùn)動(dòng)融合過程中難免會(huì)出現(xiàn)失真現(xiàn)象，所以，在融合過程中加入適當(dāng)?shù)募s束條件以避免運(yùn)動(dòng)失真是進(jìn)一步的研究重點(diǎn)。

［1］王 鑫，孫守遷，柴春雷.3維人體運(yùn)動(dòng)編輯與合成技術(shù)綜述［J］.中國圖象圖形學(xué)報(bào)，2009，14（2）：233－242.

［2］盧滌非，任文華，李國軍，等.基于樣例的交互式三維動(dòng)畫的生成［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（1）：62－71.

［3］Magnenat N，Laperrière R，Thalmann D.Jointdependent local deformations for hand animation and object grasping［C］／／Proceedings on Graphics Interface’88，Edmonton，Alberta，Canada，1988：26－33.

［4］Sturman D J.A brief history of motion capture for computer character animation［C］／／Character Motion System，SIGGRAPH 94：Course 9.

［5］鄭利平，王玉培，李 琳，等.基于運(yùn)動(dòng)峰值的動(dòng)畫角色肢體運(yùn)動(dòng)混合算法［C］／／計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)術(shù)會(huì)議（CADCG2010），2010：302－311.

［6］PolichroniadisT，Dodgson N.Motion blending using a classifier system［C］／／Proceedings of the 7th International Conference in Central Europe on Computer Graphics，Visualization and Interactive Digital Media’99（WSCE＇99），University of West Bohemia，Plzen，Czech Republic，1999：225－232.

［7］Unuma M，Anjyo K，Takeuchi R.Fourier principles for e－motion－based human figure animation［C］／／Proceedings of ACM SIGGRAPH 95，1995：91－96.

［8］Rose C，Guenter B，Bodenheimer B，et al.Efficient generation of motion transition using space time constrains［C］／／Proceedings of ACM SIGGRAPH 96，1996：147－154.

［9］Bruderlin A，Williams L.Motion signal processing［C］／／Proceedings of ACM SIGGRAPH 95，1995：97－104.

［10］Park S I，Shin H J，Shin S Y.On－line locomotion generation based on motion blending［C］／／Proceedings of ACM SIGGRAPH，2002：105－111.

［11］Kovar L，Gleicher M.Automated extraction and Parameterization of motions in large data sets［C］／／ACM Transaction on Graphics，2004，23（3）：559－568.

［12］朱登明，王兆其.基于動(dòng)作單元分析的人體動(dòng)畫合成方法研究［J］.計(jì)算機(jī)研究與發(fā)展，2009，46（4）：610－617.

［13］Hecker C，Raabe B，Enslow R W.Real－time motion retargeting to highly varied user－created morphologies ［C］／／Proceedings of ACM SIGGRAPH’08，2008：1－11.

［14］Lau M，Kuffner J.Behavior planning for character animation［C］／／Proceedings of ACM SIGGRAPH／Eurgraphics SIGGRAPH Symposium on Computer Animation，Los Angles，2005：271－280.