高晉凱,侯 文,楊冰倩,王贇贇
(中北大學 信息與通信工程學院, 太原 030051)
?
·信號處理·
基于蟻群算法的模糊C均值聚類的改進研究
高晉凱,侯 文,楊冰倩,王贇贇
(中北大學 信息與通信工程學院, 太原 030051)
在圖像分割的研究中,模糊C均值(FCM)聚類算法較之前的硬聚類有了很大的改進,是一種基于函數(shù)最優(yōu)方法的聚類算法,然而傳統(tǒng)的FCM算法的聚類中心及個數(shù)難以確定,搜索過程易陷入局部最優(yōu)。因此,提出一種基于蟻群算法的改進的FCM聚類算法。該算法利用了蟻群算法全局優(yōu)化特征以及較強魯棒性的特點,將通過蟻群算法得到的聚類中心及個數(shù)應用到傳統(tǒng)FCM算法中,彌補了傳統(tǒng)FCM聚類算法的不足。該算法對圖像進行分塊處理,并引入多尺度梯度,提高了圖像分割的準確性,最后通過實驗驗證了該算法的有效性及實用性。
圖像分割;蟻群算法;模糊C均值聚類;梯度
圖像分割是指把一幅圖像分成若干互不交疊、有意義的、具有相同性質(zhì)的區(qū)域,并提出感興趣目標的技術和過程。它是由圖像處理到圖像分析的關鍵步驟[1-2]。
模糊C均值(FCM)聚類算法應用于圖像分割時,是基于目標函數(shù)式的一種局部搜索算法,該算法對初值敏感且容易陷入局部極值,很難得到全局最優(yōu)解。因此,無法對圖像進行準確分割。而且聚類過程中,該算法計算量很大,計算耗時。另外,傳統(tǒng)FCM算法僅依據(jù)圖像的灰度特征來建立目標函數(shù),而圖像的特征是多樣的。因此,基于灰度特征建立的目標函數(shù)式無法完整地描述圖像,即難以準確地刻畫圖像特征。
以往對傳統(tǒng)FCM算法的改進,在一定程度上優(yōu)化了FCM算法,但是仍有存在一定的缺陷。文獻[3]中引入了調(diào)衡因子,在一定程度上提高了算法的抗噪性,但是需要計算所有樣本點間的距離,因此計算量很大,計算所需的時間較長,不利于圖像的實時處理;文獻[4]提出了更趨明晰的模糊隸屬度,該算法雖在一定程度上提高了圖像分割的準確性,但其聚類數(shù)目人為隨機選定,因此其聚類結果具有不確定性;文獻[5]中引入了聚類中心引導函數(shù),加快了聚類過程,但是當算法進行到一定程度時,會出現(xiàn)停滯現(xiàn)象,無法找到全局最優(yōu)解;文獻[6]提出的算法適用于灰度有明顯變化的圖像,不具有普遍性。
本文在文獻[7-8]算法的基礎上提出了基于蟻群算法的FCM聚類算法的改進,蟻群算法的離散性和并行性特點對數(shù)字圖像非常適用,基于蟻群算法的全局及分布式優(yōu)化方法,將蟻群算法與FCM聚類有機結合,可有效提高FCM算法的圖像分割效果。該算法在一定程度上提高了圖像分割的準確性以及效率,減少了計算量,縮短了計算時間。
1973年,Bezdek[9]提出了FCM聚類算法,作為早期硬C均值聚類(HCM)方法的一種改進。FCM聚類算法通過計算每個樣本點對所有類中心的隸屬度,并對目標函數(shù)不斷進行優(yōu)化找到最優(yōu)解,從而決定樣本點的類屬,達到對樣本數(shù)據(jù)集進行聚類的目的[10-11]。
將數(shù)據(jù)的聚類轉(zhuǎn)化為一個非線性優(yōu)化問題,并通過迭代來進行求解,是一種非監(jiān)督模糊聚類標定過程[12-13]。
設圖像數(shù)據(jù)樣本集為X={xi|xi=(xi1,xi2, …,xim)},其中,i=1,2,…,n,n為數(shù)據(jù)總數(shù),m為每個樣本的特征個數(shù),定義隸屬度矩陣uij為樣本xi屬于第j類的隸屬度,可表示為
(1)
式中:i=1,2,…,c,j=1,2,…,n,M∈[1+∞),是一個加權指數(shù);dij=‖xj=ci‖,表示從樣本xj到聚類中心ci的歐氏距離。
uij具有如下特征
(2)
聚類中心c={c1,c2,…,cc},計算公式如下
(3)
目標函數(shù)表達形式為
(4)
傳統(tǒng)的FCM算法是一個簡單迭代的過程,算法步驟為:(1)隨機初始化隸屬度矩陣,使其滿足式(2)特征約束條件;(2)利用式(3)計算聚類中心ci(i=1,2,…,c);(3)根據(jù)式(4)計算目標函數(shù),并判斷當目標函數(shù)值小于某一閾值,或與上次目標函數(shù)值進行比較得出的變化量小于某一閾值,或迭代次數(shù)達到最大時,算法停止,否則根據(jù)式(1)重新計算隸屬度矩陣并返回步驟(2)。
上述算法通過隨機初始化隸屬度矩陣,并對算法進行簡單迭代,多次調(diào)整聚類中心及隸屬度的值直到目標函數(shù)值的變化量達到某一范圍,最終確定樣本的聚類類別。該算法計算簡單,容易實現(xiàn),但對初值敏感且容易陷入局部極值,很難得到全局最優(yōu)解,這給圖像分割造成十分不利的影響。另外,F(xiàn)CM算法是根據(jù)圖像的灰度特征來建立目標函數(shù),而圖像的灰度是有關圖像的“不完全數(shù)據(jù)”,不能準確地刻畫圖像特征。因此采用傳統(tǒng)的FCM算法無法對圖像進行準確分割。
改進的FCM首先對蟻群算法中的信息素濃度更新算法進行改進,避免螞蟻過于集中在某些路徑上的信息素濃度增加過快,從而避免螞蟻算法陷入局部極值,將其應用于FCM聚類算法的搜索過程,則可在一定程度上避免FCM算法陷入局部最優(yōu);其次,進行聚類中心的確定,針對圖像背景復雜、有噪聲等特點引入了多尺度梯度,并將圖像進行分塊處理來提高圖像分割的準確性。
2.1 基本蟻群算法
蟻群算法是一種用來尋找優(yōu)化路徑的幾率型算法,由MarcoDorigo[14]于1992年提出,該算法指出在蟻群尋找食物時,它們總能找到一條從食物到巢穴之間的最優(yōu)路徑,并且能夠隨著環(huán)境的變化相應地搜索新的最優(yōu)路徑。
螞蟻隨機地對巢穴到食物源的路徑進行選擇,當通過某一路徑時會留下信息素,信息素以一定速率隨著時間揮發(fā),每只螞蟻在它能感知到的范圍內(nèi)尋找食物,如果有就直接過去。否則就判斷是否有信息素,如果判斷出周圍沒有信息素,螞蟻會根據(jù)自己原來的運動方向慣性地運動下去;當周圍存在信息素時,螞蟻能夠比較在感知到的范圍內(nèi)哪個方向的信息素濃度高,然后朝著信息素濃度高的方向走。每只螞蟻都依照該規(guī)則朝著信息素濃度最高的方向移動,促使該路徑中的信息素濃度不斷增強,而強度大的信息素又會吸引更多的螞蟻,如此便形成一種正反饋機制,正是由于這種正反饋機制,螞蟻最終發(fā)現(xiàn)最短路徑[15]。
將螞蟻尋找食物源的過程看作是一個不斷聚類的過程,食物源即是聚類的中心[16],因此,可以將蟻群算法應用于圖像分割,將圖像數(shù)據(jù)集合看作人工螞蟻,圖像分割的過程即為人工螞蟻尋找食物源的過程。假設圖像像素總數(shù)為N,將圖像的每個像素看作一只螞蟻,通過提取像素的灰度及梯度特征,可以得到每只螞蟻的一個表示梯度與灰度的二維向量。
假設圖像數(shù)據(jù)集合為
X={Xi|Xi=(xi1,xi2,…,xim),i=1,2,…,N}
(5)
式中:m為圖像特征,這里取值為2,分別表示梯度與灰度兩個特征。
將樣本到聚類中心的歐式加權距離表示為
(6)
式中:pk為加權因子,其值可由兩個特征對聚類的影響程度而定。
設τij(0)=0為初始信息量,則螞蟻通過路徑(i,j)時留下的信息素濃度可表示為
(7)
式中:r為聚類半徑。
根據(jù)樣本與聚類中心之間的路徑上的信息素濃度,Xi歸并到cj上的概率Pij(t)為
(8)
式中:ηij(t)=1/dij為啟發(fā)式引導函數(shù),表征Xi轉(zhuǎn)移到cj的期望程度,即啟發(fā)式函數(shù)越大,像素歸于同一類的概率就越大;?、β分別為聚類過程中信息素及引導函數(shù)影響路徑選擇的因子;K={Xk|dkj≤r,k=1,2,…,j,j+1, …,N}為下一步可選的路徑集合。
設置常數(shù)P0,當Pij(t)>P0時,將Xi歸并到cj類中,設cj={Xs|dsj≤r,s=1,2,…,J}。則可求出更新后的聚類中心為
(9)
式中:Xs∈cj。
螞蟻在移動的過程中,不同路徑上信息素的濃度發(fā)生變化,經(jīng)過一次循環(huán)后,依據(jù)全局調(diào)整規(guī)則調(diào)整不同路徑上的信息素如下
τij(t)=ρτij(t)+Δτij
(10)
式中:ρ為信息素濃度隨時間的衰減系數(shù);Δτij為本次循環(huán)中路徑信息素濃度的增量
(11)
2.2 信息素更新機制的改進
螞蟻算法通過信息素與引導函數(shù)的共同作用進行最大概率的路徑選擇,當搜索進行到一定程度后,所有螞蟻個體的解趨于一致。如果該解所對應的路徑不是全局最優(yōu)路徑,但其信息素濃度過高時,僅僅依靠公式對路徑信息素濃度進行調(diào)整會使蟻群算法陷入局部收斂,無法找到全局最優(yōu)解;當轉(zhuǎn)移概率過大時,雖然有比較快的收斂速度,但會導致算法過早收斂。因此本文提出信息素濃度調(diào)節(jié)因子ω,調(diào)節(jié)因子的應用可有效避免螞蟻過于集中的路徑上的信息素濃度增加過快的現(xiàn)象,從而能夠避免蟻群算法陷入局部極值。
引入信息素濃度調(diào)節(jié)因子ω,即
(12)
該路徑上信息素濃度更新機制表示為
“體”—多面架構成體,實現(xiàn)多層面、多維度的深度協(xié)同,具體形式是“教師教育實驗區(qū)”。以區(qū)域教師進修院校為紐帶,緊密聯(lián)系高等院校和中小學教師形成研修聯(lián)盟,改變教師發(fā)展場域,由高校引領理論方向,中小學提供教學實踐,實現(xiàn)多層面、多學科、多維度的教學研究,形成群體共振效應,整體提升中小學教師的教學能力。
τij(t)=ρτij(t)-f(ω)
(13)
信息素濃度調(diào)節(jié)因子ω的引入可在一定程度上避免螞蟻過于集中于某路徑上的信息素濃度增加過快,有利于蟻群算法尋找到全局最優(yōu)解。將該思想應用到FCM聚類算法中,則可有效避免算法陷入局部最優(yōu)解,增加了算法的實用性。
2.3 確定聚類中心
大多數(shù)處理圖像由于背景復雜、有噪聲等特點,難以確定合適的聚類中心,而傳統(tǒng)FCM算法的聚類結果依賴于初始值的選取。為了提高圖像分割的準確性,本文將圖像進行分塊處理,不同的圖像塊采用蟻群算法設置不同參數(shù)來進行處理。另外,在圖像分割過程中,采用一般的圖像分割方法提取的目標區(qū)域在弱邊緣處存在不連續(xù)性,圖像的邊緣是由圖像灰度強度的不連續(xù)性產(chǎn)生的,這種不連續(xù)性可由梯度變化來進行表征。因此,本文中使用多尺度梯度來增大梯度在弱邊緣處的響應。
確定聚類中心的過程可分為兩步進行:
(1)多尺度梯度值的計算
設圖像表示為f(x,y),由于處理圖像是離散的,則圖像的梯度可定義為
(14)
上式主要針對圖像中變化明顯的邊緣,如果要用于圖像中變化平緩的區(qū)域所形成的邊緣,則需要擴大特征定義的適用范圍,基于此提出了多尺度分析的思想[17],該思想的應用擴大了計算像素梯度時涉及像素的范圍,基于多尺度梯度得到的梯度響應能夠考慮到距離該像素點較遠的像素的差別,提高了平緩區(qū)域形成邊緣的響應,滿足了邊緣特征定義廣泛適用性的要求。
基于多尺度的梯度可定義為
(15)
式中:l為采樣尺度。
(16)
式中:a為待定參數(shù);L為采樣的最大尺度。
從該梯度值的計算中,可以看出,隨著l增大,距離邊緣兩側(cè)較遠像素的梯度值對邊緣的響應影響較小,從而可以在邊緣處得到真正的峰值響應。
(2)圖像分塊處理
將圖像分為n×n塊進行處理,首先對每個窗口內(nèi)的各個像素點根據(jù)式(16)計算梯度值,將梯度值大于閾值的像素點設為邊界或噪聲,小于閾值的像素點設為目標或背景,閾值的設定可由各窗口內(nèi)所有像素點梯度值的均值得到,這樣每個窗口內(nèi)的像素可大致分為兩類。
觀察各窗口中灰度直方圖的峰值點,計算得到各峰值點處的像素點,將得到的峰值像素點設為初始聚類中心,給每個窗口設定蟻群算法參數(shù),即迭代次數(shù)、螞蟻每次迭代的步數(shù)及各窗口的信息素矩陣。根據(jù)式(8)計算得到螞蟻移動到該窗口內(nèi)各聚類中心中的最大概率路徑,并沿最大概率路徑將像素點歸并到該聚類中心,當計算達到迭代次數(shù)時,停止計算,可以得到每個窗口內(nèi)的聚類中心。將得到的聚類中心應用于FCM聚類算法,可以極大地改善FCM算法的局部收斂性,減少FCM算法的計算量。
2.4 改進的FCM聚類算法流程
(1)初始化蟻群算法各參數(shù),如?、β、Q、M、P0、P1、P2等;
(2)將圖像分為n×n個圖像塊,觀察各圖像塊的直方圖,將直方圖的峰值點看作初始聚類中心;
(3)由式(16)計算得到各峰值像素點處的多尺度梯度值,當梯度值大于閾值P1時判為邊界點或噪聲點,當梯度值小于P1時,將像素點判為目標或背景;
(5)通過式(13)計算各路徑上的信息素濃度,并由式(8)計算Xi合并到cj的概率,當概率大于某一值P0時,將Xi合并到cj類中;
(7)當聚類中心變化量小于閾值P2時,停止計算,并輸出聚類中心及聚類個數(shù);
(8)將上述計算得到的聚類中心及聚類個數(shù)作為改進FCM聚類算法的初始聚類中心及個數(shù),并初始化改進的FCM聚類算法的各參數(shù),如P3、ε等;
(9)由dij=‖xj-ci‖計算歐氏距離dij;
(10)根據(jù)式(1)計算隸屬度矩陣,根據(jù)式(3)更新聚類中心;
(11)由式(4)計算目標函數(shù)值,并判斷當函數(shù)值小于設定閾值P3,或相對于上次目標函數(shù)值的變化量小于ε時,或達到最大迭代次數(shù)時,停止計算;否則,返回步驟(10)。
本文在MATLABR2012a環(huán)境下,以大小為256×256的三幅圖像為例,通過比較傳統(tǒng)FCM聚類算法與改進后的FCM聚類算法在圖像分割的準確性以及計算時間方面驗證算法的有效性及實用性。通過實驗,得到每個窗口最佳的迭代次數(shù)及步數(shù),取圖像分塊大小n=5。得到的實驗結果如圖1所示。
圖1 不同分割方法處理圖像比較
分析比較以上三幅圖像的原始圖像及處理后的圖像:由圖1中的兩幅圖像,可以看到采用改進FCM算法較傳統(tǒng)FCM算法,處理過的青椒圖像含雜質(zhì)點更少,說明改進的FCM算法具有一定的抗噪性;從圖2處理圖像中的帽檐、嘴唇處可以明顯看出改進的FCM算法分割后的圖像邊界輪廓較明顯;圖3中經(jīng)過改進的FCM算法處理過的圖像,其遠處房子及水面的輪廓也可以比較完整地看到,即圖像分割更加準確;加上表1兩種算法迭代次數(shù)及計算時間的比較,可以得出改進后的FCM算法迭代次數(shù)明顯減少,縮短了圖像處理的時間。
圖2 不同分割方法處理圖像比較
圖3 不同分割方法處理圖像比較
圖像圖1圖2圖3傳統(tǒng)FCM迭代次數(shù)455150改進FCM迭代次數(shù)111212傳統(tǒng)FCM計算時間/s20.012520.081319.1327改進FCM計算時間/s10.860111.01829.2765
綜上可得,基于蟻群算法的改進的FCM聚類算法在圖像分割過程中,避免了傳統(tǒng)FCM算法易陷入局部最優(yōu)、抗噪性差及計算量大、計算時間長的缺陷。
本文針對傳統(tǒng)FCM算法對初始值敏感,并且容易陷入局部最優(yōu),計算時間長等缺點,將蟻群算法與FCM算法有機結合,提出了改進的FCM算法。該改進算法利用蟻群算法來確定初始聚類中心及聚類個數(shù),有效改善了傳統(tǒng)FCM算法容易陷入局部最優(yōu)及計算時間長的缺陷。在圖像分割的過程中,采用圖像分塊處理方法及引入多尺度梯度來提高圖像分割的準確性,并在實驗中采用不同的圖像驗證了該算法的有效性。
[1] SHANKAR B U, MEHER S K, GHOSH A. Wavelet-fuzzy hybridization: feature-extraction and land-cover classification of remote sensing images[J]. Applied Soft Computing, 2011, 11( 3): 2999-3011.
[2] 李旭超, 劉海寬, 王 飛, 等. 圖像分割中的模糊聚類方法[J]. 中國圖像圖形學報, 2012,17(4):447-458. LI Xuchao, LIU Haikuan, WANG Fei, et al. The survey of fuzzy clustering method for image segmentation[J]. Journal of Image and Graphics, 2012, 17(4): 447-458.
[3] 張瑞麗, 張繼福. 基于ω-距離均值的模糊聚類算法[J]. 計算機應用, 2012, 32(7):1978-1982. ZHANG Ruili, ZHANG Jifu. Fuzzy clustering algorithm based on ω-mean distance[J]. Journal of Computer Applications, 2012, 32(7): 1978-1982.
[4] 張 揚, 王士同, 韓 斌. 基于改進模糊聚類算法魯棒的圖像分割[J]. 中國圖像圖形學報, 2008,13(5):911-917. ZHANG Yang, WANG Shitong, HAN Bin. Robust image segmentation based on improved fuzzy clustering algorithm[J]. Journal of Image and Graphics, 2008, 13(5): 911-917.
[5] 張 健. 基于蟻群算法的圖像分割方法改進研究[J]. 湖州技術學院學報, 2014(1): 84-91. ZHANG Jian. Improvement of image segmentation based on ant colony algorithm[J]. Journal of Huzhou Vocational and Technical College, 2014(1): 84-87.
[6] 薛 琴, 陳 瑋, 羅俊奇. 基于梯度算子的蟻群圖像分割算法研究[J]. 計算機工程與設計, 2007, 28(23):5660-5663. XUE Qin, CHEN Wei, LOU Junqi. Research on image segmentation by ant colony algorithm based on gratitude operator[J]. Computer Engineering and Design, 2007, 28(23): 5660-5663.
[7] 陳 亮, 郭 雷. 一種基于蟻群算法的邊緣提取算法[J]. 光子學報, 2010, 39(4):759-763. CHEN Liang, GUO Lei. An edge extraction algorithm based on ant colony algorithm[J]. Acta Photonica Sinica, 2010, 39(4): 759-763.
[8] 余衛(wèi)宇, 鄒若冰, 禹之鼎, 等. 基于局部蟻群算法的圖像分割[J]. 計算機應用, 2010, 30(5):1344-1346. YU Weiyu, ZOU Ruobing, YU Zhiding, et al. Image segmentation based on local ant colony optimization[J]. Journal of Computer Application, 2010, 35(5): 1344-1346.
[9] BEZDEK J C. Pattern recognition with fuzzy objective function algorithm[M]. New York: Plenum Press, 1981.
[10] 康曉東, 何丕廉, 劉玉潔, 等. 基于蟻群算法的醫(yī)學圖像分割研究[J]. 計算機應用研究, 2008, 25(9):2853-2855. KANG Xiaodong, HE Pilian, LIU Yujie, et al. Study on medical segmentation based on ant colony algorithm[J]. Application Research of Computers, 2008, 25(9): 2853-2855.
[11] 羅 旭, 吳曉軍. 蟻群優(yōu)化算法在WSN路由中的應用研究[J]. 計算及工程與科學, 2015, 37(4):740-746. LUO Xu, WU Xiaojun. Application study of ant colony optimization in wirelessensor network routing[J]. Computer Engineering & Science, 2015, 37(4): 740-746.
[12] 胡 慧, 何聚厚, 何秀青. 基于模糊理論和蟻群算法的圖像邊緣連接方法[J]. 計算機工程與應用, 2014, 50(3):168-172. HU Hui, HE Juhou, HE Xiuqing. Edge linking method based on fuzzy theory and ant colony algorithm[J]. Computer Engineering and Applidations, 2014, 50(3): 168-172.
[13] 白 楊, 孫 躍, 王 君, 等. 基于動態(tài)自適應蟻群算法的MRI圖像分割[J]. 計算機科學, 2008, 35(2): 226-229. BAI Yang, SUN Yue, WANG Jun, et al. Segmentation of MRI based on dynamic and adaptive ant colony algorithm[J]. Computer Science, 2008, 35(2): 226-229.
[14] 楊立才, 趙麗娜, 吳曉晴. 基于蟻群算法的模糊C均值聚類醫(yī)學圖像分割[J]. 山東大學學報, 2007,37(3):51-54. YANG Licai, ZHAO Lina, WU Xiaoqing. Medical image segmentation of fuzzy C-means clustering based on the ant colony algorithm[J]. Journal of Shandong University, 2007, 37(3): 51-54.
[15] 屠 莉, 楊立志. 一種基于蟻群優(yōu)化的圖像分類算法[J]. 計算機應用與軟件, 2015, 32(4): 202-205. TU Li, YANG Lizhi. An image classification algorithm based on ant colony optimization[J]. Computer Applications and Software, 2015, 32(4): 202-205.
[16] SURI J S, SINGH S, REDEN L. Computer vision and patter recognition techniques for 2-D and 3-D MR cerebral cortical segmention(Part I): a state-of-the-art review[J]Pattern Analysis & Applications, 2002(5): 46-76.[17] FERNANDES C, RAMOS V. ROSA A C. Self-regulated artificial ant colonies on digital image habitats[J].International Journal of Lateral Computing, 2005, 2(1): 1-8.
高晉凱 女,1990年生,碩士研究生。研究方向為智能信息處理。
侯 文 男,1967年生,教授,碩士生導師。研究方向為自動化測試與控制技術、動態(tài)測試與智能儀器。
楊冰倩 女,1991年生,碩士研究生。研究方向為圖像處理。
王贇贇 女,1990年生,碩士研究生。研究方向為信號處理。
Improved Fuzzy C-means Clustering Based on Ant Colony Algorithm
GAO Jinkai,HOU Wen,YANG Bingqian,WANG Yunyun
(School of Information and Communication Engineering, North University of China, Taiyuan 030051, China)
In the study of image segmentation, fuzzy C-means clustering algorithm (FCM) has been greatly improved compared to the previous hard clustering, which is a clustering algorithm based on a function of best practices. However, the clustering center and number are difficult to be determined for the traditional FCM, also the search process is easy to fall into local optimum. So an improved FCM clustering algorithm is proposed based on the ant colony algorithm.The improved algorithm uses the global optimization features and strong characteristics of robustness of ant colony algorithm.The cluster centers and number obtained by ant colony algorithm are applied to a traditional FCM algorithm to make up for the shortcomings of the traditional FCM. The improved algorithm improves the image segmentation accuracy by processing the image blocks and introducing the multi-scale gradient. Finally the effectiveness and the practicality of the improved algorithm is verified through the experiments.
image segmentation; ant colony algorithm; fuzzy C-means clustering; gradient
10.16592/ j.cnki.1004-7859.2016.11.007
高晉凱 Email:740526799@qq.com
2016-08-17
2016-10-19
TP311.13
A
1004-7859(2016)11-0030-05