基于半監督距離學習的運動相似性度量算法

李 斌,孫懷江

(南京理工大學計算機科學與工程學院,南京210094)

基于半監督距離學習的運動相似性度量算法

李 斌,孫懷江

(南京理工大學計算機科學與工程學院,南京210094)

人體運動捕獲技術的發展使得運動捕獲數據不斷積累,人體運動的檢索技術成為運動數據管理和重用過程中的關鍵環節。由于邏輯相似的運動在數值上并不一定相似,使用歐式距離度量2個運動間的邏輯相似性難以取得理想的結果。為此,提出一種半監督的距離度量學習算法,利用帶標記的運動和未標記運動進行訓練以得到運動間的馬氏距離度量,從而判斷2個運動之間的邏輯相似性,實現運動檢索。實驗結果表明,與現有的大部分檢索算法相比,該算法能夠得到更高的查詢精度,且沒有任何人工干預,可應用于自動檢索領域。

人體運動捕獲數據;半監督;距離學習;相似性度量;檢索;識別精度

1 概述

在計算機三維人體動畫技術領域,人體運動捕獲數據的研究是極具挑戰性的課題。利用運動捕獲數據來驅動人體運動,可以得到符合人們視覺要求的動畫效果,這種方法為動畫創作提供了重要的媒體素材。伴隨著運動捕獲技術的向前發展,大量的三維人體運動捕獲數據得以積累,并已經建立起很多大規模運動數據庫［1-2］。在對數據庫進行管理和重用的過程中,不可避免地需要進行數據庫的查詢和瀏覽操作,因此,在數據庫中如何精確高效地檢索運動數據成為一個十分重要的問題。

在傳統的人體運動捕獲數據檢索方法中,基于內容的方法往往可以得到較好的結果,該類方法中運動數據相似性度量的研究是其主要難點。在給定特征的情況下,比較2個運動之間的相似度是一件困難而又至關重要的事情。相似性度量最簡單的方法是使用歐式距離度量,但是很多研究表明邏輯上相似的運動在數值上并不一定相似［3］,這樣在運動捕獲數據的相似性度量上歐式距離難以取得理想的結果。現有的方法往往使用字串匹配［3-5］、向量夾角余弦［6］、歐式距離［7］來度量運動間的相似性并用于檢索,但很難得到滿意的結果。另一方面,距離度量學習在信息檢索中也扮演一個重要的角色,很多研究表明學習適當的距離度量并通過其進行相似性度量能夠改善檢索算法的精度［8］,文獻［9-11］也證明使用監督或半監督度量學習,能夠很好地改善通過度量相似性而得到的檢索結果。因此,很多研究人員嘗試通過少量的監督信息,自動地進行距離度量的學習,以提高檢索質量。隨著運動捕獲數據的不斷積累,人工標記運動數據變得越來越難,得到的數據往往只有一部分是標記了正確的信息,其他大量的數據都是未標記的。僅使用監督學習方法使得檢索范圍局限于有限的類別中,很難使其所學習到的距離度量準則擴展到其他類別運動數據上。文獻［12］提出了一種半監督的距離學習方法,用來度量運動數據幀與幀之間的相似度,相對于傳統的基于監督學習的建模方法,這類方法能夠自動地(半自動地)建立模型,可以減輕人的負擔,同時增強算法的適用性。

目前傳統的運動數據檢索方法大多著重于運動特征的提取。運動捕獲數據是高維時序數據,并且幀率高、數據量龐大、缺少結構化信息。很多方法過度依賴于特征提取的好壞,并且這些方法所提供的特征往往只能夠區分部分運動類別,很難應用于實際場合。為了能夠盡可能地反映人體運動的內在規律,特征的選擇上應該豐富、全面。但是這樣也帶來了一些問題,特征與特征相互之間的關系變得更加復雜,維度越高越難以進行分析,使得運動數據間相似度計算困難,簡單的度量很難得到理想的結果。

針對這些問題,本文提出一種半監督距離學習方法,給出一種有效的相似性度量標準,用于運動數據的檢索。盡可能有效地利用已標記運動數據的類別信息,使得邏輯相似的運動數據之間距離盡可能地小,而邏輯不相似運動數據之間的距離盡可能地大。同時,由于存在大量的未標記運動數據,使用稀疏表示中的相關方法［13］建模來挖掘未標記運動數據之間以及標記運動和未標記運動之間的相似性關系,而這些關系可以使所學習的度量準則更加準確。

2 特征提取

由于不同的運動捕獲設備所捕獲的人體運動數據結構不同,為了能夠有效地處理來源不同的數據,本文使用人體最重要的15個關節進行特征提取,也即根關節、頭部、頸部、軀干和四肢等重要關節。

一般情況下,2個運動數據在時間上是不等長的,需要使用動態時間規劃(DTW)對2個數據在時間維度上進行對齊,但這樣造成了一定的信息損失和不必要的干擾。文獻［7］使用關節間的相對距離(JRD)作為特征,并在JRD基礎上,提出了關節相對距離的方差(VJRD)作為特征,方差表示每個JRD在其均值上的波動范圍。文獻［12］提出了幾何姿態描述符(GPD),幾乎包含了運動姿態中的各種信息,如關節位置、關節間距離、關節間夾角和關節到某個平面的距離等信息,能夠有效地表示運動數據。VJRD能夠保留運動邏輯相似性的同時避免DTW的對齊操作。但是VJRD僅僅包含了關節間距離的信息,對于復雜的人體運動數據,其信息量包含不夠,所以使用特征極為豐富的GPD替換JRD作為特征。

本文使用VGPD作為一個運動序列的特征。對于一個運動序列M,可以形式化地表示為M={F1, F2,…,FT},包含T幀運動數據,Ft(1≤t≤T)表示其中的一幀。對于每一幀來說,需計算1 683個特征。構造運動序列每一幀GPD,當一個運動序列得到其GPD后,可簡單地通過式(1)求取其VGPD:

3 半監督距離學習

人體運動數據庫可以形式化地表示成X={x1, x2,…,xi,…,xN},其中,N表示數據庫中運動序列的個數,xi∈Rd(d=1 683),表示單個運動序列。另外,數據庫中包含一部分帶有類別標簽的數據,用yij∈{0,1}表示第i個運動和第j個運動是否屬于同一類別運動。任意2個運動序列之間的歐式距離為:

采用歐式距離進行相似性度量的優點是有較高的計算效率,而不足之處是計算過程忽略了運動數據特征的語義解釋,這種度量方法不能和人的相似度感知取得一致,也即邏輯上相似的運動在數值上并不相似,而不是所希望的邏輯相似的運動間距離小,邏輯不相似運動間距離大,很難得到準確的度量結果。自然地需要學習一個與運動數據特征描述一致的相似度計算函數,也即使用度量學習學習得到一個馬氏距離度量標準M,在新的變換空間中得到符合邏輯的度量標準,所以新的距離度量公式可以表示為:

其中,M∈R1683×1683,為了保證式(3)有效,需要保證M是一個對稱、半正定矩陣。所以,可以將M寫為M=WTW。那么距離度量公式可表示為:

其中,W∈Rd×d′,并且d′＜d。

本文目的是通過優化學習得到最優的W,為此需要定義一系列的損失函數來達到目的。文獻［10］通過引入一系列的損失函數,通過優化得到幀之間的相似性度量準則。與文獻［12］相類似,首先需要充分利用運動數據的標記信息。不同于文獻［12］的地方在于,當2個運動數據屬于同一類時,認為它們是相似的,也就是語義上的相似,也即邏輯相似的運動其數值距離也應盡可能地小。這樣需要保證相同類別的運動數據間的距離小,不同類別間的距離大。用Esimilar來表示相同類別運動數據間的距離平方和:

為了保證相同類別的運動數據間的距離小,需要最小化Esimilar,即:

同樣用Edissimilar來表示不同類別運動數據間的距離平方和:

另一方面在實際應用中,有標記的訓練數據往往數量很小,而存在大量無標記數據。為此,本文提出一種半監督學習方法。認為任意的一個運動序列可以被其他的運動序列線性組合進行表示,并且相同類別的運動數據具有相近的表示方法。假設X=［x1,x2,…,xN］表示相同類別運動數據所組成的一個矩陣,每一列xi表示一個運動序列,X則表示為未標記運動數據所組成的一個矩陣,同樣每一列代表一個運動序列。那么可以得到:

其中,A=［a1,a2,…,aN］。式(9)表示每個標記的運動數據可以由未標記的運動數據線性表示,ai表示每個運動序列xi的重構系數。由于未標記的數據量較大,通常情況下,只是用其中的一部分運動數據就可很好地進行重構。與此同時,由于X中的運動數據同屬于一個類別,這些運動數據的重構方式是相似的,也就是說使用相同的未標記運動數據就可以很好地重構所有X中的運動數據。上述2個方面的特性正好與Group-lasso［13］類似。為此本文引入它來求解A。Group-lasso可以令A中的某些行全為0,這樣意味著同一類別的運動數據用同樣的一批未標記數據重構,符合人類的直覺。

其中,‖·‖F表示矩陣的F范數;‖·‖2,1表示l2,1范數。原始運動數據與重構后的運動數據間的距離也小,這種信息也需要在學習中保留下來。用EG表示它們之間的距離平方和:

其中,IN表示N×N的單位矩陣;SG=(IN-A)(INA)T,那么相應的損失函數為:

但是應當注意到在未標記的數據中還包含了大量未知類別的數據,這些運動數據同樣十分重要,可以采用文獻［12］的方式,不同的是將之前使用過的數據剔除掉。未標記數據矩陣X中的每一個運動序列xi同樣可以被其他的運動序列線性重構,與上述方法類似,運動序列xi的重構系數是稀疏的,通過式(13)進行求解:

其中,‖·‖1表示l1范數。同上一樣用ESr表示它們之間的距離平方和:

其中,xi∈,最小化得到損失函數為:

綜合式(6)、式(8)、式(12)、式(15)可得最終的損失函數:

式(16)是一個 trace ratio優化問題,令 A= XSdissimilarXT,B=X(Ssimilar+SG+SSr)XT,那么式(16)可以寫為:

由此可以很容易地得到最優的W,進而得到M。當新來一個查詢樣本,用該馬氏距離度量求得其與數據庫中其他運動數據間的距離,將這些距離由小到大排序,即可得到檢索結果。

4 實驗與評價

本文實驗已標記數據使用來自波恩大學的運動捕獲數據庫HDM05［2］,該數據庫中包含了3 634個不同的運動片段,其中所有的運動片段均是單一類別運動,包含52種不同類別的運動。數據庫總大小為720 MB。為了驗證本文方法的有效性,將有標記的一部分數據看作是未標記數據。首先在數據庫中選取出90%的運動,其中一半作為訓練樣本集,另一半作為測試時的待檢索數據庫。訓練樣本集中,再選取出其中的40種類別的運動數據,其中40%的運動數據用于監督學習,剩余60%的運動數據與其他12種類別的作為無標記運動數據用于訓練。數據庫中剩余10%的運動序列作為測試樣本集進行檢索。為了驗證本文方法的有效性,選取了一些比較典型的方法進行對比,即無監督類方法［14］,使用了部分監督信息,但未進行度量學習的方法［7］、監督學習方法［11］以及半監督學習方法［12］。同時本文采用TopN側率來評價檢索的質量,在統計檢索精度時,N的取值為待檢索數據庫中相應類別的樣本總數。

圖1列出了本文方法與其他方法的部分類比運動檢索精度比較。圖1被分為2個部分,其中左邊8條表示有標記運動數據的檢索結果,而右邊6條表示無標記運動數據的檢索結果。從圖中可以看出,本文方法在檢索質量上具有明顯的優勢。文獻［14］使用了幾何特征,是一種無監督的檢索方法,由于幾何特征并不能很好地表示運動數據,并且需要大量的人工干預,檢索精度很難達到一個理想的水平。文獻［7］利用運動的類別信息對不同類別的運動進行特征選擇,進而利用線性回歸得到待檢索運動序列較優的特征,在一定程度上彌補了歐式距離的不足,但并未解決邏輯相似運動在數值上不一定相似這一本質問題。文獻［11-12］以及本文方法通過監督/半監督的度量學習,利用運動捕獲數據的類別信息有效地彌補了歐式距離的不足,檢索效果得到大幅的提升。

圖1 TopN策略下運動數據檢索精度

另一方面,文獻［14］由于不需要任何監督信息,對于無標記運動的檢索要稍遜于文獻［7,11］。由于文獻［12］和本文方法使用半監督學習方法,使用了大量的未標記運動用于訓練,對于數據庫中未標記的運動也能很好地檢索出來,從圖中也可以看出本文方法要明顯優于其他方法。文獻［11］由于只使用已標記的運動數據,所能挖掘到的信息有限,當標記數目不足或不全面時,其性能將大幅度下降,例如對于走路運動來說,細分可以劃分為很多種類型,如正常走路和跛行,當訓練數據庫中無跛行運動時,使用文獻［11］方法將很難檢索出跛行的運動數據。對于這種情況,文獻［12］所提出的方法也很難解決。由于正常行走和跛行都屬于走路,包含了相同的內在規律,本文方法通過Group-lasso來挖掘標記運動與非標記運動之間的這種關系,用于相似性度量學習,從而可以應用于各種場合。從圖2的P-R曲線中也可以看出本文提出方法的檢索精度和召回率已經達到一個比較高的水平。

圖2 檢索精度-召回率曲線(P-R曲線)

5 結束語

本文提出了一種半監督的度量學習方法,得到運動間的相似性度量標準,該標準能夠很好地判斷運動捕獲數據之間的相似性,通過比較運動間的相似性達到運動檢索的目的。實驗結果表明,本文方法要優于現有的大部分檢索方法,能夠達到較高的檢索精度和召回率。但是本文所使用的運動特征為VGPD,具有較高的維度,隨著數據量的增加,需要花費更多時間進行訓練。同時,本文方法在訓練過程中使用了運動數據的類別信息,每種類別的運動都有較為充足的訓練樣本,但是在實際應用中,某些運動類別的數據可能十分少,這將直接影響訓練的結果,如何有效地利用這些數據并得到較好的訓練結果也是今后的研究方向之一。

［1］ CMU.Carnegie Mellon Mo-cap Database［EB/OL］.(2003-10-29).http://mocap.cs.cmu.edu.

［2］ Müller M,R?derT,Clausen M,etal.A Weber: Documentation mo-cap Database HDM05［EB/OL］.(2011-08-31).http://mocap.cs.cmu.edu.

［3］ Müller M,R?der T,Clausen M.Efficient Content-based Retrieval of Motion Capture Data［J］.ACM Transactions on Graphics,2005,24(3):667-685.

［4］ 田 楓,劉賢梅,沈旭昆,等.一種基于運動姿態的三維人體運動檢索方法［J］.計算機仿真,2012,29(11): 42-46.

［5］ 劉云根,劉金剛.基于人體姿勢編碼的運動數據檢索［J］.計算機輔助設計與圖形學學報,2011,23(4): 586-593.

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

［7］ Tang J,Leung H.Retrieval of Logically Relevant 3D Human Motions by Adaptive Feature Selection with Graded Relevance Feedback［J］.Pattern Recognition Letters,2012,33(4):420-430.

［8］ 羅 辛,邰曉英,Masami S,等.一種基于度量距離學習的圖像檢索方法［J］.廣西師范大學學報:自然科學版,2007,25(2):186-189.

［9］ Müller H,Pun T,Squire D.Learning from User Behavior in Image Retrieval:Application ofMarketBasket Analysis［J］.International Journal of Computer Vision, 2004,56(2):65-77.

［10］ Weinberger K Q,Blitzer J,Saul L K.Distance Metric Learning for Large Margin Nearest Neighbor Classification［J］.The Journal of Machine Learning Research,2009,(10):207-244.

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

［12］ Chen Cheng,Zhuang Yueting,Nie Feiping,et al.Learning a 3D Human Pose Distance Metric from Geometric Pose Descriptor［J］.IEEE Transactions on Visualization and Computer Graphics,2011,17(11):1676-1689.

［13］ Yuan Ming,Lin Yi.Model Selection and Estimation in Regression with Grouped Variables［J］.Journal of the Royal Statistical Society,Series B,2007,68(1):49-67.

［14］ 祝銘陽,藍榮祎,孫懷江,等.一種人體運動相似性度量方法［J］.計算機工程,2011,37(12):155-157.

編輯 顧逸斐

Motion Similarity Measurement Algorithm Based on Semi-supervised Distance Learning

LI Bin,SUN Huaijiang
(School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China)

With the rapid development of the human motion capture technology,large amount of motion capture data is gradually accumulated,then human motion retrieval and recognition technology becomes the essential issue for motion data management and reuse.Logically similar motions may be numerically dissimilar,so it is difficult to get feasible results if the logical similarity between two movements is measured with Euclidean distance.This paper presents a semisupervised distance learning method for measuring the logical similarity with Mahalanobis distance which is trained by labeled and unlabeled motion data.Experimental evaluation result of the method shows that the proposed method is effective for motion retrieval.

human motion capture data;semi-supervised;distance learning;similarity measurement;retrieval;

1000-3428(2014)11-0178-05

A

TP391

10.3969/j.issn.1000-3428.2014.11.035

南京理工大學自主科研專項計劃基金資助項目(2011YBXM79)。

李 斌(1987-),男,碩士研究生,主研方向:三維人體動畫,運動數據檢索;孫懷江,教授、博士、博士生導師。

2013-11-19

2013-12-19E-mail:lbin@outlook.com

中文引用格式:李 斌,孫懷江.基于半監督距離學習的運動相似性度量算法［J］.計算機工程,2014,40(11):178-182.

英文引用格式:Li Bin,Sun Huaijiang.Motion Similarity Measurement Algorithm Based on Semi-supervised Distance Learning［J］.Computer Engineering,2014,40(11):178-182.

identification precision