基于梯度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