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

徐路，蔣振剛

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

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

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

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

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

1 FCM分割算法

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

并且滿足下列約束條件：

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

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

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

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

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

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

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

2.1 確定聚類中心步驟：

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

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

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

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

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

為了準確的劃分區間，在如下情況時，優先操作下述方法：

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

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

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

設tl為區間起點，th為區間終點，h(i)為像素i所出現的概率，L值為256。

2.2 圖像分割步驟

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

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

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

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

3 實驗結果

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

表1 FCM算法與本文提出的算法對多組圖像進行分割的數據統計

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

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

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

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

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

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

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

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

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

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

4 結論

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

參考文獻

［1］ Bezdek J C，Ehrlich R，Full 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］ 何巍，魏國棟，師為禮，等.基于點云的膝關節脛骨三維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］ 張軍賢.基于改進模糊聚類算法的醫學圖像分割研究［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］ 張小峰.基于模糊聚類算法的醫學圖像分割技術研究［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］ 張翡，范虹，郝艷榮.結合非局部均值的快速FCM算法分割MR圖像研究［J］.計算機科學，2014，41（5）：304-307.

［15］ 郭榮傳，葉水生，閔泉，等.改進的快速FCM圖像分割算法［J］.計算機系統應用，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］.北京：電子工業出版社，2013.