一種基于索引空間的三維運(yùn)動(dòng)捕獲數(shù)據(jù)檢索方法

徐從洋 徐江峰

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

一種基于索引空間的三維運(yùn)動(dòng)捕獲數(shù)據(jù)檢索方法

徐從洋 徐江峰

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

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

運(yùn)動(dòng)捕獲數(shù)據(jù) 運(yùn)動(dòng)檢索 特征提取 索引空間

0 引 言

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

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

基于內(nèi)容的檢索方法主要包括兩個(gè)技術(shù)難點(diǎn)：

(1) 運(yùn)動(dòng)數(shù)據(jù)的特征提取

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

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

(2) 索引與相似度匹配

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

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

本文采用參考Laban運(yùn)動(dòng)分析自定義的特征描述人體肢體之間以及肢體與環(huán)境之間的關(guān)系，利用特征值組合表示不同運(yùn)動(dòng)姿態(tài)從而構(gòu)建一個(gè)與運(yùn)動(dòng)時(shí)序相關(guān)的索引空間，依據(jù)此索引空間可以完成快速且準(zhǔn)確的運(yùn)動(dòng)檢索。

1 運(yùn)動(dòng)特征定義與提取

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

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

圖1 人體骨骼分段模型

我們參照Laban運(yùn)動(dòng)分析將特征集合主要分為身體特征、動(dòng)力學(xué)特征和外形特征。

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

動(dòng)作表現(xiàn) 這個(gè)特征表示人體軀段在當(dāng)前是否是運(yùn)動(dòng)的狀態(tài)，通過計(jì)算與相鄰姿態(tài)間的位移量是否超過閾值。此特征主要針對四肢和整體的位移。

(1)

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

朝向信息 表示人體上下兩部分相對于基礎(chǔ)姿態(tài)時(shí)的朝向是否有大的變化。此特征可以描述例如轉(zhuǎn)身等朝向信息有變化的運(yùn)動(dòng)。

(2)

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

(3)

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

(4)

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

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

空間 空間特征區(qū)分運(yùn)動(dòng)軌跡是直線或非直線，由當(dāng)前姿態(tài)與前Δ幀區(qū)間的距離比率計(jì)算而來的。

(5)

力度 力度特征主要區(qū)分運(yùn)動(dòng)是猛烈的還是輕緩的。通常猛烈運(yùn)動(dòng)的特點(diǎn)是速度值由大到小變化非常快，減速明顯；而輕緩的運(yùn)動(dòng)速度平均，減速較慢甚至沒有。

(6)

時(shí)間 時(shí)間特征與力度特征相對應(yīng)，根據(jù)運(yùn)動(dòng)速度由小到大變化快慢區(qū)分運(yùn)動(dòng)是突然的還是穩(wěn)步變化的。此特征和力度特征一起可以詳細(xì)描述動(dòng)作從靜止開始到運(yùn)動(dòng)再到靜止結(jié)束的整個(gè)過程的風(fēng)格。例如急切的敲門表現(xiàn)為突然和猛烈的，而原地起跳表現(xiàn)為突然和輕緩的。

平滑度 描述運(yùn)動(dòng)在一定時(shí)間范圍內(nèi)的連續(xù)性，體現(xiàn)在運(yùn)動(dòng)速度曲線是否在時(shí)間范圍[j-Δ,j+Δ]內(nèi)存在多個(gè)波峰波谷，即加速與減速切換是否頻繁。

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

(7)

圖2 特征定義示例

2 索 引

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

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

圖3 運(yùn)動(dòng)片段匹配索引空間

根據(jù)定義的索引結(jié)構(gòu)的特點(diǎn)，可以很方便地實(shí)現(xiàn)運(yùn)動(dòng)子序列匹配，模糊查找等常見檢索需求。

子序列匹配 當(dāng)輸入查詢運(yùn)動(dòng)片段時(shí)，其有可能是數(shù)據(jù)庫中某些長運(yùn)動(dòng)片段的子序列。在檢索中，通過查詢運(yùn)動(dòng)片段的第一關(guān)鍵幀姿態(tài)對應(yīng)的特征值序列可以快速定位到索引空間中的相似姿態(tài)，即找到查詢運(yùn)動(dòng)片段在長運(yùn)動(dòng)片段中相匹配的開端。

模糊查找 當(dāng)用戶需要與查詢運(yùn)動(dòng)片段部分特征相似而非完全一致的運(yùn)動(dòng)數(shù)據(jù)時(shí)，可以通過指定部分特征要求匹配。指定特征越少，相匹配的就越多。

實(shí)時(shí)查找 由于構(gòu)建索引空間是線下完成，并且檢索時(shí)可以并發(fā)查找多個(gè)相似運(yùn)動(dòng)，因此檢索速度快，能實(shí)現(xiàn)實(shí)時(shí)查找。

3 檢 索

根據(jù)以上的特征提取與索引空間定義，我們結(jié)合折半查找算法和姿態(tài)特征匹配實(shí)現(xiàn)檢索。在算法描述前，首先給出一些定義說明。

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

算法描述如下：

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

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

Step5：如果Q還有下一幀，轉(zhuǎn)至Step2；否則除去Mh中命中次數(shù)小于Q關(guān)鍵幀長度50%的運(yùn)動(dòng)片段，所得Mh即為最終檢索結(jié)果。

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

由于Q中每一幀只在索引空間中查找一次，避免了運(yùn)動(dòng)的重復(fù)匹配。檢索結(jié)果中包含匹配運(yùn)動(dòng)片段中第一幀命中Q的幀序號，因此可以實(shí)現(xiàn)子序列匹配的首幀定位。

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

本文實(shí)驗(yàn)數(shù)據(jù)包括卡內(nèi)基梅隆大學(xué)人體運(yùn)動(dòng)捕獲數(shù)據(jù)庫[12]的共約400個(gè)運(yùn)動(dòng)片段，分為8類，如表1所示。所有運(yùn)動(dòng)捕獲數(shù)據(jù)關(guān)節(jié)數(shù)為23，幀頻率為24 fps，運(yùn)動(dòng)片段長度為40幀到5 000幀不等。我們使用C++開發(fā)出一個(gè)檢索系統(tǒng)，實(shí)現(xiàn)檢索前的運(yùn)動(dòng)數(shù)據(jù)預(yù)處理和檢索時(shí)的整個(gè)過程。實(shí)驗(yàn)中系統(tǒng)運(yùn)行在Intel P4 2.7 GHz CPU和2 GB內(nèi)存的PC機(jī)上。

表1 實(shí)驗(yàn)數(shù)據(jù)庫運(yùn)動(dòng)數(shù)據(jù)分類

4.1 運(yùn)動(dòng)數(shù)據(jù)預(yù)處理階段

運(yùn)動(dòng)數(shù)據(jù)預(yù)處理即為對原始運(yùn)動(dòng)數(shù)據(jù)集進(jìn)行檢索前的線下處理，包括關(guān)鍵幀提取，特征提取和構(gòu)建索引空間三個(gè)步驟。

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

2) 本文第1節(jié)共定義了36個(gè)布爾特征，因此特征提取階段會將運(yùn)動(dòng)片段的每一關(guān)鍵幀轉(zhuǎn)換為一個(gè)長度為36的布爾序列，對應(yīng)值范圍為[0，236]。最終將每個(gè)運(yùn)動(dòng)片段轉(zhuǎn)化為一個(gè)特征向量。

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

圖4 特征分布與姿態(tài)重復(fù)度

4.2 檢索階段

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

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

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

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

圖5 運(yùn)動(dòng)“走”檢索結(jié)果

圖6 運(yùn)動(dòng)“從坐到站起直走”檢索結(jié)果

圖7 運(yùn)動(dòng)“雙腿合并向前跳”子序列檢索結(jié)果

本文檢索算法在查找某一幀對應(yīng)特征序列時(shí)使用折半查找搜索索引空間，查找時(shí)間復(fù)雜度log2n，n為姿態(tài)總數(shù)，最多為236，則每個(gè)特征序列查找次數(shù)最多為log2236=36。對于本文實(shí)驗(yàn)環(huán)境，原始查詢運(yùn)動(dòng)片段為300幀時(shí)，查找平均時(shí)間為0.034 s。

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

本文對文獻(xiàn)[3]的特征定義進(jìn)行改進(jìn)并提出了一種新的索引構(gòu)建和檢索方法，具有靈活、快速、準(zhǔn)確檢索的特點(diǎn)，能夠運(yùn)用在大規(guī)模運(yùn)動(dòng)數(shù)據(jù)庫檢索中。

圖8 多種方法在幾種不同運(yùn)動(dòng)類別上檢索結(jié)果的P-R對比

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

圖9 多種方法在不同數(shù)據(jù)庫大小下的檢索時(shí)間

5 結(jié) 語

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

由于在檢索時(shí)唯一的參數(shù)“需匹配特征”的指定會影響到檢索結(jié)果，需要用戶具有一定的先驗(yàn)知識，因此下一步我們的目標(biāo)是自適應(yīng)地針對不同類別運(yùn)動(dòng)匹配其突出的運(yùn)動(dòng)特征，達(dá)到智能檢索的目的。

[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] 藍(lán)榮祎，孫懷江，連荷清，等．人體運(yùn)動(dòng)捕獲數(shù)據(jù)的向量空間建模與檢索[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 潘紅，肖俊，吳飛，等．基于關(guān)鍵幀的三維人體運(yùn)動(dòng)檢索[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2009, 21(2): 214-222.

[8] 劉云根，劉金剛．重建誤差最優(yōu)化的運(yùn)動(dòng)捕獲數(shù)據(jù)關(guān)鍵幀提取[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 肖伯祥，張強(qiáng)，魏小鵬．人體運(yùn)動(dòng)捕捉數(shù)據(jù)特征提取與檢索研究綜述[J]．計(jì)算機(jī)應(yīng)用研究, 2010, 27(1): 10-13.

[11] 連荷清．人體運(yùn)動(dòng)捕獲數(shù)據(jù)的檢索方法研究[D]．南京：南京理工大學(xué), 2013.

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

[13] 劉賢梅，趙丹．面向內(nèi)容的三維人體運(yùn)動(dòng)檢索技術(shù)研究綜述[J]．計(jì)算機(jī)工程與應(yīng)用, 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。國家科技支撐計(jì)劃項(xiàng)目(2014BAH09F00);國家自然科學(xué)基金項(xiàng)目(61379079)。徐從洋，碩士，主研領(lǐng)域：虛擬現(xiàn)實(shí)。徐江峰，教授。

TP3

A

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