區(qū)域生長輔助的地圖配準(zhǔn)在室內(nèi)定位中的應(yīng)用*

楊衛(wèi)軍, 鄒 贏, 徐正蓺, 張新鵬, 黃 超, 魏建明

(1.上海大學(xué) 通信與信息工程學(xué)院, 上海 200444； 2.中國科學(xué)院 上海高等研究院,上海 201210；3.上海商學(xué)院,上海 200235)

?

區(qū)域生長輔助的地圖配準(zhǔn)在室內(nèi)定位中的應(yīng)用*

楊衛(wèi)軍1,2, 鄒 贏3, 徐正蓺2, 張新鵬1, 黃 超2, 魏建明2

(1.上海大學(xué) 通信與信息工程學(xué)院, 上海 200444； 2.中國科學(xué)院 上海高等研究院,上海 201210；3.上海商學(xué)院,上海 200235)

地圖匹配(MM)算法通過粒子濾波(PF)利用室內(nèi)地圖信息來抑制基于慣性傳感器的室內(nèi)定位系統(tǒng)的誤差累計。利用區(qū)域生長(RG)算法結(jié)合當(dāng)前步長和方向信息在地圖上找到合理的落腳范圍，并以此來判斷粒子的有效性。這種方法能有效改善地圖配準(zhǔn)算法的實用性和計算復(fù)雜度。提出一種改進的零速度(ZV)檢測算法能準(zhǔn)確提取步伐信息，間接提升了零速度更新(ZUPT)算法和地圖配準(zhǔn)算法的精度。實驗結(jié)果表明:該算法的定位誤差小于1.0 %，定位精度比單純的航位推算(DR)算法平均提高了5.97 %。

區(qū)域生長; 粒子濾波; 地圖配準(zhǔn); 航位推算; 零速度檢測

0 引 言

室內(nèi)定位在應(yīng)急救援過程中有著舉足輕重的作用，準(zhǔn)確的位置信息有助于指揮人員更好地實施救援指揮調(diào)度，同時也有助于保護救援人員的生命安全?；趹T性傳感器的室內(nèi)定位技術(shù)區(qū)別于其他無線定位技術(shù)，無需額外基礎(chǔ)設(shè)施的輔助就能完成定位。因此，以其自完備的特性完全適用于突發(fā)情況。

然而，不管是通過慣性積分[1]還是通過計步[2]的方法來進行航位推算(dead-reckoning,DR)都無法消除誤差的累積。雖然在文獻[1,3,4]中利用零速度更新(zero velocity update,ZUPT)減小了誤差的累計，但無法從徹底根除?；诹Ｗ訛V波器(particle filter,PF)融合地圖信息輔助定位的算法[5,6]，利用地圖信息能顯著遏制誤差的累計。

本文基于DR+ZUPT+PF的算法框架，提出了一種新的融合地圖信息的方法。利用圖像分隔之區(qū)域生長(region growing,RG)算法來生成下一步合理的落腳區(qū)域，落在該區(qū)域的粒子認為是有效粒子，否則為無效粒子。這種方法相比文獻[7, 8]中通過計算線段間關(guān)系來判斷粒子有效性的方法，在計算復(fù)雜度上有明顯的改善，且只需要以圖片格式輸入處理器內(nèi)存中，簡化了地圖在計算機中的表示和存儲方法。

1 算法框架

本文提出的基于慣性傳感器的室內(nèi)定位算法框圖如圖1所示。

圖1 算法框架圖Fig 1 Algorithm frame

2 關(guān)鍵算法

單純DR的誤差以三次方的速度增長，利用ZUPT[9]方法能有效抑制誤差的累積。結(jié)合地圖信息利用PF算法[6]能進一步抑制方向的漂移。本文在上述基礎(chǔ)上，提出了改進的零速度檢測方法以及基于區(qū)域生長算法的地圖配準(zhǔn)方法。

2.1 零速度檢測

研究發(fā)現(xiàn)利用陀螺儀角速度閾值法檢測效果最好[9,10]。如圖2(a)所示，為陀螺儀部分信號圖。如圖2(b)所示為角速度閾值法的檢測結(jié)果。本文在此基礎(chǔ)上提出一種改進的檢測算法，通過增加滑窗平均和延遲判決來消除誤判點。

圖2 改進的零速度檢測算法實驗結(jié)果圖Fig 2 Experimental result of improved ZV detection algorithm

具體的，對于角速度的模值，利用滑窗均值代替單一時刻的模值

(1)

圖3 改進的零速度檢測算法Fig 3 Improved ZV detection algorithm

2.2 地圖配準(zhǔn)算法

通常利用PF方法進行地圖配準(zhǔn)(map-matching,MM)時，需要將地圖表示成點、線或者多邊形的幾何。用線段代表墻壁，線段之間是否相交表示行走中是否穿墻。在本部分設(shè)計了基于RG和PF的地圖配準(zhǔn)算法。

2.3 RG算法

RG是圖像分割的一種方法，用來尋找具有相似特征的像素集合構(gòu)成的區(qū)域。在本文中利用RG算法生成當(dāng)前步子合理的落腳點范圍。

首先以當(dāng)前零速度時刻位置點Pk為種子，令

i=1,2,…,N

(2)

式中 Pki為Pk周圍第i個像素點的坐標(biāo)位置，S為當(dāng)前跨步合理的落腳范圍，Lmax為最大可能步長。J(Pki)為Pki對應(yīng)的灰度值。Gth為判定灰度特征相似的門限值，將小于Gth并且在最大步長范圍內(nèi)的位置點劃歸到S區(qū)域內(nèi)，反之則劃歸到S之外。如圖4所示淺灰色部分所示即為S代表的區(qū)域。

圖4 區(qū)域生長結(jié)果示意圖Fig 4 Result of region growing

在PF階段，令落在S外的粒子為無效粒子，如圖4中灰色粒子所示。這種方法相比于文獻[6]中通過線段間關(guān)系判斷粒子有效性的方法在算法復(fù)雜度和執(zhí)行效率上有明顯的提升。具體的性能對比結(jié)果如圖5所示，RG算法的時間復(fù)雜度明顯小于線段關(guān)系法，且不會受地圖復(fù)雜度的影響。

圖5 時間復(fù)雜度和地圖復(fù)雜度的關(guān)系Fig 5 Relationship between time complexity and map complexity

3 實 驗

本次實驗將慣性測量單元置于腳尖位置，具體的安裝示意圖如圖6所示。

實驗中分別對7個人進行測試，每個人平均測3組，具體的測試路徑分兩種，一種如圖8所示為閉合的矩形路徑，另一種如圖9所示為平面隨機行走的閉合路徑。經(jīng)測距儀測量，圖8中實際行走距離為162.6 m，圖9中實際行走距離為188.8 m。具體的實驗結(jié)果的統(tǒng)計信息如表1所示。

圖6 實驗過程示意圖Fig 6 Diagram of experimental process

表1 測試結(jié)果統(tǒng)計

如圖7是對路徑1的誤差統(tǒng)計結(jié)果，其中灰色條表示DR的定位誤差，黑色條表示本文提出的算法的定位誤差。柱形條頂端標(biāo)注的是相對誤差(誤差與實際行走距離的比)。單純的DR平均相對誤差為7.46 %，穩(wěn)定性不高。而本文所提出的改進算法定位誤差均在1.0 %以內(nèi)，平均相對誤差為0.73 %，且對不同測試人員的穩(wěn)定性較高。

圖7 路徑1中兩種算法的誤差對比Fig 7 Comparison chart of error of two algorithms of path l

圖8所示為路徑1的實驗結(jié)果，點劃線為DR的實驗結(jié)果。實線表示本文提出的算法輸出的結(jié)果。虛線為實際參考路徑，是一個閉合的矩形路徑。從圖中可以看到在第一條長走廊的2/3距離不到的位置，DR由于誤差的累計已經(jīng)開始出現(xiàn)方向的偏差，并且持續(xù)累積。而結(jié)合RG和PF算法對DR進行修正能有效抑制誤差的累計。

圖8 閉合矩形路徑下兩種算法的對比圖Fig 8 Comparison diagram of two algorithms of closed rectangular path

圖9所示為路徑2的實驗結(jié)果，其中點劃線為DR算法輸出的行走軌跡。實線為本文算法的計算結(jié)果，虛線為實際的行走路徑。具體的DR的實際誤差為6.80 m，相對誤差為3.6 %。而經(jīng)過修正后的算法定位誤差明顯減小，實際誤差為0.73 m，相對誤差為0.39 %。

圖9 隨機路徑下兩種算法的對比圖Fig 9 Comparison diagram of two algorithms of random path

4 結(jié) 論

本文提出了一種改進的零速度檢測算法，在單純地使用角速度模值閾值法的基礎(chǔ)上能很好地消除奇點，提高零速度檢測的精度。此外提出利用DR算法生成跨步落腳點的合理區(qū)域，并以此來判決PF中粒子的有效性。通過這種方法能方便地應(yīng)用圖片格式的地圖信息，無需將地圖抽象成其他數(shù)據(jù)結(jié)構(gòu)形式，也避免了大量線段關(guān)系的計算，從而提高了MM算法的效率，降低了算法的復(fù)雜度。最終顯著的減小了DR的誤差累計，提高了定位精度。

[1] Foxlin E.Pedestrian tracking with shoe-mounted inertial sensor-s[J].Computer Graphics and Applications,2005,25(6):38-46.

[2] 張 迅,黎 偉,周建國,等.基于傳感器的室內(nèi)測試軌跡系統(tǒng)[J].傳感器與微系統(tǒng),2015,34(6):43-45，49.

[3] Jiménez A R,Seco F,Prieto J C,et al.Indoor pedestrian navigation using an INS/EKF framework for yaw drift reduction and a foot-mounted IMU[C]∥Positioning Navigation and Communication(WPNC),Dresden,Germany,2010:135-143.

[4] Xu Zhengyi,Wei Jianming,Zhang Bo,et al.A robust method to detect zero velocity for improved 3D personal navigation using inertial sensors[J] .Sensors,2015,15(4):7708-7727.

[5] Bao Haitao,Wong W C.A novel map-based dead-reckoning algorithm for indoor localization[J].Journal of Sensor and Actuator Networks,2014,3(1):44-63.

[6] Perttula A,Leppakoski H,Kirkko-Jaakkola M,et al.Distributed indoor positioning system with inertial measurements and map matching[J].Instrumentation and Measurement,2014,63(11):2682-2695.

[7] Pinchin J,Hide C,Moore T.A particle filter approach to indoor navigation using a foot mounted inertial navigation system and heuristic heading information[C]∥2012 International Conference on Indoor Positioning and Indoor Navigation(IPIN),IEEE,Australia,2012:1-10.

[8] 馮成濤,申崇江,劉 楊,等.基于粒子濾波的室內(nèi)地圖匹配算法[C]∥第五屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會論文集——S9組合導(dǎo)航與導(dǎo)航新方法,2014.

[9] Fischer C,Talkad Sukumar P,Hazas M.Tutorial:Implementation of a pedestrian tracker using foot-mounted inertial sensors[J].IEEE Pervasive Computing,2013,12(2):17-27.

[10] Skog I,H?ndel P,Nilsson J O,et al.Zero-velocity detection—An algorithm evaluation[J].IEEE Transactions on Biomedical Engineering,2010,57(11):2657-2666.

Application of map-matching aided by region growing in indoor positioning*

YANG Wei-jun1,2, ZOU Ying3, XU Zheng-yi2, ZHANG Xin-peng1, HUANG Chao2, WEI Jian-ming2

(1.School of Communication and Information Engineering,Shanghai University,Shanghai 200444,China;2.Shanghai Advanced Research Institute,Chinese Academy of Sciences,Shanghai 201210,China;3.Shanghai Business School,Shanghai 200235,China)

Map-matching(MM)algorithm is used to inhibit accumulation of error of indoor positioning system based on inertial sensor with particle filtering(PF)and indoor map.Use region growing(RG)algorithm,combined with step length and orientation,find reasonable area on indoor map,and decide validity of particles according to this.This method can reduce computational complexity and improve practicality of MM algorithm.An improved zero velocity(ZV)detection algorithm is proposed,which can extract step information accurately,and indirectly enhance precision of zero velocity update(ZUPT)algorithm and MM algorithm.Experimental result shows that localization error of the proposed algorithm is less than 1.0 % and the precision is increased by 5.97 % on average compared with dead-reckoning(DR) algorithm.

region growing(RG); particle filtering(PF); map-matching(MM); dead-reckoning(DR); zero velocity(ZV)detection

2015—11—16

中國科學(xué)院戰(zhàn)略性技術(shù)先導(dǎo)專項資助項目(XDA06000000)

10.13873/J.1000—9787(2016)10—0141—04

TP 212.9

A

1000—9787(2016)10—0141—04

楊衛(wèi)軍(1990-)，男，山西朔州人，碩士，研究方向為基于多傳感器融合的室內(nèi)定位技術(shù)的研究。

應(yīng)用技術(shù)