区域生长辅助的地图配准在室内定位中的应用*

杨卫军, 邹 赢, 徐正蓺, 张新鹏, 黄 超, 魏建明

(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-)，男，山西朔州人，硕士，研究方向为基于多传感器融合的室内定位技术的研究。

应用技术