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

張 健，李宏升

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

1 引 言

圖像分割是按照某種算法把它分成多個(gè)區(qū)域并將感興趣的目標(biāo)提取出來(lái)[1]，在圖像處理領(lǐng)域中屬于重要組成部分，對(duì)于分析目標(biāo)特征具有重要意義。

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

本文采取基于圖論閾值對(duì)圖像分割，首先構(gòu)造圖論和圖像的映射函數(shù)關(guān)系，每個(gè)頂點(diǎn)通過(guò)點(diǎn)來(lái)映射，每條邊通過(guò)線(xiàn)來(lái)映射；然后用基于區(qū)域?qū)傩缘膱D像邊緣決策表，不同像素點(diǎn)或不同組像素點(diǎn)之間的灰度特征差作為權(quán)重系數(shù)，通過(guò)基于決策屬性權(quán)重來(lái)構(gòu)造像素聯(lián)系圖；接著采用聚類(lèi)計(jì)算像素到目標(biāo)類(lèi)和背景類(lèi)的相似程度，最小生成樹(shù)策略解決偽割集問(wèn)題；最后給出圖像閾值設(shè)定以及算法流程。實(shí)驗(yàn)仿真顯示分割圖像邊緣信息的效果明顯清晰，消除了圖像分割中存在的過(guò)合并和欠合并現(xiàn)象，且信息熵大。

2 算法描述

2.1 圖像像素屬性

2.1.1 基于關(guān)聯(lián)函數(shù)的圖像像素空間連接

將一幅圖像視為一個(gè)帶權(quán)的無(wú)向圖G，G為有序三元組[V(G)，E(G)，χG]，其中V(G)是非空的頂點(diǎn)集，E(G)是不與V(G)相交的邊集，而χG是關(guān)聯(lián)函數(shù)，把欲分割圖像中每一個(gè)像素作為圖論數(shù)據(jù)集合中的頂點(diǎn)，則:

χG(e)=uv,

(1)

其中：u、v以像素為端點(diǎn)的分割線(xiàn)段表示，使圖G的每條邊對(duì)應(yīng)圖G的無(wú)序頂點(diǎn)對(duì)[8]。這樣每個(gè)頂點(diǎn)通過(guò)點(diǎn)來(lái)映射，每條邊通過(guò)線(xiàn)來(lái)映射，線(xiàn)連接著映射該邊端點(diǎn)的點(diǎn)，連接同一條邊的兩頂點(diǎn)。圖1給出了4個(gè)像素點(diǎn)的連接圖，其中V(G)=(v1,v2,v3,v4)為頂點(diǎn)集，E(G)=(v1v2,v1v3,v1v4,v2v3,v2v4,v3v4)為無(wú)向邊集。

圖1 4個(gè)像素點(diǎn)的連接Fig.1 Connection of four pixels

2.1.2 基于區(qū)域?qū)傩缘膱D像邊緣決策表

據(jù)像素灰度的不同把原始圖像分為若干不連通的區(qū)域[9]，w(vi,vj)為e(vi,vj)∈χG(e)對(duì)應(yīng)的 2 個(gè)區(qū)域之間的邊緣權(quán)重，設(shè)圖像分割邊緣決策表為:

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

(2)

其中：U={x1,x2,…,xn}為圖像分割邊緣論域，C={a1,a2,…,am}和D分別稱(chēng)為圖像邊緣條件屬性集和分割決策屬性集，?a∈C，Va=[la,ra]?R是實(shí)值區(qū)間。決策表里有多個(gè)屬性，并且對(duì)每一個(gè)屬性，任意兩個(gè)像素區(qū)域間都有這個(gè)屬性關(guān)系，因此，任意兩個(gè)像素區(qū)域間都要連 |C∪D|條邊，構(gòu)成了以像素區(qū)域?yàn)閷傩躁P(guān)系的圖像。表1給出了基于屬性關(guān)系像素區(qū)域間決策表。

表1像素區(qū)域間的屬性關(guān)系決策表

Tab.1 Relationship of decision table between regions of pixels

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

不同像素點(diǎn)或不同組像素點(diǎn)之間的灰度特征差作為權(quán)重系數(shù)，通過(guò)基于決策屬性權(quán)重來(lái)構(gòu)造像素聯(lián)系圖[10]，結(jié)果如圖2所示，其中標(biāo)號(hào)1代表的權(quán)重是{a[0.8，0.9]，b[2，0.5]}；2代表的權(quán)重是{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 基于決策屬性權(quán)重的像素聯(lián)系圖Fig.2 Pixel connection diagram based on decision of weight

2.2 圖像割集劃分

2.2.1 圖像割集區(qū)域相似度

假設(shè)目標(biāo)像素的聚類(lèi)集合為A，背景像素的聚類(lèi)集合為B,像素灰度k到目標(biāo)類(lèi)的最小距離d1到背景類(lèi)的最小距離d2，即:

(3)

則像素到目標(biāo)類(lèi)和背景類(lèi)的相似程度大小為：

(4)

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

2.2.2 圖像割集最小決策樹(shù)

計(jì)算像素與目標(biāo)和背景區(qū)域相似度后，需要把虛假像素相似度進(jìn)行區(qū)分，評(píng)價(jià)各個(gè)不同分類(lèi)狀態(tài)，使相似度聚類(lèi)問(wèn)題轉(zhuǎn)化為數(shù)據(jù)優(yōu)化問(wèn)題[12]。設(shè)圖G中分割區(qū)域邊的權(quán)重和為：

(5)

式中：權(quán)重最小的w(T)為圖G的最小生成樹(shù)。

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

2.2.3 合并區(qū)域判定

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

(6)

欲分割2個(gè)相鄰區(qū)域內(nèi)之間相似性的特征量

(7)

區(qū)域間的差異值：

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

(8)

合并判決條件為：

(9)

當(dāng)滿(mǎn)足合并判決條件時(shí),說(shuō)明這兩個(gè)區(qū)域內(nèi)像素節(jié)點(diǎn)間的相似性較大,反之,則彼此之間的關(guān)聯(lián)性較低[14-15]。

2.3 圖像閾值分割

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

T=ζγi,j,

(10)

當(dāng)常數(shù)ζ較大時(shí)，分割效果較粗糙,較小時(shí),分割效果較精細(xì),不同ζ值會(huì)得到不同的分割效果，設(shè)定常數(shù)：

(11)

2.4 算法過(guò)程

①輸入圖像，采用基于關(guān)聯(lián)函數(shù)的圖像像素連通區(qū)域的計(jì)算權(quán)重；

②邊緣決策表對(duì)連通區(qū)域劃分；

③最小決策樹(shù)計(jì)算區(qū)域相似度；

④判斷合并條件,滿(mǎn)足執(zhí)行步驟5，否則執(zhí)行步驟2；

⑤ζ精度控制；

⑥輸出圖像。

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

利用本文方法對(duì)不同圖像進(jìn)行分割實(shí)驗(yàn),并與其他方法進(jìn)行比較,同時(shí)對(duì)不同算法的分割結(jié)果采用定量實(shí)驗(yàn)準(zhǔn)則進(jìn)行相應(yīng)的評(píng)價(jià)分析。

3.1 視覺(jué)分割效果

采用3種復(fù)雜圖像,不同算法仿真結(jié)果如圖3所示。

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

3.2 定性分析

熵值反映圖像包含的平均信息量，采用熵值對(duì)分割效果進(jìn)行評(píng)價(jià)，熵H定義為：

(12)

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

表2 分割后的圖像信息熵對(duì)比

本文算法分割后的圖像信息熵比較大，說(shuō)明分割圖像得到的信息比其他算法大，這是因?yàn)楫?dāng)滿(mǎn)足合并判決條件時(shí),不需要分割，則保留了圖像信息。

3.3 算法性能分析

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

由表3的結(jié)果證明，本文算法處理時(shí)間比其它算法處理時(shí)間至少要節(jié)約1 s時(shí)間,具有實(shí)時(shí)性，錯(cuò)割率較低，可以保證分割的效率，這是因?yàn)閷?duì)合并區(qū)域判定后使區(qū)域內(nèi)部差別盡可能小，區(qū)域之間差別盡可能大。

表3 不同算法的錯(cuò)割率、處理時(shí)間對(duì)此

4 結(jié) 論

采用圖論閾值算法，構(gòu)造圖論和圖像的映射函數(shù)關(guān)系，每個(gè)頂點(diǎn)通過(guò)點(diǎn)來(lái)映射，每條邊通過(guò)線(xiàn)來(lái)映射；用基于區(qū)域?qū)傩缘膱D像邊緣決策表，不同像素點(diǎn)或不同組像素點(diǎn)之間的灰度特征差作為權(quán)重系數(shù)，通過(guò)基于決策屬性權(quán)重來(lái)構(gòu)造像素聯(lián)系圖；接著采用聚類(lèi)計(jì)算像素到目標(biāo)類(lèi)和背景類(lèi)的相似程度，最小生成樹(shù)策略解決偽割集問(wèn)題；最后給出圖像閾值設(shè)定以及算法流程。得出分割圖像邊緣信息的效果明顯清晰，消除了圖像分割中存在的過(guò)合并和欠合并現(xiàn)象，且信息熵大，為以后研究圖像分割提供一種新的思路。

[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] 張?zhí)?一種改進(jìn)的基于圖的圖像分割方法[J].西華大學(xué)學(xué)報(bào),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].南京信息工程大學(xué)學(xué)報(bào),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] 方富貴.圖論的算法和應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程,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] 盧鵬,王錫淮,肖健梅.連續(xù)屬性決策表離散化的圖論方法[J].計(jì)算機(jī)工程與應(yīng)用,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] 洪漢玉,顏露新,郭祥云,等.生產(chǎn)線(xiàn)復(fù)雜場(chǎng)景條件下的動(dòng)目標(biāo)提取方法[J].華中科技大學(xué)學(xué)報(bào),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] 段薇,馬麗,路向陽(yáng).基于信息增益和最小距離分類(lèi)的決策樹(shù)改進(jìn)算法[J].科學(xué)技術(shù)與工程,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] 熊小華,劉艷芳,寧愛(ài)兵.圖的Steiner最小樹(shù)的競(jìng)爭(zhēng)決策算法[J].上海理工大學(xué)學(xué)報(bào),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].電子測(cè)量與儀器學(xué)報(bào),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].計(jì)算機(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)