王革超，梁久禎，陳　璟，朱向軍江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

加速度差分有限狀態(tài)機(jī)計(jì)步算法*

王革超+，梁久禎，陳璟，朱向軍
江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

WANG Gechao,LIANG Jiuzhen,CHEN Jing,et al.Step counting algorithm based on finite state machine using acceleration differential.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1133-1142.

摘要：在用戶行為無(wú)法預(yù)知的實(shí)際計(jì)步應(yīng)用中，如何保持計(jì)步算法的準(zhǔn)確性和穩(wěn)定性是一個(gè)極具挑戰(zhàn)的問(wèn)題。傳統(tǒng)的計(jì)步算法利用閾值設(shè)定和峰值檢測(cè)，并不能解決計(jì)步算法的普適性和穩(wěn)定性。針對(duì)上述問(wèn)題，提出了基于加速度差分作為特征的有限狀態(tài)機(jī)（acceleration differential based on finite state machine，AD-FSM）計(jì)步算法。該算法將原始加速度取平方和，并通過(guò)卡爾曼濾波去除噪聲干擾，最后使用加速度差分有限狀態(tài)機(jī)實(shí)現(xiàn)計(jì)步檢測(cè)。實(shí)驗(yàn)結(jié)果表明，該算法在正常和干擾情況下能夠提供精確的計(jì)步結(jié)果，誤差分別為1.12%、4.00%，驗(yàn)證了該計(jì)步算法在降低狀態(tài)機(jī)復(fù)雜度的同時(shí)具有較強(qiáng)的穩(wěn)定性和魯棒性，更能適應(yīng)復(fù)雜的應(yīng)用場(chǎng)景。

關(guān)鍵詞：室內(nèi)定位；計(jì)步；抗干擾；有限狀態(tài)機(jī)；加速度差分

1　引言

步行作為人類活動(dòng)中最基礎(chǔ)、最普及、最重要的運(yùn)動(dòng)形式，使得深入地研究計(jì)步器具有重要的意義[1]。在過(guò)去的十年里，智能手機(jī)在計(jì)算能力、內(nèi)存大小和微機(jī)電傳感器（如加速計(jì)、磁力計(jì)、陀螺儀）數(shù)量方面有著極大的改善，而其性能可靠、低成本、不受外界環(huán)境限制等特點(diǎn)，使得基于手機(jī)內(nèi)置傳感器的應(yīng)用方案得到了廣泛關(guān)注和研究。其中室內(nèi)定位技術(shù)因在商業(yè)、公共安全以及軍事等諸多領(lǐng)域中的廣泛應(yīng)用需求，成為信息技術(shù)領(lǐng)域重點(diǎn)研究對(duì)象之一。

近年來(lái)，國(guó)內(nèi)外學(xué)者提出了很多室內(nèi)定位技術(shù)和算法，主要有基于紅外線、超聲波、RFID（radio frequency identification）和LED[2]等技術(shù)。在基于手機(jī)慣性傳感器的計(jì)步方案中[3-6]，個(gè)人航位推測(cè)（personal dead reckoning，PDR）方案已成為當(dāng)前室內(nèi)定位的新熱點(diǎn)[7]。PDR技術(shù)運(yùn)用步數(shù)-步長(zhǎng)模型[8-9]，結(jié)合初始已知位置的位移和方向信息，使用慣性傳感器來(lái)計(jì)算室內(nèi)行人的位移量，因此需要計(jì)步器進(jìn)行距離量測(cè)。

加速度傳感器可以檢測(cè)人體運(yùn)動(dòng)過(guò)程中加速度的變化，對(duì)加速度值進(jìn)行處理判斷后輸出運(yùn)動(dòng)人員的累計(jì)步數(shù)[10]。目前，計(jì)步方案中基于加速度傳感器的計(jì)步算法成為研究熱點(diǎn)。文獻(xiàn)[11]的實(shí)驗(yàn)表明，基于加速度傳感器的計(jì)步算法具有高魯棒性和低復(fù)雜度的優(yōu)勢(shì)，這對(duì)智能手機(jī)有限的計(jì)算能力、內(nèi)存大小和續(xù)航能力極為重要。

當(dāng)前計(jì)步算法主要分為以下4類：

（1）設(shè)定閾值

文獻(xiàn)[12]提出在用戶腳上安裝慣性傳感器，通過(guò)一個(gè)加速度方差閾值的滑動(dòng)窗口過(guò)濾加速度數(shù)據(jù)，然后對(duì)其判斷是否達(dá)到兩個(gè)預(yù)設(shè)定的閾值。該方法依賴高精度加速度計(jì)，不適用于手機(jī)內(nèi)置的加速度傳感器。文獻(xiàn)[13]提出的基于加速度的計(jì)步算法引入了校正因子，用于修正幅值檢測(cè)的閾值，提高了檢測(cè)精度。文獻(xiàn)[14]提出在用戶腳踝安裝慣性傳感器進(jìn)行計(jì)步檢測(cè)，當(dāng)加速度值達(dá)到設(shè)定閾值時(shí)，步數(shù)累加，該算法也依賴高精度傳感器和靜態(tài)閾值。自適應(yīng)調(diào)整閾值能夠提高該計(jì)步方法的精度。

（2）峰值檢測(cè)

文獻(xiàn)[15]提出的行走時(shí)的水平加速計(jì)值和垂直加速計(jì)值變化曲線可以被近似認(rèn)為正弦波，通過(guò)識(shí)別正弦波進(jìn)行計(jì)步判定。文獻(xiàn)[16]的零交叉法對(duì)加速度信號(hào)低通濾波后，由加速度信號(hào)正向過(guò)零的次數(shù)進(jìn)行計(jì)數(shù)。零交叉法對(duì)于噪聲較少的信號(hào)工作良好，然而正常情況下，加速度信號(hào)更為復(fù)雜，且不按周期分布。因而對(duì)于零交叉法，難以精確地確定步數(shù)。文獻(xiàn)[17]首先通過(guò)低通濾波器對(duì)加速計(jì)數(shù)據(jù)過(guò)濾噪聲，然后檢測(cè)兩個(gè)局部最小值之間選取局部最大值，根據(jù)最小值與最大值之差是否大于預(yù)設(shè)定閾值進(jìn)行計(jì)步檢測(cè)。峰值檢測(cè)算法的復(fù)雜度比較低，但當(dāng)用戶遇到干擾時(shí)，同樣會(huì)達(dá)到峰值，檢測(cè)到多余的步數(shù)。

（3）零速率修正

文獻(xiàn)[18-19]使用零速率修正（zero velocity update，ZUPT）方法進(jìn)行步數(shù)檢測(cè)，對(duì)加速度積分獲得垂直位移，并通過(guò)幾何計(jì)算得出步長(zhǎng)信息。該方法需要將傳感器裝置固定在腰上，對(duì)噪聲的抗干擾能力較差。文獻(xiàn)[20]提出一種粒子濾波框架下利用建筑物結(jié)構(gòu)先驗(yàn)知識(shí)對(duì)ZUPT算法計(jì)算的軌跡進(jìn)行修正的算法，提高了定位精度。

（4）算法融合

文獻(xiàn)[21]針對(duì)之前算法對(duì)手機(jī)擺放位置和使用習(xí)慣等限制，提出了一種精確的計(jì)步算法。該算法第一階段從智能手機(jī)的加速度計(jì)獲取線性加速度值和重力值。然后，獲取線性加速度值的水平分量，并且確定線性加速計(jì)數(shù)據(jù)的周期波動(dòng)的起始點(diǎn)。第二階段采用相關(guān)系數(shù)的概念，對(duì)采集的傳感測(cè)量值判斷是否符合相似波形趨勢(shì)并計(jì)算步數(shù)。相比之前算法，該算法針對(duì)手機(jī)不同擺放位置的處理具有明顯的優(yōu)勢(shì)。

Alzantot等人[22]通過(guò)使用有限狀態(tài)機(jī)（finite state machine，F(xiàn)SM）與閾值進(jìn)行計(jì)步檢測(cè)，根據(jù)步態(tài)變化調(diào)整相應(yīng)閾值。Yim[23]在此算法基礎(chǔ)上，對(duì)有限狀態(tài)機(jī)增加一個(gè)狀態(tài)，更好地屏蔽噪聲數(shù)據(jù)，提高了計(jì)步精度。有限狀態(tài)機(jī)對(duì)加速度正弦波檢測(cè)效果較好且復(fù)雜度小，但Alzantot和Yim的算法沒(méi)有對(duì)數(shù)據(jù)進(jìn)行預(yù)處理操作，實(shí)驗(yàn)結(jié)果也表明其抗干擾能力較弱。

以上計(jì)步算法[12-23]大多在理想情況下采集數(shù)據(jù)，極少考慮復(fù)雜的現(xiàn)實(shí)應(yīng)用環(huán)境對(duì)加速度采集數(shù)據(jù)造成的噪聲干擾。對(duì)此，本文提出一種使用加速度差分作為特征的有限狀態(tài)機(jī)計(jì)步算法，稱為加速度差分狀態(tài)機(jī)計(jì)步算法（acceleration differential based on finite state machine，AD-FSM）。與現(xiàn)有算法相比，本文計(jì)步算法具有以下特點(diǎn)：（1）以加速度差分為特征；（2）閾值設(shè)定與步頻、采樣頻率相關(guān)；（3）屏蔽噪聲機(jī)制，可以有效地屏蔽異常情況，提供精確的計(jì)步結(jié)果。

2　加速度差分狀態(tài)機(jī)計(jì)步算法

Alzantot和Yim設(shè)計(jì)的FSM在正常情況下，對(duì)如圖1所示的正弦波檢測(cè)效果較好。在異常情況下，如手機(jī)震動(dòng)來(lái)電，手動(dòng)模擬行走等情況下，加速度變化如圖2所示。此前FSM算法對(duì)符合閾值的正弦波進(jìn)行步數(shù)判定，沒(méi)有考慮干擾情況下正弦波周期的異常變化，因而得出偏差較大的結(jié)果。針對(duì)干擾情況下出現(xiàn)的異常數(shù)據(jù)，本文使用加速度差分作為特征的有限狀態(tài)機(jī)計(jì)步算法。

Fig.1　Acceleration signal under normal environment圖1　正常情況下的加速度變化

Fig.2　Acceleration signal under interference environment圖2　干擾情況下的加速度變化

2.1數(shù)據(jù)預(yù)處理

手機(jī)內(nèi)置的加速度傳感器一般都是三軸的，可以測(cè)得手機(jī)發(fā)生運(yùn)動(dòng)時(shí)的前向加速度、側(cè)向加速度和垂直加速度，如圖3所示。實(shí)際應(yīng)用中，用戶攜帶手機(jī)的方式多種多樣，為了使計(jì)步算法能夠適用于不同位置上手機(jī)的擺放，一般采取的方法是對(duì)三軸加速度值的平方求和得到總的加速度，如式（1）所示，結(jié)果如圖4所示。

Fig.3　Raw signals from accelerometer圖3 原始加速度值

Fig.4　Acceleration after combination圖4　合成后的加速度值

2.2卡爾曼濾波

現(xiàn)代多數(shù)的智能手機(jī)配置的傳感器由于噪聲以及伴隨時(shí)間的衰退，經(jīng)常會(huì)產(chǎn)生錯(cuò)誤的數(shù)據(jù)，不能精確地測(cè)量數(shù)值。因此，需要算法對(duì)原始數(shù)據(jù)進(jìn)行矯正和過(guò)濾。

卡爾曼濾波器用于估計(jì)離散時(shí)間過(guò)程的狀態(tài)變量x∈?n[24]。這個(gè)離散時(shí)間過(guò)程由式（2）離散隨機(jī)差分方程描述：

定義觀測(cè)變量z∈?n，得到測(cè)量方程式（3）：

其中，隨機(jī)信號(hào)ωk和vk分別表示過(guò)程激勵(lì)噪聲和觀測(cè)噪聲，Q和R分別是其服從的正態(tài)分布的參數(shù)；μk為控制函數(shù)，矩陣B表示控制輸入μ∈?l的增益；矩陣A表示將上一時(shí)刻狀態(tài)線性映射到當(dāng)前時(shí)刻狀態(tài)的增益；矩陣H表示狀態(tài)變量xk對(duì)測(cè)量變量zk的增益。

根據(jù)卡爾曼濾波原理可以建立加速度信號(hào)的卡爾曼濾波模型。由于加速度信號(hào)為一維信號(hào)，并假設(shè)加速度信號(hào)間是相互獨(dú)立的，可以將式（2）和（3）簡(jiǎn)化為如下形式：

卡爾曼濾波過(guò)程包括兩步：首先根據(jù)歷史數(shù)據(jù)使用線性隨機(jī)差分方程生成一個(gè)當(dāng)前的預(yù)測(cè)值，然后根據(jù)觀測(cè)值對(duì)預(yù)測(cè)值進(jìn)行更新，并生成新的誤差協(xié)方差。簡(jiǎn)化后的卡爾曼濾波模型如圖5所示[24]。

Fig.5　Process of Kalman filter圖5　卡爾曼濾波器原理

卡爾曼濾波在消減噪聲和平滑數(shù)值方面具有非常好的效果，能夠較好地還原加速度變化趨勢(shì)，用于分析運(yùn)動(dòng)步態(tài)的周期性。從圖6中可以看到，經(jīng)過(guò)卡爾曼濾波后，噪聲有了極大的收斂，顯著提高了計(jì)步的準(zhǔn)確性。

Fig.6　Signal after performing Kalman filter圖6　卡爾曼濾波后的波形

2.3加速度差分

由圖7單步的波形變化可知，單步的加速度變化[24]可分解為正向加速度變化和負(fù)向加速度變化，并對(duì)加速度變化趨勢(shì)進(jìn)行累加，當(dāng)正向加速度變化量和負(fù)向加速度變化量都達(dá)到某個(gè)特定閾值后，即為完成一步。本文設(shè)定當(dāng)加速度前向差分大于閾值T，正向差分累計(jì)量Din加1；當(dāng)加速度逆向差分大于閾值，負(fù)向差分累計(jì)量Dde加1。具體公式如式（6）所示。

Fig.7　An example of state transitions during one step detection圖7 單步的波形變化

其中，差分閾值T用來(lái)抑制緩慢噪聲，最優(yōu)值T通過(guò)數(shù)值實(shí)驗(yàn)選取。

2.4有限狀態(tài)機(jī)

該有限狀態(tài)機(jī)主要有S0、S1、S2這3個(gè)狀態(tài)，分布如圖7所示。S0表示平穩(wěn)狀態(tài)，即人開(kāi)始行走和行走結(jié)束的狀態(tài)；S1表示峰值狀態(tài)，用戶邁步，加速度達(dá)到了最大值；S2表示谷值狀態(tài)，用戶收腳，加速度減少到最小值。

為了描述該狀態(tài)機(jī)流程，引入如下符號(hào)：

Thr：加速度起始閾值；

De_Thr：干擾閾值；

In_Peek_Thr：在一個(gè)采樣周期內(nèi)，正向加速度變化量能達(dá)到的最大值；

De_Peek_Thr：在一個(gè)采樣周期內(nèi)，負(fù)向加速度變化量能達(dá)到的最大值。

狀態(tài)機(jī)流程圖如圖8所示，具體描述如下：

Fig.8　Flow chart ofAD-FSM圖8AD-FSM流程圖

開(kāi)始在S0狀態(tài)，當(dāng)加速度小于Thr閾值后，進(jìn)入S1峰檢測(cè)狀態(tài)，將Din和Dde置0。

在S1狀態(tài)時(shí)，增加噪聲屏蔽機(jī)制。當(dāng)遇到噪聲干擾時(shí)，因加速度波形會(huì)在極短的時(shí)間內(nèi)劇烈波動(dòng)，Dde會(huì)和Din一起增加，但因?yàn)镈e_Thr的值小于或等于In_Peek_Thr，所以Dde會(huì)首先滿足De_Thr的條件，返回起始狀態(tài)S0，重新開(kāi)始檢測(cè)，以此過(guò)濾異常數(shù)據(jù)。只有在正常步行下，Din增加至In_Peek_Thr同時(shí)Dde小于De_Thr，進(jìn)入S2谷值檢測(cè)狀態(tài)。

在S2狀態(tài)時(shí)，Dde增加至De_Peek_Thr，狀態(tài)機(jī)返回S0狀態(tài)，步數(shù)加1。

Fig.9　States ofAD-FSM under normal environment圖9正常情況下的AD-FSM狀態(tài)變化

圖9和圖10分別為正常步行和干擾條件下步行，加速度值與AD-FSM的狀態(tài)機(jī)狀態(tài)變化。從圖9中可以看到，在未行走時(shí)段，狀態(tài)機(jī)在S0狀態(tài)與S1狀態(tài)反復(fù)，并未進(jìn)入S2狀態(tài)。當(dāng)用戶開(kāi)始行走，狀態(tài)機(jī)從S0到S1至S2狀態(tài)正常切換，完成計(jì)步。圖10驗(yàn)證了AD-FSM在遇到異常干擾時(shí)，狀態(tài)機(jī)由于S1的噪聲檢測(cè)機(jī)制，可以較好地過(guò)濾異常數(shù)據(jù)。

Fig.10　States ofAD-FSM under interference environment圖10干擾情況下的AD-FSM狀態(tài)變化

AD-FSM完整算法如下所示。

3　實(shí)驗(yàn)及結(jié)果分析

本文實(shí)驗(yàn)對(duì)算法閾值和算法性能進(jìn)行分析。算法閾值實(shí)驗(yàn)使用劍橋大學(xué)[11]的數(shù)據(jù)集，該數(shù)據(jù)集由27個(gè)人，130次實(shí)驗(yàn)，6種擺放位置組成。通過(guò)該數(shù)據(jù)集對(duì)算法中使用到的閾值進(jìn)行校準(zhǔn)與分析。第二部分實(shí)驗(yàn)使用2臺(tái)Android智能手機(jī)（MEIZU MX4/100 Hz，SAMSUNG N7100/100 Hz）和1個(gè)Fitbit智能手環(huán)，智能手機(jī)預(yù)裝Noom Walk計(jì)步APP。

一般來(lái)講，計(jì)步精度評(píng)估分為平均有向相對(duì)誤差δ和平均相對(duì)誤差ε，其計(jì)算公式如式（7）和式（8）所示。其中Cest(i)為算法對(duì)第i個(gè)樣本得到的估算計(jì)步結(jié)果，Cgt(i)為算法對(duì)第i個(gè)樣本得到的真實(shí)計(jì)步結(jié)果。平均有向相對(duì)誤差δ反映閾值變化影響測(cè)量值與真實(shí)值的偏差程度，而平均相對(duì)誤差ε衡量計(jì)步方案的精度。

3.1算法閾值分析

實(shí)驗(yàn)開(kāi)始階段，通過(guò)算法分析對(duì)各閾值進(jìn)行初始化，初始值設(shè)置見(jiàn)表1。將數(shù)據(jù)集記錄的數(shù)據(jù)輸入到程序中，其他閾值保持初始值不變的情況下，多次改變?cè)O(shè)定值，通過(guò)對(duì)比實(shí)驗(yàn)結(jié)果，選取最優(yōu)閾值。

Table 1　Initial value of thresholds表1 閾值設(shè)定初始值

3.1.1差分閾值

差分閾值T是判斷加速度變化的標(biāo)準(zhǔn)，直接影響加速度差分累積量的結(jié)果。由圖11中可以看出，當(dāng)T=0.047時(shí)，平均相對(duì)誤差最小?；诒疚乃惴▽?duì)T值進(jìn)行如下分析：當(dāng)T值設(shè)置得越大，Din和Dde的變化量就越小，加速度變化量就越難達(dá)到累計(jì)量，測(cè)量結(jié)果比實(shí)際數(shù)少，平均相對(duì)誤差增大。T值設(shè)置得越小，Din和Dde的變化就越大，加速度變化量就越易達(dá)到累計(jì)量，測(cè)量結(jié)果比實(shí)際數(shù)多，平均相對(duì)誤差也會(huì)增大。只有當(dāng)T值設(shè)定在一個(gè)合理的范圍內(nèi)，平均相對(duì)誤差才能達(dá)到最小值。

Fig.11　Relationship betweenTandε圖11　T值與平均相對(duì)誤差的關(guān)系

3.1.2加速度起始閾值

AD-FSM算法中狀態(tài)機(jī)的Thr決定S0到S1的起始點(diǎn)，即Din起始累加位，由圖7單步波形變化可以看出，Din的起始位應(yīng)在9.0之上。圖12的實(shí)驗(yàn)結(jié)果也證明了上述觀點(diǎn)，當(dāng)Thr=9.6時(shí)，狀態(tài)機(jī)轉(zhuǎn)換效果最好。

Fig.12　Relationship betweenThrandε圖12　Thr值與平均相對(duì)誤差的關(guān)系

3.1.3差分累計(jì)值

每個(gè)人的步頻因身高、年齡、性別的不同而有所差異，本文假設(shè)最大步頻SF為180 bpm，則單步周期Cs，由式（9）計(jì)算出為1/3 s。峰值In_Peek_Thr和谷值De_Peek_Thr為加速度變化量最大值，當(dāng)加速度變化量全為正或負(fù)時(shí)，加速度變化量最大值等于一個(gè)步頻內(nèi)采樣點(diǎn)總數(shù)，則由式（10）計(jì)算可得In_Peek_ Thr=De_Peek_Thr=8。

當(dāng)干擾屏蔽閾值De_Thr設(shè)置較小時(shí)，因無(wú)法過(guò)濾噪聲干擾，造成檢測(cè)結(jié)果偏大；設(shè)置較大時(shí)，則因過(guò)濾正常值，造成檢測(cè)結(jié)果偏小。

分析表2實(shí)驗(yàn)結(jié)果，驗(yàn)證由公式計(jì)算得到的In_ Peek_Thr和De_Peek_Thr為最優(yōu)累計(jì)值，且De_Thr等于3時(shí)，平均相對(duì)誤差和平均有向相對(duì)誤差最小。當(dāng)De_Thr大于3時(shí)，檢測(cè)結(jié)果偏大，反之，檢測(cè)結(jié)果偏小，驗(yàn)證以上分析。

Table 2　Relationship between Peek_Thr, De_Thr andε,δ表2　Peek_Thr、De_Thr與平均相對(duì)誤差、平均有向相對(duì)誤差的關(guān)系

分析以上實(shí)驗(yàn)結(jié)果，不合適的閾值可能會(huì)導(dǎo)致以下兩種現(xiàn)象：無(wú)法過(guò)濾噪聲干擾和有些區(qū)段或被遺漏，這都會(huì)影響計(jì)步結(jié)果的精確度?；跍y(cè)試結(jié)果，認(rèn)定以下數(shù)值：當(dāng)SAF=5時(shí)，T=0.047，Thr=9.6，In_Peek_Thr=8，De_Peek_Thr=8，De_Thr=3。在計(jì)步時(shí)，根據(jù)用戶步態(tài)自適應(yīng)地分配閾值，是有可能實(shí)現(xiàn)的，也是將來(lái)的工作。

3.2算法性能分析

Noom Walk APP、Fitbit手環(huán)和Android傳感器API提供的Step Counter傳感器，是目前市場(chǎng)上幾類成熟的計(jì)步方法。Noom Walk是當(dāng)前Android應(yīng)用市場(chǎng)下載量居首的計(jì)步軟件。Fitbit手環(huán)是一款內(nèi)置計(jì)步功能的可穿戴健康腕帶。Android系統(tǒng)提供的Step Counter傳感器，供開(kāi)發(fā)者多在非計(jì)步器APP中使用。

本實(shí)驗(yàn)環(huán)節(jié)共有7名測(cè)試者（4男3女）參與，每名測(cè)試者在實(shí)驗(yàn)過(guò)程中攜帶兩部相同的手機(jī)和佩戴運(yùn)動(dòng)手環(huán)，分別標(biāo)記為主機(jī)和副機(jī)。要求每名測(cè)試者分別進(jìn)行4組不同步數(shù)和不同測(cè)試場(chǎng)景的測(cè)試。

該實(shí)驗(yàn)階段共分為兩種情況：首先分析在正常行走條件下，計(jì)步算法的準(zhǔn)確性和穩(wěn)定性；然后通過(guò)分析在干擾情況下的計(jì)步結(jié)果來(lái)驗(yàn)證計(jì)步算法的魯棒性。

3.2.1正常情況下步行

表3為在不同步數(shù)情況下，各計(jì)步方案的平均相對(duì)誤差結(jié)果。由表3結(jié)果可以看出，在步數(shù)為17時(shí)，其誤差率在5%左右。當(dāng)步數(shù)為500時(shí)，大部分計(jì)步算法誤差率低于1%。Noom Walk APP和Android Step Counter檢測(cè)步數(shù)的敏感性較低。因此，在大多數(shù)情況下，兩者計(jì)步結(jié)果往往小于實(shí)際步數(shù)。同時(shí)，F(xiàn)itbit、UPTIME和Modified FSM-Based方法具有較高的敏感性，但是一個(gè)微小的晃動(dòng)（上或下）可能會(huì)導(dǎo)致其計(jì)步。

實(shí)驗(yàn)表明，數(shù)據(jù)量越大，提供的有效信息越多，計(jì)步算法的準(zhǔn)確度越高。本文算法的平均誤差在1.12%，優(yōu)于其他方案。實(shí)驗(yàn)對(duì)比所用到的計(jì)步方案平均誤差在2.80%，說(shuō)明大部分計(jì)步方案在只包含靜止和走路的正?；顒?dòng)中可以可靠地進(jìn)行計(jì)步。

Table 3　Performance of step detection algorithms under normal environment表3　正常行走幾種計(jì)步方案的平均相對(duì)誤差結(jié)果對(duì)比

3.2.2干擾情況下步行

接下來(lái)，測(cè)試人員在以下干擾環(huán)境下行走并采集數(shù)據(jù)：

場(chǎng)景1行走過(guò)程中，手持采集設(shè)備行走100步，采集其間晃動(dòng)手機(jī)進(jìn)行干擾；

場(chǎng)景2手持采集設(shè)備行走100步，采集其間來(lái)電震動(dòng)10 s進(jìn)行干擾；

場(chǎng)景3手機(jī)置于桌子，來(lái)電震動(dòng)10 s干擾；

場(chǎng)景4手動(dòng)晃動(dòng)采集設(shè)備10 s。

表4為在不同測(cè)試場(chǎng)景下，各計(jì)步方案的平均計(jì)步結(jié)果，其中數(shù)值均為步數(shù)。

分析實(shí)驗(yàn)結(jié)果，在場(chǎng)景1中，運(yùn)動(dòng)造成的干擾對(duì)其他計(jì)步方案均有影響，且未考慮干擾情況的FSM算法計(jì)步結(jié)果較差；在場(chǎng)景2和場(chǎng)景3中，Noom Walk、Android Step Counter和AD-FSM均能夠屏蔽噪聲的干擾；但在場(chǎng)景4中，只有本文AD-FSM算法能夠很好地屏蔽干擾。

由表3和表4的對(duì)比結(jié)果來(lái)看，本文算法在兩種情況下的計(jì)步結(jié)果更加逼近真值，誤差率均小于平均誤值，反映出本文算法的穩(wěn)定性和健壯性。

4　結(jié)束語(yǔ)

對(duì)已有計(jì)步算法實(shí)驗(yàn)分析可知，閾值設(shè)定和抗干擾處理能力都會(huì)影響計(jì)步精度，而現(xiàn)有算法很少關(guān)注這一問(wèn)題。對(duì)此，本文使用加速度差分作為特征的有限狀態(tài)機(jī)計(jì)步算法進(jìn)行計(jì)步檢測(cè)。首先通過(guò)對(duì)原始加速度平方和求值，使算法結(jié)果與手機(jī)擺放方向無(wú)關(guān)，然后利用卡爾曼濾波去除噪聲干擾。最后，使用基于加速度差分的有限狀態(tài)機(jī)進(jìn)行計(jì)步檢測(cè)。實(shí)驗(yàn)結(jié)果表明，當(dāng)用戶以常規(guī)方式進(jìn)行步數(shù)檢測(cè)時(shí)，所設(shè)計(jì)的方案優(yōu)于其他方案，但差別不大。在數(shù)據(jù)采集遇到人為或意外干擾情況下，本文方案較其他方案有著極大的準(zhǔn)確度優(yōu)勢(shì)。本文計(jì)步算法結(jié)合運(yùn)動(dòng)狀態(tài)分析動(dòng)態(tài)調(diào)整閾值，并融合方向等其他數(shù)據(jù)進(jìn)行室內(nèi)定位系統(tǒng)的開(kāi)發(fā)，也是下一步的研究方向。

Table 4　Performance of step detection algorithms under interference environments表4　干擾條件下幾種計(jì)步方案的計(jì)步結(jié)果對(duì)比

References:

[1]Cayir Y,Aslan S M,Akturk Z.The effect of pedometer use on physical activity and body weight in obese women[J]. European Journal of Sport Science,2015,15(4):351-356.

[2]Wu Nan,Wang Xudong,Hu Qingqing,et al.Multiple LED based high accuracy indoor visible light positioning scheme [J].Journal of Electronics and Information Technology,2015, 37(3):727-732.

[3]Harle R.A survey of indoor inertial positioning systems for pedestrians[J].IEEE Communications Surveys&Tutorials, 2013,15(3):1281-1293.

[4]Youssef M,Yosef M A,El-Derini M.GAC:energy-efficient hybrid GPS-accelerometer-compass GSM localization[C]// Proceedings of the 2010 IEEE Global Telecommunications Conference,Miami,USA,Dec 6-10,2010.Piscataway,USA: IEEE,2010:1-5.

[5]Constandache I,Choudhury R R,Rhee I.Towards mobile phone localization without war-driving[C]//Proceedings of the 2010 International Conference on Computer Communications,San Diego,USA,Mar 14-19,2010.Piscataway,USA: IEEE,2010:1-9.

[6]Li Fan,Zhao Chunshui,Ding Guanzhong,et al.A reliable and accurate indoor localization method using phone inertial sensors[C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing,Pittsburgh,USA,Sep 5-8,2012. New York,USA:ACM,2012:421-430.

[7]Ojeda L,Borenstein J.Personal dead-reckoning system for GPS-denied environments[C]//Proceedings of the 2007 IEEE International Workshop on Safety,Security and Rescue Robotics,Roma,Sep 27-29,2007.Piscataway,USA:IEEE,2007:1-6.

[8]Shih W Y,Chen L Y,Lan K C.Estimating walking distance with a smart phone[C]//Proceedings of the 2012 5th International Symposium on Parallel Architectures,Algorithms and Programming,Taipei,China,Dec 17-20,2012.Piscataway, USA:IEEE,2012:166-171.

[9]Subramanian S P,Sommer J,Zeh F P,et al.PBIL PDR for scalable bluetooth indoor localization[C]//Proceedings of the 2009 3rd International Conference on Next Generation Mobile Applications,Services and Technologies,Cardiff,UK, Sep 15-18,2009.Piscataway,USA:IEEE,2009:170-175.

[10]Zhao N.Full-featured pedometer design realized with 3-axis digital accelerometer[J].Analog Dialogue,2010,44(6):1-5.

[11]Brajdic A,Harle R.Walk detection and step counting on unconstrained smartphones[C]//Proceedings of the 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing,Zurich,Switzerland,Sep 8-12,2013.New York, USA:ACM,2013:225-234.

[12]Jimenez A R,Seco F,Prieto C,et al.A comparison of pedestrian dead-reckoning algorithms using a low-cost MEMS IMU[C]//Proceedings of the 2009 IEEE International Symposium on Intelligent Signal Processing,Budapest,Hungary, Aug 26-28,2009.Piscataway,USA:IEEE,2009:37-42.

[13]Oner M,Pulcifer-Stump J A,Seeling P,et al.Towards the run and walk activity classification through step detection—an Android application[C]//Annual International Conference of the IEEE Engineering in Medicine and Biology Society, San Diego,USA,2012:1980-1983.

[14]Hu Weiya,Lu Jialiang,Jiang Sheng,et al.WiBEST:a hybrid personal indoor positioning system[C]//Proceedings of the 2013 IEEE Wireless Communications and Networking Conference,Shanghai,China,Apr 7-10,2013.Piscataway,USA: IEEE,2013:2149-2154.

[15]Jang H J,Kim J W,Hwang D H.Robust step detection method for pedestrian navigation systems[J].ElectronicsLetters,2007,43(14):749-751.

[16]Beauregard S,Haas H.Pedestrian dead reckoning:a basis for personal positioning[C]//Proceedings of the 3rd Workshop on Positioning,Navigation and Communication,Hannover,Germany,Mar 16,2006:27-35.

[17]Wang He,Sen S,Elgohary A,et al.No need to war-drive: unsupervised indoor localization[C]//Proceedings of the 10th International Conference on Mobile Systems,Applications,and Services,Low Wood Bay,UK,Jun 25-29,2012. New York,USA:ACM,2012:197-210.

[18]Lan K C,Shih W Y.Using simple harmonic motion to estimate walking distance for waist-mounted PDR[C]//Proceedings of the 2012 IEEE Wireless Communications and Networking Conference,Shanghai,China,Apr 1-4,2012. Piscataway,USA:IEEE,2012:2445-2450.

[19]Lo C C,Chiu C P,Tseng Y C,et al.A walking velocity update technique for pedestrian dead-reckoning applications [C]//Proceedings of the 2011 IEEE 22nd International Symposium on Personal,Indoor and Mobile Radio Communications,Toronto,Canada,Sep 11-14,2011.Piscataway,USA: IEEE,2011:1249-1253.

[20]Gu Yang,Song Qian,Li Yanghuan,et al.A particle filter method for pedestrian navigation using foot-mounted inertial sensors[J].Journal of Electronics&Information Technology,2015,37(2):484-488.

[21]Pan M S,Lin H W.A step counting algorithm for smartphone users:design and implementation[J].IEEE Sensors Journal,2015,15(4):2296-2305.

[22]Alzantot M,Youssef M.UPTIME:ubiquitous pedestrian tracking using mobile phones[C]//Proceedings of the 2012 Wireless Communications and Networking Conference, Shanghai,China,Apr 1-4,2012.Piscataway,USA:IEEE,2012: 3204-3209.

[23]Yim J.A smartphone indoor positioning method[J].International Journal of Smart Home,2013,7(5):9-18.

[24]Welch G,Bishop G.An introduction to the Kalman filter, TR 95-041[R].University of North Carolina at Chapel Hill, 1995.

附中文參考文獻(xiàn)：

[2]吳楠,王旭東,胡晴晴,等.基于多LED的高精度室內(nèi)可見(jiàn)光定位方法[J].電子與信息學(xué)報(bào),2015,37(3):727-732.

[20]谷陽(yáng),宋千,李楊寰,等.基于慣性鞋載傳感器的人員自主定位粒子濾波方法[J].電子與信息學(xué)報(bào),2015,37(2):484-488.

WANG Gechao was born in 1990.He is an M.S.candidate at Jiangnan University,and the member of CCF.His research interests include wireless sensor networks and indoor location,etc.

王革超（1990—），男，河南鄭州人，江南大學(xué)碩士研究生，CCF會(huì)員，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，室內(nèi)定位等。

LIANG Jiuzhen was born in 1968.He is a professor and M.S.supervisor at Jiangnan University,and the senior member of CCF.His research interests include artificial intelligence and pattern recognition,etc.

梁久禎（1968—），男，山東泰安人，江南大學(xué)教授、碩士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識(shí)別等。

CHEN Jing was born in 1977.She is a lecturer at Jiangnan University,and the member of CCF.Her research interests include wireless sensor networks and bioinformatics,etc.

陳璟（1977—），女，工學(xué)博士，江南大學(xué)講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，生物信息學(xué)等。

ZHU Xiangjun was born in 1991.He is an M.S.candidate at Jiangnan University,and the member of CCF.His research interests include wireless sensor networks and indoor location,etc.

朱向軍（1991—），男，江蘇徐州人，江南大學(xué)碩士研究生，CCF會(huì)員，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，室內(nèi)定位等。

*The National Natural Science Foundation of China under Grant Nos.61170121,71503103(國(guó)家自然科學(xué)基金). Received 2015-10,Accepted 2016-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-01-04,http://www.cnki.net/kcms/detail/11.5602.TP.20160104.0953.004.html

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP212

doi:10.3778/j.issn.1673-9418.1510006

Step Counting Algorithm Based on Finite State Machine Using Acceleration Differential?

WANG Gechao+,LIANG Jiuzhen,CHEN Jing,ZHU Xiangjun
School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China +Corresponding author:E-mail:wanggechao@gmail.com

Abstract:In the application of step counting,how to keep the stability and accuracy of step counting algorithm is a challenging problem.The traditional approach using fixed thresholds and peak detection can not solve the problem of stability and adaptability.In response to these problems,this paper proposes a step counting algorithm based on finite state machine using acceleration differential as a feature(AD-FSM).Firstly,AD-FSM uses the sum of squared acceleration to orientation-independent and applies Kalman filtering to eliminate noise.Then,AD-FSM counts steps by finite state machine.The experimental results show that the proposed algorithm can provide accurate counting results in the normal and interference situations,the errors are only 1.12%and 4.00%.This highlights the ability of the proposed algorithm to provide stability,robustness,and efficient counting in complex scenarios with fewer complications.

Key words:indoor location;step counting;anti-interference;finite state machine;acceleration differential