區域生長輔助的地圖配準在室內定位中的應用*

楊衛軍, 鄒 贏, 徐正蓺, 張新鵬, 黃 超, 魏建明

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

?

區域生長輔助的地圖配準在室內定位中的應用*

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

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

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

區域生長; 粒子濾波; 地圖配準; 航位推算; 零速度檢測

0 引 言

室內定位在應急救援過程中有著舉足輕重的作用，準確的位置信息有助于指揮人員更好地實施救援指揮調度，同時也有助于保護救援人員的生命安全。基于慣性傳感器的室內定位技術區別于其他無線定位技術，無需額外基礎設施的輔助就能完成定位。因此，以其自完備的特性完全適用于突發情況。

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

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

1 算法框架

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

圖1 算法框架圖Fig 1 Algorithm frame

2 關鍵算法

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

2.1 零速度檢測

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

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

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

(1)

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

2.2 地圖配準算法

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

2.3 RG算法

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

首先以當前零速度時刻位置點Pk為種子，令

i=1,2,…,N

(2)

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

圖4 區域生長結果示意圖Fig 4 Result of region growing

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

圖5 時間復雜度和地圖復雜度的關系Fig 5 Relationship between time complexity and map complexity

3 實 驗

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

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

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

表1 測試結果統計

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

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

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

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

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

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

4 結 論

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

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

[2] 張 迅,黎 偉,周建國,等.基于傳感器的室內測試軌跡系統[J].傳感器與微系統,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] 馮成濤,申崇江,劉 楊,等.基于粒子濾波的室內地圖匹配算法[C]∥第五屆中國衛星導航學術年會論文集——S9組合導航與導航新方法,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

中國科學院戰略性技術先導專項資助項目(XDA06000000)

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

TP 212.9

A

1000—9787(2016)10—0141—04

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

應用技術