基于圖論閾值算法的圖像分割研究

張 健，李宏升

(黃淮學院 信息工程學院，河南 駐馬店 463000)

1 引 言

圖像分割是按照某種算法把它分成多個區域并將感興趣的目標提取出來[1]，在圖像處理領域中屬于重要組成部分，對于分析目標特征具有重要意義。

基于圖論的圖像分割國內研究為：常見的方法有圖論最小生成樹方法、圖論主集等[2]，它們的一個共同特點是將圖像中的像素以聚類或者分組的方法進行劃分，進而完成對圖像的分割，但是不會將漸變區域與常數區域合并，使圖像出現誤分割；隨后圖論最優分割模型[3]，可以得到圖的全局性質，但是需要構造的度量函數并非最佳，算法的時間復雜度較高，對復雜的圖像進行分割時，會導致圖像分割速度較慢，從而在很多實時視覺處理場合無法采用。國外研究為：Wu和Leahy提出用圖論最小割進行圖像分割[4]，利用分割的像素之間相似性最小化作為分割標準，但該方法易出現較小的分割；Shi和Malik提出了一種改進的歸一化割的分割方法[5]，通過計算所有連接邊的權值在整個圖的邊集權值中所占的分量，消除Wu和Leahy方法的較小分割偏向，但是受圖像大小限制，難以實用；Grady和Schwartz針對Shi和Malik的問題，提出了圖論等周分割的方法[6]，這種方法不需要相似矩陣的重構操作，復雜圖像出現誤分割；Felzenszwalb提出采用圖論全局信息進行分割[7]，采用近鄰函數和灰度函數作為權值和相似度函數，但分割精度上受到一定影響。

本文采取基于圖論閾值對圖像分割，首先構造圖論和圖像的映射函數關系，每個頂點通過點來映射，每條邊通過線來映射；然后用基于區域屬性的圖像邊緣決策表，不同像素點或不同組像素點之間的灰度特征差作為權重系數，通過基于決策屬性權重來構造像素聯系圖；接著采用聚類計算像素到目標類和背景類的相似程度，最小生成樹策略解決偽割集問題；最后給出圖像閾值設定以及算法流程。實驗仿真顯示分割圖像邊緣信息的效果明顯清晰，消除了圖像分割中存在的過合并和欠合并現象，且信息熵大。

2 算法描述

2.1 圖像像素屬性

2.1.1 基于關聯函數的圖像像素空間連接

將一幅圖像視為一個帶權的無向圖G，G為有序三元組[V(G)，E(G)，χG]，其中V(G)是非空的頂點集，E(G)是不與V(G)相交的邊集，而χG是關聯函數，把欲分割圖像中每一個像素作為圖論數據集合中的頂點，則:

χG(e)=uv,

(1)

其中：u、v以像素為端點的分割線段表示，使圖G的每條邊對應圖G的無序頂點對[8]。這樣每個頂點通過點來映射，每條邊通過線來映射，線連接著映射該邊端點的點，連接同一條邊的兩頂點。圖1給出了4個像素點的連接圖，其中V(G)=(v1,v2,v3,v4)為頂點集，E(G)=(v1v2,v1v3,v1v4,v2v3,v2v4,v3v4)為無向邊集。

圖1 4個像素點的連接Fig.1 Connection of four pixels

2.1.2 基于區域屬性的圖像邊緣決策表

據像素灰度的不同把原始圖像分為若干不連通的區域[9]，w(vi,vj)為e(vi,vj)∈χG(e)對應的 2 個區域之間的邊緣權重，設圖像分割邊緣決策表為:

S={U,C∪D,V,F},

(2)

其中：U={x1,x2,…,xn}為圖像分割邊緣論域，C={a1,a2,…,am}和D分別稱為圖像邊緣條件屬性集和分割決策屬性集，?a∈C，Va=[la,ra]?R是實值區間。決策表里有多個屬性，并且對每一個屬性，任意兩個像素區域間都有這個屬性關系，因此，任意兩個像素區域間都要連 |C∪D|條邊，構成了以像素區域為屬性關系的圖像。表1給出了基于屬性關系像素區域間決策表。

表1像素區域間的屬性關系決策表

Tab.1 Relationship of decision table between regions of pixels

U12345678a0．911．31．31．41．41．64b20．5312133d10010111

不同像素點或不同組像素點之間的灰度特征差作為權重系數，通過基于決策屬性權重來構造像素聯系圖[10]，結果如圖2所示，其中標號1代表的權重是{a[0.8，0.9]，b[2，0.5]}；2代表的權重是{a[0.9，0.6]，b[0.9，0.5]}；3是{a[0.9，0.1]，b[0.9，0.5]}；4是{a[0.6，0.9]，b[3，0.5]}；5是{a[4，0.9]，b[3，0.5]}；6是{a[0.8，0.3]，b[2，3]}；7是{a[1.4，1.3]，b[0.9，3]}；8是{a[1.3，1.3]，b[0.9，3]}；9是{a[0.6，0.3]，b[3，3]}；10是{a[4，1.3]，b[3，3]}；11是{a[0.8，0.4]，b[2，2]}；12是{a[0.7，0.4]，b[0.9，2]}；13是{a[0.3，1.4]，b[0.9，2]}；14是{a[0.6，0.4]，b[3，2]}；15是{a[4，0.4]，b[3，2]}。

圖2 基于決策屬性權重的像素聯系圖Fig.2 Pixel connection diagram based on decision of weight

2.2 圖像割集劃分

2.2.1 圖像割集區域相似度

假設目標像素的聚類集合為A，背景像素的聚類集合為B,像素灰度k到目標類的最小距離d1到背景類的最小距離d2，即:

(3)

則像素到目標類和背景類的相似程度大小為：

(4)

其中:η[χG(e)=1]標記像素與目標區域更相似，它能夠保證與目標更相似的像素被劃分到目標區域[11]，η[χG(e)=0]標記像素與背景區域更相似，它能夠保證與背景更相似的像素被劃分到背景區域。

2.2.2 圖像割集最小決策樹

計算像素與目標和背景區域相似度后，需要把虛假像素相似度進行區分，評價各個不同分類狀態，使相似度聚類問題轉化為數據優化問題[12]。設圖G中分割區域邊的權重和為：

(5)

式中：權重最小的w(T)為圖G的最小生成樹。

假設集合P用于存放G的最小生成樹中的頂點，集合Q存放G的最小生成樹中的邊。令集合P的初值為P={v1}(假設構造最小生成樹時，從頂點v1出發)，集合Q的初值為Q=Φ。從所有p∈P、v∈(V-P)選取具有最小權值的邊pv，將頂點v加入集合P中，將邊pv加入集合Q中，如此不斷重復，直到P=V時，最小生成樹構造完畢，這時集合Q中包含了最小生成樹的所有邊[13]，從而有效地解決分割過程中出現的偽割集以為目標分割不完整的問題。

2.2.3 合并區域判定

圖像割集最小決策樹形成后，需要使區域內部差別盡可能小，區域之間差別盡可能大，使用判定函數判定2個區域是分割還是合并。設欲分割區域內部像素點間相似性的特征量φ1,φ1分割區域最小生成樹中邊緣權重的最大值：

(6)

欲分割2個相鄰區域內之間相似性的特征量

(7)

區域間的差異值：

γi,j=min(φ2,φ3),

(8)

合并判決條件為：

(9)

當滿足合并判決條件時,說明這兩個區域內像素節點間的相似性較大,反之,則彼此之間的關聯性較低[14-15]。

2.3 圖像閾值分割

設閾值T用于控制分割的精度,其定義為:

T=ζγi,j,

(10)

當常數ζ較大時，分割效果較粗糙,較小時,分割效果較精細,不同ζ值會得到不同的分割效果，設定常數：

(11)

2.4 算法過程

①輸入圖像，采用基于關聯函數的圖像像素連通區域的計算權重；

②邊緣決策表對連通區域劃分；

③最小決策樹計算區域相似度；

④判斷合并條件,滿足執行步驟5，否則執行步驟2；

⑤ζ精度控制；

⑥輸出圖像。

3 實驗仿真

利用本文方法對不同圖像進行分割實驗,并與其他方法進行比較,同時對不同算法的分割結果采用定量實驗準則進行相應的評價分析。

3.1 視覺分割效果

采用3種復雜圖像,不同算法仿真結果如圖3所示。

其中(a1)、(b1)、(c1)為待分割的原始圖像，(a2)、(b2)、(c2)是圖論主集法分割效果，(a3)、(b3)、(c3)是圖論最優分割模型分割效果，(a4)、(b4)、(c4)是圖論最小分割模型分割效果，(a5)、(b5)、(c5)是圖論等周分割法分割效果，(a6)、(b6)、(c6)是本文分割效果，從分割效果上可以看出，本文提出的算法分割得到的圖像邊緣信息的效果明顯清晰，一定程度上消除了圖像分割中存在的過合并和欠合并現象。這是因為本文算法對分割區域生成最小決策樹后還要計算相鄰區域的差異性。

3.2 定性分析

熵值反映圖像包含的平均信息量，采用熵值對分割效果進行評價，熵H定義為：

(12)

其中：pi為像素級為i∈[0，255]的出現的相對頻率。H越大則圖像的平均信息量越大，表2給出了分割后的圖像信息熵對比。

表2 分割后的圖像信息熵對比

本文算法分割后的圖像信息熵比較大，說明分割圖像得到的信息比其他算法大，這是因為當滿足合并判決條件時,不需要分割，則保留了圖像信息。

3.3 算法性能分析

為了比較不同算法的性能，表3給出了不同算法的錯割率、處理時間。

由表3的結果證明，本文算法處理時間比其它算法處理時間至少要節約1 s時間,具有實時性，錯割率較低，可以保證分割的效率，這是因為對合并區域判定后使區域內部差別盡可能小，區域之間差別盡可能大。

表3 不同算法的錯割率、處理時間對此

4 結 論

采用圖論閾值算法，構造圖論和圖像的映射函數關系，每個頂點通過點來映射，每條邊通過線來映射；用基于區域屬性的圖像邊緣決策表，不同像素點或不同組像素點之間的灰度特征差作為權重系數，通過基于決策屬性權重來構造像素聯系圖；接著采用聚類計算像素到目標類和背景類的相似程度，最小生成樹策略解決偽割集問題；最后給出圖像閾值設定以及算法流程。得出分割圖像邊緣信息的效果明顯清晰，消除了圖像分割中存在的過合并和欠合并現象，且信息熵大，為以后研究圖像分割提供一種新的思路。

[1] 張俊娜,馮云芝.基于量子最大熵多閾值算法的圖像分割研究[J].激光與紅外,2013,43(5):578-582.

Zhang J N, Feng Y Z. Image segmentation research based on quantum maximum entropy algorithm [J].LaserandInfrared,2013,43(5):578-582.(in Chinese)

[2] Cheng L J, Ding Y S, Hao K R,etal. An ensemble kernel classifier with immune clonal selection algorithm for automatic discriminant of primary open- angle glaucoma [J].NeuroComputing, 2012, 83(4):1-11.

[3] 張田.一種改進的基于圖的圖像分割方法[J].西華大學學報,2011,30(1):61-64.

Zhang T. An Improved graph-based image segmentation method [J].JournalofXihuaUniversity,2011,30(1):61-64.(in Chinese)

[4] Wu Z, Leahy R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1993, 15(11):1101-1113.

[5] Shi J, Malik J. Normalized cuts and image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2000, 22(8):888-905.

[6] Grady L, Schwartz E L. Isoperimetric graph partitioning for image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2006, 28(3):469-475.

[7] Felzenszwalb P. Efficient graph-based image segmentation [J].InternationalJournalofComputerVision,2004, 59(2):167-181.

[8] 陳麗娟.矩陣論中的圖論匹配法[J].南京信息工程大學學報,2011,3(6):571-573.

Chen L J . Matching method of graph theory in matrix theory [J].JournalofNanjingUniversityofInformationScienceandTechnology,2011,3(6):571-573.(in Chinese)

[9] 方富貴.圖論的算法和應用研究[J].計算機與數字工程,2012,40(2):115-117.

Fang F G. Study on the Algorithm and applications in graph theory [J].ComputerandDigitalEngineering,2012,40(2):115-117. (in Chinese)

[10] 盧鵬,王錫淮,肖健梅.連續屬性決策表離散化的圖論方法[J].計算機工程與應用,2012,48(6):13-16.

Lu P, Wang X H, Xiao J M. Graph method of discretization of decision table with continuous attributes [J].ComputerEngineeringandApplications,2012,48(6):13-16. (in Chinese)

[11] 洪漢玉,顏露新,郭祥云,等.生產線復雜場景條件下的動目標提取方法[J].華中科技大學學報,2012,40(7):57-61.

Hong H Y,Yan L X,Guo X Y,etal. Approach to extract moving targets from production line under complex scenes [J].JournalofHuazhongUniversityofScienceAndTechnology,2012,40(7):57-61. (in Chinese)

[12] 段薇,馬麗,路向陽.基于信息增益和最小距離分類的決策樹改進算法[J].科學技術與工程,2013,13(6):1643-1646.

Duan W, Ma L, Lu X Y. An improved algorithm of decision tree based on information gain and minimum distance classification [J].ScienceTechnologyandEngineering,2013,13(6):1643-1646. (in Chinese)

[13] 熊小華,劉艷芳,寧愛兵.圖的Steiner最小樹的競爭決策算法[J].上海理工大學學報,2012,34(5):1643-1646.

Xiong X H, Liu Y F, Ning A B. Competitive decision algorithm for the steiner minimal tree problem in graphs[J].JournalofUniversityofShanghaiforScienceandTechnology,2012,34(5):1643-1646. (in Chinese)

[14] 李蓀,李哲英,劉佳,等.圖論分割算法算子消耗模型OCM的建立與分析[J].電子測量與儀器學報,2012,26(11):1011-1018.

Li S,Li Z Y, Liu J,etal. Operator cost model and analysis based on graph-based segmentation [J].JournalofElectronicMeasurementandInstrument,2012,26(11):1011-1018. (in Chinese)

[15] 張乾,馮夫健,林鑫,等.一種基于圖論的圖像分割算法[J].計算機工程,2012,38(18):194-197.

Zhang Q,Feng F J,lin X,etal. An image segmentation algorithm based on graph theory [J].ComputerEngineering,2012,38(18):194-197. (in Chinese)