基于行人航位推算的后向地磁匹配算法

王安义， 欧 雪

(西安科技大学通信与信息工程学院， 西安 710054)

随着信息时代的到来，人们越来越依赖基于位置的服务(location based service，LBS)。在室外环境中，全球定位系统(global positioning system，GPS)能够提供准确的LBS，然而在室内环境中，GPS信号受到建筑物的遮挡，不能提供准确的定位服务，因此全球导航卫星系统(global navigation satellite system，GNSS)技术无法应用到室内环境中[1]。室内环境一般比较复杂，建筑物内部结构的复杂性、室内物品的摆放等的影响将会造成无线信号的多径传播、非视距接收，因此基于无线信号传播的室内定位方法具有一定局限性[2]。行人航位推算(pedestrian dead reckoning，PDR)是低成本便携式设备中航迹推算思想的延伸[3]，通过步数和步长计算距离，并通过磁力计和陀螺仪确定方向，能保持较高的定位精度，成为一种新兴的定位方法。

中外对PDR和地磁融合定位[4]的研究已取得一些成果；芬兰IndoorAtlas公司开发的一款利用地磁信息定位的软件可以达到2～3 m的定位精度[5]；文献[6]利用移动机器人，结合动态时间规整(dynamic time warping, DTW)和粒子滤波算法进行地磁定位，定位精度优于1 m，但考虑行人和机器人移动方式的不同，算法的可移植性尚待商榷；文献[7-8]提出一种指纹快速采集方法用于构建地磁指纹库从而进行快速定位，该方法需要数据集人员匀速行走连续采集地磁数据后，再将数据均匀分配到采集路线上的各个点，对采集人员行走过程稳定性要求极高，实际操作难度太大；文献[9-10]利用惯性导航结合地磁进行室内定位，有效弥补了惯性传感器长期使用不稳定的缺点，但只使用了单点地磁值作为匹配对象，在地磁分辨率不高的区域将出现误匹配；文献[11]提出一种增强型粒子滤波法用于提高室内手机定位系统的定位精度，可以实现1～2 m的定位精度，但是算法过于复杂。

针对上述问题，现提出一种基于PDR的后向地磁匹配算法，将单点匹配和序列匹配进行融合。整个过程依赖于智能手机获取行人实时的加速度测量值、陀螺仪测量值和磁力计测量值。在地磁匹配阶段，首先利用K最近邻(K-nearest neighbor, KNN)算法计算与PDR解算得到的当前时刻位置最近的N个地磁基准点和该N个地磁基准点中与当前时刻地磁模值相似度最大的K个地磁基准点，然后将当前时刻与上一时刻(一个步伐)的地磁序列与K个地磁基准点作为终点的K条基准地磁序列进行DTW匹配，匹配度最高的基准地磁序列的终点即为当前时刻最优位置。

1 定位原理

1.1 PDR定位

PDR利用惯性传感器得到的数据来计算行人相对位置从而实现定位[12]，其定位原理如图1所示。

图1 PDR定位原理图Fig.1 PDR positioning schematic diagram

k-1时刻位置Pk-1的坐标为 (xk-1,yk-1)，行人从点Pk-1运动到点Pk(xk,yk)时，利用行走的距离Sk和航向角θk可以通过式(1)得到P1的坐标为

(1)

从式(1)可知，在已知前一时刻位置的基础上可以通过PDR解算出当前时刻的位置。式(1)中有两个关键参数S和θ，即当前时刻的步长和迈步朝向。

在实际的行走过程中，距离S为每一个步伐内的步长。S可以通过加速度计算得到，行人手持的智能手机内置加速度计可以实时记录行走时三维加速度值。利用加速度差值计算步长[13]，表达式为

(2)

式(2)中:k1和k2为固定常数；γ为补偿参数；Tstep为该步的时间长度；Δa为一个步伐内的加速度差值的平均数；amax和amin分别为一个步伐内加速度最大值和最小值。

航向角θ可以通过磁力计测量值进行坐标系换算和陀螺仪测量值积分得到，通过粒子滤波算法融合磁力计和陀螺仪的方向角，最终确定θ的值。

1.2 地磁定位

地磁定位是指纹定位的一种，由离线构建地磁基准库、在线匹配定位两个阶段构成。首先采集室内区域地磁场特征信息，得到地磁指纹库，经过处理得到较高分辨率的地磁基准库。当行人经过该区域时，随身携带的智能手机内置的磁力计实时获取地磁场的特征值信息，并利用相关算法与地磁基准库中地磁信息进行匹配。通过计算后确定当前地磁信息与地磁基准库中的最相似点即匹配点，最终确定出行人的精确位置。

在构建地磁基准库时，首先需要采集定位区域的地磁信息。单点采集和连续采集是最常用的两种地磁数据采集方式。单点采集是指按一定采样间隔记录定位区域的地磁信息，然后通过插值算法增加数据密度。连续采集是指采集人员手持采集仪器在定位区域按路线匀速行走，再将采集的数据均匀分配在行走路线上。

在线匹配定位时，通过相关度量匹配、DTW等匹配算法将当前时刻的地磁信息与地磁基准库中的数据进行匹配[14]，确定当前时刻的位置。

2 改进的地磁定位匹配算法

分别优化离线建库和在线匹配两个阶段，改进后的定位框图如图2所示。

图2 地磁定位框图Fig.2 Magnetic positioning block diagram

离线建库：采集定位区域的地磁信息并生成两个不同分辨率的地磁基准库。

在线匹配：将实时的单点地磁信息与地磁基准库1作单点匹配，并利用DTW算法将实时的地磁序列与地磁基准2作序列匹配，最终输出位置。

2.1 双分辨率地磁基准库

利用连续采集法对定位区域进行地磁数据采集时对采集人员的行走速度有极高的匀速要求，如果行走速度没有固定，后续构建的地磁基准库将出现不可忽略的误差。不同行人行走速度各不相同，如果测试人员与数据采集人员行走模式和行走速度差异较大，将出现无法匹配的问题。因此选择单点采集的方式采集用于构建地磁指纹库的地磁数据，用地磁模值作为地磁特征量，表达式为

(3)

式(3)中：Mi为点Pi(xi,yi)的地磁值；Mx、My、Mz分别为手机载体坐标中三轴磁力值。

针对单点采集费时费力问题，利用克里金插值算法[15]减少数据采集量,在已测得Pi点的地磁值的前提下，Pk点的地磁值可以表示为

(4)

式(4)中：λi为每个采样点的权值，与插值点和采样的距离及采样点空间分布有关。λi需要满足条件

(5)

(6)

式中：γ(Pi,Pj)为样本点Pi与Pj的半变异值；γ(Pi,Pk)为样本点Pi与插值点Pk的半变异值；φ为满足方差最小化条件的拉格朗日常数。

通过设置不同插值密度可以构建不同分辨率的地磁基准库。插值密度过低将造成地磁指纹过少出现较大定位误差，插值密度过高将出现大量等值数据，在匹配阶段将“一对多”情况，导致定位失败。基于以上考虑，将构建双密度的地磁基准库用于后续地磁匹配。

2.2 基于DTW的后向地磁匹配算法

单点匹配简单方便但利用的有效信息太少，容易出现误匹配，严重影响定位精度。序列匹配可以有效提高匹配精度,但全局搜索的方式复杂且浪费时间。基于DTW的序列匹配可以允许两个匹配序列长度不一致，匹配方式灵活、效率更高。利用单点匹配和序列匹配结合的方式用于地磁匹配，达到定位目的，具体过程分为以下几个步骤：

步骤一PDR解算出当前时刻位置Pi。

步骤二在地磁基准库1中搜索与Pi欧式距离最近的N个地磁基准点。

步骤三在N个点中搜索与此刻地磁值相似度最高的K个点，该K个点即为单点匹配结果及K条地磁基准序列匹配终点。

步骤四利用DTW将当前步伐(抬脚-落脚)内的连续地磁序列与地磁基准库2中的K条地磁基准序列进行匹配。

步骤五最佳匹配的地磁基准序列的终点Ki为解算出的当前时刻位置。

假设地磁测试指纹序列T和参考指纹序列K的长度分别为m和n，T={m1,m2,…,mm}，K={M1,M2,…,Mn}，序列T中所有元素与K中所有元素构成的距离矩阵可以表示为

(7)

式(7)中:d(i,j)为测试指纹序列T中的第i个位置的特征量mi与参考指纹序列K中第j个位置的特征量Mj之间的距离。首先初始化累积距离矩阵，即D(1,1)=(1,1)，则有D(1,2)=D(1,1)+d(1,2)，D(2,1)=D(1,1)+d(2,1)。由于(i,j)只允许到达水平格点(i-1,j)、竖直格点(i,j-1)以及对角格点(i-1,j-1)的三者之一，因此可以得到该帧到下一帧的最短距离为min[D(i-1,j),D(i,j-1),D(i-1,j-1)]，通过递推计算出两个序列的累积距离最小值

D(m,n)=d(m,n)+min[D(m-1,n),D(m,n-1),D(m-1,n-1)]，

m,n≥2

(8)

依次连接各帧之间最小距离对应的点得到测试指纹序列与参考指纹序列之间的规整路径。

最终累积距离最小的地磁基准序列的终点Ki即为输出位置。

3 实验与分析

为了验证本文算法的有效性，在西安科技大学北院3号教学楼四楼走廊进行实验。该楼层为实验室集中楼层，有大量电子仪器，能够较好地检验算法的抗干扰性。实验所用的手机型号为iphone 8，实验所用数据来源于手机内置的磁力计、加速度计、陀螺仪和计时器。实验人员先用定点法采集实验区域地磁数据，再随机行走形成若干条待定位路径用于测试算法。

3.1 离线建库

在构建地磁指纹库过程中，利用地砖将定位区域划分为90 cm × 60 cm的长方形小区域。采集时实验人员在每个长方形顶点距离地面约1 m处以50 Hz的采样频率连续采集5 s，然后对每个采样点的三维磁场数据进行求模值、滤波和平均处理，得到地磁指纹库如图3所示。

图3 地磁指纹库Fig.3 Geomagnetic fingerprint library

图4 不同插值间隔生成的地磁基准库Fig.4 Geomagnetic reference library generated by different interpolation intervals

图4为插值后的地磁基准库分辨率示意图，由地磁指纹库进行克里金插值处理后生成。为了比较不同插值间隔对地磁分辨率的影响，选取了三组插值间隔进行分析比较，分别为0.2 m×0.4 m，0.1 m×0.2 m和0.05 m×0.1 m。

通过观察分析可知，适当缩小插值间隔可以提高地磁基准库分辨率，如图4(b)分辨率高于图4(a)。然而插值间隔与分辨率并不是严格呈反比关系，图4(c)插值间隔在图4(b)基础上缩小了10倍，但分辨率并没有明显提高。考虑到行人的身体宽度，30～40 cm的定位误差都是可以接受的，因此在单点匹配时选用的地磁基准库1的插值间隔为0.2 m×0.4 m。考虑到PDR过程采样频率的影响，序列匹配的地磁基准库插值间隔为0.1 m×0.2 m。

3.2 在线定位

在PDR中，对加速度进行处理后用于步伐检测，步伐检测结果如图5所示。

图5 步伐检测结果Fig.5 Step detection results

图5中，一个完整的步伐由A→B→C→D→E组成，其中点A、点C和点E代表加速度过零点，点B和点D分别代表加速度峰值和谷值。用一个步伐结束时刻(点E)的磁力计测量值与地磁基准库1进行单点匹配，用一个步伐内(点A至点E)的地磁序列与地磁基准库2进行DTW匹配。

以一个随机测试点为例，得到的单点匹配结果如图6所示。基准点与PDR地磁值相似度最高的5个点即为单点匹配结果，将作为接下来序列匹配的终点。

图6 单点匹配结果Fig.6 Single point matching results

接着进行DTW匹配，计算实验地磁序列与五条地磁基准序列的最小累积距离，累积距离最小的地磁基准序列与实验地磁序列的匹配情况如图7所示。

图7 DTW匹配结果Fig.7 DTW match results

实验人员选择两条路径，每一条路径以任意速度行走五次，共获取10组待定位数据。在给定初始位置的前提下，通过本文算法解算出位置信息，得到的平均位误差如表1所示。

表1 10组数据平均定位误差Table 1 Average positioning error of 10 groups of data

从表1中可以分析得到，10组数据平均定位误差均小于1.5 m，其中最大平均定位误差为1.26 m，最小平均定位误差为0.52 m。路径一的定位效果明显路径二，通过分析原始地磁数据得知，路径二的地磁变化更明显，更有利于地磁匹配，因此定位精度更高。

4 结论

针对常用地磁匹配算法存在的匹配搜索范围过广、时间过长的问题，提出构建双分辨率地磁基准库，并融合单点匹配和序列匹配提高匹配效率。比较了不同插值间隔的克里金插值方法对地磁分辨效果的影响，以此为根据选取两组不同插值间隔用于构建双分辨率地磁基准库，同时改进基于DTW的后向地磁序列匹配算法。经过实验验证，本文算法最大定位误差小于1.5 m，可以满足普通室内定位需求。