一种改进的行人导航算法研究

刘　宇，向高林，王伊冰，陈燕苹，吕　玲，黄河明

(重庆邮电大学 光电信息感测与传输技术重庆市重点实验室，重庆 400065)



一种改进的行人导航算法研究

刘宇，向高林，王伊冰，陈燕苹，吕玲，黄河明

(重庆邮电大学 光电信息感测与传输技术重庆市重点实验室，重庆 400065)

摘要：目前大多行人导航系统的研究都以手持手机、绑在腰间等单一姿态为前提，并未考虑行人使用手机过程中同时存在接电话、放在上衣口袋等多种姿态的情况。分析了行人使用手机的4种常见姿态，基于行人航迹推算(pedestrian dead reckoning, PDR)算法设计了一种改进的行人导航算法。利用神经网络(back propagation，BP)模型对手机姿态进行智能识别，设计了一种新的步态检测算法来对多姿态下的步态进行有效检测，并将行人行走过程分为单一姿态与姿态切换过程，对2个过程的航向进行了修正。软件测试结果表明，多姿态下实现系统定位精度在20‰以内，达标率在85%以上，应用于导航系统能够提供准确、可靠、持续的位置信息。

关键词：行人导航定位；神经网络(BP)；姿态识别；步态检测；航向修正

0引言

十多年以来，为了解决室外定位导航“最后一公里”的问题，科技巨头和研究机构在室内定位技术方面开展了大量的研究。其中，基于多传感器的行人导航系统被广泛应用于室内定位中，该技术主要利用佩戴在行人身上的低精度微机电系统(microelectro mechanical systems, MEMS)加速度传感器、MEMS陀螺仪、磁力计进行行人运动数据采集，结合行人航迹推算 (pedestrian dead reckoning, PDR) 算法求得行人的位置，从而为行人提供精确定位[1-2]。目前智能手机已经深入到人们的日常生活中，智能手机的屏幕自动旋转，智能手机游戏中的重力感应，指南针等神奇的功能都归功于集成在智能手机中的磁力计，陀螺仪和加速度计(magnetic, angular rate and gravity, MARG)传感器，这也为行人导航技术在智能手机平台上的实现提供了必要的硬件条件[3-5]。

目前关于行人导航系统的研究能得到较为稳定的单一姿态下的航向，但是由于行人使用手机方式的多样性，手机位置随时会发生变换，因此，有必要设计一种能检测行人姿态并且允许姿态间自由切换的算法。行人使用手机的姿态有手持、打电话、将手机放在上衣口袋等多种姿态，而目前对多姿态下的行人导航定位研究较少。M.Susi[6]设计了一种基于决策树的姿态识别算法，能准确识别出手臂摆动与非手臂摆动姿态，姿态判别准确率大于90%，并且不同的姿态下的步态检测的准确率大于97%，但是没有将非手臂摆动姿态进一步区分开来，且只是简单地对姿态进行识别，没有考虑多种姿态下的定位功能。ZHANG Hemin[7]设计了一种基于支持向量机的姿态识别算法，该算法能识别手持、电话、上衣口袋以及包里4种姿态，识别准确率大于94%，并且实现了4种单一姿态下的行人导航，但是并未考虑不同姿态间切换的情况。

为了满足行人使用手机过程中的定位需求，本文设计了一种定位精度较高且易于实现的行人导航算法。

1系统框架

行人导航系统由数据采集模块、数据处理模块、姿态判别模块、航迹推算模块4个部分组成。

1.1数据采集模块

本文使用Android智能手机平台作为手机采集的平台，手机型号为华为Mate1。当点击开始按钮时，开启线程开始采集传感器数据，采样频率为50 Hz。数据采集完毕后，通过MATLAB导入手机生成的数据文件，以方便数据分析，其中，数据采集模块流程框图如图1所示。

图1　数据采集模块流程框图Fig.1　Flow diagram of data collection module

1.2数据处理模块

本文在选取特征量时，时域上可考虑的特征值有：陀螺能量，加速度能量，陀螺方差，加速度方差，加速度模值最大值、最小值，陀螺模值最大值、最小值，加速度均值，陀螺均值等。由于特征量较多，如果都作为神经网络(back propagation,BP)的输入进行训练，计算量会较大，因此，本文使用主成分分析法(principal component analysis, PCA) 对特征向量降维，找出最优特征量。

表1是通过统计产品与服务解决方案(statistical product and service solutions, SPSS)软件分析的结果。其中，加速度能量、加速度方差和陀螺方差分别对应成分1，2，3，它们的累积方差超过85%，因此，选择这3种特征量作为BP的输入特征量。

1.3姿态判别模块

此模块主要负责对手机姿态进行判别，模块接收数据处理模块传入的特征值，将得到的特征值代入已训练的BP神经网络模型，得到手机姿态，最后将判别结果传入航迹推算模块。

人工神经网络 (artificial neural networks, ANN)是一种模拟人类的思维方式，并根据这种思维方式进行的分布式并行信息处理的算法数学模型，ANN的自适应能力和自学习能力主要用于解决信号处理中的自适应和非线性问题[8-9]。

表1　主成份SPSS分析结果

注：提取方法为主成份分析。

BP神经网络的隐含层节点数对BP神经网络预测精度有较大的影响：节点数太少，网络不能很好地学习，需要增加训练次数，训练的精度也受影响；节点数太多，训练时间增加，网络容易过拟合。最佳隐含层节点数的选择主要参考(1)—(3)式。

(1)

(2)

l=lbn

(3)

(1)—(3)式中，n为输入层节点数；l为隐含层节点数；m为输出层节点数；a为0—10之间的常数。在实际问题中，隐含层节点数的选择首先是依据(1)—(3)式来确定节点数的大概范围，然后用试凑法确定最佳的节点数。

为了使BP神经网络有预测能力，必须先通过训练数据对BP神经网络网络训练，不断调整ωij和ωjk权值，最终使网络具有联想记忆和预测能力。BP神经网络的训练包括以下7个步骤。

步骤1网络初始化。根据系统输入输出序列(X,Y)确定网络输入层节点数n，隐含层节点数l，输出层节点数m，初始化输入层、隐含层和输出层神经元之间的连接权值ωij和ωjk，初始化隐含层阈值aj，输出层阈值bk，给定学习速率和神经元激励函数。

步骤2隐含层输出计算。根据输入变量xi，输入层和隐含层之间的连接权ωij以及隐含层阈值aj计算隐含层输出Hj，表示为

(4)

步骤3输出层输出计算。定义Ok为BP神经网络预测输出，它可以根据隐含层输出Hj，连接权值ωjk和阈值b计算得到

(5)

(5)式中，Ok为BP神经网络预测输出；ωjk为隐含层与输出层连接权值；bk为输出层阈值。

步骤4误差计算。根据网络预测输出Ok和期望输出Yk，本文取误差为

(6)

步骤5权值更新。更新网络连接权值ωij和ωjk，表示为

(7)

(8)

(7)—(8)式中，η为学习速率；ek代表期望输出Yk与网络预测输出Ok之间的差值。

步骤6阈值更新。通过网络预测误差ek设置网络节点阈值aj和bk。

(9)

(10)

步骤7判断预测误差ek是否达到要求，若达到，则结束学习过程，否则，返回步骤2。

输出层有手持、电话、上衣口袋、手臂摆动4种，即输出层有4个节点。输入层可考虑的特征值有陀螺方差、加速度能量、加速度方差3个节点。

采集不同姿态下步行的数据，采集人员身高分布为155—160 cm4人，160—165 cm5人，165—170 cm10人，170—175 cm6人，175—180 cm4人，一共29人，基本覆盖所有智能手机用户群。由于数据量较大，数据采集在一周内分批次完成。本文一共采集不同姿态的训练样本数1 840份。每种姿态样本数均为460份，采集的样本数如表2所示。

表2　不同行为的样本数

1.4航迹推算模块

1.4.1航迹推算原理

此模块主要负责计算行人的坐标位置，模块接收数据处理模块传入的原始数据，结合姿态判别模块的输出结果对原始数据进行相应坐标变换，然后利用PDR算法求解出行人的步态、步长以及经过修正后的航向值，最终得到行人的位置坐标。

航迹推算技术基本思想是通过载体携带的加速度传感器及航向传感器获得单位时间内载体发生的位移及航向，从而可以根据上一时刻载体的位置和航向推算出当前载体在当前时刻的位置和航向。如图2所示，图2中，E，N分别表示正东方位、正北方位，O为原点，若已知开始时刻的位置坐标(x0,y0)，则任一时刻(xk,yk)的位置坐标为

(11)

(11)式中，θi和di分别表示第i步的航向角和步长。

图2　航迹推算原理Fig.2　Principle of pedestrian dead reckoning

1.4.2步态检测

考虑手臂摆动姿态与非手臂摆动姿态运动的差异性，常用的峰值检测，零点检测以及融合步态检测算法都不适用于手臂摆动姿态。因此，本文通过分析大量数据，利用一个迈步周期中加速度变化特性，设计了一种新的全姿态下的计步算法。为了避免手臂摆动姿态的漏计步现象，本文设计的步态检测算法只需进行波峰与波谷的检测，检测波峰时将上一步的波谷与波峰均值作为比较条件，若满足，则继续进行波谷检测，检测到波谷，则认为检测到一个步态。本文设计的全姿态下的计步算法为

(12)

(12)式中，ΔT为2个相邻峰值之间的时间间隔；Tth为设定的时间阈值，Acc_max(i-1)和Acc_min(i-1) 分别为上一步的波峰与波谷，Acc_max(i)为当前步的波峰。

利用本文提出的步态检测算法对4种姿态下的行走数据进行处理(见图3)。由图3可以看到，4种单一姿态下的步态基本被标注了出来，步态判别准确率接近100%。

图3　4种姿态步态检测图Fig.3　Gait dection of four attitude

1.4.3步长估计

自行人航迹推算算法出现以来，步长估计的精度是行人航迹推算算法中关键的一步，影响整个算法的精度，因此，步长估计算法也成为广大学者研究的重点，如线性模型，到人体运动模型，再到经验模型，再到之后的神经网络模型等。

本文使用一种常用且精度相对较高的线性模型来进行步长估计，影响行人步长的因素主要是步频和行人身高，因此，本文使用了行人身高与步频来计算行人步长，表示为

(13)

(13)式中，h代表行人的身高；fstep为行人行走的步频；a,b,c分别为线性模型公式的校准系数，通过大量的训练数据得到不同姿态下校准系数a,b,c的值，可以通过调整校准系数a,b,c的值来求得不同姿态下较准确的步长估计。

1.4.4航向修正算法

行人在使用手机过程中切换到其他姿态会造成2个问题：1)横滚角接近90°时(如电话姿态、上衣口袋姿态横滚角姿态)，姿态融合算法解算的航向会出现跳变的现象；2)姿态切换间切换时，手机坐标系与行人坐标系不再相对静止，根据手机传感器数据解算的航向不能反映行人的运动轨迹，因此，需要对多姿态下的航向进行修正。本文行人航向修正算法分为两个部分：稳定姿态航向修正与姿态切换航向修正。

航向修正算法首先通过互相关性检测行人是否进入姿态切换过程，若进入姿态切换过程，算法首先判断姿态切换前3步行人是否在直线行走，若是，则取3步航向平均值作为姿态切换过程替代航向，从而对姿态切换过程的航向进行了修正。姿态切换过程后，进入单一姿态修正过程。若算法判别姿态进入电话或者上衣口袋姿态，则需要对采集到的原始数据进行坐标变换，坐标变换公式为

(14)

(15)

(14)—(15)式中，[xh,yh,zh]T为变换前的坐标，[new_xh_ear,new_yh_ear,new_zh_ear]T为切换到打电话姿态后的坐标，变换矩阵为[00-1;0-10;-100]，[new_xh_packet, new_yh_packet,new_zh_packet]T为切换到上衣口袋姿态的坐标，变换矩阵为[00-1;010;100]。

2测试

本文选取重庆邮电大学三教学楼过道等室内场景作为测试地点。开始测试时，将华为Mate1手机拿在手中，沿着图4给出的轨迹以正常速度行走。行走过程中在不同姿态间进行切换，除了姿态切换过程，其他阶段保持手机基本稳定。测试时行走轨迹需要形成一个环路，使起点与终点重合，测试完毕后记录定位精度，若起点和终点最后的误差越小，则说明系统的定位效果越好，图5是通过改进前的PDR算法得到的轨迹图，图6是通过本文改进后的PDR算法得到的轨迹图，可见，本文改进后的PDR算法可在多姿态切换行走过程中得到稳定的航向信息。

图4　行走参考轨迹Fig.4　Walking reference trajectory of pedestrian

图5　PDR算法得到的轨迹Fig.5　Trajectory obtained by the PDR

图6　PDR算法改进后得到的轨迹Fig.6　Trajectory obtained by the improved PDR

本文在多个测试场景对软件进行了测试，测试完成后统计测试达标次数与达标率，如表3所示。可以看到，本文设计的算法可实现在多姿态下的室内定位，系统定位精度在20‰以内(步行1 km，误差在20 m以内)达标率在85%以上，基本满足行人室内定位需求。

表3　轨迹精度测试结果

3结论

在室内定位系统中，针对传统PDR算法约束条件高，在定位过程中手机只能保持静止的问题，分析了行人使用手机常见的4种姿态，设计了一种改进的行人导航算法，该算法能够智能识别行人使用手机时的姿态，实现了4种姿态下的定位，并有效解决了不同姿态间切换造成的航向跳变现象，使得行人可以在定位过程中自由切换手机姿态，能够满足行人在室内使用手机进行需求。

参考文献：

[1]付强文, 秦永元, 李四海, 等. 车辆运动学约束辅助的惯性导航算法[J]. 中国惯性技术学报, 2012, 20(6): 640-643.

FU Qiangwen, QIN Yongyuan, LI Sihai, et al. Vehicle kinematics constraints aided inertial navigation algorithm[J]. Journal of Chinese Inertial Technology, 2012, 20(6): 640-643.

[2]RYAN J G, BEVLY D M. On the Observability of Loosely Coupled Global Positioning System/Inertial Navigation System Integrations With Five Degree of Freedom and Four Degree of Freedom Inertial Measurement Units[J]. Journal of Dynamic Systems, Measurement, and Control, 2014, 136(2): 21-23.

[3]CHO S Y, PARK C G. MEMS based pedestrian navigation system[J].Journal of Navigation, 2006, 59(01): 135-153.

[4]田增山, 张媛. 基于智能手机 MARG 传感器的行人导航算法[J]. 重庆邮电大学学报: 自然科学版, 2014, 26(2): 223-227.

TIAN Zengshan, ZHANG Yuan. Pedestrian navigation algorithm based on smartphone MARG sensor[J].Journal of Chongqing university of posts and telecommunications: Natural Science Edition, 2014, 26(2): 223-227.

[5]LIU J, CHEN R, PEI L, et al. A hybrid smartphone indoor positioning solution for mobile LBS[J]. Sensors, 2012, 12(12): 17208-17233.

[6]SUSI M, RENAUDIN V, LACHAPELLE G. Motion mode recognition and step detection algorithms for mobile phone users[J].Sensors, 2013, 13(2): 1539-1562.

[7]ZHANG H M, YUAN W Z, SHEN Q, et al. A Handheld Inertial Pedestrian Navigation System with Accurate Step Modes and Device Poses Recognition[J].Sensors Journal IEEE, 2015, 15(3):1421-1429.

[8]袁曾任. 人工神经元网络及其应用[M].北京: 清华大学出版社, 1999: 29-35.YUAN Zengren. The application of Artificial neural network[M].Beijing: Tsinghua University Press,1999:29-35.

[9]史峰, 王小川, 郁磊, 等. MATLAB神经网络30个案例分析[M].北京: 北京航空航天大学出版社, 2010: 12-16.

SHI Feng, WANG XiaoChuan, YU Lei, et al. 30 case analysis of MATLAB neural network[M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2010: 12-16.

An improved pedestrian navigation algorithm

LIU Yu, XIANG Gaolin, WANG Yibing, CHEN Yanping, LV Ling, HUANG Heming

(Chongqing Key Laboratory of Photoelectronic Information Sensing and Transmitting Technology,Chongqing University of Posts and Telecommunications, Chongqing 400065,P.R.China)

Abstract:Nowadays the premise of most pedestrian navigation system is used by a single pose, such as hand-held, tied to the waist and so on, but the diversity ways in which people use smart phones are not taken into consideration, such as taking a phone call, putting the phone in the pocket at the same time. This paper analyzes the four poses by which pedestrians use smart phones and an improved pedestrian navigation algorithm based on the PDR. Firstly, the algorithm used the BP neural network model to identify the smartphone attitude. Secondly, a new gait step detection algorithm was designed to detect the step in four poses. Finally, the pedestrian walking process can be divided into single posture and posture switching process. This paper corrected the heading of the two walking process. The software test results showed that achieving the control rate of system positioning precision within 20‰ was above 85% for the posture. The navigation system can provide accurate, reliable and continuous location information by the improved algorithm.

Keywords：pedestrian navigation; back propagation (BP) neural net; posture recognition; step detection; head correction

DOI：10.3979/j.issn.1673-825X.2016.02.015

收稿日期：2015-05-18

修订日期：2015-12-21通讯作者：刘宇liuyu@cqupt.edu.cn

基金项目：国家自然科学基金 (51175535)；国际联合研究中心科技平台与基地建设(cstc2014gjhz0038)；重庆市研究生科研创新项目(cys15163)

Foundation Items：The National Natural Science Foundation of China(51175535); The International Joint Research Center technology platform and base construction(cstc2014gjhz0038); The Graduate student research innovation project of Chongqing(cys15163)

中图分类号：TP274

文献标志码：A

文章编号：1673-825X(2016)02-0233-06

作者简介：

刘宇(1972-)，男，重庆人，教授，博士，硕士生导师，长期从事微振动惯性传感器、光机电一体化科学技术研发和MEMS惯性传感技术研究。E-mail：liuyu@cqupt.edu.cn。

向高林(1990-)，男，重庆人，硕士研究生，主要研究方向为MEMS惯性传感技术。E-mail：xianggaocqupt@sina.com。

(编辑：王敏琦)