改進的分水嶺算法在粘連圖像分割中的應用

張文飛 韓建海,2* 郭冰菁,2 李向攀,2 劉賽賽

1(河南科技大學機電工程學院 河南 洛陽 471003)2(河南省機器人與智能系統重點實驗室 河南 洛陽 471003)3(鄭州科技學院 河南 鄭州 450000)

0 引 言

當前，我國的水果品質已經接近國際先進水平，然而水果市場的國際競爭力仍然很低，主要原因就在于我國的水果產后處理能力不足，其中像上線、清洗、烘干等處理比較容易解決，而水果分揀技術才是最核心的關鍵技術。但是我國目前水果檢測和分揀技術仍比較落后，致使那些接近國際品質的水果沒有被真正地分揀出來[1]。

目前，我國是世界上最大的原料藥生產國和出口國，由于需求巨大，醫藥生產單純靠人工勞動力無法滿足，因此在很多醫藥生產線上出現了像機器人這樣的自動化設備來代替人工完成一些生產工序，比如：醫藥生產、藥品分揀、包裝等，這些設備大都配有視覺裝置，通過圖像信息使自動化設備高效準確地完成作業任務。然而藥品種類繁多，擺放雜亂無章，視覺機器人在分揀時容易出現漏撿、錯撿的情況，造成的后果嚴重。所以不管是水果還是醫藥分揀，分揀的精度要求都是很高的，而分割又是分揀的核心一環，能否精確地將圖像分割出來將直接影響后續分揀結果的好壞。

圖像分割就是將圖像中有意義或者感興趣的目標區域提取出來，用于圖像的后續處理[2]。但是由于設備或人為原因，以及圖像在捕獲、傳輸的過程中容易受到外界環境的影響，會使得到的圖像質量降低，能否將目標物體從圖像中準確分割出來將會直接影響后續圖像處理的效果[3-4]。圖像分割中比較難解決的問題就是圖像的粘連性問題，在進行多種類水果和藥盒無序分割時，若能解決水果和藥盒之間的粘連性問題，將會很大程度上提高水果和藥盒的分揀效率與檢測精度。針對不同粘連程度的圖像分割問題，研究者們提出了各種分割算法及其改進算法?；谛螒B學操作的圖像分割算法具有簡單、快速等特點，適用于簡單圖像的分割，但用于對粘連程度高的圖像進行分割時，效果并不理想[5-6]。基于圖論的圖像分割算法會隨著圖像分辨率的提升而導致圖的存儲空間大、構圖計算量大、計算速度慢等問題[7]?；诎键c匹配的圖像分割算法分割效果依賴于能否正確匹配凹點，然而對于那些粘連程度比較高的圖像，凹點是很難得到有效匹配的，也會導致分割不精確[8-9]。相對于其他圖像分割算法，分水嶺算法[10-11]對微弱邊緣比較敏感，不容易丟失邊緣信息，這也是解決粘連性問題的關鍵，但同時也會造成圖像過分割的情況，影響分割精度。目前針對分水嶺過度分割的問題，常見的解決方案有兩種：一種是利用給分割圖像制作一個掩膜標記來作為種子點引導分水嶺分割；另一種是對分水嶺分割后的圖像利用一些區域合并準則合并相似區域。本文結合形態學運算和歐氏距離變換來改進傳統的分水嶺算法，用于分割粘連程度高的圖像。實驗結果表明，該算法在對于粘連程度高的多種類混合水果和藥盒無序分割時具有很好的分割效果。

1 相關知識及算法流程

1.1 粘連圖像的特征

1.1.1顏色特征

水果的種類多種多樣，由于地域環境，生長時接收光照情況的不同，同一種水果也會出現很大的顏色差異，但主要還是以黃色、青色、紅色為主。這些水果有些是純色的，有些是混合顏色搭配的。藥盒的種類更是多種多樣，不同廠家有不同的設計風格，又加上藥盒本身上面的顏色大都以混合顏色為主，所以對圖像的分割造成了較大干擾。

1.1.2幾何特征

水果的形狀輪廓主要以圓形和橢圓形為主，藥盒的形狀輪廓主要以矩形為主，本文統一用圖像輪廓外接圓來衡量其大小。實驗主要分割外接圓大小在25 cm2以內的水果，長寬在16 cm×12 cm，也就是外接圓大小為314 cm2以內的藥盒。水果原圖和藥盒原圖如圖1所示。

1.2 算法流程

本文提出了一種結合形態學運算和距離變換的改進分水嶺分割方法。首先對圖像進行前景提取[12-13]，得到目標圖像，然后利用形態學運算去除噪聲，接著制作掩膜標記，進行分水嶺分割，這樣可以在保證分割準確率的前提下大大提高粘連圖像整體的分割效率。具體實現流程如下：

Step1輸入粘連圖像A，背景圖像B，通過求取|A-B|≤閾值，提取前景圖像P；

Step2輸入圖像P，用形態學運算去除多余的背景噪聲，輸出圖像G；

Step3輸入圖像G，求取距離圖像D，進行連通區域分析，得到標記圖像M；

Step4結合形態學圖像G，距離圖像D，連通區域標記圖像M，制作掩膜標記，進行分水嶺分割。

2 算法原理及改進

2.1 遞歸雙邊濾波

2.1.1 遞歸雙邊濾波算法

對于粘連的水果或者藥盒圖像，由于圖像中目標區域顏色和形狀都很類似，若是用一般的濾波方法，比如高斯濾波、中值濾波，雖然能夠得到一定的平滑圖像，實現去除噪聲的效果，但是對于粘連程度高的圖像來說，在降噪的同時會使得部分邊緣信息丟失。而遞歸雙邊濾波算法是一種高通濾波器，能夠濾除掉圖像中的低頻信息，銳化像輪廓邊緣這樣的高頻圖像信息。相比傳統雙邊濾波算法，遞歸雙邊濾波算法對值域濾波器核進行了約束，通過累積從像素坐標(i,j)到像素坐標(k,l)路徑上相鄰像素值的鄰近性來實現[14]。

2.1.2 遞歸雙邊濾波算法的實現

從像素點(i,j)到像素點(k,l)有很多路徑，本算法中采取的遞歸路徑是先對像素點進行水平方向遞歸，在此基礎上再對像素點進行垂直方向遞歸。遞歸雙邊濾波具體實現如下：

(1)

(2)

ω(i,j,k,l)=r(i,j,k,l)×d(i,j,k,l)

(3)

式(1)是遞歸雙邊濾波算法的值域核，表示從像素(i,j)到(k,l)相似像素值的遞歸；式(2)是遞歸雙邊濾波算法空域核，表示從像素(i,j)到(k,l)的空間域系數；式(3)是表示兩個像素點的加權系數，取決于空域核和值域核的乘積。由于對值域核的遞歸約束，使得粘連圖像中同一目標區域的像素彼此的依賴性更強，圖像的粘連處邊緣更加突出。

2.2 結合形態學運算的前景提取

形態學運算是圖像處理中常用的一種數學工具。其基本思想是先構建一個結構元素，讓其在圖像中移動，與圖像中的像素進行交、并集等集合運算[15-16]。本文用S(x)代表結構元素，(x,y)代表圖像中的像素點，對于形態學中常用的腐蝕、膨脹、開運算、閉運算四種運算定義如下：

腐蝕：E=X⊙S={x,y|Sxy?X}

(4)

膨脹：E=X⊕S={x,y|Sxy∩A!=?}

(5)

開運算：O=(X⊙E)⊕S

(6)

閉運算：C=(X⊕S)⊙S

(7)

為了后續圖像精確分割，首先對粘連圖像進行前景提取處理，本文采取的方式是先對前景信息進行粗提取，再進行精提取。具體實現方式如下：先采取一幅無前景圖像的背景圖像，然后將粘連圖像與背景圖像灰度化，進行相減，與設定的閾值比較，來達到圖像前景信息的粗提取，這樣就能去除大部分的背景圖像信息，但是會有一些背景信息成為噪聲點；接著再通過形態學運算，像處理傳統噪聲一樣，來進行降噪處理，進行前景精提取，就能得到比較理想的前景信息。如圖2、圖3所示。

對于水果和藥盒這兩種粘連圖像，通過實驗測試，若是選取3×3的結構元素，則對圖像腐蝕的程度會較低，達不到所需的去除背景噪聲的效果；若是選取11×11或者更大的結構元素，會出現粘連圖像邊緣被腐蝕掉的情況。最終選取5×5的矩形內核結構元素，先對圖像進行腐蝕操作，去除粘連圖像中的一些離散噪聲，收縮圖像邊界，再選取7×7的矩形內核結構元素對圖像進行開運算，進一步平滑粘連物體邊界的同時不明顯改變其面積大小，就能將粘連圖像的前景信息給提取出來。

2.3 距離變換

2.3.1距離變換的原理

在二維空間中，距離圖像是對二值圖像處理操作中常用的手段，其實質是將圖像中每個非零像素與距其最近的零點像素的距離來作為距離圖像相對應位置的像素[17-18]。距離圖像可以使物體中心位置區域的像素更加突出，越靠近中心位置，像素灰度值越高，在距離圖像中表現得越高亮；越靠近邊界，像素值灰度值越低，圖像表現得越晦暗。

2.3.2距離變換的實現

本實驗采用歐氏距離變換，將一個大小為M×N的二值圖像用一個二維數組AM×N=[aij]來表示，aij=1表示前景像素點，用aij=0表示背景像素點。假設背景像素集合表示為：B={(x,y)|aij=0}，前景像素集合表示為：F={(x,y)|aij=1}，則對集合A里面所有像素點(i,j)進行式(8)所示的距離變換；式(9)解釋了歐氏距離計算方法。

dij=min{DE[(i,j),(x,y)],(x,y)∈B}

(8)

(9)

對水果和藥盒圖像做歐氏距離變換，得到距離圖像，根據距離圖像中像素距離背景像素越遠圖像越亮的特性，可以很容易確定粘連圖像中超過某一閾值的高亮像素的大致位置。通過距離變換的水果和藥盒圖像如圖4所示。

2.4 連通區域分析

連通區域指圖像中位置相鄰并且像素值相同的像素點組成的圖像區域。本文采用的是基于種子填充法的連通區域分析，具體實現步驟如下：

1) 逐行掃描圖像，直到當前像素點為前景像素，即P(x,y)=1。

(1) 將P(x,y)作為種子，并賦予其一個標簽label，然后再將與該棧頂像素值相同的鄰域像素都壓入棧中；

(2) 彈出棧頂像素，賦予其相同的label，然后再將與該棧頂像素值相同的所有鄰域像素都壓入棧中；

(3) 重復步驟(2)，直到棧內元素為空，便找到了圖像P中的一個連通區域，該區域內的像素值被標記為label；

2) 重復步驟1)，直到掃描結束，就可得到圖像P的所有連通區域。

2.5 分水嶺掩膜標記的制作

分水嶺分割精度的高低取決于掩膜標記制作的好壞。本文掩膜標記的制作是結合形態學運算、距離圖像和連通區域分析標記圖像來共同制定的。具體實現為將形態學處理后的圖像與距離圖像二值化結果做差值運算，然后遍歷差值后的圖像像素，找出非零像素，并在連通區域標記圖對應位置做上標記，即得到分水嶺掩膜標記，如圖5所示。

2.6 改進分水嶺算法流程

改進后的分水嶺算法實現過程大致為：先用遞歸雙邊濾波算法對彩色圖像濾波，然后對圖像進行灰度化、二值化、形態運算等操作，最后制作掩膜標記(mask)指導分水嶺分割圖像。改進后分水嶺算法分割流程如圖6所示。

3 實 驗

本實驗算法是在Ubuntu 16.04操作系統下，基于Clion IDE，采用C++語言進行編寫和測試，實驗數據來源于實驗室利用kinect v2采集的混合水果數據和藥盒數據。圖7-圖11列出了采用傳統分水嶺分割算法、圖切割算法和結合距離變換的分水嶺算法對水果和藥盒圖像的分割效果圖。

從圖8(a)、圖9(a)、圖10(a)、圖11(a)可以看出，不管是水果數據還是藥盒數據，傳統分水嶺算法分割的效果都不是很理想，過分割現象比較嚴重，主要原因是傳統分水嶺算法的分割過程是比較盲目的，易受噪聲點的影響，產生過多的極小值點，在進行像素排序和模擬浸沒的過程中，誤把噪聲點區域當成盆地，造成圖像過度分割。從圖8(b)、圖9(b)、圖10(b)、圖11(b)可以看出，圖切割算法的分割效果要比傳統的分水嶺算法要好得多，能夠分割出粘連圖像的大致輪廓，但存在的問題是很多目標輪廓之間是連通的，也會造成粘連分割定位不準確。從圖8(c)、圖9(c)、圖10(c)、圖11(c)可以看出，相比傳統分水嶺算法和圖切割算法而言，結合距離變換的分水嶺算法，對于種類比較多粘連程度比較大的目標物體分割精度提升很多。雖然此算法需要制作掩膜標記來引導分水嶺分割目標物體，但是卻在制作掩膜標記的時候，拋開了傳統的將圖像經過預處理再進行邊緣檢測的結果作為掩膜標記的思想，通過對圖像做距離變換來突出目標物體的粘連部分，再對圖像進行連通區域分析，根據形態學圖像、距離變換圖像，連通區域標記圖像來制作分水嶺的掩膜標記。這種掩膜標記制作方法在很大限度上緩解了分水嶺掩膜標記制作不精確造成的過分割或欠分割的問題，對于水果和藥盒的粘連圖像分割具有很好的分割效果。

(a) 水果原圖 (b) 藥盒原圖圖1 粘連圖像原圖

(a) 前景粗提取 (b)前景精提取圖2 水果圖像前景提取

(a) 前景粗提取 (b) 前景精提取圖3 藥盒圖像前景提取

(a) 水果距離圖像 (b) 藥盒距離圖像圖4 粘連圖像的距離圖像

(a) 水果圖像掩膜標記 (b) 藥盒圖像掩膜標記圖5 粘連圖像的掩膜標記圖像

圖6 改進算法流程

(a) 水果原圖 (b) 藥盒原圖圖7 水果、藥盒原圖

(a) 傳統分水嶺 (b) 圖切割算法 (c) 改進分水嶺圖8 水果分割算法比較

(a) 傳統分水嶺 (b) 圖切割算法 (c) 改進分水嶺圖9 分割圖像輪廓外接圓效果圖

(a) 傳統分水嶺 (b) 圖切割算法 (c) 改進分水嶺圖10 藥盒分割算法比較

(a) 傳統分水嶺 (b) 圖切割算法 (c) 改進分水嶺圖11 藥盒分割效果圖

為了進一步驗證本文算法的優勢，又分別使用500幅隨意混合的水果圖像和500幅隨意混合的藥盒圖像來驗證傳統分水嶺分割算法、圖分割算法和改進的分水嶺算法的分割正確率。分割正確率計算如下：

(10)

為了直觀地比較三種分割算法在圖像分割時間效率上的差別，以傳統分水嶺分割算法運算時間為標準進行對比，計算這三種算法的歸一化運算時間：

(11)

三種分割算法實驗結果正確率、歸一化運算時間如表1、表2所示。

表1 三種分割算法分割水果結果比較

表2 三種分割算法分割藥盒結果比較

由表1可以看出，傳統分水嶺算法分割水果圖像時沒有引導，分割比較盲目，每次分割都要進行像素排序，尋找種子點，再進行“模擬浸水”，比較費時，還容易受噪聲點的影響，分割準確率也比較低，約10%左右。相比而言，圖切割算法和改進后的分水嶺算法分割時，效果要好很多，其中：圖切割的分割時間約縮短至傳統分水嶺算法的三分之一，分割準確率達到了65.4%；本文改進后的分水嶺分割算法的分割時間約為傳統分水嶺算法的五分之一，分割準確率達到了96.4%。

由表2可以看出，在對藥盒圖像進行分割時，傳統分水嶺算法由于分割時的局限性，分割時間比較高，分割準確率也是比較低的，約14.6%。而圖切割算法對于藥盒圖像分割相比傳統分水嶺算法在分割時間與分割準確率上有了很大改善，時間縮短為傳統分水嶺的近三分之一，分割準確率也達到了74.8%。本研究中改進的分水嶺分割算法相比前兩種分割算法，在時間和分割準確率上都有很大提升，分割準確率更是達到了97.2%。

4 結 語

本文在傳統分水嶺算法的基礎上，闡述了一種結合距離變換的標記分水嶺算法，主要用于解決粘連程度比較大的目標物體的分割，在很大程度上改善了分水嶺算法造成的過分割和欠分割問題，得到比較理想的分割效果。

本文改進后的分水嶺算法，在水果和藥盒圖像的實驗中，分割準確率達到97.2%，分割時間能穩定在90 ms左右。

由于水果種類和藥盒種類比較多，后期還需要進一步改善算法，以便更適用于工業或醫藥等行業的應用。