基于實(shí)時步長匹配的行人室內(nèi)定位方法①

鐘立揚(yáng), 崔超遠(yuǎn), 王儒敬, 孫丙宇(中國科學(xué)院 合肥智能機(jī)械研究所, 合肥 3003)(中國科學(xué)院大學(xué), 北京 00049)

基于實(shí)時步長匹配的行人室內(nèi)定位方法①

鐘立揚(yáng)1,2, 崔超遠(yuǎn)1, 王儒敬1, 孫丙宇11(中國科學(xué)院 合肥智能機(jī)械研究所, 合肥 230031)2(中國科學(xué)院大學(xué), 北京 100049)

針對室內(nèi)定位研究中行人航位推算(PDR)算法的傳統(tǒng)步長模型無法充分反映個體差異性的問題, 提出一種以衛(wèi)星測距為基礎(chǔ), 建立個體步長特征數(shù)據(jù)庫代替步長模型的方法. 在室外將衛(wèi)星測距應(yīng)用到步長測算中, 建立不同速度特征與步長的對應(yīng)關(guān)系. 在室內(nèi), 改進(jìn)了K-最近鄰(KNN)算法, 對跨步進(jìn)行實(shí)時步長匹配, 結(jié)合方向信息計(jì)算出行人的當(dāng)前位置. 實(shí)驗(yàn)結(jié)果表明, 室內(nèi)定位最大誤差距離可以控制在4%以內(nèi), 平均絕對誤差距離可以控制在2%以內(nèi), 定位精度較傳統(tǒng)步長模型有較大提高.

室內(nèi)定位; 行人航位推算; 衛(wèi)星測距; K-最近鄰; 實(shí)時步長匹配

1 引言

隨著經(jīng)濟(jì)社會的發(fā)展和智能手機(jī)的高度普及, 基于位置的服務(wù)(LBS, location based service)已經(jīng)越來越得到重視, 尤其在大型復(fù)雜的室內(nèi)環(huán)境中, 如火車站、機(jī)場、大型超市、醫(yī)院等區(qū)域, 人們對位置服務(wù)有迫切需求. 目前行人的室外定位主要通過衛(wèi)星和無線通信基站來實(shí)現(xiàn), 但由于建筑物對衛(wèi)星信號的遮擋及衰減作用, 無法實(shí)現(xiàn)行人的室內(nèi)定位, 而基站的定位精度在幾十到幾百米, 同樣無法滿足室內(nèi)的精確定位.

針對行人室內(nèi)定位, 目前的解決方案包括有源和無源兩種方式. 有源定位需要事先布設(shè)信號節(jié)點(diǎn), 主要是測量終端設(shè)備信號強(qiáng)度, 通過指紋定位算法進(jìn)行定位, 如WiFi定位[1,2], 藍(lán)牙定位[3], ZigBee定位[4]等.無源定位不需布設(shè)信號節(jié)點(diǎn), 一種是將慣性導(dǎo)航機(jī)制引入移動設(shè)備[5], 另一種是行人航位推算(PDR, pedestrian dead reckoning)算法[6-8].

PDR算法根據(jù)慣性傳感器數(shù)據(jù)對行人行走步數(shù)、步長和方向進(jìn)行計(jì)算, 獲取行走距離和方向. 算法的關(guān)鍵在于準(zhǔn)確地估算行人的步長, 文獻(xiàn)[6]建立了一個基于步頻和步長之間線性關(guān)系的步長估計(jì)模型; 文獻(xiàn)[7]使用一個與跨步周期內(nèi)最大最小加速度有關(guān)的非線性經(jīng)驗(yàn)?zāi)Ｐ? 文獻(xiàn)[8]將人行走模式近似為一個倒立的單擺, 通過三角關(guān)系計(jì)算步長. 由于不同人步長的差異與個人身高、習(xí)慣、心情等均有一定關(guān)系, 上述線性和非線性模型很難反應(yīng)出不同個體的步長差異.

智能手機(jī)內(nèi)置加速度計(jì), 磁航向計(jì)等MEMS傳感器, 為室內(nèi)行人航位推算提供了方便,通過采集加速度數(shù)據(jù), 利用峰值法檢測跨步[9-11]. 為了充分考慮個體步長的差異, 提出一種以衛(wèi)星測距為基礎(chǔ), 建立個體步長特征數(shù)據(jù)庫代替步長模型的方法. 在室外將衛(wèi)星測距引入步長測算中, 建立不同速度特征與步長的對應(yīng)關(guān)系, 進(jìn)入室內(nèi)后采用改進(jìn)的K-最近鄰(KNN, knearest-neighbor)算法對步長進(jìn)行實(shí)時匹配, 結(jié)合磁航向計(jì)確定行走方向, 完成行人行走距離和方向的推算.

2 行人室內(nèi)定位原理

2.1 PDR算法基本原理

通常情況下, 認(rèn)為行人在很短的采樣時間內(nèi)做直線運(yùn)動, 當(dāng)已知某一時刻的位置、航向和行人位移量就可以推斷出下一時刻的位置信息. 圖1演示了PDR算法的基本原理, 通過遞推公式(1)可以計(jì)算出行人k時刻的位置.

圖1 PDR算法原理圖

Ek和Nk表示行人第k步在東北天坐標(biāo)系下的東向和北向坐標(biāo), Sk表示該步的步長, ak表示該步的航向[12,13].

2.2 跨步檢測

推算行人位置的前提是準(zhǔn)確檢測行人的每一次跨步. 在一個完整的行走周期中, 人首先處于靜止?fàn)顟B(tài);開始邁步時身體向上向前運(yùn)動, 加速度出現(xiàn)波峰狀態(tài);當(dāng)人在垂直和水平方向的速度達(dá)到最大后加速度出現(xiàn)波谷狀態(tài), 開始減速, 當(dāng)邁出的腳和地面接觸穩(wěn)定后整個周期結(jié)束.

手機(jī)所處的設(shè)備坐標(biāo)系中, X軸沿屏幕向右, Y軸沿屏幕向上, Z軸則垂直于屏幕向外[14]. 當(dāng)手機(jī)屏幕向上水平握持行走時, 設(shè)備坐標(biāo)系的Z軸與東北天坐標(biāo)系中的天向軸大致重合, 通過檢測Z軸加速度峰值即可實(shí)現(xiàn)對行人跨步的檢測.

由于手機(jī)內(nèi)置MEMS傳感器的精度相比專業(yè)設(shè)備較低, 以及行人行走狀態(tài)的不確定性造成加速度信號出現(xiàn)較多的毛刺, 需要對原始數(shù)據(jù)做相應(yīng)的平滑濾波處理. 平滑濾波算法選用簡單移動平均法(SMA, simple moving average), 滑動窗口大小設(shè)為L, SMA算法將包括當(dāng)前測量值A(chǔ)k在內(nèi)的前L個測量值平均值作為當(dāng)前時刻的平滑輸出結(jié)果.

當(dāng)測量得到新的加速度Ak時, 即把新數(shù)據(jù)加入滑動窗口, 同時刪除最舊的一個加速度Ak-L, 依次遞推. L的值根據(jù)實(shí)驗(yàn)效果選取為20, 圖2為某次行走過程中采樣頻率為100Hz時手機(jī)Z軸加速度原始數(shù)據(jù)經(jīng)過平滑濾波后的時間序列, 峰值即為周期內(nèi)最大加速度Amax, 谷值即為周期內(nèi)最小加速度Amin.

圖2 平滑濾波后Z軸加速度

為了提高檢測的準(zhǔn)確率, 只有峰值大小超過閾值的才會被判定為有效峰值, 實(shí)驗(yàn)中發(fā)現(xiàn)閾值設(shè)為0.4可以最大程度地過濾無效峰值同時保留有效峰值. 人自然行走的步頻在1-3Hz之間[15], 所以在檢測峰值的同時還要計(jì)算峰值的間隔時間, 屏蔽不在合理時間間隔區(qū)間的峰值.

2.3 個體步長特征數(shù)據(jù)庫的建立

不同人步長的差異與個人身高、習(xí)慣、心情等均有一定關(guān)系, 常規(guī)的線性或非線性步長模型在面對不同個體時很難適用. 目前智能手機(jī)集成的衛(wèi)星位置解算芯片, 融合了GPS, 北斗, 格洛納斯等系統(tǒng)的多源定位信息, 精度可以達(dá)到米級. 故本文直接使用手機(jī)給出的位置信息, 將衛(wèi)星測距引入行人的步長測算,進(jìn)而建立一個屬于個體的步長特征數(shù)據(jù)庫. 測量A, B兩點(diǎn)所在位置的經(jīng)緯度, 利用公式(3)即可計(jì)算兩點(diǎn)位置之間的直線距離S[15].

其中(Lng1,Lat1)表示A點(diǎn)經(jīng)緯度, (Lng2,Lat2)表示B點(diǎn)的經(jīng)緯度, a=Lng1-Lng2為兩點(diǎn)經(jīng)度之差, b=Lat1-Lat2為兩點(diǎn)緯度之差, 6378137為地球半徑, 單位為米.

為了提高測距的準(zhǔn)確性, 需要行人以近似直線的方式從A點(diǎn)步行到B點(diǎn), 并盡量保持一種速度狀態(tài), 在衛(wèi)星測距的同時檢測跨步, 記錄每步的特征值, 利用式(4)計(jì)算該種速度狀態(tài)的平均步長.

其中S為式(3)計(jì)算得到的A, B兩點(diǎn)之間的直線距離, N為這一過程檢測到的跨步總數(shù).

假設(shè)速度有m種狀態(tài), 步長特征包括一個跨步周期內(nèi)的最大加速度Amax、最小加速度Amin、周期時長T.室外衛(wèi)星測距的過程也就是步長特征數(shù)據(jù)庫建立的過程, 共有m×N組跨步特征值集合, 同時也是m種速度狀態(tài)下跨步的特征值與步長對應(yīng)關(guān)系的生成過程. 記D=(d1, d2, …, dm)代表m種不同速度狀態(tài)下的步長集合, C=(Amax, Amin, T)代表一個跨步特征值的集合, 按(C, dj)鍵值對的形式存儲數(shù)據(jù), 其中dj∈D.

2.4 步長匹配

進(jìn)入室內(nèi)后, 初始位置由衛(wèi)星定位信息給出. 記C*=(A*max, A*min, T*)為檢測到的新的跨步特征值集合, m種速度狀態(tài)代表m種已有的類, 匹配過程的實(shí)質(zhì)是對C*做出分類的過程.

行人行走的開始和結(jié)束階段步長特征數(shù)據(jù)并不穩(wěn)定, 波動較大. 為了減少KNN算法計(jì)算量, 匹配過程中對個體步長特征數(shù)據(jù)庫進(jìn)行簡化. 實(shí)驗(yàn)表明, 只保留每種速度狀態(tài)下(N/3,2×N/3)區(qū)間即中間段的m×N/3組特征數(shù)據(jù)完全可以保證匹配的準(zhǔn)確率, 記n=m×N/3.匹配算法如下:

①計(jì)算C(i)與C*間的歐氏距離dist(C(i),C*),i=1,2…,n;

② 按升序?qū)ist(C(i),C*)排序, 找出排在前k個的最小距離對應(yīng)的C(i);

③ 根據(jù)存儲的(C, dj)鍵值對查找這k組C(i)對應(yīng)的步長d;

④ D集合中出現(xiàn)次數(shù)最多的d值作為當(dāng)前C*對應(yīng)的步長;中C與C*的歐氏距離dist(C,C*)為

2.5 方向確定

智能手機(jī)內(nèi)置磁航向計(jì), 根據(jù)對地磁場的感應(yīng)可以實(shí)時指示出手機(jī)當(dāng)前頂部與正北方向的夾角, 當(dāng)手機(jī)繞著Z軸旋轉(zhuǎn)時, 該角度值將發(fā)生改變, 此方向?qū)⒆鳛樾腥说男凶叻较?

3 測試與驗(yàn)證

3.1 測試系統(tǒng)工作流程

本次測試以搭載Android5.0系統(tǒng)的小米4C手機(jī)為例, 采樣頻率100Hz. 首先測試人員需要在室外測算不同行走速度下的步長, 然后在進(jìn)入室內(nèi)后實(shí)時匹配新的跨步步長, 最后結(jié)合方向信息計(jì)算位置, 整個測試系統(tǒng)的工作流程如圖3所示.

圖3 測試系統(tǒng)工作流程

3.2 測試結(jié)果與誤差分析

室外測試地點(diǎn)選在環(huán)境開闊的中國科學(xué)院合肥智能機(jī)械研究所大樓外的人行道上, 手機(jī)最少可以連接10顆衛(wèi)星,

最多可以連接20顆以上的衛(wèi)星, 保證了衛(wèi)星測距的準(zhǔn)確性. 速度狀態(tài)選為較慢速度、正常速度和較快速度三種, 測試人員身高178cm, 在三種速度狀態(tài)下的實(shí)際行走步數(shù)均控制在100步, 得到的步長計(jì)算結(jié)果分別為0.60m、0.74m和0.88m.

室內(nèi)測試地點(diǎn)選在智能所大樓內(nèi)的走廊, 測試距離50m, 分別計(jì)算在較慢速度、正常速度、較快速度以及變速行走這四組形式下的距離, 每組測試5次,得到的20組測試數(shù)據(jù)分布如圖4所示.

圖4 20組測試數(shù)據(jù)

從圖中可以看出, 雖然各種速度狀態(tài)下的計(jì)算距離每次均不相同, 但都圍繞50m上下浮動. 偏差的原因包括兩點(diǎn), 一是本方法固有的誤差, 因?yàn)槿说娜魏蝺刹降牟介L不會絕對相等; 二是步長匹配過程中產(chǎn)生的誤差, 即步長的誤判. 進(jìn)一步分析測試數(shù)據(jù), 結(jié)果如表1所示.

表1 測試數(shù)據(jù)分析

可以得出, 最大誤差距離可以控制在4%以內(nèi), 平均絕對誤差距離可以控制在2%以內(nèi). 不同的行走狀態(tài)下均能實(shí)現(xiàn)較為準(zhǔn)確地步長匹配, 尤其對于實(shí)際中最容易出現(xiàn)的變速行走狀態(tài), 同樣具有很好的效果.由于較慢速度下加速度數(shù)值波動稍大, 導(dǎo)致計(jì)算結(jié)果誤差范圍擴(kuò)大.

將同樣的測試數(shù)據(jù)分別應(yīng)用在文獻(xiàn)[6]的線性模型:

其中a, b為系數(shù), f為頻率. 以及文獻(xiàn)[7]中的非線性經(jīng)驗(yàn)?zāi)Ｐ?

其中H為系數(shù), Amax, Amin分別為一個跨步周期內(nèi)的最大最小加速度. 得到的結(jié)果與本文的方法比較, 如圖5所示.

圖5 結(jié)果比較

通過比較可以發(fā)現(xiàn), 本文的方法相比文獻(xiàn)[6]和文獻(xiàn)[7]最大誤差距離分別減少48.8%和35.8%, 平均絕對誤差距離分別減少54.3%和36.6%. 文獻(xiàn)[6]中的線性模型在較慢速度下計(jì)算步長偏小, 整體計(jì)算距離減小, 誤差加大. 文獻(xiàn)[7]的方法則在變速行走時誤差加大. 相比之下, 本文的方法對于個體差異適應(yīng)性強(qiáng),整體數(shù)據(jù)結(jié)果穩(wěn)定性好, 沒有出現(xiàn)較大的偏差.

4 結(jié)語

行人室內(nèi)定位研究具有十分廣闊的應(yīng)用前景, 特別是不依賴外部信息可以自主工作的PDR算法是室內(nèi)定位研究的一大熱點(diǎn). 本文將PDR算法應(yīng)用于普通的智能手機(jī), 利用優(yōu)化的KNN算法實(shí)時匹配室外衛(wèi)星測距得到的行人三種速度下的步長, 實(shí)現(xiàn)了室內(nèi)環(huán)境下行人的無源自主定位. 室內(nèi)最大誤差距離可以控制在4%以內(nèi), 平均絕對誤差可以控制在2%以內(nèi), 相比常規(guī)的步長模型結(jié)果穩(wěn)定, 定位精度更高. 但本文的方法依賴于室外衛(wèi)星定位精度, 同時行人的實(shí)際步長遠(yuǎn)遠(yuǎn)不止三種, 同樣會造成計(jì)算誤差. 后續(xù)研究考慮對速度的劃分通過聚類方式實(shí)現(xiàn), 同時對匹配結(jié)果與步長模型計(jì)算結(jié)果進(jìn)行加權(quán)組合, 給出更準(zhǔn)確可靠的步長估算, 進(jìn)一步提高行人的室內(nèi)定位精度.

1肖亞龍,張士庚,王建新.一種基于多維標(biāo)度和區(qū)域細(xì)化的無線室內(nèi)定位方法.計(jì)算機(jī)學(xué)報(bào),2016.(在線出版)

2 周錦,李煒,金亮,陳曦.基于KNN-SVM算法的室內(nèi)定位系統(tǒng)設(shè)計(jì).華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,43(增刊I): 517–520.

3 陳國平,馬耀輝,張百珂.基于指紋技術(shù)的藍(lán)牙室內(nèi)定位系統(tǒng).電子技術(shù)應(yīng)用,2013,39(3):104–107.

4 曹建玲,孫希勝,索建偉,任智.基于梯度信息的ZigBee網(wǎng)絡(luò)PAN間混合路由算法.華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,42(6):79–84.

5 陳天嘯,曾鵬飛,虞致國,王曉澗,顧曉峰.iOS 平臺下慣性室內(nèi)定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn).計(jì)算機(jī)工程與應(yīng)用,2014,50(15): 207–210.

6 Li F, Zhao C, Ding G, et al. A reliable and accurate indoor localization method using phone inertial sensors. Proc. of the 2012 ACM Conference on Ubiquitous Computing. ACM. 2012. 421–430.

7 田國會,張慶賓,丁娜娜.基于WT-UKF 的PDR/GPS 組合定位算法.控制與決策,2015,30(1):86–90

8 邸文華,劉昱,黃鎮(zhèn)彩.基于iOS平臺的步長計(jì)算方案與實(shí)現(xiàn).電子測量技術(shù),2012,35(9):32–35

9 周瑞,羅磊,李志強(qiáng),桑楠.一種基于智能手機(jī)傳感器的行人室內(nèi)定位算法.計(jì)算機(jī)工程,2016,(11):22–26.

10 Roy N, Wang H, Roy Choudhury R. I am a smartphone and I can tell my user’s walking direction. Proc. of the 12th Annual International Conference on Mobile Systems, Applications, and Services. ACM. 2014. 329–342.

11宋敏,申閆春.室內(nèi)定位航位推測算法的研究與實(shí)現(xiàn).計(jì)算機(jī)工程,2013,39(7):293–297.

12王克己.室內(nèi)定位系統(tǒng)中的行人航跡推算研究[碩士學(xué)位論文].北京:北京郵電大學(xué),2014.

13陳國良,張言哲,汪云甲,孟曉林.WiFi-PDR室內(nèi)組合定位的無跡卡爾曼濾波算法.測繪學(xué)報(bào),2015,44(12):1314–1321.

14陳春陽,郭英,畢京學(xué).手機(jī)陀螺儀與加速度計(jì)聯(lián)合定位初步分析.導(dǎo)航定位學(xué)報(bào),2014,2(4):74–77.

15 陳偉.基于GPS和自包含傳感器的行人室內(nèi)外無縫定位算法研究[博士學(xué)位論文].合肥:中國科學(xué)技術(shù)大學(xué),2010.

Method of Pedestrian Indoor Positioning Based on Real-Time Step-Size Matching

ZHONG Li-Yang1,2, CUI Chao-Yuan1,WANG Ru-Jing1, SUN Bing-Yu11(Institute of Intelligent Machine, Chinese Academy of Sciences, Hefei 230031, China)2(University of Chinese Academy of Sciences, Beijing 100049, China)

Focus on the problem of the traditional step-size model used in pedestrian dead reckoning algorithm cannot fully reflect individual differences in the research of indoor positioning. We propose a method to establish database of individual feature of step-size based on satellite ranging and then replace the step-size model. Satellite ranging is applied to calculate the step-size in the outdoor, the corresponding relationship between different speed features and step-size is set up. Then we carry out real-time step-size matching indoors for the step, using improved K-nearest-neighbor(KNN) algorithm and calculate people’s current position combined with direction information. The actual test results show that the maximum error distance can be controlled within 4%, and the mean absolute error distance can be controlled within 2%. The positional accuracy has a larger enhancement compared to the traditional step-size model.

indoor positioning; pedestrian dead reckoning; satelliteranging; K-nearest-neighbor; real-time step-size matching

2016-07-05;收到修改稿時間:2016-08-29

10.15888/j.cnki.csa.005656