基于轨迹图像特征匹配的渔船轨迹相似度计算和轨迹分类①

徐文进,解 钦,黄海广

1(青岛科技大学 信息科学技术学院,青岛 266061)

2(温州大学 计算机与人工智能学院,温州 325035)

据农业部2019年统计,我国现拥有渔船73.12 万艘,从事渔业的人口为1828.02 万人.全社会渔业经济总产值26406.50 亿元,其中海洋捕捞产值为2116.02 亿元[1].在海洋捕捞给人们带来丰厚经济收入的同时,也使得我国的渔业发展遇到了许许多多的问题.随着出海捕捞成本变高,近海捕捞作业能力增强,导致我国渔业资源衰退较为严重和分布范围变得不均衡.由于渔民作业方式不规范及相关部门监管能力不足,海洋生态环境遭到严重的破坏.另外,作为海洋经济产值的重要组成部分,越来越多的沿海国家开始大力发展海洋渔业的科技信息化和现代化.因此,为了能够解决渔业发展面临的问题和应对其他国家的竞争,我国也开始推动渔业信息化的建设.其中,实现现代化至关重要的过程就是实现数据的采集和合理分析应用.AIS 系统作为渔业监管中不可或缺的手段,它被广泛应用于海上行驶、信息通信和生产作业等方面.另外,该系统能够实时采集海上作业渔船的位置、速度和转向角等数据,并通过卫星与地面基站进行接收和通信,从而实现作业渔船的海上管理和监控.但是,AIS 数据只包含了渔船自身的信息和实时航行数据,并不包含渔船的捕捞方式、作业状态和捕鱼热点等深层次信息,这就要求进一步的通过分析航行状态数据来获取.传统的方法对AIS 数据的研究和挖掘不够深入,但随着人工智能的快速发展,将机器学习应用到渔船轨迹的分析中,对实现渔船行为的实时监控、作业渔场的发现、捕捞强度的挖掘和掌握渔业资源变动等问题具有重要的意义[2].

为了获取渔船之间的作业关系、发现捕鱼热点以及精准预测渔船未来的轨迹,划分渔船轨迹类型成为了至关重要的一步.然而,划分渔船轨迹类型的主要方式就是计算轨迹相似度,文献[3]中谢彬等基于欧式距离对移动对象进行轨迹相似度的计算,该算法适用于获取的轨迹中轨迹点的个数要跟随时间序列一一对应.文献[4]采用弗雷歇算法对船舶轨迹相似度进行建模,然后使用DBSCAN对轨迹进行聚类,最后得到了经典轨迹模型.Zhen 等在文献[5]里整合k-medoids 聚类和朴素贝叶斯分类器,实现了船舶作业行为的分类和异常行为的检测.文献[6]使用原始的动态规划算法和DBSCAN 聚类实现了渔船轨迹的快速分类识别.涂刚凯等[7]使用传统的LCSS 算法从海量人员时空轨迹数据中挖掘人员之间的关系,但是最长公共子序列算法出现了时间阈值选取的敏感性问题,并且该算法允许跳过某些轨迹点所以是一种非常粗糙的轨迹相似度度量方法.Lee 等[8-11]使用了多次的轨迹聚类算法,对轨迹段的形状、特征角点、线段角度等进行线性处理来描述相似度,并对渔船的轨迹实现了线性化的分段和聚类.然而,轨迹的切片标准难以确定,很难将轨迹段划分为同类型的片段,这也导致轨迹的分段聚类方法效果不稳定以及计算复杂等问题[12].以上方法虽然都取得了不错的效果,但是均未充分考虑海上捕捞航行轨迹的特点,因而存在种种不足.

本文在对渔船AIS 数据进行可视化之后,发现某些渔船的轨迹是很相似的,这是因为捕鱼区的位置在较长时间内是不会发生变化以及渔船之间存在协同作业的行为.针对这种特点,论文提出了一种基于轨迹图像的相似度计算方法,这种方法使用了图像特征点检测、特征点描述与特征点匹配,然后设定阈值来进行轨迹的分类.通过这种方法使得计算轨迹相似度的方法转换为计算图像相似度的方法,从而使计算效率和速度提高,并且结果可视化.经过划分渔船轨迹之后,可以更好的对轨迹数据进行挖掘,能够有效地发现渔船之间的协作关系、训练分类渔船预测模型.

1 相关概念

ORB 将FAST 算法和BRIEF 算法进行了结合,并在两种算法的基础上添加了图像旋转与尺度不变性以及特征提取速度快的优点[13].首先,它通过FAST 来获取图像的特征点,然后使用BRIEF对特征点进行描述.

1.1 FAST 特征点

FAST (Features from Accelerated Segment Test)是一种快速的特征检测算法.首先,它通过计算随机选取的像素点与其邻域的像素差值,若存在连续数个像素点的灰度值大于预先设定的阈值,即认为该像素点为特征点,但是该特征点不具有旋转不变性[14].针对这一个问题,ORB 算法使用灰度质心法为每个检测到的特征点添加一个主方向.特征点的灰度矩阵定义为:

其中,I(x,y)为点(x,y) 处的灰度值,那么图像的质心C为:

那么质心与特征点之间的夹角定义为该检测点的方向:

另外,将x和y的取值范围设定在半径为r的圆形区域内,即x,y∈[-r,r],这能够提升算法的旋转不变性.

1.2 BRIEF 特征描述符

BRIEF (Binary Robust Independent Elementary Features)用来对特征点进行描述.首先,它在特征点附近随机选取若干像素点,计算这些点对的二值响应值,然后由这些响应值构成特征点的描述符.

在该算法中使用长度为n的二值码串来描述特征点,其中,这个二值码串是由特征点周围的n个像素点对生成的,将这2n个点 (xi,yi),i=1,2,···,2n组成一个矩阵S:

然后,使用邻域方向 θ和对应的旋转矩阵Rθ,构建S的一个矫正版本Sθ,那么:

其中,θ是式(3)中特征点求得的主方向.

2 本文算法

计算轨迹相似度的过程中主要是轨迹特征点检测、特征点描述,最后是特征匹配.图像特征点检测的关键在于角点检测,角点的特性是向任何方向移动像素的变化都很大.本文中使用ORB 特征检测和BF 匹配计算轨迹图片的相似度,其中BF 匹配是一种暴力匹配的方式,它将计算样本图片中的每一个特征点与对照图片中的所有特征点之间汉明距离,然后选择最近邻和次近邻的两个特征点,设定最近邻距离除以次近邻距离的比率小于某个阈值来进行特征点筛选.

假设样本图片的特征点个数为numx,样本某一特征点与最近邻特征点M、次近邻特征点N的距离分别为disM、disN,则阈值η为:

满足阈值η的特征点个数为numy,则相似度ζ为:

为了计算轨迹图像相似度,设计了算法1.

算法1.渔船捕捞轨迹图像相似度算法1) 将渔船AIS 数据转换为可视化图像,图像只保留轨迹,并设定轨迹图像大小;2) 从文件夹中读取轨迹图像,并将轨迹图像转换为灰度图;

3) 使用ORB 特征检测器对轨迹图像进行特征检测,并对特征点使用BRIEF 算法进行描述;4) 使用BF 暴力匹配的方式,将样本图片中的每一个特征点与对照图片中的所有特征点计算汉明距离;η numy/numx 5) 选择最近邻M和次近邻N 两个特征点计算阈值.然后计算满足阈值的特征点的个数占总特征点的比例,此值即为相似度;6) 将相似度满足阈值的轨迹划分为同一类别.

3 实验

3.1 实验数据

渔船AIS 数据来源于浙江省海洋与渔业局,其中渔船均在浙江登记,数据格式如表1所示.由于设备或者其它异常原因会出现一些错误,要对异常、错误或者不符合范围的数据进行分析和过滤.首先设定了渔船的海上航行范围:经度范围[105°,130°],纬度范围[10°,40°].其次设定渔船的速度区间,因为渔船的行为分为:抛锚、捕捞、航行,所以每种行为对应不同的速度区间.根据统计可得,渔船抛锚时的速度接近于0 节,捕捞时的速度为0～5.5 节,正常航行的速度为5.5～12节,所以选择0～12 节作为速度区间.

表1 渔船AIS 数据格式表

如图1,编号为29902的渔船在2016年4月～2016年6月3 个月,渔船的真实轨迹点数据共计18 049 条.

图1 编号为29902的渔船轨迹

3.2 捕鱼热点实验

针对前文所述,本文使用2015年、2016年的渔船数据做了热力图对比,如图2所示.通过实验发现,沿海区域以及远海区域的捕鱼热点变化较小,主要是海洋中部区域有些许变化,捕鱼热点整体呈稳定趋势.

图2 2015年、2016年捕鱼热力图

3.3 实验结果

经过本文中提出的轨迹图像相似度计算方法,可以快速、有效地进行计算和分类,文中选取部分划分类型的渔船轨迹进行比对.由图3、图4、图5所示,渔船轨迹划分类型准确率高,各类型的主要轨迹相同.通过这种方式,也可以清晰获取渔船之间的协作关系以及捕鱼热点的发现.下文中选取两组渔船的轨迹图像,通过匹配特征来验证算法.

图3 A 组部分渔船2016年4月至5月轨迹

图4 B 组部分渔船2016年4月至5月轨迹

图5 C 组部分渔船2016年4月至5月轨迹

如图6所示,选择两组轨迹图像其部分特征点进行特征匹配,并且特征点之间匹配度高.其中,存在某些特征点匹配发生偏移的现象,主要原因在于轨迹图像过于繁杂,导致部分特征模糊.

图6 两对渔船轨迹特征点匹配

本文选择传统的轨迹相似度算法DTW (Dynamic Time Warping)和LCSS (Longest Common SubSequence)作为对照.通过表2可知,在浙江渔船的数据集上,本文算法在时间和准确率上都有较好的效果,其中时间一栏代表一条渔船轨迹与其他渔船轨迹匹配一轮所花费的时间.传统方法的不足之处在于,一方面两者均是动态算法,复杂的计算带来了较大的时间消耗.另一方面,LCSS 只关注于局部匹配,而DTW对噪音和离群点的抑制效果较差.对于本文算法来说,本质是将轨迹点之间的计算转换为图像点之间的计算,这种方法提高了计算效率和准确率.

表2 算法效果对比

4 结论与展望

通过实验验证了本文所提出的图像轨迹相似度算法可以有效并快速地对轨迹进行计算和分类,也验证了捕鱼热点区域随时间变化较小.文中提出的ORB 算法和暴力匹配的方法可以对图像进行特征点检测、描述以及匹配,但是这种方法需要多次实验尝试不同的阈值.另外,由实验结果可发现,处理之后的轨迹图像存在冗余的现象.所以接下来的研究工作,一方面要进一步处理渔船AIS 数据,压缩轨迹数据;另一方面需要尝试改进算法,将人为设定的阈值改为算法设定.