一种融合地图与传感器信息的室内地图匹配新算法

doi:10.3969/j.issn.1001-893x.2014.12.013引用格式:余彦培.一种融合地图与传感器信息的室内地图匹配新算法J.电讯技术,2014,54(12):1656-1662.YUYan-pei.ANewIndoorMapMatchingAlgorithmFusingMapandSensorInformationJ.TelecommunicationEngineering,2014,54(12):1656-1662.一种融合地图与传感器信息的室内地图匹配新算法*余彦培*(中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101)摘摇要:基于粒子滤波技术,提出了融合地图信息与传感器信息的室内地图匹配算法,对于在室内定位中由状态空间模型描述的非线性系统,通过非参数化的蒙特卡洛(MonteCarlo)模拟方法来实现递推贝叶斯滤波,将室内地理信息数据、传感器信息、无线定位信息融入到粒子的权重值中,对观测值进行不断修正。实验证明,所提出的基于粒子滤波的地图匹配技术有效解决了由于无线定位结果穿墙、错定至隔壁房间而造成的用户体验差等问题,同时对室内定位结果进行了修正,提高了室内定位精度。关键词:位置服务;室内定位;地图匹配;传感器信息;粒子滤波;数据融合中图分类号:TN967.2摇摇文献标志码:A摇摇文章编号:1001-893X(2014)12-1656-07ANewIndoorMapMatchingAlgorithmFusingMapandSensorInformationYUYan-pei(StateKeyLaboratoryofEnvironmentalInformationSystem,InstituteofGeographicSciencesandNaturalResourcesResearch,ChineseAcademySciences,Beijing100101,China)Abstract:Thispaperproposesanewmapmatchingalgorithmbasedonparticlefilter,whichfusesmapandsensorinformation.Firstly,thenonlinearindoorpositioningsystemisdescribedbystatespacemodel.Then,therecursiveBayesianfilteringisimplementedthroughtheparameterizedMonteCarlomethod,andthein鄄doorgeographicdata,sensors,wirelesspositioninginformationarefusedtomodifytheweightsoftheparti鄄clesandtheobservedvalue.Theexperimentshowsthattheproposedmapmatchingtechnologycaneffec鄄tivelysolvetheuserexperienceproblemscausedbywrongpositioningresult.Also,thisalgorithmimprovestheindoorpositioningaccuracy.Keywords:locationbasedservice;indoorpositioning;mapmatching;sensorsinformation;particlefilter;datafusion1摇引摇言在位置服务(LocationBasedService,LBS)发展如火如荼的今天,GNSS(GlobalNavigationSatelliteSystem)已经在室外得到广泛应用,以WiFi为代表的室内定位技术则正成为LBS领域技术攻关的新热点。目前室内精确定位主要依托WiFi技术,各大科研机构及企业在WiFi定位方面的研究已基本达到极限,精度基本在实验环境12m,商用环境25m,很难进一步提高1。如文献2提出的WiFiSLAM定位技术,定位误差在24m,该技术已被美·6561·第54卷第12期2014年12月电讯技术TelecommunicationEngineeringVol.54摇No.12Dec.2014*收稿日期:2014-09-05;修回日期:2014-11-17摇摇Receiveddate:2014-09-05;Reviseddate:2014-11-17基金项目:中国博士后科学基金资助项目(2014M550818)FoundationItem:ChinaPostdoctoralScienceFoundation(2014M550818)通讯作者:yuypigsnrr.ac.cn摇摇Correspondingauthor:yuypigsnrr.ac.cn国Apple公司收购,我国目前业内领先的“寻鹿冶室内定位技术定位误差在13m3。在商用环境,米级的精度尚不能使定位精确到具体的房间,且由于室内地图较室外地图更加精细,定位结果的抖动在室内地图上体现更加明显,造成较差的用户体验。在室内无线定位精度达到极限的情况下,融合传感信息和室内地图匹配的辅助技术是提升室内定位精度的有效方法。利用定位数据融合室内地图的过程通常称之为地图匹配。地图匹配广泛应用在室外的车载导航系统中,使用道路网信息对车辆进行约束。文献4提出的基于位置点匹配算法实现了直线道路、多边形区域等各种路考的准确纠正,但是在用户位置出现间断时仅依靠位置点的地图匹配算法很难实现准确地图匹配。在室内定位导航中,则需要点(门)、线(路网)、面(房间)要素来约束。文献5中,利用室内基础矢量信息构建室内结构通行模型,并融合传感器和地图信息结果,对无线定位结果进行了约束,但该文献中只是对最终定位结果进行地图约束,在约束过程中并未考虑定位结果的平滑滤波问题。平滑滤波对定位效果优化有重要作用,粒子滤波是一种重要的滤波手段,由于其非参数化的特点,摆脱了解决非线性滤波问题时随机变量必须满足高斯分布的制约,为分析非线性动态系统提供了一种有效的解决方法,已经用于室内定位领域6。在传感信息辅助方面,文献7提出了一种融合个人鞋式IMU信息和建筑平面信息的算法框架,能够获得相对较高的室内个人导航精度。上述文献分别从地图匹配与传感器辅助的角度在一定程度上改善了定位精度。本文结合地图匹配与传感器辅助技术,基于粒子滤波技术进一步提高了室内无线定位精度。本文首先介绍了粒子滤波的原理;其次介绍室内地理信息拓扑结构模型,在此基础上,提出了基于地图矢量模型的新的地图匹配算法,该算法结合室内地图拓扑结构,以无线定位结果为观测值,并使用手机传感器得到的PDR(PedestrianDeadreckoning)信息,减小位置更新过程中的误差,不断修正无线定位结果,使其趋近于真值;最后,对算法进行了实验验证,多次实验结果表明,本算法对于改善室内定位导航系统中定位误差具有较好的效果。2摇粒子滤波原理粒子滤波核心是通过大量随机试验近似后验概率分布,用样本均值替换积分运算,从而获得状态最小方差分布,可以用在任何形式的状态空间模型上。一个动态系统模型可由以下方程来描述:xk=f(xk-1,vk-1)(1)zk=h(xk,wk)(2)式(1)、(2)分别为系统的状态方程和观测方程,xk为k时刻系统状态向量,zk为观测值,vk-1和wk分别为系统噪声和观测噪声。初始概率密度为p(x0|z0)=p(x0)(3)根据系统状态转移模型预测:p(xk|z1:k-1)=乙p(xk|xk-1)p(xk-1|z1:k-1)dxk-1(4)由先验概率推导后验概率:p(xk|z1:k)=p(zk|xk)p(xk|z1:k-1)p(zk|z1:k-1)(5)其中,p(zk|z1:k-1)=乙p(zk|xk)p(xk|z1:k-1)dxk(6)以上为粒子滤波的基本原理,得到求后验概率的递推方法,但是积分很难实现。此时利用状态空间中大量的样本点来近似要估计的分布,利用这些样本把积分问题转换为求和问题:p(xk|zk)抑移Ni=1棕ik啄(xk-xik)(7)式中,xik为是k时刻第i个样本的状态,其相应的权值为棕ik。权值的更新为棕ik=棕ik-1p(zk|xik)p(xik|xik-1)q(xik|xi0:k-1,z1:k)(8)式中,q(xik|xi0:k-1,z1:k)为重要性密度函数。3摇面向地图匹配的室内地理信息数据结构室内地图与室外地图不同,不同的地图服务商提供的室内地图风格不一,尚未形成统一的行业标准8。从本质上找出建筑物共性的空间拓扑模型,并以面向对象的思想进行分类,是室内地图匹配技术中有效快速获取地理信息数据的关键所在。室内地图表达的元素通常有走廊、房间、卫生间、入口、扶梯、电梯、楼梯等,这些元素都是由点、线、面描述的矢量图形,由这些点、线、面构成的空间数据是室内地图共性的部分,对这些空间数据进行总结归类是地图匹配算法的关键。室内地图中房间、走廊等对象的本质都是多边形,多边形的每条边可认为是墙壁,根据多边形的边·7561·第54卷余彦培:一种融合地图与传感器信息的室内地图匹配新算法第12期上是否有门,将所有的多边形分为两大类,可到达区域和不可到达区域,门是出入可通达区域的唯一途径,如图1所示,位于多边形上的圆点代表门,没有门的多边形如天井、中空等称为不可到达区域。图1摇室内地图Fig.1Indoormap室内信息数据结构如图2所示,“+冶代表公有的,可操作的,ID是区域唯一标识,Type是区域可通达性的标志位,Points是围成多边形各个顶点坐标,并按顺序存储,Doors是可到达区域边界上门的坐标。这种数据结构设计的优势在于能够方便读取地理信息矢量数据,并作为每个粒子的属性进行存储,加快粒子与地理信息融合速度,提高程序运行效率。图2摇室内地理信息数据结构Fig.2Datastructureofindoorgeographicinformationsystem4摇基于粒子滤波的地图匹配新算法4.1摇状态转移方程和观测方程除无线定位与地图信息外,手机终端的传感器信息也是室内定位有力的辅助信息。利用传感器信息,采用PDR技术,可检测人员行走的方向与步频、步长。PDR技术中的步频、步长检测已较为成熟,难点在于用户运动方向检测上。大部分PDR应用中,传感器模块都是固定在鞋或腰上,以便获得较为准确的方向,显然,这种方式有较大的局限性:由于人们携带手机等移动定位终端的随意性,该方式无法广泛应用于手机导航服务中。文献9中提出了一种基于终端姿态的运动方向检测算法,可在行人不以固定姿态手持终端情况下对行人运行方向进行准确测量。本文将采用这种方法来进行航位推算,推算公式作为粒子滤波的状态转移方程。公式为Xk=EkNk准éëêêêêùûúúúúk=Ek-1+Lk·sin(准k)Nk-1+Lk·cos(准k)准k-1+驻准éëêêêêùûúúúúk(9)式中,Lk、准k分别为第k次定位的行走距离(PDR的计步值乘以步长得到)和航向(由PDR得到),驻准k为第k-1步到第k步的航向变化,Ek-1、Nk-1为行走第k步前的东向坐标和北向坐标,Ek、Nk为完成第k步后的东向坐标和北向坐标。观测方程根据室内无线定位结果、PDR结果及其误差范围给出:Zk=EkNkLk渍éëêêêêêùûúúúúúk+啄e啄n啄l啄éëêêêêêùûúúúúú渍(10)式中,啄e、啄n分别是无线定位结果东向和北向均方根误差,其中Ñ滓2=啄2e+啄2n(11)4.2摇粒子权重计算室内无线定位系统可以看作一个离散系统,知道定位结果在当前时刻为止所有状态和样本,依据定位粒子滤波的状态转移方程可以对每个粒子得到一个预测粒子,越是接近真实状态的粒子,当然越有可能获得观测值,因此需要对每个粒子赋予一个权值。把样本集合与样本权值集合来辨识当前时刻的后验概率密度函数,如下式:p(s0:k|z1:k)=1N移Ni=1棕ik啄(s0:k-si0:k)(12)式中,si0:k:i=1,2,N为从后验概率分布采集的随机样本,N表示样本的个数,z1:k表示从开始时刻·8561·www.teleonline.cn电讯技术摇摇摇摇2014年到k时刻的观测值,wik,i=1,N表示第k个样本的归一化权值。本文遵循重要性采样原则来计算粒子的权值,后验概率密度函数用离散的加权粒子来近似的表示,所有粒子的加权和可以表示定位状态的估计值。本文提出的粒子的权重计算将由以下四个方面考虑。(1)融入室内地理信息的权重利用房间、走廊的拓扑关系可以进一步限定行人运动轨迹,减小定位的误差范围。如图3所示,圆圈里面的点表示当前时刻定位状态,周围圆圈代表误差范围,当融合地理信息拓扑关系后,即可排除阴影部分的可能性,从而减小定位误差范围,提升定位精度。本文提出室内空间结构简单模型将作为每个粒子的属性,并根据相邻两个粒子之间的位置关系推算粒子的权重值。图3摇定位误差范围Fig.3Rangeoferror粒子在可通达和不可通达区域的权重,本文在前面对可通达区域和不可通达区域作了详细解释,当粒子处于不可通达的区域中,将作为无效粒子。棕r=0,不可通达区棕reach,可通达区(12)式中,棕reach是粒子落入可通达区域的权重值,棕reach为大于0的常量值。如图4,“*冶是落入不可通达区域中的粒子,“+冶为可通达区域中的粒子。图4摇可通达和不可通达区域中的粒子Fig.4Particlesinaccessibleareaandunaccessiblearea(2)粒子穿墙与不穿墙的权重门是出入可通达区域的唯一途径,当粒子没有通过门这一要素,从一个可通达区域到另一个可通达区域时,被视为穿墙。当相邻两个粒子发生穿墙现象时,粒子的权重值赋予0。棕c=0,穿越墙体棕normal,从门通过(13)式中,棕normal是相邻两个粒子通过门穿越墙壁的权重值,为大于0的常量值。(3)相邻粒子距离权重在状态转移方程中,步长作为观测量之一,对当前所以样本进行估计。在粒子更新之后,相邻粒子间的距离有可能大于观测的行走距离,这时需要使用距离权重来限制。棕d=0,dis>S棕walk,0臆dis臆S(14)式中,dis为相邻两个粒子之间的距离,S为当前时刻的行走距离观测值。(4)粒子的方向权重值图5中兹为定位点的观测方向(图中的指向P)与前后两粒子连线的夹角,夹角越小说明预估粒子运动方向与行人运动方向越相近。图5摇方向的定义Fig.5Definitionofdirection由于用携带的手机来识别人的运动方向技术尚未成熟,对于方向的观测值存在更大的不确定性,因此方向权重值的最大值不能在总权值中占主导地位。方向性权重值如下:棕兹=0,兹>孜cos兹,兹臆孜(15)式中,兹取绝对值,孜为角度差阈值,一般取45毅。棕兹取值在0和1之间,兹越小,棕兹越大,保证了不会因为权值过大而造成不确定性扩大,又能很好地反映方向估计值与观测值变化趋势。4.3摇算法流程本文提出的算法总体上分为4个阶段,即初始化阶段、搜索阶段、决策阶段、重采样阶段,如图6所示。·9561·第54卷余彦培:一种融合地图与传感器信息的室内地图匹配新算法第12期图6摇算法流程图Fig.6Algorithmflow(1)初始化阶段统一坐标系将定位点坐标、地图坐标系、惯性坐标系统一起来,转换成以东向为X轴、北向为Y轴的平面直角坐标系。为粒子赋予属性值。如图7所示,每个粒子(Particle)有4个属性,Location属性是Point类型,表示粒子的x、y坐标;Orientation表示粒子的方向;Step表示当前时刻粒子的步长;Geoinfo表示粒子中融入的地理信息,是Geographic类,包括粒子周围所有的面(shapes)、所有的线(lines)、所有的点(doors),还有粒子本身位于哪个面上。图7摇粒子的属性Fig.7Propertiesofparticle(2)搜索阶段首先由室内无线定位技术得到定位结果P以及定位误差范围滓,以P为中心、滓为半径的周围随机生成500个粒子,作为初始粒子,如图8所示。图8摇生成粒子群Fig.8Particlesgeneration然后由状态转移方程加上控制量对每一粒子计算得到一个预测粒子。(3)决策阶段得到预测粒子之后,并不是所有粒子都能接近真实状态,这时需要对所有粒子进行评价,依据4.2节所述,每个粒子都包含融入室内地理信息的权重棕ir、粒子穿墙与不穿墙的权重棕ic、相邻粒子距离权重棕id、粒子的方向权重棕i兹,将这4个权值累加得到每个粒子的总权值棕ik:棕ik=棕ir+棕ic+棕id+棕i兹,i=1,2,N(16)(4)重采样阶段为防止粒子产生退化现象,在重要性采样的基础上加上重采样10,复制权值大的粒子,淘汰权重值小的粒子。权重值归一化:棕ik=棕ik移Ni=1棕ik(17)归一化之后计算真实状态的估计值:P=移Nipi·棕i(18)下一轮滤波,再将重采样过后的粒子集输入到状态转移方程中。4.4摇算法实现的伪代码以下将用伪代码来解释本节所述算法:for摇i=1:Nu=randn;棕sum=0;摇摇forj=1:N摇摇摇棕sum=棕sum+w(j);摇摇摇if摇棕sum>=u摇摇摇摇摇P(:,i)=P(:,j);摇摇摇摇摇break;摇摇摇摇end摇摇endend(1)生成0,1区间均匀分布的随机数ui;(2)计算粒子的权值累计量棕sumi,i=1,2,N;(3)对于每个滋i,寻找归一化权值累计量大于或等于滋i的最小标号j,即姿j-1<ui<姿j。当ui落在区间姿j-1,姿j时,pjk被复制一次。经过重采样之后的粒子,就代表了真实状态的概率分布了。·0661·www.teleonline.cn电讯技术摇摇摇摇2014年5摇应用实例和结果分析实验采用Android系统的终端,基于WiFi室内定位技术获取无线定位结果,采用传感器为电子罗盘与加速度计传感器,以及相对坐标系下的高精度室内电子地图。图9为进房间时的前后时刻粒子分布图,k-1和k时刻无效区粒子落入不可通达区域(排烟井、燃气井),将视为无效粒子,还有一些粒子由于粒子间距离大于最大步长阈值,以及穿越没有门的墙壁,也将视为无效粒子。图9摇地图约束前的粒子分布图Fig.9Particlesdistributionbeforemapmatching根据这些条件将无效粒子剔除,得到图10效果。图中虽然粒子数目已经减少,但是不会出现穿墙的现象,进出房间更加平稳,而且提高了程序运行效率。图10摇地图约束后的粒子分布图Fig.10Particlesdistributionaftermapmatching利用上述算法进行实测,结果如图11所示。由图中可以看出,原始定位结果在地图上显示较乱,给用户造成较差的体验,只融合传感器信息的粒子滤波,由于没有地图的约束,时常会发生穿墙等现象,通过添加地图的约束的粒子滤波之后,进一步纠正了定位结果,不会出现穿墙或进错房间的现象。大量室内行走实验证明,采用基于粒子滤波的室内地图匹配算法,93%的时间能够将室内定位误差校正到2.2m以内。图11摇实测结果Fig.11Experimentresult6摇结摇论在室内定位中,无线定位精度无法保证定位结果落入正确的区域,定位误差23m时仍有可能出现定位结果落入隔壁房间等现象,导致用户体验很差。本文基于粒子滤波技术,提出了融合地图信息与传感器信息的室内地图匹配算法,将传感器得到的计步值与航向角引入系统的状态与观察方程,并在滤波器迭代过程中,利用地图信息对粒子进行优化。经过试验验证,本算法提升了定位精度,与传统滤波方向相比,在滤波过程中实现了地图匹配,有效防止了定位结果穿墙而过等现象。该技术可应用在手机WiFi或蓝牙定位系统中,使用户获得更好的用户体验,在目前室内定位技术应用蓬勃发展的今天,具有良好的应用前景。参考文献:1摇DengZhongliang,YuYanpei,YuanXie,etal.SituationandDevelopmentTendencyofIndoorPositioningJ.ChinaCommunications,2013(3):42-55.2摇KaoWeiwen,HuyBuiquang.IndoorNavigationwithSmar鄄tphone-basedVisualSLAMandBluetooth-connectedWheel-RobotC/Proceedingsof2013CACSInterna鄄·1661·第54卷余彦培:一种融合地图与传感器信息的室内地图匹配新算法第12期tionalAutomaticControlConference.Nantou:IEEE,2013:395-400.3摇百度百科.北京智慧图科技有限责任公司EB/OL.(2014-07-14)2014-10-28http:/baike.baidu.com/view/14180469.htm4摇王忠民,王青,张荣,等.一种基于位置点的地图匹配改进算法J.计算机应用研究,2013,30(11):3319-3323.WANGZhong-min,WANGQing,ZHANGRong,etal.Improvedmap-matchingalgorithmbasedonpositionpointsJ.ApplicationResearchofComputers,2013,30(11):3318-3319.(inChinese)5摇RuanFengli,DengZhongliang,AnQian,etal.AMethodofMapMatchinginIndoorPositioningC/Proceedingsof2014ChinaSatelliteNavigationConference(CSNC).Nanjing:s.n.,2014:669-679.6摇GustafssonF,GunnarssonF,BergmanN,etal.Particlefiltersforpositioning,navigation,andtrackingJ.IEEETransac鄄tionsonSignalProcessing,2002,50(2):425-437.7摇谢波,江一夫,严恭敏,等.个人导航融合建筑平面信息的粒子滤波方法J.中国惯性技术学报,2013,21(1):1-6.XIE-Bo,JIANGYi-fu,YANGong-min,etal.Novelpar鄄ticlefilterapproachforfusingbuildingplaneintopedes鄄triannavigationJ.JournalofChineseInertialTechnolo鄄gy,2013(1):1-6.(inChinese)8摇邓晨,夏青,林雕,等.基于空间认知的移动室内地图设计新模式J.系统仿真学报,2014,26(9):2097-2103.DENGChen,XIAQing,LINDiao,etal.MobileIndoorMapDesignModeBasedonCognitionofSpaceCognitionJ.JournalofSystemSimulation,2014,26(9):2097-2103.(inChinese)9摇WANGKeji,DengZhongliang,LuoShengmei,etal.Pedestri鄄andeadreckoninginhandheldterminalwithinertialmeas鄄urementunitC/Proceedingsof2014ChinaSatelliteNav鄄igationConference.Nanjing:s.n.,2014:681-690.10摇李善姬,禹爱兰.一种改进重采样的粒子滤波算法J.电讯技术,2011,51(9):35-38.LIShan-ji,YUAi-lan.AnimprovedresamplingparticlefilteringalgorithmJ.TelecommunicationEngineering,2011,51(9):35-38.(inChinese)作者简介:余彦培(1986),男,重庆人,2013年获博士学位,现从事博士后工作,主要研究方向为室内定位与地图。YUYan-peiwasborninChongqing,in1986.HereceivedthePh.D.degreein2013.Heisnowengagedinpostdoctoralresearch.Hisresearchconcernsindoorpositioningandmap.Email:yuypigsnrr.ac.cn·2661·www.teleonline.cn电讯技术摇摇摇摇2014年