文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.08.035
中文引用格式: 吳齊云,戰(zhàn)蔭偉,邵陽. 基于DTW和K-means的動作匹配和評估[J].電子技術應用,2016,42(8):141-143,153.
英文引用格式: Wu Qiyun,Zhan Yinwei,Shao Yang. Human motion matching and evaluation based on STDTW and K-means[J].Application of Electronic Technique,2016,42(8):141-143,153.
0 引言
康復訓練是病人通過訓練使患病的肢體逐漸恢復功能,達到治療效果。Kinect體感外設可以在不受背景和光照等影響下監(jiān)測人體動作,近幾年被應用到康復訓練中。文獻[1]結合Kinect用于在學步車上提取腿部信息進行醫(yī)療分析。文獻[2]利用Kinect的深度傳感器獲取深度圖像來識別3D人體姿態(tài)?;贙inect的康復訓練系統相較于傳統的面對面指導訓練方法不僅可以減少醫(yī)生的工作量,更可以提高病患訓練的便捷性和自主性。
康復系統的關鍵在于人體動作識別。近年來對人體動作識別的研究十分活躍。NATARAJAN P等人[3]將CRF用到了人體動作識別中。Shi Qinfeng等人[4]針對連續(xù)的動作序列提出一種判定式的馬爾可夫模型(即HMM算法)。由于CRF和HMM算法需先建模,算法復雜度較大。故本文提出一種人體動作識別方法,該方法通過 Kinect實時提取骨骼關節(jié)點三維坐標,計算骨骼關節(jié)點空間角度,以空間角度變化值定義一組動作,然后通過改進的DTW算法把兩組動作序列的角度值進行匹配,得到兩個序列之間的失真值,最后通過K-means聚類方法得到動作評估結果。
1 特征提取
Kinect傳感器是康復訓練系統的核心數據采集裝置。Kinect通過20個關節(jié)點來表示一個站立的人體骨架,如圖1。
圖1 人體骨架關節(jié)點
一個關節(jié)與其相鄰的兩個關節(jié)構成一個夾角。如圖2所示,肘關節(jié)E和腕關節(jié)W、肩關節(jié)J就構成一個以E為頂點的角。
圖 2 人體關節(jié)角度
使用余弦定理計算關節(jié)角度:
利用Kinect獲得一組動作關節(jié)點坐標,計算每一幀關節(jié)點空間角度值,判定兩組動作相似性即為判定兩個角度序列之間的相似性。測定兩個角度序列的相似性可看作是兩個時間序列之間的距離測量。
2 動作匹配
康復訓練中,訓練者會盡量模仿標準動作,但在時序上仍會存在很大差異[5]。因此需要對動作序列進行時序規(guī)整,采用動態(tài)時間規(guī)整算法DTW[6]來解決距離測量過程中時間軸差異問題。
2.1 動態(tài)時間規(guī)整算法DTW
設X和Y分別是長度為m和n的序列:
記xm和yn間的距離為d(xm,yn),簡寫為d(m,n),1≤m≤M,1≤n≤N。
兩條序列匹配的距離即為距離dk(m,n)加權和:
為了確保求得的路徑A是一條全局最優(yōu)規(guī)整路徑,有約束條件:路徑必須起點(1,1)到終點(M,N);路徑保持時間順序單調不減;m和n只能依次增加0或者1,即(m,n)后一點必須是(m+1,n),(m,n+1)或者(m+1,n+1);路徑的斜率不能太小也不能太大,可以限制斜率在0.5~2范圍內。
具有最小累積距離的路徑才是最優(yōu)規(guī)整路徑,有且僅有一條,根據式(5)和約束條件可得DTW距離的遞歸公式:
2.2 一般的DTW改進方式
DTW算法雖然測量距離精準度很高,但是運算量很大,時間復雜度和空間復雜度都是O(M×N)[7]。近年來DTW的算法改進方法最多的是:全局路徑限制[8]和放寬端點對齊[9]改進方法。
文獻[8]的全局路徑限制方法是把路徑的斜率限制在1/3~3之間,此方法減少了DTW的運算量,但精確度會有所降低。
實際應用中由于環(huán)境等各種因素的影響,起點和終點會有變化,引起誤差,故放寬端點對齊方法是起點在(1,1)、(1,2)、(2,1)、(1,3)、(3,1)等中選擇一最小值作為松弛起點,終點在(N,M)、(N-1,M)、(N,M-1)、(N-2,M)等中選擇一最小值作為松弛終點。此方法并沒有減少運算量,但增加了精確度,減少誤差。
2.3 本文改進的DTW算法
目前一般的DTW改進算法在精確度和運算量上并不能同時很好地滿足,本文提出一種改進DTW方法,為了在提高算法復雜度的同時,保證精確度。
在本文的實驗中最終需要得到的是最優(yōu)規(guī)整路徑的累積距離值,只需要存儲每一次迭代的一個對齊時間對(xm,yn),簡寫為(m,n)。因此沒有必要用一個矩陣來保存所有時間對,可改為只保存2列,由大小是2×n的數組dist[][]和pos[][]分別存儲距離值和時間對,兩列由pre和cur表示,即指針cur始終指向當前時間點信息,返回兩個序列當前時間和距離,pre指向當前的前一時間,如圖3。
圖3 數據存儲
故DTW算法式(6)可改為:
其中m是序列X中cur指向的時間點,上述存儲的是求得的最優(yōu)路徑的全局距離,同樣地,最優(yōu)路徑是由pos[][]存儲:
數組dist和pos均有兩列,pre和cur指針循環(huán)以確保數組中移動并為數組元素指定操作,減少操作時間,如表1所示。
由于本文改進的DTW有兩個數組dist和pos,每個數組的大小是2×N,每個時間點只需要運算兩個數組,所以時間復雜度和空間復雜度都是O(N),相比于傳統DTW的O(M×N),速率明顯提高。
3 動作評價
在一個連續(xù)動作中涉及到的關節(jié)角度變化序列不止一個,通過改進的DTW算法得到兩個動作過程中所有關節(jié)角度變化序列的距離后,取平均值,對該距離平均值進行分析得到評價結果。
選取5個人每個動作按優(yōu)秀、良好、合格做出實驗樣本,分別和標準動作序列通過本文改進的DTW求距離。選取最長的距離作為“合格”的下界D。將0~D分為3段區(qū)間,W-0=Q-W=D-Q,將W和Q作為良好和合格的初始中心點,優(yōu)秀的中心點始終是0。
由于參數只有W和Q兩個分割點,故選擇Kmeans算法取K=2對各區(qū)域進行聚類。將樣本點R與0、W及Q計算距離,取三個中最小的距離作為該樣本點的區(qū)域所在。
分別計算良好、合格的所有樣本點中心:
其中,C為良好區(qū)域的重心點,M為分散到區(qū)域內的樣本點數,dcw為樣本點到M距離。
通過Kmeans劃分出區(qū)域的同時,已計算得出良好和合格的期望,假設各區(qū)域的期望方差都符合高斯分布,則通過最大似然估計得到各區(qū)域的期望和方差:
分別對和求導后,求解和得:
其中xk表示第k個樣本和標準樣本距離,N表示元素總數。歸一化后得到隸屬函數:
把測試動作和標準動作的角度序列在經過改進的DTW算法求得距離后,通過隸屬函數確定動作的評估結果。
4 實驗分析
實驗在康復訓練系統中進行。實驗者通過Kinect控制虛擬人物模擬標準動作進行運動,把實驗者的動作和標準動作進行動作匹配后,得到動作評價結果。實驗選取10人進行4組動作訓練,每組動作10次。圖4示,訓練動作:伸肘側平舉(1-2-1)、屈肘側平舉(1-3-4-1)、抱頭張肩(1-5-6-7-1)和復雜動作(1-2-3-4-5-6-7-8)。
圖4 動作示意圖
實驗中用DTW算法、HMM算法、一般的改進DTW算法以及本文改進的DTW算法分別進行動作匹配,實驗結果以識別成功次數和速率(單位:s/次)作為比較標準,見表2。
5 結語
實驗表明,本文改進的DTW方法能準確有效地進行人體動作識別,相較于傳統DTW算法、一般改進DTW算法、HMM算法匹配速率有明顯的提高且不影響精確度,動作越復雜時間越長,速率提升效果越好。在接下來的工作中,將進一步研究康復訓練系統的界面設計。
參考文獻
[1] HU R Z L,HARTFIEL A,TUNG J,et al.3D Pose tracking of walker users′ lower limb with a structured-light camera on a moving platform[C].Computer Vision and Pattern Recognition Workshops,2011:29-36.
[2] Zheng Xiao,Fu Mengyin,Yang Yi,et al.3D Human postures recognition using Kinect[C].2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC),2012:344-347.
[3] NATARAJAN P,NEVATIA R.View and scale invariant action Recognition using multiview shape flow models[C].Proceedings of The IEEE International Conference on Computer Vision and The Pattern Recognition,Alaska,USA,2008:1-8.
[4] Shi Qinfeng,Cheng Li,Wang Li,et al.Human action segmentation and recognituin using discriminative semiMarkov models[J].International Journal of Computer Vision,2011,93(1):22-32.
[5] 黃天羽,石崇德,李鳳霞,等.一種基于判別隨機場模型的聯機行為識別方法[J].計算機學報,2009,32(2):275-281.
[6] KRUSKALL J,LIBERMAN M.The symmetric time warping problem:from continuous to discrete[J].In Time Warps,String Edits and Macromolecules:The Theory and Practice of Sequence Comparison.Addison-Wesley,1983,23(5):125-161.
[7] ABID H,HARUNUR R.User independent hand gesture recognition by accelerated DTW[C].Informatics Electronics & Vision(ICIEV),2012 International Conference,2012:1033-1037.
[8] HSU Y L,CHU C L.An inertial pen with dynamic time warping recognizer for handwriting and gesture recognition[J].IEEE Sensors Journal,2015,15(2):154-163.
[9] KAPRYKOWSKY H,RODET X.Globally optimal short-time dynamic time warping application to score to audio alignment[C].ICASSP 2006 Proceedings.2006.