基于TDD的科考船航迹分段方法研究

王建 史景聪 黄冬梅 郑小罗 何盛琪 张北辰

研究论文

基于TDD的科考船航迹分段方法研究

王建1史景聪1黄冬梅1郑小罗1何盛琪1张北辰2

(1上海海洋大学, 上海 201306;2中国极地研究中心, 上海 200136)

“雪龙”号极地科考船是推动我国极地科学考察事业发展的重要工具, “雪龙”号在数十次的极地科考过程中累积了大量的航迹数据, 其中蕴含的巨大价值亟须挖掘。针对科考船的航迹分段是将科考船移动轨迹分为停留与行驶两部分, 合理的分段方法可以分离出信息更丰富的航迹段, 有利于航迹知识提取。然而, 由于原始航迹信息密度分布不均等原因, 现有的航迹分段方法往往会造成分段过多等问题, 结果并不理想。本文针对该问题, 提出了一种针对科考航迹整体的时域差分(Time Domain Difference, TDD)分段方法。本方法基于时间域对航速进行差分处理, 有效降低了因为航速波动频繁对分段结果的影响。同时, 考虑到该方法的差分步长在航迹处理过程中的不明确性, 本文将差分后航迹的路程损失和航速波动幅值进行归一化处理, 提出了航迹差分时间步长的动态确定方法, 并以速率阈值对航迹进行分段。最后本文以第29次南极科考航迹数据为例, 将本方法与经典的具有噪声的基于密度的聚类方法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)进行了比较, 实验结果表明本文提出的方法可有效降低航迹分段时分段过多的问题, 在分段准确性和时间效率等方面结果更优。

科考航迹 时域差分 停留 步长 DBSCAN

0 引言

我国近年来在极地考察领域取得了很大的进展, “雪龙”号作为我国极地科考不可或缺的破冰船, 是科学家们赴两极地区科考的有力支撑。在“雪龙”号航行的几十年间, 极地科考距离远, 周期往往长达数月之久, 每次出航都会产生数万甚至数十万不等的航迹点, 累积了大量的航迹数据。作为重要的极地科考成果之一, 科考航迹数据按照一定采集频率获得了连续时空点序列, 每个航迹点都记录了科考船在该点的时间、位置、航向、速度等运动信息, 历史航迹数据蕴含极大的研究价值, 并可为后续航行提供重要参考。但同时, 科考航迹数据具有周期长、单条数据量大、采样间隔不一、信息密度不均等特点, 给航迹数据的处理、分析和挖掘带来了困难与挑战。

航迹分段可根据船行速度将航迹分为停留与行驶两部分。停留是指船在某一位置停泊超过一定时间(如船只入港后下锚、装卸货物等), 或是在一定区域内徘徊、迂回等状态, 且此过程也超过一定时间。行驶是指船舶在停留区之间的移动过程状态, 期间正常速度高于停留状态[1-3]。其中停留部分是航行的重要节点, 可提取出航行路径、船只状态、考察区域等重要活动信息, 是分段研究的重要目标之一。合理的航迹分段算法可以有效提取出停留航段信息, 减少航迹冗余, 降低处理成本, 在船只行为分析、异常检测、航迹规划和快速可视化展示等方面[4-8]提供有力的技术支撑。

1 相关工作

近年来针对“雪龙”号的船行状况[9]、破冰模式[10]及监控系统[11]等都有研究, 然而针对科考航迹分段方法的研究较少。在陆路轨迹及船舶自动识别系统(Automatic Identification System, AIS)等航迹分段方法研究方面, 归纳起来主要可以分为以下3类。

(1)基于速率的分段

2003年Ashbrook和Starner[12]将汽车轨迹的停与留以速度是否为零进行了简单的粗分段。Krumm和Horvitz[13]针对由GPS定位误差造成停留识别错误的问题做出改进, 通过定义时间阈值与平均速度阈值, 并计算超过该时间阈值内的平均速度是否低于速度阈值, 对轨迹的停留进行分段。彭祥文等[14]通过设置的移动目标转向角阈值和速度变化率阈值进行轨迹分段, 计算得到相邻轨迹点的航行差值以及速率变化后与预先设定的值比较, 满足其中一个则以该点为断点进行轨迹分段。

(2)基于候选停留区的航迹分段

Alvares等[15]通过预先定义重点区域的边界和大小, 再判断航迹在区域内的停留时间是否达到阈值来获取停留信息。齐凌艳等[1]定义抽取子轨迹要考虑的三个因素: 时间阈值、距离阈值、地理位置, 通过计算目标到达目的位置后在停留区内的移动距离、到达及离开时间, 判断是否满足设置阈值, 来获取轨迹的停留信息。

(3)基于聚类的分段

杜胜兰等[16]采用DBSCAN算法对武汉大学校内的大量学生轨迹进行处理, 结合校园超市、教学楼等地理信息提取停留特征, 用于分析武大学生的特定群体行为。权宇澄和吴健平[17]提出了以时间为聚类核心距的DBSCAN改进算法, 该算法一定程度上解决了航迹数据采样间隔不均的问题。Pallotta等[18]使用DBSCAN算法基于航迹点聚类去除不可用数据, 进一步识别具有异常行为的航迹, 搭建了船只航迹异常检测和路线预测框架。

在现有航迹分段方法中, 基于速率阈值分段的方法在移动目标速度波动频繁时容易造成分段过多的问题; 候选停留区方法, 由于海上区域边界不明确且无路网匹配, 并不适用于海上航迹分段; 聚类分段方法容易受采样密度和空间重叠等因素的影响, 时间复杂度较高。综上所述, 针对陆路及海上AIS航迹分段方法的研究虽然取得了一定进展, 但分段效率和准确性方面仍有待进一步提升。本文在分析现有分段方法基础上提出了一种针对科考航迹整体的时域差分分段方法(TDD), 并动态地解决了差分步长在航速差分过程中的不明确问题, 最后通过与航迹分段的经典算法DBSCAN进行对比, 验证了本文方法的有效性。

2 研究方法

本研究的技术路线如图1所示。首先提取原始航迹数据中包含必要信息的航迹点作为可用航迹数据, 并进行插值拟合处理, 减少因数据缺失或采样间隔差异对采样点空间密度分布的影响, 然后根据采样点的经纬度计算得到航迹点的航程数据, 并采用差分法对航迹做多阶差分处理, 在多阶差分数据的基础上通过归一化方法求得航程损失与航速标准差的平衡点, 确定合适的差分步长。最后计算原始航迹数据的平均航速作为分段阈值, 实现航迹分段。下面将针对技术路线中的多阶差分计算和动态差分步长确定进行进一步说明。

图1 基于TDD的科考航迹分段技术路线

Fig.1. Technical route of track segmentation for scientific expedition based on TDD

2.1 多阶差分计算

式(1)中各参数定义与计算方法如下。

图2 原始航速数据

Fig.2. Original speed data

图3 多阶航迹差分

Fig.3. Multi-order track difference

2.2 动态差分步长的确定

差分法通过增大差分步长来计算较长时间段内的平均航速, 使得航速状态的改变更加明显, 便于航迹分段, 但差分步长过大时也会带来数据失真较大的问题。由于差分步长过大使得多个航速峰值和谷值等特征点缺失, 导致过度缩小航速状态差异, 造成相邻分段被合并而分段过少的问题, 如图3中的图d所示。不同航迹有着不同的停留分布与特点, 造成航迹分段时的差分步长也有所不同。因此, 动态地确定差分步长对航迹的准确分段有着重要的影响。

比较不同差分步长的差分结果后, 可发现锯齿状航速的幅值过大是造成分段过多的主要原因, 而锯齿现象的严重程度可以通过航速的标准差来衡量, 且随着差分步长的增大, 航速标准差逐渐减小。同时, 采用差分法所获得的差分航速是伴随着路程损失的, 随着差分步长的增大, 路程损失也随之增大。图4为航迹的路程损失和航速标准差随差分步长增大的变化图, 可以看出路程损失随差分步长的增大而增大, 与差分步长正相关, 而航速标准差则相反, 与差分步长负相关。

对同一航迹不同差分步长的航速标准差和路程损失采用归一化方法处理后求交点[21], 可在航速标准差和路程损失带来的影响中求取一个平衡点, 得到相对合理的差分步长值。航速的标准差公式为:

其中v为原始航迹的速度平均值。路程损失为:

其中S为当前路程值,S为实际路程值,S为路程损失值。将多阶差分步长的航速标准差和路程损失值归一化处理, 即

其中, 为航速最大标准差, 为航迹最大路程损失值。当式(6)成立时, 可求得即为适用于当前航迹分段的差分步长值。