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

范浩祥，張小鳳

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

1 引言

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

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

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

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

2 相關(guān)工作

2.1 FCM

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

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

(1)

(2)

模糊隸屬度和聚類(lèi)中心的迭代公式如下

(3)

(4)

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

FCM算法在應(yīng)用到圖像分割中時(shí)，主要是灰度圖像的分割。由于灰度圖像灰度等級(jí)的有限可數(shù)特性，在完成模糊聚類(lèi)過(guò)程后，還要對(duì)聚類(lèi)中心進(jìn)行取整，對(duì)各個(gè)灰度級(jí)的隸屬度進(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è)灰度級(jí)別，在一定程度上限制了算法中需要處理的數(shù)據(jù)量大小，因而使用這種映射關(guān)系的算法，相較于傳統(tǒng)FCM算法可提高圖像分割的效率[13]。

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

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

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

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

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

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

βs=(S×T)×0.1%

(10)

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

βm=5βs

(11)

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

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

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

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

具體流程如下：

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

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

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

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

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

Step5：獲取圖片的總像素?cái)?shù)N，以K為聚類(lèi)數(shù)進(jìn)行像素?cái)?shù)量均分，各分區(qū)像素?cái)?shù)量均值為num=N/K。根據(jù)num確定灰度空間Ω中各類(lèi)別的起止灰度級(jí)別gmink、gmaxk，k∈[1，K]，對(duì)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ù)所在灰度等級(jí)，即FCM初始化中心點(diǎn)xk

(13)

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

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

首先，用Lena來(lái)驗(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圖像的聚類(lèi)中心結(jié)果如表1所示。由表1中Lena圖像的結(jié)果可見(jiàn)，減法聚類(lèi)和區(qū)域中位點(diǎn)法均可以找出Lena圖片的聚類(lèi)中心數(shù)為4個(gè)，聚類(lèi)數(shù)量與文獻(xiàn)[14]Lena圖像四聚類(lèi)的結(jié)果一致，且區(qū)域中位點(diǎn)法獲得的初始化中心與FCM算法的結(jié)果更加接近。

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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