一种基于双队列技术的过滤GPS位置漂移点的方法及装置

一种基于双队列技术的过滤gps位置漂移点的方法及装置
技术领域
1.本发明涉及gps定位监控技术领域，特别是涉及一种基于双队列技术的过滤gps位置漂移点的方法及装置。

背景技术：

2.由于gps卫星定位信号会受到大气电离层变化、云层遮挡、天气潮湿情况以及周边高大建筑物的多径反射等复杂因素的影响，因此通过车载gps进行定位时经常会出现坐标定位点发生位置漂移的现象，其误差可达几十甚至达到几百米。gps漂移可以分为静态漂移和动态漂移。静态漂移是当gps终端静止的时候，其定位坐标会在某个范围内不停的变化，甚至还会显示出速度；由于这种漂移现象大多发生在车辆速度较低时，所以现有的过滤gps漂移点的方式，大多采用速度判断：如果当前点速度为0或者小于某一阈值时就认为该点静止、过滤掉该点。而动态漂移是指在有速度的运动过程中，定位点产生了漂移距离。在将连续定位点作为运行轨迹时，如果有位置漂移点，则反映出来的轨迹数据在地图上将会显示出跳跃的现象，这将对后续基于定位点的数据分析工作造成巨大的误差影响。
3.由于静态偏移有个很明显的特征是，这种漂移现象大多发生在车辆速度较低时，所以现有的过滤gps漂移点的方式，大多采用速度判断：如果当前点速度为0或者小于某一阈值时就认为该点静止、过滤掉该点。这种方法虽然可以过滤掉低速点，但堵车时车实际上还在缓慢行驶，而这些点却全部会被过滤掉。针对动态漂移点问题，现有技术直接通过两点距离超过理论最大距离而进行过滤，没有考虑位置偏移发生的持续时间，以及发生漂移时刻的具体细节，因此会大大增加错误过滤的可能。除此之外，仅通过时间和位置信息就能进行过滤的还有数学计算方法，如卡尔曼滤波和粒子滤波，然而卡尔曼滤波虽然可以过滤属于噪声的位置异常点，但其输出的结果是滤波后估计的新轨迹数据点，对过滤筛选原有数据点的需求并不友好和方便；而粒子滤波计算复杂度较高。做法上较为简便的，还有通过gps信号强度、wifi辅助定位信号强度变化等为依据来进行过滤的方法。

技术实现要素：

4.本发明目的在于针对现有技术的不足，提出一种基于双队列技术的过滤gps位置漂移点的方法及装置，可以高效、准确对静态飘移点和动态漂移点进行过滤。本发明方法通过双队列技术，将原始gps点数据集分成多批次加入到两个预设队列中进行考虑，结合了距离、速度、位移方向等维度，不需要依赖更多信息地实现了对车载gps数据中发生位置漂移的异常定位点进行高效地过滤。
5.本发明的目的是通过以下技术方案来实现的：第一方面，本发明提供了一种基于双队列技术的过滤gps位置漂移点的方法，该方法包括以下步骤：
6.步骤一：数据点提取：获取终端设备在指定连续时间范围内的gps采集点，并提取gps采集点中的时间、经纬度、速度信息形成相应的数据点；
7.步骤二：异常点检验：将数据点中时间重复的点作为异常点去除，剩余数据点作为
有效数据点集；
8.步骤三：漂移点过滤：根据采集时间顺序将检验后的有效数据点集基于漂移点过滤算法，通过对一段段小轨迹的综合考虑来过滤掉整个轨迹中位置发生漂移的点与轨迹，筛选出有效点，从而形成合理的点轨迹；漂移点过滤算法具体过程如下：
9.步骤1：进行算法的初始化工作：创建两个容量大小分别为c1和c2的列表tl1和tl2，作为未发生位置漂移时和出现位置漂移点后存储暂时有效点的缓存队列，以及创建一个不固定长度的永久有效点队列fl，作为存储过滤后永久有效点的答案结果队列；此外，初始化创建两个权重点w1和w2为null值，在过滤批次中随着点传入，用来代表未发生位置漂移时点轨迹和发生位置漂移后点轨迹的最新位置和行驶方向；
10.步骤2：正式执行算法的过滤过程：对具有n个gps数据点的点集{p1，p2，...，pn}进行逐个判断、逐批过滤，当tl1和tl2均没有元素时，开启新一轮的过滤批次；对于首个点p1执行步骤3，对于非首个点pi(即i∈[2，n])执行步骤4，当n个点全部都已完成判断后，执行步骤20；
[0011]
步骤3：对首个gps点作假设性处理：直接将gps点中的首个点p1作为暂时有效点，加入未发生漂移时的暂时有效点缓存队列tl1中，并且p1的值直接赋值给权重点w1，然后回到步骤2执行下一个点p
i+1
的过滤判断；
[0012]
步骤4：对于非首个点pi，先判断权重点w2是否为null值，如果w2＝＝null则执行步骤5，否则执行步骤10；＝＝表示两者相同判断；
[0013]
步骤5：w2＝＝null表明本次过滤批次中，当前时刻还未出现过位置漂移点，此时由权重点w1来表示tl1中暂时有效点所对应的点轨迹的最新位置和行驶方向；判断当前判断点pi是否漂移，需要计算当前判断点pi与权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤6，否则执行步骤7；
[0014]
步骤6：表示当前判断点pi对于tl1中的暂时有效点所对应的轨迹而言是位置漂移点，在不改变w1的情况下，通过w2代表在出现位置漂移点pi后的点轨迹的位置和行驶方向，具体为：将位置漂移点pi的值直接赋值给权重点w2，并将pi点存入到已经发生了位置漂移后存储暂时有效点的缓存队列tl2中，回到步骤2执行下一个点p
i+1
的过滤判断；
[0015]
步骤7：表明pi与权重点w1的位移距离在理论允许距离之内，将pi加入到tl1中，并通过权重点前一时刻的值与新传入的gps点根据一定权重比例关系更新位置值，并将pi的时间值、速度值赋值给w1的时间值、速度值，然后执行步骤8；
[0016]
步骤8：判断tl1中的元素个数是否已经达到c1，如果len(tl1)≥c1，则执行步骤9，如果len(tl1)《c1则直接回到步骤2执行下一个点p
i+1
的过滤判断；
[0017]
步骤9：由于len(tl1)≥c1已经达到了预设数量阈值，将tl1中的暂时有效点全部计为永久有效点加到永久有效点队列fl中，并清空tl1，完成当前过滤批次的点过滤过程；回到步骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断；
[0018]
步骤10：w2≠null表明本次过滤批次g中已经出现了位置漂移点，此时w2代表了tl2中暂时有效点即位置漂移点出现后的点轨迹的最新位置和行驶方向，计算当前判断点pi与
w2的距离时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤11，否则执行步骤18；
[0019]
步骤11：如果有则让当前判断点pi依次与代表tl1轨迹位置和方向的权重点w1和fl中的最后一个永久有效点进行校验判断；先执行步骤12，与权重点w1进行校验判断；
[0020]
步骤12：计算当前判断点pi与能代表tl1中暂时有效点所对应轨迹的位置和行驶方向的权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果是的情况则执行步骤13，如果将pi点加入到tl1中，并对权重点w1的位置值进行更新，并将pi的时间值、速度值赋值给w1的时间值、速度值，接着执行步骤8判断tl1中点的数量是否已经满足条件；
[0021]
步骤13：由于将当前判断点pi与永久有效点队列fl进行校验判断。首先检测fl中是否有元素，如果fl有元素则执行步骤14，否则执行步骤17；
[0022]
步骤14：计算当前判断点pi与fl中的最后一个有效点p
last
的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果内，则执行步骤15，否则执行步骤16；
[0023]
步骤15：如果则清空tl1和tl2中所有的暂时有效点，重新从当前判断点pi开始过滤考虑，设置w2＝null，将当前判断点pi的值赋值给w1，并将pi点存入缓存队列tl1；回到步骤2，带着当前判断点pi的信息开始新一批次的过滤，对下一个点p
i+1
进行过滤判断；
[0024]
步骤16：如果则在不处理tl1的情况下清空tl2，将pi的值赋值给权重点w2，并将pi点存入缓存队列tl2，把pi作为新的位移漂移轨迹起始点处理，用tl2记录后续轨迹；回到步骤2，执行下一个点p
i+1
的过滤判断；
[0025]
步骤17：由于永久有效点队列fl中暂时还没有数据，无法通过fl中的点进行判断，因此直接清空和tl1和tl2，设置w2＝null，将当前判断点pi的值赋值给w1，并将pi点存入缓存队列tl1；回到步骤2，带着当前判断点pi的信息开始新一批次的过滤考虑，对下一个点p
i+1
进行过滤判断；
[0026]
步骤18：此时将pi点加入暂时有效点缓存队列tl2中，并对w2的位置值和用pi的时间值、速度值赋值给w2的时间值、速度值进行更新；在tl2加入pi点后，判断tl2是否达到了预设数量阈值c2，如果len(tl2)≥c2，则执行步骤19，否则直接回到步骤2，执行下一个点p
i+1
的过滤判断；
[0027]
步骤19：如果有len(tl2)≥c2，判断tl1中元素个数是否已经达到宽松数量阈值kc*c1，如果len(tl1)≥kc*c1则满足条件，先把暂时有效点队列tl1中的点加入到永久有效点队列fl后清空tl1；否则直接舍弃掉tl1中所有的点；在处理完tl1中的点后，再把tl2中的点加入到永久有效点队列fl中并清空tl2，之后将w2的值赋值给w1并设置w2为null值，完成当前过滤批次的点过滤过程；接着重新回到步骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断：
[0028]
步骤20：当n个点全部进行过滤判断完后，此时缓存队列tl1和tl2中还有暂时有效
点，对tl1和tl2剩余点做数量判断，由于tl2肯定无法满足数量要求c2，因此只需要计算tl1数量是否达到宽松数量阈值kc*c1，如果满足则将tl1中的暂时有效点也计为永久有效点加入到永久有效点队列fl中，否则直接舍弃；最终得到永久有效点队列fl中的点集为真正有效的点。
[0029]
进一步地，步骤二中，还将采集时间相邻且位移在距离阈值内的点全部用一个点或者两个点代替，其他点作为异常点去除。
[0030]
进一步地，步骤5中，δd
max
最大允许移动距离计算如下：
[0031]
δd
max
＝v
max
*δt
[0032]
其中为计算过程中两个采样点的时间间隔；v
max
是预设的最大限制速度或者取两点速度最大值。
[0033]
进一步地，所述预设的最大限制速度，即依据道路限速、车辆类型的最大速度；所述取两点速度最大值，即设置为max(v
wj
，v
pi
)，根据最大的行驶车速计算最大允许移动距离。
[0034]
进一步地，步骤7、步骤12、步骤18中：位置值更新公式如下：
[0035]
wj＝(1+k
p
)*p
i-k
p
*wj，j∈(1，2)
[0036]
权重点wj是p
i-1
与pi延长线上一点，k
p
是延长比例参数，延长距离为
[0037]
第二方面，本发明提供了一种基于双队列技术的过滤gps位置漂移点的装置，包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现所述的基于双队列技术的过滤gps位置漂移点的方法。
[0038]
第三方面，本发明提供了一种计算机可读存储介质，其上存储有程序，所述程序被处理器执行时，实现所述的基于双队列技术的过滤gps位置漂移点的方法。
[0039]
本发明的有益效果：本发明吗提供了一种o(n)计算复杂度的易于计算且易于代码复现的位置异常点过滤算法；算法中权重点的计算反映了行驶的惯性，能更准确地识别出位置偏移异常点，拥有更好的过滤率；此外，相比于大多数点过滤算法只能过滤个别点，本发明算法既能过滤个别点，也能过滤一整段偏移轨迹，在保留点原始信息的前提下拥有较好的过滤效果。
附图说明
[0040]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图做简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动前提下，还可以根据这些附图获得其他附图。
[0041]
图1为本发明提供的基于双队列技术的过滤gps位置漂移点的方法的流程图；
[0042]
图2为本发明实施例提供的过滤gps漂移点执行过程示意图；
[0043]
图3为本发明在实际路网数据和gps数据下的过滤效果对比图，其中图3中的(a)为原始的gps数据点展示图，图3中的(b)为gps数据点经过过滤后的过滤效果展示图；
[0044]
图4为本发明提供的基于双队列技术的过滤gps位置漂移点的装置的结构图。
具体实施方式
[0045]
下面将结合附图对本发明作进一步地详细描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0046]
如图1所示，本发明提供的一种基于双队列技术的过滤gps位置漂移点的方法，具体步骤如下：
[0047]
步骤一：数据点提取：获取终端设备在指定连续时间范围内的gps采集点，并提取gps采集点中的时间、经纬度、速度等信息形成相应的数据点。
[0048]
步骤二：异常点检验：将数据点中时间重复的点作为异常点去除，可选的还可以将采集时间相邻且位移距离特别近的点全部用一个点或者两个点代替，其他距离相近的点作为异常点去除；
[0049]
步骤三：漂移点过滤：根据采集时间顺序将检验后的有效数据点集输入到漂移点过滤算法中，通过对一段段小轨迹的综合考虑来过滤掉整个轨迹中位置发生漂移的点与轨迹、筛选出有效点，从而形成合理的点轨迹。具体过程如下：
[0050]
步骤1：进行算法的初始化工作：创建两个容量大小分别为c1和c2的列表tl1和tl2，作为未发生位置漂移时和出现位置漂移点后存储暂时有效点的缓存队列，以及创建一个不固定长度的永久有效点队列fl，作为存储过滤后永久有效点的答案结果队列。c1、c2是预设的配置参数，根据经验c2可设置为16(c2＝16的含义是得在位置漂移点出现后，有15个合理的暂时有效点，这段轨迹点认为是有效的)，c1可设置为8；此外，初始化创建两个权重点变量w1和w2为null值，在过滤批次中随着点传入，用来代表未发生位置漂移时点轨迹和发生位置漂移后点轨迹的最新位置和行驶方向。
[0051]
步骤2：正式执行算法的过滤过程：对具有n个gps数据点的点集{p1，p2，...，pn}进行逐个判断、逐批过滤，当tl1和tl2都没有元素时，意味着开启了新一轮的过滤批次。对于首个点p1执行步骤3，对于非首个点pi(即i∈[2，n])执行步骤4，当n个点全部都已完成判断后，执行步骤20。
[0052]
步骤3：算法会对首个gps点作假设性处理——直接将gps点中的首个点p1作为暂时有效点，加入未发生漂移时的暂时有效点缓存队列tl1中，并p1的值直接赋值给权重点w1，然后回到步骤2执行下一个点p
i+1
的过滤判断。
[0053]
步骤4：对于非首个点pi，先判断权重点w2是否为null值，如果w2＝＝null则执行步骤5，否则执行步骤10，＝＝表示两者相同判断。
[0054]
步骤5：w2＝＝null表明本次过滤批次g中，当前时刻还未出现过位置漂移点，此时由权重点w1来表示tl1中暂时有效点所对应的点轨迹的最新位置和行驶方向。判断当前判断点pi是否漂移，需要计算当前判断点pi与权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤6，否则执行步骤7。δd
max
最大允许移动距离：δd
max
＝v
max
*δt，其中为计算过程中两个采样点的时间间隔；v
max
可以是预设的最大限制速度或者取两点速度最大值；
[0055]
所述预设的最大限制速度，即依据道路限速、车辆类型的最大速度，假设车辆最大合理速度δd
max
为80km/h(22m/s)、定位时间间隔δt为2s来算，则下一个定位点与权重点的
距离大于相差44m就会被当作为偏移点。由于gps点可能会出现在有一段时间没有成功获取定位点的情况，所以需要计算的是两点间隔时间来计算两点的最大允许偏移点范围。
[0056]
所述取两点速度最大值，即设置为根据最大的行驶车速计算最大允许移动距离，pi的速度为10m/s，w1的速度为11m/s，那么即使以11m/s的速度行驶，在两者时间差δt＝2m/s的情况下，δd
max
＝max(10，11)*2＝22m。
[0057]
步骤6：意味着当前判断点pi对于tl1中的暂时有效点所对应的轨迹而言是位置漂移点，但由于无法直接判断tl1中的点都是无效的漂移轨迹，还是当前判断点pi或者pi之后的一段轨迹是漂移轨迹，因此在不改变w1的情况下，启用w2代表在出现位置漂移点pi后的点轨迹的位置和行驶方向：将位置漂移点pi的值直接赋值给权重点w2，并将pi点存入到已经发生了位置漂移后存储暂时有效点的缓存队列tl2中，回到步骤2执行下一个点p
i+1
的过滤判断。
[0058]
步骤7：表明pi与权重点w1的位移距离在理论允许距离之内，所以认为当前判断点pi是未发生漂移的合理点，因此将pi加入到tl1中，并通过权重点前一时刻的值与新传入的gps点根据一定权重比例关系更新位置值，即通过更新公式w1＝(1+k
p
)*p
i-k
p
*w1对权重点w1的位置值和将pi的时间值、速度值赋值给w1的时间值、速度值进行更新，然后执行步骤8。权重点w1是p
i-1
与pi延长线上一点，k
p
是延长比例参数，根据经验可设置为k
p
＝0.05，延长距离为权重点更新具有权重比例关系是为了权衡兼顾前后暂时有效点之间的位置和移动方向的关系，后续点在移动方向上出现的可能性更大，能一定程度上抵消掉gps信号本身可能有的精度上的误差(调头的话这个假设就是错误的，但是由于调头时速度小，那么采样时间内的移动距离就小，再加上k
p
的值本身就比较小，所以在这种情况下也不会造成负面影响)。
[0059]
步骤8：判断tl1中的元素个数是否已经达到c1，如果len(tl1)≥c1，则执行步骤9，如果len(tl1)《c1则意味着tl1中点数量还不足够形成一段有效的轨迹，所以直接回到步骤2执行下一个点p
i+1
的过滤判断。
[0060]
步骤9：由于len(tl1)≥c1已经达到了预设数量阈值，所以认为tl1中的暂时有效点全部是合理的，将其全部计为永久有效点加到永久有效点队列fl中，并清空tl1，完成了当前过滤批次g的点过滤过程。回到步骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断。
[0061]
步骤10：w2≠null表明本次过滤批次g中已经出现了位置漂移点，此时w2代表了tl2中暂时有效点即位置漂移点出现后的点轨迹的最新位置和行驶方向，所以计算当前判断点pi与w2的距离时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤11，否则执行步骤18。
[0062]
步骤11：如果有表明当前判断点pi对于tl2中暂时有效点所对应的发生过位置突变的点轨迹而言又是位置漂移点，此时需要让当前判断点pi依次与代表tl1轨迹位置和方向的权重点w1和fl中的最后一个永久有效点进行校验判断。先执行步骤12，与权重点w1进行校验判断。
[0063]
步骤12：计算当前判断点pi与能代表tl1中暂时有效点所对应轨迹的位置和行驶方向的权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的
最大允许移动距离δd
max
，如果是的情况则执行步骤13，如果则表明当前判断点pi对于tl1对应的轨迹而言未发生偏移，仍然是有效的，因此将pi点加入到tl1中，并根据更新公式w1＝(1+k
p
)*p
i-k
p
*w1对权重点w1的位置值进行更新，并将pi的时间值、速度值赋值给w1的时间值、速度值，接着执行步骤8判断tl1中点的数量是否已经满足条件。
[0064]
步骤13：由于表明当前判断点pi对于tl1中暂时有效点所对应的轨迹而言也是漂移点，接着继续将当前判断点pi与永久有效点队列fl进行校验判断。首先检测fl中是否有元素，如果fl有元素则执行步骤14，否则执行步骤17。
[0065]
步骤14：计算当前判断点pi与fl中的最后一个有效点p
last
的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果内，则执行步骤15，否则执行步骤16。
[0066]
步骤15：表示虽然当前判断点pi对于tl1和tl2中的点所对应的轨迹而言都是漂移点，但是对于已计为永久有效点的轨迹而言是未发生偏移的，因此直接清空tl1和tl2中所有的暂时有效点，重新从当前判断点pi开始过滤考虑，设置w2＝null，将当前判断点pi的值赋值给w1，并将pi点存入缓存队列tl1。回到步骤2，带着当前判断点pi的信息开始新一批次的过滤，对下一个点p
i+1
进行过滤判断。
[0067]
步骤16：表明pi对于tl1、tl2、fl对应的轨迹而言都发生了位置漂移，此时在不处理tl1的情况下清空tl2，将pi的值赋值给权重点w2，并将pi点存入缓存队列tl2，把pi作为新的位移漂移轨迹起始点处理，用tl2记录后续轨迹。回到步骤2，执行下一个点p
i+1
的过滤判断。
[0068]
步骤17：由于永久有效点队列fl中暂时还没有数据，无法通过fl中的点进行判断，因此直接清空和tl1和tl2，设置w2＝null，将当前判断点pi的值赋值给w1，并将pi点存入缓存队列tl1。回到步骤2，带着当前判断点pi的信息开始新一批次的过滤考虑，对下一个点p
i+1
进行过滤判断。
[0069]
步骤18：此时将pi点加入暂时有效点缓存队列tl2中，并根据更新公式w2＝(1+k
p
)*p
i-k
p
*w2对w2的位置值和用pi的时间值、速度值赋值给w2的时间值、速度值进行更新。在tl2加入pi点后，判断tl2是否达到了预设数量阈值c2，如果len(tl2)≥c2，则执行步骤19，否则直接回到步骤2，执行下一个点p
i+1
的过滤判断。
[0070]
步骤19：如果有len(tl2)≥c2意味着虽然发生了位置漂移，但后续tl2中的暂时有效点都是连续而稳定的，即后续轨迹都是合规的，因此反而需要判断位置突变前的点是否能够构成一段有效轨迹：判断tl1中元素个数是否已经达到宽松数量阈值kc*c1，kc设置为含义是在tl2元素个数已满时综合考虑是否需要加上tl1中的点)，如果len(tl1)≥kc*c1则满足条件，先把暂时有效点队列tl1中的点加入到永久有效点队列fl后清空tl1；否则由于tl1中点数量不够，所以认为其对应的轨迹是漂移轨迹，直接舍弃掉tl1中所有的点。在处理完tl1中的点后，再把tl2中的点加入到永久有效点队列fl中并清空tl2，之后将w2的值赋值给w1并设置w2为null值，完成了当前过滤批次g的点过滤过程。接着重新回到步骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断。
[0071]
步骤20：当n个点全部进行过滤判断完后，此时缓存队列tl1和tl2中还有暂时有效
点，为了尽可能多地保留点的信息，因此对tl1和tl2剩余点做数量判断，由于tl2肯定无法满足数量要求c2，因此只需要计算tl1数量是否达到宽松数量阈值kc*c1，如果满足则将tl1中的暂时有效点也计为永久有效点加入到永久有效点队列fl中，否则直接舍弃。最终得到永久有效点队列fl中的点集就是真正有效的点。
[0072]
本发明提出的过滤方法需要将点按照多个批次加入到预设队列，对点进行检验之后，才能确认这一批的点哪些部分是真实有效点，并输出到永久有效点队列中。在未加入到fl中的点全都是暂时有效点，被加入到fl中的点才是最终的真实有效点。当每次将暂时有效点队列tlj中的数据点加入到永久有效点队列fl后认为是这批点过滤的结束，当新输入下一个点时便进入了下一批点的过滤，对一批点进行过滤遍历的过程中，权重点同一时刻只有一个有效，要么w1有效，要么w2有效，它们代表的是在一段轨迹被判定暂时有效后的稳定位置点，也代表了从p
i-1
到pi的惯性方向的位置点。当发生位置漂移点后，启用w2其值不再为null，当当前过滤批次没有出现位置漂移点时，一直使用权重点w1代表轨迹的最新位置和行驶方向。判断点pi与权重点产生大的距离偏移值则会被判定为临时偏移点，如果这个临时偏移点之后的若干个点都没有再发生偏移，则说明pi后的这段轨迹有效，则将这些点全部加入到fl中作为最终有效轨迹点中并更新w1权重点为最后的点pi，反之当权重点代表的轨迹点数比较少且又发生了偏移，表明该段点轨迹不满足永久有效点的数量要求，则统一被认为是偏移点轨迹，需要被过滤掉。
[0073]
实施例：如图2所示，为本发明实施例提供的过滤gps漂移点执行过程示意图，本发明实施例具体过程如下：
[0074]
1.收集gps点数据，从中提取时间、经纬度、速度信息后输入到算法中，预设算法中使用到的配置参数为c1＝8、c2＝16、k
p
＝0.05。
[0075]
2.对于首个点p1，直接将p1作为暂时有效点，将其值赋值给w1，并将p1加入到未发生漂移时记录暂时有效点的队列tl1中。【p1判断结束，继续对p2进行过滤判断】
[0076]
3.p2执行判断过程：由于w2＝＝null，因此计算的是未发生漂移时的权重点w1和p2之间的关系。得到两者的距离差δd
w1～p2
、时间差δt以及对应的最大允许移动距离δd
max
。因为所以p2被认为未发生偏移，作为暂时有效点加入到暂时有效点队列tl1中，将p2的时间值和速度值直接赋值给w1，同时根据公式对w1的位置值进行更新。【p2判断结束，继续对p3进行过滤判断】
[0077]
4.p3执行判断过程：同样的对p3进行过滤判断后，由于将p3作为暂时有效点加入到暂时有效点队列tl1中，同时根据p3和原w1的值更新w1的位置、时间、速度值。【p3判断结束，继续对p4进行过滤判断】
[0078]
5.p4执行判断过程：由于w2＝＝null，因此p4计算的还是与w1之间的关系。得到两者的距离差时间差δt以及对应的最大允许移动距离δd
max
。由于有所以p4对于暂时有效点队列tl1中的点而言是漂移点，此时启用w2，将p4的值全部赋值给w2，并将p4加入到出现位置漂移点后记录暂时有效点的队列tl2中。【p3判断结束，继续对p4进行过滤判断】
[0079]
6.p5执行判断过程：由于w2≠null，因此p5计算的是与w2之间的关系。得到两者的距离差时间差δt以及对应的最大允许移动距离δd
max
。因为所
以p5对于暂时有效点队列tl2中的点而言也是偏移点，此时考虑到pi可能是临时漂移点，因此先与tl1中的点进行校验：计算当前定位点p5与代表tl1对应点轨迹的权重点w1的距离差时间差δt以及对应的最大允许移动距离δd
max
，因为所以p5对于暂时有效点队列tl1中的暂时有效点而言也是偏移点。于是再与永久有效点队列fl进行校验，但由于此时fl为空，因此可以直接判定pi为又一新的漂移点。清空tl1和tl2、取代p4，将p5设置为新的漂移点即p5的值赋值给w2。【p4判断结束，继续对p5进行过滤判断】
[0080]
7.p6执行判断过程：此时w2≠null，因此计算p6与w2之间的关系。得到两者的距离差时间差δt以及对应的最大允许移动距离δd
max
。因为所以直接将p6作为暂时有效点加入到暂时有效点队列tl2中。【p6判断结束，继续对p7进行过滤判断】
[0081]
8.继续对p7、p8、p9、p
10
、p
11
、p
12
、p
13
、p
14
、p
15
、p
16
、p
17
、p
18
、p
19
、p
20
进行过滤计算后都没有发生漂移，于是都被加入到暂时有效点队列tl2中，当p
20
加入时，有len(tl2)＝＝c2＝＝16，于是将tl2中的点全部作为永久有效点加入到永久有效点队列fl中，再清空tl2，设置w2＝null，完成当前批次的过滤。【p
20
判断结束，继续对p
21
进行过滤判断】
[0082]
9.p
21
开启新一批的过滤，此时由于w2重设为null，因此计算的是与w1之间的关系，得到两者的距离差时间差δt以及对应的最大允许移动距离δd
max
。因为。因为所以将p
21
作为暂时有效点加入到也已经重设清空的暂时有效点队列tl1中。【p
21
判断结束，继续对p
22
进行过滤判断】
[0083]
10.p
21
作为最后一个点，p
21
判断结束后所有的点都已经判断过了，最后做收尾处理，判断len(tl1)＝1小于kc*1＝6，由于当前tl1数量不足以构成小段的有效轨迹因此直接舍弃tl1中点p
21
，完成整个的过滤过程。
[0084]
11.最终完成整个过滤后，答案队列fl中有点p5、p6、p7、p8、p9、p
10
、p
11
、p
12
、p
13
、p
14
、p
15
、p
16
、p
17
、p
18
、p
19
、p
20
为过滤后输出的有效点，其余被判为无效点。
[0085]
过滤效果对比图说明：如图3中的(a)所示，车辆真实有效的行驶轨迹为从
①
处开始由南至北经过高架桥达到
②
处的一段点轨迹，但在轨迹的开始处
①
，由于接近路口红绿灯车辆正在低速甚至停止移动，于是gps定位发生了偏移，被错位地定位在了图片右侧的
③
处。由于停车时间较长，因此在
③
点处实际上有较多的定位异常点。如果考虑到过滤后续的应用需求对点除经纬度以外的信息都不关注，那么可以再前接一个合并重合点的过滤器，从而可以将这些经纬度非常接近甚至重合的点简单近似地认为是一个点处理(如果是要保留时间、加速度信息，可以认为是始末两个点)。将处理过重合点的点轨迹输入到双队列过滤算法，可以看到在结合后续点的信息后，
③
处地位置偏移点已被过滤掉，过滤后的点轨迹结果如图3中的(b)所示。
[0086]
如果gps坐标点的后续用途中，对相同位置的点信息不敏感，则可以直接将距离特别近的多个点用一个点进行代替，从而减少异常点一次性出现太多次并都在相同位置附近而被认为有效点轨迹的可能。
[0087]
与前述基于双队列技术的过滤gps位置漂移点的方法的实施例相对应，本发明还提供了基于双队列技术的过滤gps位置漂移点的装置的实施例。
[0088]
参见图4，本发明实施例提供的一种基于双队列技术的过滤gps位置漂移点的装
置，包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，用于实现上述实施例中的基于双队列技术的过滤gps位置漂移点的方法。
[0089]
本发明基于双队列技术的过滤gps位置漂移点的装置的实施例可以应用在任意具备数据处理能力的设备上，该任意具备数据处理能力的设备可以为诸如计算机等设备或装置。装置实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在任意具备数据处理能力的设备的处理器将非易失性存储器中对应的计算机程序指令读取到内存中运行形成的。从硬件层面而言，如图4所示，为本发明基于双队列技术的过滤gps位置漂移点的装置所在任意具备数据处理能力的设备的一种硬件结构图，除了图4所示的处理器、内存、网络接口、以及非易失性存储器之外，实施例中装置所在的任意具备数据处理能力的设备通常根据该任意具备数据处理能力的设备的实际功能，还可以包括其他硬件，对此不再赘述。
[0090]
上述装置中各个单元的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。
[0091]
对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本发明方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
[0092]
本发明实施例还提供一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，实现上述实施例中的基于双队列技术的过滤gps位置漂移点的方法。
[0093]
所述计算机可读存储介质可以是前述任一实施例所述的任意具备数据处理能力的设备的内部存储单元，例如硬盘或内存。所述计算机可读存储介质也可以是任意具备数据处理能力的设备的外部存储设备，例如所述设备上配备的插接式硬盘、智能存储卡(smart media card，smc)、sd卡、闪存卡(flash card)等。进一步的，所述计算机可读存储介质还可以既包括任意具备数据处理能力的设备的内部存储单元也包括外部存储设备。所述计算机可读存储介质用于存储所述计算机程序以及所述任意具备数据处理能力的设备所需的其他程序和数据，还可以用于暂时地存储已经输出或者将要输出的数据。
[0094]
上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。

技术特征：

1.一种基于双队列技术的过滤gps位置漂移点的方法，其特征在于，该方法包括以下步骤：步骤一：数据点提取：获取终端设备在指定连续时间范围内的gps采集点，并提取gps采集点中的时间、经纬度、速度信息形成相应的数据点；步骤二：异常点检验：将数据点中时间重复的点作为异常点去除，剩余数据点作为有效数据点集；步骤三：漂移点过滤：根据采集时间顺序将检验后的有效数据点集基于漂移点过滤算法，通过对一段段小轨迹的综合考虑来过滤掉整个轨迹中位置发生漂移的点与轨迹，筛选出有效点，从而形成合理的点轨迹；漂移点过滤算法具体过程如下：步骤1：进行算法的初始化工作：创建两个容量大小分别为c1和c2的列表tl1和tl2，作为未发生位置漂移时和出现位置漂移点后存储暂时有效点的缓存队列，以及创建一个不固定长度的永久有效点队列fl，作为存储过滤后永久有效点的答案结果队列；此外，初始化创建两个权重点w1和w2为null值，在过滤批次中随着点传入，用来代表未发生位置漂移时点轨迹和发生位置漂移后点轨迹的最新位置和行驶方向；步骤2：正式执行算法的过滤过程：对具有n个gps数据点的点集{p1,p2,...,p
n
}进行逐个判断、逐批过滤，当tl1和tl2均没有元素时，开启新一轮的过滤批次；对于首个点p1执行步骤3，对于非首个点p
i
(即i∈[2,n])执行步骤4，当n个点全部都已完成判断后，执行步骤20；步骤3：对首个gps点作假设性处理：直接将gps点中的首个点p1作为暂时有效点，加入未发生漂移时的暂时有效点缓存队列tl1中，并且p1的值直接赋值给权重点w1，然后回到步骤2执行下一个点p
i+1
的过滤判断；步骤4：对于非首个点p
i
，先判断权重点w2是否为null值，如果w2＝＝null则执行步骤5，否则执行步骤10；＝＝表示两者相同判断；步骤5：w2＝＝null表明本次过滤批次中，当前时刻还未出现过位置漂移点，此时由权重点w1来表示tl1中暂时有效点所对应的点轨迹的最新位置和行驶方向；判断当前判断点p
i
是否漂移，需要计算当前判断点p
i
与权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤6，否则执行步骤7；步骤6：表示当前判断点p
i
对于tl1中的暂时有效点所对应的轨迹而言是位置漂移点，在不改变w1的情况下，通过w2代表在出现位置漂移点p
i
后的点轨迹的位置和行驶方向，具体为：将位置漂移点p
i
的值直接赋值给权重点w2，并将p
i
点存入到已经发生了位置漂移后存储暂时有效点的缓存队列tl2中，回到步骤2执行下一个点p
i+1
的过滤判断；步骤7：表明p
i
与权重点w1的位移距离在理论允许距离之内，将p
i
加入到tl1中，并通过权重点前一时刻的值与新传入的gps点根据一定权重比例关系更新位置值，并将p
i
的时间值、速度值赋值给w1的时间值、速度值，然后执行步骤8；步骤8：判断tl1中的元素个数是否已经达到c1，如果len(tl1)≥c1，则执行步骤9，如果len(tl1)＜c1则直接回到步骤2执行下一个点p
i+1
的过滤判断；步骤9：由于len(tl1)≥c1已经达到了预设数量阈值，将tl1中的暂时有效点全部计为永久有效点加到永久有效点队列fl中，并清空tl1，完成当前过滤批次的点过滤过程；回到步
骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断；步骤10：w2≠null表明本次过滤批次g中已经出现了位置漂移点，此时w2代表了tl2中暂时有效点即位置漂移点出现后的点轨迹的最新位置和行驶方向，计算当前判断点p
i
与w2的距离时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果执行步骤11，否则执行步骤18；步骤11：如果有则让当前判断点p
i
依次与代表tl1轨迹位置和方向的权重点w1和fl中的最后一个永久有效点进行校验判断；先执行步骤12，与权重点w1进行校验判断；步骤12：计算当前判断点p
i
与能代表tl1中暂时有效点所对应轨迹的位置和行驶方向的权重点w1的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果是的情况则执行步骤13，如果将p
i
点加入到tl1中，并对权重点w1的位置值进行更新，并将p
i
的时间值、速度值赋值给w1的时间值、速度值，接着执行步骤8判断tl1中点的数量是否已经满足条件；步骤13：由于将当前判断点p
i
与永久有效点队列fl进行校验判断。首先检测fl中是否有元素，如果fl有元素则执行步骤14，否则执行步骤17；步骤14：计算当前判断点p
i
与fl中的最后一个有效点p
last
的距离差时间差以及结合最大速度v
max
得到时间内的最大允许移动距离δd
max
，如果内，则执行步骤15，否则执行步骤16；步骤15：如果则清空tl1和tl2中所有的暂时有效点，重新从当前判断点p
i
开始过滤考虑，设置w2＝null，将当前判断点p
i
的值赋值给w1，并将p
i
点存入缓存队列tl1；回到步骤2，带着当前判断点p
i
的信息开始新一批次的过滤，对下一个点p
i+1
进行过滤判断；步骤16：如果则在不处理tl1的情况下清空tl2，将p
i
的值赋值给权重点w2，并将p
i
点存入缓存队列tl2，把p
i
作为新的位移漂移轨迹起始点处理，用tl2记录后续轨迹；回到步骤2，执行下一个点p
i+1
的过滤判断；步骤17：由于永久有效点队列fl中暂时还没有数据，无法通过fl中的点进行判断，因此直接清空和tl1和tl2，设置w2＝null，将当前判断点p
i
的值赋值给w1，并将p
i
点存入缓存队列tl1；回到步骤2，带着当前判断点p
i
的信息开始新一批次的过滤考虑，对下一个点p
i+1
进行过滤判断；步骤18：此时将p
i
点加入暂时有效点缓存队列tl2中，并对w2的位置值和用p
i
的时间值、速度值赋值给w2的时间值、速度值进行更新；在tl2加入p
i
点后，判断tl2是否达到了预设数量阈值c2，如果len(tl2)≥c2，则执行步骤19，否则直接回到步骤2，执行下一个点p
i+1
的过滤判断；步骤19：如果有len(tl2)≥c2，判断tl1中元素个数是否已经达到宽松数量阈值k
c
*c1，如果len(tl1)≥k
c
*c1则满足条件，先把暂时有效点队列tl1中的点加入到永久有效点队列fl后清空tl1；否则直接舍弃掉tl1中所有的点；在处理完tl1中的点后，再把tl2中的点加入到
永久有效点队列fl中并清空tl2，之后将w2的值赋值给w1并设置w2为null值，完成当前过滤批次的点过滤过程；接着重新回到步骤2开启新一批次的过滤，对下一个点p
i+1
进行过滤判断；步骤20：当n个点全部进行过滤判断完后，此时缓存队列tl1和tl2中还有暂时有效点，对tl1和tl2剩余点做数量判断，由于tl2肯定无法满足数量要求c2，因此只需要计算tl1数量是否达到宽松数量阈值k
x
*c1，如果满足则将tl1中的暂时有效点也计为永久有效点加入到永久有效点队列fl中，否则直接舍弃；最终得到永久有效点队列fl中的点集为真正有效的点。2.根据权利要求1所述的一种基于双队列技术的过滤gps位置漂移点的方法，其特征在于，步骤二中，还将采集时间相邻且位移在距离阈值内的点全部用一个点或者两个点代替，其他点作为异常点去除。3.根据权利要求1所述的一种基于双队列技术的过滤gps位置漂移点的方法，其特征在于，步骤5中，δd
max
最大允许移动距离计算如下：δd
max
＝v
max
*δt其中为计算过程中两个采样点的时间间隔；v
max
是预设的最大限制速度或者取两点速度最大值。4.根据权利要求3所述的一种基于双队列技术的过滤gps位置漂移点的方法，其特征在于，所述预设的最大限制速度，即依据道路限速、车辆类型的最大速度；所述取两点速度最大值，即设置为根据最大的行驶车速计算最大允许移动距离。5.根据权利要求1所述的一种基于双队列技术的过滤gps位置漂移点的方法，其特征在于，步骤7、步骤12、步骤18中：位置值更新公式如下：w
j
＝(1+k
p
)*p
i-k
p
*w
j
，j∈(1,2)权重点w
j
是p
i-1
与p
i
延长线上一点，k
p
是延长比例参数，延长距离为6.一种基于双队列技术的过滤gps位置漂移点的装置，包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，其特征在于，所述处理器执行所述可执行代码时，实现如权利要求1-5中任一项所述的基于双队列技术的过滤gps位置漂移点的方法。7.一种计算机可读存储介质，其上存储有程序，其特征在于，所述程序被处理器执行时，实现如权利要求1-5中任一项所述的基于双队列技术的过滤gps位置漂移点的方法。

技术总结

本发明公开了一种基于双队列技术的过滤GPS位置漂移点的方法及装置，该方法包括以下步骤：步骤一：数据点提取：获取终端设备在指定连续时间范围内的GPS采集点，并提取GPS采集点中的时间、经纬度、速度信息形成相应的数据点；步骤二：异常点检验：将数据点中时间重复的点作为异常点去除，剩余数据点作为有效数据点集；步骤三：漂移点过滤：根据采集时间顺序将检验后的有效数据点集基于漂移点过滤算法，通过对一段段小轨迹的综合考虑来过滤掉整个轨迹中位置发生漂移的点与轨迹，筛选出有效点，从而形成合理的点轨迹。而形成合理的点轨迹。而形成合理的点轨迹。

技术研发人员：

陈力 张子健 王备 陈奇

受保护的技术使用者：

浙江大学

技术研发日：

2023.01.03

技术公布日：

2023/3/10