基于实时步长匹配的行人室内定位方法①

钟立扬, 崔超远, 王儒敬, 孙丙宇(中国科学院 合肥智能机械研究所, 合肥 3003)(中国科学院大学, 北京 00049)

基于实时步长匹配的行人室内定位方法①

钟立扬1,2, 崔超远1, 王儒敬1, 孙丙宇11(中国科学院 合肥智能机械研究所, 合肥 230031)2(中国科学院大学, 北京 100049)

针对室内定位研究中行人航位推算(PDR)算法的传统步长模型无法充分反映个体差异性的问题, 提出一种以卫星测距为基础, 建立个体步长特征数据库代替步长模型的方法. 在室外将卫星测距应用到步长测算中, 建立不同速度特征与步长的对应关系. 在室内, 改进了K-最近邻(KNN)算法, 对跨步进行实时步长匹配, 结合方向信息计算出行人的当前位置. 实验结果表明, 室内定位最大误差距离可以控制在4%以内, 平均绝对误差距离可以控制在2%以内, 定位精度较传统步长模型有较大提高.

室内定位; 行人航位推算; 卫星测距; K-最近邻; 实时步长匹配

1 引言

随着经济社会的发展和智能手机的高度普及, 基于位置的服务(LBS, location based service)已经越来越得到重视, 尤其在大型复杂的室内环境中, 如火车站、机场、大型超市、医院等区域, 人们对位置服务有迫切需求. 目前行人的室外定位主要通过卫星和无线通信基站来实现, 但由于建筑物对卫星信号的遮挡及衰减作用, 无法实现行人的室内定位, 而基站的定位精度在几十到几百米, 同样无法满足室内的精确定位.

针对行人室内定位, 目前的解决方案包括有源和无源两种方式. 有源定位需要事先布设信号节点, 主要是测量终端设备信号强度, 通过指纹定位算法进行定位, 如WiFi定位[1,2], 蓝牙定位[3], ZigBee定位[4]等.无源定位不需布设信号节点, 一种是将惯性导航机制引入移动设备[5], 另一种是行人航位推算(PDR, pedestrian dead reckoning)算法[6-8].

PDR算法根据惯性传感器数据对行人行走步数、步长和方向进行计算, 获取行走距离和方向. 算法的关键在于准确地估算行人的步长, 文献[6]建立了一个基于步频和步长之间线性关系的步长估计模型; 文献[7]使用一个与跨步周期内最大最小加速度有关的非线性经验模型; 文献[8]将人行走模式近似为一个倒立的单摆, 通过三角关系计算步长. 由于不同人步长的差异与个人身高、习惯、心情等均有一定关系, 上述线性和非线性模型很难反应出不同个体的步长差异.

智能手机内置加速度计, 磁航向计等MEMS传感器, 为室内行人航位推算提供了方便,通过采集加速度数据, 利用峰值法检测跨步[9-11]. 为了充分考虑个体步长的差异, 提出一种以卫星测距为基础, 建立个体步长特征数据库代替步长模型的方法. 在室外将卫星测距引入步长测算中, 建立不同速度特征与步长的对应关系, 进入室内后采用改进的K-最近邻(KNN, knearest-neighbor)算法对步长进行实时匹配, 结合磁航向计确定行走方向, 完成行人行走距离和方向的推算.

2 行人室内定位原理

2.1 PDR算法基本原理

通常情况下, 认为行人在很短的采样时间内做直线运动, 当已知某一时刻的位置、航向和行人位移量就可以推断出下一时刻的位置信息. 图1演示了PDR算法的基本原理, 通过递推公式(1)可以计算出行人k时刻的位置.

图1 PDR算法原理图

Ek和Nk表示行人第k步在东北天坐标系下的东向和北向坐标, Sk表示该步的步长, ak表示该步的航向[12,13].

2.2 跨步检测

推算行人位置的前提是准确检测行人的每一次跨步. 在一个完整的行走周期中, 人首先处于静止状态;开始迈步时身体向上向前运动, 加速度出现波峰状态;当人在垂直和水平方向的速度达到最大后加速度出现波谷状态, 开始减速, 当迈出的脚和地面接触稳定后整个周期结束.

手机所处的设备坐标系中, X轴沿屏幕向右, Y轴沿屏幕向上, Z轴则垂直于屏幕向外[14]. 当手机屏幕向上水平握持行走时, 设备坐标系的Z轴与东北天坐标系中的天向轴大致重合, 通过检测Z轴加速度峰值即可实现对行人跨步的检测.

由于手机内置MEMS传感器的精度相比专业设备较低, 以及行人行走状态的不确定性造成加速度信号出现较多的毛刺, 需要对原始数据做相应的平滑滤波处理. 平滑滤波算法选用简单移动平均法(SMA, simple moving average), 滑动窗口大小设为L, SMA算法将包括当前测量值Ak在内的前L个测量值平均值作为当前时刻的平滑输出结果.

当测量得到新的加速度Ak时, 即把新数据加入滑动窗口, 同时删除最旧的一个加速度Ak-L, 依次递推. L的值根据实验效果选取为20, 图2为某次行走过程中采样频率为100Hz时手机Z轴加速度原始数据经过平滑滤波后的时间序列, 峰值即为周期内最大加速度Amax, 谷值即为周期内最小加速度Amin.

图2 平滑滤波后Z轴加速度

为了提高检测的准确率, 只有峰值大小超过阈值的才会被判定为有效峰值, 实验中发现阈值设为0.4可以最大程度地过滤无效峰值同时保留有效峰值. 人自然行走的步频在1-3Hz之间[15], 所以在检测峰值的同时还要计算峰值的间隔时间, 屏蔽不在合理时间间隔区间的峰值.

2.3 个体步长特征数据库的建立

不同人步长的差异与个人身高、习惯、心情等均有一定关系, 常规的线性或非线性步长模型在面对不同个体时很难适用. 目前智能手机集成的卫星位置解算芯片, 融合了GPS, 北斗, 格洛纳斯等系统的多源定位信息, 精度可以达到米级. 故本文直接使用手机给出的位置信息, 将卫星测距引入行人的步长测算,进而建立一个属于个体的步长特征数据库. 测量A, B两点所在位置的经纬度, 利用公式(3)即可计算两点位置之间的直线距离S[15].

其中(Lng1,Lat1)表示A点经纬度, (Lng2,Lat2)表示B点的经纬度, a=Lng1-Lng2为两点经度之差, b=Lat1-Lat2为两点纬度之差, 6378137为地球半径, 单位为米.

为了提高测距的准确性, 需要行人以近似直线的方式从A点步行到B点, 并尽量保持一种速度状态, 在卫星测距的同时检测跨步, 记录每步的特征值, 利用式(4)计算该种速度状态的平均步长.

其中S为式(3)计算得到的A, B两点之间的直线距离, N为这一过程检测到的跨步总数.

假设速度有m种状态, 步长特征包括一个跨步周期内的最大加速度Amax、最小加速度Amin、周期时长T.室外卫星测距的过程也就是步长特征数据库建立的过程, 共有m×N组跨步特征值集合, 同时也是m种速度状态下跨步的特征值与步长对应关系的生成过程. 记D=(d1, d2, …, dm)代表m种不同速度状态下的步长集合, C=(Amax, Amin, T)代表一个跨步特征值的集合, 按(C, dj)键值对的形式存储数据, 其中dj∈D.

2.4 步长匹配

进入室内后, 初始位置由卫星定位信息给出. 记C*=(A*max, A*min, T*)为检测到的新的跨步特征值集合, m种速度状态代表m种已有的类, 匹配过程的实质是对C*做出分类的过程.

行人行走的开始和结束阶段步长特征数据并不稳定, 波动较大. 为了减少KNN算法计算量, 匹配过程中对个体步长特征数据库进行简化. 实验表明, 只保留每种速度状态下(N/3,2×N/3)区间即中间段的m×N/3组特征数据完全可以保证匹配的准确率, 记n=m×N/3.匹配算法如下:

①计算C(i)与C*间的欧氏距离dist(C(i),C*),i=1,2…,n;

② 按升序对dist(C(i),C*)排序, 找出排在前k个的最小距离对应的C(i);

③ 根据存储的(C, dj)键值对查找这k组C(i)对应的步长d;

④ D集合中出现次数最多的d值作为当前C*对应的步长;中C与C*的欧氏距离dist(C,C*)为

2.5 方向确定

智能手机内置磁航向计, 根据对地磁场的感应可以实时指示出手机当前顶部与正北方向的夹角, 当手机绕着Z轴旋转时, 该角度值将发生改变, 此方向将作为行人的行走方向.

3 测试与验证

3.1 测试系统工作流程

本次测试以搭载Android5.0系统的小米4C手机为例, 采样频率100Hz. 首先测试人员需要在室外测算不同行走速度下的步长, 然后在进入室内后实时匹配新的跨步步长, 最后结合方向信息计算位置, 整个测试系统的工作流程如图3所示.

图3 测试系统工作流程

3.2 测试结果与误差分析

室外测试地点选在环境开阔的中国科学院合肥智能机械研究所大楼外的人行道上, 手机最少可以连接10颗卫星,

最多可以连接20颗以上的卫星, 保证了卫星测距的准确性. 速度状态选为较慢速度、正常速度和较快速度三种, 测试人员身高178cm, 在三种速度状态下的实际行走步数均控制在100步, 得到的步长计算结果分别为0.60m、0.74m和0.88m.

室内测试地点选在智能所大楼内的走廊, 测试距离50m, 分别计算在较慢速度、正常速度、较快速度以及变速行走这四组形式下的距离, 每组测试5次,得到的20组测试数据分布如图4所示.

图4 20组测试数据

从图中可以看出, 虽然各种速度状态下的计算距离每次均不相同, 但都围绕50m上下浮动. 偏差的原因包括两点, 一是本方法固有的误差, 因为人的任何两步的步长不会绝对相等; 二是步长匹配过程中产生的误差, 即步长的误判. 进一步分析测试数据, 结果如表1所示.

表1 测试数据分析

可以得出, 最大误差距离可以控制在4%以内, 平均绝对误差距离可以控制在2%以内. 不同的行走状态下均能实现较为准确地步长匹配, 尤其对于实际中最容易出现的变速行走状态, 同样具有很好的效果.由于较慢速度下加速度数值波动稍大, 导致计算结果误差范围扩大.

将同样的测试数据分别应用在文献[6]的线性模型:

其中a, b为系数, f为频率. 以及文献[7]中的非线性经验模型:

其中H为系数, Amax, Amin分别为一个跨步周期内的最大最小加速度. 得到的结果与本文的方法比较, 如图5所示.

图5 结果比较

通过比较可以发现, 本文的方法相比文献[6]和文献[7]最大误差距离分别减少48.8%和35.8%, 平均绝对误差距离分别减少54.3%和36.6%. 文献[6]中的线性模型在较慢速度下计算步长偏小, 整体计算距离减小, 误差加大. 文献[7]的方法则在变速行走时误差加大. 相比之下, 本文的方法对于个体差异适应性强,整体数据结果稳定性好, 没有出现较大的偏差.

4 结语

行人室内定位研究具有十分广阔的应用前景, 特别是不依赖外部信息可以自主工作的PDR算法是室内定位研究的一大热点. 本文将PDR算法应用于普通的智能手机, 利用优化的KNN算法实时匹配室外卫星测距得到的行人三种速度下的步长, 实现了室内环境下行人的无源自主定位. 室内最大误差距离可以控制在4%以内, 平均绝对误差可以控制在2%以内, 相比常规的步长模型结果稳定, 定位精度更高. 但本文的方法依赖于室外卫星定位精度, 同时行人的实际步长远远不止三种, 同样会造成计算误差. 后续研究考虑对速度的划分通过聚类方式实现, 同时对匹配结果与步长模型计算结果进行加权组合, 给出更准确可靠的步长估算, 进一步提高行人的室内定位精度.

1肖亚龙,张士庚,王建新.一种基于多维标度和区域细化的无线室内定位方法.计算机学报,2016.(在线出版)

2 周锦,李炜,金亮,陈曦.基于KNN-SVM算法的室内定位系统设计.华中科技大学学报(自然科学版),2015,43(增刊I): 517–520.

3 陈国平,马耀辉,张百珂.基于指纹技术的蓝牙室内定位系统.电子技术应用,2013,39(3):104–107.

4 曹建玲,孙希胜,索建伟,任智.基于梯度信息的ZigBee网络PAN间混合路由算法.华中科技大学学报(自然科学版),2014,42(6):79–84.

5 陈天啸,曾鹏飞,虞致国,王晓涧,顾晓峰.iOS 平台下惯性室内定位系统设计与实现.计算机工程与应用,2014,50(15): 207–210.

6 Li F, Zhao C, Ding G, et al. A reliable and accurate indoor localization method using phone inertial sensors. Proc. of the 2012 ACM Conference on Ubiquitous Computing. ACM. 2012. 421–430.

7 田国会,张庆宾,丁娜娜.基于WT-UKF 的PDR/GPS 组合定位算法.控制与决策,2015,30(1):86–90

8 邸文华,刘昱,黄镇彩.基于iOS平台的步长计算方案与实现.电子测量技术,2012,35(9):32–35

9 周瑞,罗磊,李志强,桑楠.一种基于智能手机传感器的行人室内定位算法.计算机工程,2016,(11):22–26.

10 Roy N, Wang H, Roy Choudhury R. I am a smartphone and I can tell my user’s walking direction. Proc. of the 12th Annual International Conference on Mobile Systems, Applications, and Services. ACM. 2014. 329–342.

11宋敏,申闫春.室内定位航位推测算法的研究与实现.计算机工程,2013,39(7):293–297.

12王克己.室内定位系统中的行人航迹推算研究[硕士学位论文].北京:北京邮电大学,2014.

13陈国良,张言哲,汪云甲,孟晓林.WiFi-PDR室内组合定位的无迹卡尔曼滤波算法.测绘学报,2015,44(12):1314–1321.

14陈春阳,郭英,毕京学.手机陀螺仪与加速度计联合定位初步分析.导航定位学报,2014,2(4):74–77.

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

Method of Pedestrian Indoor Positioning Based on Real-Time Step-Size Matching

ZHONG Li-Yang1,2, CUI Chao-Yuan1,WANG Ru-Jing1, SUN Bing-Yu11(Institute of Intelligent Machine, Chinese Academy of Sciences, Hefei 230031, China)2(University of Chinese Academy of Sciences, Beijing 100049, China)

Focus on the problem of the traditional step-size model used in pedestrian dead reckoning algorithm cannot fully reflect individual differences in the research of indoor positioning. We propose a method to establish database of individual feature of step-size based on satellite ranging and then replace the step-size model. Satellite ranging is applied to calculate the step-size in the outdoor, the corresponding relationship between different speed features and step-size is set up. Then we carry out real-time step-size matching indoors for the step, using improved K-nearest-neighbor(KNN) algorithm and calculate people’s current position combined with direction information. The actual test results show that the maximum error distance can be controlled within 4%, and the mean absolute error distance can be controlled within 2%. The positional accuracy has a larger enhancement compared to the traditional step-size model.

indoor positioning; pedestrian dead reckoning; satelliteranging; K-nearest-neighbor; real-time step-size matching

2016-07-05;收到修改稿时间:2016-08-29

10.15888/j.cnki.csa.005656