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

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

?

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

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

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

關鍵詞:圖像分割; 核函數; 支持向量機; 粒子群優化; K均值聚類

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

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

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

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

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

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

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

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

2　優化多核 SVM 圖像分割方法

2.1SVM 多核核函數

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

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

圖1　不同核函數的變化曲線

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

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

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

2.2基于粒子群的多核SVM參數優化算法

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

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

圖2　基于粒子群的多核SVM參數優化算法流程

2.3基于K均值聚類和優化多核SVM的圖像分割

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

3　實驗結果與分析

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

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

3.1訓練樣本選取圖像分割效果對比

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

圖4　多核 SVM 參數尋優結果

圖5　訓練樣本不同選取方式的優化多核SVM圖像分割效果

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

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

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

圖6　不同核函數的SVM 圖像分割效果

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

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

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

4　結語

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

參考文獻

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

2許新征,丁世飛,史忠植,等.圖像分割的新理論和新方法.電子學報,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徐海祥,喻莉,朱光喜,等.基于支持向量機的磁共振腦組織圖像分割.中國圖象圖形學報,2006,10(10):1275–1280.

6黃建燈,陳慶全.基于支持向量機的紅細胞彩色圖像分割.計算機系統應用,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張學工.關于統計學習理論與支持向量機.自動化學報,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汪洪橋,孫富春,蔡艷寧等.多核學習方法.自動化學報,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

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

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