基于网格的航道模式提取算法研究∗

牛敬华 马良荔 覃基伟

（海军工程大学 武汉 430000）

1 引言

在经济全球化背景下，海上贸易运输占据了全球贸易运输量的90%以上，海上运输安全因此显得尤为重要，船舶自动识别系统（Automatic Identification System，AIS）正是在这一背景下产生的。AIS简化和促进了信息的交换，首先它在海上交通防避碰方面发挥了重要作用，其发出的内容包括船只当前的经度、纬度、船首向、航迹向、航速等动态信息，为船只避让提供了充分的准备时间。其次，其包含的静态内容包括船名、呼号、水上移动通信业务标识码（Maritime Mobile Service Identify，MMSI）、国际海 事 组 织（International Maritime Organization，IMO）、船舶类型、船长、船宽、船舶状态、吃水、目的地等，方便了海事部门对船舶的航行进行连续的监视和管理。AIS包含的信息比较丰富，通过分析挖掘历史数据，可以还原船舶的历史轨迹，分析船舶的行为模式，为海事监管提供方便。其发出信号的频率从两秒到几分钟不等，根据船只当前的航向状态决定，航行速度越快，转向速率越快，发出信号的频率也就越高，反之，当船只停靠码头或者抛锚时，发出信号的频率最低。安装该系统的船只产生了大量的数据，合理有效地分析利用这些数据可以提高海事监管的效率。当前国外学者对AIS的研究比较多，海事成立了专门的机构进行研究；国内相对来说起步较晚，研究资料比较少。本文在研究国内外资料的基础上，提出一种基于网格的航道实时提取算法，可对特定区域进行处理，提取出航道信息，用于展示实时的航道情况。

2 相关研究

按照研究对象进行划分，当前的航道提取算法主要分为两种：基于点的航道提取算法和基于轨迹的航道提取算法。其中，基于点的提取算法以单条AIS数据为单位，对点进行分析，不考虑同一条船产生数据的关联性，认定AIS数据服从独立同分布；基于轨迹的提取算法以每条船的航迹为单位，对线进行分析。基于点的航道提取算法因不考虑点之间存在的关联性，丢失了很多潜在信息，然而应用比较灵活，算法复杂度低，通用性广。基于轨迹的航道提取算法克服了以上的不足，首先把同一目标的点集合组成一条轨迹，然后以轨迹为单位进行挖掘提取，但这种方法会增加了算法设计的复杂性，提高了运算量适合对大量数据进行实时运算。

1）基于点的轨航迹取算法

此类算法充分利用了AIS信息中的经度、纬度、船首向、航迹向、航速等动态信息，采用聚类的思想进行分析［1］。对AIS数据中的各个属性进行了离散化处理，把航行速度由低到高划分为五个区间，航行方位均分为八个区间，经纬度每0.1°平方划分为一个格子，在此基础上对数据进行聚类处理，并对聚类处理后的结构应用Apriori和Fp-Growth算法进行关联统计，最终得到航道信息。此方法充分利用了AIS包含的信息，获取的知识可进一步应用于船舶运动模式预测和异常检测［2］。考虑了在采集过程中数据可能存在的不完整性，采用遗传算法对AIS数据进行处理，提取数据集中密度大于设定门限的航点。由于对数据的处理过程是迭代进行的，且对已提取的航点增加了衰减系数来保证航点的实时性，此算法可应用于对实时数据流的处理［3］。提出了一种新的航道生成方法，在始发港口和目的港口之间随机插入可能经过的航点，将生成的航点与历史数据的相近性作为筛选函数，通过遗传算法进行迭代优化，最终产生连通始发港口和目的港口的航道。优点在于可以进行大量数据的运算［4］。把电位势法应用于航道的表示，可使航道进行可视化展示，也为异常检测提供了有力支持。提出了滑动窗口法选择AIS数据集，用线性衰减函数表示历史数据的权重，方便航道数据的实时更新。

2）基于轨迹的航迹提取算法

此类算法主要是通过对轨迹间相似性应用聚类或分类算法来实现的。由于轨迹中不同点之间时间间隔有长有短，距离间隔也各不相同，必须先对轨迹稀疏地方进行插值，对密集地方用轨迹压缩算法处理，得到相对均匀平滑的历史轨迹，再选取合适的轨迹相似度测量方法对轨迹间相似度进行计算。文献［7］通过航线生成、航线聚类、聚类中心线提取，提出了一种基于空间聚类分析的南海主要航线提取方法，对南海主要航线分布特征进行分析。此方法优点在于获取的航道模型清晰，与实际航道一致性高。文献［8］根据船舶海上的运动特征，研究了船舶航向和航速变化规律，为研究船舶行为特征提供了新的依据。同时设计了在线识别船舶的搁置行为的算法，对航线规划中的船舶热点区域有一定的参考价值。然而，大多数已有的算法都是以轨迹的完整性为基础的，在实际情况下，因AIS信号覆盖率低或因采集时间太短，大多数情况下无法获取完整轨迹，这些算法的效果便会下降，无法适应复杂的应用环境。

本文提出一种结合点与轨迹信息的方法，首先根据单个点的静态和动态信息，采用基于网格的算法提取航点数据，然后根据轨迹信息把得到的航点位置联系起来，形成有向加权图，提取出航道信息。

3 航道提取模型设计

航道模型的表示有多种，基于点的航道模型对过去点的信息进行统计分析，把航道模型定义为该海域历史点的多数行为。基于轨迹的航道模型对历史轨迹进行聚类，对每个类泛化拟合通用航迹来表示模型。

本文中航道提取模型主要分为两个部分：航点的提取和航道的提取。其中，航点的提取是指把适航水域中具有代表性的关键节点找出来，组成有向图的节点，本文定义航行历史数据比较密集的点为关键点。航道提取是指根据航迹的信息将不同的航点用边联系起来，并赋予权值，形成航道模型。

3.1 航点的提取

由于全球的航道信息分布极不规范，对于航道的提取和应用是分区域进行的，本文中对航道的提取也是对选定区域进行的，并对航点定义如下。

定义1（航点） 对于地图上的任意一点P，给定一个距离阈值θ和一个数量阈值α，通过计算点P到数据记录中所有AIS点的距离，若距离小于θ的数量大于α，则认定点P为航点，如式（1）所示。

通过借用分布式计算的思想，先将选定区域划分成长为Δlon、宽为Δlat的网格，分别计算得到每一个网格内的航点，然后将每个网格内的航点集合起来，最终得到整个区域内的航点数据。网格边长的选取需要对具体海域和数据进行调整，若网格的边太大，会造成各个网格内点分布极为不均，影响计算性能；若选取太小，则许多网格内的点太少以至于无法识别为航点。

航点提取算法如表1中算法所示，（2～6）首先遍历数据集，将每个点划分到对应的网格中。（7）选择每个网格中符合航点的标准的点，首先从网格中任选一点point-a，（11～17）然后统计网格中附近点的数量，（18～22）如果点point-a附近点数量多于阈值α，则认定其为航点。航点附近的点作为航点一部分，从待处理的数据集中删去。

3.2 航道的提取

孤立的航点包含的信息量是有限的，只能代表距离该航点周围θ内的历史航行情况，只有把孤立的航点联系起来，才能形成有信息支撑的航道图。

航道的提取是在获取到航点之后进行的，提取过程中应用到轨迹的连续信息。要得到轨迹数据，需要对AIS数据集进一步处理。首先将AIS数据按照MMSI区分开，得到每条船的轨迹数据集，再将每个数据集中点的顺序按照时间戳排列，便得到每条船的轨迹。由于船舶在不同行驶状态下发出AIS信号的频率不同，船速较高和转向率高时频率高，船速低时频率低，这就意味着同一条船的轨迹点分布是不均匀的。

表1 航点提取算法

如图1（a）所示，为未处理的原始轨迹，其轨迹点密度分布不均匀。在矩形标识区域太过稠密，而在圆形标识区域，没有轨迹点，太过稀疏，轨迹点过于稠密和稀疏都会对算法产生不良影响。此外，在一些AIS基站无法完全覆盖到的盲区，也会有一些空白。因此要对轨迹进行预处理，使轨迹平滑均匀，预处理算法如表2中算法所示。对轨迹的处理包括两种情况：对于轨迹点稀疏的部分，要进行插值处理，补足可能遗漏的AIS信息；对于太密集的部分，为了减少计算量，要进行轨迹压缩处理，删去冗余的轨迹点。轨迹插值算法比较成熟，插值后轨迹较为平滑的算法有拉格朗日插值和牛顿插值，本文为了计算方便采用简单的线性插值。插值后会出现点在陆地上的情况，在实际实验中，这种情况较少出现，不会对结果造成影响，故对此类错误不做额外处理。对于轨迹压缩算法近年来相关研究也比较多［5～6，9］，本文在结合已提出压缩算法的优缺点，综合算法性能和所需实际出发，采用在线压缩算法，将轨迹中密集且非关键点删除。对单条轨迹处理效果如图1（b）所示，处理后的轨迹点分布比较均匀，轨迹平滑。

图1 轨迹预处理

算法2中对轨迹进行处理使其密度均匀，（2）对于轨迹中每个点Q，（3）计算其与前一个点的距离distance，（4～5）若距离大于设定的临界点距离，则应用插值算法，在这两点间插入点；（6～7）若距离小于设定的临界点距离的一半，则应用压缩算法，删去点Q及其后面距离太小的点。

表2 轨迹预处理算法

轨迹预处理完成后，把轨迹经过的航点关联起来。对于每一条轨迹，如果按照时间顺序依次经过了A、B两个航点，便认为A、B两点存在联系，将A指向B的有向边权重加一。如表3中算法所示，（1）首先初始化航道图，（2）对于数据集中的每一条轨迹，（4～5）遍历轨迹中的每一个点，（6～10）如果航迹中当前点所属于的航点与之前点所属的航点不同，则将两点对应的航点关联起来，权值增加（7）。

定义2 对于轨迹trajectory和航点Q，若在trajectory上的任意一点P，该点距离航点Q的距离小于θ，则认定轨迹trajectory经过航点Q，如式（2）、（3）所示。

在得到的有向加权图中，两个航点之间的边权重越大，说明存在的联系越密切，从一点驶向另一点的可能性就越高。

表3 航道提取算法

航点之间的联系建立之后，需要对边的权重做归一化处理，归一化后边的值表示流动的概率，概率大小与权重正相关，权重越大，概率越高，从任意一点出发的所有的边权重和为1。

4 实验与分析

本文实验所用计算机为通用型计算机，CPU型号i7-4700，内存16GB-DRR3。实验数据集为公开AIS数据，选取南海海域西至113.5°E，东至114°，南至21.9°N，北至22.4°N，共20万条数据。如图2所示，观察数据集可发现主要包括两条航道，从点A至B和从A至C，本实验将航道从AIS信息中提取出来，并以有向加权图的形式予以表示。

图2

4.1 数据预处理

在获得的公开AIS数据中，存在许多错误数据和无法使用的数据，需要对数据进行预处理。预处理包括两部分：对错误数据的剔除和对轨迹的预处理。

首先将数据中航速过高、经纬度不在正常范围内的数据进行过滤处理，其次对轨迹中前后两点时间戳的差太大的数据进行筛除。

4.2 航点提取

实验中网格边的选取为Δlon=Δlat=3θ，θ为0.008°，α为80，对所选区域分网格进行航点提取，效果如图4所示，提取到航点后，将距离航点θ以内的点清除掉，如图5所示，只剩下3.75%的点，说明航点代表了大部分的点，包含了航道的主要信息。也就是说，本次提取到的航点可以作为航道的关键点使用。

图3

4.3 航道提取

在已得到的航点的基础上，利用轨迹信息将航点之间的边补充完整，形成有向加权图。

如图4所示，黑色线表示航点之间的联系，线段的粗细表示权重大小，这与图2中表现出的航迹点密度一致。已提取的航道中航点过于密集，不利于进行下一步的使用，需要进行压缩处理，删除中间部分冗余航点。本文实验首先根据每个点的航向提取出局部公共航向，将垂直于公共航向且邻接的航点合并，形成一条按航向分布的航点线。然后采用道格拉斯算法对合并后的航点进行压缩，只保留两端和中间曲度较大的航点信息。

图4

图5

如图5，当船舶在航道中沿1→2→3→6→5→4和10→9→8→7→6→5→4方向航行时，对于船舶未来方向的预测是容易的，只需沿着连接航点的道路前进即可，终点都是4位置。反之，当沿反方行航行，尤其是到达点6时，未来航向的预测有两种可能，即驶向点3或驶向点7，本实验中其概率分别为 p（6→3）=w（6→3）/（w（6→3）+w（6→7））=13%和 p（6→7）=w（6→ 7）/（w（6→3）+w（6→7））=87%。

5 结语

本文借鉴了基于点的航道提取算法和基于轨迹的航道提取的算法的优点，提出了一种基于网格的航道模式提取算法。此算法复杂度低，可应用于特定区域航道模型的快速提取，且得到的有向加权图可进行船舶未来运动模式的预测。

随着我国对外开放水平的提高，海运安全也变得越来越重要。航道的提取，海事异常的检测、船舶未来运动模式的预测是充满挑战性的研究课题，针对当前AIS数据量大，人工管理困难的现状，本文提出了一种航道提取算法，可有效表示当前航道模型，基于此可进行船舶未来运动模式的预测，为海事情况的自动化监督提供支撑。

未来的研究工作包括：

1）建立针对海量AIS数据的存储查询底层数据库，可以针对时间和时空快速检索船只的历史信息。

2）建立可有效检测船舶异常行为的模型，进一步提升海事管理的智能程度。