一种基于双速度特征的轨迹划分方法
时间：2022-11-15 14:00:05 来源：柠檬阅读网 本文已影响 人 
祝 贺，于子兴
(南京邮电大学 计算机学院，江苏 南京 210023)
随着便携式传感设备被广泛应用在人们的日常生活中，由此产生了携带重要位置信息的轨迹数据，例如人类生活的行为轨迹数据、自然环境记录数据等，刻画了目标对象在时空环境下的个体行为。
轨迹压缩即使用更少存储空间的数据信息来代表原始的轨迹时空信息。现有的轨迹压缩方法一般根据轨迹点的位置信息(经、纬度和偏离角度)来筛选和保留具有显著特征的轨迹点，然而这些方法都没有考虑从节点的移动特征角度出发来对轨迹进行划分，划分结果有一定的局限性。
因此，笔者考虑节点的双速度特征(速度和加速度)，并将这些特征结合起来，从而实现对轨迹的有效划分。
提出的划分轨迹的方法主要有如下2个创新点：
(1)基于速度和加速度特征对轨迹进行划分，该方法能够筛选和保留具有显著特征的轨迹点，同时确保划分后的轨迹与原来轨迹的形状相似。
(2)基于节点双速度特征检测来提取停留点的算法，该算法相对其他停留点选择算法不仅能够更准确地提取出停留点，而且具有更低的时间复杂度。
轨迹划分技术类似于较早提出的轨迹压缩技术，但又有所不同，轨迹划分根据轨迹中的关键特征进行划分，而轨迹压缩则是根据某个距离度量进行压缩。目前已有较多工作，比如文献[4]分别介绍了离线压缩方法和在线压缩方法两种轨迹压缩策略。离线轨迹压缩的典型算法有DP算法，DP算法是将原始轨迹用满足特定的垂直欧氏距离的多个轨迹段来近似表示。与离线压缩相比，在线压缩在传输时能立即对每个轨迹进行压缩，例如滑动窗口算法和开放窗口算法。开放窗口算法是一种基于DP算法的启发式方法，该算法的思想是设定空间误差应满足的阈值，然后通过使用越来越多的点来逼近每个轨迹段直到达到空间误差小于约束值的目标。
除了上述两类方法，文献[8]还提出一个有界象限系统BQS的轨迹压缩方法。该方法的优点是能够获得不同的压缩误差界限，快速地得到压缩结果，它以起点为中心建立一个虚拟坐标系，在每个象限中，以由盒跟线形成的凸包限定待评估的点。Liu等人还提出了一次误差界限的轨迹压缩算法OPERB，该算法通过基于拟合函数的局部距离检查方法来维持有向线段近似缓冲点。Lee等人提出了一种基于最小描述长度的轨迹划分方法MDL。此外，文献[11-12]借助于路网结构，把轨迹数据点的序列映射到路网路段上，用两个点构成的边来表示同一条道路上的轨迹点。
2.1 基本概念
首先给出以下几个定义：
定义1 坐标点p
：一个带时间戳的坐标点定义为p
=(Lat,Lngt,T
),其中Lat为纬度，Lngt为经度,T
为时间戳。定义2 轨迹Tra：一条轨迹Tra定义为按时序组成的一组坐标点序，Tra=p
→p
→…→p
，其中p
.T
<p
+1.T
。定义3 停留点SP：一个停留点定义为SP=(Lat,Lngt,T
,T
),表示节点SP在时间T
到达，然后在时间T
离开。2.2 根据速度变化提取特征点
当节点由一种出行方式切换到另外一种出行方式时，它的移动速度会发生很大变化，像其出行方式由步行切换到乘公共汽车，移动速度会增大，由乘坐地铁换成骑自行车，其移动速度会减小。
考虑到出行方式的变化会引起速度的改变，为了检测切换不同出行方式的切换点，将移动速度差定义为Δv
,+1=|v
,+1-v
+1,+2|,其中v
,+1代表节点在轨迹段p
p
+1上的平均速度，如果Δv
,+1大于给定的速度阈值，那么p
+1将被认为是特征点，在这里为了衡量速度的波动，以速度的标准差作为速度变化阈值。速度变化阈值v
表示为：
(1)
2.3 根据加速度变化提取特征点
通常节点在遇到某些特殊事件时，其加速度变化较大，例如路口转弯、等红绿灯、公共汽车或者地铁停靠站台。
为了检测加速度改变的轨迹点，将轨迹上点p
+1的加速度定义为:
t
是轨迹点p
的时间戳，加速度差定义为Δa
,+1=|a
+1-a
|，如果Δa
,+1大于给定的加速度阈值，那么p
+1将被认为是特征点。以加速度的标准差作为加速度变化阈值。加速度变化阈值a
表示为：
(2)
2.4 根据速度和加速度提取停留点
节点经常访问或长期停留的地点可以看作停留点。文献[16-18]中提出了综合空间距离远近和时间间隔多少提取停留点的方法：首先测量起始轨迹点与后继轨迹点之间的距离是否大于设定的距离阈值，然后判断起始轨迹点与最后一个满足条件的轨迹点之间的时间跨度。如果时间跨度大于时间阈值，则以这些轨迹点的平均位置作为停留点。
为了解决选择错误的起始轨迹点，以及无法从存在往返路径的轨迹中确定停留点的问题，文献[19]提出了基于节点移动速度的停留点提取方法SPEMS。
此外，需要注意简单地设置前后搜索到的两点的中间节点作为停留点，而移除两点之间的其他轨迹点，可能会引起轨迹形态发生剧烈变化。如图1所示，其中v
≤v
，v
表示速度变化阈值，因为p
和p
在以p
为圆心，r
为半径的搜索圆之外，则以p
为中心并通过向后和向前搜索分别找到p
和p
，r
表示搜索半径阈值。若判断Δt
(p
,p
)≥δ
，则p
为停留点。同时，注意到节点在靠近停留点前会存在减速行为，在节点将要离开该位置时，节点会明显提高其移动速度，即会存在加速度先减小后增大的变化过程。所以需要在搜索圆中能确定加速度减小或者加速度增大的轨迹点，选择介于这两点的中间轨迹点作为停留点，否则选择介于前后搜索确定的轨迹点之间的平均位置作为停留点，该方法能有效解决所选停留点引起原始轨迹形态发生剧烈变化的问题。据此，在SPEMS算法的基础上引入加速度指标，提出了一种基于双速度特征(速度和加速度)的停留点提取方法SPEDV(stop points extraction method based on the moving speeds and accelerated velocity of nodes)。
图1 原始轨迹形态发生剧烈变化
SPEDV根据以下步骤提取停留点：
步骤1：遍历每组相邻的GPS轨迹点p
、p
+1和p
+2，计算出加速度a
+1和速度v
,+1。步骤2：如果v
,+1≤λ
(λ
表示速度阈值)，则执行以p
+1为中心的向后搜索来提取p
，使得不等式dist(p
+1,p
)≤r
和dist(p
+1,p
)>r
成立，其中r
表示搜索半径阈值，k
=m
+2,m
+3,…,lst。步骤3：执行以p
+1为中心的向前搜索来提取p
，使得不等式dist(p
+1,p
)≤r
和dist(p
+1,p
)>r
成立，其中r
表示搜索半径阈值，k
=i
,i
-1,…,fst。步骤4：如果时间间隔Δt
(p
,p
)≥δ
(δ
表示时间阈值)，令F
=fst，判断a
≥β
,β
是加速度阈值是否成立，若成立，则flag=1；否则判断
a
≥β
是否成立，若成立则令flag1=1，F
=fst+1，终止迭代，否则继续判断a
≥β
是否成立，直到满足fst+n
>m
+1。步骤5：令B
=lst，判断a
≤-β
是否成立，若成立flag2=1，否则判断a
≤-β
是否成立，若成立则令flag2=1和B
=lst-1，否则继续判断a
≤-β
是否成立，直到满足lst-n
<m
+1。步骤6：如果flag1=1或者flag2=1，则移除p
和p
之间所有的点，取中间点p
(+)2作为停留点。否则，以介于p
和p
之间的所有轨迹点的平均位置作为停留点，并移除p
和p
之间所有的点。对于图1中选取的停留点导致原始轨迹形态发生剧烈变化的情况，利用SPEDV算法则有效规避了这种风险，其停留点提取结果如图2所示。
图2 SPEDV提取停留点
SPEDV的伪代码在算法1中进行了描述:
算法1:停留点检测算法(SPEDV)。
输入:轨迹数据集Tra=p
,p
,…,p
,速度阈值λ
，时间阈值δ
，半径r
，加速度阈值β
输出:停留点集合SP
1:m
=1,flag1=0,flag2=02:whilem
<n
-2 do3: 计算加速度a
+1、速度v
,+14: ifv
,+1≤λ
then5: fst=Backward_Search(Tra[]，m
,r
)6: lst=Forward_Search(Tra[],m
,r
)7: end if
8:Δt
=p
.t
-p
.t
9: if Δt
≥δ
then10:F
=first,B
=last11: while fst<m
+1 do12: ifa
≤-β
13: flag1=1
14:F
=fst,break15: end if
16: fst=fst+1
17: end while
18: while lst>m
+1 do19: ifa
≥β
20: flag1=1
21:B
=lst,break22: end if
23: lst=lst-1
24: end while
25: mid=(F
+B
)/
2.26: if flag1‖flag2==1
27: Add Tra[mid] to SP
28: else
29:p
和p
之间的所有轨迹点的平均位置赋给Tra[mid]30: Add Tra[mid] to SP
31: end if
32: Remove points fromp
top
exceptp
33: else
34:m
=m
+135: end if
36:end while
2.5 基于双速度特征的轨迹划分算法
在基于双速度特征的轨迹划分方法TPDV(trajectory partition method based on double velocities)中，根据速度和加速度变化提取特征点，使用SPEDV算法提取出停留点，根据这些提取出来的特征点对轨迹进行划分。TPDV的伪代码在算法2中进行了描述：
算法2：TPDV算法。
输入:轨迹数据集Tra=p
,p
,…,p
,速度阈值λ
，加速度阈值β
，时间阈值δ
，半径r
输出:特征点集合FP
1:m
=1,k
=0,FP=∅2: FP←(FP∪p
),FP←(FP∪p
)3:v
←计算速度标准差4:a
←计算加速度标准差5: whilem
≤n
-2 do6: if |v
,+1-v
+1,+2|≥v
then7: FP←(FP∪p
+1)8: else
9: if |a
+1-a
|≥a
then10: FP←(FP∪p
+1)11: end if
12:m
=m
+113: end while
14: SP=TPDV(TR,r
,λ
,β
,δ
)15:FP←(FP∪SP)
16:按时间从小到大将FP的点排序
2.6 度量指标
利用三个指标来衡量轨迹划分算法的性能：(a)简化率，即划分后的轨迹点数目与原轨迹点数的比例；
(b)运行时间，指划分轨迹需要的运行时间；
(c)文献[19]提出的评估轨迹划分误差测量方法。
本节将对TPDV算法进行仿真分析，评估TPDV在Geolife数据集上的性能。所有仿真都在配备有Windows 10、2.40 GHz CPU和16 GB内存的PC上进行。
3.1 数据集
以微软研究Geolife项目中收集的182个用户的轨迹数据作为仿真实验数据集。这些数据包含了一系列轨迹点，每一个点轨迹点包含经纬度、时间戳等信息。
3.2 轨迹划分方法的比较
表1 仿真参数设置
3.2.1 仿真1─与TPMF算法比较
首先比较了与同基于节点移动特征进行轨迹划分的TPMF算法，测试了它们在运行时间、简化率和轨迹划分误差三方面的性能。首先对节点1的所有轨迹进行了划分，仿真结果如图3～图5所示。
图3 单节点运行时间比较
图4 单节点简化率比较
从图3可以看出，TPDV的运行时间要比TPMF短，这是因为TPMF递归提取移动方向变化的特征点。如图4所示，在简化率方面，TPDV比TPMF算法提取了更多的轨迹点作为特征点。而就划分误差而言，在图5中，TPDV要低于TPMF的误差曲线。因此，相较于TPMF，TPDV算法具备更低的时间复杂度，同时轨迹划分误差率也更小。
图5 单节点划分误差比较
为了获得更准确的实验结果，对更大量的轨迹点进行了实验。为此从数据集中选择了5个节点(Node 1、3、5、6、9)，仿真结果分别如图6～图8所示。
图6 多节点运行时间比较
图7 多节点简化率比较
图8 多节点划分误差比较
图6中TPDV在每个节点上的运行时间都要比TPMF少，且节点中轨迹点数量越多，时间差越大(在节点7上时间相差约2 s，对于节点5则相差11 s左右)。图7中给出了节点的平均简化率，TPDV算法的简化率在80%至90%之间，要略低于TPMF，原因在于TPDV比TPMF算法提取了更多的轨迹点作为特征点。TPDV根据加速度变化提取的特征点中不仅包含了移动方向变化显著的轨迹点，还有遭遇红绿灯、公共汽车或者地铁停靠站台等特殊情况的轨迹点。从图8可以明显看出，TPDV的平均误差(5个节点的平均误差都靠近15%刻度线)始终比TPMF要低，这都归因于利用SPEDV算法提取停留点，有效解决了误选停留点导致原始轨迹形态发生剧烈变化的问题。
3.2.2 仿真2─与其他算法比较
此外，还将TPDV算法与其他4种算法(DP、BQS、OPERB、MDL)进行了比较。其中各算法用到的欧氏距离阈值都设置为10 m。仿真结果如图9～图11所示。
图9 运行时间
如图9所示，OPERB算法的运行时间快于其他算法，TPDV的运行时间要比BQS、MDL和DP算法短，略高于OPERB算法的运行时间，MDL运行时间比其他算法要长的多。
图10 简化率
在图10中，OPERB在节点平均简化率方面表现最优，达到90%以上，MDL在所有算法中取得最低的简化率。TPDV和DP的简化率曲线相互交叉，它们的简化率都介于80%到85%之间，而BQS的简化率略高于TPDV和DP。
图11 划分误差
在图11中，TPDV的平均误差始终比DP、BQS和OPERB小，MDL获得了最低的平均误差，这主要归因于MDL算法近似地划分轨迹，保留了大量的轨迹点且尽可能地维持了轨迹形状。
综合上述仿真结果，TPDV算法根据轨迹点速度和加速度提取特征点来对子轨迹进行划分，在简化率和轨迹划分误差之间取得较好的平衡，同时也具备较低的时间复杂度。
轨迹划分作为轨迹数据挖掘的一个主要步骤，该文提出了一种基于双速度特征的轨迹划分方法。该方法的突出优点是全面考虑了节点的移动特征，在去掉大量冗余点的情况下，保持了节点的移动轨迹形状骨架。未来的研究将关注TPDV方法中参数设置的自适应解决方案，如参数r
、δ
和β
的值。此外，还将研究基于TPDV的轨迹挖掘算法，以获得节点的运动模式。 猜你喜欢 阈值轨迹加速度 非平稳声信号下的小波变换去噪方法研究现代电子技术(2022年11期)2022-06-14非均匀光照下文本图像分割算法研究科技研究(2021年15期)2021-09-10浅谈求轨迹方程中的增解与漏解福建中学数学(2021年1期)2021-02-28无从知晓小资CHIC！ELEGANCE(2021年44期)2021-01-11利用迭代软阈值方法抑制恒时演化类核磁共振实验中的采样截断伪峰分析化学(2017年12期)2017-12-25走出“加速度”理解的误区新高考·教师版(2016年2期)2017-07-05捕捉物体运动轨迹课堂内外(小学版)(2017年3期)2017-04-15加速度新题型精析中学生数理化·高一版(2016年8期)2016-12-07向心加速度公式推导新高考·高一物理(2015年5期)2015-08-18向心加速度学习一卡通新高考·高一物理(2015年5期)2015-08-18
