基于GIS的室内定位约束与优化算法

林巍凌

(1.信息工程大学，河南 郑州 450000；2.海军兵种指挥学院，广东 广州 510430)



基于GIS的室内定位约束与优化算法

林巍凌1,2

(1.信息工程大学，河南 郑州 450000；2.海军兵种指挥学院，广东 广州 510430)

摘要：随着室内定位技术的不断发展，室内导航渐渐成为可能。但由于室内定位精度和稳定性较差，导致定位点漂移，导航引导错误，用户体验感差，无法满足室内精细导航需求。文中根据室内空间的特点，结合GIS空间分析与导航推测算法，设计出一种适合室内定位约束与优化算法，能在不影响定位效率的情况下很大程度上改善定位效果。经实际场地实验，效果良好。

关键词：室内定位；定位约束；室内地图；DR；导航推测

随着定位与导航技术应用的普及，人们对定位信息的需求逐渐拓展到室内，但不管是定位手段还是地图表达，室内一直是业界研究的一块盲区。十多年以来，为了解决室外定位导航“最后一公里”的问题，科技巨头和研究机构在室内定位技术方面开展了大量的研究，如基于移动通信网络的辅助GPS(A-GPS)、伪卫星(Pseudolite)、无线局域网(WLAN)、射频标签(RFID)、Zigbee、蓝牙(Bluetooth，BT)、超宽带无线电(UltraWideBand，UWB)、地磁其他卫星或地面数字通信及广播信号、红外定位、光跟踪定位、计算机视觉定位、超声波定位等。室内定位技术的长足进步，促进室内地图研究的兴起。谷歌于2011-11率先发布了室内地图，其中包括了美国、日本等国家的大型商场和机场。此后国内地图厂商，如百度、高德也相继推出自己的室内地图产品。不少创业公司也不失时机地展开研究，企图占有一席之地。有了室内地图，可以帮助用户更加清晰地辨别每个楼层的建筑物平面布局，了解建筑物内主要兴趣点的分布，给用户带来全新的购物、休闲体验。据不完全统计，目前可做展示使用的室内地图普遍比例尺在1∶50，甚至更大，覆盖全国300座城市，超过100万个室内兴趣点。但由于室内定位精度较差(通常在3～10m)，无法达到精细导航的需求，因此，本文提出一种室内定位约束算法，在一定程度上对定位结果进行修正，使定位效果更佳(并非提高定位精度)。

1室内定位约束必要性

目前主流室内定位技术均基于传感器(Wi-Fi或者蓝牙)进行定位，而室内环境错综复杂，干扰源多，信号反射、折射、衍射产生多径传播，室内的温度湿度变化，物体变动，人员流动都会对室内定位精度产生影响(见表1)。不管采用哪种定位技术，都摆脱不了其自身的局限性。

表1　不同定位技术对比

定位精度和稳定性差在实际导航应用中表现为定位点跳跃、穿越、倒退、偏离路线、方向错误、引导错误等。这些问题解决不了，室内精细导航就无从谈起。在室内定位技术尚不成熟的情况下，只能利用算法对其进行优化、修正，以期达到更好的定位效果。

2室内定位约束与优化

室外车载导航系统可以采用多种车辆定位方式，例如GPS、INS(InertialNavigationSystem)、DR(DeadReckoning)，且车载导航系统能从车辆中获取各种状态参数，例如速度、行进角度、转数等等，融合道路数据可以对定位点做到非常精准位置估计。而室内由于环境限定，能融合的数据比较少，且室内空间开放，没有显性的道路要素，要素排列紧密，因此，室内道路约束难度要远远大于室外。

2.1数据准备

室内定位约束同样需要各种数据的支持，在室内环境中，为了获得更强的普适性，可以利用的数据大致有3类:①终端传感器数据。包括终端的电子罗盘、加速度计等。②与定位匹配的矢量地图数据。包括地图要素、道路拓扑数据等。③用户行为数据。包括用户行进的历史轨迹、行为习惯等。

2.1.1传感器数据

目前，绝大部分的智能移动终端都配备各种传感器，主要有重力传感器、距离传感器、电子罗盘、光线传感器、三轴陀螺仪、红外传感器、计步器传感器，部分设备还配备气压传感器、磁场传感器等。这些传感器数据对定位约束提供极大的帮助,如表2所示。

表2　主要传感器提供数据及其作用

因此，尽可能多的收集并利用移动终端传感器数据，对于室内定位的约束优化将起到至关重要的作用。

2.1.2地图数据

定位离开地图的配合将会变得难以理解。定位通过地图进行表达，因此，地图数据给定位提供最基本的数学基础和载体。同时定位提供给用户最基本的方位指示，可以说定位与地图相辅相成。因此，地图数据能够提供给定位很多辅助，是定位约束优化最为基本也是最为重要的手段。

室内地图数据大致包括要素信息以及拓扑信息。由于室内是开放空间，没有显性的道路要素，道路要素通常也不明确表达。所有室内道路拓扑均为在生产室内地图时生成。在导航时，调用道路拓扑数据进行路径规划，从而显示出模拟的路线。在室外导航系统中，定位约束可以简单地将定位点约束到规划路线上即可，但在室内这么处理会导致很多问题，如图1所示。

图1　室内道路约束常见问题

因此，要解决这些问题光靠道路拓扑数据远远不够，需要专门制作用于定位约束的数据，且不同的约束文件，产生的效果也不同。

2.1.3用户行为数据

用户行为数据主要包括用户的历史轨迹、行走习惯、用户行为习惯等。这些数据需要经过长时间的搜集并处理之后才能运用。可以用来预测用户下一步的行为，对定位点进行一定预判，达到优化的目的。

2.2算法设计

通过分析定位点精度不稳定产生的问题，归纳起来大概有以下两类：一是定位点漂移；二是导航错误问题。定位点漂移问题解决重点在于将定位点约束到一定范围内，使其在可接受范围内移动。导航错误问题主要表现为倒退、偏离航线、错误方向等。在室外，解决这类问题主要手段是道路匹配和导航推测(DeadReckoning，DR)。在室内，通过融合智能终端传感器的信息，也可以使用类似方法。因此，整个算法流程如图2所示。

图2　定位约束算法流程

1)获取一个定位点，根据地图的数学基础进行坐标变换，形成一个初始定位点。

2)利用前期处理出来的约束数据对定位点进行约束修正，保证定位点位于有效区域内，为后续道路匹配和DR提供一个较好的结果。

3)对定位点进行路网匹配，使定位点尽可能沿着既定路线移动。

4)利用传感器数据以及用户行为数据对航迹进行预测，从而进一步优化定位点。

5)将定位点输出至地图，并将用户的本次定位进行记录，将作为下一次导航推测的依据。

2.3算法实现

2.3.1定位约束文件生成

定位约束文件主要用来对原始定位点进行初步的筛选和优化，对后续定位预测起到至关重要的作用。本文提出两种比较有效的生成方案。

方案1：栅格法

栅格法的中心思想是将地图按一定比例栅格化，并按可通行区域和不可通行区域进行二值化(黑色为不可通行区，白色为可通行区域)，具体步骤如下：

1)读取室内地图，并按照一个像素0.5m的比例尺生成黑色栅格图像。

2)遍历地图要素，若为可通达区域，则在图像上绘制成白色。

3)遍历所有路网，并对其做缓冲区，并对缓冲区填充成白色。

4)对生成的二值图像做优化处理，例如膨胀、腐蚀，去除一些微小的孤岛和干扰面。如图3所示。

图3　栅格定位约束文件生成示意图

使用栅格法制作定位约束数据有很多优点：制作简便，数据量小，计算效率高，容易理解，修改方便等；但也有不可避免的缺点，例如可通行区域根据路网生成，限定太死，定位点很容易卡死；栅格数据只能用于判定定位点是否位于有效区内，用于空间分析效率低，因此不适合用于复杂度更高的运算；而矢量方案则可以弥补这些不足。

方案2：矢量法

矢量法区别于栅格法之处在于用几何形状来描述有效区域。生成有效区时，可以假定室内区域所有区域均可以到达，然后将不可到达区域(例如天井、墙壁等)扣除后就是最终的定位约束区域。

矢量法生成的定位约束文件为矢量数据，可以将其认为是实体要素，可以跟任何其他要素进行空间关系判断和进行空间分析；另外可以看出，矢量定位约束文件能最大程度的描述出可通行区域，从而可以更精准地对定位进行约束。但矢量定位数据量比较大，且随着要素复杂度变高数据量也随着变大。不过，矢量数据理解起来不如栅格数据直观，修改也比栅格数据要麻烦，如图4所示。

图4　矢量定位约束文件示意图

由于两种方案都有不可避免的缺点，本文采取的策略为当室内地图较为简单时直接调用栅格方案；当室内地图要素多，且复杂度高时，将先利用栅格方案快速纠正，若纠正不理想，则调用矢量方案进行进一步校正，从而达到最好的效果。通过实际验证，在大部分情况下栅格方案在效率上表现得更为优秀；而矢量方案则效果更好。通过结合两者，可以在很大程度上改善定位效果。

2.3.2道路匹配算法

在矢量地图表达模型中，道路要素是由弧段和节点抽象的。弧段不能有分支，只有起始节点和终止节点。节点用来表达弧段的关联关系和几何位置。道路通常由若干条弧段组合而成，如图5所示。

图5中1～9为节点，[1,2,3,4]、[4,5,6,7]、[4,9,8]构成3条弧段。假设用户从节点8走向节点9，其中G点为定位点坐标，P点为用户实际位置，那么Ek表示定位点到用户实际位置的误差，该误差为定位误差与定位点坐标转换误差的综合。

图5　道路抽象示意图弧段[8,9]的方程表示为

(1)

建立用户运动的卡尔曼滤波离散化状态方程式(2)和观测方程式(3)。

(2)

(3)

卡尔曼滤波器的状态变量为U=(Xk,Yk,vx,vy,ax,ay,ex,ey)，其中Xk，Yk为x方向和y方向的位置分量；vx，vy为x方向和y方向的速度分量;ax，ay为x方向和y方向的加速度分量；ex,ey为综合误差在x方向和y方向的分量；wk为高斯白噪声；方差为Q。其中：

式中：T为卡尔曼滤波器状态估计的更新时间，τ为相关时间系数。

将原始定位点坐标G与速度信息vx和vy作为外部观测量，系统的观测方程的观测变量为A=(Xk,Yk,vx,vy)，w(k)为高斯白噪声，方差为R。观测方程的观测矩阵为

当用户在某条道路上行进时，轨迹点实际位置P应满足式(1)，即道路对用户行进状态起到了约束作用，成为系统模型的约束条件。道路方程式(1)、系统状态方程式(2)和观测方程式(3)构成了道路约束条件的系统模型，根据广义最小二乘法原理可以推导出带约束条件的卡尔曼滤波算法，得到公式如下：

(4)

通过该算法，不断地将定位点往道路上进行纠正，从而达到抑制定位点漂移的作用，但由于室内道路是人为界定，因此，纠正过后也许并不是最佳选择。另外道路约束不能解决导航时停顿、倒退等状态问题，这就需要依靠导航推测算法来解决。

2.3.3DR算法

航位推测最早应用于航海的航行定位中，是一种利用物体现在位置及速度推测未来位置和方向的航海技术。由于需要使用加速度计、磁罗盘、陀螺仪，成本高，尺寸大，因此，并没有在其他交通领域广泛推广。近年来，随着微电子技术的发展，这些设备的重量、体积、成本都极大降低，使航位推测法可以在车载、智能终端中得以应用。本文也将利用DR技术来对定位点进行预测与推算，从而使定位点更加平滑与真实。

假设行人运动均在二维平面上，在短时间内可以认为行人在做直线运动，获取起始点位置信息，就可以通过算法预测下一刻精确的位置信息及其坐标轴上的偏移量，如下式：

或者

式中：O(x,y)为目标点；R(x,y)为起始点；v为速度；a为加速度；Δt为时间差。

整个推测过程需要确定两个关键因素：行进位移S和行进方向角θ。

1)获取行进距离。行进的位可以通过经典计步器原理计算获取。人们在行进过程中，会在垂直和水平方向产生加速度，并产生周期性变化，利用这个原理可以用于计算行走步数，如图6所示。

图6　人们迈步加速度变化示意图

若智能移动终端配备计步器传感器，则可直接获取数据。

2)获取行进方向角。智能移动终端一般配备电子罗盘，通过该传感器即可得到绝对航向角(0°～360°)。方法简单易用，但电子罗盘极易受到干扰，导致角度精度不稳定。若对角度精度要求较高可以利用捷联航向角来替代绝对航向角度。捷联航向角计算方法为：获取智能移动终端三轴陀螺仪数据，对其进行积分运算并结合初始航向角进行一定角度转化而得。捷联航向角获取不受外界干扰，当电子罗盘角度不稳定时，可以用于辅助计算前进方向信息。

通过航行推测，可以在很大程度上优化定位效果，防止绝大部分导航问题的出现。

3现场实验

本文用于测试的手机为GoogleNexus5，配备了重力传感器、电子罗盘、三轴陀螺仪以及计步器传感器。详细测试如图7所示。

图7　实地测试结果

图7中，虚线表示的是实际的路网信息；虚线表示实际定位点形成的轨迹；粗实线是经过定位约束优化后形成的轨迹。本次测试总共采集了312个定位点，定位点间隔约1s，行走距离约120m，按正常速度(约5km/h)，计步器计算步数约252步，定位精度平均3.5m，方向误差±2.5°。可以看出，经过约束和优化后，定位效果得到明显改善；圆圈所在之处出现倒退的现象由于采用了航位推测，也被正确纠正。

4结束语

本文针对室内定位的特点设计了适合室内定位约束优化算法，对于改善和提高定位效果起到了重要作用，能为室内精细导航提供有效辅助。

参考文献：

[1]汪苑，林锦国.几种常用室内定位技术的探讨[J].中国仪器仪表,2011(2):54-57.

[2]宋敏，申闫春.室内定位航位推算法的研究与实现[J].计算机工程,2013,39(7):293-297.

[3]HIGHTOWERJ，BORRIELLOG.LocationSystemsforUbiquitousComputing[J].JournalofComputer，2001，34(8).

[4]刘艳,鲍远律,左峻疆.基于GIS的导航系统地图匹配算法[J].微型机与应用,2005(6):52-53.

[5]COLLIERWC.In-vehicleRouteGuidanceSystemsUsingMapMatchedDeadReckoning[C].ProceedingsofIEEEPosition，LocationandNavigationSymposium，1990.

[6]毕军,付梦印，张宇河.基于D-S证据推理的车辆导航系统地图匹配算法[J].北京理工大学学报,2002,22(3):393-395.

[7]伍小洁,房建成.一种带速度观测量的GPS动态定位自适应卡尔曼滤波算法[J].中国惯性技术学报,2000,8(3)：27-32.

[8]杨广龙,孔勇平,钟致民，等.基于多模指纹匹配的室内定位系统设计与实现[J].计算机工程与设计，2013，34(5)：1896-1901.

[9]马海兵，黄智伟，黄乐乐，等.基于ArcGIS的室内地图服务系统的设计与实现[J].测绘与空间地理信息，2015，38(3)：92-94.

[10] 孙伟，丁伟，徐爱功，等.基于微惯性技术的室内定位理论及应用[J].测绘与空间地理信息，2015，38(9)：84-88.

[11]CHENX,SCHONFELDD,KHOKHARA.Localizationandtrajectoryestimationofmobileobjectswithasinglesensor.2007.

[12]DIFC，FICCOM，RUSSOS.Indoorandoutdoorlocationbasedservicesforportablewirelessdevices[C].Proc25thIEEEInternationalConferenceonDistributedComputingSystemsWorkshops,2005.

[13] 杨华,刘军发,陈益强.一种基于多终端动态协同的室内定位方法[J].计算机应用研究,2012，29(7):2457-2461.

[14] 杨凯，郭英，毕京学.基于安卓平台的室内实时定位[J].测绘科学，2015，40(6)：125-128.

[15] 沈田.无线室内定位系统研究[J].中国新通信,2009(17):34-35.

[16] 邹坤,修春娣,杨东凯.基于感知概率的室内定位算法[J].全球定位系统,2013，38(6):7-11.

[17] 朱志慧.基于多元回归方法对室内定位适应性的研究[J].电脑与电信,2011(4):61-62.

[责任编辑：刘文霞]

DOI:10.19349/j.cnki.issn1006-7949.2016.10.003

收稿日期：2015-06-06；修回日期：2015-09-30

基金项目：国家自然科学基金资助项目(41471336)

作者简介：林巍凌(1979-)，男，讲师，博士研究生.

中图分类号：P228;TP391

文献标识码：A

文章编号：1006-7949(2016)10-0010-07

Indoor positioning constraints and optimization algorithm based on GIS

LIN Weiling1,2

(1.InformationEngineeringUniversity，Zhengzhou450000，China;2.NavalArmsCommandAcademy，Guangzhou510430，China)

Abstract：With the continuous development of indoor positioning technology，indoor navigation becomes possible gradually.But due to the low accuracy and poor stability of indoor positioning，the drift of positioning points，guiding the navigation error，and less user-friendly effect，cannot meet the fine interior navigation requirements.This paper,combined with GIS spatial analysis and reckoning algorithm，designs a suitable indoor positioning constraints and optimization algorithm based on the characteristics of the indoor space，which can greatly improve the positioning performance.Throught the experiments，the effect proves good.

Key words：indoor positioning;positioning constraints;indoor map;DR;dead reckoning