劉 哲, 譚振江, 王洪君

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

0 引 言

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

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

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

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

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

(1)

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

算法1

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

2) 期望步。計算在第n次迭代時每個樣本i屬于第j類的后驗概率

(2)

3) 最大化步。通過求解對數(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)點, 是B樣條基曲線的線性組合, 也是目前廣泛應用的一種擬合方法。

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

(6)

(7)

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

(8)

(9)

2.2 聚類算法

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

算法2 (NNBEM算法)

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

輸出： 聚類結(jié)果

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

(10)

(11)

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

Step2 Expectation: 在m次迭代時, 像素xi屬于第k類的后驗概率

(12)

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

(13)

(14)

(15)

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

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

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

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

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

(16)

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

(17)

(18)

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

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

(19)

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

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

3.1 模擬圖像

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

3.2 真實圖像聚類

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

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

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

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

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

4 結(jié) 語

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

參考文獻：

[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]. 吉林大學學報: 理學版, 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]劉哲, 宋余慶, 陳健美, 等. 基于二類切比雪夫正交多項式非參數(shù)混合模型的圖像分割 [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]. 北京： 北京航空航天大學出版社, 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.