動態(tài)粒子群優(yōu)化K-means的圖像分割算法研究

楊雨航

（重慶師范大學計算機與信息科學學院，重慶401331）

0 引言

圖像分割是一個從目標圖像中具有獨特性質(zhì)的區(qū)域中將感興趣的目標提取出來的一門技術或者一個過程，對于后續(xù)進行的圖像分析和圖像識別有著不可忽視的影響，是完成圖像處理的關鍵步驟[1]。目前，圖像分割已經(jīng)廣泛應用于包括工業(yè)、醫(yī)學、交通、農(nóng)業(yè)等各個領域[2-3]。

K-means聚類算法是一種半監(jiān)督學習方法，特點是能夠快速處理大數(shù)據(jù)集，目前已經(jīng)在圖像分割領域得到廣泛應用[4]。但K-means聚類算法存在以下幾點局限性[5]：K-means聚類算法采取隨機選取初始聚類中心的辦法，因此，聚類結(jié)果對聚類中心的依賴較高；K-means聚類算法需在算法進行初始化時即確定聚類數(shù)目；K-means聚類算法的結(jié)果受噪聲點影響較大，對噪聲較為敏感，容易被少量數(shù)據(jù)影響最終聚類結(jié)果；K-means聚類算法容易收斂至局部最優(yōu)解，從而錯過全局最優(yōu)解。

為了克服這些局限性，粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）因其擁有強大的全局搜索優(yōu)化的能力這一特點[6]，帶給國內(nèi)外一些研究人員啟發(fā)，提出了一些通過結(jié)合PSO粒子群優(yōu)化算法對K-means聚類算法進行改進的方法。如穆瑞輝提出的基于粒子群優(yōu)化的模糊K-means目標分類算法[7]；班俊碩提出的基于PSO與K-means聚類的混合算法[8]；劉桂紅等提出的利用PSO+K-means混合算法來改進全局優(yōu)化能力[9]。然而，粒子群優(yōu)化算法PSO本身也存在一些局限性[10]，由于標準粒子群優(yōu)化算法的慣性系數(shù)為初始化時的一個固定值，該值的選取如果不合適，可能會出現(xiàn)粒子在某局部極端之間徘徊，導致算法結(jié)果收斂至局部最優(yōu)解甚至難以收斂至一個結(jié)果。

本文通過結(jié)合改進的粒子群優(yōu)化和K-means聚類算法來進行圖像分割。首先采用雙邊濾波對目標圖像進行平滑降噪處理，以減輕噪聲對后續(xù)圖像分割過程中K-means算法聚類結(jié)果的影響，再通過動態(tài)調(diào)整PSO粒子群優(yōu)化算法中的慣性系數(shù)的大小更新每次迭代中的粒子速度，使其能夠克服易于陷入局部最優(yōu)的缺點，獲得較好的圖像分割效果。

1 相關理論

1.1 K-means算法

K-means算法應用于圖像分割[11]時，即將目標數(shù)字圖像劃分為K個簇，通常情況下，K-means算法將每一幅目標圖像都抽象成具有n維向量的數(shù)據(jù)點集合X={X1,X2,…,Xn}，找出該集合的子集 Z={C1,C2,…,Ck}來最小化目標函數(shù)：

式中，‖Xj-Ci‖2表示目標圖像數(shù)據(jù)點Xj到聚類中心Ci的歐氏距離，D越小，說明聚類效果越好。因此，K-means算法通過對目標函數(shù)進行多次迭代使其達到最小化，并在每次迭代時不斷更新聚類中心，更新公式為：

式中，ni表示第i個簇中數(shù)據(jù)點的個數(shù)，聚類中心在更新過程中，同一聚類中心的簇中的數(shù)據(jù)點相似度朝著增大的趨勢發(fā)展，而不同簇之間數(shù)據(jù)點之間的相似度逐漸減小的方向發(fā)展，直至聚類中心不再變化，說明已達到收斂，聚類完成。

1.2 標準粒子群算法

粒子群算法[12]，也叫做粒子群優(yōu)化算法或者鳥群覓食算法，算法初始化時先隨機化問題最優(yōu)解，經(jīng)過不斷迭代計算，最終得到最優(yōu)解。對于每一個優(yōu)化問題，PSO都將該問題的解看作是搜索空間中忽略體積和質(zhì)量的粒子，每一個粒子都有其對應的初始位置和初始速度，并隨著適應度值的不同每一次迭代都有相應變化，每個粒子都有一個對應的適應度，該適應度的大小由目標優(yōu)化函數(shù)決定。假定在D維空間中存在N個粒子，粒子i的位置表示為Xi={Xi1,Xi2,…,XiD}，粒子i的速度表示為Vi={Vi1,Vi2,…,ViD}，粒子i其個體經(jīng)歷的最好位置表示為pbesti={pi1,pi2,…,piD}，粒子群經(jīng)歷的全局最佳位置表示為gbest={g1,g2,…,gD}。

第k次迭代粒子i的第j維的速度更新計算公式如下：

第k次迭代粒子i的第j維位置更新計算公式如下：

式中，w為慣性系數(shù),；c1和c2為加速度常數(shù)，也稱學習因子，分別代表著粒子的自我學習能力和集體學習能力，取值區(qū)間為[0,4]，通常取 c1=c2=2；r1和 r2為兩個在區(qū)間[0,1]均勻分布的隨機數(shù)。

2 改進的動態(tài)PSO優(yōu)化K-means的圖像分割算法

2.1 平滑濾波

由于圖像在采集、獲取、傳送和轉(zhuǎn)換過程中的環(huán)境復雜多變，例如會受到光照、電磁等因素影響，均存在不同程度的被可見或不可見的噪聲干擾，導致圖像不僅在視覺質(zhì)量上有所下降，噪聲甚至可能會掩蓋某些重要圖像細節(jié)[13]。因此，在對采集到目標圖像做進一步的分割處理時，可先對圖像進行必要的濾波降噪[14]處理。

本文算法選擇雙邊濾波來完成對目標圖像的降噪處理。雙邊濾波[15]是一種非線性濾波方法，通過將目標圖像的像素值相似度與空間鄰近度相結(jié)合完成采樣，以達到同時考慮到灰度相似性和空域信息的目的，從而在完成對圖像進行降噪的同時對圖像邊緣也能夠進行很好保存。濾波效果如圖1所示。

圖1 平滑濾波結(jié)果對比

2.2 動態(tài)慣性系數(shù)

根據(jù)前文對標準粒子群算法的描述可知，該算法容易錯過全局最優(yōu)解，而陷入局部最優(yōu)解的徘徊。因此，將固定慣性系數(shù)進行動態(tài)調(diào)整是一個解決該問題的有效途徑。本文算法使每次迭代的慣性系數(shù)w服從一個概率分布，其概率密度函數(shù)為：

2.3 動態(tài)PSO優(yōu)化K-means算法

本文算法在完成平滑濾波預處理之后，剩下的工作主要分為兩個階段：第一個階段為利用動態(tài)粒子群優(yōu)化算法搜索全局最優(yōu)解得到初始聚類中心；第二階段為K-means算法繼續(xù)進行迭代直至收斂。首先從將目標圖像平滑濾波處理后得到的具有n維向量數(shù)據(jù)點集合X中隨機選取m個數(shù)據(jù)點構成優(yōu)化問題的解空間，也即后續(xù)在K-means算法階段用來初始化聚類中心；然后將集合X中剩余數(shù)據(jù)點分配給這m類，令xi為集合X中的第i個數(shù)據(jù)點，cj為第j個聚類中心，若||xi-cj||=min||xi-ck||（其中k=1,2,…,m），則將數(shù)據(jù)點xi歸入第j類，該粒子的適應度計算公式為：

由此，動態(tài)粒子群算法的收斂程度可由粒子的適應度變化表示，即當粒子適應度不再變化時，算法收斂。本文選擇使用方差δ2來表示適應度變化，當方差小于某一指定值時，認為該算法達到全局最優(yōu)，其計算公式如下：

式中，favg表示粒子的平均適應度，計算公式如下：

當動態(tài)粒子群優(yōu)化算法達到全局最優(yōu)后，將輸出的最優(yōu)解結(jié)果作為第二階段K-means聚類算法的初始聚類中心，從而在一定程度上克服K-means聚類算法初始聚類中心的隨機選取對聚類結(jié)果影響較大這一局限性，有效提高K-means算法的收斂速度。

本文算法流程如下：

Step1.讀取目標圖像數(shù)據(jù)，采用雙邊濾波進行降噪處理；

Step2.計算每個粒子適應度；

Step3.更新慣性系數(shù)，粒子速度和位置；

Step4.計算適應度方差；

Step5.判斷方差大小，若大于規(guī)定值，則返回Step2，若不大于規(guī)定值，則輸出結(jié)果到下一步驟；

Step6.將輸出的全局最優(yōu)解作為聚類算法的初始聚類中心；

Step7.計算數(shù)據(jù)點到聚類中心距離；

Step8.更新聚類中心直至收斂，若聚類中心不再變化，輸出結(jié)果，否則，返回Step7。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境及實驗數(shù)據(jù)

本文所提算法的實現(xiàn)平臺為Anaconda3-5.2.0-Windows-x86_64，實驗所用計算機硬件配置為：Intel Core i5-4200U CPU@1.60GHz，內(nèi)存：4.00GB（3.75GB可用）。為了證明本文算法的分割性能，與K-means算法和標準粒子群優(yōu)化K-means的PSOK算法進行圖像分割對比實驗。本文算法實驗參數(shù)設置如下：

（1）在三個算法中K-means算法部分，令初始聚類中心數(shù)量為k=3；

（2）在 PSOK 算法中，令 c1=c2=2.0，w=0.8；

（3）在本文算法中，令c1=c2=2.0。

三種不同算法圖像分割結(jié)果如圖3所示，后文將從定性分析和定量分析兩個方面進行圖像分割效果研究分析。

3.2 定性分析

觀察圖2可知，相較于K-means算法和PSOK算法，在以圖像中的動物為目標進行分割時本文算法在保留細節(jié)的基礎上可以獲得更優(yōu)的圖像分割效果，在相同區(qū)域輪廓完整，邊緣清晰，總體分割效果更令人滿意。因此，本文算法分割性能要優(yōu)于K-means算法和PSOK算法。

圖2 三種不同算法圖像分割效果圖

3.3 定量分析

本文算法在圖像分割上性能優(yōu)于標準粒子群優(yōu)化K-means的PSOK算法的原因，除了本文算法引入了雙邊濾波對目標圖像進行降噪預處理之外，最主要的原因是本文算法對慣性系數(shù)進行動態(tài)調(diào)整之后，粒子群優(yōu)化算法的全局優(yōu)化性能大大提升。本文選取了Sphere函數(shù)和Griewank函數(shù)兩種標準測試函數(shù)對本文使用的粒子群優(yōu)化算法和標準粒子群優(yōu)化算法進行比較。參數(shù)設置如表1所示。

表1 標準測試函數(shù)參數(shù)設置

使用上述兩種標準函數(shù)對本文算法使用的粒子群優(yōu)化算法與標準粒子群優(yōu)化算法的迭代結(jié)果如圖3所示。

圖3 標準測試函數(shù)迭代過程

圖3中，DPSO代表本文改進的動態(tài)粒子群優(yōu)化算法，PSO代表傳統(tǒng)標準粒子群優(yōu)化算法。從圖3（a）中可以看出，對于Sphere函數(shù)，兩種算法均能非?？焖俚厥諗恐磷顑?yōu)解，差異非常小，但本文改進的動態(tài)粒子群優(yōu)化算法仍然更快速的收斂至最優(yōu)解。從圖3（b）中可以看出，對于Griewank函數(shù)，雖然兩種算法最后均收斂至全局最優(yōu)解，然而標準粒子群優(yōu)化算法在中途有陷入局部最優(yōu)解的趨勢，明顯動態(tài)粒子群優(yōu)化算法更快更穩(wěn)定。因而，采用本文動態(tài)粒子群優(yōu)化算法在圖像分割中實現(xiàn)了預期效果。

4 結(jié)語

本文提出了一種改進的結(jié)合動態(tài)粒子群優(yōu)化與K-means聚類的混合算法來進行圖像分割，該算法通過引入雙邊濾波在最大限度保留邊緣信息的情況下對圖像進行降噪預處理，再通過動態(tài)調(diào)整慣性系數(shù)達到提高粒子群算法優(yōu)化能力的目的，從而使該算法在圖像分割整體上獲得優(yōu)異的效果。實驗結(jié)果表明，本文算法結(jié)合了K-means算法快速收斂的特點和PSO全局搜索的能力，且相對于標準粒子群優(yōu)化K-means的PSOK算法獲得更好的分割效果和更高的分割效率。但是，對于PSO算法中慣性系數(shù)的動態(tài)調(diào)整只是隨機產(chǎn)生，自適應程度不足，在后續(xù)研究中將繼續(xù)對慣性系數(shù)和學習因子的動態(tài)調(diào)整進行自適應的改進，使其更好的分割圖像。