夏 磊

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

0 引言

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

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

1 模板匹配方法

1.1 Euclidean Distance

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

(1)

1.2 DTW

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

圖1 典型DTW比較子序列

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

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

(2)

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

(3)

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

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

3)單調性：點在包絡路徑上的間隔要求是單調的。

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

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)路徑中，對應兩個連續(xù)數據片段相似部分的往往只有路徑上的一小段。因此我們需要將最優(yōu)路徑上特定的子路徑切割出來，這些子路徑滿足的條件是：

1)子路徑包含的點的數量，即子路徑長度長于L；

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

(5)

1.4 Cross Correlation

在信號處理中，經常要研究兩個信號的相似性，或者一個信號經過一段時間延遲后自身的相似性，以便實現信號檢測、識別與提取等[12]?？捎糜谘芯啃盘栂嗨菩缘姆椒ǚQ為相關。給定兩個時間序列X和Y，其長度分別為n和m，其互相關函數定義為：

(6)

通常來講，互關聯(lián)指數可以對兩個信號的標準差進行歸一化，及互相關系數：

(7)

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

(8)

該函數通常用來從白噪聲中分離周期性信號以識別信號周期及信號的重復模式。

2 系統(tǒng)框架與算法設計

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

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

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

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

2.1 模板生成

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

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

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

2.2 閾值確定

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

2.3 相似度計算

與DTW算法相似，通過更新距離計算矩陣來計算相似性。每次IsDTW計算過程存儲兩個值，D(t,k)和X(t,k)。D(t,k)為序列Y和子序列Si,t之間DTW距離的最小值，X(t,k)為序列Xi,t的開始時間，即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的目標是在給定序列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 結果與分析

3.1 數據集

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

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

圖5 實驗數據與真實標度

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

3.2 實驗結果

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

圖6 ROC示意圖

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

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

圖7 IsDTW方法在不同實驗數據集上的結果比較

本文所提出的改進的DTW算法在不同的實驗場景下，都取得了較好的實驗結果。從以上實驗結果，我們可以得到以下結論：

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

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

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

3.4 與統(tǒng)計機器學習方法比較

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

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

表2 IsDTW與統(tǒng)計機器學習方法性能比較

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

4 結論

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

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

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

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

[4] 咼潤華,蘇婷婷,馬曉偉. BP神經網絡聯(lián)合模板匹配的車牌識別系統(tǒng)[J]. 清華大學學報(自然科學版),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] 朱保鋒,宋 艷. 一種改進的BM算法性能分析[J]. 中州大學學報，2015(3):114-116.

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

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

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

[11] 劉 鶴. 基于人工神經網絡的認知無線電頻譜感知研究[J]. 電子測試,2012,(9):37-41.

[12] 王 燕,安云杰. 時間序列相似性度量方法[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] 劉明亮,朱江淼. 數字信號處理對電子測量與儀器的影響研究[J]. 電子測量與儀器學報,2014,28(10):1041-1046.

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