鄭利平， 夏新宇， 王玉培

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 動態(tài)時間扭曲

2.1 計算幀間距

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

一個有m個關節(jié)的角色，計算其運動中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）為相應關節(jié)的加權(quán)系數(shù)，

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

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

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

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

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

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

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

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

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

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

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

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

圖3 下一個可選單元格

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

3 運動合成

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

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

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

忽略角色根關節(jié)的運動軌跡，局部姿態(tài)完全可用四元數(shù)集合表示。因此，局部姿態(tài)融合轉(zhuǎn)化為四元數(shù)的插值。經(jīng)典的四元數(shù)插值為球面線性插值，主要是在對四元數(shù)各個分量分別插值，然后重新規(guī)則化使其滿足約束條件i2＝j2＝k2＝－1。但是，重新規(guī)則化會造成扭曲和單一化的副作用，從而影響動畫品質(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)換為相應的四元數(shù)。依次對兩運動序列相似幀中的每個關節(jié)旋轉(zhuǎn)數(shù)據(jù)進行四元數(shù)混合，合成連續(xù)的局部運動姿態(tài)。

3.2 重構(gòu)根關節(jié)運動軌跡

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

4 實驗結(jié)果與分析

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

圖4 恐龍的2個運動序列

圖5 幀間距的灰度圖表示及時間扭曲曲線

圖6 融合運動序列中的若干幀姿態(tài)

5 結(jié)束語

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

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

［2］盧滌非，任文華，李國軍，等.基于樣例的交互式三維動畫的生成［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］鄭利平，王玉培，李 琳，等.基于運動峰值的動畫角色肢體運動混合算法［C］／／計算機輔助設計與圖形學學術(shù)會議（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］朱登明，王兆其.基于動作單元分析的人體動畫合成方法研究［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.