梁 軍，洪澤泓，余松森

（華南師范大學 軟件學院，廣東 佛山 528225）

0 引言

圖像分割技術(shù)是圖像處理中重要的環(huán)節(jié)，也是圖像分析的預處理步驟之一。圖像分割主要是根據(jù)原始圖像的亮度、顏色或者圖內(nèi)紋路等信息將圖片中不同的區(qū)域分開，以便根據(jù)具體需求去除不重要的部分和取出需要的部分，它被廣泛應用于醫(yī)藥、農(nóng)業(yè)、工業(yè)生產(chǎn)等各個領(lǐng)域［1］。目前，基于灰色圖像的分割已十分成熟，但彩色圖像的分割效率較低且精度不高，仍需進一步研究［2］。

聚類算法是圖像分割的常用方法之一［3-4］。早期，Comaniciu 等［5-7］將Mean Shift 應用于圖像平滑、分割和視頻跟蹤等領(lǐng)域，反復迭代計算當前點的偏移均值，最后經(jīng)過多次移動直至滿足條件；但Mean Shift 也存在很多缺點，比如分割效果時間復雜度較高、圖像分塊數(shù)量不可控。為了降低該算法的時間復雜度，Sheikh 等［8］提出了Medoid Shift 算法，它每次迭代會計算出新的中心點，而不是新的位置。后來，Vedaldi 等［9］對Medoid Shift 算法作出改進，使每個點移動到梯度增加的最近的點，稱為Quick shift；但是Quick shift 算法并不是一種迭代的算法，因此不能有效控制聚類的數(shù)量以及大小。隨著深度學習技術(shù)的發(fā)展，受到深度網(wǎng)絡(luò)中Dropout技術(shù)的啟發(fā)，張琦等［10］提出了稀疏聚類的方法，但是目前仍應用于像素點較少的圖片數(shù)據(jù)集中。k均值（k-means）算法簡單易用，但對聚類中心數(shù)量和其初始化位置有較大依賴。

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是Kennedy 等提出的一種的啟發(fā)式算法，它具有良好的全局搜索能力［11］。將PSO 和k-means 聚類算法結(jié)合能很好地克服k-means 本身算法的局限性，例如：Chan 等［11］將PSO 算法與SOM（Self-Organizing Map）結(jié)合的混合算法對k-means 進行優(yōu)化，選出最有價值的客戶并針對有價值客戶提出合理的營銷策略；Wang 等［12］將PSO 算法結(jié)合k-means 應用于網(wǎng)絡(luò)安全領(lǐng)域，對用戶行為進行聚類分析和有效識別風險賬戶；He 等［13］將PSO 算法結(jié)合k-means 應用于礦產(chǎn)資源承載能力的評估；Ibrahim 等［14］使用聚類算法預測電力公司的用戶行為，結(jié)合PSO 算法可達到更優(yōu)的效果，使公司利潤最大化；Tao 等［15］提出了一種基于適應度峰值聚類的動態(tài)多群粒子群算法和增強學習策略；Zhang 等［16］將PSO 算法與k-means 結(jié)合并 在YCbcr 顏色空間下對農(nóng)產(chǎn)品進行語義分割。

PSO 算法結(jié)合k-means 應用于各領(lǐng)域都可達到較好的效果，但大部分算法忽視了PSO本身的局限性，即PSO算法容易陷入局部最優(yōu)。結(jié)合不同的優(yōu)化算法的優(yōu)勢可以實現(xiàn)對PSO算法本身的改進，例如高兵等［17］結(jié)合麻雀搜索算法的大范圍搜索與PSO算法的快速收斂的特點提出網(wǎng)絡(luò)入侵檢測算法。本文不僅將PSO算法與k-means相結(jié)合應用到圖像分割領(lǐng)域，還對PSO算法進行了一定改進，增加了遺傳算法的變異機制，提高了算法性能和穩(wěn)定性。本文提出了一種基于改進粒子群優(yōu)化算法和遺傳變異的圖像分割模型PSOM-K（Particle Swarm Optimization Mutations-K-means），主要工作如下：

1）針對標準PSO 容易陷入局部最優(yōu)的問題，對PSO 公式進行改進，增加隨機鄰居粒子位置對其自身位置的影響，提高其全局搜索能力。

2）將改進的PSO 與遺傳變異（對每次優(yōu)化后的位置按一定概率對其中一位進行變異）相結(jié)合，提高模型的泛化能力。

3）對紅（Red，R）、綠（Green，G）、藍（Blue，B）三通道的聚類中心的值（非位置）分別進行初始化且不需要確定它們聚類中心的具體位置（對于R 通道，像素點值與哪個聚類中心值接近，就屬于哪一類，G 和B 通道類似）。

1 相關(guān)工作

1.1 標準PSO算法

粒子群算法是一種仿生算法，通過模擬飛鳥的行為尋找最優(yōu)解。它的本質(zhì)是通過算法將個體信息和社會信息聯(lián)合起來，從而使無序的群體慢慢收斂于最優(yōu)粒子周圍。每個粒子的位置代表一種解決方案（即一種解）。在整個尋優(yōu)的過程中，每個粒子會根據(jù)式（1）（2）來更新自己的速度和位置：

其中：i表示微粒i；j表示微粒的第j維；表示第代；c1和c2為加速常量，通常在（0，2）上取值；w為慣性權(quán)重因子；r1和r2為（0，1）上兩個相互獨立的隨機函數(shù)。假設(shè)d表示解空間的維度，那么xi=(xi1，xi2，…，xid)為 第i個粒子的位置，vi=(vi1，vi2，…，vid)為第i個粒子飛行的速度，pi=(pi1，pi2，…，pid)為第i個粒子的個體歷史最優(yōu)位置，gi=(gi1，gi2，…，gid)為全局歷史最優(yōu)位置。

1.2 圖像的聚類分割算法

假設(shè)需將一張灰色圖像分割成k個部分。那么，任意一個像素點與第i個聚類中心Ci(1 ≤i≤k)之間的距離為：

其中t為像素點的值。

令Ti={ti1，ti2，…，timi}(1 ≤i≤k)表示圖像第i個部分的像素點的集合，mi表示第i個部分的像素點的總數(shù)。那么，該像素點集合Ti的質(zhì)心點值Xi為：

k-means 對灰色圖像分割的算法如算法1。針對彩色圖像，可分別對R、G、B 通道用算法1 完成分割，然后再合并成彩色圖像。

算法1 灰色圖像分割算法。

輸入 一張灰色圖像、圖像分割數(shù)量k，迭代次數(shù)m和閾值σ；

輸出 分成k個部分的灰色圖像。

步驟1 隨機設(shè)置k個像素點的值為聚類中心。

步驟2 按式（3）計算每個像素點與k個聚類中心的距離，并將每個點劃分為與之最近的聚類中心點的類別。

步驟3 按式（4）更新聚類中心。

步驟4 當?shù)螖?shù)小于m或前后聚類中心值的距離大于σ，循環(huán)步驟2～3；否則跳到步驟5。

步驟5 已確定k個聚類中心，按式（3）計算每個像素點和k個聚類中心的距離，并將該像素點的值變更為與之最近的聚類中心點的值。

步驟6 將這張灰色圖像分割成k個部分。

1.3 圖像分割評價指標及適應度函數(shù)

圖像分割質(zhì)量通常可通過均方誤差（Mean-Square Error，MSE）、峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）、結(jié)構(gòu)相似性（Structural Similarity Index Measure，SSIM）、特征相似性（Feature Similarity Index Measure，F(xiàn)SIM）和FSIMc（Feature Similarity Index Measure color）［18］進行評估。這些指標在圖像分割、超分辨率以及圖像去模糊等領(lǐng)域應用廣泛。FSIM 是SSIM 較成功的變種，可用于對灰色和彩色圖像分割質(zhì)量的評估。FSIMc相較于FSIM，更有利于評價彩色圖像，它對一張圖片中的所有像素點賦予不同的重要性，如沿著圖片中央物體邊緣的像素點相較于其他背景像素點，肯定更能界定物體的結(jié)構(gòu)。但采用FSIMc 指標的文獻較少，大部分文獻還是用PSNR 和FSIM 作為評價彩色圖像的指標，因此本文只是將FSIMc 指標作為粒子群優(yōu)化中的適應度函數(shù)，在圖像分割的最終評價指標上仍采用PSNR和FSIM。

1.3.1 圖像分割評價指標

1）PSNR指標。

其中：x、y分別表示原圖及圖像分割后的圖片；M、N分別表示輸入圖片的橫向和縱向長度。PSNR 的值越大，說明圖像分割質(zhì)量越好。

2）FSIM指標。

假設(shè)PC1(x)和PC2(x)分別表示原圖與分割后的圖片的相位一致性特征（詳細公式見文獻［18］）。PCm(x)=max{PC1(x)，PC2(x)}，取值在［0，1］。通過Sobel、Prewitt 和Scharr 算子結(jié)合，可以分別從橫向和縱向計算圖片的梯度特征Gx與Gy，并得到單幅圖片的梯度特征為G=假設(shè)原圖與分割后的圖片的梯度特征為G1與G2，結(jié)合PC1(x)與PC2(x)可以計算出SL(x)。FSIM 的取值為［0，1］，F(xiàn)SIM 越接近1，表示圖像分割的效果越好。FSIM 可將圖片轉(zhuǎn)為YIQ顏色空間，然后改成圖像分割指標FSIMc。

3）FSIMc指標。

先將圖片由RGB 顏色空間轉(zhuǎn)換成YIQ 顏色空間，然后利用Y 通道計算SL(x)與PCm(x)，計算方法與上述FSIM 方法相同。再根據(jù)YIQ 中的I、Q 通道，計算兩幅圖片的色度相似度SI(x)與SQ(x)，即得到SC(x)=SI(x) ·SQ(x)。FSIMc的取值也為［0，1］。

1.3.2 適應度函數(shù)

假設(shè)向量X、Y、Z分別代表R、G、B 三通道的k個聚類中心，即 ：X={x1，x2，…，xk}，Y={y1，y2，…，yk}、Z={z1，z2，…，zk}(0 ≤xi，yi，zi≤255，1 ≤i≤k)。定義每個粒子的位置為{x1，x2，…，xk，y1，y2，…，yk，z1，z2，…，zk}。

計算單個粒子的適應度函數(shù)值，如算法2 所示。

算法2 適應度函數(shù)值計算。

步驟1 對于R 通道的二維矩陣的任意一個像素點x′，計算x′與其聚類中心{x1，x2，…，xk}中哪一個類中心xi(1 ≤i≤k) 最近，則該像素點屬于那一類并更新x′。即x′=

步驟2 對G、B 通道做和R 通道相類似的操作。

步驟3 利用式（8）計算粒子對應的FSIMc 值，即適應度函數(shù)值。

2 PSOM-K

2.1 改進的PSO算法

將標準PSO 算法用于k-means 圖像分割領(lǐng)域易陷入局部最優(yōu)且全局視野不夠，因此本文對標準PSO 公式進行了改進，增加了當代隨機鄰居粒子位置對其自身的影響。通過增強粒子的社會性增加它的全局搜索解的能力。

更新后的公式為：

其中：sk=(sk1，sk2，…，skd)為當代隨機鄰居粒子k的位置，其余參數(shù)與式（1）（2）類似。

同時，每次更新完位置，將三通道的位置轉(zhuǎn)換成二進制表示，三通道的位置各有0.05 的概率產(chǎn)生變異，將其中的一位變成相反的數(shù)字，防止陷入局部最優(yōu)。

2.2 遺傳變異操作

本文增加遺傳變異操作的目的也是為了使模型不易陷入局部最優(yōu)。在每次用式（9）（10）對粒子的位置更新后，然后以β的概率確定其是否變異。首先將每個粒子更新后的位置拆分成R、G、B 三通道的聚類中心。

針對R 通道，按β概率確定其聚類中心值{x1，x2，…，xk}是否變異。如變異，則先將所有k個值都轉(zhuǎn)變?yōu)槎M制。然后對每一個二進制數(shù)，隨機選取一位進行變異，即0-1 變換（0 變?yōu)? 和1 變?yōu)?）。

對G 和B 通道做類似的操作。最后將R、G、B 三通道的聚類中心按1.3.2 節(jié)方式合成該粒子的位置。

2.3 PSOM-K

本文提出了一種基于改進粒子群優(yōu)化算法和遺傳變異的圖像分割模型PSOM-K。PSOM-K 將改進PSO 和遺傳變異操作相結(jié)合對聚類中心進行初始化，最后運用k-means 對圖像分割。PSOM-K 的圖像分割流程如算法3 所示。

算法3 圖像分割模型PSOM-K。

輸入 一張彩色圖像、圖像分割數(shù)量k，粒子數(shù)N，粒子群優(yōu)化迭代數(shù)Num和變異概率β（一張彩色圖像可看成R、G、B 三通道的合成，每個通道是一個二維矩陣，取值范圍為0～255）；

輸出 圖像分割后的彩色圖像。

步驟1 對N個粒子的位置（即N個解決方案）進行隨機初始化，即對每個粒子代表的R、G、B 三通道的聚類中心進行隨機初始化。

步驟2 根據(jù)算法2 計算N個粒子的適應度函數(shù)值（即FSIMc 值），更新粒子群的全局最優(yōu)位置和每個粒子的歷史最優(yōu)位置。

步驟3 用改進的粒子群優(yōu)化公式，即式（9）（10），對N個粒子的位置進行更新。

步驟4 根據(jù)第2.2 節(jié)，對每個粒子的位置進行遺傳變異操作。

步驟5 當?shù)螖?shù)不小于Num時，重復步驟2～4；否則跳到步驟6。

步驟6 根據(jù)第1.3.2 節(jié)，可將全局歷史最優(yōu)粒子的位置拆分成R、G、B 三個通道的聚類中心的初始值（每個通道k個聚類中心）。用算法1 的步驟2～6 分別對R、G、B 三通道的聚類中心進行更新。

步驟7 合并R、G、B 三通道，輸出這張彩色圖像的分割結(jié)果。

在PSOM-K 中，由于不同的彩色圖像擁有不同的色彩分布，從R、G、B 三通道分別用PSO 對其聚類中心進行優(yōu)化，得到較合理的聚類中心；同時，結(jié)合遺傳算法的變異操作，提高模型的泛化性；另外，從R、G、B 三通道分別聚類，提升彩色圖像分割的效果。

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

本文使用Matlab R2019b作為開發(fā)工具。實驗參數(shù)設(shè)置如下：粒子數(shù)N=10，粒子群優(yōu)化迭代數(shù)Num=10，加速常量c1=0.1，c2=0.8，c3=0.1，變異概率β=0.05，聚類中心數(shù)量k∈｛4，6，8，10｝。本文取3次實驗的平均值作為評估結(jié)果。

3.1 數(shù)據(jù)集

本文選用伯克利大學分割數(shù)據(jù)集（BSDS500）［19］中的21張圖像做實驗，其中一部分選擇的圖像是為了與相關(guān)文獻作對比，其他的圖像是隨機抽取的。這21 張圖像如圖1 所示。

圖1 伯克利大學分割數(shù)據(jù)集的圖像（481×321或321×481）Fig.1 Images（481×321 or 321×481）from Berkeley segmentation dataset

3.2 性能比較

針對不同的應用，圖像分割可分為粗粒度圖像分割和細粒度圖像分割。本文擬對聚類中心數(shù)量k進行有差別的設(shè)置，使得算法能適用于不同的圖像分割級別。本文擬劃分k≤10（粗粒度）和k≥40（細粒度）這兩個類別作測試。

3.2.1 粗粒度圖像分割對比

令聚類中心數(shù)量k=4、6、8、10，本文將PSOM-K 與CEFO（Chaotic Electromagnetic Field Optimization）［20］和WOA-DE（Whale Optimization Algorithm-Differential Evolution）［21］等算法對比性能。因此，本文選用了文獻［20］和［21］中的6 張圖像在圖像分割指標PSNR和FSIM上進行對比，結(jié)果如表1所示。

圖像分割指標PSNR 和FSIM 越大越好，從表1 可以看出，與CEFO［20］和WOA-DE［21］相比，本文PSOM-K 模型在這6張圖片上的圖像分割指標PSNR 和FSIM 上都能達到最好效果。例如：當k=4 時，相對于CEFO［20］，PSOM-K 在圖1（e）（g）（h）上FSIM 分別提高了9.97%、12.69%、7.70%；相較于WOA-DE［21］，PSOM-K 在圖1（j）（k）（l）上FSIM 分別提高了15.57%、5.05%、19.02%。當k=10 時，相對于CEFO［20］，PSOM-K 在圖1（e）（g）（h）上PSNR 分別提高了29.92%、30.43%、30.77%；相較于 WOA-DE［21］，PSOM-K 在圖1（j）（k）（l）上PSNR 分別提高了0.87%、14.93% 和14.62%。在k=4 的時候FSIM指標與CEFO［20］相比提 升 了7.7%～12.69%，與WOA-DE［21］相比提升了5.05%～19.02%。因此，本文PSOM-K 模型用將改進PSO 和遺傳變異結(jié)合后的策略應用于k-means 的聚類中心位置的初始化是非常有效的。

圖2 展示了部分圖像在CEFO 和PSOM-K 上的分割效果。從主觀感受對圖2 進行評價：采用CEFO 的整體圖像亮度偏暗，顏色稍微失衡，整體的色彩傾向灰度，如：圖2（d）在較低閾值的時候，可以看出顏色明顯偏離原圖；圖2（b）的其他圖片也有著肉眼可見的偏藍色調(diào)。PSOM-K 產(chǎn)生的分割效果更加接近真實圖片，而且在圖片的細節(jié)展示中更加細膩，本文模型相較于CEFO 更加符合真實情況。

3.2.2 細粒度圖像分割對比

令聚類中心數(shù)量k=40、50、60、70，將PSOM-K 與和HWOA（Hybrid Whale Optimization Algorithm）［22］對比性能。表2 表明，相較于HWOA［22］，PSOM-K 在FSIM 指標上稍有下降，但在PSNR 指標上有很明顯的提升。例如：在圖（s）上，當k=40 時，PSOM-K 相對于HWOA，F(xiàn)SIM下降了0.11%，但PSNR 提升了8.41%；在其他情況，與細粒度分割算法HWOA相比，在k=40 時，PSOM-K 在FSIM 指標最多下降0.45%，但PSNR 指標提升7.59%～13.58%。由于PSNR 指標主要從圖片噪聲方面評價圖片質(zhì)量，而FSIM 指標對圖片的評價，更多集中于圖像的特征相似性。PSOM-K 在PSNR 指標上提升較多，說明本文模型對于噪聲的處理更有優(yōu)勢；PSOM-K 在FSIM 指標上略有下降，說明本文模型因為對于整體噪聲優(yōu)化而忽視了一些局部特征。

表2 細粒度圖像分割的FSIM和PSNR對比Tab.2 Comparison of FSIM and PSNR of fine-grained image segmentation

3.3 消融實驗

為了測試PSOM-K 中改進策略的有效性，首先將標準粒子群優(yōu)化（Standard PSO）算法與k-means 的結(jié)合稱為“SPSO-K”，只增加鄰居粒子的改進PSO 算法與k-means 算法結(jié)合稱為“PSON-K”，然后對比k-means、SPSO-K、PSON-K 和PSOM-K 在指標FSIM 和PSNR 上的性能表現(xiàn)，如表3 所示。

表3 不同聚類中心數(shù)量的FSIM和PSNRTab.3 FSIM and PSNR for different numbers of cluster centers

表3 顯示出：使用標準PSO 算法對k-means 聚類中心的位置初始化（即SPSO-K）可以提高k-means 算法的性能，使用隨機鄰居粒子的PSON-K 可以提高SPSO-K 算法的性能，驗證的改進步驟的有效性；并且在增加了隨機鄰居粒子的基礎(chǔ)上增加遺傳變異機制的PSOM-K 能進一步提高PSON-K 算法的性能。在粒子群算法中，增加隨機鄰居粒子對自身位置的影響，提高了粒子的全局搜索能力，有利于尋找全局最優(yōu)解；而遺傳算法的變異機制提高了PSOM-K 的泛化能力，在模型中加入隨機變異，相當于增加了模型的噪聲擾動，訓練出來的模型更穩(wěn)定。

本文每個實驗做3 次，3 次實驗的標準差可反映算法的穩(wěn)定性。表3 展示了5 張圖片圖1（a）（b）（f）（c）（i）在FSIM和PSNR 指標上的標準差的平均值（k等于4、6、8、10 的標準差的平均值）。表4 表明了PSOM-K 模型在5 張圖片上的FSIM 值的標準差都比SPSO-K 與PSON-K ??；在PSNR 值的標準差上，除了圖片（f），其余都比SPSO-K 小。再對5 張圖片的標準差進一步平均，在FSIM 和PSNR 指標上，PSOM-K 的平均標準差分別為0.003 095 和0.146 069，而SPSO-K 的平均標準差分別為0.008 56 和0.308 604，PSON-K 的平均標準差分別為0.004 440 和0.223 173。PSOM-K 模型的平均標準差更小，說明PSOM-K 相對于SPSO-K 和PSON-K 更穩(wěn)定，進一步表明了隨機鄰居位置影響和遺傳變異這兩種改進策略的有效性。

表4 SPSO-K、PSON-K和PSOM-K在FSIM和PSNR上的標準差比較Tab.4 Standard deviation comparison of SPSO-K，PSON-K and PSOM-K in FSIM and PSNR

將SPSO-K、PSON-K 和PSOM-K 算法在圖1（a）上（k=4）進行圖像預分割的參數(shù)收斂測試，通過互不干擾的100次迭代尋優(yōu)結(jié)果如圖3 所示?？梢钥闯觯夯跇藴蔖SO 的SPSO-K 算法收斂速度較快，但是很快便陷入局部最優(yōu)；而只增加了隨機鄰居粒子的PSON-K 增加了全局搜索能力，獲得了較好的效果，但是對于陷入局部的問題仍然沒有解決；而增加了遺傳變異機制的PSOM-K算法則提升了算法的泛化能力，可以使算法通過不斷迭代獲得更好的效果。

圖3 圖像預分割優(yōu)化效果Fig.3 Image pre-segmentation optimization effect

4 結(jié)語

針對k-means 算法聚類中心位置對其性能有較大影響的問題，本文提出了PSOM-K 模型對粒子群算法進行了改進，并結(jié)合了遺傳算法的變異操作，同時采用了FSIMc 作為適應度函數(shù)，最后應用RGB 顏色空間的三通道獨立聚類的方式對彩色圖像進行分割。在伯克利分割數(shù)據(jù)集上的實驗結(jié)果表明：隨機鄰居位置影響、遺傳變異及三通道獨立聚類這三種策略提高了k-means 算法的分割性能及其穩(wěn)定性。因為PSOM-K 應用了復雜度較高的聚類中心位置的初始化方法，所以它的運行時間相對于k-means 較長。PSOM-K 模型可被應用于圖像預處理、圖像壓縮等方面。在未來的工作中，可嘗試將這三種改進策略應用于不同的算法（例如Hierarchical clusting、Bayesian clustering、evolution-based clusting 等）來提高圖像分割的效果。