基于規(guī)范化的B樣條密度模型的聚類算法

劉 哲, 譚振江, 王洪君

(1. 吉林師范大學(xué) 計(jì)算機(jī)學(xué)院, 吉林 四平 136000； 2. 江蘇大學(xué) 電氣信息工程學(xué)院, 江蘇 鎮(zhèn)江 212013)

0 引 言

聚類分析在模式識別和圖像處理領(lǐng)域中具有廣泛的應(yīng)用前景[1,2]。圖像識別和圖像分割是其主要的應(yīng)用方面, 目前研究已經(jīng)取得了許多成果。早在1979年, Coleman和Andrews就提出了用聚類分析進(jìn)行圖像分割。Yao等[3]提出了基于數(shù)學(xué)形態(tài)學(xué)的K-means聚類算法實(shí)現(xiàn)圖像分割。Zhao等[4]提出了廣義的模糊C-means聚類算法實(shí)現(xiàn)灰度圖像有效分割。Liu等[5]提出了一種結(jié)合空間信息的模糊譜聚類算法實(shí)現(xiàn)對噪聲圖像分割。這些方法大多數(shù)都是直接在圖像上進(jìn)行聚類分析, 由于圖像的復(fù)雜性和無規(guī)律性, 存在很多缺陷?；诿芏染垲惙椒ㄊ歉鶕?jù)密度概念對數(shù)據(jù)對象進(jìn)行聚類和分割的。它根據(jù)數(shù)據(jù)對象的密度或某種密度函數(shù)生成聚類。ISC(Intelligent Subspace Clustering)[6], Rough-DBSCAN(Density Based Spatial Clustering Applications with Noise)[7], DBSC(Density-Based Spatial Clustering)[8]等都是具有代表性的基于密度的聚類方法, 并在應(yīng)用中表現(xiàn)了良好性能。

在基于密度的聚類方法中, 通常選擇熟知的高斯、t、Poisson和α等分布。這些帶有先驗(yàn)性質(zhì)的參數(shù)化方法并非總能給出對各種醫(yī)學(xué)圖像合適的描述, 模型的基本假設(shè)與實(shí)際的物理模型之間存在較大差異, 即有“模型失配”問題。非參數(shù)密度估計(jì)方法在無需對模型做任何假設(shè)前提下, 具有有效擬合任意形式的概率分布性能, 文獻(xiàn)[9]提出基于核密度估計(jì)(KDE: Kernel Denstity Estimate)的聚類方法, 該方法可有效地實(shí)現(xiàn)腹部CT圖像分割, 但隨著樣本量增加計(jì)算量也不斷增大, 而且存在平滑參數(shù)難以自適應(yīng)估計(jì)及計(jì)算速度較慢等缺點(diǎn)。為此, 文獻(xiàn)[10]提出了無監(jiān)督的非參數(shù)正交多項(xiàng)式密度模型實(shí)現(xiàn)圖像分割, 但隨著樣本量增加正交多項(xiàng)式密度估計(jì)以恒速率收斂, 而且正交多項(xiàng)式密度估計(jì)是一個(gè)函數(shù)而不是概率密度函數(shù)。

筆者以圖像數(shù)據(jù)為研究對象, 利用B樣條函數(shù)在函數(shù)逼近方面的優(yōu)勢, 在研究圖像灰度密度分布基礎(chǔ)上, 提出一種基于B樣條密度函數(shù)的圖像聚類算法。首先定義灰度圖像的非參數(shù)標(biāo)準(zhǔn)化的B樣條密度估計(jì)模型, 通過NNBEM(Non-parametric B-spline Expectation Maximum)算法估計(jì)模型的參數(shù), 最后根據(jù)貝葉斯準(zhǔn)則實(shí)現(xiàn)對圖像的聚類。

1 傳統(tǒng)的混合模型

設(shè)X={X1,X2,…,XN}為隨機(jī)觀察數(shù)據(jù)集,Xi是d維隨機(jī)變量,Xi間相互獨(dú)立,fi(x|θi)(i=1,2,…,K)是對應(yīng)的概率密度函數(shù), 其中,x∈Rd是Xi取值,θi是模型參數(shù)。若將Xi樣本按一定權(quán)重混合后, 再從中任取一個(gè)進(jìn)行觀察, 則其概率密度函數(shù)

(1)

在有限概率混合模型中, 最常見的是高斯混合模型(GMM: Gaussian Mixture Model), 模型中每個(gè)高斯密度函數(shù)的未知參數(shù)θ=(α1,μ1,Σ1,α2,μ2,Σ2,…,αk,μk,Σk),μk為均值,Σk為協(xié)方差, 則用EM算法[11]進(jìn)行極大似然估計(jì)。

算法1

1) 模型參數(shù)初始賦值。假設(shè)混合模型的分類數(shù)k已知, 對混合模型中各密度分布待估計(jì)參數(shù)θ進(jìn)行初始設(shè)置。

2) 期望步。計(jì)算在第n次迭代時(shí)每個(gè)樣本i屬于第j類的后驗(yàn)概率

(2)

3) 最大化步。通過求解對數(shù)似然方程, 計(jì)算期望值到達(dá)極大值點(diǎn)時(shí)的參數(shù)： 均值μ, 協(xié)方差矩陣Σj及權(quán)重αj, 用于下次迭代

(3)

(4)

(5)

4) 滿足結(jié)束條件則停止, 否則轉(zhuǎn)至2)。

2 基于規(guī)范化的B樣條密度模型的圖像聚類

2.1 基于B樣條密度函數(shù)的模型構(gòu)造

在數(shù)值分析中, B樣條[12]是樣條曲線一種特殊的表示形式, 采用逼近原理構(gòu)造曲線、 曲面, 保留了Bezier方法中的優(yōu)點(diǎn), 是B樣條基曲線的線性組合, 也是目前廣泛應(yīng)用的一種擬合方法。

Curry和SchCoenberg提出d次(d=1,2,…)k(k=1,2,…)個(gè)節(jié)點(diǎn)的每個(gè)B樣條曲線段表示為

(6)

(7)

設(shè)x1,x2,…,xn是n個(gè)獨(dú)立同分布f的隨機(jī)樣本, 線性組合f是多個(gè)B樣條的混合, 則B樣條密度函數(shù)估計(jì)為

(8)

(9)

2.2 聚類算法

根據(jù)定義的非參數(shù)規(guī)范化的B樣條密度模型, 不需要預(yù)先假設(shè)圖像像素的條件概率密度函數(shù), 直接根據(jù)樣本數(shù)據(jù)估計(jì)出該數(shù)據(jù)場的概率密度函數(shù)。若模型中參數(shù)θk=(b0,k,…,bN-1,k)[11], 圖像樣本數(shù)據(jù)分類數(shù)k=1,…,K, 則fN(x)=f(x|θk)。采用NNBEM算法估計(jì)模型參數(shù), 得到圖像聚類結(jié)果。

算法2 (NNBEM算法)

輸入： 圖像樣本數(shù)據(jù)X=(x1,…,xn)[12], 分類數(shù)K

輸出： 聚類結(jié)果

Step1 Initialization: 使用K-means算法初始劃分為K類, 并對參數(shù)進(jìn)行初始化設(shè)置

(10)

(11)

其中nk是第k類包含的樣本個(gè)數(shù),l=0,…,N-1。

Step2 Expectation: 在m次迭代時(shí), 像素xi屬于第k類的后驗(yàn)概率

(12)

Step3 Maximization: 根據(jù)第m次迭代得到樣本的后驗(yàn)概率, 第m+1次迭代更新參數(shù)為

(13)

(14)

(15)

其中j(xi)表示像素xi的類別標(biāo)簽。

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

為驗(yàn)證提出的NNBEM算法效果, 該實(shí)驗(yàn)使用Dell公司圖像專用工作站, Matlab7.0作為實(shí)驗(yàn)開發(fā)工具, 采用的模擬圖像和實(shí)驗(yàn)數(shù)據(jù)來源于美國加州大學(xué)伯克利分校的BSDB標(biāo)準(zhǔn)測試圖像數(shù)據(jù)庫[13]。為驗(yàn)證聚類算法的聚類性能, 對該算法與非參數(shù)正交多項(xiàng)式混合模型的聚類算法(SNEM: Stochastic Nonparametric Expectation Maximum)[10]進(jìn)行了比較。為評價(jià)聚類算法性能, 采用指標(biāo)VI(Variation of Information)、 ARI(Adjusted Rand Index)[14]和F-measure[15]衡量。

對于有n個(gè)樣本的數(shù)據(jù)集, VI利用參考聚類圖像的熵和實(shí)際聚類結(jié)果的熵計(jì)算獲得, 用來衡量實(shí)際聚類結(jié)果相對參考聚類結(jié)果的信息變化, VI值越小, 其聚類結(jié)果越準(zhǔn)確。計(jì)算如下

VVI(S,S′)=H(S)+H(S′)-2I(S,S′)

(16)

其中H和I分別表示聚類結(jié)果的熵和S和S′兩個(gè)聚類結(jié)果之間的互信息。其計(jì)算如下

(17)

(18)

其中P(k)為圖像中任意一個(gè)像素屬于第k個(gè)聚類的概率；P(k,k′)為像素在S中屬于第k個(gè)聚類并且同時(shí)在S′中屬于第k′個(gè)聚類的聯(lián)合概率。

指標(biāo)ARI把樣本類別劃分看作是它們之間一種關(guān)系, 或?qū)颖痉衷谕活? 或在不同類, 通過統(tǒng)計(jì)正確聚類對數(shù)評價(jià)算法性能。對于有n個(gè)樣本的數(shù)據(jù)集, ARI計(jì)算如下

(19)

其中nkk′為被劃分到類別k類別k′的樣本個(gè)數(shù)；AARI(S,S′)值越大, 聚類的正確率越高。

a 原始圖像 b 聚類結(jié)果

3.1 模擬圖像

采用模擬圖像, 其灰度取值范圍Ω={0,1,…,255}, 有3個(gè)聚類Λ={1,2,3}, 圖像大小為237×237像素。模擬圖像分割結(jié)果如圖1所示。從圖1中可看出, 通過筆者算法可實(shí)現(xiàn)對模擬圖像的準(zhǔn)確聚類。

3.2 真實(shí)圖像聚類

實(shí)驗(yàn)數(shù)據(jù)來源于美國加州大學(xué)伯克利分校的BSDB標(biāo)準(zhǔn)測試圖像數(shù)據(jù)庫[12], 對非參數(shù)正交多項(xiàng)式密度模型的SNEM聚類算法與筆者的NNBEM聚類算法進(jìn)行比較的結(jié)果如圖2所示。

圖2a為原始圖像, 圖2b非參數(shù)正交多項(xiàng)式混合模型SNEM算法聚類結(jié)果[10], 圖2c為筆者NNBEM算法聚類結(jié)果。從視覺角度看, 筆者提出的方法效果優(yōu)于SNEM聚類算法。

a 原圖 b SNEM算法 c 筆者NNBEM算法 d 人工分割

為量化聚類劃分的性能, 對上述圖像數(shù)據(jù)每種算法分別運(yùn)行20次, 計(jì)算其評價(jià)指標(biāo)VI、 ARI及F-measure的平均值如表1所示。從實(shí)驗(yàn)結(jié)果可看出, 筆者聚類算法NNBEM的VI指標(biāo)值小于SNEM算法, 其聚類結(jié)果較SNEM算法更準(zhǔn)確； 筆者聚類算法ARI及F-measure值均大于SNEM算法, 其聚類性能都優(yōu)于基于非參數(shù)正交多項(xiàng)式的SNEM聚類算法。

表1 兩種算法聚類算法性能比較

4 結(jié) 語

筆者提出了一種規(guī)范化的B樣條密度模型的圖像聚類算法。通過定義非參數(shù)規(guī)范化B樣條混合模型, 利用EM算法估計(jì)B樣條混合模型參數(shù), 最后根據(jù)貝葉斯準(zhǔn)則實(shí)現(xiàn)圖像聚類。該算法有效地克服了有參混合模型對每個(gè)模型分布的假設(shè)帶來的不一致問題及目前存在的非參數(shù)正交多項(xiàng)式密度函數(shù)不是概率密度函數(shù)的缺陷。實(shí)驗(yàn)結(jié)果表明, 該算法優(yōu)于SNEM算法, 對圖像聚類效果較好, 準(zhǔn)確率高。算法的計(jì)算復(fù)雜度高于SNEM算法及對初始值仍比較敏感, 如何在聚類性能和計(jì)算復(fù)雜度之間進(jìn)行折中以及如何設(shè)定初始值不影響聚類性能問題, 將是下一步研究的重點(diǎn)。

參考文獻(xiàn)：

[1] KANNAN S R, DEVI R, RAMATHILAGAM S, et al. Effective FCM Noise Clustering Algorithms in Medical Images [J]. Computers in Biology and Medicine, 2013, 43(2): 73-83.

[2]曲福恒, 胡雅婷, 馬駟良, 等. 一種高效魯棒的無監(jiān)督模糊c均值聚類算法 [J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版, 2012, 50(6): 1179-1184.

QU Fu-heng, HU Ya-ting, MA Si-liang, et al. An Efficient and Robust Clustering Algorithm for Unsupervised Fuzzy c-Means [J]. Journal of Jilin University: Science Edition, 2012, 50(6): 1179-1184.

[3]YAO Hong, DUAN Qing-ling, LI Dao-liang, et al. An Improved-Means Clustering Algorithm for Fish Image Segmentation [J]. Mathematical and Computer Modelling, 2013, 58(3/4): 784-792.

[4]ZHAO Feng, JIAO Li-cheng, LIU Han-qiang. Kernel Generalized Fuzzy C-Means Clustering with Spatial Information for Image Segmentation [J]. Digital Signal Processing, 2013, 23(1): 184-199.

[5]LIU Han-qiang, ZHAO Feng, JIAO Li-cheng. Fuzzy Spectral Clustering with Robust Spatial Information for Image Segmentation [J]. Applied Soft Computing, 2012, 12(11): 3636-3647.

[6]JAHIRABADKAR S, KULKARNI P. Isc-Intelligent Subspace Clustering, A Density Based Clustering Approach for High Dimentsional Dataset [J]. World Academy of Science, Engineering and Technology, 2009, 55: 69-73.

[7]VISWANATH P, SURESH BABU V. Rough-DBSCAN: A Fast Hybrid Density Based Clustering Method for Large Data Sets [J]. Pattern Recognition Letters, 2009, 30(16): 1477-1488.

[8]LIU Qi-liang, DENG Min, SHI Yan, et al. A Density-Based Spatial Clustering Algorithm Considering Both Spatial Proximity and Attribute Similarity [J]. Computers & Geosciences, 2012, 46: 296-309.

[9]XIE Cong-hua, SONG Yu-qing, LIU Zhe. Density-Based Clustering Algorithm Using Kernel Density Estimation and Hill-down Strategy [J]. Journal of Information & Computational Science, 2010, 7(1): 135-142.

[10]劉哲, 宋余慶, 陳健美, 等. 基于二類切比雪夫正交多項(xiàng)式非參數(shù)混合模型的圖像分割 [J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 11(48): 2008-2014.

LIU Zhe, SONG Yu-qing, CHEN Jian-mei, et al. Image Segmentation Based on Non-Parametric Mixture Models of Chebyshev Orthogonal Polynomials of the Second Kind [J]. Journal of Computer Research and Development, 2011, 11(48): 2008-2014.

[11]MELNYKOV V, MELNYKOV I. Initializing the EM Algorithm in Gaussian Mixture Models with an Unknown Number of Components [J]. Computational Statistics & Data Analysis, 2012, 56(6): 1381-1395.

[12]顏慶津. 數(shù)值分析 [M]. 北京： 北京航空航天大學(xué)出版社, 1992.

YAN Qing-jin. Numerical Analysis [M]. Beijing: Beihang University Press, 1992.

[13]FOWLKES C, MARTIN D, MALIK J. The Berkeley Segmentation Dataset and Benchmark(BSDB). [2013-02-10]. [DB/OL]. http://www.cs.berkeley.edu/projects/vision/grouping/segbench.

[14]WANG Li-jun, DONG Ming. Multi-Level Low-Rank Approximation-Based Spectral Clustering for Image Segmentation [J]. Pattern Recognition Letters, 2012, 33(16): 2206-2215.

[15]STEINBACH M, KARYPIS G, KUMAR V. A Comparison of Document Clustering Techniques [C]∥Proc of the KDD Workshop on Text Mining. Boston, USA: [s.n.], 2000: 109-111.