廖一鵬 王衛(wèi)星

(福州大學(xué) 物理與信息工程學(xué)院， 福建 福州 350108)

結(jié)合非下采樣Contourlet變換的改進(jìn)圖論MST圖像分割*

廖一鵬 王衛(wèi)星

(福州大學(xué) 物理與信息工程學(xué)院， 福建 福州 350108)

為提高圖論最小生成樹的分割精度，保留更多邊緣細(xì)節(jié),提出了一種結(jié)合非下采樣Contourlet變換(NSCT)及改進(jìn)圖論最小生成樹(MST)的圖像分割方法.首先,將圖像進(jìn)行NSCT分解，得到一個(gè)低頻子帶和多個(gè)高頻方向子帶,對(duì)各高頻方向子帶采用改進(jìn)的貝葉斯萎縮閾值抑制噪聲,通過(guò)模極大值檢測(cè)關(guān)聯(lián)邊緣的像素點(diǎn),結(jié)合低頻子帶灰度值和高頻子帶系數(shù)構(gòu)造多尺度多方向的MST邊權(quán),并加重關(guān)聯(lián)邊緣的邊權(quán)重;然后,從區(qū)域內(nèi)部和區(qū)域間差異函數(shù)以及合并機(jī)制方面對(duì)MST分割算法進(jìn)行改進(jìn),降低噪聲或孤立點(diǎn)的影響;最后,改進(jìn)和聲搜索算法的“調(diào)音”策略,自適應(yīng)獲取MST分割算法的最優(yōu)參數(shù),得到全局最優(yōu)分割.實(shí)驗(yàn)結(jié)果表明:與其他改進(jìn)圖論MST分割方法相比,文中方法的抗噪聲性能好,提高了分割精度，且錯(cuò)分率低，所得圖像邊緣細(xì)節(jié)明顯，分割效果較好.

圖像分割;非下采樣Contourlet變換;最小生成樹;貝葉斯萎縮閾值;和聲搜索算法;分割精度;抗噪性能

自Zahn[1]最早將圖論應(yīng)用于圖像分割以來(lái)，圖論圖像分割技術(shù)因具有對(duì)數(shù)據(jù)聚類有較好的魯棒性、對(duì)形狀不敏感且能夠把握住全局信息等優(yōu)點(diǎn)，逐步成為圖像分割領(lǐng)域中的一個(gè)新熱點(diǎn).2006年Sharon等[2]提出了一種分層的至上而下的圖論分割方法，利用該方法，和巖石背景顏色相近的獵豹和不易分辨的草叢中的蝴蝶都能清晰地提取出來(lái)，分割效果好且效率高.2004年Felzenszwalb等[3]提出了最小生成樹(MST)分割算法，該算法結(jié)果簡(jiǎn)單、分割過(guò)程充分考慮全局信息，可根據(jù)圖像特性進(jìn)行不同分割且效率高;但MST分割算法存在一定缺陷——邊權(quán)設(shè)置只考慮灰度值，目標(biāo)邊緣細(xì)節(jié)易丟失;人工設(shè)置參數(shù)，參數(shù)設(shè)置偏大易產(chǎn)生欠分割，而參數(shù)設(shè)置過(guò)小易產(chǎn)生過(guò)分割，不易把握分割尺度．

為解決這一問(wèn)題，Van等[4]提出結(jié)合k-均值聚類的改進(jìn)MST算法實(shí)現(xiàn)對(duì)水果缺陷檢測(cè);王衛(wèi)星等[5]提出了結(jié)合形態(tài)學(xué)分析的改進(jìn)MST算法實(shí)現(xiàn)對(duì)粘連細(xì)胞圖像分割、提出了結(jié)合摳圖的改進(jìn)MST算法實(shí)現(xiàn)模糊背景圖像分割[6];李慧等[7]提出結(jié)合最小異質(zhì)性合并的改進(jìn)MST算法實(shí)現(xiàn)對(duì)遙感圖像分割.但是這些改進(jìn)方法都是基于具體圖像目標(biāo)特點(diǎn)來(lái)確定分割準(zhǔn)則的，而且邊權(quán)函數(shù)的改進(jìn)都是單一尺度的.近幾年來(lái)，多尺度幾何理論的發(fā)展為圖像處理提供了新的思路，在圖像去噪、邊緣檢測(cè)、圖像融合領(lǐng)域得到廣泛應(yīng)用[8- 10].Cunha等[11]提出了非下采樣Contourlet變換(NSCT)，繼承了Contourlet變換的多方向性和各向異性的特點(diǎn)，而且具有平移不變性，更能表現(xiàn)圖像的細(xì)節(jié)和幾何結(jié)構(gòu)，所以可在NSCT域構(gòu)造多尺度多方向的MST邊權(quán)，以提高像素間的差異.Oran等[12]提出的和聲搜索算法(HS)對(duì)樂(lè)隊(duì)調(diào)音進(jìn)行模擬以實(shí)現(xiàn)完美和聲，是一種人工智能優(yōu)化算法，具有很強(qiáng)的全局搜索能力，是解決MST圖像分割算法參數(shù)自適應(yīng)優(yōu)化的有效工具．

現(xiàn)有研究表明，可以結(jié)合NSCT分解、改進(jìn)MST分割準(zhǔn)則以及和聲搜索算法來(lái)彌補(bǔ)傳統(tǒng)MST分割算法的不足.為此，文中提出了一種結(jié)合非下采樣Contourlet變換及改進(jìn)圖論最小生成樹的圖像分割方法.該方法首先將圖像進(jìn)行NSCT分解，得到多尺度多方向子帶圖像，高頻子帶通過(guò)改進(jìn)貝葉斯萎縮閾值和非線性增益函數(shù)抑制噪聲，結(jié)合低頻子帶灰度值和高頻方向子帶系數(shù)構(gòu)造多尺度多方向的MST邊權(quán)，并加重關(guān)聯(lián)邊緣的邊權(quán)重以提高分割精度;然后從區(qū)域內(nèi)部和區(qū)域間差異函數(shù)、邊權(quán)函數(shù)和合并機(jī)制方面對(duì)MST分割準(zhǔn)則進(jìn)行改進(jìn)，以降低噪聲或孤立點(diǎn)的影響;最后對(duì)和聲搜索算法的“調(diào)音”策略進(jìn)行改進(jìn)，自適應(yīng)獲取MST分割算法的最優(yōu)參數(shù)，以得到全局最優(yōu)分割.并通過(guò)實(shí)驗(yàn)對(duì)提出的方法的性能進(jìn)行了驗(yàn)證.

1 NSCT域邊權(quán)函數(shù)構(gòu)造

1.1 非下采樣Contourlet變換

Do等[13]提出的Contourlet變換對(duì)圖像進(jìn)行下采樣，不具有平移不變性.非下采樣Contourlet變換繼承了Contourlet變換多尺度多方向的特性，而且分解過(guò)程中去掉下采樣環(huán)節(jié)，使分解后圖像具有平移不變性，能更準(zhǔn)確地表現(xiàn)圖像的細(xì)節(jié)和幾何結(jié)構(gòu)信息.NSCT分解流程如圖1所示，先采用非下采樣塔式濾波器組(NSPFB)對(duì)圖像進(jìn)行多尺度分解，得到低頻子帶和多個(gè)帶通子帶，然后再采用非下采樣方向?yàn)V波器組(NSDFB)對(duì)各個(gè)帶通子帶進(jìn)行多方向分解，得到多個(gè)不同方向的高頻子帶圖像，最后得到一個(gè)近似圖像的低頻子帶和多個(gè)不同尺度不同方向高頻子帶，而且這些子帶圖像的分辨率都和原始圖像相同．

1.2 高頻子帶系數(shù)處理

圖1 非下采樣Contourlet分解流程

Fig.1 Flow chart of nonsubsampled contourlet decomposition

(1)

(2)

根據(jù)貝葉斯準(zhǔn)則，可得貝葉斯萎縮閾值：

(3)

此閾值沒考慮同尺度各方向子帶間的關(guān)系;圖像中的邊緣及細(xì)節(jié)信息對(duì)應(yīng)系數(shù)的絕對(duì)值比較大，所具有的能量也比較大;而噪聲比較分散，對(duì)應(yīng)能量較小，系數(shù)絕對(duì)值也較小;根據(jù)能量特征改進(jìn)閾值：

(4)

(5)

局部模極大值點(diǎn)，也就是邊緣點(diǎn)，并乘上權(quán)重系數(shù)λ．

(6)

最后，該方向子帶的系數(shù)處理函數(shù)為

(7)

1.3 邊權(quán)函數(shù)構(gòu)造

原MST算法的權(quán)重函數(shù)僅考慮灰度值的差異，沒考慮像素點(diǎn)的空間位置，若兩像素距離較遠(yuǎn)，其相關(guān)性也較弱.另外，也沒考慮到邊緣梯度和方向，如圖2所示，紅色線條代表關(guān)聯(lián)圖像邊緣的邊，黑色線條代表屬于區(qū)域內(nèi)部的邊，原MST算法分割如圖2(b)，如果加大關(guān)聯(lián)圖像邊緣的邊權(quán)重(比如放大1.2倍)，分割如圖2(c)，可提高分割精度，突出邊緣細(xì)節(jié)．

圖2 邊權(quán)圖分割

(8)

綜合考慮低頻子帶灰度值、像素間距離、多尺度多方向高頻子帶系數(shù)，重新定義邊權(quán)函數(shù):

w(vm,vn)=|I(vm)-I(vn)|+d(vm,vn)+

exp[G(vm,vn]

(9)

其中，I(vm)和I(vn)分別是像素點(diǎn)vm和vn的在低頻子帶的灰度級(jí);d(vm，vn) 代表vm和vn之間的空間歐氏距離，d(vm，vn)=[ (xm-xn)2+(ym-yn)2]1/2．

2 差異函數(shù)及合并機(jī)制改進(jìn)

在NSCT域邊權(quán)構(gòu)造的基礎(chǔ)上，將圖像映射成一個(gè)加權(quán)圖G(V，E)，采用基于合并策略的Krusal算法進(jìn)行分割，該算法運(yùn)算效率高、分割效果好且結(jié)構(gòu)簡(jiǎn)單，但存在一定缺陷，本研究改進(jìn)如下.

原算法用最大邊權(quán)來(lái)代表區(qū)域內(nèi)部的差異，容易受噪聲或孤立點(diǎn)影響，本研究采用平均邊權(quán)來(lái)代表區(qū)域內(nèi)部的差異：

(10)

而區(qū)域間的差異用最大邊權(quán)和最小邊權(quán)的平均值來(lái)代替，重新定義差異函數(shù)為

(11)

(12)

C1與C2是V的子集，對(duì)應(yīng)于圖像分割出的區(qū)域，C1與C2是兩個(gè)相鄰的分割區(qū)域.改進(jìn)后的差異函數(shù)降低了分割敏感度，易造成欠分割，但可通過(guò)參數(shù)t來(lái)調(diào)節(jié)分割尺度．

(13)

根據(jù)式(13)的判別準(zhǔn)則，若D(C1,C2)=0，則將兩區(qū)域合并一起，否則不合并.對(duì)于分割結(jié)果，如果Cα≠Cβ并且|Cα|

3 基于改進(jìn)和聲搜索的最優(yōu)分割

3.1 目標(biāo)函數(shù)

圖像分割效果取決于參數(shù)t和q的設(shè)置，為此，把最優(yōu)分割的求解轉(zhuǎn)換成一個(gè)優(yōu)化問(wèn)題，也就是要求分割結(jié)果的類間差異和類內(nèi)差異的比值最大，建立目標(biāo)函數(shù)為

(14)

3.2 改進(jìn)和聲搜索最優(yōu)參數(shù)

基本和聲搜索(HS)算法對(duì)樂(lè)隊(duì)調(diào)音進(jìn)行模擬以實(shí)現(xiàn)完美和聲[16]，根據(jù)該思想可對(duì)優(yōu)化問(wèn)題進(jìn)行求解.在HS算法中，候選解之間的“調(diào)音”相互獨(dú)立，沒有信息共享機(jī)制，而且迭代過(guò)程帶寬BW保持不變，易陷入局部最優(yōu)解.本研究對(duì)HS算法的“調(diào)音”策略和BW的設(shè)置進(jìn)行改進(jìn)，設(shè)記憶庫(kù)保留概率為HMCR，音調(diào)調(diào)解率為PAR，xbest和xworst為記憶庫(kù)中的最優(yōu)和最差和聲，xnew為將產(chǎn)生的新和聲.隨機(jī)產(chǎn)生r1、r2，若r1

xnew=rand(xbest-BW,xbest+BW)

(15)

BW=|xbest-xworst|

(16)

改進(jìn)了最優(yōu)位置的更新策略，即對(duì)記憶庫(kù)“最優(yōu)美和聲”xbest進(jìn)行“調(diào)音”，又保留了音調(diào)調(diào)節(jié)參數(shù)BW，且隨著迭代次數(shù)增加，BW慢慢縮小，能快速找到全局最優(yōu)解.設(shè)置2個(gè)樂(lè)器(即t和q)，初始化和聲記憶庫(kù)HM，產(chǎn)生M個(gè)初始和聲，記錄每個(gè)個(gè)體的適應(yīng)度值，這里適應(yīng)度是式(14)中H的值，算法流程如圖3所示.

(17)

圖3 改進(jìn)和聲搜索算法流程圖

3.3 改進(jìn)后MST算法的分割步驟

(1) 對(duì)圖像進(jìn)行NSCT分解得到一個(gè)低頻子帶和多尺度多方向高頻子帶，提取低頻子帶灰度值，對(duì)各高頻方向子帶系數(shù)進(jìn)行噪聲抑制和模極大值檢測(cè)．

(2) 將圖像映射為圖G(V，E):構(gòu)造8鄰域加權(quán)圖，|V|=n，|E|=m，并進(jìn)行邊權(quán)設(shè)定.把E中所有的權(quán)重按照升序排列，得到集合π=(O1，O2，… ，Om)．

(3) 初始化和聲記憶庫(kù)HM，產(chǎn)生初始和聲，記錄每個(gè)個(gè)體的適應(yīng)度，并從HM中隨機(jī)選擇一組t和q．

(4) 令初始分割為S0，S0=(v1，v2，…，vn)，即V中每一個(gè)元素(頂點(diǎn))為一類，設(shè)d為區(qū)域合并的執(zhí)行次數(shù)，對(duì)于d=1，2，…，m，重復(fù)步驟(5)．

(6) 返回S=Sm，然后進(jìn)行細(xì)小區(qū)域合并，并進(jìn)行適應(yīng)度計(jì)算，如果新個(gè)體優(yōu)于HM中最差個(gè)體，則替換所對(duì)應(yīng)的個(gè)體，否則不變．

(7) 判斷是否達(dá)到終止條件，如果達(dá)到最大迭代次數(shù)，轉(zhuǎn)步驟(8)，否則采用改進(jìn)的“調(diào)音”策略產(chǎn)生新的個(gè)體，并轉(zhuǎn)步驟(4)．

(8) 給分割結(jié)果的各個(gè)區(qū)域著色，并輸出分割結(jié)果．

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本研究所提出的改進(jìn)MST分割方法的性能，以Intel(R) Core(TM)i5-4 570 CPU@3.20 GH、4.00 GB(RAM)為硬件平臺(tái)，以Windows 7 Matlab 2014a為仿真運(yùn)行環(huán)境，結(jié)合相關(guān)圖片進(jìn)行測(cè)試．

在分割之前，先構(gòu)造邊權(quán)函數(shù)，對(duì)圖像進(jìn)行NSCT多尺度分解，實(shí)驗(yàn)對(duì)‘Peppers’圖像進(jìn)行2尺度分解，得到1個(gè)低通圖像、高頻尺度1的4個(gè)方向子帶圖像和高頻尺度2的8個(gè)方向子帶圖像，如圖4所示.低頻反映的是圖像的輪廓信息，提取各像素的灰度值和計(jì)算像素間距離.高頻方向子帶表現(xiàn)的是圖像噪聲、邊緣和紋理細(xì)節(jié)，先進(jìn)行噪聲抑制，采用模極大值提取邊緣系數(shù)，并相應(yīng)增大其權(quán)重值，這里設(shè)λ=1.2，最后根據(jù)式(9)計(jì)算各頂點(diǎn)的多尺度邊權(quán)．

采用文中提出的改進(jìn)MST分割方法對(duì)256×256‘Peppers’圖像進(jìn)行分割實(shí)驗(yàn)，參數(shù)設(shè)置為：①t為分割控制尺度，50≤t≤600;②q為細(xì)小區(qū)域合并控制參數(shù)，這里取范圍為2≤q≤80;③和聲記憶庫(kù)HM的和聲個(gè)數(shù)M=10，和聲記憶庫(kù)保留概率HMCR=0.9，記憶庫(kù)擾動(dòng)概率PAR=0.33，實(shí)驗(yàn)發(fā)現(xiàn)迭代次數(shù)超過(guò)1 160以后不再替代最差個(gè)體，因此設(shè)置最大迭代次數(shù)N=1 200.文中方法與已有文獻(xiàn)中的方法的分割效果如圖5所示．

圖4 圖像NSCT分解

由圖5可見，與其他MST分割效果比較，原MST算法分割結(jié)果存在大量過(guò)分割和欠分割，分割效果差;文獻(xiàn)[4]的算法通過(guò)t均值聚類，有效解決了過(guò)分割，但是存在部分欠分割和細(xì)小區(qū)域;文獻(xiàn)[5]的算法結(jié)合形態(tài)學(xué)對(duì)分割區(qū)域再處理，小區(qū)域合并而大區(qū)域再分割，解決了細(xì)小區(qū)域的存在，但是大區(qū)域部分存在大量過(guò)分割;文獻(xiàn)[6]的算法通過(guò)手動(dòng)調(diào)節(jié)參數(shù)t和合并參數(shù)q，并改進(jìn)了合并規(guī)則，一定程度上解決了過(guò)分割和欠分割現(xiàn)象，但邊權(quán)設(shè)置簡(jiǎn)單，大量邊緣細(xì)節(jié)丟失; 文獻(xiàn)[7]的算法采用顏色最小異質(zhì)性對(duì)相鄰區(qū)域進(jìn)行合并，有效解決了過(guò)分割現(xiàn)象，但顏色相近的相鄰區(qū)域易產(chǎn)生合并，使顏色相近的水果粘連在一起;文中方法通過(guò)改進(jìn)和聲搜索最優(yōu)參數(shù)t和q有效解決了過(guò)分割和欠分割現(xiàn)象，通過(guò)NSCT域構(gòu)造多尺度邊權(quán)函數(shù)和加重關(guān)聯(lián)邊緣的邊權(quán)值，使分割區(qū)域邊緣細(xì)節(jié)明顯，與實(shí)際目標(biāo)較吻合．

圖5 本文方法與已有方法的分割效果

Fig.5 Segmentation effect of proposed method and existing methods

為評(píng)價(jià)文中方法的抗噪性能，對(duì)‘Peppers’圖像疊加均值為0、方差為20的高斯白噪聲，采用不同的頻域去噪方法進(jìn)行處理，并進(jìn)行比較，結(jié)果如圖6所示.去噪后圖像峰值信噪比(PSNR)統(tǒng)計(jì)如表1所示．

由圖6可見，文中算法無(wú)論在信噪比，還是在平滑和邊緣保持度方面，都有很大的提高.為驗(yàn)證去噪分割效果，分別對(duì)噪聲圖像6(b)和去噪后圖像6(f)進(jìn)行分割，效果如圖6(g)和6(h)，對(duì)噪聲圖像分割，結(jié)果出現(xiàn)了過(guò)分割和很多噪聲孤立點(diǎn)，去噪處理后再分割，平滑了噪聲，解決了過(guò)分割和減少了孤立噪聲點(diǎn)，且邊緣較完整．為了評(píng)價(jià)本文方法的分割效果，將文中分割方法與現(xiàn)有的改進(jìn)MST方法進(jìn)行比較，圖7展示了3幅經(jīng)典圖像的分割效果及比對(duì)．

由圖7可見，文獻(xiàn)[4]方法存在欠分割現(xiàn)象，馬身體部位缺失，花瓣粘連一起，無(wú)法將兔子完全分離模糊背景;同時(shí)，草地背景、兔子身體部位和花瓣周邊背景區(qū)域過(guò)分割，存在孤立細(xì)小區(qū)域. 文獻(xiàn)[5]方法對(duì)中等大小的區(qū)域分割效果好，小區(qū)域存在欠分割而大區(qū)域存在過(guò)分割現(xiàn)象，3幅圖的背景部分過(guò)分割現(xiàn)象嚴(yán)重，花瓣內(nèi)部粘連一起，兔子被分割為多個(gè)區(qū)域且眼睛部位不明顯.文獻(xiàn)[6]方法解決了上述的部分過(guò)分割和欠分割問(wèn)題，但是邊緣細(xì)節(jié)丟失，馬與草地不能很好地分離，花瓣內(nèi)部邊緣缺失，兔子胡須不明顯.文獻(xiàn)[7]方法有效解決了過(guò)分割現(xiàn)象，但顏色相近的相鄰區(qū)域易產(chǎn)生最小異質(zhì)性合并，使顏色相近的區(qū)域粘連一起，馬腳與背景合為一體，紅色花瓣粘連為一體，兔子胡須被背景吸收且眼睛部位缺失.文中方法較好地解決了上述問(wèn)題，很好地解決了過(guò)分割和欠分割現(xiàn)象，且合并了孤立細(xì)小區(qū)域，分割效果較好，結(jié)合NSCT域構(gòu)造多尺度邊權(quán)函數(shù)使分割結(jié)果的邊緣較完整，細(xì)節(jié)更加明顯．

圖6 不同方法的圖像去噪及分割結(jié)果

Fig.6 Image denoising and segmentation effect of different methods

表1 不同去噪方法的PSNRTable 1 PSNR of different denoise methods

圖7 不同方法分割結(jié)果比較

為了進(jìn)一步客觀評(píng)價(jià)分割精度，對(duì)5種方法的分割精度進(jìn)行比較，精度計(jì)算公式如下[6]：

(18)

式中：WEpixel是期望分割結(jié)果的總邊界像素點(diǎn)；Epixel和Upixel分別表示和期望分割結(jié)果對(duì)比，出現(xiàn)在期望分割結(jié)果中的邊界像素點(diǎn)和不出現(xiàn)的邊界像素點(diǎn)，即邊界點(diǎn)的正確率與錯(cuò)誤率；μ是懲罰系數(shù)，其值越小對(duì)錯(cuò)誤像素點(diǎn)的懲罰越小，精度也越高，這里選取μ=0.3，這里期望的分割結(jié)果采用人工繪制的邊界圖.隨機(jī)選取40幅圖像，分別對(duì)原始圖像和加入0均值、不同程度方差(S)的高斯白噪聲圖像進(jìn)行分割，平均分割精度統(tǒng)計(jì)如表2所示．

表2 不同方法分割精度的比較Table 2 Comparison of precision of different methods

由表2可見，對(duì)原始圖像分割時(shí)，相比于文獻(xiàn)[4- 7]的方法，文中方法最少可提高3.2個(gè)百分點(diǎn)的分割精度;另外，隨著噪聲水平的增加，文獻(xiàn)[4- 7]方法的分割精度大幅度下降，而文中方法保持較高的分割精度．

將文中方法進(jìn)行實(shí)際應(yīng)用，用來(lái)處理網(wǎng)狀型裂縫之間交錯(cuò)復(fù)雜、線形雜亂、圖像上存在很多噪聲的路面網(wǎng)狀裂縫圖像，并與其他方法的處理結(jié)果進(jìn)行比較，結(jié)果如圖8所示。

圖8 路面圖像分割結(jié)果對(duì)比

由圖8可見，采用文獻(xiàn)[4- 6]中方法進(jìn)行分割時(shí)因受噪聲影響，存在大量過(guò)分割且裂縫細(xì)節(jié)不明顯;采用文獻(xiàn)[7]中方法進(jìn)行分割時(shí)，微弱裂縫與背景顏色接近，被最小異質(zhì)性合并到背景，造成一部分裂縫缺失;采用文中方法進(jìn)行分割時(shí)，裂縫連續(xù)、細(xì)節(jié)明顯，且裂縫完全分離背景，通過(guò)二值化、細(xì)化、毛刺去除及斷點(diǎn)連接后與原圖疊加，最終結(jié)果如圖8(i)所示.采用其他傳統(tǒng)方法檢測(cè)時(shí)，檢測(cè)出的裂縫不清晰，檢測(cè)結(jié)果中新增了許多斑點(diǎn)和偽裂縫噪聲，無(wú)法進(jìn)一步的裂縫提取分離.由此可見，文中方法對(duì)于含大量噪聲的裂縫圖像在抗噪性能、分割精度方面有較大的優(yōu)勢(shì)．

5 結(jié)論

針對(duì)圖論最小生成樹分割算法精度低、分割尺度無(wú)法正確把握、邊緣細(xì)節(jié)信息易丟失等不足，提出了一種結(jié)合非下采樣Contourlet變換和改進(jìn)圖論最小生成樹的圖像分割方法.首先將圖像進(jìn)行NSCT分解，高頻子帶通過(guò)改進(jìn)貝葉斯萎縮閾值和非線性增益函數(shù)抑制噪聲，通過(guò)模極大值檢測(cè)關(guān)聯(lián)邊緣的像素點(diǎn)，提取低頻子帶灰度值和各個(gè)高頻子帶系數(shù)構(gòu)造多尺度多方向的MST邊權(quán)，并加重關(guān)聯(lián)邊緣的邊權(quán)重；其次從區(qū)域內(nèi)部和區(qū)域間差異函數(shù)、邊權(quán)函數(shù)和合并機(jī)制方面對(duì)MST分割準(zhǔn)則進(jìn)行改進(jìn)，降低了噪聲影響和孤立細(xì)小區(qū)域；最后改進(jìn)和聲搜索算法，自適應(yīng)獲取MST分割算法的全局最優(yōu)分割，有效地克服了過(guò)分割和欠分割現(xiàn)象.并通過(guò)實(shí)例應(yīng)用對(duì)不同圖像分割方法的抗噪性能、分割效果和分割精度進(jìn)行比較.結(jié)果表明，該方法與其他改進(jìn)MST算法相比，抗噪性能好，分割精度提高了3.2個(gè)百分點(diǎn)，且邊緣細(xì)節(jié)明顯，與實(shí)際目標(biāo)較為吻合，分割效果較好.該方法也存在計(jì)算量大的問(wèn)題，如何優(yōu)化算法效率是下一步的研究工作.

[1] ZAHN C.Graph-theoretical methods for detecting and describing gestalt clusters [J].IEEE Transactions on Com-puters，1971，C- 20:68- 86．

[2] SHARON E，GALUN M，SHARON D，et al.Hierarchy and adaptivity in segmenting visual scenes [J].Nature，2006，442:810- 813．

[3] FELZENSZWALB P F，HUTYENLOCHER D P.Efficient graph-based image segmentation [J].International Journal of Computer Vision，2004，59(2):167- 181．

[4] VAN H P，BYUNG R L.An image segmentation approach for fruit defect detection using k-means clustering and graph-based algorithm [J]. Vietnam Journal of Computer Science，2015， 2(1):25- 33．

[5] 王衛(wèi)星，田利平，王悅.基于改進(jìn)的圖論最小生成樹及骨架距離直方圖分割細(xì)胞圖像 [J].光學(xué)精密工程，2013，21(9):2464- 2472．

WANG Wei-xing， TIAN Li-ping， WANG Yue. Segmentation of cell images based on improved graph MST and skeleton distance mapping [J].Optics and Precision Engineering， 2013， 21(9):2464- 2472．

[6] 王衛(wèi)星，石紅玉.結(jié)合閉合解摳圖及最小生成樹的圖論分割算法 [J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2014，46(9):682- 687．

WANG Wei-xing，SHI Hong-yu.A minimum spanning tree based image segmentation algorithm with closed form solution [J]. Journal of Harbin Institute of Technology， 2014，46(9):682- 687．

[7] 李慧，唐韻瑋，劉慶杰，等.一種改進(jìn)的基于最小生成樹的遙感影像多尺度分割方法 [J].測(cè)繪學(xué)報(bào)，2015，44(7):791- 796．

LI Lui，TANG Yun-wei，LIU Qing-jie，et al. An improved algorithm based on minimum spanning tree for multiscale segmentation of remote sensing imagery [J].Acta Geodaeticaet Cartographica Sinica，2015，44(7):791- 796．

[8] LIU L， JIA Z H， YANG J，et al.A medical image en-hancement method using adaptive thresholding in NSCT domain combined unsharp masking [J].International Journal of Imaging Systems and Technology，2015，25(3):199- 205．

[9] ZHONG F P，MA Y Q，LI H F.Multifocus image fusion using focus measure of fractional differential and NSCT [J]. Pattern Recognition and Image Analysis，2014，24(2):234- 242．

[10] 吳一全，朱麗，李立.基于NSCT和KFCM聚類的圖像邊緣檢測(cè)方法 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，43(5):59- 65．

WU Yi-quan，ZHU Li， LI Li.Edge detection of images based on NSCT and KFCM [J].Journal of South China University of Technology(Natural Science Edition)，2015，43(5)：59- 65．

[11] CUNHA A L，ZHOU J P，DO N M.The nonsubsampled contourlet transfortn:theory，design，and applications[J]. IEEE Transactions on Image Processing，2006，15(10):3089- 3101．

[12] ORAN M G，MAHDAVI M.Global best harmony search [J].Applied Mathematics and Computation，2008，198(2):643- 666．

[13] DO M N，VETTERLI M.The contourlet transform:an efficient directional multiresolution image representation [J].IEEE Transactions on Image Processing，2005，14(12):2091- 2106．

[14] 吳一全，殷駿，戴一冕.基于人工蜂群優(yōu)化的NSCT域圖像模糊集增強(qiáng)方法 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，43(1):59- 65．

WU Yi-quan，YIN Jun，DAI Yi-man. Image enhancement in NSCT domain based on fuzzy sets and artificial bee colony optimization [J].Journal of South China University of Technology(Natural Science Edition)，2015，43(1):59- 65．

[15] TONG Y，ZHAO M R，WEI Z L，et al.Synthetic aperture radar image nonlinear enhancement algorithm based on NSCT transform [J].Physical Communication,2014，13(C):239- 243．

[16] DAS S，MUKHOPADHYAY A，ROY A，et al.Exploratory power of the harmony search algorithm:analysis and improvements for global numerical optimization[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B:Cybernetics，2011，41(1):89- 106．

ImprovedGraphMST-BasedImageSegmentationwithNon-SubsampledContourletTransform

LIAOYi-pengWANGWei-xing

(College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, Fujian, China)

In order to improve the segmentation accuracy of graph's minimum spanning tree and reserve more edge details, a new image segmentation method, which is on the basis of non-subsampled Contourlet transform (NSCT) and improved graph's minimum spanning tree (MST) is proposed. Firstly, an image is decomposed into a low-frequency sub-band and several high-frequency direction sub-bands through NSCT decomposition. Secondly, the high-frequency direction sub-bands are denoised according to the improved Bayes shrink threshold, and edge points are detected according to the module maxima. Then, a multi-scale multi-direction MST edge weight is constructed according to the grey value of low-frequency sub-band and the coefficients of high-frequency sub-bands, and the edge weight of edge points is increased. Moreover, MST algorithm is improved in two main aspects, one is the function of intra-regional and inter-regional differences, and the other is the re-merge mechanism after segmentation. Thus, the impact of noises or isolated points can be reduced. Finally, the optimal position adjustment strategy of harmony search is improved and adopted to find the optimal parameters of global optimal MST segmentation results adaptively. Experimental results show that, in comparison with other improved MST algorithms, the proposed method improves both anti-noise performance and segmentation accuracy, and helps obtain images with higher segmentation accuracy and better edge details.

image segmentation; non-subsampled Contourlet transform; minimum spanning tree; Bayes shrink threshold; harmony search algorithm; segmentation accuracy; anti-noise performance

2016- 08- 19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170147,61471124,61601126)

*Foundationitems: Supported by the National Natural Science Foundation of China(61170147,61471124,61601126)

廖一鵬(1982-),男,博士生,講師,主要從事圖像處理與模式識(shí)別研究.E-mail:fzu_lyp@163.com

1000- 565X(2017)07- 0143- 10

TP 391

10.3969/j.issn.1000-565X．2017.07.020