文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2016.08.035
中文引用格式: 吳齊云,,戰(zhàn)蔭偉,,邵陽. 基于DTW和K-means的動(dòng)作匹配和評(píng)估[J].電子技術(shù)應(yīng)用,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 引言
康復(fù)訓(xùn)練是病人通過訓(xùn)練使患病的肢體逐漸恢復(fù)功能,達(dá)到治療效果,。Kinect體感外設(shè)可以在不受背景和光照等影響下監(jiān)測(cè)人體動(dòng)作,,近幾年被應(yīng)用到康復(fù)訓(xùn)練中。文獻(xiàn)[1]結(jié)合Kinect用于在學(xué)步車上提取腿部信息進(jìn)行醫(yī)療分析,。文獻(xiàn)[2]利用Kinect的深度傳感器獲取深度圖像來識(shí)別3D人體姿態(tài),。基于Kinect的康復(fù)訓(xùn)練系統(tǒng)相較于傳統(tǒng)的面對(duì)面指導(dǎo)訓(xùn)練方法不僅可以減少醫(yī)生的工作量,,更可以提高病患訓(xùn)練的便捷性和自主性,。
康復(fù)系統(tǒng)的關(guān)鍵在于人體動(dòng)作識(shí)別。近年來對(duì)人體動(dòng)作識(shí)別的研究十分活躍,。NATARAJAN P等人[3]將CRF用到了人體動(dòng)作識(shí)別中,。Shi Qinfeng等人[4]針對(duì)連續(xù)的動(dòng)作序列提出一種判定式的馬爾可夫模型(即HMM算法)。由于CRF和HMM算法需先建模,,算法復(fù)雜度較大,。故本文提出一種人體動(dòng)作識(shí)別方法,該方法通過 Kinect實(shí)時(shí)提取骨骼關(guān)節(jié)點(diǎn)三維坐標(biāo),計(jì)算骨骼關(guān)節(jié)點(diǎn)空間角度,,以空間角度變化值定義一組動(dòng)作,,然后通過改進(jìn)的DTW算法把兩組動(dòng)作序列的角度值進(jìn)行匹配,得到兩個(gè)序列之間的失真值,,最后通過K-means聚類方法得到動(dòng)作評(píng)估結(jié)果,。
1 特征提取
Kinect傳感器是康復(fù)訓(xùn)練系統(tǒng)的核心數(shù)據(jù)采集裝置。Kinect通過20個(gè)關(guān)節(jié)點(diǎn)來表示一個(gè)站立的人體骨架,,如圖1,。
圖1 人體骨架關(guān)節(jié)點(diǎn)
一個(gè)關(guān)節(jié)與其相鄰的兩個(gè)關(guān)節(jié)構(gòu)成一個(gè)夾角。如圖2所示,,肘關(guān)節(jié)E和腕關(guān)節(jié)W,、肩關(guān)節(jié)J就構(gòu)成一個(gè)以E為頂點(diǎn)的角。
圖 2 人體關(guān)節(jié)角度
使用余弦定理計(jì)算關(guān)節(jié)角度:
利用Kinect獲得一組動(dòng)作關(guān)節(jié)點(diǎn)坐標(biāo),,計(jì)算每一幀關(guān)節(jié)點(diǎn)空間角度值,,判定兩組動(dòng)作相似性即為判定兩個(gè)角度序列之間的相似性。測(cè)定兩個(gè)角度序列的相似性可看作是兩個(gè)時(shí)間序列之間的距離測(cè)量,。
2 動(dòng)作匹配
康復(fù)訓(xùn)練中,,訓(xùn)練者會(huì)盡量模仿標(biāo)準(zhǔn)動(dòng)作,但在時(shí)序上仍會(huì)存在很大差異[5],。因此需要對(duì)動(dòng)作序列進(jìn)行時(shí)序規(guī)整,,采用動(dòng)態(tài)時(shí)間規(guī)整算法DTW[6]來解決距離測(cè)量過程中時(shí)間軸差異問題。
2.1 動(dòng)態(tài)時(shí)間規(guī)整算法DTW
設(shè)X和Y分別是長度為m和n的序列:
記xm和yn間的距離為d(xm,,yn),,簡(jiǎn)寫為d(m,n),,1≤m≤M,,1≤n≤N。
兩條序列匹配的距離即為距離dk(m,,n)加權(quán)和:
為了確保求得的路徑A是一條全局最優(yōu)規(guī)整路徑,,有約束條件:路徑必須起點(diǎn)(1,1)到終點(diǎn)(M,,N),;路徑保持時(shí)間順序單調(diào)不減;m和n只能依次增加0或者1,,即(m,,n)后一點(diǎn)必須是(m+1,n),,(m,,n+1)或者(m+1,,n+1);路徑的斜率不能太小也不能太大,,可以限制斜率在0.5~2范圍內(nèi),。
具有最小累積距離的路徑才是最優(yōu)規(guī)整路徑,有且僅有一條,,根據(jù)式(5)和約束條件可得DTW距離的遞歸公式:
2.2 一般的DTW改進(jìn)方式
DTW算法雖然測(cè)量距離精準(zhǔn)度很高,,但是運(yùn)算量很大,,時(shí)間復(fù)雜度和空間復(fù)雜度都是O(M×N)[7],。近年來DTW的算法改進(jìn)方法最多的是:全局路徑限制[8]和放寬端點(diǎn)對(duì)齊[9]改進(jìn)方法。
文獻(xiàn)[8]的全局路徑限制方法是把路徑的斜率限制在1/3~3之間,,此方法減少了DTW的運(yùn)算量,,但精確度會(huì)有所降低。
實(shí)際應(yīng)用中由于環(huán)境等各種因素的影響,,起點(diǎn)和終點(diǎn)會(huì)有變化,,引起誤差,故放寬端點(diǎn)對(duì)齊方法是起點(diǎn)在(1,,1),、(1,2),、(2,,1)、(1,,3),、(3,1)等中選擇一最小值作為松弛起點(diǎn),,終點(diǎn)在(N,,M)、(N-1,,M),、(N,M-1),、(N-2,,M)等中選擇一最小值作為松弛終點(diǎn)。此方法并沒有減少運(yùn)算量,,但增加了精確度,,減少誤差。
2.3 本文改進(jìn)的DTW算法
目前一般的DTW改進(jìn)算法在精確度和運(yùn)算量上并不能同時(shí)很好地滿足,,本文提出一種改進(jìn)DTW方法,,為了在提高算法復(fù)雜度的同時(shí),,保證精確度。
在本文的實(shí)驗(yàn)中最終需要得到的是最優(yōu)規(guī)整路徑的累積距離值,,只需要存儲(chǔ)每一次迭代的一個(gè)對(duì)齊時(shí)間對(duì)(xm,,yn),簡(jiǎn)寫為(m,,n),。因此沒有必要用一個(gè)矩陣來保存所有時(shí)間對(duì),可改為只保存2列,,由大小是2×n的數(shù)組dist[][]和pos[][]分別存儲(chǔ)距離值和時(shí)間對(duì),,兩列由pre和cur表示,即指針cur始終指向當(dāng)前時(shí)間點(diǎn)信息,,返回兩個(gè)序列當(dāng)前時(shí)間和距離,,pre指向當(dāng)前的前一時(shí)間,如圖3,。
圖3 數(shù)據(jù)存儲(chǔ)
故DTW算法式(6)可改為:
其中m是序列X中cur指向的時(shí)間點(diǎn),,上述存儲(chǔ)的是求得的最優(yōu)路徑的全局距離,同樣地,,最優(yōu)路徑是由pos[][]存儲(chǔ):
數(shù)組dist和pos均有兩列,,pre和cur指針循環(huán)以確保數(shù)組中移動(dòng)并為數(shù)組元素指定操作,減少操作時(shí)間,,如表1所示,。
由于本文改進(jìn)的DTW有兩個(gè)數(shù)組dist和pos,每個(gè)數(shù)組的大小是2×N,,每個(gè)時(shí)間點(diǎn)只需要運(yùn)算兩個(gè)數(shù)組,,所以時(shí)間復(fù)雜度和空間復(fù)雜度都是O(N),相比于傳統(tǒng)DTW的O(M×N),,速率明顯提高,。
3 動(dòng)作評(píng)價(jià)
在一個(gè)連續(xù)動(dòng)作中涉及到的關(guān)節(jié)角度變化序列不止一個(gè),通過改進(jìn)的DTW算法得到兩個(gè)動(dòng)作過程中所有關(guān)節(jié)角度變化序列的距離后,,取平均值,,對(duì)該距離平均值進(jìn)行分析得到評(píng)價(jià)結(jié)果。
選取5個(gè)人每個(gè)動(dòng)作按優(yōu)秀,、良好,、合格做出實(shí)驗(yàn)樣本,分別和標(biāo)準(zhǔn)動(dòng)作序列通過本文改進(jìn)的DTW求距離,。選取最長的距離作為“合格”的下界D,。將0~D分為3段區(qū)間,W-0=Q-W=D-Q,,將W和Q作為良好和合格的初始中心點(diǎn),,優(yōu)秀的中心點(diǎn)始終是0,。
由于參數(shù)只有W和Q兩個(gè)分割點(diǎn),故選擇Kmeans算法取K=2對(duì)各區(qū)域進(jìn)行聚類,。將樣本點(diǎn)R與0,、W及Q計(jì)算距離,取三個(gè)中最小的距離作為該樣本點(diǎn)的區(qū)域所在,。
分別計(jì)算良好,、合格的所有樣本點(diǎn)中心:
其中,C為良好區(qū)域的重心點(diǎn),,M為分散到區(qū)域內(nèi)的樣本點(diǎn)數(shù),,dcw為樣本點(diǎn)到M距離。
通過Kmeans劃分出區(qū)域的同時(shí),,已計(jì)算得出良好和合格的期望,,假設(shè)各區(qū)域的期望方差都符合高斯分布,則通過最大似然估計(jì)得到各區(qū)域的期望和方差:
分別對(duì)和求導(dǎo)后,,求解和得:
其中xk表示第k個(gè)樣本和標(biāo)準(zhǔn)樣本距離,N表示元素總數(shù),。歸一化后得到隸屬函數(shù):
把測(cè)試動(dòng)作和標(biāo)準(zhǔn)動(dòng)作的角度序列在經(jīng)過改進(jìn)的DTW算法求得距離后,,通過隸屬函數(shù)確定動(dòng)作的評(píng)估結(jié)果。
4 實(shí)驗(yàn)分析
實(shí)驗(yàn)在康復(fù)訓(xùn)練系統(tǒng)中進(jìn)行,。實(shí)驗(yàn)者通過Kinect控制虛擬人物模擬標(biāo)準(zhǔn)動(dòng)作進(jìn)行運(yùn)動(dòng),,把實(shí)驗(yàn)者的動(dòng)作和標(biāo)準(zhǔn)動(dòng)作進(jìn)行動(dòng)作匹配后,得到動(dòng)作評(píng)價(jià)結(jié)果,。實(shí)驗(yàn)選取10人進(jìn)行4組動(dòng)作訓(xùn)練,,每組動(dòng)作10次。圖4示,,訓(xùn)練動(dòng)作:伸肘側(cè)平舉(1-2-1),、屈肘側(cè)平舉(1-3-4-1)、抱頭張肩(1-5-6-7-1)和復(fù)雜動(dòng)作(1-2-3-4-5-6-7-8),。
圖4 動(dòng)作示意圖
實(shí)驗(yàn)中用DTW算法,、HMM算法、一般的改進(jìn)DTW算法以及本文改進(jìn)的DTW算法分別進(jìn)行動(dòng)作匹配,,實(shí)驗(yàn)結(jié)果以識(shí)別成功次數(shù)和速率(單位:s/次)作為比較標(biāo)準(zhǔn),,見表2。
5 結(jié)語
實(shí)驗(yàn)表明,,本文改進(jìn)的DTW方法能準(zhǔn)確有效地進(jìn)行人體動(dòng)作識(shí)別,,相較于傳統(tǒng)DTW算法、一般改進(jìn)DTW算法,、HMM算法匹配速率有明顯的提高且不影響精確度,,動(dòng)作越復(fù)雜時(shí)間越長,,速率提升效果越好。在接下來的工作中,,將進(jìn)一步研究康復(fù)訓(xùn)練系統(tǒng)的界面設(shè)計(jì),。
參考文獻(xiàn)
[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,,F(xiàn)u 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ī)場(chǎng)模型的聯(lián)機(jī)行為識(shí)別方法[J].計(jì)算機(jī)學(xué)報(bào),,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.