楊雨航

（重慶師范大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶401331）

0 引言

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

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

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

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

1 相關(guān)理論

1.1 K-means算法

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

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

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

1.2 標(biāo)準(zhǔn)粒子群算法

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

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

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

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

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

2.1 平滑濾波

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

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

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

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

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

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

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

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

式中，favg表示粒子的平均適應(yīng)度，計(jì)算公式如下：

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

本文算法流程如下：

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

Step2.計(jì)算每個(gè)粒子適應(yīng)度；

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

Step4.計(jì)算適應(yīng)度方差；

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

3.2 定性分析

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

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

3.3 定量分析

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

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)參數(shù)設(shè)置

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

圖3 標(biāo)準(zhǔn)測(cè)試函數(shù)迭代過(guò)程

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

4 結(jié)語(yǔ)

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