一种基于聚类及几何特征的北斗轨迹纠偏抽稀方法

周雅静 王得举

（1.宁波城市职业技术学院 浙江省宁波市 315000 2.上海普适导航科技股份有限公司 上海市 200000）

北斗定位终端在接收信号差、外界干扰等因素下，会出现位置漂移现象。漂移现象会造成航程数据显著增加，出现较大的统计错误；同时轨迹位置在前端UI 渲染展示时，会出现杂乱无章的连线，UI 效果也不美观。因此需要研究对漂移点的纠正。

北斗定位终端在上报位置的时候，一般都是定时回报位置数据，在有地面通信网络的情况下，其报告周期一般比较小，会上报大量的数据。大量的点在对外输出及展示等情况下是不利的。需要寻找关键有价值的位置点并保留下来、剔除不影响整体轨迹的低价值位置点，来整体提升系统的效率。

本文通过对位置聚类及几何特征的研究，形成一种能对轨迹点进行纠正、抽稀的方法，使得轨迹展示效果快速、平滑并保留重要的轮廓特征点。

1 纠正算法

发生发散漂移的判定规则是在较短的时间间隔内，位置发生剧烈的变化。

对于一批待纠正的轨迹点序列，每一点其包括的元素为经度、维度、时间等属性。轨迹序列使用P={p1,p2,……,pn}表示，其中pi表示某点的相关信息。纠正算法采取滑动轨迹序列窗口方式[1]，滑动窗口是指在轨迹序列中，截取的固定长度的连续子序列，并不断向前推进窗口滑动，完成序列的遍历。

滑动窗口长度以WinLen 表示（默认5 个点），设计目标在一个滑动窗口长度内，可以纠正一个轨迹点的发散漂移。

从P={p1,p2,……,pn}中，取第一窗口作为开始滑动窗口。系统默认开始窗口序列点未发生漂移现象。待检测点为紧接着该窗口内的下一点。计算待检测点和第一窗口最后点的时间间隔TDF，时间间隔阈值是系统给定的超参数。如果时间间隔TDF 大于间隔阈值，不进行纠正算法，窗口向前滑动一位作为新的窗口，窗口的元素始终为WinLen 个。待检测点下移一位。重复待检测点和第一窗口最后点的时间间隔判断。

如果时间间隔TDF 小于设定参数，则进行新的距离判断流程：计算滑窗内相邻两点的球面距离间隔，求其窗内距离间隔平均值记为APW，并计算待检测点和滑动窗口最后点的位置间隔PDF；如果PDF 小于APW 的设定倍数（默认2.0），认为不是漂散点，继续采取滑窗和检测点都前移一位的方式，继续采取上述先判定时间后判定距离的方式。如果PDF 大于APW 的设定倍数（默认2.0），认为是漂散点，采取差值的方式进行位置纠正，纠正的方式是取滑窗内后两点修正。修正公式为：

x,y 分表表示经纬度。当进行差值纠正时，为减少累计效应，影响整体轨迹效果，这时候整个窗口向前滑动WinLen 个单位，待检测点向前移动WinLen 个单位。开始新的检测流程。

2 形成骨架

从P={p1,p2,……,pn}中取子序列P1={p1,p2,……,pi}、 P2={p1,p2, ……,pi+1}。计算P1 中任意两点最远距离为D1MAX，计算P2 中任意两点最远距离为D2MAX；如果D2MAX-D1MAX 小于给定聚类距离超参阈值，认为pi+1点的加入P1 不会改变P1 的聚集态势，可以继续检测下一个点，因此这时候 i=i+1，增加新的一个点到P1、P2 子序列中，重复上述检测；如果D2MAX-D1MAX 大于给定聚类距离超参阈值，认为pi+1点不能加入P1 子序列中；这时候P1 子序列的质心点pm代替P1 子序列，P1 原点位被抽稀掉。新选取子序列P1，P2 在i 序号的基础上作为起点，重复计算直到P 序列被遍历完全。

图1：拐点示意图

图2：折点示意图

图3：未处理的漂点

求出质心点计算公式：

3 骨架抽稀

轨迹上的特征点是指描述轨迹走向、轮廓的重要点。通常是拐点或折线点，重要的点在抽稀过程中要保留，只能抽稀掉非重要的点。

拐点，又称反曲点，在数学上指改变曲线向上或向下方向的点，直观地说拐点是使切线穿越曲线的点，即连续曲线的凹弧与凸弧的分界点。若该曲线图形的函数在拐点有二阶导数，则二阶导数在拐点处异号或不存在。

通过相邻的四点（A,B,C,D）进行检测，对（AB,BC,CD）线段集，判断（ABXBC）、（BCXCD）叉乘结果是否相异来判断[2]。

对于折线点，采用三点来检测夹角∠ABC 来判断。∠ABC 通过计算|AB|，|BC|，|AC|线段长度，反余弦函数来计算完成。系统给定两个角度阈值超参。一个是较大角度阈值，一个是较小角度阈值。自适应选择其中之一作为当前阈值进行角度检测。当∠ABC 小于当前角度阈值的时候。认为点B 是折线点，在抽稀过程中要保留。

自适应选择作当前角度阈值的策略方法是：

当前点B 被抽稀掉的时候，说明下一个点对于保持轮廓相对重要，因此当前角度取较小角度阈值，增加下一点被保留的可能性；

当前点B 被作为重要点保留的时候，下一个点对于保持轮廓不重要，当前角度取较大的角度阈值，减少下一点被保留的可能性。

4 实验效果

在图3 为原始的未处理的漂点，可以看到漂移比较严重。经过算法纠正后，漂点得到纠正，效果良好，如图4 所示。

图5 为原始轨迹图，有2257 个点位；图6 为经过算法计算后的点位，仅有1029 个点位，相对原始数据，数据量大幅度减少，同时保留的轨迹的特征和轮廓。

图4：纠正漂点后的轨迹

图5：2257 个的原始轨迹

图6：抽稀后轨迹1029 个点