張 健，李白燕

（黃淮學院信息工程學院，駐馬店463000）

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

張 健，李白燕

（黃淮學院信息工程學院，駐馬店463000）

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

圖像處理；最小割集；權值；最小生成樹

引 言

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

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

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

1 算法描述

1.1 基于圖論的圖像表示

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

Fig.1 Optimization process

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

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

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

由于圖的節(jié)點對應了圖像中的各個像素點，對圖像的分割等價于將節(jié)點集V分割成不相交子集，分割表示為：

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

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

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

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

式中，E1（xi）為相似能量，表示將節(jié)點i賦值為xi的代價；E2（xi，xj）為先驗能量，表示相鄰節(jié)點i和j分別賦值為xi和xj的代價，λ為加權系數(shù)。

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

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

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

1.4 算法流程

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

2 實驗仿真

2.1 視覺分割效果

采用3種不同類型的經(jīng)典圖像：多峰模式Lena圖像、雙峰模式pout圖像、單峰模式rice圖像。不同算法仿真結果如圖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是本文中算法分割效果。從分割效果上可以看出，本文中算法分割出目標信息，而其它算法分割出來的目標物體含有大量的背景信息，不能準確地分割出目標來。

2.2 魯棒性分析

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

對原始Lena圖像逐漸改變灰度，像素個數(shù)的對比指標來檢驗該算法是否具有魯棒性，如表1所示。

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

Table 1 Pixels of image gray level before and after change

2.3 時間復雜度分析

為了比較算法的復雜度，表2中給出了運行時間和峰值內(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

本文中算法的運行時間少，所需的峰值內(nèi)存小，對圖像處理具有實時性。這是因為歐式距離計算邊的權值，通過最小生成樹對圖分割。

3 小 結

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

張 ?。?980-），男，碩士，講師，研究方向為信號處理、智能控制。

E-mail：hhzhj＠foxmail.com

2013-12-25；

2014-03-07