周曉明 李釗 劉雄英

(1.華南理工大學(xué)理學(xué)院，廣東廣州510640;2.華南理工大學(xué)亞熱帶建筑科學(xué)國家重點實驗室，廣東廣州510640)

模糊C均值聚類(FCM)是由Dunn［1］率先提出的，Bezdek［2-3］對該理論進(jìn)行了完善，他不僅證明了該算法的收斂性，而且給出了該算法基于最小二乘迭代的優(yōu)化算法.

FCM算法因迭代簡單，且其模糊性符合人眼的視覺習(xí)慣，因而在圖像分割領(lǐng)域得到了廣泛的應(yīng)用［4］.傳統(tǒng)的FCM分割方法是將像素的灰度值作為聚類特征進(jìn)行聚類以得到各個像素的類屬，屬于同一類屬的像素歸為同一個區(qū)域以完成圖像分割，但是直接運用FCM算法進(jìn)行圖像分割需要人為確定聚類數(shù)，而人為確定聚類數(shù)往往存在許多不足:①主觀性較強，不同人對同一幅圖像往往得到不同的聚類數(shù)目;②由于人眼受圖像相鄰區(qū)域?qū)Ρ榷鹊挠绊?，往往只能確定圖像的區(qū)域數(shù)，而區(qū)域數(shù)不等于聚類數(shù)，因為不同的區(qū)域若其灰度值相近則在聚類過程中應(yīng)該屬于同一類;③降低了FCM算法的自動化程度.基于以上原因解決聚類數(shù)需人為確定的問題具有十分重要的意義.

如何確定數(shù)據(jù)集的聚類數(shù)是所有聚類算法面臨的一個關(guān)鍵問題，也是聚類有效性的一個重要的研究方向.傳統(tǒng)的解決方法是先定義一個聚類有效性指標(biāo)V，該指標(biāo)是關(guān)于聚類數(shù)c的函數(shù).然后對不同的c值計算其相應(yīng)的V值.對于某一數(shù)據(jù)集，若V是關(guān)于c的單調(diào)函數(shù)，則函數(shù)曲線的拐點處對應(yīng)的c值被認(rèn)為是最佳聚類數(shù)，若V不是關(guān)于c的單調(diào)函數(shù)，則函數(shù)在最值處對應(yīng)的c值被認(rèn)為是最佳聚類數(shù).近十幾年來，有多種聚類有效性指標(biāo)被學(xué)者相繼提出［5-18］.這里先作簡單的介紹.

Xie等［6］定義第j類的類內(nèi)緊湊度為Comp(j)，再用相距最近的兩個聚類中心的距離度量類間的分散度Sep(c)，則有效性指標(biāo)被定義為Comp(j)之和與Sep(c)的商.Campello等［11］提出了另一種指標(biāo)VF_sil.設(shè)d(i，j)是樣本i到類j的距離.首先將各個對象依據(jù)最大隸屬度原則進(jìn)行聚類，然后對每一個樣本i，設(shè)其屬于第j類，則可計算出si，si=1-然后對每個s加權(quán)i求和得到VF_sil.

Bouguessa等［10］用類內(nèi)模糊協(xié)方差矩陣的跡度量聚類緊湊度，用類間模糊協(xié)方差矩陣的跡度量類間的分離度.令類內(nèi)模糊協(xié)方差矩陣為Fj，類間模糊協(xié)方差矩陣為SB，則有效性指標(biāo)VSCG為SB的跡與Fj的跡之和的商.

這類確定聚類數(shù)的方法雖然直觀清晰，但存在一些明顯的不足:首先每種有效性指標(biāo)往往只適合特定分布的數(shù)據(jù)集，對同一數(shù)據(jù)集，不同的有效性指標(biāo)往往得到不同的最佳聚類數(shù)，因此Pal等［13］指出，運用一個有效性指標(biāo)確定數(shù)據(jù)集的聚類數(shù)往往是不可信的;其次采用這種試探性的方法將大大增加算法的計算量，從而限制了其在實際中的應(yīng)用.

文中提出的算法避免了采用聚類有效性指標(biāo)來自動確定聚類數(shù)目，而是根據(jù)圖像這類數(shù)據(jù)集的特點對其進(jìn)行4叉樹結(jié)構(gòu)的子圖分解，直到子圖滿足一定條件時進(jìn)行聚類數(shù)為2的FCM聚類分割，最后依據(jù)一定條件進(jìn)行區(qū)域合并從而避免了聚類數(shù)的直接確定.此外，由于FCM的迭代運算是一種高次運算，對子圖進(jìn)行聚類相當(dāng)于將一個數(shù)據(jù)集分成若干部分單獨聚類，降低了每次參與聚類的對象數(shù)目，因而相對于對整張圖像進(jìn)行聚類降低了計算量.

1 FCM背景理論

FCM算法通過最小化目標(biāo)函數(shù)來實現(xiàn)樣本的最優(yōu)劃分.假設(shè)將n個樣本聚成c類，則目標(biāo)函數(shù)為且滿足約束條件i=1，2…，n，μij＞0.其中，xi為樣本i的特征向量，vj是第j類的聚類中心，μij為樣本i關(guān)于j類的隸屬度，m為權(quán)重函數(shù)，文獻(xiàn)［13］從聚類有效性的實驗中得到m的取值為1.5～2.5，本研究取m=2. FCM算法通過更新vj和μij來優(yōu)化目標(biāo)函數(shù).根據(jù)拉格朗日條件極值理論可得到更新公式:

當(dāng)相鄰的兩輪迭代得到的目標(biāo)函數(shù)值滿足: |Jt-Jt+1|＜ε，則可以認(rèn)為已經(jīng)得到較好的聚類結(jié)果從而停止更新，其中ε是一個很小的正數(shù)，稱為容許誤差.最后根據(jù)隸屬度最大原則將樣本劃分到其隸屬度最大值對應(yīng)的類中.

2 基于子圖分解與區(qū)域合并的FCM自動分割算法

2.1 圖像直方圖的信息熵與聚類峰值數(shù)

圖像直方圖是圖像的一種十分重要的統(tǒng)計信息，它很好地反映了圖像的灰度分布情況，其波峰和波谷是直方圖非常有用的信息，文中定義兩個參數(shù)來描述圖像的直方圖.

(1)直方圖的信息熵

圖1 信息熵的比較Fig.1 Contrast of the information entropy

(2)直方圖的波峰數(shù)估計

直方圖的不規(guī)則性會產(chǎn)生大量假的波峰和波谷，因而其波峰數(shù)難以統(tǒng)計，為解決這一問題，對圖像歸一化處理后的直方圖進(jìn)行FCM聚類處理.以聚類后的直方圖的波峰數(shù)估計原直方圖的波峰數(shù)，具體步驟如下:

①計算圖像的64級灰度直方圖，得到數(shù)組h，h包含64個元素，每個元素的取值為圖像取該級灰度的像素數(shù).

③對t的64個元素進(jìn)行聚類數(shù)為2的FCM聚類，初始聚類中心為{0}和{1}，容許誤差取0.001.

④按隸屬度最大原則對元素進(jìn)行歸類，得到聚類直方圖s.計算s的波峰數(shù)peak_n作為h波峰數(shù)的估計值.

聚類后的直方圖沒有了原始直方圖的許多細(xì)小波動，而這些細(xì)小波動往往會被誤認(rèn)為波峰或波谷.圖2所示為原始直方圖與聚類后的直方圖，聚類后的直方圖顯示峰值數(shù)為2.

圖2 原始直方圖與聚類后的直方圖Fig.2 Original histogram and the histogram after clustering

2.2 區(qū)域間的巴氏距離

巴氏距離是衡量直方圖相似性的常用標(biāo)準(zhǔn)，巴氏距離越大，則兩個直方圖越相似.文中通過計算圖像兩個相鄰區(qū)域直方圖的巴氏距離來衡量這兩個區(qū)域的相似度.

2.3 整體算法流程

1)基于子圖分解的FCM圖像分割

進(jìn)行圖像分割時先將圖像劃分為子圖直到子圖滿足以下兩點中的一點:

(1)子圖直方圖的inf小于原圖直方圖的inf且子圖直方圖的peak_n小于等于2;

(2)子圖大小小于一定閾值α，α可以根據(jù)圖像中最小區(qū)域的面積進(jìn)行調(diào)整，文中統(tǒng)一取1024.

此時對子圖的像素做聚類數(shù)目為2的FCM聚類.聚類后根據(jù)最大隸屬度原則對像素進(jìn)行分類.進(jìn)行聚類分割時初始聚類中心均設(shè)為{0，255}，容許誤差取0.001.

2)基于區(qū)域面積與巴氏距離的區(qū)域合并

林木資源資產(chǎn)個體的生長發(fā)育及投入產(chǎn)出情況具有階段性，不同類型林木資產(chǎn)每個階段具有不同的生長發(fā)育特性，只有充分掌握各自特點才能便于后期經(jīng)濟(jì)價值的核算以及體系的建立。

基于原始圖像子圖的分割將會使得分割得到的區(qū)域數(shù)大于實際的區(qū)域數(shù)，因此進(jìn)行適當(dāng)?shù)膮^(qū)域合并是必要的.文中的區(qū)域合并基于以下兩條準(zhǔn)則:

(1)若兩個相鄰區(qū)域的巴氏距離ρ(r，q)大于閾值β，則將他們合并.文中β統(tǒng)一取0.22.

(2)若區(qū)域的面積小于閾值γ，則將其合并到灰度值均值與其最接近的相鄰區(qū)域中.γ也是與圖像的最小區(qū)域的面積有關(guān)，文中統(tǒng)一取50.

為了更清晰地敘述本文算法流程，這里將算法的流程用流程框圖表示出來，如圖3所示.

3 實驗結(jié)果分析

以rice圖為例展示文中算法的具體過程及中間結(jié)果.圖4(a)為待分割的rice圖，圖4(b)是基于子圖分解的FCM聚類分割后的結(jié)果，圖4(c)是基于相鄰區(qū)域巴氏距離進(jìn)行區(qū)域合并后的結(jié)果，圖4(d)是合并掉小區(qū)域后的結(jié)果.

文中提出的算法將與傳統(tǒng)人為確定聚類數(shù)的方法和兩種較經(jīng)典的自動確定聚類數(shù)的指標(biāo)(F_stl有效性準(zhǔn)則［11］和SCG有效性準(zhǔn)則［10］)相比較，采用有效性準(zhǔn)則時將分別計算聚類數(shù)為2～10的情況下這兩個準(zhǔn)則的取值，取最大值對應(yīng)的聚類數(shù)作為最佳聚類數(shù).聚類時容許誤差統(tǒng)一取0.001.

圖3 提出的算法流程圖Fig.3 Proposed algorithm flowchart

表1示出了F_stl有效性準(zhǔn)則和SCG有效性準(zhǔn)則對于3幅圖像在不同聚類數(shù)下的取值.表2示出了人工方法及這兩個準(zhǔn)則對于這3幅圖像得到的聚類數(shù).從結(jié)果可以看出，F(xiàn)_stl準(zhǔn)則和人工方法在確定最佳聚類數(shù)時具有較一致的結(jié)果，SCG準(zhǔn)則容易受光照不均勻等因素的影響，所產(chǎn)生的最佳聚類數(shù)與前兩種方法有較大差距.

圖4 rice圖的分割過程Fig.4 Segmentation process of rice image

表1 實驗圖像的有效性指標(biāo)Table 1 Validity index of experiment images

表2 圖像的最優(yōu)聚類數(shù)Table 2 Optimal clustering number of images

圖5 rice圖實驗結(jié)果Fig.5 Experiment results of rice image

圖6 lena圖實驗結(jié)果Fig.6 Experiment results of lena image

圖5(a)在聚類數(shù)為2的情況下可以得到較好的分割效果，但由于光照不均勻的影響在圖片下方的米粒出現(xiàn)了不同程度的缺損.相比之下文中算法可以很好地將所有米粒完整分割出來，且整個過程無需人工干預(yù).

圖6(a)在聚類數(shù)為2的情況下得到的分割效果要優(yōu)于聚類數(shù)為5的情況，但由于部分區(qū)域內(nèi)的灰度值波動較大，因而在人物臉部出現(xiàn)一些錯誤分割.而文中算法可以將臉和肩的輪廓分割出來.

圖7(a)在聚類數(shù)為2的情況下可以得到不錯的聚類效果，但在左邊十字架等區(qū)域出現(xiàn)了區(qū)域不完整的現(xiàn)象.相較而言，文中算法分割出來的區(qū)域比較連續(xù)完整.

圖7 house圖實驗結(jié)果Fig.7 Experiment results of house image

此外文中算法由于不需直接確定聚類數(shù)，因此避免了對最佳聚類數(shù)的搜索，而且由于FCM的迭代運算是一種高次運算，對子圖進(jìn)行聚類相當(dāng)于將一個數(shù)據(jù)集分成若干部分單獨聚類，降低了每次參與聚類的對象數(shù)目，在聚類對象總數(shù)一定的情況下這種分治的方法有助于降低運算量.

表3示出了不同算法分割這3幅圖片的耗時，仿真實驗運行的硬件環(huán)境為AMD Athlon(tm)64 X2 Dual Core Processor 4400++，CPU主頻為2.30GHz，內(nèi)存為2.00GB.編程環(huán)境為Matlab7.0.從表3的運行時間對比可以看出，采用基于聚類有效性指標(biāo)的方法進(jìn)行聚類數(shù)的自動確定是十分耗時的.而文中提出的算法在實現(xiàn)自動分割的基礎(chǔ)上避免了聚類數(shù)目的直接確定，同時基于子圖的FCM分割減少了每次聚類的對象集規(guī)模，因而大幅降低了運算量.

表3 4種方法的運行時間對比Table 3 Contrast of operating time of four methods s

為了對分割結(jié)果進(jìn)行一定的定量分析，文中對rice圖進(jìn)行了人工分割并將以上算法的分割結(jié)果與之對比，定義了3個指標(biāo)來描述分割算法的準(zhǔn)確度.設(shè)算法分割圖中劃分為米粒且實際屬于米粒的像素數(shù)為n1，算法分割圖中劃分為米粒的總像素數(shù)為m1，算法分割圖中劃分為背景且實際屬于背景的像素數(shù)為n2，算法分割圖中劃分為背景的總的像素數(shù)則有以下定義:對象分割正確率;背景正確分割率;總體分割正確率

表4示出了文中算法和各項對比算法的指標(biāo)計算結(jié)果.從表中可以看出文中算法的分割結(jié)果和人工的分割結(jié)果十分接近，人工確定聚類數(shù)下的分割可以得到較高的對象分割正確率，但由于光照不均勻的影響使得圖片下方的米粒出現(xiàn)殘缺從而降低了背景分割正確率.而SCG準(zhǔn)則下的分割結(jié)果正確率最低.

表4 4種方法的正確率對比Table 4 Contrast of correct rates of four methods %

4 結(jié)語

針對FCM用于圖像分割時聚類數(shù)難以自動確定這一問題，傳統(tǒng)的基于聚類有效性分析的自動聚類數(shù)確定方法存在著準(zhǔn)確度低與運算量大等缺點.文中提出一種新的算法用于解決該問題.該算法對先對圖像進(jìn)行4叉樹結(jié)構(gòu)的子圖分解，然后通過分析子圖直方圖的信息并結(jié)合子圖的大小決定繼續(xù)分解還是進(jìn)行聚類數(shù)固定的FCM分割，最后分析相鄰區(qū)域的相似度并結(jié)合區(qū)域的面積進(jìn)行區(qū)域合并.在3幅實際圖像上的實驗表明，該算法可以避免聚類數(shù)的直接確定，具有較好的分割效果且大幅降低了運算量.

［1］ Dunn J C.A fuzzy relative of the ISO DATA process and its use in detecting compact well-separated clusters［J］. Journal of Cybernetics，1974，3(3):32-57.

［2］ Bezdek J C.Pattern recognition with fuzzy objective function algorithms［M］.New York:Plenum Press，1981:20-35.

［3］ Bezdek J C.A convergence theorem for the fuzzy iso data clustering algorithms［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1980，PAMI-2(1):1-8.

［4］ Kettaf F Z，BI D，Asselin de Beauville J P.A comparison study of image segmentation by clustering techniques［C］∥Proceedings of 3rd International Conference on Signal Processing.Beijing:Chinese Institute of Electronics，1996: 1280-1290.

［5］ Chen M Y，Linkens D A.Rule-base self-generation and simplification for data-driven fuzzy models［J］.Fuzzy Sets and Systems，2004，142(2):243-265.

［6］ Xie X L，Beni G.A validity measure for fuzzy clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13(8):841-847.

［7］ Xie Y，Raghavan V V，Dhatric P，et al.A new fuzzy clustering algorithm for optimally finding granular prototypes［J］.Approximate Reasoning，2005，40(1):109-124.

［8］ Gath I，Geva A B.Unsupervised optimal fuzzy clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1989，11(7):773-781.

［9］ Tsekouras G E，Sarimveis H.A new approach for measuring the validity of the fuzzy c-means algorithm［J］.Advances in Engineering Software，2004，35(8/9):597-875.

［10］ Bouguessa M，Wang S R.A new efficient validity index for fuzzy clustering［C］∥Proceedings of the Third International Conference on Machine Learning and Cybernetics.Shanghai:The Hong Kong Polytechnic University，2004:26-29.

［11］ Campello R J G B，Hruschka E R.A fuzzy extension of the silhouette width criterion for cluster analysis［J］. Fuzzy Sets and Systems，2006，157(21):2858-2875.

［12］ Cho S B，Yoo S H.Fuzzy Bayesian validation for cluster analysis of yeast cell-cycle data［J］.Pattern Recognition，2006，39(12):2405-2414.

［13］ Pal N R，Bezdek J C.On cluster validity for fuzzy cmeans model［J］.IEEE Transactions on Fuzzy Systems，1995，3(3):370-379.

［14］ 賁圣蘭，蘇光大.基于錯誤度量的模糊聚類有效性函數(shù)［J］.模式識別與人工智能，2010，23(1):11-16. Ben Sheng-lan，Su Guang-da.A fuzzy cluster validity index based on clustering mistake measures［J］.Pattern Recognition and Artificial Intelligence，2010，23(1): 11-16.

［15］ 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究［J］.計算機科學(xué)，2011，38(2):225-228. Zhou Shi-bing，Xu Zhen-yuan，Tang Xu-qing.Comparative study on method for determining optimal number of clusters based on affinity propagation clustering［J］. Computer Science，2011，38(2):225-228.

［16］ 張愛華.基于模糊聚類分析的圖像分割技術(shù)研究［D］.武漢:華中科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，2004.

［17］ 周世兵，徐振源，唐旭清.一種基于近鄰傳播算法的最佳聚類數(shù)確定方法［J］.控制與決策，2011，26 (8):1147-1152. Zhou Shi-bing，Xu Zhen-yuan，Tang Xu-qing.Method for determining optimal number of clusters based on affinity propagation clustering［J］.Control and Decision，2011，26(8):1147-1152.

［18］ 楊銳.基于模糊聚類及水平集方法的圖像分割技術(shù)研究［D］.長春:吉林大學(xué)電子科學(xué)與工程學(xué)院，2011.