楊 偉

（泉州理工學院 通識教育中心，福建 泉州362000）

基于空間分布支持向量機的圖像分割

楊 偉

（泉州理工學院 通識教育中心，福建 泉州362000）

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

模糊聚類；支持向量機；圖像分割；空間分布

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

1 圖像的空間分布信息

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

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

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

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

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

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

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

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

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

2 基于空間分布的支持向量機

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

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

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

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

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

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

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

2）懲罰因子C和輸入樣本個數(shù)的選擇.懲罰因子C的選擇應適中，如果C值過大，就會增大對錯分樣本的懲罰，導致錯分樣本減少，分類器的VC維增大，分類器的泛化性能變?nèi)酰绦蜻\行時間過長；如果C值過小，就會減小對錯分樣本的懲罰，導致錯分樣本增多，分類器的VC維減小，分類器的泛化性能變?nèi)?，圖像分割精度不高.經(jīng)過實驗發(fā)現(xiàn)，C＝100時圖像分割精度較為理想.

從圖像隨機選取n個樣本作為訓練樣本輸入空間X，并由模糊聚類分割已初分割圖像選取對應的輸出域Y，本文選取n＝500.

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

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

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

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

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

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

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

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

第6步 以該類任意支持向量樣本點的第1個分量作為該類每個像素的灰度值，完成圖像分割.

3 實驗結(jié)果和分析

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

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

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

實驗表明：單純的模糊C－均值圖像分割的識別率最低，空間分布模糊C－均值的識別率相對模糊C－均值有所提高；支持向量機和空間分布支持向量機之間的差別不大，它們的識別率比模糊聚類有大幅地提高，達到了很好的效果（90%）.實驗表明融合模糊聚類支持向量機的方法優(yōu)于單純的模糊聚類方法.

4 結(jié)論

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

［1］林瑤，田捷，羅希平.圖像分割方法綜述［C］∥全國信息與自動化技術推廣應用大會論文集.北京：中國自動化學會，2001：86－97.

［2］甄文智，范九倫，謝維信.基于二維直方圖的圖像模糊聚類分割新方法［J］.北京：計算機應用工程，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］.許建華，張學工，譯.北京：電子工業(yè)出版社，2004：324－360.

［9］付巖，王耀威，王偉強，等.SVM用于基于內(nèi)容的自然圖像分類和檢索［J］.北京：計算機學報，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—），男，助教，研究方向為小波分析及其應用.