動態粒子群優化K-means的圖像分割算法研究

楊雨航

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

0 引言

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

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

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

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

1 相關理論

1.1 K-means算法

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

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

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

1.2 標準粒子群算法

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

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

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

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

2 改進的動態PSO優化K-means的圖像分割算法

2.1 平滑濾波

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

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

圖1 平滑濾波結果對比

2.2 動態慣性系數

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

2.3 動態PSO優化K-means算法

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

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

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

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

本文算法流程如下：

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

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

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

Step4.計算適應度方差；

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

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

Step7.計算數據點到聚類中心距離；

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

3 實驗結果及分析

3.1 實驗環境及實驗數據

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

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

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

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

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

3.2 定性分析

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

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

3.3 定量分析

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

表1 標準測試函數參數設置

使用上述兩種標準函數對本文算法使用的粒子群優化算法與標準粒子群優化算法的迭代結果如圖3所示。

圖3 標準測試函數迭代過程

圖3中，DPSO代表本文改進的動態粒子群優化算法，PSO代表傳統標準粒子群優化算法。從圖3（a）中可以看出，對于Sphere函數，兩種算法均能非常快速地收斂至最優解，差異非常小，但本文改進的動態粒子群優化算法仍然更快速的收斂至最優解。從圖3（b）中可以看出，對于Griewank函數，雖然兩種算法最后均收斂至全局最優解，然而標準粒子群優化算法在中途有陷入局部最優解的趨勢，明顯動態粒子群優化算法更快更穩定。因而，采用本文動態粒子群優化算法在圖像分割中實現了預期效果。

4 結語

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