基于PDR和地理网格的室内外一体化定位方法

原 璟，程 承 旗，童 晓 冲，陈 东

(1.北京大学遥感与地理信息系统研究所，北京 100871；2.北京大学工学院，北京 100871；3.信息工程大学地理空间信息学院，河南 郑州 450001;4.国家信息中心，北京 100045)

基于PDR和地理网格的室内外一体化定位方法

原 璟1，程 承 旗2*，童 晓 冲3，陈 东4

(1.北京大学遥感与地理信息系统研究所，北京 100871；2.北京大学工学院，北京 100871；3.信息工程大学地理空间信息学院，河南 郑州 450001;4.国家信息中心，北京 100045)

为降低现有定位方法对基础设施和电子地图的依赖程度，该文结合环境中的二维码信息与智能手机传感器采集的数据，提出了一种基于行人航迹推算(PDR)技术和地理网格的室内外一体化定位方法。该方法由网格编码提供室内外一体的位置信息，消除PDR定位过程中的累积误差，并通过便捷的编码运算实现位置的高效求解，最终以网格单元展示行人位置与行走轨迹。按照全球规则划分、多层级嵌套及编码可计算的地理网格选取原则，以GeoSOT为例开展实验，定位误差始终控制在行走距离的5%以内，证明了算法的可行性与有效性。该方法可用于通讯链路受阻或地图难以获得等特殊场景的辅助定位，对于室内外一体化定位技术的发展具有实用价值。

室内外定位；行人航迹推算(PDR)；地理网格；GeoSOT；智能手机

0 引言

随着信息技术的发展，人们对地理空间4A(Anytime，Anywhere，Anybody，Anything)服务的需求不断增长[1]，基于位置的服务(Location Based Services，LBS)逐渐成为人们日常生活的重要组成部分。定位技术作为LBS的基础研究内容之一，受到学术界和导航工业界的广泛关注。目前，卫星定位技术在室外的应用已经十分成熟，但在室内或一些特殊场景中，信号衰减、多径干扰等原因造成卫星定位精度下降[2]，故常采用基于WiFi、蓝牙、红外线、超宽带、ZigBee等技术的定位方式。与此同时，功能强大、灵活便携的智能手机的普及使得LBS与定位技术更为大众化。然而，现有定位系统大多面临以下问题：1)定位过程依赖空间星座、基站等外部基础设施，系统建设的工作量大、成本高；2)当电子地图或室内平面结构图难以获得时，位置信息与地图的关联失败，定位功能的应用受限。

行人航迹推算(Pedestrian Dead Reckoning，PDR)[3,4]是一种基于自包含传感器的相对定位技术，其优势在于定位的自主性与连续性，即仅依靠加速度计、陀螺仪、磁感应器等传感器感知行人运动状况与周围环境条件，就能够实现位置的递归计算。随着低功率、多种类的传感器在智能手机上的广泛应用，PDR成为理想的辅助定位手段。该技术不需要复杂的基站建设，也不需要对移动设备进行扩展，定位过程无通信开销。但缺点也十分明显：定位初期必须依靠其他定位方式获得初始位置，定位过程中误差随行走距离的增长逐渐累积。

地理网格是一种科学、简明的定位参照系统[5]，网格单元划分规则、无缝无叠、分级明确[6]，网格编码描述地物的位置信息及空间关系[7,8]。目前，国内外应用较为成熟的网格与编码包括美国国家格网(United States National Grid，USNG)[9]、加拿大自然区域编码(Natural Area Code，NAC)[10]、谷歌开放位置码(Open Location Code，OLC)[11]、中国国家地理格网[5]、2n一维整型数组的全球经纬度剖分网格(Geographic coordinate Subdividing grid with One dimension integral coding on 2n-Tree，GeoSOT)[12]等。地理网格既可以作为辅助图层与地图叠加显示，也可以脱离地图而单独存在，提高了紧急救援、灾难管理等场景中的定位效率。因此，PDR技术与地理网格共同应用于智能手机平台，可以解决通讯链路受阻或地图难以获得等特殊场景下的定位问题，具有较强的实用性。本文设计了基于PDR与地理网格的室内外一体化定位方法，分析了地理网格选取原则，并以GeoSOT为例论述了PDR与地理网格在位置获取、位置计算和位置展示3个方面的结合方法。

1 PDR算法基础

PDR定位以行人步态的生理学特征为基础，利用加速度计检测步频、估算步长[13]，综合陀螺仪、磁感应器求解航向，在初始位置已知的前提下根据式(1)逐步递推行人位置，定位原理如图1所示。

(1)

式中:(x1，y1)表示上一步位置，(x2，y2)表示当前位置，d为步长，θ为航向角。

图1 PDR算法原理示意[14]

1.1 步频检测

步频检测的主要目的在于从连续的传感器数据中识别跨步起点，便于后续步长、方向计算时以单步为单位进行数据处理，本文采用“平滑窗口+峰值探测+动态阈值”的方法检测步频[15,16]，具体步骤如下：

第一步，计算剔除重力加速度后的加速度模值a，为简便起见，直接将线性加速度计的三轴输出模值(alx，aly，alz)带入式(2)计算:

(2)

第二步，根据式(3)，使用长度为2N+1的平滑窗口对加速度模值a滤波。

(3)

第三步，峰值探测用于消除身体抖动造成的计步误差，包括：1)波峰大于阈值apeak；2)波谷小于阈值avalley；3)波峰与波谷的差大于阈值adiff；4)相邻波峰之间的时间差大于阈值T。

第四步，以当前单步波峰和上一单步波谷的平均值作为动态阈值，加速度波形向上经过该值的时刻即为上一步的结束点和当前跨步的开始。

1.2 步长估算

步长估算可以使用常数/伪常数、线性、非线性、人工智能、单摆等[15]模型法，也可以利用身高或肌电信号等求解。综合考虑算法复杂度、精度、可操作性等诸多因素，本文选择式(4)所示的非线性模型[17]，训练求得模型参数后估算步长。

(4)

式中:amax、amin分别为步频检测得到单步加速度模值的最大值和最小值，k1、k2为模型参数。

1.3 方向检测

方向检测由加速度计、陀螺仪和磁感应器综合实现。首先根据加速度计和校准后的磁感应器计算载体坐标系与导航坐标系之间的旋转矩阵，进而求得初始航向角，并以磁偏角修正。单步的航向以该步内所有采样点航向角的平均值表示，其中每一个采样点所对应的航向角以式(5)定义，即：当前时刻陀螺仪z轴输出值ωiz小于等于阈值ωTh时，采用上一时刻的航向角θi-1；反之，由上一时刻航向角θi-1加陀螺仪积分得到的航向改变量Δθ求得。

(5)

2 地理网格选取原则

地理网格与PDR通过优势互补，实现了对基础设施和电子地图依赖性小的室内外一体化定位。两者的结合主要表现在：1)位置获取：地理网格编码为PDR初始位置输入和累积误差清零提供所在位置的绝对坐标；2)位置计算：在PDR算法基础上，通过地理网格编码运算实现行人位置的高效求解；3)位置展示：跨步结束时，以地理网格单元展示行人所在位置。

按照上述结合策略，定位参照系统地理网格的选取原则如下：1)全球规则划分。规则划分是地理网格提供位置信息的基本前提，全球统一保证了室内外或不同地域之间具有相同的位置表示方式。位置获取方面，全球地理网格扩展了PDR因累积误差而受限的定位范围；位置计算方面，则有助于避免PDR在不同坐标系或量测单位下使用时复杂的转换操作。2)多层级嵌套。地理网格体系提供了丰富的网格尺度，同层级网格之间无缝无叠、覆盖全球，相邻层级之间严格嵌套、转换便捷。位置计算方面，小尺度网格对定位区域的精细表达保证了PDR算法的定位精度；位置展示方面，多尺度网格允许在最佳展示尺度基础上以不同精度显示行人位置。3)编码可计算。地理网格编码的计算能力是改进传统PDR算法的重要保证，位移运算等形式的编码运算实现了编码与空间区域、编码与编码间的快速转换。其中，编码位移运算以地理网格间的方位关系与距离关系为基础，有助于简化位置计算过程，提高位置计算效率。

3 基于PDR和GeoSOT的室内外一体化定位方法

GeoSOT是按照四叉树递归剖分的方式将全球划分为具有明确区域位置和尺度特征的32级等经纬度网格体系，满足PDR算法对地理网格选取所提的全部要求[18]。考虑到GeoSOT厘米级最细表达精度及其较强的编码计算能力，本文以GeoSOT为例，详述PDR与地理网格在位置获取、位置计算与位置展示方面的结合方法。

3.1 位置获取

位置获取主要是为定位算法提供代表行人位置的地理网格编码，实现途径多样。本文选择存储空间大、识别速度快的二维码作为位置信息存储与传播的媒介，向其中存入四进制一维的GeoSOT编码。行人通过智能手机扫描二维码，获得定位开始所需的初始位置网格编码或累积误差清零所需的中间位置网格编码。这种位置获取方式类似于在二维码中存入停车位编号的地下停车场定位，目前已有部分应用实例，可行性较强，通过事先设置典型地物的位置二维码即可完成定位区域初期建设，不仅能够实现方便快捷、成本低廉的室内外一体化定位，还解决了通讯链路受阻等特殊场景下的定位问题。

3.2 位置计算

GeoSOT在全球范围内具有统一的定位基础，是室内外空间数据一体化组织的有效途径，在实现步频检测、步长估算、方向检测的基础上，引入编码位移操作改进按照式(1)计算位置的传统PDR算法。编码位移计算以二进制二维的GeoSOT网格编码为输入，在东北半球，代表经度的整型编码加1表示向右平移1个网格，减法表示向左平移；代表纬度的整型编码加1表示向上平移一个网格，减法表示向下平移。因此，图2中两个灰色网格所在位置之间的移动，通过左下角网格经度方向编码加5、纬度方向编码加3即可实现。

图2 网格编码位移计算原理示意

在网格编码位移操作的基础上，PDR位置计算流程如图3所示。具体计算步骤如下：

第一步，获得k位置的网格编码Ck，若Ck是由扫描二维码得到的四进制一维编码，则进行编码转换得到二进制二维编码；若Ck是位置计算得到的二进制二维编码，则跳过转换，直接进行下一步。

第二步，通过边长计算函数求k位置第32级GeoSOT网格的边长l。

第三步，根据式(6)计算步长所对应纬度方向、经度方向平移的网格个数。

(6)

式中:Nlat、Nlon分别为纬度方向和经度方向上平移的网格数，d代表步长，θ代表航向角，l代表网格边长。

第四步，对k位置的网格编码Ck进行编码位移操作，求得k+1位置的网格编码C。

第五步，若k+1位置存在二维码，则扫码获取的CQR作为定位结果，同时清零PDR技术的累积误差；若k+1位置不存在二维码，则以计算结果C作为k+1位置的网格编码。

将k+1位置网格编码作为输入可递推得到下一位置网格编码。另外，受定位范围限制，通常网格边长变化不大，位置递推过程中可省略网格边长计算，以最近一次扫码后计算所得网格边长代替即可。

图3 位置计算流程

3.3 位置展示

位置展示是以地理网格单元覆盖的空间区域形象化表达行人所在位置。理论上，当网格层级不高于位置获取与位置计算所用层级时，任意满足定位范围与定位精度需求的层级均可设为位置展示网格层级，其中，最佳层级是边长不大于行人步长的最大尺度网格所在层级，该层级网格对于PDR算法误差具有较好的容错性，兼顾了行人跨步的区分度以及行走轨迹的连续性。

行人步长约0.5～0.8 m[15]，根据文献[19]，赤道地区第27级GeoSOT网格边长约0.5 m，是边长不大于行人步长的最大尺度网格。通常情况下，第27级GeoSOT网格可以保证相邻跨步结束时，行人处于不同且邻近的GeoSOT网格中，因此将其设为行人位置与行走轨迹展示的最佳网格。

4 实验与分析

为验证基于PDR和地理网格的室内外一体化定位方法的可行性与有效性，本文选用GeoSOT网格及其编码，设计如下实验。1)实验平台：智能手机vivo X3t，Android4.2.1操作系统，包含加速度传感器、线性加速度传感器、磁感应器、陀螺仪、摄像头等，定位系统初始界面如图4所示。2)实验场地：北京华宇时尚购物中心F1层，室内结构及参考行走路线如图5所示。参考路线分为两段，第一段从室外开始向南行走，后转弯，经商场大门由室外进入室内，再次转弯后继续向南行走至位置改正点；第二段是商场内一个矩形通道。3)实验方法：开始前准备好GeoSOT位置二维码，测试者匀速行走，凭经验保持手机水平，避免过度倾斜，整个定位过程全部离线进行。测试者首先在初始位置扫描GeoSOT位置二维码，持手机原地旋转360°校准磁感应器读数，然后启动定位功能，随测试者逐步向前行走，手机可实时计算当前位置，并在系统中更新显示。到达改正点后，暂停传感器数据获取，扫描二维码并清除累积误差，然后重新启动数据获取及定位功能。

图4 定位系统主界面

图5 测试场地室内结构及参考行走路线

结果表明：使用和行人步长相近的第27级GeoSOT网格(测试地区网格的经向边长约0.48 m，纬向边长约0.37 m)展示行人位置，并将其与参考路线叠加显示，两者基本一致(图6)。测试前程的理论航向约为180°→90°→180°，但陀螺仪漂移和累积误差的存在导致第二阶段航向角不断减小，直接影响到第三阶段航向。测试后程的理论航向约为90°→180°→270°→360°(0°)，第三阶段的累积误差影响到第四阶段航向。这一现象在图6中十分明显，测试前程的第二次拐弯、测试后程的第三次拐弯角度改变量均近似90°，却因累积误差导致了航向偏离，由此可见扫描二维码并清零累积误差的必要性。

图6 位置计算结果与参考路线对比

表1显示了定位测试中其余指标的情况，两组测试的定位误差始终保持在行走距离的5%以内，其中测试后程的行走距离达到百米级别，总计步长度与参考距离的误差约1.5 m，终点距其理论位置约3.4 m。另外，为减小身体抖动引入的误差，测试者慢速前行，因此步频较低，步长偏小。

表1 定位测试结果

综上，基于PDR和GeoSOT的室内外一体化定位方法较为准确地反映了行人的位置信息，在采用PDR基础算法计算步长和航向的情况下，行走距离误差、终点及其理论位置误差均小于5%，定位精度达到目前大多数系统的水平。另外，定位全程无通信开销，不依赖于电子地图。该实验对PDR与其余地理网格结合的室内外一体化定位方法具有一定的参考价值，一定程度上证明了PDR与地理网格联合定位的可行性与有效性。

5 结语

智能手机功能的日益完善，使得发展一种对外部基础设施和电子地图依赖性小的定位方法成为可能。本文将定位技术与地理网格结合，提出了一种基于PDR和地理网格的室内外一体化定位方法。该方法以地理网格为定位参照系统，按照PDR的算法原理，在获得网格编码提供的位置信息的基础上，借助智能手机传感器依次完成步频检测、步长估算和方向检测，通过编码的位移运算实现位置的高效求解，并以网格单元可视化表达行人所在位置。在PDR和GeoSOT结合的定位实验中，总体定位误差能够控制在行走距离的5%以内，且定位精度通过增加环境中二维码数量等方式可以进一步提高，为特殊场景下的定位问题提供了解决思路。目前研究仅局限于二维环境下地理网格与PDR技术的结合，下一步可将三维立体网格引入，如GeoSOT-3D[19]，发展适用性更强的三维室内外一体化定位算法。

[1] 欧阳斌.基于嵌入式传感器的室内定位技术的研究[D].天津：天津大学，2013.

[2] 任慧君.半自动的室内定位与导航[D].上海：华东师范大学，2015.

[3] JUDD T.A personal dead reckoning module[A].Proceedings of ION GPS-97[C].1997.47-51.

[4] LEVI R，JUDD T.Dead reckoning navigational system using accelerometer to measure foot impacts:U.S.Patent,US5583776[P].1996-12-10.

[5] 国家测绘局.GB/T 12409-2009 地理格网[S].北京：中国标准出版社，2009.

[6] 白凤文，许华燕.国家地理格网在数字城市建设中的应用[J].测绘通报，2012(4)：92-94.

[7] 陈会仙，张小霞，刘绪友，等.国家地理格网编码与二维条码的集成应用之探讨[J].测绘科学，2013，38(4)：152-154.

[8] 兀伟，李朋德，张坤，等.基于位置服务的地理格网编码设计[J].测绘通报，2013(2)：41-44.

[9] FGDC.FGDC-STD-011-2001 United States National Grid[S].Reston,Virginia,2001.

[10] 冯淳.地理格网参考系统的建立与应用[D].西安：长安大学，2006.

[11] Open Location Code:An open source standard for addresses,independent of building numbers and street names[EB/OL].https://github.com/google/open-location-code/blob/master/docs/olc_definition.adoc，2015.

[12] 程承旗，郑承迅.一种统一现有经纬度剖分网格的方法：中国，CN102609525A[P].2012-07-25.

[13] 田国会，张庆宾，丁娜娜.基于WT-UKF的PDR/GPS组合定位算法[J].控制与决策，2015，30(1)：86-90.

[14] 陈国良，张言哲，汪云甲，等.WiFi-PDR室内组合定位的无迹卡尔曼滤波算法[J].测绘学报，2015，44(12)：1314-1321.

[15] 陈伟.基于GPS和自包含传感器的行人室内外无缝定位算法研究[D].合肥：中国科学技术大学，2010.

[16] 张世哲.基于惯性传感器和WiFi的室内定位系统的设计与实现[D].北京：北京邮电大学，2012.

[17] 徐伟.基于Android手机的室内定位技术研究与实现[D].武汉：华中师范大学，2014.

[18] 吕雪锋，廖永丰，程承旗，等.基于GeoSOT区位标识的多源遥感数据组织研究[J].北京大学学报(自然科学版)，2014，50(2)：331-340.

[19] 郭辉.地球空间立体剖分格网研究[D].北京：北京大学，2012.

Integration of Indoor and Outdoor Positioning Method Based on PDR and Geographic Grid

YUAN Jing1，CHENG Cheng-qi2，TONG Xiao-chong3，CHEN Dong4

(1.InstituteofRemoteSensingandGeographicInformationSystem,PekingUniversity,Beijing100871；2.CollegeofEngineering,PekingUniversity,Beijing100871；3.InstituteofSurveyingandMapping,InformationEngineeringUniversity,Zhengzhou450001；4.StateInformationCenter,Beijing100045,China)

In order to reduce current positioning methods′ dependence on infrastructures and electronic maps,this paper proposes a novel indoor-outdoor integrated positioning method whose implementation uses QR codes and smartphone sensor data.This method is based on Pedestrian Dead Reckoning(PDR) technology and geographic grid,meaning that its design refers to PDR algorithm and its positioning reference chooses geographic grid.PDR and geographic grid have complementary advantages on position acquisition,calculation and presentation.To be specific,firstly the method obtains indoor-outdoor integrated positions in the format of geographic grid codes and eliminates accumulated errors of PDR.Secondly,based on the estimations of step counts,step sizes and step directions,positions can be figured out efficiently through simple code calculation.Finally,positions and routes of the pedestrian are showed by grid cells.According to geographic grid selection principles which consist of global subdivision,multi-level nesting and computable codes,GeoSOT is selected and used in experiments.Experiments show that positioning errors are controlled within 5% of walking distance all the time.The feasibility and effectiveness of the algorithm are demonstrated to a certain extent.Hence,this method can be used as an assisted positioning approach in some special situations where positioning devices fail to get signals or maps are hard to obtain.Additionally,the method has high practical value for the development of indoor-outdoor integrated positioning technology.

indoor-outdoor positioning；Pedestrian Dead Reckoning(PDR)；geographic grid； GeoSOT；smartphone

2016-04-06；

2016-06-15

测绘地理信息公益性行业科研专项“地名地址地理位置模型及可视化表达关键技术”(201512020)

原璟(1991-)，女，硕士研究生，主要研究方向为空间信息科学。*通讯作者E-mail：ccq@pku.edu.cn

10.3969/j.issn.1672-0504.2016.06.006

P208

A

1672-0504(2016)06-0032-05