一種基于索引空間的三維運動捕獲數據檢索方法

徐從洋 徐江峰

(鄭州大學信息工程學院 河南 鄭州 450001)

一種基于索引空間的三維運動捕獲數據檢索方法

徐從洋 徐江峰

(鄭州大學信息工程學院 河南 鄭州 450001)

為能有效檢索當前大量的三維人體運動捕獲數據從而投入使用，針對三維人體運動捕獲數據的獨有特性，提出一種高效的檢索方法。首先通過關鍵幀提取對原始運動數據降維，然后采用自定義的符合人體運動語義的特征將原始角度數據轉換為特征序列。根據數據庫中所有運動片段對應的特征序列構建一種基于姿態特征的索引空間。檢索時通過在索引空間上順序匹配姿態特征來查找時序一致的匹配運動片段。實驗結果表明，與大多數現有方法相比，該方法由于較好的運動語義特征提取，因此具有更好的時間效率，更高的靈活性和檢索精度，能夠滿足多種運動數據的檢索需要。

運動捕獲數據 運動檢索 特征提取 索引空間

0 引 言

近年來，隨著三維人體運動捕獲技術的日益成熟以及多媒體技術的快速發展，大量的視覺真實感強、富有表現力的人體運動捕獲數據被錄制保存，并被有效地應用在了三維動畫、電影制作和游戲等產業中。然而大量的運動捕獲數據同時也增加了其被有效管理和重用的難度。因此，如何對運動數據庫進行精確高效的檢索成為了該領域的重要研究目標。

當前的運動檢索方法主要有基于運動模板匹配、基于內容、基于索引和動態時間彎曲等方法[10]。基于內容的檢索[13]因其能從運動數據本身充分提取描述運動的信息，從而設計出高效自動的運動檢索方法的特征，被目前研究人員廣泛使用[11]。本文的方法也是基于內容的運動捕獲數據檢索方法。

基于內容的檢索方法主要包括兩個技術難點：

(1) 運動數據的特征提取

原始運動捕獲數據如BVH格式數據采用人體各關節相對于父關節旋轉角度和整體偏移量描述運動姿態，高采集頻率幀描述運動軌跡，構成了一個較大的二維原始數據空間。并且自然人體運動具有很大的靈活性,因而具有較高的自由度,導致人體運動特征的表示和描述存在較大的困難。因此，面對運動數據高時間、空間復雜度，找到一種有效的特征表示方法，對于數據降維和提高檢索效率具有重大意義。

關鍵幀方法如潘紅等[7]首先根據運動數據定義簡單特征，然后提取關鍵幀代表整個運動時序序列，該方法對原數據有效降維但特征提取不夠完善。聚類方法[2,9]以層次化方式描述運動，將相似的運動數據歸類并提取特征值，用特征值集合表示運動。Wu等[2]、Deng等[9]將整個人體劃分為幾部分，并對每部分進行聚類。Chao等[4]使用了一組正交球面諧波基函數來代表運動軌跡，并將調和函數系數作為編碼結果，提供了一種直觀的規格化查詢方法，但不能捕捉到人體運動的動態性。Barnachon等[1]用運動圖中的關鍵路徑代表運動片段。Wang等[6]使用局部線性回歸模型學習多個拉普拉斯算子圖以保留運動數據的局部幾何結構，然后將這些圖結合起來互補特征信息。Kapadia等[3]根據特定各肢體之間以及肢體與環境之間的關系自定義特征，這樣做比直接幀間對比更節省運行時間且有很好檢索效果。其中文獻采用Laban運動分析定義了一組可以表示人體結構、幾何與動態特征的運動鍵值來編碼運動。

(2) 索引與相似度匹配

特征提取后如何構建索引結構是保證相似度匹配高效性、準確性、靈活性的前提。良好的索引結構應具有緊湊、獨立于數據庫大小、容易更新和支持子序列與模糊查找等特性。相似度匹配是運動檢索最后的階段，算法應具有良好的時間空間復雜度，并且能夠在數值相似和邏輯相似之間找到一個合理的折中，從而得到符合用戶需求的檢索結果。

藍榮祎等[5]將人體結構分上下兩部分，分塊對所有運動片段提取關鍵姿態并通過AP聚類找出具有代表性的關鍵姿態，然后將運動片段轉換成運動文檔后通過向量空間模型對數據進行檢索。Deng等[9]建立身體各部分分層表示的運動序列索引表，然后使用快速字符串匹配算法進行運動序列的匹配。潘紅等[7]在檢索過程中構建距離矩陣求得運動片段間的相似度從而實現檢索，需要在每次檢索時消耗大量時間計算匹配路徑與相似度。Kapadia等[3]建立單詞查找樹，然后用正則表達式表示樣本特征與樹中特征序列對比，但需要建立大量樹才能對應所有特征并且需要檢索時有一定先驗知識。

本文采用參考Laban運動分析自定義的特征描述人體肢體之間以及肢體與環境之間的關系，利用特征值組合表示不同運動姿態從而構建一個與運動時序相關的索引空間，依據此索引空間可以完成快速且準確的運動檢索。

1 運動特征定義與提取

根據Laban運動分析LMA( Laban Movement Analysis)[Laban 1971]定義，人類運動中包含很多特性：(1)結構特性和物理特性；(2)動作的動態性與意圖；(3)運動中的人體形態。索引運動數據庫的一個基本要求就是需要包含這些運動特性，盡可能全面而精煉的特征能夠更好地描述動作，提高檢索結果準確率。

我們先根據人體結構劃分出一組身體軀段S，如圖1所示。然后定義了一組布爾型運動特征F(p)={fk(p)}(k對應特征序號)，其中每個特征對應動作姿態p的一個特定動作特性，不同的特征由不同的身體軀段集合計算而來。雖然每個運動特征fk(p)對應的是一個關鍵幀姿態pj，但有些運動特征如關節瞬時速度是根據一定范圍[j-Δ,j+Δ]內相鄰幀計算出來的，因此保留了運動的動態性。

圖1 人體骨骼分段模型

我們參照Laban運動分析將特征集合主要分為身體特征、動力學特征和外形特征。

(1) 身體特征主要描述人體運動的結構和幾何特征，這個類別可以幫助識別人體哪一部分在移動，哪些部位間有接觸和人體部位運動的模式。在這部分特征的定義中，我們考慮到了人體一些關節的自由度通常小于3，因此一些不太可能出現的姿態特征可以直接忽略以精簡特征空間。

動作表現 這個特征表示人體軀段在當前是否是運動的狀態，通過計算與相鄰姿態間的位移量是否超過閾值。此特征主要針對四肢和整體的位移。

(1)

相對位置 描述各肢體間相對位置，例如左右腿在身體平面的前或后面，在平面前特征值為1，否則為0。(如圖2(a)所示)此特征可描述身體各部位的位置狀態，是所定義特征中最重要且最多的部分。

朝向信息 表示人體上下兩部分相對于基礎姿態時的朝向是否有大的變化。此特征可以描述例如轉身等朝向信息有變化的運動。

(2)

肢體間接觸信息 計算各肢體是否接觸(兩肢體之間距離是否小于閾值)，例如左右胳膊的分開與合并，可以更精確地區分動作。

(3)

夾角信息 計算當前姿態中四肢的夾角和人體上下兩部分間的夾角是否小于閾值，例如可以通過大腿和小腿之間以及上半身和下半身之間的這一夾角特征判斷人是直立還是蹲下(如圖2(b)所示)。

(4)

其余還有中心位移、重心偏向和支撐點等特征。

(2) 動力學特征更多描述動作的邏輯動態性，同樣的一個身體姿態可能是由兩個語義完全不同的動作表現出來。例如向前伸手的動作，輕緩地遞東西與憤怒地推搡在語義上完全不同，這是僅幾何位置特征所不能表現的。參照Laban運動分析分為四個動力學特征：空間、力度、時間和平滑度。

空間 空間特征區分運動軌跡是直線或非直線，由當前姿態與前Δ幀區間的距離比率計算而來的。

(5)

力度 力度特征主要區分運動是猛烈的還是輕緩的。通常猛烈運動的特點是速度值由大到小變化非常快，減速明顯；而輕緩的運動速度平均，減速較慢甚至沒有。

(6)

時間 時間特征與力度特征相對應，根據運動速度由小到大變化快慢區分運動是突然的還是穩步變化的。此特征和力度特征一起可以詳細描述動作從靜止開始到運動再到靜止結束的整個過程的風格。例如急切的敲門表現為突然和猛烈的，而原地起跳表現為突然和輕緩的。

平滑度 描述運動在一定時間范圍內的連續性，體現在運動速度曲線是否在時間范圍[j-Δ,j+Δ]內存在多個波峰波谷，即加速與減速切換是否頻繁。

(3) 外形特征描述人體運動姿態的輪廓，特征主要定義人整體與四肢的不同外形狀態。(如圖2(c)所示)

(7)

圖2 特征定義示例

2 索 引

經過第1節所描述的關鍵幀提取和自定義特征提取，原始運動數據得到了有效的降維和邏輯特征表示，每個運動姿態pj轉化成了一個對應的布爾特征值序列F(pj)=f1(pj)f2(pj)…fk(pj)，而運動片段則可表示為特征序列集合：mi:={F(p1),F(p2),…,F(pn)}。由于一個特征序列代表特征相同的一類動作，因此我們得到了一個基于整個數據庫的姿態特征空間，而每一個運動片段則可理解為空間中一些姿態按時序順序的連接，如圖3所示。

由此，我們定義了特征空間來索引整個運動數據庫。對于一個運動姿態，其對應的布爾特征值序列可以作為該姿態在索引空間中的索引號，將該姿態特征序列與對應某特征位為1，其余位為0的序列相與，即可得到該姿態在某特征的值。在特征提取階段，記錄每個姿態所在的運動片段序號和對應幀序號，作為該姿態的索引信息。最后將所有姿態按布爾特征值大小排序，順序存儲。由此可以看出，索引空間將數據庫中所有運動片段的不同姿態提取出來，同時包含了每個姿態在運動片段中的信息。而索引空間的更新(通常為增加信息)也非常容易，直接插入一個新的運動姿態及索引信息或只增加已有姿態的新索引信息即可。

圖3 運動片段匹配索引空間

根據定義的索引結構的特點，可以很方便地實現運動子序列匹配，模糊查找等常見檢索需求。

子序列匹配 當輸入查詢運動片段時，其有可能是數據庫中某些長運動片段的子序列。在檢索中，通過查詢運動片段的第一關鍵幀姿態對應的特征值序列可以快速定位到索引空間中的相似姿態，即找到查詢運動片段在長運動片段中相匹配的開端。

模糊查找 當用戶需要與查詢運動片段部分特征相似而非完全一致的運動數據時，可以通過指定部分特征要求匹配。指定特征越少，相匹配的就越多。

實時查找 由于構建索引空間是線下完成，并且檢索時可以并發查找多個相似運動，因此檢索速度快，能實現實時查找。

3 檢 索

根據以上的特征提取與索引空間定義，我們結合折半查找算法和姿態特征匹配實現檢索。在算法描述前，首先給出一些定義說明。

輸入包括特征向量表示的查詢運動片段Q，用戶指定的需匹配特征sf和姿態索引空間FIndexSpace。其中sf轉換為一個指定特征位為1，其余位為0的二進制序列。假如全部特征數為10，指定必須匹配的特征位為0、1、3、6、7(以0開始，從左向右)，則sf=1101001100。在查找中兩特征序列分別和sf相與后值相等即為匹配。定義每次查找得到的運動片段集合M0和當前總命中運動片段集合Mh，記錄匹配到的運動片段序號，命中次數以及幀序號。

算法描述如下：

Step3：如果mj∈M0∧mi?Mh，將mi直接合并入Mh，記錄其幀序號并置其命中次數為1；

Step4：如果mi∈M0∧mi∈Mh，比較mi在M0中的幀序號f0和在Mh中的最后一次命中的幀序號fh：如果f0>fh，將mi合并入Mh并將其命中次數加1；否則將Mh中對應mi的命中次數減1；

Step5：如果Q還有下一幀，轉至Step2；否則除去Mh中命中次數小于Q關鍵幀長度50%的運動片段，所得Mh即為最終檢索結果。

算法中使用折半查找在姿態空間中找到與查詢片段Q中某一幀相匹配的姿態，并可以按照第2節索引結構的定義得到匹配姿態所在運動數據庫中的運動片段集合，表示為該查詢姿態在這些運動片段中出現。由此知當命中同一運動片段次數越多，表示該運動片段與查詢片段Q越相似。同時記錄匹配姿態的幀序號，每次命中下一幀時比較幀序號是否按照升序排列，保證檢索結果與Q時序一致。最后排除只有少數幀與Q時序一致的運動片段，所得結果按命中次數排序即為與Q相似度由大到小的運動檢索結果。

由于Q中每一幀只在索引空間中查找一次，避免了運動的重復匹配。檢索結果中包含匹配運動片段中第一幀命中Q的幀序號，因此可以實現子序列匹配的首幀定位。

4 實驗結果與分析

本文實驗數據包括卡內基梅隆大學人體運動捕獲數據庫[12]的共約400個運動片段，分為8類，如表1所示。所有運動捕獲數據關節數為23，幀頻率為24 fps，運動片段長度為40幀到5 000幀不等。我們使用C++開發出一個檢索系統，實現檢索前的運動數據預處理和檢索時的整個過程。實驗中系統運行在Intel P4 2.7 GHz CPU和2 GB內存的PC機上。

表1 實驗數據庫運動數據分類

4.1 運動數據預處理階段

運動數據預處理即為對原始運動數據集進行檢索前的線下處理，包括關鍵幀提取，特征提取和構建索引空間三個步驟。

1) 考慮到線下處理的要求，我們采用計算量大但更準確穩定的劉云根等[8]的重建誤差最優化的關鍵幀提取方法。實驗通過文中方法對所有原始運動數據提取關鍵幀，不同動作的最優壓縮率不同，簡單緩慢的動作最優壓縮率高，而復雜猛烈的動作最優壓縮率較低。如緩慢行走的壓縮率平均為7%，而舞蹈的壓縮率平均為16%。最終所有運動數據提取過后的總幀數為40 238幀，總平均壓縮率為約11%，可以看出大大減少了后期對運動數據處理的量。

2) 本文第1節共定義了36個布爾特征，因此特征提取階段會將運動片段的每一關鍵幀轉換為一個長度為36的布爾序列，對應值范圍為[0，236]。最終將每個運動片段轉化為一個特征向量。

3) 構建索引空間將所有特征向量的每個特征提取出來，記錄下所在運動片段的序號和幀序號，并將所有特征排序。由特征定義可知索引空間大小不會超過236，但實際中由于一些常見的姿態如直立不動，普通的慢走等會重復出現在多個不同的運動中(如圖中兩個峰值)；同時一些特征定義中理論上的姿態基本不會出現，因此最終的索引空間會遠小于236。本實驗中，最終提取的不同特征值共31 386個，特征分布與姿態重復度如圖4所示。根據運動數據集的不同，姿態重復的多少有無和峰值的分布會有所不同，但基本會體現為少數幾個姿態重復度較高，而大部分姿態只出現一到幾次。最終雖然減少的重復姿態不多，但是在檢索一些有重復動作的運動片段時仍能有效減少檢索階段對相同姿態的重復比較。

圖4 特征分布與姿態重復度

4.2 檢索階段

線下構建好索引空間后，即可通過輸入查詢片段并指定需匹配特征進行線上檢索。其中查詢片段也要通過關鍵幀提取和特征提取轉化為特征向量。根據第3節對檢索算法的描述，得到部分實驗結果如圖5-圖7，并按相似性高低從上到下排序。

圖5第一行為用戶輸入的查詢運動片段“走”，并指定兩腿的相對位置特征、身體運動特征匹配走的形態，指定兩腿力度特征來區別于跑步運動。圖5(a)-(e)為數據庫中運動“走”的幾類檢索結果。可以看出指定特征較少時，檢索結果為“走”的模糊查找結果。但同時檢索結果類別間相差比較大，則可以通過指定更多的特征來更精確化檢索。圖5(a)為最近似于查詢運動的結果；圖5(b)為愉悅地走路，身體有大幅度上下擺動，可通過附加中心位移特征去除此類走的結果；圖5(c)為雙臂水平向后張開走路，可通過附加匹配胳膊的相對位置特征去除；圖5(d)為轉圈走，運動軌跡為非直線，可通過簡單地附加身體空間特征去除。

圖6第一行為查詢運動片段，描述為“從坐到站起直走”。除了上述對走的特征指定外，還指定了身體上下部分夾角和兩腿的夾角特征以及外形特征。圖6(a)為最接近的檢索結果；圖6(b)為站起來時轉彎走，因此可通過附加身體空間特征去除；圖6(c)為翹起腿坐并將一只手放在腿上，可以通過附加肢體間接觸信息特征去除；圖6(d)為迅速站起走，可通過附加時間特征去除；圖6(e)為醉酒下的從坐到走，表現為身體來回擺動，并且動作不穩，因此可附加重心偏向和平滑度特征去除。

圖7為反映子序列查詢的檢索，第一行為查詢片段“雙腿合并向前跳”，圖7(a)為匹配到的運動片段，然而其匹配的片段為圖7(b)“向前走后雙腿合并向前跳”運動片段開始于第39幀的子序列，即實現了子序列的匹配。

圖5 運動“走”檢索結果

圖6 運動“從坐到站起直走”檢索結果

圖7 運動“雙腿合并向前跳”子序列檢索結果

本文檢索算法在查找某一幀對應特征序列時使用折半查找搜索索引空間，查找時間復雜度log2n，n為姿態總數，最多為236，則每個特征序列查找次數最多為log2236=36。對于本文實驗環境，原始查詢運動片段為300幀時，查找平均時間為0.034 s。

為了對比不同算法在測試運動數據庫的檢索效果，圖8為各算法在多個運動類別上的P-R(precision-recall)曲線，可以看到由于本文算法通過特征提取將原始角度數值轉換成具有邏輯語義的特征值，并在檢索時適配查詢運動選擇要匹配的特征進行檢索，因此具有相對較好的查準率與查全率。文獻[3]方法構建字典樹并結合正則表達式檢索，提高了檢索速度。但由于每棵字典樹只對應一個特征，因此在匹配多棵字典樹后需要將結果合并，合并的過程不能保證特征之間的時序一致，而這也將提高錯誤匹配的幾率。文獻[7]定義八段骨骼角度特征對數據集比較敏感，不同風格的運動在匹配網絡中較難形成匹配路徑，因此會丟失一些語義相同但風格不同的匹配運動。并且文獻[7]每次檢索都需要通過大量計算來得到查詢運動與數據庫運動的相似度與匹配路徑，相對耗時。

本文對文獻[3]的特征定義進行改進并提出了一種新的索引構建和檢索方法，具有靈活、快速、準確檢索的特點，能夠運用在大規模運動數據庫檢索中。

圖8 多種方法在幾種不同運動類別上檢索結果的P-R對比

圖9所示為本文算法和文獻[3,7]在不同大小的運動數據庫上檢索時間的對比。實驗使用多個類型不同、長度均為300幀的查詢片段，將每種方法在同樣大小數據庫下的多次檢索時間求平均。由圖中可以看出，在運動數據庫較小時，三種方法的檢索時間基本一致，但隨著運動數據庫的增大，文獻[3]和文獻[7]方法的檢索時間都有明顯增加。文獻[7]由于每次檢索都有匹配路徑和相似度的計算開銷，因此檢索時間隨數據庫的增大增加尤為明顯，文獻[3]構建的單詞查找樹可以減少重復的匹配，但隨數據庫的增大，構建的樹會大量增加，因此檢索時間也有增加。而本文方法由于構建了與數據庫大小無關的索引空間，而檢索是在索引空間上進行的，因此數據庫的增大對本文算法的檢索時間沒有太大影響。

圖9 多種方法在不同數據庫大小下的檢索時間

5 結 語

本文提出一種新的運動捕獲數據檢索方法，通過關鍵幀提取和自定義的特征提取對運動數據進行有效降維，然后定義了一種記錄運動數據庫中所有運動姿態分布信息的索引空間；在檢索階段采用快速查詢索引空間進行運動片段的匹配。本文方法構建的索引空間不依賴于數據庫的大小且修改容易，檢索時通過靈活地指定特征匹配可以進行不同精確程度的匹配，因此具有很好的檢索性能和效果。

由于在檢索時唯一的參數“需匹配特征”的指定會影響到檢索結果，需要用戶具有一定的先驗知識，因此下一步我們的目標是自適應地針對不同類別運動匹配其突出的運動特征，達到智能檢索的目的。

[1] Barnachon M, Bouakaz S, Boufama B, et al. A real-time system for motion retrieval and interpretation[J]. Pattern Recognition Letters, 2013, 34(15): 1789-1798.

[2] Wu S, Wang Z, Xia S. Indexing and retrieval of human motion data by a hierarchical tree[C]//Proceedings of the 16th ACM Symposium on Virtual Reality Software and Technology, 2009: 207-214.

[3] Kapadia M, Chiang I K, Thomas T, et al. Efficient motion retrieval in large motion databases[C]//Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. ACM, 2013: 19-28.

[4] Chao M W, Lin C H, Assa J, et al. Human motion retrieval from hand-drawn sketch[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(5): 729-740.

[5] 藍榮祎，孫懷江，連荷清，等．人體運動捕獲數據的向量空間建模與檢索[J]. 計算機輔助設計與圖形學學報, 2011, 23(8): 1357-1364.

[6] Wang Z, Feng Y, Qi T, et al. Adaptive multi-view feature selection for human motion retrieval[J]. Signal Processing, 2016, 120: 691-701.

[7] 潘紅，肖俊，吳飛，等．基于關鍵幀的三維人體運動檢索[J]．計算機輔助設計與圖形學學報, 2009, 21(2): 214-222.

[8] 劉云根，劉金剛．重建誤差最優化的運動捕獲數據關鍵幀提取[J]．計算機輔助設計與圖形學學報, 2010, 22(4): 670-675.

[9] Deng Z, Gu Q, Li Q. Perceptually consistent example-based human motion retrieval[C]//Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games. ACM, 2009: 191-198.

[10] 肖伯祥，張強，魏小鵬．人體運動捕捉數據特征提取與檢索研究綜述[J]．計算機應用研究, 2010, 27(1): 10-13.

[11] 連荷清．人體運動捕獲數據的檢索方法研究[D]．南京：南京理工大學, 2013.

[12] Carnegie Mellon University. CMU Graphics Lab Motion Capture Database[EB/OL]. http://mocap.cs.cmu.edu.

[13] 劉賢梅，趙丹．面向內容的三維人體運動檢索技術研究綜述[J]．計算機工程與應用, 2012, 48(18): 148-153,163.

A RETRIEVAL METHOD OF 3D MOTION CAPTURE DATA BASED ON INDEX SPACE

Xu Congyang Xu Jiangfeng

(SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001,Henan,China)

In order to effectively retrieve a large number of 3D human motion capture data and put it into use, this paper proposes an efficient retrieval method for the unique characteristics of 3D human motion capture data. Firstly, the original motion data dimension is reduced by key frame extraction, and then the original angle data is transformed into the feature sequence by using the customized human motion semantic feature. According to the feature sequences of all the moving segments in the database, an index space based on attitude feature is constructed. At the time of retrieval, By matching the attitude features sequentially in the index space, the matching motion fragments with the same timing are found. Experimental results show that the proposed method has better time efficiency, higher flexibility and retrieval precision than most existing methods because of better motion semantic feature extraction.

Motion capture data Motion retrieval Feature extraction Index space

2016-02-28。國家科技支撐計劃項目(2014BAH09F00);國家自然科學基金項目(61379079)。徐從洋，碩士，主研領域：虛擬現實。徐江峰，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.04.025