时空和语义结合的船舶轨迹数据压缩方法

刘海砚,郭 漩,刘俊楠

1.信息工程大学数据与目标工程学院,河南 郑州 450000; 2.郑州大学计算机与人工智能学院,河南 郑州 450000; 3.郑州大学地球科学与技术学院,河南 郑州 450000

近年来,大数据、移动互联、卫星定位技术高速发展,船舶自动识别系统(automatic identification system,AIS)得到普及和推广[1]。AIS产生了覆盖范围广、时效性强的船舶轨迹数据,被广泛应用于船舶航行特征挖掘、国际经济贸易模式分析等方面[2]。海量轨迹数据的大数据特征既带来了研究机遇,也对传统数据分析方法带来一系列挑战[3]。此外,海量冗余的轨迹数据降低了轨迹检索分析的效率[4-5],不利于进行数据挖掘。为有效缩减轨迹数据存储和传输的成本,亟须结合船舶语义时空特征控制压缩过程,使用关键信息表示船舶轨迹数据,进而满足数据压缩需求。

轨迹数据压缩的本质是数据的有损压缩,即通过最重要的时空和语义信息表示轨迹,满足压缩后数据与原始轨迹的相似度[6]。轨迹具有精确的地理空间坐标,因此传统的轨迹数据压缩方法通常仅考虑其空间特征,将轨迹抽象为线要素并采用线化简技术实现压缩。如道格拉斯—普克(Douglas-Peucker,DP)[7]、滑动窗口(sliding window,SD)[8]、普通开放窗口[9]等算法,分别在全局和局部两个方面使用欧氏距离计算并删除偏移量较小的点,实现顾及几何特征的轨迹线要素压缩。由于轨迹具有时间属性,文献[10—11]结合了时间和空间信息压缩轨迹。此外,文献[12]引入时空距离,优化DP等算法,提高轨迹距离的度量精度,但仍需预先传入距离阈值参数。文献[13]提出了一种DP算法的阈值估算方法,根据轨迹长度自动控制轨迹数据压缩过程,但难以顾及轨迹关联城市设施的语义信息。在语义压缩方面,伴随城市路网结构的愈发成熟,部分学者逐渐采用路网获取轨迹语义信息实现轨迹数据压缩。文献[14]基于城市路口的语义特征,设计了车辆轨迹的语义表示和分段轨迹数据压缩方法。文献[15]结合兴趣点、重点地物和路段,辅助用户理解轨迹信息,提高轨迹数据压缩比例。文献[16]根据城市和乡村地区兴趣点的分布差异,探索适应不同区域地物密度的轨迹语义压缩方法。虽然基于路网的轨迹语义压缩可显著减少空间存储开销,但在海洋中行驶的船舶轨迹缺少足量的兴趣点和路网结构,难以基于地物实现船舶轨迹语义压缩。

针对以上问题,本文以AIS船舶轨迹为试验数据,提出一种时空和语义结合的轨迹数据压缩方法(spatio-temporal and semantic trajectory compression,SSTC)。首先,分析船舶轨迹的时空和语义特征,并设计轨迹数据压缩流程。其次,分别根据时空和语义信息,计算船舶轨迹点的特征值。然后,采用BLG树(binary line generalization tree)和加权融合法综合轨迹点的时空和语义特征值,获取轨迹点的重要性排序,最终实现顾及船舶航行时空和语义特征的轨迹数据压缩。

1 船舶轨迹特征和压缩流程

1.1 轨迹时空和语义特征

船舶轨迹(Trj)是船舶在地理空间留下的痕迹,由包含空间位置、时间节点、语义特征等信息的轨迹点集合组成,可表示为Trj={P1,P2,…,Pn}。其中Pi={li,bi,ti,vsi}为轨迹点,li、bi、ti、vsi分别表示轨迹点的经度、纬度、采样时间、具体语义信息,且轨迹中∀1≤i≤j≤n,均存在ti

空间特征是事物的基本特征,可通过li、bi表示轨迹的空间形态、分布和走向等[17]。其中,空间形态作为轨迹数据的主要特征,可通过少量的空间特征点表示原始轨迹。时间特征是轨迹数据区别于传统地理空间数据的本质特征,展示移动对象的动态变化特点。为了形成一体化时空特征,文献[13]提出时间同步欧氏距离,在近似轨迹上按时间比例获取原始轨迹点的近似点并计算两点的欧氏距离,对时间和空间特征进行转换,使时间与空间位于统一的度量标准,以度量并获取时空特征显著的轨迹点。在远距离载运工具中,船舶运载的历时最长,因此产生的冗余点显著多于其他移动对象,且存在周期长,跨度大,轨迹间长度差别明显等特征。

语义特征指事物蕴含的基本含义,语义是词语和事实之间的关系,可作为联系知识表示和现实世界的途径[18],通常包括静态语义和动态语义[19]。其中,静态语义涉及兴趣点等地理空间环境信息,但是海洋存在的兴趣点等地理空间设施较少,难以与船舶轨迹建立关联。动态语义包括船舶航速、航向等随时间平缓变化的信息,可直接表示船舶骤停或急转等航行状态变化,也可间接体现船舶受地理空间环境的影响[8],为船舶轨迹数据压缩提供了一种途径。

1.2 轨迹数据压缩流程

本文以船舶轨迹数据为研究对象,提出了一种结合船舶轨迹时空和语义特征的数据压缩方法。如图1所示,压缩算法包括船舶轨迹的时空特征值计算、语义特征值计算、特征点融合排队和轨迹数据压缩4个部分,具体内容如下。

(1) 轨迹时空特征值计算。以轨迹的时间标签和经纬度坐标为基础,通过DP算法和时间同步欧氏距离,计算并获取轨迹的时空特征点,进而通过少量轨迹点反映轨迹的时空特征。

(2) 轨迹语义特征值计算。以轨迹点的航速和航向作为语义信息,通过SD算法依次计算轨迹点的语义信息变化,进而获取轨迹点的语义特征。

(3) 特征点融合排队。分别对轨迹点的时空和语义特征进行重要性排序,并采用加权融合排队方法,获得综合考虑时空和语义特征的轨迹点重要性队列。

(4) 轨迹数据压缩。按照重要性程度对轨迹点进行排列,仅根据传入的压缩比例获取目标轨迹点数目即可保留特征显著的轨迹点并删除其他点,实现轨迹数据压缩,减少数据冗余,优化存储结构。

2 船舶轨迹点的时空和语义特征值计算

轨迹数据压缩算法应保留更能体现船舶行驶特征的轨迹点,而时空和语义属于不同的评价标准,因此需分别在时空和语义角度计算轨迹点的特征值。

2.1 轨迹点的时空特征值计算

DP算法是一种可以根据空间特征保留重要轨迹点的线压缩算法,该方法思想简单且性能较好,在线化简等制图综合领域应用广泛[20]。然而,DP算法采用垂直欧氏距离度量偏移量,仅考虑了位置信息,而轨迹点表示的是船舶在具体时刻的位置,因此还需综合考虑轨迹点的时间信息。

图2 时空特征值计算

2.2 轨迹点的语义特征值计算

船舶轨迹数据的动态语义信息包括船舶的对地航速(speed over ground,SOG)和对地航向(course over ground,COG),可以通过其数值变化计算船舶的航行特征[8]。其中,SOG表示船舶在风和水流影响下的航行速度,航速的通常单位为节或海里/小时,相当于1 h船舶行驶的距离,1节为1.852 km/h[21]。COG表示船舶在风和水流影响下的航行角度[22],由真北线顺时针方向开始计量当前时刻(t1)与下一时刻(t2)船舶航行角度,计量范围为0°～360°(图3)。COG和SOG结合可体现船舶动态变化信息,也可间接表示其受水和风的影响,可作为计算轨迹语义特征值的重要变量。

图3 对地航向示例

DP算法可以在全局角度保留船舶轨迹的时空特征[4],却难以在局部顾及船舶航行状态变化的语义信息,传统SD算法采用垂直欧氏距离计算窗口内的特征变化,仅能应用于时空特征误差的度量,均不直接适用于船舶轨迹动态语义特征点的计算。本文以SD算法的滑动窗口为基础,从轨迹起点开始,初始化滑动窗口,并逐步移动窗口,在一个固定大小的窗口中根据固定数目的轨迹点,计算局部窗口内轨迹点的语义特征值。图4展示了轨迹的语义特征计算过程,首先初始化一个窗口大小为3的滑动窗口,窗口内包括3个轨迹点;然后计算第1个窗口内轨迹点的语义特征值,即第2个点(P2)相对于第1个点(P1)和第3个点(P3)对地航速(Δsog_P2)变化的绝对值平均数,3个轨迹点形成的对地航向变化夹角(Δcog_P2);最后,窗口向前滑动,依次计算P3、P4、P5和P64个轨迹点的对地航速和对地航向变化,由此获得船舶轨迹点的语义特征值。

图4 语义特征值计算

3 船舶轨迹数据压缩

船舶轨迹通过部分特征点即可概略表达轨迹特征,而且轨迹特征点数目与压缩比例呈现反比关系,本文将在语义和时空综合约束下压缩原始船舶轨迹。

3.1 轨迹特征点排队

SD算法以局部窗口为约束,计算的轨迹点语义特征值,可以分别根据Δsog和Δcog的数值对比,获取降序排序。然而时空特征值采用逐层二分方式的DP算法,直接构建偏离值的排序队列方式容易忽视DP算法的层次性[23]。

为了获取DP算法的偏离值排序队列,本文以文献[23]提出的单条曲线BLG树为基础,采用二叉树表示整条轨迹的时空特征值。该二叉树的根结点为轨迹点到近似轨迹的最大时空欧氏距离点,即最大时空特征值点,根结点的左右子结点则分别为其左右子轨迹的最大时空特征值点。图5展示了DP算法分割原始轨迹构建BLG树的过程,其中轨迹Trj1由{P1,P2,…,P10}点集组成,P1和P10是首尾轨迹点构建的初始近似轨迹线,由时空同步欧氏距离可知P4为最大特征点,因此将其作为根结点;然后将轨迹分为{P1,P2,P3,P4}和{P4,P5,P6,P7,P8,P9,P10}两个子轨迹,此时最大特征值点分别为P2和P8,即BLG树中根节点的左右子节点为P2和P8,由此类推可构建轨迹的BLG树(图5(b))。

图5 原始轨迹和BLG树

BLG树的结点存储层次和偏离值体现了轨迹点表示时空特征的能力,层次越高、偏移量越大则能力越强。通常父结点的偏移量会比子结点的偏移量大,然而DP算法不能保证子轨迹最大特征值结点的偏移量一定小于其父轨迹最大特征值结点的偏移量。

如果直接按照特征值大小排队轨迹点,将会破坏轨迹和子轨迹之间的层次关系,而如果按照先层次后特征值的顺序对轨迹点进行排队,则会出现子节点特征值大于父节点特征值的现象。如图5(b)所示,P6是子节点,其偏移量(926 km)大于父节点P8(910 km),也大于节点P2(573 km)。为了根据时空同步距离构建线性排序,需从根节点开始按照先层次、后特征值的方式将BLG树转为排序BLG树。具体来说,①将根节点P4加入排序BLG树,序号为1,并将P4的左右子节点P2和P8加入待排序队列;②在待排序队列中选择偏移量最大的节点P8加入排序BLG树,并将P8的左右子节点也加入待排序队列,此时待排序队列包括P2、P6和P9;③重复步骤②,直至待排序队列为空;④获得最终排序BLG树。经过以上步骤构建的排序BLG树,既可保证层次间的父子关系,又可保证特征值的大小顺序。如图5(c)所示,P8和P6的节点排序为2和3,保证了层次关系,同时P2和P6的节点排序为4和3,保证了特征值的排序关系。最后根据排序BLG树、语义特征值和时空特征值的变化,依次进行降序排列,其中原始轨迹的首尾点直接排序在前2位,进而将以特征值为依据的轨迹数据压缩,转换为以特征值排序为基础的轨迹数据压缩。图6列出了Trj1的时空特征值、语义特征值Δsog和Δcog的排序结果,其中P4在排序BLG树中的序号为1,但在排序结果中需在首尾点之后,因此序号为3。

图6 特征值排序

3.2 轨迹数据压缩

作为船舶行为特征挖掘等应用的主要数据源之一,船舶轨迹数据可充分体现船舶航线和航速等时空和语义变化,但二者间的评价标准存在差异[24]。为了融合轨迹特征点的时空和语义评价因素,本文采用加权融合方法[25]对单特征值排序结果进行加权,以获得最终的排序结果(O),融合不同指标的评价结果并提高运算速度,具体公式如下

O=ωaOst-1+ωbOcog-1+ωcOsog-1

(1)

式中,Ost、Ocog和Osog分别表示轨迹点的时空、航向和航速特征值的排序结果,排序的倒数表示轨迹点的重要性程度;ωa、ωb、ωc是3个重要性的权重,用于平衡不同因素的重要性程度,且满足ωa+ωb+ωc=1。

特征值队列排序之后的轨迹点已经按照重要性程度进行排列,排序靠前的轨迹点指时空和语义特征显著的点,排序靠后的轨迹点指显著性低的点,进而建立了压缩比例和排序队列的关联关系,根据压缩比例可压缩船舶原始轨迹。如式(2)所示,根据压缩比例(ratio)和轨迹点总数(Countall)计算保留(Countreserved)或删除(Countremoved)的轨迹点数目,并以排序队列为基础,保留排序靠前的Countreserved个轨迹特征点,同时删除排序靠后的Countremoved个轨迹点,经过以上步骤无须考虑域值参数,根据压缩比例即可自动获取压缩结果

(2)

4 试验与分析

为验证轨迹数据压缩方法的可行性,本文以Windows 10(64位)操作系和C++语言为软件运行环境,以AMD Ryzen 9 5900HX with Radeon Graphics 3.30 GHz处理器和32 GB内存为硬件运行环境,同时以2016年覆盖全球的中国油轮数据作为试验轨迹展开验证,其中轨迹点的上传间隔为2 s至3 min不等。根据时空信息对原始轨迹进行误差点删除和分段等预处理,经统计,试验数据涉及油轮5265艘,选取轨迹点数目位于900～1000区间的正常行驶轨迹段进行试验分析,共包含轨迹10 120条,轨迹点9 625 498个。同时,为消除时空和语义因素对轨迹数据压缩的影响差异,本文将轨迹的时空和语义特征值排序队列赋予等量的权重(即ωa是0.5),并将角度(ωb)和速度(ωc)两个权重均取值为0.25,以确保两个语义因素对轨迹数据压缩具有相同的影响。

4.1 压缩评价方法

船舶轨迹数据压缩技术可消减无用点数据,进而提升轨迹挖掘的效率,降低数据存储成本。目前,轨迹数据压缩的评价指标主要包括压缩比例、运行时间,以及长度损失和长度损失率[22]。其中SSTC算法根据压缩比例动态调整压缩过程,因此压缩比例并不作为本文方法的评价指标。运行时间是评价海量轨迹数据压缩算法优劣的重要指标,在相同数据规模下,算法运行时间短,则效率高且实用性更强。长度损失评价方法可通过原始船舶轨迹点与压缩后轨迹线的相对偏差进行评价,也可通过原始轨迹和压缩后的轨迹长度偏差衡量压缩精度,但前者通常作为DP和SD算法压缩过程的评判指标,后者难以适应船舶轨迹周期长、跨度大、轨迹间长度差别明显等特征。为了更加客观地评价算法性能,本文采用长度损失率表示轨迹的压缩精度,根据原始轨迹和压缩后的轨迹长度评价压缩算法的质量,计算如下

(3)

式中,|PnPn-1|表示2个离散轨迹点的欧氏距离,Length和Length′表示原始轨迹和压缩后轨迹的总长度,且二者差值表示长度损失(Length_loss),长度损失与原始轨迹长度的比值是长度损失率,用于衡量轨迹数据压缩精度。

4.2 压缩算法质量对比分析

影响压缩轨迹长度损失的最大因素是压缩比例,压缩比例越小保留的轨迹点越多,产生的长度损失越小,越能保持轨迹的形态特征。如图7所示,SSTC、DP和SD算法的长度损失均随压缩比例增加而加大,但即使压缩比例增加至0.9时,3种算法的长度损失比例均小于0.000 35%,相对于船舶的长途航行,其误差较小。此外,压缩比例在0.2～0.5之间时,SSTC算法的压缩质量较高,而随着压缩比例增加,3种压缩算法的误差增长明显。压缩比例达到0.6后,在同等压缩条件下,本文为了保留语义特征点需忽视部分时空特征值较小的轨迹点,因此本文的长度损失稍高于其他两种算法。综上,SSTC算法结合了DP和SD算法的优势,3种算法压缩后的轨迹数据,均与原始轨迹具有较高的相似度,在质量方面不分上下。

图7 轨迹数据压缩算法的长度损失率

4.3 压缩算法效率对比分析

本文通过对比分析SSTC、DP和SD算法的运行时间,评价压缩算法的效率。假如轨迹点的数目为N,传统DP算法的时间复杂度为O(N2),SD算法的时间复杂度为O(N),而SSTC算法是对DP和SD算法的结合,还需涉及时间复杂度为O(Nlog2N)的堆排序操作,则时间复杂度可估算为O(N2+N+Nlog2N)。然而,DP和SD算法需要通过距离阈值控制压缩过程,不同地理环境下需要多次测试阈值,才可获取指定压缩比例的结果。而本文可以根据压缩比例自动获取需要保留的轨迹特征点,跳过阈值参数测试即可获得压缩结果,因此SSTC算法虽然单次运行耗时较长,但实际应用中多次运行的平均效率较高。

为在同一压缩比例下测量算法时间,经过试验压缩比例0.1～0.9分别对应的DP和SD算法的平均阈值为0.08、0.26、0.5、1.3、2.7、6.7、18、100、500 m,本文在不同压缩比例下分析3种算法的压缩效率(图8)。如图8(a)所示,SD算法的效率最高,压缩算法单次运行需要10 ms。DP算法的运行效率居中,并且随着压缩比例的增加,其运行时间逐渐减少。SSTC算法对全部轨迹点进行排序,与阈值无关,仅与轨迹点的时空和语义特征相关,虽然单次运行时间最长,但仅需构建一次排队序列,即可根据压缩比例进行多次压缩。如图8(b)所示,经过5次阈值试验后,SSTC算法平均耗时将明显低于DP算法,也优于SD算法,表明多次测试阈值或阈值动态变化情况下,SSTC算法效率较高。

图8 轨迹数据压缩算法的平均运行时间

4.4 本文压缩算法实例分析

本文以MMSI号为414213000的油轮为例,针对2016年1月15日至2016年1月25日由波斯湾航行至中国南海的一条轨迹数据(图9(a)),展示本文方法船舶轨迹数据压缩结果,其中黑色线为原始轨迹,红色点表示压缩比例为0.1情况下,SSTC算法保留的轨迹特征点。如图9(b)和图9(c)所示,黄色圆点为本文压缩算法可以保留,但传统DP和SD算法无法保留的轨迹点,其中轨迹点31、32和33的COG为6°、12.2°和12.4°,轨迹点32与前后时刻存在较大的航向变化差值,因此保留具有此类对地航向变化明显的轨迹点。同样轨迹点717、718和719的SOG分别为3.3、11.1和13.6节,轨迹点718是一个加速特征明显的轨迹点,因此本文方法也将此类轨迹点保留。此外,图9(d)中黄色方点展示了DP算法保留但本文方法并未保留的轨迹点,其中轨迹点884的航速和航向语义特征在各自的排序队列相对靠后,虽然其时空特征变化较为明显,但无法满足在现有压缩比例下的轨迹点保留条件。通过算法实例分析表明,SSTC算法可以在保证时空几何特征的同时兼顾语义特征,压缩后的轨迹更能体现船舶的行驶状态。

图9 轨迹数据压缩实例

5 结 论

海量船舶轨迹数据存在冗余,容易增加存储负担和传输成本,因此亟须结合业务需求压缩船舶轨迹数据。然而船舶轨迹的语义特征和时空特征在度量标准和评价标准方面存在差异,现有轨迹数据压缩方法无法综合考虑船舶航行的语义特征和轨迹的时空特征。针对以上问题,本文以AIS为数据源提出了一种顾及时空和语义特征的船舶轨迹数据压缩方法。首先,分别计算船舶轨迹点的时空、航速和航向特征值,获取单独特征值的排序队列。然后,采用加权融合法综合轨迹点的时空和语义特征的单独排序队列,获取轨迹点重要性排序。最后,通过船舶轨迹的压缩效率、质量对比分析,以及压缩算法实例分析,证明本文方法可有效保留船舶行驶的动态语义信息和时空形态特征,也可以根据压缩比例控制船舶轨迹数据压缩过程,为海量船舶轨迹数据的存储与分析提供了基础。在后续研究中还需结合高斯分布函数,探索轨迹点特征值变化的分布特征,确定轨迹点的特征变化阈值,进而辅助实现船舶轨迹的语义压缩方法,进一步提高轨迹数据压缩效果和质量。此外,如何依据压缩任务的特点和区域特征等先验知识动态调整时空和语义特征权重,进而提升算法的普适性和通用性,也需进行深入研究。