圖像模糊聚類分割初始聚類中心優(yōu)化算法研究

范浩祥，張小鳳

(陜西師范大學(xué)物理學(xué)與信息技術(shù)學(xué)院，陜西 西安 710119)

1 引言

圖像的分類與識別在智能信息領(lǐng)域中具有廣泛的應(yīng)用[1]。在圖像處理中，圖像分割是至關(guān)重要的技術(shù)[2]。通常的圖像分割方法主要有閾值分割、聚類分割、邊緣分割等[3]。其中聚類分割方法中，模糊C均值算法(Fuzzy C-Means： FCM) 是一種無監(jiān)督的聚類分割算法[4]，廣泛應(yīng)用于醫(yī)學(xué)圖像、遙感圖像和紅外圖像分割[5]等多個(gè)方面。

FCM作為一類通過迭代更新使目標(biāo)函數(shù)逼近最優(yōu)值的算法，其存在著對初始值敏感和易于陷入局部最優(yōu)的問題。目前，對FCM算法在圖像處理應(yīng)用中的改進(jìn)主要包括：聚類數(shù)量的自適應(yīng)確定、聚類中心初始化、利用圖像空間信息提升算法有效性等。在聚類中心初始化方面，單凱晶[6]等采用一種改進(jìn)的最大最小距離算法對原始空間中的數(shù)據(jù)進(jìn)行粗分類，所得結(jié)果作為初始聚類中心。萬龍[7]提出均值距離最遠(yuǎn)中心法。劉萬軍[8]等人使用灰度直方圖波峰和波谷尋找初始聚類中心和聚類數(shù)。馬冬梅[5]等人通過灰度直方圖的斜率來確定聚類數(shù)量和初始聚類中心。雖然對灰度統(tǒng)計(jì)直方圖分布形態(tài)的分析，可以充分利用圖像的灰度信息，但不可避免的在某些灰度直方圖中存在寬度極小的尖峰，導(dǎo)致依照形態(tài)學(xué)來分析灰度直方圖時(shí)出現(xiàn)較大誤差。Yager[9]等人提出了山函數(shù)算法用以解決FCM中聚類中心初始化的問題，用以實(shí)現(xiàn)聚類中心點(diǎn)和聚類數(shù)量的自適應(yīng)確定。Chiu[10]在山函數(shù)基礎(chǔ)上提出減法聚類，以樣本點(diǎn)來計(jì)算候選聚類中心，減少了工作量。裴繼紅[11]等人提出了樣本空間中樣本半徑的計(jì)算方法，并應(yīng)用密度函數(shù)算法來確定聚類中心，使算法計(jì)算復(fù)雜度大幅度降低。該算法在初始聚類中心的確定、聚類效果以及抗噪性方面都有著良好的效果。以上文獻(xiàn)中部分使用了密度分布特征，可以在一定程度上使得初始聚類中心點(diǎn)的分布更趨合理，降低了FCM算法陷入局部最優(yōu)的概率。

在實(shí)際應(yīng)用中，F(xiàn)CM的聚類中心和隸屬度矩陣在算法中是相互依賴的。在算法執(zhí)行過程中，其中一方有較大數(shù)值調(diào)整會導(dǎo)致另一方有大幅度的變動(dòng)。而傳統(tǒng)FCM算法中，聚類中心及隸屬度矩陣的初始化值與最終聚類結(jié)果有一定差別，F(xiàn)CM算法在執(zhí)行的起始若干代中，聚類中心出現(xiàn)較大幅度的調(diào)整，即粗聚類階段。在算法迭代一定代數(shù)后，聚類中心逼近最優(yōu)結(jié)果，聚類中心的變化趨于小范圍調(diào)整收斂，即為細(xì)聚類階段。通常，在對FCM進(jìn)行初始化參數(shù)優(yōu)化改進(jìn)時(shí)，會優(yōu)先選擇優(yōu)化初始聚類中心點(diǎn)的位置分布，而隸屬度矩陣在算法開始時(shí)依然是隨機(jī)初始化。因此，單純對聚類中心點(diǎn)位置初始化的算法只是在一定程度上減少了FCM算法在粗聚類階段的時(shí)間消耗。

針對上述問題，本文提出了灰度直方圖區(qū)域中位點(diǎn)法，該算法結(jié)合直方圖灰度合并谷值尋優(yōu)確定聚類數(shù)量，通過均勻劃分灰度級別區(qū)域并計(jì)算其像素?cái)?shù)量中位點(diǎn)來確定待分割圖像的初始聚類中心，實(shí)現(xiàn)圖像的聚類中心初始化。將灰度直方圖區(qū)域中位點(diǎn)法和FCM算法相結(jié)合，實(shí)現(xiàn)對圖像聚類分割性能的提升。

2 相關(guān)工作

2.1 FCM

1981年，J.C.Bezdek[12]等人將已有的K-means硬聚類算法推廣為模糊C均值聚類算法，即FCM算法。

設(shè)X={xi|i=1，2，…，N}是有N個(gè)數(shù)據(jù)、K個(gè)類的數(shù)據(jù)集，在FCM算法中，通過優(yōu)化如下的目標(biāo)函數(shù)來實(shí)現(xiàn)聚類

(1)

(2)

模糊隸屬度和聚類中心的迭代公式如下

(3)

(4)

其中γ為迭代代數(shù)。

FCM算法在應(yīng)用到圖像分割中時(shí)，主要是灰度圖像的分割。由于灰度圖像灰度等級的有限可數(shù)特性，在完成模糊聚類過程后，還要對聚類中心進(jìn)行取整，對各個(gè)灰度級的隸屬度進(jìn)行硬化。

2.2 灰度圖像映射到直方圖空間

假設(shè)圖像的大小為S×T，f(s，t)是圖像陣列在位置(s，t)處的像素灰度值函數(shù)，f(s，t)∈{0，1，2，…，255}。定義圖像的一維灰度統(tǒng)計(jì)直方圖函數(shù)為

(5)

其中

(6)

則傳統(tǒng)FCM算法的目標(biāo)函數(shù)可表示為

(7)

(8)

(9)

將圖像從原像素空間映射到其灰度直方圖特征空間，由于灰度直方圖最大只有256個(gè)灰度級別，在一定程度上限制了算法中需要處理的數(shù)據(jù)量大小，因而使用這種映射關(guān)系的算法，相較于傳統(tǒng)FCM算法可提高圖像分割的效率[13]。

3 基于區(qū)域中位點(diǎn)的聚類中心初始化方法

通常，圖像的灰度統(tǒng)計(jì)直方圖中“峰”的數(shù)量與圖像的最優(yōu)分割數(shù)量存在某種關(guān)聯(lián)。在對圖像的灰度直方圖進(jìn)行劃分的過程中，將若干灰度級合并可減少灰度直方圖中的“毛刺”，方便獲得灰度統(tǒng)計(jì)直方圖中的“谷”，進(jìn)而確定聚類數(shù)量。基于此，本文將原256個(gè)灰度級均分為32組，將原灰度直方圖His(g)，g∈[0，255]，映射為新的灰度直方圖H′(g′)，g′∈[1，32]，采用以“谷”來劃分“峰”的方法，通過確定合適的“谷”的數(shù)量，保證灰度直方圖H′(g′)中每個(gè)大“峰”都能在一個(gè)獨(dú)立區(qū)間內(nèi)，在一定程度上降低形態(tài)學(xué)分析帶來的聚類數(shù)量的誤判。

在預(yù)選出候選“谷”點(diǎn)的過程中，需要解決兩個(gè)問題，其一，由于直方圖的分布特點(diǎn)，在用“谷”點(diǎn)確定區(qū)間分割數(shù)量時(shí)，由于兩“谷”點(diǎn)距離過近或“谷”點(diǎn)距離灰度空間邊界過近導(dǎo)致出現(xiàn)極小區(qū)間。其二，直方圖的邊界出現(xiàn)低密度分布區(qū)域會導(dǎo)致低密度分區(qū)。

對于第一個(gè)問題，在預(yù)選出候選“谷”點(diǎn)后，用現(xiàn)有候選“谷”點(diǎn)對整個(gè)灰度空間進(jìn)行分割，取各分割區(qū)間寬度的均值的一半作為閾值φ，當(dāng)現(xiàn)有分割區(qū)間的寬度小于φ時(shí)，則將該區(qū)間與其左側(cè)區(qū)間合并，若區(qū)間左側(cè)為灰度空間邊界，則將該區(qū)間與其右側(cè)區(qū)間合并。

對于第二個(gè)問題，假設(shè)圖像的大小為S×T，當(dāng)同時(shí)滿足如下兩個(gè)條件則該區(qū)域?yàn)榈兔芏确植紖^(qū)域：

條件1：灰度直方圖H′(g′)中單個(gè)灰度級像素?cái)?shù)量不及圖片總像素?cái)?shù)量的0.1%，即單灰度級像素?cái)?shù)量閾值

βs=(S×T)×0.1%

(10)

條件2：從灰度空間邊界起連續(xù)多個(gè)灰度級對應(yīng)像素?cái)?shù)之和不及總像素?cái)?shù)的0.5%，即連續(xù)多灰度級像素總數(shù)閾值：

βm=5βs

(11)

Lena圖像的灰度直方圖低密度分布區(qū)域示意圖如圖1。由圖可知，Lena圖像灰度直方圖的兩端，單個(gè)灰度級不超過50像素，從邊界起連續(xù)灰度級像素?cái)?shù)量和不超過250，則該區(qū)域?yàn)榈兔芏确植紖^(qū)域。

圖1 灰度直方圖低密度分布區(qū)域示意圖

在明確了灰度直方圖中“谷”的確定方法后，考慮采用直方圖灰度合并谷值尋優(yōu)確定聚類數(shù)量，通過劃分灰度級別區(qū)域，計(jì)算直方圖的像素?cái)?shù)量中位點(diǎn)來確定待分割圖像的初始聚類中心。算法流程圖如圖2所示。

圖2 區(qū)域中位點(diǎn)聚類中心初始化FCM算法流程圖

具體流程如下：

Step1：獲取灰度圖像的灰度統(tǒng)計(jì)直方圖His(g)，將256個(gè)灰度級別均分為32組，每一組包含8個(gè)灰度級別，即將原灰度空間Ω映射為新灰度空間Ω′，獲得新灰度直方圖函數(shù)H′(g′)，g′∈[1，32]。

Step2：在H′(g′)中，當(dāng)一個(gè)灰度級的對應(yīng)像素?cái)?shù)量小于左右相鄰兩個(gè)灰度級別對應(yīng)的像素?cái)?shù)，確定其為“谷”，將該灰度級放入候選池。

Step3：用候選池中的灰度級對灰度空間Ω′進(jìn)行分割。計(jì)算閾值φ，當(dāng)區(qū)間的寬度小于φ，則將該區(qū)間的左邊界(較小的灰度級)從候選池中刪除，若區(qū)間左邊界灰度級為1，則將該區(qū)間的右邊界(較大的灰度級)從候選池中刪除。

Step4：計(jì)算得出當(dāng)前待處理圖像的單灰度級像素?cái)?shù)量閾值βs和連續(xù)多灰度級像素總數(shù)閾值βm。當(dāng)處于灰度直方圖兩端的灰度級同時(shí)滿足條件1和條件2，則該區(qū)域?yàn)榈兔芏确植紖^(qū)域。

若有候選“谷”點(diǎn)在此區(qū)域，需將其從候選池中刪除。此時(shí)候選池中剩余的“谷”點(diǎn)數(shù)量加1，即為算法確定的聚類數(shù)量K。

Step5：獲取圖片的總像素?cái)?shù)N，以K為聚類數(shù)進(jìn)行像素?cái)?shù)量均分，各分區(qū)像素?cái)?shù)量均值為num=N/K。根據(jù)num確定灰度空間Ω中各類別的起止灰度級別gmink、gmaxk，k∈[1，K]，對His(g)進(jìn)行分區(qū)。

Step6：由step5獲得直方圖分區(qū)，計(jì)算每個(gè)分區(qū)包含的像素點(diǎn)數(shù)量分別為numk，其中

(12)

Step7：根據(jù)式(13)計(jì)算各區(qū)域的像素?cái)?shù)量中位數(shù)所在灰度等級，即FCM初始化中心點(diǎn)xk

(13)

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

為驗(yàn)證區(qū)域中位點(diǎn)法在圖像聚類分割初始化階段的效果，分別采用Lena圖像和BSDS500數(shù)據(jù)集中的圖片對算法的性能進(jìn)行測試。在CPU為AMD Ryzen5 2500U 2.00 GHz，內(nèi)存8GB，Windows10 64位系統(tǒng)，Matlab 2014a編程環(huán)境下，對測試圖像分別采用區(qū)域中位點(diǎn)法、最大最小值法和減法聚類法方法進(jìn)行聚類分割初始化。在仿真測試過程中，每張測試圖片分別使用每種算法執(zhí)行30次，取運(yùn)算平均用時(shí)進(jìn)行比較。

首先，用Lena來驗(yàn)證區(qū)域中位點(diǎn)法算法的性能。實(shí)驗(yàn)所用Lena圖片及其灰度直方圖如圖3-a1，3-a2所示。圖3-a3為用不同初始化方法進(jìn)行初始化時(shí)的目標(biāo)函數(shù)變化曲線。由圖3-a3的結(jié)果可知，本文算法具有較快的收斂速度，可以用較少的迭代次數(shù)，實(shí)現(xiàn)圖像的初始化。不同初始化方法所獲得的Lena圖像的聚類中心結(jié)果如表1所示。由表1中Lena圖像的結(jié)果可見，減法聚類和區(qū)域中位點(diǎn)法均可以找出Lena圖片的聚類中心數(shù)為4個(gè)，聚類數(shù)量與文獻(xiàn)[14]Lena圖像四聚類的結(jié)果一致，且區(qū)域中位點(diǎn)法獲得的初始化中心與FCM算法的結(jié)果更加接近。

選用BSDS500數(shù)據(jù)集中編號為87015、181079、223061、230098、385028的圖片，對區(qū)域中位點(diǎn)法的圖像分割性能進(jìn)行了測試，其原灰度圖、灰度直方圖和聚類分割目標(biāo)測試，如圖3b-f所示。其中，圖3的b2～f2為測試圖片的灰度直方圖，b3～f3為算法初始化后FCM聚類分割目標(biāo)函數(shù)變化曲線?？梢钥闯觯瑧?yīng)用不同初始化方法獲得的聚類中心應(yīng)用到FCM算法后，獲得的目標(biāo)函數(shù)值均收斂到相同值。圖3-a3～f3中，區(qū)域中位點(diǎn)法均以顯著優(yōu)勢收斂到最優(yōu)值，且區(qū)域中點(diǎn)法初始化的目標(biāo)函數(shù)最終收斂值明顯小于其它初始化方法。即，相較于對比算法，本文算法對FCM算的加速效果更為顯著。

圖3 測試圖片及其對應(yīng)的灰度直方圖和目標(biāo)函數(shù)變化曲線

表1所示為不同方法初始化得到的聚類中心與FCM獲得的聚類中心的對比。從表1中可以看出，四聚類的情況下，本文所提出的初始化算法獲得的聚類中心點(diǎn)與FCM最終聚類結(jié)果非常接近，比如，在編號為223061的測試圖例中，區(qū)域中位點(diǎn)法得到的初始聚類中心到最終結(jié)果平均距離為3，而減法聚類除第四個(gè)中心與結(jié)果很接近外，初始化中心與最終結(jié)果距離均值為17.75，減法聚類的結(jié)果與FCM的聚類結(jié)果差異較大。

表1 不同初始化方法獲得的聚類中心與FCM聚類結(jié)果的對比

為了探究算法的執(zhí)行效率，將初始化階段的耗時(shí)用T1表示，F(xiàn)CM算法階段耗時(shí)用T2表示，用T2-FCM表示傳統(tǒng)FCM算法的平均耗時(shí)，總耗時(shí)為Ttotal=T1+T2，Ttotal-FCM表示傳統(tǒng)FCM算法平均總耗時(shí)，并設(shè)Ttotal-FCM=T2-FCM，分別從算法總耗時(shí)，初始化后FCM階段算法耗時(shí)兩個(gè)方面呈現(xiàn)算法特性。為了表征不同初始化FCM算法相較于傳統(tǒng)FCM算法的執(zhí)行效率，定義

(14)

(15)

仿真結(jié)果如表2和表3所示，其中表2為優(yōu)化總耗時(shí)與隨機(jī)初始化FCM的耗時(shí)對比，表3為優(yōu)化初始化后，F(xiàn)CM階段耗時(shí)與隨機(jī)初始化FCM耗時(shí)的對比。從表2和表3的計(jì)算結(jié)果可以看出，三種初始化方法均一定程度上降低了FCM聚類算法在時(shí)間上的消耗，對于圖87015、181079、230098，本文算法的執(zhí)行效率相較于傳統(tǒng)FCM均有13%～25%的提升，而在對于圖385028的結(jié)果，區(qū)域中位點(diǎn)法更是實(shí)現(xiàn)了超過一倍的性能提升。區(qū)域中位點(diǎn)法在FCM階段運(yùn)行時(shí)間的消耗與初始化加FCM階段運(yùn)行時(shí)間消耗方面，均低于隨機(jī)初始化情況下FCM平均運(yùn)行時(shí)間的一半。

表2 Ttotal (s)耗時(shí)對比

表3 T2(s)耗時(shí)對比

5 結(jié)語

針對現(xiàn)有FCM圖像聚類分割算法聚類中心隨機(jī)初始化易導(dǎo)致算法陷入局部最優(yōu)且計(jì)算效率不高的問題，提出了一種基于圖像灰度直方圖灰度級合并谷值尋優(yōu)確定聚類數(shù)量，并依據(jù)圖像灰度統(tǒng)計(jì)直方圖的均分區(qū)域中位點(diǎn)確定FCM聚類初始化中心點(diǎn)。對實(shí)際的圖像進(jìn)行FCM聚類分割的結(jié)果表明，相較于對比算法，本文算法在運(yùn)算復(fù)雜度和對FCM算法的加速方面具有較為明顯的優(yōu)勢。