一種改進的快速FCM圖像分割算法

徐路，蔣振剛

（長春理工大學 計算機科學技術(shù)學院，長春 130022）

由Bezdek J C等人提出的模糊C均值（Fuzzy C-means，簡稱FCM）算法［1］是通過優(yōu)化目標函數(shù)對數(shù)據(jù)樣本進行模糊聚類的方法，是一種可以應(yīng)用于圖像分割的較為重要的聚類方法［2-3］，為實現(xiàn)圖像測量、配準［4-5］、融合以及三維重建的提供基礎(chǔ)支撐。FCM算法對圖像的模糊特征具有較強的魯棒性，而且相對于硬聚類分割算法而言能保留更多的圖像原始信息，具有更好、更穩(wěn)定的聚類性能［6］，同時FCM算法是一種非監(jiān)督模糊聚類方法，被廣泛的應(yīng)用于醫(yī)學圖像處理、圖像分析等諸多范疇。

FCM算法應(yīng)用于圖像分割時可以減少人為的干預(yù)，且較適合灰度圖像中存在較大不確定性的特點。雖然FCM算法用于圖像分割有其特有優(yōu)勢，但也存在著明顯不足［7］：算法聚類中心是隨機初始化得到的，導致算法的迭代次數(shù)較多，沒有考慮鄰域點與中心點的相關(guān)性及目標函數(shù)對隸屬度的約束［8-10］，導致算法的分割結(jié)果不夠精確。

對隨機初始化聚類中心的問題，很多學者進行了廣泛深入的研究，并取得了一定的成果。文獻［11］提出了一種結(jié)合灰度直方圖的快速FCM算法，通過結(jié)合圖像直方圖的統(tǒng)計特性，基于直方圖的峰值點來判別劃分區(qū)間，從而初始化聚類中心，但未考慮峰值點小于聚類數(shù)目時的區(qū)間劃分情況。王改華等人［12］提出一種改進算法，采取分塊思想，利用均值特征對初始聚類的中心像素和中心數(shù)進行計算，然后根據(jù)塊方差的比較結(jié)果計算不同的隸屬度函數(shù)。但文章手動設(shè)定閾值較多，且先分塊求均值，用歐式距離判別聚類中心，后分別計算均勻塊與非均勻塊的隸屬度函數(shù)，在一定程度上提升了算法的計算復雜度。文獻［13］提出了一種初始聚類中心的選取規(guī)則，即每個聚類中心之間的距離應(yīng)該保持設(shè)定的最小閾值，通過不斷的調(diào)整閾值的大小，使選取聚類中心可在多個可行域上進行，從而避免局部收斂的缺點。但如何選取到合適的閾值還需進一步的研究。張翡等人［14］通過將圖像從像素空間映射到其灰度直方圖空間，然后平均劃分區(qū)間，同時考慮密度與距離的乘積來確定初始聚類中心，但其區(qū)間劃分方法對灰度值較為集中的圖像效果不理想。文獻［15］提出了在精簡數(shù)據(jù)集，壓縮迭代數(shù)據(jù)量的基礎(chǔ)上，運用灰度值對應(yīng)頻數(shù)與距離的聯(lián)系初始化聚類中心的算法，由于依舊采用平分區(qū)間的思想，在區(qū)間劃分上仍存在準確性問題。Zhou D等人［16］提出一種新算法，首先分段輸出前景區(qū)域和后景區(qū)域，然后在分段結(jié)果基礎(chǔ)上引用核函數(shù)求得聚類中心，利用具有偏置場的模糊聚類算法劃分空間鄰近像素，然而該算法消耗了過多的時間將像素仔細劃分到其更相似的簇中，并且一些參數(shù)設(shè)置的影響，在研究中沒有詳細揭示，如γ。

考慮到上述問題，本文重點從準確劃分區(qū)間求取聚類中心點，同時兼顧算法計算復雜度的關(guān)鍵點出發(fā)，針對FCM算法隨機初始化聚類中心的問題進行改進，提出一種基于確定初始聚類中心的快速FCM圖像分割算法。該算法通過最大類間方差法［17］劃分圖像灰度區(qū)間初始化聚類中心，從而減少算法的迭代次數(shù)。該算法不僅可以應(yīng)用于FCM算法中，同時可應(yīng)用于多種采用隨機初始化聚類中心的FCM類算法（如FCM_S、FCM_S1及FCM_S2等算法）中，提升算法計算速度。

1 FCM分割算法

FCM算法是一種應(yīng)用于圖像分割的重要聚類方法，其基本思想是通過迭代尋找到最優(yōu)的聚類中心vi以及隸屬度uik，以使目標函數(shù)Jm（U，C）取得最小值，從而實現(xiàn)圖像的優(yōu)化分割。

并且滿足下列約束條件：

數(shù)據(jù)集X=(x1,x2,x3,…,xN)∈Rs為圖像灰度值的集合，s是樣本xk（k=1，2，3，…，N）的維數(shù)，c代表聚類的類別數(shù)，N代表待聚類樣本數(shù)據(jù)集中包含的數(shù)據(jù)點的個數(shù)，uik表示X中第k個樣本數(shù)據(jù)點歸屬于第i類的隸屬度，vi（i=1，2，3，…，c）為每個聚類的聚類中心，2≤c≤N，m∈［1，+∞）為聚類加權(quán)指數(shù)，控制著數(shù)據(jù)劃分過程的模糊程度，若m=1，模糊C均值聚類便退化成硬C均值聚類，很多研究表明，m=2的取值較為理想，d2ik（xk，vi）為第k個樣本數(shù)據(jù)點到第i類聚類中心vi的歐式距離，U={uik}代表一個n*c維的矩陣。

在約束條件下，根據(jù)拉格朗日乘子法可以得到使得目標函數(shù)式（1）取極小值的必要條件：

隸屬度函數(shù)和聚類中心由式（3）、式（4）不斷迭代更新，直到目標函數(shù)J取得最小值時，F(xiàn)CM算法收斂，并取得最終的聚類中心vi。

FCM算法收斂也可以通過檢測聚類中心vi和模糊隸屬度uik的變化來完成。當連續(xù)兩次求出的聚類中心vi或模糊隸屬度uik的差值小于一定的閾值時，則認為算法收斂，并取得最終的聚類中心。

最后使用最大隸屬度函數(shù)法來對分類結(jié)果進行去模糊操作，完成圖像分割。用Ck表示第k個待分類樣本點xk隸屬于第i類的程度，有

2 確定初始聚類中心的快速FCM算法

本文采用最大類間方差法在圖片整個灰度范圍內(nèi)找到最優(yōu)的閾值點，然后用該點把灰度區(qū)間分成兩個子區(qū)間。再依次通過最大類間方差法繼續(xù)劃分子區(qū)間，根據(jù)限定條件選取劃分閾值，直到達到設(shè)定的劃分閾值個數(shù)，進行FCM算法分割。

2.1 確定聚類中心步驟：

（1）計算待分割圖像的直方圖，保存每一個像素的灰度值出現(xiàn)的概率。確定聚類數(shù)目C。

（2）采取最大類間方差法取得閾值t1，將區(qū)間劃分為［0，...，t1］和［t1+1，...，L-1］（若只將圖像分為兩類取t1做劃分閾值T1，劃分區(qū)間。）。

（3）在區(qū)間［0，...，t1］和［t1+1，...，L-1］上，根據(jù)最大類間方差法的原則，分別取得閾值t2，t3，比較t1，t2，t3附近的方差值（數(shù)據(jù)歸一化后求得的方差值）Di（i=1，2，3），取較大的Di值所對應(yīng)的ti值作為劃分閾值T1，T2。

（4）設(shè)上述取得t1，t2做劃分閾值T1，T2，則依次在［0，...，T2］，［T2+1，...，T1］中分別用最大類間方差法得到閾值t4和t5，及其附近的方差值Di（i=4，5），并與在步驟（1）中余下的區(qū)間內(nèi)求得的閾值t3對應(yīng)的D3比較，選擇最大Di（i=3，4，5）值對應(yīng)的閾值作為劃分閾值T3。

（5）對T3新劃分得到的兩個子區(qū)間按如上所述求閾值t及其附近區(qū)域的方差值D，并與前面剩下的區(qū)間算得的閾值對應(yīng)的D值進行如上比較，依次取得劃分閾值T，直到達到設(shè)定的數(shù)目為止。

為了準確的劃分區(qū)間，在如下情況時，優(yōu)先操作下述方法：

情況1：若比較用最大類間方差法求得的閾值對應(yīng)的方差值時，方差差值 ΔDi（i=1，2，3）小于ξ（ξ值可根據(jù)圖像類型自定）時，取使得新劃分子區(qū)間距離值同時取得最大（和最大，差最小，和最大優(yōu)先，和相同時取差最?。┑拈撝祎做劃分閾值T。

情況2：與已確定的相鄰的邊界過近（不存在波峰點），判定此閾值無效，不取此閾值，在下次比較時，計算其劃分的有波峰點的子區(qū)間內(nèi)的閾值，若此閾值有效，以其做比較，否則舍棄，若比較閾值均為無效閾值，則按情況1方法處理。

（6）因為靠近聚類中心的像素點對本類別的隸屬度應(yīng)大于遠離聚類中心的像素點對本類別的隸屬度，所以設(shè)定區(qū)間段中像素點，對第k個類別的隸屬度uik賦值為1，對其他類別的隸屬度賦值為0。因此，得到聚類中心的初始化公式：

設(shè)tl為區(qū)間起點，th為區(qū)間終點，h(i)為像素i所出現(xiàn)的概率，L值為256。

2.2 圖像分割步驟

（1）設(shè)置聚類個數(shù)C，權(quán)重指數(shù)m，終止閾值ε，最大迭代次數(shù)Lmax，按2.1中確定聚類中心的方法算出聚類中心vi。

（2）按照公式（3）計算模糊隸屬度uik。

（3）重復公式（3）到（4），直到＜ε或者達到最大迭代次數(shù)Lmax。（b為算法迭代次數(shù)。）

（4）根據(jù)隸屬度最大原則，依照公式（5）做去模糊化處理，完成圖像分割。

3 實驗結(jié)果

為了驗證本文所提出算法的有效性，分別采用FCM算法及本文算法在MATLAB R2016a編程環(huán)境下對20幅模擬腦圖像，20幅腦MR圖像，10幅心臟CT圖像，10幅細胞圖像，10幅人臉圖像，10幅自然圖像進行圖像分割及結(jié)果比較（圖像均由512×628個像素組成）。實驗平臺為Windows 7，Intel（R） Xeon（R） CPU E3-1200V23.10GHz，RAM 10GB，實驗設(shè)置參數(shù)m=2，目標函數(shù)收斂的閾值ε=0.00001，迭代最大次數(shù)Lmax為200，F(xiàn)CM算法的迭代次數(shù)及CPU時耗取5次均值，方差差值ξ=0.0001，判斷t值附近方差D時取t值附近50像素的區(qū)間范圍。

表1 FCM算法與本文提出的算法對多組圖像進行分割的數(shù)據(jù)統(tǒng)計

實驗結(jié)果表明（表1）：使用本文提出的算法對上述多組圖像進行圖像分割，所需的迭代次數(shù)與對應(yīng)的CPU時耗較之隨機初始化聚類中心的FCM算法在多數(shù)案例中均有所降低，其中，實驗最優(yōu)情況為降低算法迭代次數(shù)61.20%，最劣情況為增加算法迭代次數(shù)13.13%。

由表1中數(shù)據(jù)可以看出本文提出的算法較之FCM算法對模擬腦圖像與腦MR圖像的平均改進效率更為明顯，對自然圖像的平均改進效率較為低下。因為腦圖像相似灰度值分布區(qū)域較為集中，計算聚類中心時，更為精確。而由于自然圖像的多樣性，部分自然圖像較之其他圖像灰度分布具有不確定性，使得其直方圖灰度值抖動較大，計算聚類中心點時精確性有所欠缺。

圖 1（a）為一幅模擬腦圖像，（b）為其對應(yīng)的FCM算法及本文提出的算法的分割結(jié)果（因為本文提出的算法只針對確定算法的聚類中心做出改進，所以分割結(jié)果與FCM算法分割結(jié)果相同），（c）為其對應(yīng)的直方圖。聚類數(shù)目設(shè)置為C=4（將圖像分為腦白質(zhì)、灰質(zhì)、腦髓液和背景）。

圖1 模擬腦圖像的原始圖像、分割結(jié)果及直方圖

按照2.1小節(jié)的算法步驟可以得出圖1（c）中的劃分閾值分別為49，105，183，在劃分的區(qū)間中應(yīng)用公式（6）求出聚類中心vi（i=1，…，4）值分別為19.3075，80.5983，134.6177，234.2696，與最終系統(tǒng)算得的聚類中心值 17.5988，80.0802，135.2761，238.8832較為接近，從而較之隨機初始化聚類中心的FCM算法的減少了算法的迭代次數(shù)，加快了算法的收斂速度。

圖2（a）為一幅自然圖像，（b）為其對應(yīng)的FCM算法及本文提出的算法的分割結(jié)果，（c）為其對應(yīng)的直方圖。聚類數(shù)目設(shè)置為C=4（將圖像分為前景、中景、遠景和天空）。

圖2 自然圖像的原始圖像、分割結(jié)果及直方圖

按照2.1小節(jié)算法步驟（1）至（3）可以得出圖2（c）中的劃分閾值分別為T1=58，T2=202，在步驟（4）中比較閾值31，123，236附近的灰度值方差時，由于閾值236附近灰度值抖動較大，以致在選取劃分閾值時，選取了不理想的劃分閾值T3=236，在劃分的區(qū)間中應(yīng)用公式（6）求出聚類中心vi（i=1，…，4）值 分 別 為 30.1598，115.2752，224.4136，250.6030，最終系統(tǒng)算得的聚類中心值25.9405，62.4323，160.3823，239.0716，相差較大，故算法的收斂速度較之隨機初始化聚類中心的FCM算法并無優(yōu)勢，甚至增加算法迭代次數(shù)。

表2為采用FCM算法與本文提出的算法對圖1（a）、圖2（a）進行圖像分割的迭代次數(shù)與運行時間的數(shù)據(jù)統(tǒng)計，從表中可看出，對于圖1（a），本文所提出的算法所需的迭代次數(shù)少于隨機初始化聚類中心的FCM算法的迭代次數(shù)，CPU時耗也較之FCM算法有所減少。而對于圖2（a），本文提出的算法迭代次數(shù)及CPU時耗均多于隨機初始化聚類中心的FCM算法。

表2 FCM算法與本文提出的算法對圖1、圖2分割的迭代次數(shù)與運行時間

4 結(jié)論

本文提出一種結(jié)合最大類間方差法的快速FCM圖像分割算法。算法充分利用圖像統(tǒng)計直方圖信息初始化聚類中心，以減少FCM算法的迭代次數(shù)，提高圖像分割效率。實驗表明本文提出的算法對于相似灰度值分布區(qū)域較為集中的圖像（如醫(yī)學圖像）效果較為明顯，可以快速得到系統(tǒng)最終確定的聚類中心，進而加快算法的收斂速度，而算法對直方圖灰度值抖動較大的圖像效果不夠理想。該算法可應(yīng)用于采取隨機初始化聚類中心的FCM相關(guān)的算法中，通過確定初始聚類中心，可以有效提高FCM類算法的運算效率。

參考文獻

［1］ Bezdek J C，Ehrlich R，F(xiàn)ull W.FCM：The fuzzy c-means clustering algorithm［J］.Computers&Geosciences，1984，10（2）：191-203.

［2］ ZhangD，WangY.Medicalimagesegmentation based on FCM clustering and rough set［J］.Chinese JournalofScientific Instrument，2006，27（12）：1683-1687.

［3］ Chen W，Giger M L，Bick U.A fuzzy c-means（FCM）-based approach for computerized segmentation of breast lesions in dynamic contrast-enhanced MR images［J］.Academic Radiology，2006，13（1）：63-72.

［4］ 何巍，魏國棟，師為禮，等.基于點云的膝關(guān)節(jié)脛骨三維CT與MRI圖像配準［J］.長春理工大學學報：自然科學版，2015，38（5）：131-135.

［5］ 陳克寒，楊華民.利用光線投射法虛擬X光線圖片進行基于灰度的2D/3D配準算法研究［J］.長春理工大學學報：自然科學版，2016，39（2）：103-106.

［6］ YangJ.Fuzzyc-means'performancecomparison with hard clustering and improvement［J］.Computer Knowledge&Technology，2008，4（S2）：192-194.

［7］ 張軍賢.基于改進模糊聚類算法的醫(yī)學圖像分割研究［D］.武漢：華中科技大學，2012.

［8］ Feng Y，Dong F，Xia X，et al.An adaptive fuzzy C-meansmethod utilizing neighboring information for breast tumor segmentation in ultrasound images［J］.Medical Physics，2017，44（7）：3752-3760.

［9］ Venu N，AnuradhaB.Multil-Kernelsintegration for FCM Algorithm for medical image segmentation using histogram analasis［J］.Indian Journal of Science&Technology，2015，8（34）：1-8.

［10］ Guo F，Wang X，Shen J.Adaptive fuzzy c-means algorithm based on local noise detecting for image segmentation［J］.Iet Image Processing，2016，10（4）：272-279.

［11］ 張小峰.基于模糊聚類算法的醫(yī)學圖像分割技術(shù)研究［D］.濟南：山東大學，2014.

［12］ 王改華，李德華.A fast and effective fuzzy clustering algorithm for color image segmentation［J］.北京理工大學學報：英文版，2012，21（4）：518-525.

［13］ 張慧哲，王堅.基于初始聚類中心選取的改進FCM聚類算法［J］.計算機科學，2009，36（6）：206-209.

［14］ 張翡，范虹，郝艷榮.結(jié)合非局部均值的快速FCM算法分割MR圖像研究［J］.計算機科學，2014，41（5）：304-307.

［15］ 郭榮傳，葉水生，閔泉，等.改進的快速FCM圖像分割算法［J］.計算機系統(tǒng)應(yīng)用，2009，18（7）：33-36.

［16］ Zhou D，Zhou H.A modified strategy of fuzzy clustering algorithm for image segmentation［J］.Soft Computing，2015，19（11）：3261-3272.

［17］ Gonzalez R C，Wood R E，Eddins S L.Digital image processing using MATLAB.Second Edition［M］.北京：電子工業(yè)出版社，2013.