基于圖論最小割集算法的圖像分割研究

張 健，李白燕

（黃淮學(xué)院信息工程學(xué)院，駐馬店463000）

基于圖論最小割集算法的圖像分割研究

張 健，李白燕

（黃淮學(xué)院信息工程學(xué)院，駐馬店463000）

為了提高圖像分割的質(zhì)量，采用圖論最小割集算法進(jìn)行了研究。首先將圖像中的像素點(diǎn)映射為圖論節(jié)點(diǎn)，節(jié)點(diǎn)權(quán)值通過(guò)平衡因子與共享最近鄰節(jié)點(diǎn)數(shù)的比率計(jì)算；然后基于最小化能量方程建立圖像最小割集，提取分割塊內(nèi)的灰度值作為塊特征向量，用最小生成樹(shù)對(duì)圖分割；接著用判定函數(shù)判斷臨近區(qū)域是合并或者分割；最后給出了算法流程。結(jié)果表明，該算法可以分割出目標(biāo)信息，并且算法魯棒性好、峰值內(nèi)存小。

圖像處理；最小割集；權(quán)值；最小生成樹(shù)

引 言

圖像分割是將圖像細(xì)分為多個(gè)圖像子區(qū)域（像素的集合）的過(guò)程［1］，把感興趣的圖像目標(biāo)區(qū)域從不同區(qū)域的背景區(qū)域中提取出來(lái)，從而為下一步處理奠定基礎(chǔ)。

圖像分割方法有閾值分割法（threshold method，TM）、小波分析法（wavelet analysis method，WAM）、區(qū)域生長(zhǎng)法（region growing method，RGM）、分裂融合法（fission and fusion method，F(xiàn)FM）、數(shù)學(xué)形態(tài)學(xué)法（mathematical morphological method，MMM）、多尺度法（multiple scales method，MSM）、馬爾可夫隨機(jī)場(chǎng)模型法（Markov random field model method， MRFMM）、水線法（waterline method，WM）等［2］。閾值分割法較其它方法具有直觀性、易于實(shí)現(xiàn)、性能穩(wěn)定等性質(zhì)，使其被廣泛地應(yīng)用，但是存在計(jì)算量較大的缺點(diǎn)［3］。小波和閾值結(jié)合算法有較強(qiáng)的抗噪聲性能［4］，很難有效地選擇閾值，后來(lái)出現(xiàn)硬閾值法和軟閾值法，但是經(jīng)過(guò)硬閾值函數(shù)處理后在正負(fù)閾值處不連續(xù)，軟閾值方法通常會(huì)丟掉某些特征，分割圖像會(huì)產(chǎn)生劇烈震蕩。模糊集聚類的閾值方法（fuzzy threshold clustering method，F(xiàn)TCM）把背景與目標(biāo)進(jìn)行劃分［5］，聚類樣本不需要訓(xùn)練集，但對(duì)初始分割需要提供一個(gè)初始參量，同時(shí)仍需多次迭代，花費(fèi)大量的運(yùn)算時(shí)間。最大類間方差的閾值方法（Otsu threshold method，OTM）選取類間最大方差的灰度值為最佳閾值［6］，計(jì)算簡(jiǎn)單，但是當(dāng)背景與目標(biāo)灰度相差不大，會(huì)出現(xiàn)黑色區(qū)域，只對(duì)類間方差是單峰的圖像有較好分割效果。

本文中采取圖論最小割集算法（graph theoryand minimum cut set，GTMCS）對(duì)圖像分割，首先圖像中的像素點(diǎn)映射為圖論節(jié)點(diǎn)，節(jié)點(diǎn)權(quán)值通過(guò)平衡因子與共享最近鄰節(jié)點(diǎn)數(shù)的比率計(jì)算；然后基于最小化能量方程建立圖像最小割集，提取分割塊內(nèi)的灰度值作為塊特征向量，最小生成樹(shù)對(duì)圖分割；接著判定函數(shù)判斷臨近區(qū)域是合并或者分割；最后給出了算法流程。實(shí)驗(yàn)仿真顯示本文中的算法能分割出目標(biāo)信息，且算法魯棒性好、峰值內(nèi)存小。

1 算法描述

1.1 基于圖論的圖像表示

在圖論中通過(guò)第i個(gè)節(jié)點(diǎn)vi以及連接不同節(jié)點(diǎn)間的第p個(gè)無(wú)向邊ep構(gòu)成幾何圖形，圖像分割需要把圖像的2維像素點(diǎn)映射到圖論中。圖像中的像素點(diǎn)映射圖論節(jié)點(diǎn)vi∈V，集合V為所有節(jié)點(diǎn)集合；任意兩個(gè)像素點(diǎn)對(duì)之間構(gòu)成無(wú)向邊e（vi，vj）∈E，標(biāo)記為eij，集合E為所有邊的集合；整幅圖像對(duì)應(yīng)的無(wú)向圖表示為G＝（V，E），每個(gè)無(wú)向邊對(duì)應(yīng)的相關(guān)權(quán)重w（vi，vj）∈W，標(biāo)記為wij，集合W為所有無(wú)向邊權(quán)重的集合［7］；整幅圖像對(duì)應(yīng)的無(wú)向帶權(quán)圖表示為G＝（V，E，W），其中節(jié)點(diǎn)權(quán)值通過(guò)平衡因子l∈（0，1）與共享最近鄰節(jié)點(diǎn)數(shù)θi的比率計(jì)算：

Fig.1 Optimization process

式中，wi表示vi的節(jié)點(diǎn)權(quán)值；θi表示vi與其它節(jié)點(diǎn)的共享最近鄰數(shù)的總和［8］。

通過(guò)大圖G0（V0，E0）構(gòu)造更小規(guī)模的圖Gi（Vi，Ei）進(jìn)行優(yōu)化，其中Vi＋1包含的新節(jié)點(diǎn)數(shù)必須小于Vi。在優(yōu)化匹配中，每條邊的2個(gè)節(jié)點(diǎn)標(biāo)記為Gi＋1中的1個(gè)節(jié)點(diǎn)，不與匹配中任何邊關(guān)聯(lián)的節(jié)點(diǎn)可以直接標(biāo)記為Gi＋1的節(jié)點(diǎn)。例如當(dāng)邊（u，v）的2個(gè)節(jié)點(diǎn)u∈Vi，v∈Vi形成新節(jié)點(diǎn)h∈Vi＋1，則新節(jié)點(diǎn)h的權(quán)為節(jié)點(diǎn)u和v的權(quán)之和，與新節(jié)點(diǎn)h關(guān)聯(lián)的邊的權(quán)為與u和v關(guān)聯(lián)的邊的權(quán)消除邊（u，v）的權(quán)。如果某條邊與u和v均關(guān)聯(lián)，則這條邊的權(quán)就是這些邊的權(quán)之和［9］，見(jiàn)圖1。在圖1a中，權(quán)w4，w10和權(quán)w6，w11分別獨(dú)立，在圖1b中，形成新節(jié)點(diǎn)關(guān)聯(lián)的邊的權(quán)為w4＋w10和權(quán)w6＋w11，其中權(quán)w5被消除，不與匹配中任何邊關(guān)聯(lián)的節(jié)點(diǎn)權(quán)可以直接標(biāo)記，如w1，w2，w3，w7，w8，w9。

1.2 基于最小化能量方程的圖像最小割集建立

由于圖的節(jié)點(diǎn)對(duì)應(yīng)了圖像中的各個(gè)像素點(diǎn)，對(duì)圖像的分割等價(jià)于將節(jié)點(diǎn)集V分割成不相交子集，分割表示為：

式中，i≠j，i，且j＝1，2，…，k；k稱為分割數(shù)目，Vi∩Vj＝Φ。

提取分割塊內(nèi)的灰度值作為塊特征向量，把塊特征向量作為圖論G的一個(gè)頂點(diǎn)vi，小塊鄰域的分塊作為鄰接頂點(diǎn) vj，歐式距離計(jì)算邊 eij的權(quán)值w（eij），然后最小生成樹(shù)對(duì)圖分割。對(duì)節(jié)點(diǎn)集V分割的目標(biāo)是使分割后的子集同一類內(nèi)節(jié)點(diǎn)像素間差異最小，不同分類間節(jié)點(diǎn)像素相異性最大［10］。若將圖的所有節(jié)點(diǎn)分割成m個(gè)子集Vi，V2，…，Vm，其分割準(zhǔn)則為：分割后的集合Vi內(nèi)部節(jié)點(diǎn)間關(guān)聯(lián)性和相似性大；不同子集Vi和Vj相互之間的關(guān)聯(lián)性和相似性低。求最小生成樹(shù)為：

式中，I（C）是類內(nèi)差異，C1和C2是兩個(gè)不同的分割域，D（C1，C2）是類間差異。

對(duì)W中所有節(jié)點(diǎn)i分配標(biāo)記值xi，這樣圖像的前景和背景標(biāo)記分別為xi＝1和xi＝0［11］。通過(guò)最小化能量方程解決：

式中，E1（xi）為相似能量，表示將節(jié)點(diǎn)i賦值為xi的代價(jià)；E2（xi，xj）為先驗(yàn)?zāi)芰浚硎鞠噜徆?jié)點(diǎn)i和j分別賦值為xi和xj的代價(jià)，λ為加權(quán)系數(shù)。

1.3 合并與分割判定函數(shù)

判定臨近區(qū)域是合并還是分割的函數(shù)為：

式中，T為合并，F(xiàn)為不合并，π（C1，C2）是控制區(qū)域之間單位差別必須比最小的內(nèi)部差別大的程度系統(tǒng)［12］。

1.4 算法流程

（1）輸入圖像的像素點(diǎn)映射為圖論節(jié)點(diǎn)，確定節(jié)點(diǎn)權(quán)重；（2）大圖優(yōu)化匹配為小圖；（3）基于最小化能量方程建立圖像最小割集；（4）判斷合并條件，滿足執(zhí)行步驟（5），否則執(zhí)行步驟（2）；（5）k窗口可變尺度控制；（6）輸出圖像。

2 實(shí)驗(yàn)仿真

2.1 視覺(jué)分割效果

采用3種不同類型的經(jīng)典圖像：多峰模式Lena圖像、雙峰模式pout圖像、單峰模式rice圖像。不同算法仿真結(jié)果如圖2～圖4所示。

Fig.2 Simulation result of multimodal model Lena image of different algorithm

Fig.3 Simulation result of bimodal pattern pout image of different algorithm

Fig.4 Simulation result of unimodal pattern rice image of different algorithm

其中圖2a、圖3a和圖4a為待分割的原始圖像；圖2b、圖3b和圖4b是閾值法分割效果；圖2c、圖3c和圖4c是小波閾值法分割效果；圖2d、圖3d和圖4d是基于模糊集聚類的閾值方法分割效果；圖2e、圖3e和圖4e是基于最大類間方差的閾值方法分割效果；圖2f、圖3f和圖4f是本文中算法分割效果。從分割效果上可以看出，本文中算法分割出目標(biāo)信息，而其它算法分割出來(lái)的目標(biāo)物體含有大量的背景信息，不能準(zhǔn)確地分割出目標(biāo)來(lái)。

2.2 魯棒性分析

仿真圖像灰度變化情況下圖像分割的像素?cái)?shù)目，設(shè)f（x，y）表示原始的圖像在（x，y）點(diǎn)處的灰度值，灰度變化公式：

對(duì)原始Lena圖像逐漸改變灰度，像素個(gè)數(shù)的對(duì)比指標(biāo)來(lái)檢驗(yàn)該算法是否具有魯棒性，如表1所示。

從表1的分割像素?cái)?shù)目可以看出，當(dāng)外界圖像灰度變化前后，本文中算法的效果仍是最穩(wěn)定的，分割得到的目標(biāo)像素個(gè)數(shù)差距最小，具有魯棒性，而這一性質(zhì)對(duì)于圖像處理非常有意義。

Table 1 Pixels of image gray level before and after change

2.3 時(shí)間復(fù)雜度分析

為了比較算法的復(fù)雜度，表2中給出了運(yùn)行時(shí)間和峰值內(nèi)存（peak memory，PM）。

image method Lena pout rice time／s PM／Mbit time／s PM／Mbit time／s PM／Mbi t TM 1.719 22480 1.803 22480 1.765 22480 WAM 1.436 20480 1.565 20480 1.423 20480 FTCM 1.625 16384 1.877 16384 1.682 16384 OTM 1.844 19488 1.456 19488 1.771 19488 GTMCS 0.968 12288 0.980 12288 0.781 12288

本文中算法的運(yùn)行時(shí)間少，所需的峰值內(nèi)存小，對(duì)圖像處理具有實(shí)時(shí)性。這是因?yàn)闅W式距離計(jì)算邊的權(quán)值，通過(guò)最小生成樹(shù)對(duì)圖分割。

3 小 結(jié)

采用圖論算法把圖像中的像素點(diǎn)映射為圖論節(jié)點(diǎn)，節(jié)點(diǎn)權(quán)值通過(guò)平衡因子與共享最近鄰節(jié)點(diǎn)數(shù)的比率計(jì)算；然后基于最小化能量方程建立圖像最小割集，提取分割塊內(nèi)的灰度值作為塊特征向量，最小生成樹(shù)對(duì)圖分割；判定函數(shù)判斷臨近區(qū)域是合并或者分割；最后給出了算法流程。實(shí)驗(yàn)仿真顯示，本文中的算法可分割出目標(biāo)信息，且算法魯棒性好、峰值內(nèi)存小。

［1］ XU T J，QIAN X F，DAIX R，et al.Unwrapping algorithm based on segmentation and zooming for under sampled wrapped phase［J］.Laser Technology，2014，38（1）：39-43（in Chinese）.

［2］ WEIXE F，LIU X.Research of image segmentation based on 2-D maximum entropy optimal threshold［J］.Laser Technology，2013，37（4）：519-522（in Chinese）.

［3］ HUANG J，YUAN Zh W，TIAN Z Sh.Research on wavelet threshold function denoising of CDMA signal［J］.Video Engineering，2013，37（7）：75-78（in Chinese）.

［4］ LIK F，WANG Zh.Application of improved wavelet threshold denoising in speech recognition［J］.Computer Technology and Development，2013，23（5）：231-234（in Chinese）.

［5］ CHEN Y X.Ant spatial clustering based on fuzzy if-then rule［J］.Mathematics in Practice and Theory，2011，41（19）：114-119（in Chinese）.

［6］ LIM，LUO H Y，ZHENG X L，et al.Image segmentation based on improved Otsu algorithm［J］.Journal of Nanjing University of Science and Technology，2012，36（2）：332-337（in Chinese）.

［7］ HONG H Y，YAN L X，GUO X Y，et al.Approach to extract moving targets from production line under complex scenes［J］.Journal of Huazhong University of Science and Technology，2012，40（7）：57-61（in Chinese）.

［8］ XIE Y Sh，F(xiàn)AN X P，LIAO Zh F，et al.Weighted cluster fusion algorithm based on graph［J］.Application Research of Computers，2013，30（4）：1015-1016（in Chinese）.

［9］ JINGGQ，CHEN DW.A finite element nodal ordering with algebraic graph theory［J］.Journal of Tongji University，2010，38（6）：929-934（in Chinese）.

［10］ MENG Q T.Segmentation algorithms based on the natural scene graph and clustering image［D］.Suzhou：Soochow University，2010：32-46（in Chinese）.

［11］ WANG X S，ZHOU M Q，F(xiàn)AN Y CH，et al.The algorithm of graph cut using HSI weights in color image segmentation［J］.Journal of Image and Graphics，2011，16（2）：221-226（in Chinese）.

［12］ CUIB G，MENG A X.Fast remote sensing image segmentation algorithm based on nearest neighbor direct graph［J］.Computer Science，2013，40（10）：274-278（in Chinese）.

Research of image segmentation based on graph theory and minimum cut set algorithm

ZHANG Jian，LIBaiyan
（College of Information Engineering，Huanghuai University，Zhumadian 463000，China）

In order to improve the quality of image segmentation，graph theory and minimal cut set algorithm were used.Firstly，using the pixel points of image as the mapping nodes of the graph theory，the node weight were calculated by the ratio of the balance factor and the shared nearest neighbor nodes.Then，the minimum cut set of the image was established based on the minimized energy equation，the gray value of the segmentation block was extracted as the block feature vector and the image was segmented by minimum spanning tree.The adjacent regions were judged to be combined or to be segmented by judging function.Finally the algorithm flow was given.The results show that the target information can be segmented by this algorithm.This algorithm has good robustness and small peak memory.

image process；minimum cut set；weight；minimum spanning tree

TN911.73

A

10.7510／jgjs.issn.1001-3806.2014.06.030

1001-3806（2014）06-0863-04

張 健（1980-），男，碩士，講師，研究方向?yàn)樾盘?hào)處理、智能控制。

E-mail：hhzhj＠foxmail.com

2013-12-25；

2014-03-07