基于空間分布支持向量機(jī)的圖像分割

楊 偉

（泉州理工學(xué)院 通識(shí)教育中心，福建 泉州362000）

基于空間分布支持向量機(jī)的圖像分割

楊 偉

（泉州理工學(xué)院 通識(shí)教育中心，福建 泉州362000）

利用模糊聚類(lèi)與支持向量機(jī)結(jié)合的方法，將圖像的空間分布信息作為支持向量機(jī)的特征分量，并用模糊聚類(lèi)獲得的分類(lèi)結(jié)果作為支持向量機(jī)的初始訓(xùn)練樣本對(duì)圖像的所有像素點(diǎn)進(jìn)行分類(lèi)，同一類(lèi)中的像素點(diǎn)形成一個(gè)分割區(qū)域，以此獲得圖像分割.實(shí)驗(yàn)表明，該方法獲得的圖像分割效果較好，在一定程度上解決了特征維數(shù)過(guò)大所導(dǎo)致的維數(shù)災(zāi)難問(wèn)題.

模糊聚類(lèi)；支持向量機(jī)；圖像分割；空間分布

圖像分割是圖像處理與機(jī)器視覺(jué)必不可少的重要環(huán)節(jié)，其方法很多，如閾值法、聚類(lèi)法、區(qū)域生長(zhǎng)法、神經(jīng)網(wǎng)絡(luò)等，但研究表明單一的圖像分割方法難以達(dá)到理想的效果.近年來(lái)，隨著新理論和新方法［1］的不斷出現(xiàn)，多種特征的融合和多種分割方法的結(jié)合在圖像分割中得到廣泛應(yīng)用，并取得了較好效果，如：文獻(xiàn)［2］結(jié)合二維直方圖和模糊C－均值聚類(lèi)的方法，有效地抑制了噪聲，并在充分考慮圖像中各個(gè)像素的灰度值分布的基礎(chǔ)上，克服了噪聲和灰度不均勻敏感的缺點(diǎn)；文獻(xiàn)［3］引入Fisher線性判別法對(duì)K均值的聚類(lèi)圖像分割做了進(jìn)一步細(xì)化，克服了K均值聚類(lèi)易受樣本的幾何形狀及排列影響的缺點(diǎn)，同時(shí)實(shí)現(xiàn)了無(wú)監(jiān)督聚類(lèi)的圖像分割.目前，關(guān)于如何選取有效的圖像空間分布特征進(jìn)行分類(lèi)以及如何對(duì)一般灰度分布非線性的圖像進(jìn)行分類(lèi)的問(wèn)題研究得較少，由此本文以圖像的空間分布作為分類(lèi)特征信息，通過(guò)核函數(shù)將一般非線性灰度圖像的特征信息映射變換到高維特征空間，并以支持向量機(jī)構(gòu)造線性判別函數(shù)來(lái)實(shí)現(xiàn)原空間中的非線性灰度圖像分割.

1 圖像的空間分布信息

理想的圖像分割不但要求所有的特征應(yīng)當(dāng)屬于相同的目標(biāo)區(qū)域，而且還要求他們?cè)诳臻g上應(yīng)該緊湊，所以，成功的分割算法應(yīng)當(dāng)既用到圖像像素的特征信息，又用到定位于圖像像素的空間分布的信息.文獻(xiàn)［4］提出了一種圖像空間分布信息的度量的模糊聚類(lèi)方法（FSCM），該方法在計(jì)算樣本的離散性時(shí)同時(shí)考慮特征向量的離散性和空間位置的距離.

設(shè)圖像定義為在W×H的矩形網(wǎng)格上的二維數(shù)據(jù)集S＝ ｛（i，j）∶1≤i≤W，1≤j≤H｝，其中（i，j）為圖像像素的坐標(biāo).把坐標(biāo)地址為s＝（si，sj）的像素值x標(biāo)為特征xs，索引s表示該像素在圖像網(wǎng)格中的位置.為了能既利用圖像的特征信息，又能有效利用圖像的空間分布信息聚類(lèi)，對(duì)特征xs和第r類(lèi)中心vr的相異性的測(cè)量drs采用特征相異性dFrs和空間相異性dSrs的組合：

其中：α是加權(quán)因子；dFrs為傳統(tǒng)的距離度量，表示xs與第r類(lèi)原型vr特征離散性，公式為：

drSs的計(jì)算應(yīng)滿足性質(zhì)：如果1個(gè)像素的位置處于目標(biāo)區(qū)域內(nèi)，那么應(yīng)該認(rèn)為它與目標(biāo)區(qū)域類(lèi)更有相似之處.

在圖像網(wǎng)格中，定義每個(gè)像素位置s的鄰域?yàn)棣莝，鄰域集η＝｛ηs∶s∈S｝.由于在同一鄰域內(nèi)的像素點(diǎn)彼此之間是相關(guān)的，因此，1個(gè)像素的空間相關(guān)關(guān)系可被描述為包含該點(diǎn)的鄰域.如果xs鄰域內(nèi)的所有像素點(diǎn)都屬于第r類(lèi)，那么可以認(rèn)為xs也屬于第r類(lèi)，并且歸一化設(shè)定空間相異性drSs為0；反之，如果鄰域內(nèi)沒(méi)有任何1點(diǎn)屬于第r類(lèi)，則認(rèn)為特征xs不屬于第r類(lèi)，并且置drSs歸一化為1；其他情況下drSs的范圍選取在0～1之間，數(shù)值的大小對(duì)應(yīng)于被第r類(lèi)所擁有的鄰域像素點(diǎn)個(gè)數(shù).

基于以上思想，drSs的計(jì)算公式定義為：

其中：c是所預(yù)想的分類(lèi)個(gè)數(shù)；βt是s鄰域ηs中的每個(gè)位置t的貢獻(xiàn)因子，表示點(diǎn)t對(duì)全部空間的隸屬關(guān)系；權(quán)值urs是特征xs對(duì)第r類(lèi)vr的隸屬度函數(shù)，它滿足以下2個(gè)約束條件：

一般地，鄰域越緊密，鄰域內(nèi)的點(diǎn)交互關(guān)系越強(qiáng)，而且各點(diǎn)的貢獻(xiàn)越大.因此，對(duì)于每個(gè)鄰近點(diǎn)t，βt在點(diǎn)s與點(diǎn)t之間是1個(gè)與距離相關(guān)的函數(shù)，定義為：

其中系數(shù)θ決定了2個(gè)點(diǎn)相互關(guān)系消失的快慢.θ值小表示鄰域中不同點(diǎn)所做的相似貢獻(xiàn)，θ值大表示空間的相異性更依賴臨近的像素.本文經(jīng)過(guò)多次實(shí)驗(yàn)，θ值設(shè)定為0.7.

2 基于空間分布的支持向量機(jī)

模糊聚類(lèi)算法其迭代容易陷入局部極值、迭代過(guò)程中的計(jì)算量太大、空間結(jié)構(gòu)信息未能有效利用、分割出來(lái)的區(qū)域不連續(xù)以及過(guò)分割等問(wèn)題.而支持向量機(jī)（SVM）方法［5－8］以其優(yōu)良的判別分類(lèi)性能，克服了傳統(tǒng)方法的過(guò)學(xué)習(xí)和陷入局部最小的問(wèn)題，具有很強(qiáng)的泛化能力.本文將圖像的空間分布信息作為SVM的特征向量分量，訓(xùn)練樣本由模糊C－聚類(lèi)得到初始分割提供（僅提供分類(lèi)的數(shù)目，不知道其中類(lèi)的屬性）.

假設(shè)存在訓(xùn)練樣本（x1，y1），…，（xn，yn），x∈Rd，y∈｛＋1，－1｝，其中n為樣本數(shù)，d為輸入維數(shù).當(dāng)訓(xùn)練樣本集線性不可分時(shí)，引入非負(fù)松弛變量ξi，i＝1，2，…，n.分類(lèi)超平面最優(yōu)化問(wèn)題描述為

其中C＞0為懲罰系數(shù).對(duì)于樣本線性不可分的情況，可以利用非線性變換φ（xi），i＝1，…，n，將樣本映射到某一更高維的特征空間中，使樣本在這個(gè)高維的特征空間中實(shí)現(xiàn)線性正確分類(lèi).

通過(guò)求解最優(yōu)化問(wèn)題，可得到相應(yīng)的最優(yōu)決策函數(shù)：

在特征空間中樣本之間的內(nèi)積用核函數(shù)K（xi，xj）表示，因此上式可寫(xiě)為f（x）＝sgn｛wTφ（x）＋分類(lèi)超平面的權(quán)值向量w＊和閾值b＊為

其中x＊（1）和x＊（－1）分別表示2類(lèi)中任意1個(gè)支持向量.在訓(xùn)練圖像中隨機(jī)選取n個(gè)訓(xùn)練樣本點(diǎn)作為輸入空間X＝｛xn｝和輸出域Y＝｛yn｝，其中xi＝ ｛x，dSi｝＝ ｛x，dS1i，dS2i，…，dSki｝，x為圖像樣本點(diǎn)xi的特征分量，dSi＝ ｛dS1i，dS2i，…，dSki｝為xi空間分布信息.由此可確定最優(yōu)分類(lèi)判別函數(shù)的參數(shù)〈w＊，b＊〉，對(duì)圖像進(jìn)行分割.

1）支持向量機(jī)參數(shù)的選擇.核函數(shù)的選取直接影響支持向量機(jī)的性能［9］.由于多項(xiàng)式核函數(shù)具有計(jì)算簡(jiǎn)單、識(shí)別率高的優(yōu)點(diǎn)，因此本文采用多項(xiàng)式核函數(shù)：K（x，xi）＝ ［σ（x·xi）＋1］q.訓(xùn)練過(guò)程需要調(diào)整σ和q，通過(guò)采用網(wǎng)格搜索方式在二維參數(shù)空間遍歷這2個(gè)參數(shù)，并觀察其對(duì)圖像分割的影響，得到最佳經(jīng)驗(yàn)值q＝3，σ＝1.

2）懲罰因子C和輸入樣本個(gè)數(shù)的選擇.懲罰因子C的選擇應(yīng)適中，如果C值過(guò)大，就會(huì)增大對(duì)錯(cuò)分樣本的懲罰，導(dǎo)致錯(cuò)分樣本減少，分類(lèi)器的VC維增大，分類(lèi)器的泛化性能變?nèi)?，程序運(yùn)行時(shí)間過(guò)長(zhǎng)；如果C值過(guò)小，就會(huì)減小對(duì)錯(cuò)分樣本的懲罰，導(dǎo)致錯(cuò)分樣本增多，分類(lèi)器的VC維減小，分類(lèi)器的泛化性能變?nèi)?，圖像分割精度不高.經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，C＝100時(shí)圖像分割精度較為理想.

從圖像隨機(jī)選取n個(gè)樣本作為訓(xùn)練樣本輸入空間X，并由模糊聚類(lèi)分割已初分割圖像選取對(duì)應(yīng)的輸出域Y，本文選取n＝500.

3）空間鄰域窗口的選擇.對(duì)于圖像的樣本點(diǎn)s，鄰域窗口可以選擇3×3.點(diǎn)s鄰域內(nèi)的點(diǎn)對(duì)點(diǎn)s空間信息dSi的貢獻(xiàn)由式（3）和式（6）決定.

4）SVM多分類(lèi)方法選取.常用的多分類(lèi)方法有一對(duì)多方法［10－11］、一對(duì)一方法［10－11］和k－ 類(lèi)SVM方法［12］，由于一對(duì)多方法和一對(duì)一方法存在不可分區(qū)域，所以本文采用k－類(lèi)SVM方法.該方法對(duì)于給定l個(gè)訓(xùn)練樣本 （x1，y1），（x2，y2），…，（xl，yl），其中xi∈Rn，yi∈ ｛1，2，…，k｝，i＝1，2，…，l，k個(gè)二類(lèi)分類(lèi)器通過(guò)求解一個(gè)優(yōu)化問(wèn)題同時(shí)獲得，其中第i個(gè)分類(lèi)器wTiφ（x）＋bi將第i類(lèi)的訓(xùn)練樣本與其他訓(xùn)練樣本分開(kāi)，其決策函數(shù)為

綜合以上描述，基于空間分布支持向量機(jī)圖像分割的具體算法為：

第1步 先將圖像進(jìn)行模糊C－均值聚類(lèi)，初步分得k個(gè)區(qū)域（k＝1，2，3，…），其中將屬于第r個(gè)區(qū)域的樣本點(diǎn)標(biāo)記為r.令yr＝r作為SVM的輸出域Y＝ ｛yn｝的元素，并由（3）、（6）式得到每個(gè)像素點(diǎn)空間特征分量dSi＝ ｛dS1i，dS2i，…，dSki｝.

第2步 在圖像中隨機(jī)選取n個(gè)樣本點(diǎn)｛xn｝（n足夠大）作為輸入空間，每個(gè)樣本點(diǎn)的特征向量為xi＝ ｛x，dS1i，dS2i，…，dSki｝，其中x是該樣本點(diǎn)的像素值，dSri是像素點(diǎn)i對(duì)第r類(lèi)的空間鄰域信息.輸出域Y＝｛1，－1｝（兩類(lèi)問(wèn)題）；或Y＝｛1，2，…，k｝（多類(lèi)問(wèn)題），則訓(xùn)練集表示為S＝ ｛（x1，1），…，（xk，k）｝.

第3步 通過(guò)訓(xùn)練集求得第i個(gè)類(lèi)的關(guān)聯(lián)：一個(gè)權(quán)重向量和一個(gè)偏置，（wi，bi），i∈ ｛1，…，m｝，得到?jīng)Q策函數(shù)：

第4步 將特征向量xi代入（7）式，得出每個(gè)特征的分類(lèi)yr＝c（xi）.將相同輸出的特征向量歸為同一類(lèi).

第5步 將得到的特征向量新分類(lèi)重新作為訓(xùn)練樣本返回第2步進(jìn)行迭代.當(dāng)?shù)趎次迭代屬于第r分類(lèi)像素?cái)?shù)（Nnr）與第n－1次迭代屬于第r分類(lèi)像素?cái)?shù)（Nn－1r）之差其中r＝1，2，…，k，ε為較小正整數(shù)）時(shí)算法收斂結(jié)束迭代.

第6步 以該類(lèi)任意支持向量樣本點(diǎn)的第1個(gè)分量作為該類(lèi)每個(gè)像素的灰度值，完成圖像分割.

3 實(shí)驗(yàn)結(jié)果和分析

實(shí)驗(yàn)分別用模糊C－均值（FCM）、空間分布模糊C－均值（FSCM）、支持向量機(jī)（SVM）和空間分布支持向量機(jī)（SSVM）對(duì)細(xì)菌圖進(jìn)行兩類(lèi)分割，圖片大小為256×256，領(lǐng)域?yàn)?×3.實(shí)驗(yàn)圖像見(jiàn)圖1，實(shí)驗(yàn)結(jié)果如下表1.分割錯(cuò)誤率的計(jì)算公式為：，其中N為圖像中所有像素的個(gè)數(shù)，Nr為分割參考圖中屬于第r分類(lèi)的像素個(gè)數(shù)，N′r為算法分割結(jié)果屬于第r分類(lèi)的像素個(gè)數(shù)，r＝1，2，…，k，k為所分類(lèi)數(shù)目.

圖1 4種不同分割方法結(jié)果圖

表1 4種不同方法分割錯(cuò)誤率的比較

實(shí)驗(yàn)表明：?jiǎn)渭兊哪：鼵－均值圖像分割的識(shí)別率最低，空間分布模糊C－均值的識(shí)別率相對(duì)模糊C－均值有所提高；支持向量機(jī)和空間分布支持向量機(jī)之間的差別不大，它們的識(shí)別率比模糊聚類(lèi)有大幅地提高，達(dá)到了很好的效果（90%）.實(shí)驗(yàn)表明融合模糊聚類(lèi)支持向量機(jī)的方法優(yōu)于單純的模糊聚類(lèi)方法.

4 結(jié)論

本文算法結(jié)合了圖像的灰度和圖像空間分布信息，并以此作為支持向量機(jī)的特征向量，通過(guò)融合2種圖像特征，克服了聚類(lèi)算法的不足，是對(duì)多種特征、多種方法融合的圖像分割的一種嘗試.本文討論的分割算法都只是針對(duì)灰度圖像，引用的特征有限（一幅圖像包含顏色、灰度、紋理等多種特征），如何從圖像提取到合適的分割特征，以及綜合多種重要特征來(lái)作為支持向量機(jī)的特征分量，是需進(jìn)一步研究的問(wèn)題.

［1］林瑤，田捷，羅希平.圖像分割方法綜述［C］∥全國(guó)信息與自動(dòng)化技術(shù)推廣應(yīng)用大會(huì)論文集.北京：中國(guó)自動(dòng)化學(xué)會(huì)，2001：86－97.

［2］甄文智，范九倫，謝維信.基于二維直方圖的圖像模糊聚類(lèi)分割新方法［J］.北京：計(jì)算機(jī)應(yīng)用工程，2003，39（15）：89－91.

［3］Clausi D A.K－means Iterative Fisher（KIF）unsupervised clustering algorithm applied to image texture segmentation［J］.Pattern Recognition，2002（35）：1959－1972.

［4］Xia Yong，F(xiàn)eng Dagan，Wang Tianjiao，et al.Image segmentation by clustering of spatial patterns［J］.Pattern Recognition Letters，2007（28）：1548－1555.

［5］Boser B，Guyon I，Vapnik V.A training algorithm for optimal margin classifiers［C］∥Proceedings of the 5th Annual Workshop on Computational Learning Theory.Pittsburgh：ACMPress，1992：144－152.

［6］Cortes C，Vapnik V.Support vector networks［J］.Machine Learning，1995，20（3）：273－297.

［7］Scholkopf B，Burges C，Vapnik V.Extracting support data for a given task［C］∥Proceedings of First International Conference on Knowledge Discovery ＆Data Mining.Menlo Park：AAAI Press，1995：262－267.

［8］Vapnik V.Statistical Learning Theory［M］.許建華，張學(xué)工，譯.北京：電子工業(yè)出版社，2004：324－360.

［9］付巖，王耀威，王偉強(qiáng)，等.SVM用于基于內(nèi)容的自然圖像分類(lèi)和檢索［J］.北京：計(jì)算機(jī)學(xué)報(bào)，2003，26（10）：1261－1265.

［10］Hsu C W，Lin C J.A comparison of methods for multi－class support vector machines［J］.IEEE Transactions on Neural Networks，2002，13（2）：415－425.

［11］Weston J，Watkins C.Multi－class support vector machines［D］.London：Technical Report，1998.

［12］Platt J，Cristianini N，Taylor J.Large margin DAGs for multiclass classification［C］∥Proceedings of Neural Information Processing Systems.Boson：MIT Press，2000：547－553.

Image segmentation based on SVMusing spatial patterns

YANG Wei
（CenterforGeneralEducation，QuanzhouInstituteofTechnology，Quanzhou362000，China）

We propose a ne whybrid methods for image segmentation that base on support vector maching（SVM）combined withC－mean fuzzy clustering.This method spatial pattern information is used as component characteristics of the SVM，and the classification results from fuzzy clustering are used as the initial samples of the SVM.Then the pixels of the image are classified by SVMand the pixels in the same class form a segmental region.The experimental results sho wthat the ne wmethods combing fuzzy clustering and SVMcan get better results and the error ratio caused by the segmentation is decreased.

fuzzy clustering；support vector machines；image segmentation；spatial patterns

TP391.4

A

1004－4353（2012）01－0083－04

2011－11－29

楊偉（1981—），男，助教，研究方向?yàn)樾〔ǚ治黾捌鋺?yīng)用.