基于海洋遥感图像的无人艇路径覆盖规划算法

曹 毅，程向红，李丹若，刘丰宇

（1.微惯性仪表与先进导航技术教育部重点实验室，南京 210096;2.东南大学 仪器科学与工程学院，南京 210096）

无人艇（Unmanned Surface Vehicle,USV）具有低风险、高速度、自主操作和智能化水平高的特点，越来越多地被应用于海洋搜救、资源勘探、反水雷等覆盖任务中[1]。路径覆盖规划（Coverage Path Planning,CPP）是实现这些覆盖任务的关键。USV 的CPP 技术通常需要解决2 个核心问题：（1）建立精细化的地图模型；（2）设计高效、合理的覆盖路径[2-3]。

在地图建模部分，传统栅格法在路径覆盖的地图建模方面应用最为广泛[4-6]。但是考虑到USV 在海洋环境边界条件多、障碍物复杂且具有方向任意性等多方面挑战，传统栅格法无法保证海岸线与障碍物的精细化提取。在覆盖路径规划方面，当前，常用的路径覆盖算法有A*算法[7]，神经元激励算法[8]，蚁群算法[9]，遗传算法[10]，贪心算法[11]等。但这些算法应用到海洋环境中，仍然存在一些问题，如A*算法在面对大规模海洋区域时，其规划的转弯路径多且计算量过大；而神经元激励算法在进行复杂环境下路径覆盖时，该方法随机性大，且重复率较高。蚁群算法与粒子群算法均是启发于生物界行为而设计的启发式算法，这类算法可以在规划时忽略机器人本身的运动约束，但在算法初期搜索速度慢，需要较高的迭代次数才能收敛，因此算法的实时性不高，且算法程序设计较为复杂，只有在处理小范围环境时耗时较少。贪心算法计算量小且算法简单，但是其在处理全局路径覆盖规划时，易陷入局部最优。

针对上述研究现状存在的不足，提出了一种基于海洋遥感图像的无人艇路径覆盖规划算法。首先，提出了一种基于改进YOLO V3 的目标检测与图像处理融合的地图建模算法。该算法将海洋遥感图像作为USV 路径覆盖的输入，并将遥感图像中障碍物的角度信息引入到地图模型中，最终建立精细化的二值地图模型。该模型与栅格地图相比，考虑了障碍物的角度信息，地图模型更精细。其次，提出了一种基于旋转光束与贪心算法的路径覆盖算法，该算法将完整的覆盖路径分为直行路与转弯路径。并分别基于路径长度、转弯拐点数目优化两类路径。在规划转弯路径时，还将已获得的直行路径作为约束，引入贪心算法，将贪心算法的全局优化问题转化为局部优化问题，解决了贪心算法易陷入局部最优的缺陷。总的来说，本文将覆盖路径规划与目标检测、图像处理融合，构建了直接基于遥感图像的USV 路径覆盖框架，提高了无人艇执行覆盖任务的作业效率。

1 地图建模

1.1 地图模型信息描述

复杂海洋环境遥感图像包含许多不可覆盖区域，这些区域包含信息的类型各不相同。如图1 所示，浅绿色的区域为港口等基础设施(RN)的位置，该区域可通过测绘技术得到，视为已知信息。深绿色的区域为海面上的船舶障碍物(RO)，RO是未知的信息且具有不同的尺寸和方向，这些特点给精确地图模型的建立带来困难；黑色曲线框住的区域(RT)是待覆盖区域，定义为一个闭合多边形。假设本文算法的应用背景为无人艇小范围的巡逻与测绘。应用场景包含：包含多种密集障碍物的小范围远海区域，包含复杂海岸线与障碍物的小范围近岸区域。

图1 遥感地图信息示意图Fig.1 Schematic diagram of remote sensing map information

1.2 地图建模算法

地图建模的重点是精准获取RO障碍物的位置信息，为此，提出了一种基于改进YOLO V3 的旋转目标检测算法。传统YOLO V3[12]的模型输出(x,y,w,h)四维信息，即中心点的坐标和外接矩形的长、宽。该坐标只能预测目标的外接矩形框，而不能输出目标最小面积的外接矩形框。如图2 所示，在海洋遥感图像中，船舶障碍物的方向是任意且排列紧密的。如果使用传统YOLO V3 检测船舶障碍物，则相邻两艘船舶的交并比过大，会出现目标检测召回率降低且目标框与船体不拟合的问题，最终导致地图建模不精细。

图2 不同输出矩形框的检测结果Fig.2 The detection results of different output boxes

为了解决上述问题，在保证传统YOLO V3 模型预测速度情况下，本文重新定义了最小面积的外接矩形框：（tx,ty,tw,th,tθ）。其中，（tx,ty）为矩形框中心点的坐标，tw和th为矩形框长边或短边的长度，当x轴向上正方向旋转时，遇到的第一个边即为tw，则另一侧为th所在的边，旋转角度为tθ，取值范围为[-90 °,0 °]。具体定义如图3 所示，粗红线为tw，另一侧为th。定义的角tθ是tw与x轴正方向之间的夹角，其取值范围为[-90 °，0 °]。

图3 最小面积的外接矩形框示意图Fig.3 Schematic diagram of external rectangular with minimum area

对于改进后的YOLO V3 网络的新输出矩形框，需要设计网络的角度损失函数。为了缩小学习区间，让原始的tθ从-45°开始预测，取值范围设置为(0 °,-45°]和[0 °,45°），将原始学习区间缩小一倍，降低学习难度，重新定义后的角度损失函数为：

模型总损失函数包含定位损失、角度损失、置信度损失和类别损失：

其中，λcoord为训练权重，设为0.5,S为网格单元格数，B为锚框数，表示第i个网格的第j个锚框是否负责预测该目标，如果是，则=1，否则=0,Ci表示目标分类，Pi表示分类概率。

如图4(a)所示，当通过改进的YOLO V3 获取RO障碍物的信息及通过测绘手段获取RN等其他区域信息后，需要利用归一化色差原理对处理后的图像进行二值化，并建立如图4(b)所示的地图模型。归一化色差原理是根据颜色特征对图像进行二值化，提取图4(a)中的绿色区域。其中，RO与RN区域定义为1，待覆盖的海洋区域定义为0。如式(3)(4)所示：

图4 遥感地图建模过程Fig.4 The remote sensing map modeling process

其中R，G和B分别表示彩色遥感图像的红、绿和蓝3 个通道，τ为归一化色差，Mapij表示处理后的地图模型信息，0(白色部分)表示待覆盖区域，1(黑色部分)表示不可覆盖区域。固定阈值为160，其值通过对遥感图像的像素分析后得到。

2 路径覆盖规划算法

基于已建立的海洋地图模型，提出了一种基于旋转光束和贪心算法的CPP 算法。在有障碍物的不规则多边形区域中，USV 的覆盖路径会被障碍物或凹凸部分打断。因此，本文将覆盖路径分为两部分：直行路径和转弯路径。由于USV 在转弯时必须先减速后加速，转弯耗时比直行要多，所以有必要限制转弯次数，基于此本文采用旋转光束算法，以最短路径长度和最小转弯次数为目标优化直行路径。然后利用贪心算法以最短长度为目标将直行路径形成的节点进行连接，最终得到完整的覆盖路径。

2.1 基于旋转光束的直行覆盖路径规划

如图5 所示，采用前后折返运动作为USV 的覆盖模式。该种覆盖模式使得前一直行路径总是平行于下一直行路径，因此初始直行路径平行于最终直行路径。本文将这些平行直行路径定义为一系列平行光束。通过改变平行光束的斜率和截距参数，使光束组旋转。最终得到一组以转弯次数与路径长度为约束的避障直线路径。图5 中黑色网格代表障碍物，白色网格代表待覆盖区域。红色虚线表示直行路径，蓝色虚线表示转弯路径，两者共同构成完整覆盖路径。

图5 不同斜率的直行光束组Fig.5 The group of straight paths with different slopes

如图5 所示，一组红色平行直线路径定义如下：

其中，φ为直线的斜率，或，θ1=1...m，θ2=1...n，定义ϕ1和ϕ2为直行路径的水平轴和垂直轴的截距，n为垂直轴的网格总数，m为水平轴的网格总数。j为二值地图中划分窗口的总列数，i为二值地图中划分窗口的总行数，网格地图由式(4)求得。

其中，w为USV 的作业宽度，在图5 中，n=7，m=6。

定义好直行路径方程后，通过调整φ与ϕ值，使得直行路径被障碍物打断最少，从而减少整体的路径耗时。因为当直行路径障碍物打断时，转弯点的数量会增加，耗时也随之增加。限制转弯次数的代价函数定义由以下公式给出:

其中，Mapij为式(4)得到的地图模型，L∩Mapij=1，=1为若直行路径L通过地图中的障碍物，则其通过第i行，第j列的窗口格数目记为1，l'为通过障碍物的总窗口数目。

此外，限制路径长度的代价函数定义如下：

其中，L∩Mapij=0，lij=1为若直行路径L通过地图中的待覆盖区域，则其通过第i行，第j列的窗口数目lij记为1，l为通过覆盖区域的总窗口数目，δmin为长度代价函数，μ∈{μ1，μ2}为长度参数。

2.2 基于贪心算法的转弯覆盖路径规划

得到规划直线路径后，由式(5)定义的每条直行路径的截距决定直行路径的顺序。如图6 所示，采用“从左到右，从上到下”的规则，生成平行线段的排列顺序列表。该规则定义每条直行路径有两个邻域：一个是属于相邻直行路径列表的线段，另一个是不属于同一列表的线段。不属于同一列表的直线路径段是那些被障碍物打断的，如：线段(11-12)与(13-14)。转弯路径是在相邻节点之间产生的。图6 是贪婪算法的原理图。基于最短长度原则，利用贪心算法来生成转弯路径。传统的贪心算法不考虑路径的全局最优性，只考虑局部路径[13]的最优解。但本文在前一节中，通过旋转光束算法得到了直行路径，以得到的直线路径为约束，可连接得到转弯路径。通过已获取的直行路径本文将贪心算法的全局最优覆盖路径问题转化为直行路径节点连接的局部最优问题。此外，本文引入长度代价函数对贪心算法进行进一步约束，来限制贪心算法的节点搜索长度，长度代价函数如下:

其中，D为贪心算法的搜索距离，其值小于节点a与节点b之间的最小欧几里得距离。

在图6(a)中，不加直行路径约束时，贪心算法规划的转弯路径复杂、效率低下，且转弯次数较多。在图6(b)中，增加直行路径约束时，贪心算法规划的转弯路径简单，可以实现局部优化。

图6 贪心算法原理Fig.6 The principle of greedy algorithm

3 仿真实验与结果

在本节中，仿真分为两部分。首先进行地图建模仿真。该部分的仿真结果可以为后续CPP 算法的仿真提供精细的输入；其次，对CPP 算法进行仿真。为了验证两个算法在小范围复杂海洋环境下的可行性和高效性，本文选择了两种典型的复杂海洋环境作为仿真对象。第一类是包含多种密集障碍物的远海区域的遥感图像(图7(a))；第二类是包含复杂海岸线与障碍物的近岸区域的遥感图像(图7(b))。

图7 目标检测结果对比Fig.7 The comparison results of target detection

3.1 基于YOLO V3 的地图建模算法仿真

仿真的硬件环境为Intel 系列CPU i7，GPU:GeForce GTX3080Ti。系统环境为Ubuntu 18.04。为了公平起见，本文算法与比较算法的训练的参数如表1所示。

表1 训练参数设置Tab.1 training parameters setting

算法的评价指标为平均精度、输出框面积比、检测时间和召回率。输出框面积比用来衡量地图建模精准度，其公式如下所示：

其中，Sv为船舶输出框的面积（即地图模型中的黑色区域），S为遥感图像的总面积，o为输出框的面积例。o值越小，地图模型的精度越高。

目标检测仿真结果如图7 所示。图7(a)和图7(c)为改进后YOLO V3 的检测结果，图7(b)和图7(d)为改进前YOLO V3 的检测结果。表2 为在包含200 张图片的验证集上计算得到的平均精度与召回率结果。

从表2 可以看出，改进后的YOLO V3 的平均精度比改进前的YOLO V3 提高了12.1%，召回率提高了18.6%。从图7 中可以看出，图7(a)中有9 个船舶障碍，图7(b)中有4 个船舶障碍物都被准确检测到。这证明了YOLO V3 的改进策略在海洋遥感图像船舶检测上是有效的。

表2 与改进前YOLO V3 结果对比Tab.2 results compared with the original YOLO V3

此外，需要将检测完成后的图像利用归一化色差原理处理为二值图，建立可输入CPP 算法中的地图模型。二值化地图模型结果分析如表3 所示。

表3 o 值对比结果Tab.3 comparison results of o

从表3 可以看出，在2 个仿真场景中，利用改进的YOLO V3 的检测结果建立的地图模型，其o值都小于改进前的YOLO V3。在2 个仿真环境中，o最多下降了4.91%。综上所述，改进的YOLO V3 能够更准确地提取海洋遥感图像中的船舶障碍物且可为CPP算法提供更精细的地图模型。

3.2 路径覆盖算法仿真

路径覆盖算法的输入地图模型为图7(a)与图7(c)的二值图像，其大小为800 像素×800 像素；路径覆盖应用场景为：USV 资源探测，其传感器扫描宽度为：10 像素。

算法的评价指标为覆盖率、重复率、路径长度、计算时间和转弯拐点数。由于USV 在转弯时必须减速和加速，所以转弯时的平均速度要低于直线行驶时的平均速度。因此，拐点越少，USV 的路径覆盖效率越高。具体公式如下所示：

其中，Cr为覆盖率，Rr为重复率，S为目标海域总面积，Sn为覆盖面积，Sr为重复覆盖面积。

为了验证旋转光束+贪心算法（本文算法）融合的优越性，选取了“旋转光束+概率路线图[14]”算法，“旋转光束+A*”算法作为对比，3 种算法依次记为：M1，M2，M3。其可视化结果如图8 所示，在图8 中选取了两个场景进行对比，图8(a)与图8(b)为M1 的仿真结果，图8(c)与图8(d)为M2 的仿真结果，图8(e)与图8(f)为M3 的仿真结果，其中彩色线条为规划的路径，黄色虚线框为重复率较高的区域，横坐标和纵坐标单位为像素。

图8 所提算法与其他算法对比结果Fig.8 The comparison results between the proposed algorithm and other algorithms

从图8(a)到图8(f)中可以看出，由于概率路线图与A*算法的随机性较大，M2 与M3 算法规划的路径具有更多的重复率较高的区域。客观分析结果如表4所示，表格中的数据为取2 个地图模型路径覆盖仿真结果的平均值。从表4 中可以看出，在覆盖率方面，M1，M2，M3 算法规划的路径覆盖率均达到100%。在重复率方面，本文算法的平均重复率为2.05%。与M2，M3 算法相比，平均降低了2.95%。验证了本文所提的CPP算法在复杂海洋环境中具有较高的覆盖率和较低的重复率，具有较好的可行性。在路径长度方面，本文算法比M2，M3 算法的路径长度要少，平均减少30%，验证了本文算法具有更高的效率。综上所述，在2 个不同仿真场景中，本文提出的算法模型在平均覆盖率，平均重复率，平均长度，平均转弯拐点与平均计算耗时上均更具优势。

表4 不同模型的结果对比Tab.4 comparison results of different models

此外，为了证明所提算法的优越性，本文选取了文献[9]基于栅格地图的神经元激励算法作为对比，图8(g)与图8(h)为基于神经元激励的CPP 算法的仿真结果，其输入地图模型为栅格图，网格大小为10×10。仿真图中，红线为规划路径，黄色区域为重复覆盖路径。仿真结果的评价指标对比如表5 所示。

从表5 中可以看出，在覆盖率方面，本文算法和基于神经元激励的CPP算法规划的路径覆盖率均达到100%。在重复率方面，本文算法的平均重复率为2.05%。与基于栅格地图的神经元激励算法相比，降低了1.75%。本文提出的CPP 算法在复杂海洋环境中具有较高的覆盖率和较低的重复率，具有较好的可行性。在路径长度方面，本文算法基于栅格地图的神经元激励算法的路径长度要小，平均减少9.3%。在转折点数量上，该算法的转折点数量比基于栅格地图的神经元激励算法少，平均减少71%。综上所述，本文提出的CPP算法在复杂的海洋环境中具有较短的长度和较少的转弯拐点，与基于栅格地图的神经元激励算法相比，该算法效率更高。在计算耗时方面，该算法在2 种复杂海洋环境下的计算时间均小于基于栅格地图的神经元激励算法，本文算法计算效率更高。

表5 与基于栅格地图的神经元激励算法结果对比Tab.5 results compared with the neuron excitation algorithm based on grid map

4 结论与展望

本文提出了一种基于海洋遥感图像的无人艇路径覆盖规划方法。该算法将CPP 技术与遥感图像目标检测技术和图像处理技术相结合，构建了适用于小范围复杂海洋环境遥感图像的USV 路径覆盖系统。针对精细化环境建模问题，提出了一种改进的YOLO V3 算法，通过增加角度信息来增加目标框输出维数，从而帮助CPP 建立更精确的地图模型。此外，CPP 算法将全覆盖路径分为直行路径和转弯路径，并根据路径长度约束和转弯次数约束进行计算。该算法规划的路径在时间、适用性、可行性和计算效率方面具有一定的优势。CPP 算法在处理大规模海域作业时尚有局限性。未来针对大规模海域高效作业可考虑多USV 协同技术。