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

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

0 引 言

近年來(lái)，隨著三維人體運(yùn)動(dòng)捕獲技術(shù)的日益成熟以及多媒體技術(shù)的快速發(fā)展，大量的視覺(jué)真實(shí)感強(qiáng)、富有表現(xiàn)力的人體運(yùn)動(dòng)捕獲數(shù)據(jù)被錄制保存，并被有效地應(yīng)用在了三維動(dòng)畫(huà)、電影制作和游戲等產(chǎn)業(yè)中。然而大量的運(yùn)動(dòng)捕獲數(shù)據(jù)同時(shí)也增加了其被有效管理和重用的難度。因此，如何對(duì)運(yùn)動(dòng)數(shù)據(jù)庫(kù)進(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é)相對(duì)于父關(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)特征的表示和描述存在較大的困難。因此，面對(duì)運(yùn)動(dòng)數(shù)據(jù)高時(shí)間、空間復(fù)雜度，找到一種有效的特征表示方法，對(duì)于數(shù)據(jù)降維和提高檢索效率具有重大意義。

關(guān)鍵幀方法如潘紅等[7]首先根據(jù)運(yùn)動(dòng)數(shù)據(jù)定義簡(jiǎn)單特征，然后提取關(guān)鍵幀代表整個(gè)運(yùn)動(dòng)時(shí)序序列，該方法對(duì)原數(shù)據(jù)有效降維但特征提取不夠完善。聚類方法[2,9]以層次化方式描述運(yùn)動(dòng)，將相似的運(yùn)動(dòng)數(shù)據(jù)歸類并提取特征值，用特征值集合表示運(yùn)動(dòng)。Wu等[2]、Deng等[9]將整個(gè)人體劃分為幾部分，并對(duì)每部分進(jìn)行聚類。Chao等[4]使用了一組正交球面諧波基函數(shù)來(lái)代表運(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é)合起來(lái)互補(bǔ)特征信息。Kapadia等[3]根據(jù)特定各肢體之間以及肢體與環(huán)境之間的關(guān)系自定義特征，這樣做比直接幀間對(duì)比更節(jié)省運(yùn)行時(shí)間且有很好檢索效果。其中文獻(xiàn)采用Laban運(yùn)動(dòng)分析定義了一組可以表示人體結(jié)構(gòu)、幾何與動(dòng)態(tài)特征的運(yùn)動(dòng)鍵值來(lái)編碼運(yùn)動(dòng)。

(2) 索引與相似度匹配

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

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

本文采用參考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ù)庫(kù)的一個(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對(duì)應(yīng)特征序號(hào))，其中每個(gè)特征對(duì)應(yīng)動(dòng)作姿態(tài)p的一個(gè)特定動(dòng)作特性，不同的特征由不同的身體軀段集合計(jì)算而來(lái)。雖然每個(gè)運(yùn)動(dòng)特征fk(p)對(duì)應(yīng)的是一個(gè)關(guān)鍵幀姿態(tài)pj，但有些運(yùn)動(dòng)特征如關(guān)節(jié)瞬時(shí)速度是根據(jù)一定范圍[j-Δ,j+Δ]內(nèi)相鄰幀計(jì)算出來(lái)的，因此保留了運(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è)類別可以幫助識(shí)別人體哪一部分在移動(dòng)，哪些部位間有接觸和人體部位運(yùn)動(dòng)的模式。在這部分特征的定義中，我們考慮到了人體一些關(guān)節(jié)的自由度通常小于3，因此一些不太可能出現(xiàn)的姿態(tài)特征可以直接忽略以精簡(jiǎn)特征空間。

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

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

(5)

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

(6)

時(shí)間 時(shí)間特征與力度特征相對(duì)應(yīng)，根據(jù)運(yùn)動(dòng)速度由小到大變化快慢區(qū)分運(yùn)動(dòng)是突然的還是穩(wěn)步變化的。此特征和力度特征一起可以詳細(xì)描述動(dòng)作從靜止開(kāi)始到運(yùn)動(dòng)再到靜止結(jié)束的整個(gè)過(guò)程的風(fēng)格。例如急切的敲門(mén)表現(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)過(guò)第1節(jié)所描述的關(guān)鍵幀提取和自定義特征提取，原始運(yùn)動(dòng)數(shù)據(jù)得到了有效的降維和邏輯特征表示，每個(gè)運(yùn)動(dòng)姿態(tài)pj轉(zhuǎn)化成了一個(gè)對(duì)應(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ù)庫(kù)的姿態(tài)特征空間，而每一個(gè)運(yùn)動(dòng)片段則可理解為空間中一些姿態(tài)按時(shí)序順序的連接，如圖3所示。

由此，我們定義了特征空間來(lái)索引整個(gè)運(yùn)動(dòng)數(shù)據(jù)庫(kù)。對(duì)于一個(gè)運(yùn)動(dòng)姿態(tài)，其對(duì)應(yīng)的布爾特征值序列可以作為該姿態(tài)在索引空間中的索引號(hào)，將該姿態(tài)特征序列與對(duì)應(yīng)某特征位為1，其余位為0的序列相與，即可得到該姿態(tài)在某特征的值。在特征提取階段，記錄每個(gè)姿態(tài)所在的運(yùn)動(dòng)片段序號(hào)和對(duì)應(yīng)幀序號(hào)，作為該姿態(tài)的索引信息。最后將所有姿態(tài)按布爾特征值大小排序，順序存儲(chǔ)。由此可以看出，索引空間將數(shù)據(jù)庫(kù)中所有運(yùn)動(dòng)片段的不同姿態(tài)提取出來(lá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)子序列匹配，模糊查找等常見(jiàn)檢索需求。

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

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

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

3 檢 索

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

輸入包括特征向量表示的查詢運(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開(kāi)始，從左向右)，則sf=1101001100。在查找中兩特征序列分別和sf相與后值相等即為匹配。定義每次查找得到的運(yùn)動(dòng)片段集合M0和當(dāng)前總命中運(yùn)動(dòng)片段集合Mh，記錄匹配到的運(yùn)動(dòng)片段序號(hào)，命中次數(shù)以及幀序號(hào)。

算法描述如下：

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

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

Step5：如果Q還有下一幀，轉(zhuǎn)至Step2；否則除去Mh中命中次數(shù)小于Q關(guān)鍵幀長(zhǎng)度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ù)庫(kù)中的運(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)的幀序號(hào)，每次命中下一幀時(shí)比較幀序號(hào)是否按照升序排列，保證檢索結(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的幀序號(hào)，因此可以實(shí)現(xiàn)子序列匹配的首幀定位。

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

本文實(shí)驗(yàn)數(shù)據(jù)包括卡內(nèi)基梅隆大學(xué)人體運(yùn)動(dòng)捕獲數(shù)據(jù)庫(kù)[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)片段長(zhǎng)度為40幀到5 000幀不等。我們使用C++開(kāi)發(fā)出一個(gè)檢索系統(tǒng)，實(shí)現(xiàn)檢索前的運(yùn)動(dòng)數(shù)據(jù)預(yù)處理和檢索時(shí)的整個(gè)過(guò)程。實(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ù)庫(kù)運(yùn)動(dòng)數(shù)據(jù)分類

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

運(yùn)動(dòng)數(shù)據(jù)預(yù)處理即為對(duì)原始運(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)通過(guò)文中方法對(duì)所有原始運(yùn)動(dòng)數(shù)據(jù)提取關(guān)鍵幀，不同動(dòng)作的最優(yōu)壓縮率不同，簡(jiǎn)單緩慢的動(dòng)作最優(yōu)壓縮率高，而復(fù)雜猛烈的動(dòng)作最優(yōu)壓縮率較低。如緩慢行走的壓縮率平均為7%，而舞蹈的壓縮率平均為16%。最終所有運(yùn)動(dòng)數(shù)據(jù)提取過(guò)后的總幀數(shù)為40 238幀，總平均壓縮率為約11%，可以看出大大減少了后期對(duì)運(yùn)動(dòng)數(shù)據(jù)處理的量。

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

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

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

4.2 檢索階段

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

由于在檢索時(shí)唯一的參數(shù)“需匹配特征”的指定會(huì)影響到檢索結(jié)果，需要用戶具有一定的先驗(yàn)知識(shí)，因此下一步我們的目標(biāo)是自適應(yīng)地針對(duì)不同類別運(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。國(guó)家科技支撐計(jì)劃項(xiàng)目(2014BAH09F00);國(guó)家自然科學(xué)基金項(xiàng)目(61379079)。徐從洋，碩士，主研領(lǐng)域：虛擬現(xiàn)實(shí)。徐江峰，教授。

TP3

A

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