基于改进Floodfill算法的田垄视觉导航系统*

谢仕烁，黄伟锋，2，朱立学，杨尘宇，张世昂，付根平，2

(1.仲恺农业工程学院自动化学院，广州市，510225；2.仲恺农业工程学院现代农业工程创新研究院，广州市，510225；3.广东省现代精准农业智能化装备技术研发中心，广州市，510225；4.仲恺农业工程学院机电工程学院，广州市，510225)

0 引言

近年来，我国大部分农作物产量保持增长状态[1-2]，但生产成本增加过快等因素仍然制约着我国农户的利润增长[3]。研究指出，农业自动化对提高农产品的产量和减少劳动力的制约具有一定的积极作用[4]，且机器人自主导航技术已有一定成果[5-8]，因此，农业机器人具备一定的发展前景和意义。

视觉处理技术和卫星定位技术为农业机器人自主作业能力提供了可能[9-12]。导航技术中，卫星定位导航可以提供一定的导航指引，但难以根据实际道路情况等因素进行导航，难以对实际环境做出反应；视觉导航易受光照等环境干扰影响，但其外部信息感知量丰富，因此该方法受到了许多研究者的青睐。

在图像分割方面，高国琴等[13]提出基于K-means算法的温室路径分割方法；田巍等[14]提出基于HSV阈值法的皮肤对象分割方法；Bakker等[15]提出基于2G-R-B方法的作物图像分割方法；Long等[16]使用FCN网络实现了多个对象的分割方法。以上方法均具备一定的分割能力，但在计算负担与分割结果的综合表现上效果欠佳，难以兼顾强分割性和算法简易性。

在对导航计算上，吴刚等[17]提出基于hough法的路径拟合方法，实现了小麦田间的路径计算；李亭等[18]使用扫描法进行路径计算实现了智能车的自主导航；王新忠等[19]使用最小二乘法实现番茄垄间的导航；hough拟合法和扫描法均能产生一定效果，但并无法区分道路类型，其导航效果易受道路笔直程度影响，且机器人无法单独依靠视觉系统针对特定路况执行相应任务。

综上所述，许多学者对图像分割及路径导航计算进行一定的研究试验，取得了一些成果，但机器人导航领域仍然存在一定问题。本文针对Floodfill算法进行路径分割改良，通过对十字法和扫描法进行结合改良，对不同路况使用相应方法进行计算，构建了基于改进Floodfill算法的田垄视觉导航系统，实现机器人视觉导航功能。

1 材料与方法

1.1 算法流程

算法流程如图1所示，流程分为三个部分：第一部分，从摄像头获取垄间图像并对图像进行预处理操作；第二部分，使用Floodfill算法分割路径图像，将路径图像输入十字法进行路径情况分类；第三部分，在已知路径情况的基础上应用相应算法进行导航信息计算。

图1 导航算法流程图

1.2 图像预处理

在图像处理领域中，常用的颜色空间有RGB颜色空间(Red红色，Green绿色，Blue蓝色)、HSV颜色空间(Hue色相，Satuation饱和度，Value明度)。其中，RGB颜色空间采用R(红)、G(绿)、B(蓝)三个通道来表达颜色，HSV颜色空间采用H(色相)、S(饱和度)、V(明度)来表达颜色，两种颜色空间之间可相互转换。

Floodfill算法需要进行颜色相似程度判断，具有寻找相似颜色的需求。在HSV色彩空间中，若两种颜色相似，其色相也会相近。因此，通过H(色相)参数寻找相似颜色的方法较为简单且无需大量运算，受光照等外部干扰的影响相对较小，本方法使用HSV颜色空间进行计算。

为了获得更加精确的计算结果，在计算前对图像进行高斯模糊处理，对图像进行滤波。

1.3 路径分割

1.3.1 改进Floodfill算法

本文使用Floodfill算法分割道路信息，为后续导航计算算法提供数据。Floodfill算法又称漫水填充算法，该算法的计算方法与水流动的规律相似。首先输入种子点(Seed Point)的坐标，将种子点作为“水源”，向四周符合漫延条件的位置漫延。漫延条件为：该位置与本位置的数值的相似程度符合要求。漫延方式有4方向漫延法和8方向漫延法两种，4方向漫延法规定水流只能向当前位置的“上、下、左、右”4个方向流动，而8方向漫延法则在4方向漫延法的基础上增加了“左上、右上、左下、右下”四个方向。图2为同一种子点下，不同漫延规则的计算结果。图中，黑格为不符合漫延条件的像素，灰格为被漫延区域，白格为未漫延区域。经测试，8方向漫延法具有较好的效果，故采用8方向漫延法。

(a)4方向漫延法

机器人正常行驶过程中，路径图像的中下区域包含道路信息的可能性较高。基于该先验知识，可以使用固定点法进行道路分割：选取图像底部中点作为种子点进行Floodfill算法的计算，分割结果如图3(b)所示。

(a)路径图像

试验发现，固定点法选取种子点的分割效果尚好，但若固定点处存在塑料袋等干扰物体，路径信息将被错误分割，如图4(b)所示。针对该问题，本文使用点迭代法进行改进。

(a)测试图片

点迭代法通过评价的方式选取合适的种子点，运行流程如图5所示。

图5 点迭代法运行流程

第一步，选取图像底部中点为准种子点的起始点。

第二步，使用准种子点进行Floodfill算法运算。

第三步，对本次计算结果进行评价，评价合格则进入输出分割结果，不合格则向上偏移准种子点并回到第二步进行下一次迭代。

图4(c)为使用点迭代法的分割结果。试验验证，点迭代法具备更好的鲁棒性，更适合在实际路况中使用。

1.3.2 滤波处理

道路信息虽然已经被计算出来，但仍包含一定噪声，噪声干扰将对后续的导航信息计算造成一定负面影响。针对该问题，本文引入腐蚀算法与膨胀算法对路径分割结果进行进一步滤波。

腐蚀算法与膨胀算法采用矩阵对图像进行运算，对图像进行形态学运算。腐蚀算法作用为收缩图像，其效果如图6(b)所示；膨胀算法作用为扩大图像，其效果如图6(c)所示。若使用相同矩阵在膨胀运算后进行腐蚀运算，可以在不影响原图像大小的情况下滤去原图像的“空洞”，滤波结果如图7(b)所示。

(a)原图像

(a)原图像

1.4 分类导航计算

机器人在田垄中将遇到三种情况：方向大致准确、严重偏向和驶出田垄，使用同一算法对多种路况进行计算较为困难。针对该问题，本文使用十字法对3种路况进行分类，针对不同路况采用不同算法。十字法用于严重偏向及驶出田垄2种情况的分类和方向矫正，扫描法用于方向大致准确时的方向微矫正。

1.4.1 十字法路径分类

十字法示意图如图8(a)所示，其算法计算过程如下。

1)以点Sp为起点向上寻找跳变点。若存在跳变点则将该点设为A点，否则将顶端设为A点。

2)设A点下方一定距离的点为B点。

3)寻找B点两侧的跳变点，将出现以下情况。

① 若本步骤无跳变点或跳变点均处于图像边界附近：判定当前路况为“驶出田垄”，如图8(b)所示。

(a)算法示意图

② 若本步骤存在跳变点：a)若第1步存在跳变点：将距离B点较近的跳变点设为C点，判定当前路况为“严重偏向”，进入下一步的导航计算。b)若第1步没有跳变点：判定当前路况为“方向大致准确”，使用扫描法进行导航计算。

十字法分类后，若路况不为“驶出田垄”，则进入下一步进行导航计算。

1.4.2 十字法导航计算

十字法对“严重偏向”的路况进行导航计算。以点Sp作为原点、点Sp向上为x轴的方向、点Sp向左为y轴方向，构建新的坐标轴空间，为使效果更加直观，将原示意图顺时针旋转90°，如图9所示，其偏移幅度

图9 新坐标空间示意图

(1)

其中，Kp>0表示道路向左，Kp<0表示道路向右。

图8(a)与图10中，A点B点和C点均处在同一位置，但道路边缘弯曲度不同。道路偏移程度Kp相同的情况下，弯曲程度更高的路径需要机器人更快地调整方向，避免驶出道路损坏农作物。基于以上分析，加入对弯曲边缘的判断对于增强机器人导航的可靠性具有一定意义。针对该问题，本文在弯曲边缘的道路处引入曲率计算和权值参数参与计算。取曲线起始点E，若点A、C、E不在同一直线上，使用两点间距离公式分别计算线段a，c，e的长度。

图10 十字法曲率计算示意图

平均曲率

(2)

(3)

小车与弯道的距离影响因子

(4)

由式(1)～式(4)可计算出道路偏移值

K=W1×Kp+W2×Kcir+W3×Kd

(5)

其中，W1，W2，W3为作用系数。

1.4.3 扫描法导航计算

扫描法对“严重偏向”的路况进行导航计算。扫描法使用逐行遍历的方式，寻找每一行位于中点两侧的跳变点，记录两个跳变点之间的中点。本方法在与十字法相同的坐标空间内采用一元线性回归计算的方法进行计算，设中点坐标为(xi，xi)，可得

(6)

道路信息的回归方程只表示道路走向，因此机器人处于非道路中央位置时需要使机器人向道路中心靠近，因此引入矫正权值Ke控制矫正强度，偏移值K的计算公式

K=Lb+Ke×La

(7)

当Lb≠0，即机器人处于非道路中央位置时，算法通过Lb对偏移值K的计算结果进行干涉，实现机器人向道路中心靠拢的效果。

2 试验验证

2.1 试验平台

硬件平台为香蕉采摘履带机器人，计算平台为搭载1.4 GHz主频的Cortex-A53处理器以及1 GB运行内存的Raspberry Pi 3B+，计算平台搭载操作系统为基于Linux的Raspbian。计算平台使用单目摄像头获取实时道路图像，通过STM32F103RC单片机对Safari-880T加强版履带机器人进行移动控制。部分功能借助OpenCV[20](Intel®开源计算机视觉库)辅助实现。

2.2 试验方法

路径分割性能测试：取50张多个时段的果林田垄照片，将照片转换为640像素×480像素的分辨率，使用改良Floodfill法、K-means法、点阈值法三种方法分别进行道路分割，统计计算时间和正确提取路径信息的图片数量。统计三种方法的准确率及计算时间，测试改良Floodfill法在田垄图像路径分割方面的可行性及优缺点。

导航算法测试：搭建“U”形路段作为测试路段，如图11所示，机器人以与道路中线成40°夹角的初始姿态进入路段并使用本方法进行自主导航，并在驶出测试路段时停止导航。机器人履带底盘宽0.735 m，测试路段宽约1 m，其中直道总长度约6.3 m，弯道长度约4.7 m，直道用于测试田垄中的微矫正功能；弯道用于模拟“严重偏向”的情况，测试大偏移矫正能力；采用路段出口模拟驶出田垄的情况，测试分类状况。在测试路段中设置6个检查点，在图中分别标记为点1、点2、点3、点4、点5和点6，同一侧的检查点之间的间隔为1 m，其中检查点1用于测量人为制造的偏移量。本试验通过偏移值变化情况测试导航算法的稳定性及导航性能。

图11 测试环境示意图

3 试验结果及分析

3.1 路径分割性能测试

本试验正确分割的判断标准为：算法分割区域与实际道路区域的相交面积达到实际道路区域面积的70%以上且包含较少非道路信息。为保证试验的准确性，本试验的测试数据集选取不同光照情况下不同位置的田垄道路图片，使用树莓派3B+进行计算，试验结果如表1所示。测试数据集中部分图像含有较严重的光照干扰，测试环境较为严格，因此会出现整体准确率偏低的情况。

表1 路径分割算法测试结果

试验结果中，K-means算法的准确率达到了58%，但计算时间长；HSV阈值算法的计算耗时最短，但仅有26%的准确率；改进Floodfill算法平均计算时间为120.18 ms，达到了76%的准确率。相对于K-means算法，本算法节约了92.2%的计算时间；相对于HSV算法，本算法增加了166.1%的计算时间，但准确率提高较大。试验结果表明，改进Floodfill算法具备一定优点，其计算时间与准确率符合需求。

图12为部分分割结果，其中K-means算法可分离出道路图像，但包含较多干扰信息；HSV阈值法可大致将道路分割出来，但分割结果包含了与道路颜色相近的植物；改良Floodfill算法的分割结果包含干扰信息较少，对后续导航计算的精度保证具有重要的意义。本文使用的改进Floodfill算法具备一定的优点。

(a)测试图片

3.2 导航性能测试

在机器人履带底盘头部的中央处安装一个沾湿的刷子，利用刷子记录下移动路径。导航结束后，在检查点处测量小车的偏移程度。开始测试时，机器人以与道路中心线成40°夹角的初始姿态进入测试场地，试验中的导航情况如图13所示。

(a)直道微矫正

试验结果如图14所示，本方法在仅使用比例控制的情况下仍具备一定的收敛能力，误差变化趋势相对稳定。在加入起始干扰的情况下可迅速调整姿态，矫正后的偏移值保持在6 cm以内。检查点3、检查点4分布在弯道出入口附近，由于机器人对入弯姿态的调整会导致行驶路线出现一定偏移，因此偏移值波动为正常现象。多次试验中，均无出现与物体碰撞的情况，机器人驶出测试路段时均可正确判断“驶出田垄”，验证了算法的可行性。

图14 自主导航试验结果

4 结论

针对果林环境下的自主导航机器人，为解决的田垄视觉导航计算复杂导致实时性弱的问题，本文提出了改进Floodfill算法结合分类导航的方法进行导航计算。该方法先对图像进行预处理，然后使用改进Floodfill算法进行道路分割并对分割结果进行滤波处理。得到路径分割结果后，使用十字法对路径情况进行分类，再根据路径情况使用十字法或扫描法进行导航计算。

对路径分割性能和导航算法的试验及分析表明：

1)改进Floodfill算法具有计算速度快且准确率良好的特点。在小型低算力平台中，单次分割耗时约120 ms(不包含导航计算)且达到了76%的准确率，具有良好的计算实时性和准确率，相比其他方法具有一定优势，改善了视觉导航计算量大以及室外机器人计算平台体积大且成本高昂的问题。

2)分类导航的方法具有一定的可行性，且具备一定的导航质量。

3)道路偏移值保持在6 cm内，改善了低算力平台在田垄视觉导航中实时性差及导航效果弱的问题。

本方法是对农业机器人视觉导航方法的一种探索和尝试。此外，分类导航的方法可搭配于其他路径分割算法上，具备一定可移植性，有利于提升开发效率，对视觉导航方法的研究探索和农业机器人自主作业相关技术的发展具有一定的意义。