基于UCR-DTW的地磁序列定位算法

金俊超, 马昌忠, 陈国良, 王俊鹏, 刘 奔

(1.中国矿业大学 自然资源部国土环境与灾害监测重点实验室,江苏 徐州 221116; 2.中国矿业大学 环境与测绘学院,江苏 徐州 221116)

目前,基于智能手机的室内定位技术有多种,如Wi-Fi技术、视觉技术、蓝牙技术、超宽带(ultra-wide band, UWB)技术、声波技术、伪卫星技术、行人轨迹推算技术和5G技术等,但是这些技术都不完善,存在一些缺点。例如,Wi-Fi与蓝牙定位技术精度低且受多路径影响,UWB与伪卫星技术辅助设施布设成本昂贵,声波定位技术的穿透能力较弱,行人轨迹推算技术具有误差累积等。

地磁定位作为无源自主定位技术,具有不受多路径效应与人体遮挡影响[1]、地磁场随时间变化稳定且任意位置都具有独特的地磁强度与方向[2]等优点,并且在室内建筑中由于钢筋混凝土等材料的影响,室内地磁特征明显,更有利于定位[3]。其中地磁序列定位由于精度高于点定位,相关研究成果丰富。文献[4]提出一种基于轨迹匹配的地磁定位系统,该系统可以确保在没有惯性传感器辅助下,利用改进的Smith-Waterman算法实现局部路径匹配,然后利用改进的Dijkstra模型完成行人轨迹构建,实现大型室内场景的定位;文献[5]提出一种注意力机制引导下的基于多尺度信号序列的室内定位网络,基于循环神经网络提取各个尺度下的特征信息,然后利用注意力机制将多尺度特征拼接，生成融合特征来完成匹配定位,但是深度学习运算量较大,目前很难在智能手机端完成算法运算;文献[6]提出了基于智能手机的地磁定位系统,首次将动态时间规整(dynamic time warping,DTW)算法应用于地磁序列定位中,精度达到80%以上,但是DTW算法的计算复杂度较高,导致计算效率低,无法满足室内定位实时性的需求;文献[7]针对地磁匹配的时间成本高问题,提出利用Wi-Fi信号辅助缩小匹配搜索区域,极大提高了地磁匹配效率,但是Wi-Fi指纹建库较为繁琐,前期需要消耗大量时间;文献[8]针对DTW算法计算复杂度高与实时性差问题,将快速动态规整(fast dynamic time warping,FastDTW)算法用于地磁定位,利用粗粒度化方法缩短序列长度,减小计算复杂度,计算完成后再细粒度化地磁预规整路径,规整到原来地磁序列大小来实现定位。但是,目前在地磁序列匹配相关研究中,关于DTW算法计算效率优化问题的解决方法较少,还需要进一步研究。

针对目前基于DTW的地磁定位算法计算效率低和定位时间长问题,本文提出利用加州大学河滨分校(University of California, Riverside,UCR)优化策略[9]来提高DTW算法计算效率,序列匹配时先利用重排序策略对序列进行重新排列,然后利用级联下界约束策略在DTW计算前进行约束,提前筛选指纹库内待匹配序列,将筛选得到的待匹配序列进行DTW计算,并利用全局约束策略与DTW提前抛弃策略对DTW计算进行约束。本文将基于UCR-DTW的地磁序列匹配定位算法称为本文算法,实验结果证明,地磁序列匹配效率得到了较大的提升。

1 基于UCR优化策略的DTW算法

1.1 DTW算法原理

DTW算法作为一种时间序列数据的相似性度量算法,可进行一对多的相似性匹配,匹配准确率高于欧式距离[9]。假设2条序列长度分别为m、n,构建距离矩阵dm×n后,逐步计算累积距离D(i,j),直到D(m,n)计算完成,时间计算复杂度为O(mn),无法满足室内定位算法实时性的需求。D(i,j)计算公式为:

D(i,j)=d(i,j)+min[D(i-1,j),

D(i,j-1),D(i-1,j-1)]

(1)

其中:i、j分别为2条序列上的对应序列点位置编号;i=1,2,…,m;j=1,2,…,n;d(i,j)为前一步的累积距离。

1.2 UCR优化策略

基于滑动窗口的DTW算法原理如图1所示。序列检索匹配时,减少算法时间计算复杂度的方式主要是减少DTW算法的矩阵搜索区域、缩短匹配的序列长度和减少DTW算法的重复计算次数。而UCR优化策略就是综合了上述第1种和第3种减少计算复杂度的方法。在数据库检索匹配时,对DTW结果值的计算进行条件约束,实现对数据库内序列的快速筛选,提高序列匹配效率,其策略可以概括如下。

图1 基于滑动窗口的DTW算法原理

(1) 全局约束。对DTW算法的计算范围进行约束,减少DTW算法的矩阵搜索区域。

(2) 下界约束。DTW下界(lower bound,LB)值LB(Q,C)与DTW计算结果值DTW(Q,C)满足的不等式为:

DTW(Q,C)≥LB(Q,C)

(2)

其中:Q为查询序列;C为待匹配序列。

利用下界计算复杂度低的优势,首先计算LB值,当LB值大于阈值bsf时,提前抛弃参与本次匹配的子序列,减少DTW算法的计算次数。本文利用Kim下界[10]和Keogh下界[11]。

(3) 自适应下界抛弃。利用阈值bsf约束下界计算。当LB值超过阈值时,DTW计算结果值也大于LB值,表明该条待匹配序列不是最优匹配序列,可以进行抛弃,减少DTW的重复计算次数。

(4) 序列重排序。按标准化值调整参与Keogh下界计算的序列值顺序,保证Keogh下界的LB值累加速度更快,达到下界抛弃条件,以达到加速效果。

(5) 下界计算对象转换。改进Keogh下界,保证改进Keogh下界值LBKeogh2(Q,C)优于Keogh下界值LBKeogh(Q,C),满足的条件为:

DTW(Q,C)≥LBKeogh2(Q,C)≥LBKeogh(Q,C)

(3)

(6)自适应DTW计算抛弃。利用Keogh下界历史值对DTW结果值的计算进行约束,当前DTW计算累积值大于LB值时,可以提前抛弃匹配序列,减少完整DTW算法的执行次数。

(7) 级联下界。利用不同下界计算复杂度从低到高进行计算,当计算复杂度较低的下界大于阈值时,可提前抛弃待匹配子序列,减少完整DTW结果值的计算次数。本文将Kim下界、Keogh下界和改进Keogh下界进行级联。

2 地磁定位方法

2.1 地磁序列匹配定位原理

地磁序列匹配定位分为离线采集阶段和在线匹配阶段，具体流程如图2所示。

图2 地磁序列匹配定位流程

离线采集阶段主要进行地磁指纹序列采集,将预处理后的地磁指纹序列与实际位置坐标建立映射关系,建立地磁指纹库;在线匹配阶段主要实时采集固定长度的地磁指纹序列,将预处理后的地磁序列与地磁指纹库进行指纹序列比对,确定最优定位结果。

2.2 本文算法

基于UCR-DTW的地磁序列定位算法流程如图3所示。

图3 基于UCR-DTW的地磁序列定位算法流程

手机磁力计可以获取某位置点磁场强度的三轴分量Mx、My、Mz。将三轴分量作为地磁指纹时,虽然精度高,但是易受手机姿态影响[4]。本文选取地磁模值M作为地磁指纹,其计算公式为:

(4)

在地磁序列匹配时,为确保两条序列的空间覆盖范围基本一致,本文利用波峰检测算法与Kim步长估计算法进行距离估计,获取查询序列。文献[12]研究表明，2.5 m左右的地磁序列匹配时误匹配现象较少,因此本文取2.5 m左右的地磁序列作为一个轨迹段进行匹配。当下界计算时,为了保证两条序列长度相同,利用分段聚合近似算法(piecewise aggregate approximation, PAA)[13]对序列长度进行扩充与缩减。

假设查询序列为Q,其长度为m,待匹配序列为C,其长度为n,其中n≫m。最优DTW计算结果值作为阈值bsf实现自动更新。匹配时,对查询序列Q进行标准化用于序列重排序,利用滑动窗口算法获取待匹配子序列,以下界约束策略与下界级联策略判断是否对待匹配子序列进行提前抛弃;在Kim下界计算时,利用阈值进行条件约束,并以重排序策略和下界抛弃策略对2类Keogh下界计算进行约束;最后利用全局约束策略与DTW抛弃策略在DTW算法计算时进行约束,将计算返回的DTW结果值与阈值进行比较,更新最优阈值和对应序列坐标,获取序列坐标最后一组坐标(x,y)作为当前定位结果。重复上述计算,获取最优DTW计算结果值对应的定位坐标。

3 实验与数据分析

本次实验基于Matlab平台,利用联想Y7000P笔记本(搭载i7-10875i处理器)进行试验。为了确保实验数据的可靠性,本次实验利用文献[14]在伊利诺斯大学采集制作的MagPIE数据集对DTW算法、FastDTW算法与本文算法进行比较测试。数据集内包含无人车采集和行人手持获取2类数据。为证明本文算法的实用性,实验选择行人手持模式,同时选择面积为470 m2的Loomis实验室的地磁数据。选择第1条、第2条和第3条训练序列作为指纹库序列,3条序列的长度依次为4 541、4 092、4 318,3条轨迹左右间隔0.5 m左右,指纹库内总序列长度为12 951,走廊总长度为100 m左右,地磁序列与指纹库轨迹如图4所示。现实应用中,多种轨迹段与行走速度存在差异;为减少误匹配现象出现次数,本文选取轨迹段为2.5 m的地磁序列进行算法测试。所有轨迹段均为正常行走状态下(不存在奔跑等现象,只存在行走速度差异)获取得到,轨迹近似直线行走,不存在原地踏步、转圈等特殊情况。

图4 指纹库地磁序列和指纹库轨迹

3.1 数据预处理

由于数据采集时已经对磁力计进行了校准,本次实验主要对地磁数据中的白噪声进行处理。利用小波变换算法对序列进行过滤,结果如图5所示。

图5 地磁序列滤波前后对比

由图5可知,过滤后数据与原始数据基本一致,证明数据集的数据质量较好,满足实验要求。将获取的地磁强度与数据集中Tango获取的高精度实际地理位置进行一对一映射,构建地磁指纹库。

3.2 算法运行效率

在测试集内,随机选取100条轨迹长度2.5 m左右的测试序列进行匹配定位,在获取轨迹长度基本不变的条件下,滑动窗口长度按照行人速度大小的不同进行随机变化,基本保持在60～95左右。地磁指纹库中存有3条路径的指纹序列,共12 951条地磁指纹数据,每次定位都需要遍历1次指纹库,最后取定位时间均值作为最终定位时间,分别将本文算法与FastDTW算法、DTW算法进行比较,结果见表1所列。

表1 3种算法平均定位时间 单位:s

从表1可以看出:当指纹库中的待匹配序列长度为4 092时,采用DTW算法和FastDTW算法的平均计算时间分别为2.311 9、2.636 6 s,在动态定位时,行人正常行走速度保持在0.69～1.82 m/s之间[12],每执行1次算法计算,行人将行走1.8～ 4.0 m距离,导致计算出的定位结果与实际行人位置差异较大,无法满足实时定位的需求;而本文算法的平均时间为0.192 5 s,行人行走0.1～0.3 m左右,与实际行人位置差异较小,基本满足实时定位需求；同时,随着待匹配序列长度的不断增加,DTW算法与FastDTW算法计算时间会随之线性增长,而本文算法的计算时间增长较慢,且耗时极短。相比于DTW算法,本文算法的计算时间减少高达90%以上,可见UCR策略的加速效果;而FastDTW算法的计算时间无明显提升(该现象已经在文献[15]中进行了分析)。FastDTW算法的确能够增速,但是对于查询序列的长度存在要求,随着查询序列长度增加,FastDTW算法的增速才能够体现,当查询序列大于100以上时,FastDTW算法有明显的提速效果。在指纹库待匹配序列长度为4 092时,以滑动窗口长度为100、150、200进行实验,结果见表2所列。

表2 不同滑动窗口长度下算法平均定位时间 单位:s

从表2可以看出,FastDTW算法随着滑动窗口长度增加,增速效果明显,计算效率也逐渐提升,但本文算法的计算效率还是明显强于其他2种算法,同时滑动窗口长度增加对本文算法计算时间的影响较小。

3.3 算法定位精度

为研究本文算法对定位精度的影响,利用上述构建完成的指纹库进一步进行测试。随机选取100条测试序列,其轨迹长度为2.5m左右,序列长度不一(序列长度为60～95之间)。本文算法、DTW算法和FastDTW算法的定位误差分布结果和累积分布函数(cumulative distribution function,CDF)曲线分别如图6、图7所示。

图6 算法定位误差分布

图7 算法定位误差CDF曲线

由图6可知,本文算法和其他2种算法相似,都存在个别定位误差极大的点,误差保持在30 m以上,本文将其当作粗差进行处理。由图7可知,当定位误差达到25 m左右时,CDF曲线已经趋于平稳,即后续的定位误差点发生了严重误匹配,可视为粗差,本文利用聚类函数对其进行剔除。将本文算法、DTW算法和FastDTW算法获得的定位误差结果进行误匹配率(V)、平均定位误差(E)和均方根误差(root mean square error, RMSE)计算,计算结果见表3所列。V、E、RMSE计算公式分别为:

其中:qmis为误匹配序列数;qall为测试序列总数,本文qall=100;ei为每条测试序列的匹配误差;n为序列总数,本文n=100。

从表3可以看出:3种算法的平均定位误差基本保持一致;从RMSE看,UCR优化策略对于DTW算法的精度不会产生显著影响,RMSE也基本一致;而误匹配率保持在21%左右,这主要是由于单独使用地磁强度作为指纹,导致地磁指纹特征在大区域内还是存在一定的相似度。

表3 3种算法误匹配率和误差对比

4 结 论

针对经典DTW算法计算效率低,无法满足室内定位实时性的需求,本文提出一种基于UCR优化策略的地磁序列定位算法。该算法利用UCR优化策略对DTW算法进行优化,在保证定位精度基本不变的情况下,加速效果明显;相比于DTW算法与FastDTW算法,在地磁序列匹配应用中,地磁序列匹配效率提高了90%以上。