基于K均值聚類和粒子群優(yōu)化的多核SVM圖像分割①

吳迪,戴芳,郭文艷,胡勝(西安理工大學(xué) 理學(xué)院,西安 70054)(西安交通大學(xué) 機械制造系統(tǒng)工程國家重點實驗室,西安 70049)

?

基于K均值聚類和粒子群優(yōu)化的多核SVM圖像分割①

吳迪1,戴芳1,郭文艷1,胡勝2
1(西安理工大學(xué) 理學(xué)院,西安 710054)
2(西安交通大學(xué) 機械制造系統(tǒng)工程國家重點實驗室,西安 710049)

摘 要:圖像分割是圖像理解和計算機視覺的重要內(nèi)容.針對單核SVM在進行圖像分割過程中不能兼顧分割精度高和泛化性能好的問題,提出一種基于K均值聚類和優(yōu)化多核SVM的圖像分割算法.該算法首先運用K均值聚類算法自動選取訓(xùn)練樣本,然后提取其顏色特征和紋理特征作為訓(xùn)練樣本的特征屬性,并使用其對構(gòu)造的多核SVM分割模型進行訓(xùn)練,最后用粒子群優(yōu)化算法對多核核參數(shù)、懲罰因子以及核權(quán)重系數(shù)聯(lián)合尋優(yōu),使生成的多核SVM具有更好的分割性能.實驗結(jié)果表明,本文方法在有效提取圖像目標細節(jié)的同時,獲得了更高的分割精度,與基于單核的SVM分割模型相比,具有更強的泛化能力.

關(guān)鍵詞:圖像分割; 核函數(shù); 支持向量機; 粒子群優(yōu)化; K均值聚類

圖像分割是研究如何有效地將圖像分割成各具特性的區(qū)域并提取目標區(qū)域,分割質(zhì)量的好壞很大程度上決定著后續(xù)的圖像分析和圖像理解的效果[1,2].分割的實質(zhì)就是對圖像的像素進行分類,選擇分類性能優(yōu)良的智能算法對于圖像分割具有重要意義.

SVM 在解決小樣本、高維、非線性模式分類問題上具有良好的性能,有效解決了過學(xué)習(xí)、維數(shù)災(zāi)難等問題,具有較好的泛化能力[3-6].Yu等[7]利用SVM 的特性提出了改進SVM 算法,通過減少訓(xùn)練樣本冗余而保留有效的支持向量,在顯著減少耗時的同時有效保留了分割精度.Wang等人[8]則首先提取樣本點的顏色特征和紋理特征,利用樣本點的特征屬性訓(xùn)練SVM ,然后運用訓(xùn)練好的 SVM 對彩色圖像進行分割,由于文中僅采用局部高斯核函數(shù)且其相應(yīng)的參數(shù)為人為設(shè)定,其泛化性能和分割精度均有待提高.Liu 等[9]提出了一種集成多尺度技術(shù)、混合模型和 SVM等方法的SAR 圖像分割算法,其效果優(yōu)于直接使用SVM分類器進行分割效果.Yang等[10]提出運用最小二乘支持向量機對彩色圖像進行分割,該方法自動選取訓(xùn)練樣本并提取其顏色特征與紋理特征,問題的關(guān)鍵在于支持向量機核函數(shù)的選擇以及核參數(shù)的確定.

相關(guān)研究表明,在運用 SVM 進行圖像分割時,其核函數(shù)的設(shè)計和選擇尤為重要,核函數(shù)的選取和新核函數(shù)構(gòu)造的好壞對SVM圖像分割的效率和泛化性能產(chǎn)生巨大影響,且訓(xùn)練樣本選取的方式也會影響SVM圖像分割的質(zhì)量.現(xiàn)有的基于 SVM方法分割圖像核函數(shù)多為單核核函數(shù),一定條件下表現(xiàn)出一定的學(xué)習(xí)和泛化能力.但 SVM 分割圖像中的核函數(shù)構(gòu)造和選擇及相應(yīng)參數(shù)的設(shè)定至今也沒有一套完善的理論,通常可用的幾種基本形式的核函數(shù)具有不同的映射特性,在不同的應(yīng)用場合表現(xiàn)出很大的性能差異,運用SVM 方法分割圖像時只采用單個核函數(shù)并非合理.鑒于此,為了克服SVM 算法在圖像分割應(yīng)用中的局限,提高分割精度.本文提出一種基于K均值聚類和優(yōu)化多核SVM的彩色圖像分割算法.通過粒子群算法對多核SVM各參數(shù)進行聯(lián)合尋優(yōu),獲取最優(yōu)的多核支持向量機分類模型.同時,為了有效獲取圖像的特征信息,降低SVM模型的復(fù)雜度,自動選取訓(xùn)練樣本,提取訓(xùn)練樣本的顏色特征和紋理特征并將它們?nèi)诤铣商卣飨蛄考?基于特征向量集用優(yōu)化的多核SVM模型對原圖像進行分割.最后通過實驗驗證了優(yōu)化多核SVM 圖像分割算法的有效性.

1　K均值聚類提取圖像特征

訓(xùn)練樣本的選擇在很大程度上影響了SVM的分類性能,傳統(tǒng)的訓(xùn)練樣本選取是隨機選取降低了圖像分割的自適應(yīng)性.本文運用K-均值聚類自動提取SVM 的訓(xùn)練樣本,將初始聚類數(shù)目設(shè)定為兩類,即目標和背景.K均值聚類算法具體步驟如下:

1)設(shè)定聚類數(shù)目C={ck|k=1,2,…,c}(本文c=2),初始類簇中心δk(k =1,2)以及誤差上界ξ; 找到距離設(shè)定的聚類中心最近的像素yi( i=1,2,…,n),并將該像素分配到該類中;

2)修正類簇中心: 計算每個類簇像素的均值,根據(jù)類簇的均值更新類簇中心,獲得新的類簇中心σk(k=1,2,…,c);

自動選取訓(xùn)練樣本之后,本文提取訓(xùn)練樣本的六種特征屬性,其中包括四種顏色特征: RGB顏色空間的 r,g,b 通道的像素值和亮度 i ; 兩個紋理特征參量: 角二階矩(ASM)和對比度.將其作為輸入向量來訓(xùn)練多核核函數(shù) SVM 分類器.

2　優(yōu)化多核 SVM 圖像分割方法

2.1SVM 多核核函數(shù)

在運用 SVM 對彩色圖像進行分割時,核函數(shù)的選擇和核參數(shù)的確定對數(shù)據(jù)的映射以及最終的決策效果發(fā)揮著至關(guān)重要的作用.通過引入核函數(shù),可極大的提高機器學(xué)習(xí)的非線性處理能力,同時也保持了學(xué)習(xí)機器在高維空間中的內(nèi)在線性,從而使得分割效果更好.

常見的核函數(shù)主要分為全局核函數(shù)和局部核函數(shù)兩大類[11-13].而多項式核函數(shù)和高斯核函數(shù)分別作為全局核和局部核的典型代表成為 SVM 的核函數(shù)首選[14].圖1給出不同類型的核函數(shù)在給定參數(shù)情形下函數(shù)值隨測試點x的變化曲線.

圖1　不同核函數(shù)的變化曲線

由圖1 可知,對于任意單核函數(shù),通過選擇不同的參數(shù),其呈現(xiàn)出不同的尺度效應(yīng).多項式核函數(shù)具有全局特性,泛化性能較強; 高斯核函數(shù)具有局部性,學(xué)習(xí)能力更優(yōu).而基于多核學(xué)習(xí)的方法的多核模型是一類靈活性更強的學(xué)習(xí)模型.利用多核代替單核,能增強決策函數(shù)的可解釋性,并能獲得比單核模型更優(yōu)的性能.它同時具備兩個單核的優(yōu)點,即具有更好的學(xué)習(xí)能力和泛化能力.

為了驗證多核核函數(shù) SVM 圖像分割相對于單核核函數(shù) SVM 的優(yōu)勢,本文分別選取多項式核(全局核)和徑向基核(局部核)進行凸組合,如下所示:

其中,Knew為新構(gòu)造的多核函數(shù),KPoly和KRbf分別為多項式核和徑向基核,λi(i=1,2)為權(quán)重系數(shù),滿足λi≥0且λ1+λ2=1.

2.2基于粒子群的多核SVM參數(shù)優(yōu)化算法

在選定SVM的核函數(shù)類型后,其權(quán)重系數(shù)和核參數(shù)的確定也會影響圖像分割的效果.核參數(shù)或懲罰因子C選擇不合理,就會降低SVM的圖像分割精度; 而核參數(shù)s和權(quán)重系數(shù)l越小,響應(yīng)區(qū)間越窄,得到的最優(yōu)分類面經(jīng)驗風(fēng)險也越小,但是結(jié)構(gòu)風(fēng)險增大,而且容易出現(xiàn)過擬合現(xiàn)象,導(dǎo)致SVM 的圖像分割性能降低.所以多核核參數(shù)的選取對SVM圖像分割性能起決定性作用.而粒子群優(yōu)化算法[15]利用位置和速度的概念,避免了遺傳、交叉和變異等操作,具有變量少、效率高等優(yōu)點,被廣泛應(yīng)用于智能優(yōu)化領(lǐng)域.為此本文選擇粒子群算法對這幾類參數(shù)進行聯(lián)合優(yōu)化,構(gòu)建優(yōu)化多核SVM分類器.

本文PSO粒子編碼為(d,σ,C,λ1),其中d,σ,C分別為多項式核和徑向基核的核參數(shù),λ1為多項式核的權(quán)重,徑向基核權(quán)重λ2=1-λ1.基于粒子群的多核SVM參數(shù)優(yōu)化算法流程如下圖2 所示.

圖2　基于粒子群的多核SVM參數(shù)優(yōu)化算法流程

2.3基于K均值聚類和優(yōu)化多核SVM的圖像分割

本文提出的圖像分割算法分為三個處理階段: 第一個階段是基于K均值聚類訓(xùn)練樣本的自動選取,將像素點分為前景和背景兩類并提取其特征屬性; 第二個階段是優(yōu)化多核 SVM 模型; 第三個階段是基于優(yōu)化多核 SVM 的圖像分割.采用本文算法進行圖像分割的流程如圖3所示.

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

本文的所有實驗均在軟件 MATLAB R2012b 中進行的,運行環(huán)境為 CPU 3.2GHz 內(nèi)存 2G,硬盤500G,操作系統(tǒng)是Windows 7.為了驗證本文優(yōu)化多核方法的有效性,同時增加分割的難度,以保證算法評價的實用性和客觀性.分別選取三幅復(fù)雜背景下的圖像進行實驗,其圖像尺寸大小為200*200.由于均是在自然光的條件下采集,部分反光呈白色斑點,且表面粘有雜質(zhì),它們之間呈現(xiàn)出目標邊界模糊、目標不連續(xù)和目標灰度不均勻等特點.

圖3　基于K均值聚類和粒子群優(yōu)化的多核SVM圖像分割算法流程

3.1訓(xùn)練樣本選取圖像分割效果對比

本文為了避免人工方法選取和標注訓(xùn)練樣本的主觀性不足,運用K均值聚類自動選取一定數(shù)目的訓(xùn)練樣本,之后提取其特征屬性用來訓(xùn)練優(yōu)化的多核SVM.實驗中多核 SVM 的參數(shù)通過粒子群算法進行尋優(yōu),不敏感系數(shù)e取0.1,PSO 基本參數(shù)設(shè)置如下:種群規(guī)模數(shù)20,最大遺傳代數(shù)100,加速度因子C1= C2= 0.1,其迭代效果如下圖4 所示.經(jīng)過5次迭代時多核SVM達到最優(yōu)效果.此時迭代得最優(yōu)的多核SVM參數(shù)為d =2,C =5.0,σ= 1.8,λ1=0.6.將此優(yōu)化多核的SVM模型對圖像進行分割,實驗效果如圖 5所示.

圖4　多核 SVM 參數(shù)尋優(yōu)結(jié)果

圖5　訓(xùn)練樣本不同選取方式的優(yōu)化多核SVM圖像分割效果

由圖5圖可以看出,當訓(xùn)練樣本人工選取時,其分割結(jié)果受主觀因素影響很大,誤將部分目標當作背景,將部分背景當作目標,導(dǎo)致分割結(jié)果不佳.而自動選取訓(xùn)練樣本結(jié)合優(yōu)化多核SVM分割方法則幾乎精確將所有的目標均分割出來,分割結(jié)果既突出了目標,又保留了局部細節(jié),獲得了較理想的效果.

3.2不同核函數(shù)的SVM 圖像分割效果對比

同時為了有效驗證優(yōu)化多核 SVM 的彩色圖像分割相對于單核SVM的優(yōu)越性,在相同的實驗條件下分別選取多項式核(核參數(shù)=2)、徑向基核(核參數(shù)=5.0,=1.8)進行效果比對,分割效果如圖 6 所示.

圖6　不同核函數(shù)的SVM 圖像分割效果

如圖6所示,原始圖像中(b)和(c)的目標較多且分布零散,部分圖像由于視覺較遠看起來非常模糊且(b)圖中花朵正下方的陰影部分區(qū)域顏色與背景和目標差別都不大,很容易誤認為是目標,(d)圖中左下角的花朵目標視覺極其模糊且與背景色差小,容易誤判.在基于單核SVM模型的分割結(jié)果中將這些細節(jié)錯分,分割效果不理想,其效果如圖6中間兩幅所示.而本文基于K均值聚類結(jié)合多核SVM的分割方法(見b3,c3 和d3所示)很好的表征了這些目標區(qū)域,精確的提取了圖像目標,分割結(jié)果在突出了目標的同時又保留了局部細節(jié),更加符合人們的主觀分割效果.為了進一步分析實驗結(jié)果,選取分割精度和分割時間作為衡量圖像分割性能優(yōu)劣的指標,其比較結(jié)果如表1所示.

表1　不同核函數(shù)支持向量機的分割精度和分割效率對比

由表1可以看出,對于給定的待分割圖像,多核SVM 在訓(xùn)練精度上與單核核函數(shù)SVM 相當,但是在分割精度方面卻有了一定幅度的提高.隨著待分割圖像的復(fù)雜度逐漸增加,三種核函數(shù) SVM 算法的圖像分割精度都有所降低,但是多核SVM 的降低幅度最小,說明了多核 SVM 相對于單核 SVM 具有更強的泛化能力.同時由于多核函數(shù)包含了局部核和全局核的綜合特性,其算法的圖像分割時間相對于其他兩種單核均有所增加.

4　結(jié)語

本文提出了一種基于K均值聚類和優(yōu)化多核SVM的彩色圖像分割算法.該算法充分考慮全局核和局部核函數(shù)的優(yōu)勢,通過加權(quán)組合形成多核SVM并運行粒子群算法對其參數(shù)進行尋優(yōu),獲取優(yōu)化多核SVM,然后將提取的圖像特征作為分類器的輸入對其進行分割,同時訓(xùn)練樣本的自動選取為多核SVM分割提供了良好的輸入特征,克服了人工選取樣本的主觀性.實驗結(jié)果表明,利用本文方法可以獲得較理想的分割效果,相比單核支持向量機具有更高的分割精度和泛化性能.

參考文獻

1Cheng HD,Jiang XH.Sun H,et al.Color image segmentation: Advances and prospects.Pattern Recognition,2001,34(12): 2259–2281.

2許新征,丁世飛,史忠植,等.圖像分割的新理論和新方法.電子學(xué)報,2010,38(2):76–82.

3Vapnik V.The Nature of Statistical Learning Theory.2nd ed.,Springer Berlin,2000.

4Yu H,Chang CC.Scenery image segmentation using support vector machines.Fundamenta Informaticae,2004,61(3): 379 –388.

5徐海祥,喻莉,朱光喜,等.基于支持向量機的磁共振腦組織圖像分割.中國圖象圖形學(xué)報,2006,10(10):1275–1280.

6黃建燈,陳慶全.基于支持向量機的紅細胞彩色圖像分割.計算機系統(tǒng)應(yīng)用,2009,18(1):35–38.

7Yu Z,Wong HS,Wen G.A modified support vector machine and its application to image segmentation.Image and Vision Computing,2011,29(1): 29–40.

8Wang XY,Wang QY,Yang HY,et al.Color image segmentation using automatic pixel classification with support vector machine.Neurocomputing,2011,74(18): 3898–3911.

9 Liu T,Wen XB,Quan JJ,et al.Multiscale SAR image segmentation using support vector machines.Congress on Image and Signal Processing,2008.CISP’08.IEEE.2008,3.706–709.

10Yang HY,Wang XY,Wang QY,et al.LS-SVM based image segmentation using color and texture information.Journal of Visual Communication and Image Representation,2012,23(7): 1095–1112.

11Stricker MA,Orengo M.Similarity of color images.IS&T/SPIE’s Symposium on Electronic Imaging: Science & Technology.International Society for Optics and Photonics.1995.381–392.

12張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機.自動化學(xué)報,2000,26(1):32–42.

13Cristianini N,Shawe-Taylor J.An introduction to support vector machines and other kernel-based learning methods.Mining Yor12 Conference,2000,32(8): 1–28.

14汪洪橋,孫富春,蔡艷寧等.多核學(xué)習(xí)方法.自動化學(xué)報,2010,36(8):1037–1050.

15Kennedy J.Particle swarm optimization.Encyclopedia of Machine Learning.Springer US.2010: 760–766.

Method for Image Segmentation Based on Optimized Multi-Kernel SVM and K-means Clustering

WU Di1,DAI Fang1,GUO Wen-Yan1,HU Sheng2
1(School of Science,Xi’an University of Technology,Xi’an 710054,China)
2(State Key Laboratory for Manufacturing Systems Engineering,Xi’an Jiaotong University,Xi’an 710049,China)

Abstract:Image segmentation is an important topic in image understanding and computer vision.When support vector machine (SVM)is used for image segmentation,the design of its kernel and selection of the parameters directly affect the segmentation effect.Considering the problem that SVM based on single kernel could not keep the balance between the segmentation accuracy and generalization performance,an image segmentation algorithm using optimized multi-kernel SVM (OMKSVM)based on K-means clustering was proposed in this paper.According to the multi-kernel learning theory,the new multi-kernel is constructed by a linear combination of single kernels.Firstly,the K-means clustering algorithm was applied to obtain the training samples for MKSVM automatically.Then color and texture features were extracted from the image as attributes of training samples of MKSVM,Particle Swarm Optimization (PSO)algorithm was employed to optimize the kernel parameters,the weight coefficient and the punishment coefficient of SVM simultaneously.Finally the OMKSVM was obtained to segment image.Three groups of complex color image were selected to verify the correctness of the proposed method.The results demonstrate that our method can segment the color images effectively,and has stronger generalization ability comparing with the single kernel SVM-based method.

Key words:image segmentation; kernel function; support vector machine (SVM); particle swarm optimization (PSO); K-means clustering

基金項目:①國家自然科學(xué)基金(91120014);陜西省教育廳科研計劃(12JK0534)

收稿時間:2015-07-18;收到修改稿時間:2015-09-08