夏 磊

(南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094)

0 引言

隨著人們生活節(jié)奏加快，工作壓力不斷加大，日常運(yùn)動(dòng)已經(jīng)成了現(xiàn)代人的一種現(xiàn)狀[1]。步行走路作為簡單易行的鍛煉，確保我們的身體能夠保持活力和健康。計(jì)步器[2]通過實(shí)時(shí)監(jiān)測用戶日常步行用以掌控運(yùn)動(dòng)量，步態(tài)在測算走路時(shí)所表現(xiàn)的姿態(tài)，及走路所有的動(dòng)作。用戶日常運(yùn)動(dòng)中步態(tài)計(jì)步器(Pedometer of Gait,POG)檢測問題不同于傳統(tǒng)的統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法[3]，模板匹配方法[4]往往在具有較高精度的同時(shí)能夠保持相對(duì)較高的效率，被普遍應(yīng)用與人體姿態(tài)識(shí)別實(shí)際應(yīng)用中。Muscillo[5]等利用基于個(gè)體的模板，實(shí)現(xiàn)了對(duì)下肢特定動(dòng)作的識(shí)別和捕捉。此外，Chen和Shen[6]構(gòu)建了一個(gè)基于模板匹配方法的識(shí)別框架，實(shí)現(xiàn)對(duì)右下肢精確動(dòng)作的捕捉。朱保鋒和宋艷[7]將不同的動(dòng)作編譯成序列的符號(hào)，利用字符匹配的方法實(shí)現(xiàn)動(dòng)作識(shí)別。然而，據(jù)我們所知，模板匹配方法尚未被應(yīng)用于用戶日常運(yùn)動(dòng)的POG檢測應(yīng)用中。

綜上所述，傳統(tǒng)的統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法精度低、效率差，很難被實(shí)際應(yīng)用于POG實(shí)時(shí)檢測。模板匹配方法具有精度高、實(shí)時(shí)性好等優(yōu)點(diǎn)，但尚未應(yīng)用于POG實(shí)時(shí)檢測。基于此， 本文提出一種改進(jìn)的Dynamic Template Wrapping(DTW)模板匹配方法，用于POG 實(shí)時(shí)檢測。在介紹典型的模板匹配方法的基礎(chǔ)上，提出本文設(shè)計(jì)系統(tǒng)的具體框架，及算法流程，闡述實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析比較。

1 模板匹配方法

1.1 Euclidean Distance

歐幾里得度量[8]是一個(gè)通常采用的距離定義，指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，或者向量的自然長度(即該點(diǎn)到原點(diǎn)的距離)。令X=x1,...,xi,...,xm，Y=y1,...,yi,...,yn為兩個(gè)時(shí)序序列，則距離di(i=0,...,n-m-1,n

(1)

1.2 DTW

在日常的生活中我們最經(jīng)常使用的距離毫無疑問應(yīng)該是歐式距離，但是對(duì)于一些特殊情況，歐氏距離存在著其很明顯的缺陷，比如說時(shí)間序列[10]，特別是當(dāng)樣本長度不一樣時(shí)，DTW能夠衡量這兩個(gè)序列的相似程度，或者說兩個(gè)序列的距離。DTW算法的質(zhì)量就是運(yùn)用動(dòng)態(tài)規(guī)劃的思想，利用局部最佳化的處理來自動(dòng)尋找一條路徑，兩個(gè)特征矢量之間的積累失真量最?。畯亩苊庥捎跁r(shí)長不同而可能引入的誤差。

圖1 典型DTW比較子序列

定義序列Q(模版信號(hào))和C(記錄信號(hào))，長度分別為n和m,即:

X=(t1,x1),...,(ti,xi),...,(tn,xn)

(2)

Y=(t1,y1),...,(tj,yj),...,(tn,yn)

(3)

1)邊界條件：所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束。

2)連續(xù)性：就是不可能跨過某個(gè)點(diǎn)去匹配，只能和自己相鄰的點(diǎn)對(duì)齊。這樣可以保證X和Y中的每個(gè)坐標(biāo)都在W中出現(xiàn)。

3)單調(diào)性：點(diǎn)在包絡(luò)路徑上的間隔要求是單調(diào)的。

滿足上面這些約束條件的路徑可以有指數(shù)個(gè)，然后我們感興趣的是使得下面的規(guī)整代價(jià)最小的路徑，這樣我們有：

Dist(X,Y)=D(xi,yj)+Dmin

(4)

其中:Dmin=min{Dist(i-1,j-1),Dist(i-1,j),Dist(i,j-1)}。

1.3 sDTW

一條最優(yōu)路徑，在每一條最優(yōu)路徑中，對(duì)應(yīng)兩個(gè)連續(xù)數(shù)據(jù)片段相似部分的往往只有路徑上的一小段。因此我們需要將最優(yōu)路徑上特定的子路徑切割出來，這些子路徑滿足的條件是：

1)子路徑包含的點(diǎn)的數(shù)量，即子路徑長度長于L；

2)子路徑包含的所有點(diǎn)的平均值，即子路徑平均值小于θ。給定一條包含N個(gè)點(diǎn)的路徑以及子路徑長度限制L(L

(5)

1.4 Cross Correlation

在信號(hào)處理中，經(jīng)常要研究兩個(gè)信號(hào)的相似性，或者一個(gè)信號(hào)經(jīng)過一段時(shí)間延遲后自身的相似性，以便實(shí)現(xiàn)信號(hào)檢測、識(shí)別與提取等[12]?？捎糜谘芯啃盘?hào)相似性的方法稱為相關(guān)。給定兩個(gè)時(shí)間序列X和Y，其長度分別為n和m，其互相關(guān)函數(shù)定義為：

(6)

通常來講，互關(guān)聯(lián)指數(shù)可以對(duì)兩個(gè)信號(hào)的標(biāo)準(zhǔn)差進(jìn)行歸一化，及互相關(guān)系數(shù)：

(7)

其中:σYY和σXX分別為Y和X的標(biāo)準(zhǔn)差，其值介于-1和+1之間。若γYX(τ)=-1，則說明Y與X形狀相同但相位相反；若γYX(τ)=0，則說明Y與X不具有相似性；若γYX(τ)=+1則說明Y與X完全相似。當(dāng)信號(hào)與自身相比較時(shí)，稱為自相關(guān)，定義如下：

(8)

該函數(shù)通常用來從白噪聲中分離周期性信號(hào)以識(shí)別信號(hào)周期及信號(hào)的重復(fù)模式。

2 系統(tǒng)框架與算法設(shè)計(jì)

文獻(xiàn)[13]等通常利用傅立葉變換來提取時(shí)域和頻域的不同特征，來進(jìn)行POG的檢測與分類。本文根據(jù)POG測量信號(hào)[14]的特定，從模版匹配的角度出發(fā)，采用一種改進(jìn)的sDTW算法：IsDTW，來實(shí)現(xiàn)POG的檢測與預(yù)警，在保持識(shí)別精度的前提下降低算法的復(fù)雜度。

本文所述POG檢測和分析過程，主要可以分為兩個(gè)個(gè)環(huán)節(jié)：1)數(shù)據(jù)預(yù)處理階段：主要完成模板生成、閾值確定等工作，即模型訓(xùn)練階段；2)實(shí)驗(yàn)分析階段：利用所提出算法，進(jìn)行相似度計(jì)算，判別POG。

Notations：原始信號(hào)記為X={(t1,x1),(t2,x2),...,(ti,xi),...,(tn,xn)}，待查詢子序列記為Y={(t1,y1),...,(tj,yj),...,(tm,ym)}。子序列表示從時(shí)刻i到j(luò)的X子序列。

圖2 系統(tǒng)框架示意圖

2.1 模板生成

模板序列Y，其長度m為預(yù)設(shè)好的匹配窗口長度，模板序列中包括若干傳感器采集數(shù)據(jù)子序列(加速度軸Ax,Ay,Az等)。在樣本數(shù)據(jù)中，包含大量標(biāo)記好的POG和非POG數(shù)據(jù)，分別將兩類數(shù)據(jù)劃分為長度為m的子序列，并利用Matlab的“interp1”函數(shù)進(jìn)行平均化，得到正常步態(tài)模板如圖3所示。對(duì)子序列的每一個(gè)軸向都做相同的處理，從而得到POG步態(tài)的模板如圖4所示。

圖3 正常步態(tài)模板

圖4 POG步態(tài)模板

2.2 閾值確定

上述算法另一個(gè)待解決的問題是損失函數(shù)閾值ε的確定。由常理可知，由于個(gè)體差異和噪聲等原因，該閾值會(huì)因人而異，不同的實(shí)驗(yàn)對(duì)象理應(yīng)具有不同的閾值設(shè)定。出于以上考慮，本論文在前期統(tǒng)計(jì)建模的基礎(chǔ)上，提出一個(gè)基于統(tǒng)計(jì)機(jī)器學(xué)習(xí)的動(dòng)態(tài)門限閾值估計(jì)方法。在數(shù)據(jù)預(yù)處理階段，通過標(biāo)注的訓(xùn)練數(shù)據(jù)，利用ANN分類器[15]，分析得出適合實(shí)驗(yàn)對(duì)象的閾值ε，作為實(shí)驗(yàn)分析階段的輸入。該方法通過機(jī)器學(xué)習(xí)方式獲得，在大量真實(shí)數(shù)據(jù)的基礎(chǔ)上，運(yùn)行速度快、可信度高。

2.3 相似度計(jì)算

與DTW算法相似，通過更新距離計(jì)算矩陣來計(jì)算相似性。每次IsDTW計(jì)算過程存儲(chǔ)兩個(gè)值，D(t,k)和X(t,k)。D(t,k)為序列Y和子序列Si,t之間DTW距離的最小值，X(t,k)為序列Xi,t的開始時(shí)間，即i=X(t,k)。D(t,k)可以通過如下方式獲得：

(9)

其中:Distbest=min{Dist(t,k-1),Dist(t-1,k),Dist(t-1,k-1)}，D(t,0)=0，D(0,0)=D(0,k)=+∞，(t=1,2,...,n，k=1,2,...,m)。同理，X(t,k)可以通過下式得到：

(10)

其中:X(t,0)=t。IsDTW的目標(biāo)是在給定序列X中，查找出所有與給定序列Y相似度滿足給定閾值ε的子序列Xi,j，即Dist(Xi,j,Y)≤ε，其中j=i+m-1，i=1,2,...,n-m+1。算法流程如下：

Input:xtattimet

Output: 相似子序列si,t

Fork=1tomdo

CalculateD(t,k)andX(t,k)

End

IfDmin≤εthen

If?D(t,k)>Dmin∨X(t,k)>tethen

ReturnDmin,ts,te

Dmin=+∞

Fork=1tomdo

IfX(t,k)≤tethen

D(t,k)=+∞

End

End

End

End

IfD(t,m)≤ε∧D(t,m)≤Dminthen

Dmin=D(t,m)

ts=X(t,m)

te=t

End

Fork=0tomdo

D(t-1,k)=D(t,k)

X(t-1,k)=D(t,k)

End

3 結(jié)果與分析

3.1 數(shù)據(jù)集

本文方法所依托數(shù)據(jù)來自開源數(shù)據(jù)集[6]。Bachlin及其同事以10名PD病人用戶(7名男性，3名女性；年齡66.5±4.8；病史年限：13.7±9.67)為實(shí)驗(yàn)對(duì)象進(jìn)行分析。實(shí)驗(yàn)對(duì)象皆有步行病史，并在無外力協(xié)助的情況下可以在“off-medicine”條件下行走。所有實(shí)驗(yàn)都在“off-medicine”的條件下完成數(shù)據(jù)采集和分析。

實(shí)驗(yàn)對(duì)象根據(jù)要求完成幾種實(shí)驗(yàn)場景下的數(shù)據(jù)采集：直線前后行進(jìn)、隨機(jī)停止-行進(jìn)、360度轉(zhuǎn)彎以及日常生活活動(dòng)。全程所有的活動(dòng)流程都通過攝像機(jī)記錄。兩名醫(yī)務(wù)人員通過視頻信息實(shí)時(shí)診斷病人的兩種不同活動(dòng)狀態(tài)：非凍結(jié)(行走、站立、轉(zhuǎn)彎)和凍結(jié)。當(dāng)每次POG檢測時(shí)，記錄起止時(shí)間。每名實(shí)驗(yàn)對(duì)象身上帶有3個(gè)3軸加速度計(jì)，分別放置于shank、thigh和lower back，采用頻率設(shè)置為64 Hz。在數(shù)據(jù)集中，共包含10名實(shí)驗(yàn)對(duì)象8 h 20 min的實(shí)驗(yàn)數(shù)據(jù)，237段POG數(shù)據(jù)。

圖5 實(shí)驗(yàn)數(shù)據(jù)與真實(shí)標(biāo)度

圖5所示為某位PD病人用戶實(shí)驗(yàn)過程中，傳感器記錄數(shù)據(jù)的示意圖。由圖可見，實(shí)驗(yàn)對(duì)象在起步時(shí)即發(fā)生POG現(xiàn)象，短暫停留后開始正常行進(jìn)；隨后，傳感器有監(jiān)測到由POG引起的顫抖，即發(fā)生了腿部的卡頓現(xiàn)象；較長時(shí)間的POG過后實(shí)驗(yàn)對(duì)象進(jìn)行了較快的行進(jìn)，在又一次短時(shí)POG后進(jìn)入休息狀態(tài)。基于醫(yī)生的檢測結(jié)果在圖中用彩色字體標(biāo)注，與實(shí)驗(yàn)結(jié)果相一致。此外，由圖可知，在第一、第三次POG中，短時(shí)的POG卡頓被精確識(shí)別出來而不是識(shí)別成休息狀態(tài)；第二次POG中腿部由于POG的引起的顫抖，也被準(zhǔn)確識(shí)別，說明了算法的有效性。

3.2 實(shí)驗(yàn)結(jié)果

圖6為檢測系統(tǒng)實(shí)驗(yàn)的Receiver Operating Characteristic(ROC)曲線。圖示為分別利用后背下側(cè)、大腿、小腿以及全部三個(gè)加速度數(shù)據(jù)時(shí)，系統(tǒng)識(shí)別性能的ROC曲線。由圖可知，當(dāng)數(shù)據(jù)較為豐富時(shí)(即全部使用)，系統(tǒng)ROC性能更好，即曲線更接近左上角。當(dāng)僅利用小腿數(shù)據(jù)時(shí)，性能相對(duì)較好，其原因可能與該部位更能反應(yīng)POG特性有關(guān)。

圖6 ROC示意圖

3.3 與其它模板匹配方法比較

本文利用不同的模板匹配方法在數(shù)據(jù)集[6]上進(jìn)行POG檢測分析，獲得了不同的識(shí)別結(jié)果，如圖7所示。

圖7 IsDTW方法在不同實(shí)驗(yàn)數(shù)據(jù)集上的結(jié)果比較

本文所提出的改進(jìn)的DTW算法在不同的實(shí)驗(yàn)場景下，都取得了較好的實(shí)驗(yàn)結(jié)果。從以上實(shí)驗(yàn)結(jié)果，我們可以得到以下結(jié)論：

1)不同的算法在不同的實(shí)驗(yàn)數(shù)據(jù)集上獲得了不同的精度，所有數(shù)據(jù)都利用時(shí)精度最高，利用shank時(shí)略低。由此可見，shank，其余部位數(shù)據(jù)起到了一定的輔助作用。

2)在不同的實(shí)驗(yàn)數(shù)據(jù)集上，本文所述IsDTW算法都獲得了相對(duì)較高的精度，體現(xiàn)出算法的穩(wěn)定性。同時(shí)，其最高精度達(dá)到92%。同其他算法相比，IsDTW在運(yùn)行過程中持續(xù)更新最小路徑，保持高效率的同時(shí)獲得了較高的精度；利用ANN更新動(dòng)態(tài)閾值，保持了算法的有效性。

3)DTW相關(guān)的算法普遍優(yōu)于Eudidean和Cross Correlation算法，說明在相似性度量上，對(duì)于變長數(shù)據(jù)及不確定長度序列的判別DTW更具有優(yōu)越性。

3.4 與統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法比較

為了進(jìn)一步驗(yàn)證算法的有效性，本文將基于模版匹配的POG檢測方法實(shí)驗(yàn)結(jié)果與傳統(tǒng)統(tǒng)計(jì)分類方法進(jìn)行了比較，包括Decision Tree(DT)，Naive Bayesian Network (NBN)和Artificial Neural Network(ANN)。根據(jù)參考文獻(xiàn)[6]所示，本文選擇了13個(gè)常用的時(shí)域和頻域分類特征中，利用Relief方法篩選出9個(gè)用于分類，特征如表1所示。

利用開源工具Weka，在實(shí)驗(yàn)數(shù)據(jù)及上的測試結(jié)果與本文所提出的模版匹配方法IsDTW相比較，結(jié)果如表2所示。從結(jié)果可以看出，IsDTW方法在分類精度上具有顯著的優(yōu)勢，即IsDTW>ANN>NBN>DT。ANN在統(tǒng)計(jì)分類方法中具有較高精度，但仍明顯低于IsDTW，同時(shí)，在運(yùn)行效率上也遠(yuǎn)低于本文方法，難以滿足實(shí)時(shí)應(yīng)用的需求。DT由于算法簡單，具有較高的運(yùn)行效率，但是精度難以滿足應(yīng)用需要。

表2 IsDTW與統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法性能比較

由此可見，本文提出的IsDTW方法具有高精度、高實(shí)時(shí)性的優(yōu)點(diǎn)，能夠滿足實(shí)際應(yīng)用需求。

4 結(jié)論

本文集中討論了利用模板匹配的方法進(jìn)行POG檢測。通過在開源數(shù)據(jù)集上的驗(yàn)證分析，對(duì)比了基于模板匹配規(guī)則的Euclidean、DTW、SDTW、Cross Correlation和本文提出的IsDTW算法的不同性能。由實(shí)驗(yàn)結(jié)果可以得出結(jié)論，模板匹配方法對(duì)POG檢測有一定的優(yōu)越性，同時(shí)IsDTW方法具有更高的判別精度。作為對(duì)比，本文進(jìn)一步的將IsDTW方法與非模板方法進(jìn)行比較，結(jié)果顯示，本文方法不僅具有相對(duì)較高的實(shí)驗(yàn)精度，在運(yùn)行效率上也在一定程度上優(yōu)于傳統(tǒng)方法，對(duì)實(shí)際應(yīng)用更具價(jià)值。

[1] 陳 靜,姜漢鈞,徐乃昊,等. 運(yùn)動(dòng)傳感器輔助的心電運(yùn)動(dòng)偽跡識(shí)別與消除方法[J]. 傳感器與微系統(tǒng),2016,35(1):49-51.

[2] 袁憲鋒,周風(fēng)余,袁 通,等. STM32和iNEMO模塊的高精度計(jì)步器設(shè)計(jì)[J]. 單片機(jī)與嵌入式系統(tǒng)應(yīng)用,2013,13(9):42-45.

[3] 孟池潔,王 偉,耿光剛. 基于統(tǒng)計(jì)機(jī)器學(xué)習(xí)的互聯(lián)網(wǎng)暗鏈檢測方法[J]. 計(jì)算機(jī)應(yīng)用研究,2015,32(9):2779-2783.

[4] 咼潤華,蘇婷婷,馬曉偉. BP神經(jīng)網(wǎng)絡(luò)聯(lián)合模板匹配的車牌識(shí)別系統(tǒng)[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,53(9):1221-1226.

[5] Azizpour H,Razavian A S,Sullivan J,et al. From generic to specific deep representations for visual recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2014:1-1.

[6] Huang G B,Zhou H,Ding X,et al. Extreme learning machine for regression and multiclass classification.[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & 310 Cybernetics Society,2012,42(2):513-29.

[7] 朱保鋒,宋 艷. 一種改進(jìn)的BM算法性能分析[J]. 中州大學(xué)學(xué)報(bào)，2015(3):114-116.

[8] 邢哲源,馮秀芳. 一種基于時(shí)序信譽(yù)的WSNs惡意節(jié)點(diǎn)檢測算法[J]. 傳感器與微系統(tǒng)，2015,34(7):118-120，124.

[9] 汪海濤,花 靜. 基于相對(duì)變換距離的半監(jiān)督分類算法[J]. 計(jì)算機(jī)應(yīng)用與軟件,2013,30(6):178-181.

[10] 李海林,楊麗彬. 基于增量動(dòng)態(tài)時(shí)間彎曲的時(shí)間序列相似性度量方法[J]. 計(jì)算機(jī)科學(xué),2013,40(4):227-230.

[11] 劉 鶴. 基于人工神經(jīng)網(wǎng)絡(luò)的認(rèn)知無線電頻譜感知研究[J]. 電子測試,2012,(9):37-41.

[12] 王 燕,安云杰. 時(shí)間序列相似性度量方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2016,37(9):2520-2525.

[13] Graves A,Mohamed A R,Hinton G. Speech recognition with deep recurrent neural networks[J]. 2013,38(3):6645-6649.

[14] 劉明亮,朱江淼. 數(shù)字信號(hào)處理對(duì)電子測量與儀器的影響研究[J]. 電子測量與儀器學(xué)報(bào),2014,28(10):1041-1046.

[15] 陳 潔,余詩詩,李 斌,等. 基于雙閾值比較法超聲波流量計(jì)信號(hào)處理[J]. 電子測量與儀器學(xué)報(bào),2013,27(11):1024-1033.