復雜背景下重疊橢圓形葉片的分割算法

劉鑫磊，梁 耀，黎雙文，鐘偉鎮，李豐果

（華南師范大學物理與電信工程學院/廣東省量子調控工程與材料重點實驗室，廣東 廣州 510006）

【研究意義】隨著農業生產的智能化和現代化，對植物生長狀態和病蟲害已逐步實現了實時監控，實時監控可為后期的管理提供依據。在植物生長狀態和病蟲害實時監控中，尤其是復雜背景或樹葉相互重疊時，植物葉片圖像的分割及其特征的提取是基礎，也是當前研究的熱點和難點。【前人研究進展】常見復雜背景圖像中分割出目標對象的方法有邊緣檢測法（如Sobel算子等）［1-2］、閾值分割法（如大律法等）［3-5］和形態學分割［6-7］等。此外，孫俊等［8］提出一種基于改進 Otsu 算法的生菜葉片圖像分割方法，該算法選取HSV顏色空間中的S分量，利用改進的粒子群優化算法搜索最優閾值，以該最優值作為Otsu算法的分割閾值，最終得到生菜葉片分割圖；汪慶等［9］提出了一種基于歸一化綠-紅差異指數（NDI）顏色差異特征的葉片分割算法，能夠將綠色葉片區域從自然環境中精確分割出來。為了提高復雜背景下目標樹葉分割算法的運行效率和準確性，黎雙文等［10］提出了一種超綠算法結合模糊C聚類算法分割樹葉的方法；對于復雜背景下或光照不均勻的目標樹葉，梁耀等［11］提出了一種基于GrabCut算法的復雜背景下或光照不均勻時目標樹葉的自動分割算法。上述分割算法的目標對象是單片葉片，在對自然生長狀態下目標葉片的實時監控時，監控圖像中往往出現多片目標葉片或多片目標葉片重疊的情況，給目標葉片的分割和后期的特征提取帶來極大困難。為解決這一問題，WANG等［12］提出了一種C-V模型結合改進Sobel算子的重疊葉片分割算法，該算法首先利用超綠算法去除背景中的非綠色部分，再分別以C-V模型和改進Sobel算子尋找重疊葉片的輪廓與邊緣，將二者結合起來，從而分割出重疊葉片中的上片葉子。然而由于植物葉片的多樣性和所獲取圖像的背景隨機性和復雜性，難以找到一種普適的分割算法，因此需要對不同的目標葉片和不同背景下的分割算法進行深入研究。【本研究切入點】目前還沒有研究一種普適的算法可以用于所有類型的葉片分割，因此本研究針對復雜背景下橢圓形重疊葉片的分割算法進行研究。【擬解決的關鍵問題】針對于自然生長狀態下含有復雜背景的多片重疊的目標葉片，本研究提出一種提取特征點結合貪婪算法的分割方式，可以較為有效地分割橢圓形重疊葉片。該方法可為復雜背景下多片重疊目標葉片的分割提供算法參考，也為植物生長狀態的實時監控算法奠定基礎。

1 基本原理

1.1 超綠算法

由于植物葉片多為綠色，而背景中往往含有一些非綠色區域，如建筑物、地面和天空等，因此目標葉片與背景的RGB組成是不同的，綠色葉片的G分量要高于背景，所以可以用超綠算法［13-14］有效去除整幅圖像中的非綠色背景。

設標記圖像的像素為Si，G、B、R分別為需要分割圖像的每個像素3個通道的像素值。超綠算法處理圖像可以表示為：

從式（1）可以看出，當需要分割圖像的灰度化因子大于或等于閾值T時，對應位置的標記圖像像素值不變；灰度化因子小于閾值 時，對應位置的標記圖像像素值統一為0。

1.2 凹點檢測和凸點檢測

使用貪婪算法尋找上層葉片在重疊區域的邊緣前，需將上層葉片的未重疊區域的邊緣截取一部分并翻轉到重疊區域作為貪婪算法的初始點，因此需先獲得重疊葉片的尖端點和重疊部分的凹點。凹點用來確定截取邊界，凸點用來確定對稱軸。目前凹點檢測方法有很多［15-18］，其中之一采用圓形模板來檢測目標的凹點和凸點。本文采用計算圓形模板面積的方式來確定凹點與凸點。具體算法為，首先定義一半徑為R的圓形模板，模板內的總像素點數為M。將該模板遍歷重疊葉片的邊緣點，將每個邊緣點計算圓形模板內與重疊葉片區域相重疊的像素點的個數（圖1圓圈中黑色部分的像素點個數即同時位于圓形模板與葉片區域的像素個數），設為A1；與非重疊葉片區域相重疊的像素點的個數（圖1圓圈中白色部分的像素點個數即位于圓形模板內但不在葉片區域的像素個數），設為A2。

圖1 凹點檢測與凸點檢測示意圖Fig.1 Schematic diagram of pit detection and bump detection

根據式（2）判斷第i個點Ci是否為凹點或者凸點：

式中，t1與t2分別為判斷邊緣點Ci是否為凹點或者凸點的閾值，二者不能相等。從式（2）可以看出，當模板內位于目標內（即A1）的點占比低于t1時，將該點判斷為凹點；當模板內位于背景內的點（即A2）占比高于t2時，將該點判斷為凸點。在凸點檢測和凹點檢測過程中，若有多個距離相近且滿足式（2）的凸點和凹點，則它們的位置集中在圖1中紅圈區域。本算法中，每個位置只需要一個凹點或凸點，因此分別求得每一區域的中心點作為凹點或凸點檢測的最終結果。

1.3 貪婪算法

重疊葉片分割的關鍵是準確獲得上層葉片重疊部分的邊緣信息。對于主葉脈左右完全對稱的葉片，可先獲得葉片的對稱軸，然后將未重疊的邊緣以對稱軸為軸翻轉即可得到重疊部分的邊緣。但通常情況下，葉片并非完全左右對稱，僅僅通過翻轉并不能保證翻轉后的邊緣與上層葉片重疊部分的邊緣完全吻合，需對邊緣進行進一步處理。我們提出采用貪婪算法（又稱貪心算法）［19-20］對翻轉后的邊緣進行處理，使得翻轉后的邊緣與上層葉片在重疊處的實際邊緣吻合。貪婪算法是一種尋求局部最優解的算法，其基本思想是當需要處理多個問題的最優解時，可以取出其中一個問題并假定其他問題已經處于最優解，尋找此時該問題的最優解，當找到當前問題在當前情況下的最優解則以同樣方法尋找下一問題的最優解，所有問題解決一遍則視為一次循環。

由于在重疊葉片的重疊區域中，位于上層的葉片邊緣通常會比較清晰明顯，因此，這一部分邊緣的梯度會高于周圍的葉面區域，所以本研究使用貪婪算法尋找梯度最大的邊緣區域。由于所要尋找的邊緣區域通常都是豎直方向上的，本研究所用貪婪算法的模板形狀為1行n列的長方形，并以翻轉得到的部分邊緣作為貪婪算法的起始點，如圖2所示。圖2中的數值代表以Vi為中心的模板范圍內與原圖所對應的位置上的梯度值，Vi-1，Vi和Vi+1點為貪婪算法起始點中的連續3個點，其中Vi-1表示在本次循環中已經尋找過最大梯度值的點，Vi表示在本次循環中即將尋找最大梯度值的點，Vi+1表示在本次循環中下一個尋找最大梯度值的點。以圖2中1行11列的模板為例，貪婪算法尋找最大梯度值過程為：在本次循環中，以初始位置的Vi為中心，建立一個1行11列的模板，將與原圖對應的梯度數值放入其中，并比較整個模板中的梯度數值，選擇其中梯度數值最大的位置，將該點在原圖中的對應位置作為下次循環中新的Vi點位置（在整個過程中，不需要記錄新的Vi點位置的具體梯度數值），以圖2中模板內的梯度數值為例，則應將模板左數第2個位置在原圖中對應的位置作為新的Vi點位置，當模板內存在多個相同最大梯度值時，則求出這幾個最大值的中心位置在原圖中所對應的位置，并將其作為新的Vi點位置，此時結束對點Vi的處理，對下一點即Vi+1點開始做同樣的處理，直到本次循環結束（循環結束的標志為以上層葉片尖端點為軸翻轉的邊緣點全部以上述方式處理1次）。

圖2 貪婪算法示意圖Fig.2 Schematic diagram of greedy algorithm

1.4 凸包補缺算法

重疊葉片中上層葉片邊緣的獲取是對其準確分割的前提。在使用貪婪算法尋找上層葉片在重疊處的邊緣點后，邊緣點中存在不吻合的地方。個別邊緣點偏離差到上層葉片的內部，這些偏離的點會導致上層葉片的分割出現缺口。因此需要用凸包補缺算法［21］進行補缺。凸包補缺算法的基本原理如下：

（1）確定凸包補缺算法的起始點并將所有排序。將所有點中縱坐標最小的點作為起始點，若存在多個縱坐標最小點，則選擇其中橫坐標最小的點作為起始點，以起始點為中心，建立坐標軸，依次計算其他點相對于起始點的幅角與距離，根據幅角大小進行排序，幅角相同則距離小的排在前面，如圖3A所示。

（2）以起始點開始，取3個連續的點，判斷中間點是否為凸包點。由起始點開始，依次取3個連續的點，如圖3A所示，從P0開始，依次取3個點，即P0、P1、P2，依次連接3個點形成的形狀稱之為左旋，則此時可以確定P1為凸包上的點。

（3）根據第2步的結果確定新的起始點，并重復第2步。通過第2步確定點P1為凸包點，則以該點為新的起始點，依次取3個點，如圖3B所示，從P1開始，依次取3個點：P1、P2、P3，依次連接3點形成的形狀稱之為右旋，則可以確定P2不是凸包上的點，此時需要繼續以P1為起始點，跳過P2依次選擇3個點，如圖3C所示，連接的3個點為P1、P3、P4，可以判斷這3個點所成的形狀為左旋，則P3為凸包點，則以P3為新起始點。不斷重復步驟二、步驟三，直到遍歷所有的點，將所有凸包點按順序連接起來，即可得到點集的凸包，如圖3D所示，所得到的凸包即為點集的包絡，點集內所有點都在點集的包絡范圍之內。

圖3 凸包補缺算法示意圖Fig.3 Schematic diagram of convex hull filling algorithm

2 算法流程

2.1 算法流程圖

在算法中，需要設置的參數有凹點檢測與凸點檢測的模板大小。經過嘗試，采取直徑為410個像素的圓形模板，該模板可以使凹點檢測與凸點檢測效果最好。在使用貪婪算法時，使用的模板大小為1×201，該模板可以得到較好的移動效果。算法流程如圖4所示。

圖4 復雜背景下重疊橢圓形葉片分割算法流程Fig.4 Flowchart of segmentation algorithm of overlapping elliptical leaves in complex background

2.2 算法流程描述

（1）利用超綠算法去除圖像中的非綠色部分，如天空，大地，建筑物等；

（2）提取（1）中得到的圖像中的最大連通區域，即重疊葉片區域；

（3）對（2）中得到的圖像進行頂帽變換，去除葉柄；

（4）對（3）得到的圖像進行凹點檢測與凸點檢測，得到葉片重疊區域的凹點以及尖端點；

（5）以目標葉片的兩個尖端點所確定的直線作為對稱軸，將與目標葉片重疊部分對應的外側邊緣點翻轉至兩片葉子重疊區域；

（6）以貪婪算法尋找目標葉片在重疊區域的邊緣；

（7）對（6）得到的結果進行平滑，并與目標葉片的非重疊區域的點組合，得到完整的目標葉片邊緣；

（8）對（7）得到的邊緣進行凸包補缺處理并以此邊緣分割原圖像；

（9）用（3）得到的重疊葉片區域減去（8）得到的結果，得到下層葉片未被覆蓋的區域；

（10）以（4）得到的下層葉片尖端點連線為軸，將下層葉片完整的一般翻轉，得到下層葉片的補全圖像。

3 結果與分析

3.1 目標樹葉分割

（1）使用超綠算法去除非綠色背景。圖5A為原圖，圖像中包含了大量非綠色背景，如建筑物、天空、大地等，因此首先通過超綠算法將這一部分非綠色的背景去除，得到圖5B，可以看出該算法可以有效去除背景中的非綠色部分，但是對綠色部分無效。

圖5 目標樹葉的分割Fig.5 Segmentation of target leaves

（2）提取最大連通區域，去除綠色背景。在獲取圖像時，通常會以目標重疊葉片作為主體，因此重疊葉片在圖像中所占綠色面積最大，提取圖5B中的最大連通區域得到如圖5C所示的重疊葉片區域，從而去除了綠色背景。

（3）頂帽變換去除葉柄。所得到的最大連通區域包含了重疊葉片與葉柄，而葉柄會導致凹點檢測和凸點檢測時出現偏差，因此需利用頂帽變換對圖5C去除葉柄，結果如圖5D所示。

（4）凸點檢測與凹點檢測。為了準確獲得上層葉片在重疊區域的邊緣，需要使用貪婪算法。為了不影響重疊葉片的其他邊緣而只在葉片重疊區域使用貪婪算法，需要使用凸點檢測與凹點檢測算法分別得到兩片葉片的尖端點和重疊區域的凹點，檢測結果見圖5E、F。

（5）將部分上層葉片翻轉至重疊區域，作為貪婪算法的初始點。通過凹點檢測與凸點檢測得到的特征點將重疊葉片的部分邊緣點翻轉到重疊區域作為貪婪算法的初始點，具體做法為：通過上層葉片的兩個尖端點可以確定一條直線L1，分別以兩個重疊區域的凹點做一條垂直于L1的垂線L2和L3，將L2和L3之間的上層葉片外側的邊緣點以L1為軸翻轉到另一側，如圖5G所示，以圖5G可以看出，根據葉片的對稱性，此時翻轉得到的邊緣點會位于上層葉片在重疊區域的邊緣的附近，但仍然不是完全吻合。

圖6 分割算法有效性驗證Fig.6 Verification of the effectiveness of the segmentation algorithm

（6）使用貪婪算法準確得到上層葉片在重疊區域的邊緣。為讓翻轉而來的邊緣準確貼合到上層葉片的邊緣，需使用貪婪算法來處理這一部分邊緣點，由于在重疊區域內上層葉片的邊緣是梯度最大的位置，因此使用貪婪算法使這一部分翻轉得到的邊緣點尋找到梯度最大區域即為目標葉片在重疊區域的邊緣（圖5H），將該邊緣與上層葉片非重疊的邊緣結合，得到圖5I中完整的上層葉片邊緣，以圖5（I）中的完整邊緣分割原圖像，結果見圖5J。

（7）使用凸包補缺算法對貪婪算法得到的結果進行補缺。從圖5J可以看出，此時得到的邊緣已經較為準確，但仍會存在個別邊緣點存在偏差到了上層葉片的內部，從而導致該部分的上層葉片邊緣存在缺口（圖5J）。為解決這一問題，使用凸包補缺算法，該算法可以較為有效地填補邊緣缺口，得到更為完整的上層葉片邊緣。圖5K為圖5I經過凸包補缺算法得到的更為完整的上層葉片邊緣，利用所得到的邊緣對原圖進行分割即可得到最終的目標葉片，如圖5L所示。

（8）下層葉片殘缺圖和補全圖。以整個重疊葉片區域減去上層葉片區域，得到圖5M即下層葉片未被覆蓋區域；下層葉片尖端點連線將其分為兩部分，取完整的一半以該直線翻轉，即可得到下層葉片的完整補全圖像，如圖5N所示。

3.2 分割算法有效性的驗證

為檢驗分割算法的有效性，利用與樣本1相同的算法和流程對其他樣本進行分割，結果見圖6。從圖6可以看出，以PS摳圖作為標準進行對比，有時不進行凸包運算即可得到較好的效果，如樣本1中的圖像，樣本1中的圖像中算法分割的結果沒有明顯缺陷，因此凸包對該結果影響不大。而樣本2～5在未進行凸包時算法得到的結果有不同程度的缺陷，經過凸包算法后，缺陷得到彌補。

3.3 錯分率分析

為了對分割準確率進行定量評價，選擇人工在Photoshop軟件中摳出的目標樹葉作為評價標準，使用錯分率來評價目標樹葉分割的準確率。本研究將圖像中的點定義為4種情況：算法分割的結果與手動分割的結果相比較，將分割正確的目標葉片上的點稱為正確的目標（True Positive），將目標葉片上的點判斷成了背景的點稱為錯誤的目標（False Positive），將分割正確的背景上的點稱為正確的背景（True Negative），將背景上的點判斷成了目標葉片上的點稱為錯誤的背景（False Negative），因此定義了相關的4種錯分率計算方式。第1種是將背景誤分割為目標的點即錯誤背景點占算法分割出來的目標點的比例，稱為錯誤背景率（False Negative Rate，FNR）；第2種是將目標誤分割為背景的點即錯誤目標點占算法分割出來的背景點的比例，稱為錯誤目標率（False Positive Rate，FPR）；第3種為所有誤分割的點占整個圖像的比例，稱為圖像錯分率（Error Rate，ER）；第4種為所有誤分割的點占實際葉片的比例，稱為葉片錯分率（Error Rate for Object，ERO），具體計算公式為：

表1 樣本錯分率Table 1 Misclassification error of the samples

表1為計算得到的錯分率。從表1可以看出，上層葉片與下層葉片的錯分率均在3.0%以下，且大部分情況下經過凸包后錯分率略有下降，也就是說分割準確率更高。

4 結論

為了實現在復雜背景下重疊橢圓形葉片的分割，采用了結合凸點檢測和凹點檢測的貪婪算法。通過與Photoshop軟件人工摳圖的對比，分析了所提出算法的錯分率。結果表明，本算法在對復雜背景下重疊橢圓形葉片的分割有著較良好的效果，且錯分率均在3.0%以下。這一研究可用于植物識別、生長狀態及其病蟲害的實時監控。然而算法在超綠這一步驟時，受光照影響較大，當葉片邊緣部分光照明顯不均勻時，會導致超綠后的葉片缺失，從而導致后續的凹點檢測與凸點檢測出現錯誤，影響算法的成功率；除此之外，本算法所涉及的葉片均是較為對稱的，如不滿足此條件，在使用貪婪算法時則難以得出理想結果，這些不足之處有待進一步研究改進。