基于梯度Hough变换的遮挡苹果目标定位

吴庆岗，张卫国，常化文，金保华，刘朝霞

(1.郑州轻工业学院 计算机与通信工程学院，河南 郑州 450001； 2.大连外国语大学 软件学院，辽宁 大连 116044)

基于梯度Hough变换的遮挡苹果目标定位

吴庆岗1，张卫国1，常化文1，金保华1，刘朝霞2

(1.郑州轻工业学院 计算机与通信工程学院，河南 郑州 450001； 2.大连外国语大学 软件学院，辽宁 大连 116044)

为实现自然环境中被枝叶或其他果实遮挡的苹果目标定位，提出一种基于图像边缘信息的梯度Hough变换的目标定位方法。该方法首先在Lab空间中利用K-means聚类算法对自然环境下苹果图像进行分割，然后对分割结果进行形态学操作以去除小区域，接着采用Sobel算子提取苹果目标的边缘，最后利用梯度Hough变换获取苹果目标的圆心及半径，实现遮挡苹果目标定位。实验结果表明，该方法能够有效定位遮挡苹果，定位重合度高达93.17%。

梯度Hough变换；自然环境；目标定位；苹果图像；K-means算法；形态学

随着农业现代化的发展，在自然环境下对果实进行机器采摘已经成为一种趋势。在采摘机器人的视觉系统中，果实的自动定位是关键环节，受到越来越多研究者的关注。在自然环境下，由于苹果受枝叶和其他果实的遮挡，会导致采摘机器人对目标定位不准确，严重影响采摘效率；因此，破解机器采摘过程中目标定位难题是现代农业采摘机器人发展中亟须解决的问题。

国内外学者针对机器人采摘过程中对果实目标的定位问题进行了大量研究，其中，Hough变换作为一种经典的形状检测算法，在果实检测和定位研究中受到国内外众多学者的重视。在国内，2007年谢志勇等[1]利用草莓的轮廓信息进行Hough变换，为了减少运算量，在Hough变换之前，先进行了区域标记，由于Hough变换是在各个区域中进行的，这大大压缩了参数空间，相应地减少了运算量；2008年蔡健荣等[2]尝试采用圆形Hough变换检测有遮挡和重叠的水果，提取水果相关特征，但是运算量大，耗时长，无法适应机器人对成熟果实实时采摘的要求；2010年谢忠红等[3]采用改进的圆形随机Hough变换(RHT)计算出类圆果实的圆心坐标和半径；2012年赵文旻等[4]利用圆形Hough变换以苹果果实的最小外接矩形的边长设置累加器、搜索范围和圆心距，实现对多个粘连苹果果实的定位，结果表明，该算法对缺失面积不大于50%的成熟苹果果实识别效果较好；2016年麦春艳等[5]用BPNN的苹果颜色分割方法并结合Log和Hough变换，建立苹果目标识别算法，该方法能有效克服果实遮挡、重叠和颜色变异等问题，平均识别率可达91.6%。在国外，1988年Illingworth等[6]运用圆形Hough变换(CHT)检测图像中西红柿轮廓的弧度，但需要人工设定阈值，在光线亮度发生变化时效果欠佳；2012年Hussin等[7]利用Hough变换检测自然环境下芒果的位置及数量，当果实间存在严重遮挡时，该方法效果并不理想；2014年Nanaa等[8]利用芒果的边缘图像，采用随机Hough变换定位果实目标，该方法检测率高达96.26%，但在重叠严重的情况下检测率有所降低；2015年Rizon等[9]综合运用纹理分析、形态学膨胀和腐蚀等算法进行目标识别，并采用随机Hough变换对图像中被遮挡和重叠的杧果目标进行椭圆拟合，然后利用拟合椭圆的中心定位杧果目标。

综上所述，Hough变换在遮挡果实目标定位方面应用广泛，国内外学者在提高算法精度和减少算法运行时间方面做了大量研究。但是，广泛采用的圆形Hough变换(CHT)和随机Hough变换(RHT)的参数空间是三维空间，需要大量的内存，运行速度慢。苹果在图像中具有比较稳定的形状特征(一般呈圆形或椭圆形)，本研究拟在Lab空间中利用K-means聚类算法对自然环境下的苹果图像进行分割，并在此基础上，利用类圆图像的边缘信息，采用梯度Hough变换对存在遮挡的果实目标进行定位，以降低算法计算量，同时进一步提高定位重合度。结果也可为其他果实的目标定位提供参考。

1 材料与方法

1.1 基于Lab空间的K-means聚类分割

Lab颜色空间中，a分量的变化范围为红色到绿色，值域为-128～+127(-128表示绿色，+127表示红色)。根据自然环境下苹果图像的颜色特征(以红色为主的目标和以绿色为主的背景)，在Lab颜色空间中选择a分量进行K-means分割[10]，在Lab空间提取a分量后，其在直方图上呈现出明显的双峰。为了兼顾分割效率和准确性，只需将图像分为目标和背景，因此在K-means算法中设定聚类数目为2。分割后的效果如图1-B所示，可以看出，在a分量上对图像采用K-means分割后可以很好地提取目标图像，而对一些小的区域只需要进行形态学膨胀和腐蚀运算便可去除。本文采用8×8的结构元素对分割后的图像进行形态学开操作，然后对操作后的图像结构重建并进行填充，处理后结果如图1-C所示。因为梯度Hough变换是在图像的边缘信息上进行运算，所以采用Sobel算子提取图像的边缘，边缘图像如图1-D所示。

A, 原始图像; B, 分割结果; C, 形态学处理结果; D, 边缘提取结果A, Original image; B, Segmentation result; C, Morphological operation result; D, Edge extraction图1 图像分割结果Fig.1 Image segmentation results

1.2 基于梯度Hough变换的苹果定位

利用公式(1)计算目标图像中像素强度的梯度场[15]：

(1)

1.2.1 圆心的求取

自然环境下苹果图像经K-means分割后，并不是严格意义上的圆，而是类圆图像(如图1-B所示)。利用Sobel算子提取的边缘图像，其梯度场中的非零梯度向量指向类圆中心，利用该特征定义变换，以将梯度场转换为累加数组(累加数组通常选择与梯度场相同的维度)。其中图像边缘每个像素的梯度强度值决定了圆心的概率，累加图像中最大强度值代表类圆苹果图像的圆心。累加数组的构造通过如下的投票过程来完成：对于梯度场中的每个非零梯度向量，将权重值添加到位于向量定义的线段上的累加数组的元素中，的大小被用作权重值。对于图2-A所示的苹果图像，将边缘像素强度值添加到累加数组中，如图2-B所示，累加数组的峰值越高，说明此处是圆心的概率越大。按照这个投票过程处理后，从所有非零梯度向量中收集投票以构建累加数组。

对于包含多个苹果的图像中，对应的累加数组也将具有多个峰值。累加数组中的峰值通过以下过程进行检测：首先，用高斯拉普拉斯(LoG)滤波器对累加数组进行滤波，可以用负值或零填充局部峰值之间的过渡区域，这样更容易在连续区域中分离峰值；然后，累加数组采用的阈值设置为LoG滤波之后强度最大值的25%，累加数组中的局部峰值以及它们的8邻域被标记为1，其余部分被标记为0，使得局部峰值相互隔离；最后，通过区域生长算法检测具有局部峰值的孤立区域，孤立区域的加权质心作为其所包围的局部峰值的位置。

A, 原始图像; B, 累加数组的3D视图; C, 累加数组的2D视图; D, 原图与2D视图叠加A, Original image; B, 3D view for accumulated array; C, 2D view for accumulated array; D, 2D views superimposed on original image图2 梯度Hough变换求取圆心的结果Fig.2 Circle center obtained by gradient Hough transform

累加数组中的每个局部峰值对应于图像中的苹果，将计算出的局部峰值的坐标转换为图像中的坐标，将其作为检测到的苹果图像的圆心坐标。累加后圆心检测结果如图2所示，从图2-B累加数组的3D视图可以明显看出，对累加数组经过滤波等处理后出现2个明显的峰值，说明原图(图2-A)中存在2个类圆的苹果图像，从图2-D可以看出，由图2-C的2D视图投票后的圆心位置与图2-A的苹果原图叠加后圆心位置对应较好。

1.2.2 半径的求取

(2)

(3)

式(3)中Δr是相邻r值之间的间隔。

图2-A左边苹果在选取不同r值时相应的特征曲线如图3-A所示，把特征曲线中超出给定半径范围的曲线删除，并对半径曲线进行平滑处理，得到如图3-B所示的特征曲线。对平滑处理后的特征曲线进行一阶求导，并将特征曲线中的上升沿标记为1，下降沿标记为0，以找到特征曲线中的最大值，最大值所对应的半径即为圆的半径。

2 结果与分析

为验证基于梯度Hough变换苹果定位算法的有效性，采用不同条件下的苹果图像，在定位效果、定位重合度和运行时间等方面，与圆形Hough变换实验结果进行比较。实验所采用图像为利用佳能EOS 80D相机在自然环境下采集到的80幅苹果图像，其中包括20幅无遮挡、20幅树枝遮挡、20幅树叶遮挡和20幅苹果自身遮挡的苹果图像。为了便于运行时间的比较，图4所给出的4幅图像大小全部为293×193像素。实验平台为Inter(R) Core(TM) i5-3470CPU @3.20GHz，4GB RAM，测试环境为MATLAB R2014a。关键参数设置如下：半径取值范围设置为15～70，相邻r值之间的间隔Δr=1，累加数组采用的阈值设置为LoG滤波之后强度最大值的25%。

A, 不同半径下特征曲线; B, 平滑后特征曲线A, Signature curve with different radius; B, Signature curve after smoothness图3 特征曲线Fig.3 Signature curve

图4给出了4幅具有代表性的苹果图像的实验结果。为方便分析讨论，每个苹果目标被标记不同编号。从第一列苹果原图可以看出，无遮挡苹果有8个(苹果2、4、8、9、12、13、14和16)、树枝遮挡1个(苹果15)、树叶遮挡4个(苹果6、7、10和11)、苹果自身遮挡3个(苹果1、3、5)，其中编号7和编号10的2个苹果同时被树叶和苹果自身遮挡，编号15的苹果同时被树枝和苹果自身遮挡。第二列为利用圆形Hough变换进行苹果定位的结果，第三列为利用梯度Hough变换进行苹果定位结果。由实验结果可以看出：在苹果目标没有任何遮挡的情况下，圆形Hough变换和梯度Hough变换定位效果都非常理想；在树叶遮挡的情况下，如苹果6，由于遮挡范围较小，对苹果的定位效果影响不是太大；对树枝遮挡的目标，如苹果15，梯度Hough变换明显优于圆形Hough变换；对于苹果自身遮挡的苹果，如苹果5、7和10等，梯度Hough变换也要优于圆形Hough变换。

图4 不同Hough变换定位苹果结果比较Fig.4 Comparisons for apple location between different Hough transform algorithms

从表1中可以看出，由于苹果图像是类圆图像，而不是严格意义上的圆，所以2种Hough变换定位出的苹果目标的重合度都会存在一定的误差。对于树枝和树叶遮挡不太严重的苹果目标(如7、10和15等)，由于边缘信息缺失不是太多，定位重合度相对比较理想。特别是对于苹果15，虽然下部分苹果重叠，但左右各检测出一部分边缘信息，在投票过程中对圆心投票所占比重较高，所以重合度较高。对于苹果目标存在严重遮挡的情况如苹果5，虽然可以根据苹果所在边缘定位出圆，但是重合度会有所降低，一方面是由于检测到的边缘点少，导致投票结果不准确；另一方面是由于分割面积小，导致计算误差增加。而对于存在苹果自身遮挡的目标如苹果9，由于苹果9的右半部分和苹果10的左半部分重合，使得在分割过程中相互毗连而被当作一个整体处理，从而丢失了部分边缘信息，进而导致苹果定位重合度有所降低。整体来说，自然环境下梯度Hough变换定位苹果后的平均重合度高达93.17%。

为衡量梯度Hough变换算法运行效率，表2给出了上述4幅苹果图像的定位时间。由于不同苹果图像所检测到的边缘像素点数目不同，导致同样大小的苹果图像，梯度Hough变换所需运行时间有所差异。但是和圆形Hough变换相比，梯度Hough变换对自然环境下苹果图像的定位时间有很大优势，可以满足机器采摘过程中对苹果目标定位实时处理的需要。

表1 不同Hough变换苹果定位重合度比较

Table 1 Comparisons of overlapping degree for apple location between different Hough transform algorithms

目标序号ObjectNo.真实面积A(像素)GroundtruthareaA(pixels)圆形Hough变换CircularHoughtransform重合面积C(像素)OverlappingareaC(pixels)重合度POverlappingdegree(P)/%梯度Hough变换GradientHoughtransform重合面积C(像素)OverlappingareaC(pixels)重合度Poverlappingdegree(P)/%11571145392.49150295.612115831155099.721121796.8435740564798.38555696.79468954879.5466997.10554448689.3447687.5064633405387.48428192.4073360332098.81316894.2988280751790.79794195.9191848126468.40137574.401042834580.6138790.421192270976.9089597.07122155211398.05199992.76131975192297.32196599.491410338898086.86898686.92152659240390.37259797.67167436685992.24710195.49平均Average89.2193.17

表2 不同Hough变换苹果定位时间比较

Table 2 Comparisons of time for locating apples between different Hough transform algorithms

图像序号ImageNo.图像大小(像素)Imagesize(pixels)运行时间Time/s圆形Hough变换CircularHoughtransform梯度Hough变换GradientHoughtransform1293×1930.56640.12682293×1930.46390.29883293×1930.65260.04274293×1930.53860.0603

3 小结

本研究提出一种基于梯度Hough变换的自然环境下苹果图像定位算法。结合苹果图像的颜色特征，首先在Lab空间对自然环境下苹果图像进行分割，然后对苹果目标进行形态学膨胀或腐蚀处理以消除小区域的影响，接着采用Sobel算子提取苹果目标的边缘，最后利用梯度Hough变换估计苹果目标的圆心及半径。通过利用苹果目标边缘点的梯度信息，减少了Hough变换在构建累加数组过程中的无效累加，提高了算法运行效率，可以满足采摘机器人实时工作的需要。通过对大量自然环境下无遮挡、树枝遮挡、树叶遮挡和苹果自身遮挡的苹果图像的定位测试，结果表明，平均重合度高达93.17%，具有较好的实用性。

[1] 谢志勇， 张铁中， 赵金英. 基于Hough变换的成熟草莓识别技术[J]. 农业机械学报， 2007， 38(3):106-109. XIE Z Y， ZHANG T Z， ZHAO J Y. Ripened strawberry recognition based on Hough transform[J].TransactionsoftheChineseSocietyforAgriculturalMachinery， 2007， 38(3): 106-109. (in Chinese with English abstract)

[2] 蔡健荣， 周小军， 李玉良， 等. 基于机器视觉自然场景下成熟柑橘识别[J]. 农业工程学报， 2008， 24(1):175-178. CAI J R， ZHOU X J， LI Y L， et al. Recognition of mature oranges in natural scene based on machine vision[J].TransactionsoftheCSAE， 2008， 24(1): 175-178. (in Chinese with English abstract)

[3] 谢忠红， 姬长英， 郭小清， 等. 基于改进Hough变换的类圆果实目标检测[J]. 农业工程学报， 2010， 26(7):157-162. XIE Z H， JI C Y， GUO X Q， et al. An object detection method for quasi-circular fruits based on improved Hough transform[J].TransactionsoftheCSAE， 2010， 26(7): 157-162. (in Chinese with English abstract)

[4] 赵文旻， 姬长英， 李莹莹. 自然场景下成熟苹果的图像识别研究[J]. 科学技术与工程， 2012， 12(27):6889-6891. ZHAO W M， JI C Y， LI Y Y. Recognition of ripe apples images in natural growth conditions[J].ScienceTechnologyandEngineering， 2012， 12(27): 6889-6891. (in Chinese with English abstract)

[5] 麦春艳， 郑立华， 肖昌一， 等. 自然光照条件下苹果识别方法对比研究[J]. 中国农业大学学报， 2016， 21(11):43-50. MAI C Y， ZHENG L H， XIAO C Y， et al. Comparison of apple recognition methods under natural light[J].JournalofChinaAgriculturalUniversity， 2016， 21(11): 43-50. (in Chinese with English abstract)

[6] ILLINGWORTH J， KITTLER J. A survey of the Hough transform[J].ComputerVisionGraphics&ImageProcessing， 1988， 43(2):280.

[7] HUSSIN R， JUHARI M R， KANG N W， et al. Digital image processing techniques for object detection from complex background image[J].ProcediaEngineering， 2012， 41:340-344.

[8] NANAA K， RIZON M， ABD RAHMAN M N， et al. Detecting mango fruits by using randomized Hough transform and backpropagation neural network[C]// International Conference on Information Visualisation， 2014: 388-391.

[9] RIZON M， YUSRI N A N， KADIR M F A， et al. Determination of mango fruit from binary image using randomized Hough transform[C]// International Conference on Machine Vision， 2015.

[10] 李冠林， 马占鸿， 黄冲， 等. 基于K_means硬聚类算法的葡萄病害彩色图像分割方法[J]. 农业工程学报， 2010， 26(增刊2):32-37. LI G L， MA Z H， HUANG C， et al. Segmentation of color images of grape diseases usingK_means clustering algorithm[J].TransactionsoftheCSAE， 2010， 26(Supp. 2): 32-37. (in Chinese with English abstract)

[11] 瞿钧， 甘岚. 梯度Hough变换在圆检测中的应用[J]. 华东交通大学学报， 2007， 24(1):101-104. QU J， GAN L. The application of grads Hough transformation in circle detection[J].JournalofEastChinaJiaotongUniversity， 2007， 24(1): 101-104. (in Chinese with English abstract)

[12] 张红民， 张玉坚. 基于广义Hough变换的圆心坐标快速提取方法[J]. 江汉石油学院学报， 2000， 22(2):64-66. ZHANG H M， ZHANG Y J. Fast extracting the coordinates of center of circle based on generalized Hough transform[J].JournalofJianghanPetroleumInstitute， 2000， 22(2): 64-66. (in Chinese with English abstract)

[13] 陈小艳， 王强， 李柏林. 改进的Hough变换检测圆方法[J]. 计算机系统应用， 2015， 24(8):197-201. CHEN X Y， WANG Q， LI B L. Improved Hough algorithm for circle detection[J].ComputerSystems&Applications， 2015， 24(8): 197-201. (in Chinese with English abstract)

[14] 宋寅卯， 赵明珍， 刁智华， 等. 基于Hough变换的机器视觉目标检测技术研究[J]. 中国农机化学报， 2015， 36(4):225-231. SONG Y M， ZHAO M Z， DIAO Z H， et al. Research of technology in machine vision detection based on Hough transform[J].JournalofChineseAgriculturalMechanization， 2015， 36(4): 225-231. (in Chinese with English abstract)

[15] PENG T， BALIJEPALLI A， GUPTA S K， et al. Algorithms for on-line monitoring of micro spheres in an optical tweezers-based assembly cell[J].JournalofComputing&InformationScienceinEngineering， 2007， 7(4):330-338.

(责任编辑 高 峻)

Location of occluded apples based on gradient Hough transform

WU Qinggang1， ZHANG Weiguo1， CHANG Huawen1， JIN Baohua1， LIU Zhaoxia2

(1.SchoolofComputerandCommunicationEngineering，ZhengzhouUniversityofLightIndustry，Zhengzhou450001，China; 2.SchoolofSoftware，DalianUniversityofForeignLanguages，Dalian116044，China)

In order to accurately locate the apples occluded by branches or other apples in natural environment， a method based on gradient Hough transform was proposed in the present study. Firstly， K-means clustering algorithm was used in Lab space to segment apples in natural environment. Secondly， morphological operations were made based on the segmented results to remove the influence of small area. Then， Sobel operator was adopted to extract the edge of apples. Finally， gradient Hough transform was applied to estimate the center and radius of target apples. Thus， the occluded apples could be automatically located. Experimental results showed that the method could effectively locate the occluded apples with the precision as high as 93.17%.

gradient Hough transform; natural environment; target location; apple images; K-means clustering algorithm; morphology

10.3969/j.issn.1004-1524.2017.06.22

2016-12-28

国家自然科学基金项目(61502435,61401404,U1404623)；河南省教育厅科技攻关项目(14A520034)；河南省高等学校重点科研项目(16A520028)；郑州轻工业学院博士基金项目(2014BSJJ077，2013BSJJ041)；郑州轻工业学院校青年骨干教师项目(13300093)；郑州轻工业学院研究生科技创新基金资助项目

吴庆岗(1984—)，男，河南濮阳人，博士，讲师，主要从事农业遥感图像处理研究。E-mail: wuqinggang323@126.com

TP391.41

A

1004-1524(2017)06-1009-08