基于AIS航迹和Douglas-Peucker算法的航线自动生成方法研究
2014-02-28张树凯杨家轩史国友
张树凯，杨家轩, 蔡 垚，史国友
(大连海事大学 航海学院，辽宁 大连 116026)
0 引 言
航行计划是指船舶在接受航次命令后，拟定的从一个港口航行到另一港口的过程中，有关航行安全的具体措施与对策[1]。而航线设计则是其中的一项重要内容。在航次开始前，二副应依据航海图书资料以及所查阅的海区的信息或他船的具体航行经验，确定并预画航线。超过1 500 n mile的航线还应确定是否使用大圆航线和气象定线等[1]。
长期以来，航线设计主要靠人工分析海图、查阅航海图书资料，手工绘制航线，这种传统的方法存在效率低、设计质量依赖于工作人员业务水平和工作态度等局限[2]。航线自动生成的研究，是根据起航点与目的地之间的航海条件寻求一条最安全、最经济的航线。李源惠，等[3]在研究可航行与连通性、方格序列折线化等问题基础上，提出了基于网格模型的进行ECDIS航线设计的方法。但该方法仅仅是基于海图数据的，没有考虑水文气象因素对航线设计的影响，应考虑推荐航线和网格模型组合的算法，因为在某些航区的短航段，出于避风等考虑，还要决定是否采用气象定线或者避风、避逆流等措施[1]。何立居，等[4]通过研究网格划分、搜索策略、信息更新等问题提出了基于蚁群算法的航线自动生成算法。但该方法产生的初始航线锯齿较多，需要根据不同的情况改变蚂蚁的数量和迭代次数，否则将曲线平滑后产生的误差较大，另外该方法也未考虑推荐航线气象航线等。汪柱，等[5]根据绕行障碍区的航路二分性特点，定位左右子节点并建立航路子二叉树，提出了基于航路二叉树的航线自动生成方法。但航路二叉树绕行障碍区处理不完备，效率低。
AIS基站存储了大量AIS信息，如果能够充分利用这些信息，从中提取已被实际航行证实可航行的航线，则可为船舶的驾驶员设计航线提供重要参考，以便寻找到一条安全、经济的航线，同时这也符合航线设计参考“所查阅的海区的信息或他船的具体航行经验[1]”的思想。笔者在研究AIS信息编码与解析、数据清洗异常点、Douglas-Peuker压缩的基础上提出基于AIS航迹的航线自动生成的方法。该方法使用Douglas-Peuker算法对原有的AIS航迹点进行压缩，通过压缩将冗余的航迹点去除，根据不同比例尺下的阈值设定从AIS航迹点中提取关键的转向点。AIS航迹点是真实航行情况的客观反应，在航线设计和实际航行中已经包含了气象、水文、安全、经济等各方面因素，根据两点之间直线最短的原理，从实际航线中提取关键转向点生成新航线的方法提高了经济效益。由于在压缩航迹的过程中将曲线变直线可能穿过障碍物或危险物，因此，初次提取航迹点生成的航线需要充分利用电子海图信息对生成的航线进行点、线、面的海图要素检测确保航海安全。
1 AIS信息的提取
随着AIS(船舶自动识别系统，Automatic Identification System)应用技术的发展，船载AIS和AIS基站也迅速增多。由于AIS受外界的干扰较小，现在已广泛应用在船舶通信、船岸通信、海上搜救和海事调查等方面。
1.1 数据格式转换
根据IEC61162-1国际标准规定，AIS只能传输可打印的AIS字符，字符的有效范围是0X20到0X7E之间，在这个范围内又将字符分为保留字符、有效字符和未定义字符[6]。保留字符是指传输语句中用于控制语句格式的关键字；有效字符是指除保留字符外所有可用于打印的ASCII字符；未定义字符不允许直接传输使用。AIS的每一条记录由起始符(“﹩”或“!”)开始，以语句结束符(
表1 AIS记录规范Table 1 Format of AIS records
经过封装后的AIS数据经过高级链接HDLC(High-Level Data Link Control)后进行不归零倒置NRZI(Non Return to Zero Inverted)编码，再进行GMSK(Gaussian Filtered Minimum Shift Keying)调制，插入同步和停止位后通过VHF频率传输[7]。因此首要工作是根据IEC61162-1标准和ITU 1371-1协议将AIS暗码转换为明码。
1.2 AIS信息的数据清洗
AIS信息包括静态信息、动态信息和与航次有关的信息。动态信息的数据量一般比较庞大，而且并不是所有的信息都是可为我们所用。因此在AIS信息入库前需要按照数据清洗的原则对AIS信息进行预处理，包括：
1)不完整的数据，删除AIS记录中不完整的数据，例如MMSI为0的记录。
2)错误的数据，例如在时间连续的记录中出现经纬度变化较大的点，我们称之为异常点，应采用滤波的方法予以剔除。
3)重复的数据，例如船舶锚泊时AIS的记录表现为连续的时间记录经纬度几乎不变，为减小数据的重复，应只保留一条锚泊记录。
1.3 数据库的建立
SQLite数据库是一款遵守ACID的关联式轻型数据库，它的设计目标是嵌入式的，处理速度比Mysql、PostgreSQL这两款开源世界著名的数据库管理系统快。具有开源、轻便、零配置、处理速度快等诸多优点。为了便于嵌入ECDIS系统显示，解析后的AIS数据采用SQLite数据库存储。
AIS记录包含了丰富的船舶位置信息。每条记录都包含了每条船舶唯一的海上移动通信业务标识码MMSI(Maritime Mobile Service Identify)，为了便于区分不同船舶的AIS航迹，以MMSI作为一个字段。由于Douglas-Pecker算法针对按时间排序后的航迹点进行压缩，因此选取经度，纬度，时间，作为数据库表的另外3个字段。同时为了便于航海人员根据船型、船长选择与本船特征类似的航迹作为参考，将船型、A、B、C、D作为数据库表的另外5个字段，数据库如图1。这样，航行人员便可以以起始点、船型、船宽、船长、季节为条件选择和本航次计划参数相似的航迹作为参考。
图1 AIS数据库Fig.1 AIS database
2 AIS航迹点的压缩
2.1 大地坐标系到墨卡托投影变换
AIS记录中的经纬度都是以地理坐标点的形式存储的，这样可以保证地理位置上的绝对唯一。电子海图数据的显示过程是把地理坐标值换成某一基准纬度的墨卡托坐标值，然后再由墨卡托坐标转化为屏幕坐标进行显示。在对AIS数据处理之前应先把每条记录中的经纬度坐标转变为墨卡托坐标。
地心大地坐标系的原点为地球质心O，3个基准面分别是赌球椭球面、椭球赤道面和起始大地子午面，在该坐标系中，某点P的经度λ为P点子午圈平面与起始子午面构成的二面角，纬度φ为过P点的椭球法线与赤道面的夹角。根据等角正圆柱投影的原理，墨卡托正投影的公式为：
(1)
式中：(x,y)为P点的墨卡托坐标；r0为基准纬度纬圈半径；q为等量纬度，即：
(2)
(3)
式中：a为地球椭球长轴半径；e为椭球第一偏心率；φ为基准纬度。
2.2 Douglas-Peuker算法
一个线状物体总是由其上的采样点描述的，采样点越密集，则描述原始物体的能力越强，但随之而来的是数据量的急剧增大，对数据管理和分析都带来极大的困难。例如，将宁波港2011年1个月的AIS数据导入到ECDIS平台，在进行海图平移和放大缩小时系统处理速度明显变慢，若将宁波港1年的AIS数据导入得到ECDIS系统，在进行海图的平移和放大缩小等操作时，系统等待时间多达30 s。因此Douglas-Peuker算法的核心思想是用尽可能少的点描述原始事务，并保证在容许的误差限之内再现原始形态特征。
Douglas-Peuker算法是对垂距限值算法的改进，是一种常用的线要素综合方法和曲边形逼近算法，具体的实现过程如图2。
图2 Douglas-Peuker算法提取特征点Fig.2 Extracted feature points of using Douglas-Peuker
1) 设离散的点分别为P1(x1，y1)，P2(x2，y2)，…，Pn(xn,yn)，设A=P1(x1，y1)，B=Pn(xn,yn)，用线段连接AB。
2) 在AB线段范围内寻找到AB最大距离的点，记为C。
3) 判断C点到AB的距离是否小于设定的阈值，若小于阈值，则用AB代替AB之间的所有点，循环结束，否则用线段连接AC和CB。
4) 同样按照步骤(2)所述分别寻找在AC和CB之间到线段AC和CB之间最大距离的点，假设为图2中的D点，判断D点到线段AC的距离是否小于阈值，若是，则用线段ACD代替原始点，否则用线段连接AD、DC、CB，继续循环。
2.3 AIS数据压缩
将Douglas-Peuker算法映射到航海领域，线状物等价于要生成的航线，每条AIS记录中的经纬度位置等价于采样点，则航线自动生成方法的内涵就是在密集的AIS信息采样点中提取出能描述原始航迹的数量最少的点即关键的转向点，将提取出的点连接成线称为航线。
在存储AIS航迹的SQLite的数据库中根据设定的条件选择和本船自然条件相类似的历史航迹，例如“select * from Track where MMSI = 412 454 940”，将数据库Track表中MMSI为412 454 940的船的AIS船位采集点提取出来，将经纬度转换为墨卡托坐标后变为采样点，用Douglas-Peuker算法对采样点进行压缩，通过设定合适的阈值即可得到压缩后的少量的点，称之为转向点。将这些转向点连接成线即可得到初步生成的航线，完整的实现流程如图3。
图3 航线生成流程Fig.3 Workflow of automatic routing
原始的AIS航迹由于已经避开危险物，因此是安全可靠的。在经过Douglas-Peuker算法压缩之后由于将曲线变为了直线，生成的直线即初次生成的航线有可能跨越危险物，为了确保安全需要充分利用电子海图对初次生成的航线进行航线检测，检测的内容包括航线是否穿越孤立危险物、暗礁等点物标，海底电缆、输油管道等线物标，陆地、禁航区等面物标。若检测为安全则初次航线为最终的自动生成的推荐航线，若不安全则需要修正航线。如图4，假设初次生成的航线为ABCD，在初次航线中检测出的危险物标为E，则以E为圆心，以2 n mile为半径做圆，选择压缩后离危险物两边最近的关键点即B点、C点对圆做切线得到切线BH和切线CG，将切线的交点F定义为新的关键转向点。将新的关键转向点连接成直线生成新的航线ABFCD并对新的航线进行航线检测直至安全。
图4 航线修正示例Fig.4 Example of route correction
2.4 阈值的参数优化
在Douglas-Peuker算法中通过衡量点到直线的距离是否大于阈值来决定点的取舍，通过2.2节中描述的步骤可知当阈值等于0时数据压缩比最小，压缩后的直线和原直线相同，当阈值等于∞时压缩比最大，压缩后的曲线只保留起点和终点，曲线内点全部被剔除。
根据大量实验操作的结果，当比例尺为1∶800 000时将阈值设为2 000压缩的效果最理想，当海图的比例尺变大时，阈值可适当变小，当海图的比例尺变小时，阈值可适当变大。
3 算法实现与实例分析
以ECIDS为显示平台，将算法应用到实际中去。由于AIS数据限制，仅以琼州海峡VTS中心收集的2006年9月和10月的全部数据为例，如图5。
图5 航线参数设置Fig.5 Route setting
首先设置航路的起始点经纬度，船舶的船长、船宽和船型参数，以及航行的季节。算法将自动在SQLite数据库中搜索与设置参数相符合或相近的AIS航迹。检索后符合要求的航迹将在列表中一一列出，航线人员可在搜索结果中进一步挑选，选中后点击“原始航迹显示”可将该船的历史航迹回放，点击“压缩航迹显示”可将该船的历史航迹进行Douglas-Peucker和航线检测并最终生成关键的转向点，点击“导出关键转向点”可将转向点导出。以MMSI编号为412454***的历史航迹为例，将该船舶的AIS数据进行数据清洗后入库，共计得到3 352对有效坐标点，点击“原始航迹显示”将历史航迹显示在ECDIS，如图6。
图6 船舶的AIS历史航迹Fig.6 AIS track of ship
将阈值上限设为2 000，下线设置为800，点击“压缩航迹显示”,后进行Douglas-Peuker和航线检测运算，经过运算后得到7对转向点，压缩率高达99.79%，大大节省了AIS数据库的空间。点击“导出关键转向点”将这7对转向点导出。显示在ECDIS上，如图7。
图7 从AIS航迹中提取的航路Fig.7 Route extracted from AIS track
4 结 语
通过对照AIS历史航迹在电子海图上的显示和压缩后的数据在电子海图上的显示，虽然压缩率高达99.79%，但压缩后的数据仍能够真实而完整的显示原始的形态。基于AIS航迹的航线自动生成算法由于数据来源于真实的船舶航迹，船舶在经过特殊的地理位置时会查阅相应的航海图书资料和气象水文资料等帮助船舶驾驶员设计航线，而船舶的历史轨迹能够为船舶驾驶员提供重要参考。经过实例证明笔者提出的基于AIS航迹的船舶自动生成算法是切实有效的，但笔者只针对1条船的AIS航迹进行了Douglas-Peuker运算从而提取出转向点生成航线，在选择AIS航迹时为了更加适合本船特性，需要进行人工干预，找出和本船船长、船型、季节等特性
和本船相似的AIS航迹。下一步的工作将提取多条AIS航迹进行Douglas-Peuker运算并采用模糊聚类的方法将多条航迹汇合形成推荐的航迹带，这样，在船舶设定好季节和船舶参数后，自动生成算法将在航迹带中找出最佳适合船舶的航迹作为推荐航线。
[1] 郭禹.航海学[M].大连:大连海事大学出版社,2005.
Guo Yu.Marine Navigation[M].Dalian:Dalian Maritime University Press,2005.
[2] 夏雷,姜汉新,汪柱.电子海图最优航线自动生成算法的改进[J].海洋测绘,2012,32(2):43-45.
Xia Lei,Jiang Hanxin,Wang Zhu.The improvement of automatic routing algorithm based on electronic chart[J].Hydrographic Surveying and Charting,2012,32(2):43-45.
[3] 李源惠,潘明阳,吴娴.基于动态网格模型的航线自动生成算法[J].交通运输工程学报,2007,7(3):34-39.
Li Yuanhui,Pan Mingyang,Wu Xian.Automatic creating algorithm of route based on dynamic grid model[J].Journal of Traffic and Transportation Engineering,2007,7(3):34-39.
[4] 何立居,李启华.基于蚁群算法的航线自动生成研究[J].中国航海,2009,32(3):71-75.
He Liju,Li Qihua,Automatic generation of ship route based on ant colony algorithm[J].Navigation of China,2009,32(3):71-75.
[5] 汪柱,李树军,张立华,等.基于航路二叉树的航线自动生成方法[J].武汉大学学报:信息科学版,2010,35(4):407-410.
Wang Zhu,Li Shujun,Zhang Lihua,et al.A method for automatic routing based on route binary tree[J].Journal of Wuhan University:Geomatics and Information Science,2010,35(4):407-410.
[6] International Electrotechnical Commission.Maritime navigation and radio communication equipment and systems Digital interfaces [EB/OL].(2006-3-20) [2013-10-10].http://www.iec.ch/.
[7] 初秀民,徐海潮,万剑,等.基于多线程的船载自动识别系统报文解析 [J].中国航海,2011(2):20-23.
Chu Xiumin,Xu Haichao,Wan Jian,et al.Parsing shipborne AIS message based on multithreading[J].Navigation of China,2011(2):20-23.
[8] 张树凯.基于S63标准的电子海图数据保护方案研究[D].大连:大连海事大学,2013.
Zhang Shukai.Research of ENC Data Protection Scheme Based on S63[D].Dalian:Dalian Maritime University,2013.
