基于PSO-KMeans快速圖像分割算法模型的應用

陳興志　王代文　劉乃瑤　樂文濤　黃飛翔

摘? 要：圖像分割是圖像識別和計算機視覺至關(guān)重要的預處理。文章結(jié)合PSO算法搜索全局最優(yōu)及KMeans算法對選取初始聚類中心的缺陷，使用PSO算法搜索并尋找全局最優(yōu)，將搜尋值回代到KMeans聚類算法中對圖像進行分割。結(jié)果表明，基于PSO-KMeans快速圖像分割算法模型具有更高的精確度和有效性。PSO算法對KMeans算法的優(yōu)化作用明顯，有效對圖片數(shù)據(jù)進行了分割，進一步優(yōu)化了KMeans算法對圖像分割的時間，提高了算法收斂的速度。

關(guān)鍵詞：PSO算法;KMeans算法;PSO-KMeans快速算法;收斂速度;圖像分割

中圖分類號：TP391.4? ? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）05-0079-04

Application of Fast Image Segmentation Algorithm Model

Based on PSO-KMeans

CHEN Xingzhi，WANG Daiwen，LIU Naiyao，LE Wentao，HUANG Feixiang

（School of Science，Southwest University of Science and Technology，Mianyang? 621010，China）

Abstract：Image segmentation is an important preprocessing of image recognition and computer vision. In this paper，PSO algorithm is used to search the global optimum and KMeans algorithm is used to select the initial cluster center. PSO algorithm is used to search and find the global optimum，and the search value is replaced by KMeans clustering algorithm to segment the image. The results show that the fast image segmentation algorithm model based on PSO-KMeans has higher accuracy and effectiveness. PSO algorithm plays an important role in the optimization of KMeans algorithm，effectively segmenting the image data，further optimizing the time of image segmentation of KMeans algorithm，and improving the convergence speed of the algorithm.

Keywords：PSO algorithm;KMeans algorithm;PSO-KMeans fast algorithm;convergence speed;image segmentation

0? 引? 言

圖像分割是圖像識別和計算機視覺至關(guān)重要的預處理，在國內(nèi)外有著眾多相關(guān)圖像分割算法研究，但是目前仍未有一種能夠適用于絕大多數(shù)圖像通用的分割算法，當前國內(nèi)外對于圖像分割相關(guān)研究最常用的是聚類算法中的K均值算法，K均值算法需要先選擇K個初始類均值，之后將每個像素歸入均值離它最近的類，再重新計算出新的類均值，此后迭代執(zhí)行前面步驟，直到新類與舊類均值之差小于某一閾值。

本文研究內(nèi)容是西南科技大學大學生創(chuàng)業(yè)項目，目的是找到一種能夠適用于多數(shù)圖像的分割算法，該研究以PSO算法與K-Means算法為基礎，通過粒子群算法的方式，實現(xiàn)對復雜多線性多維度數(shù)據(jù)空間的有效計算，進而達到對圖像進行分割的目的，此類算法能夠應用于多數(shù)圖像的分割，極大縮短了圖像分割速度[1]。

1? 基于PSO-KMeans快速圖像分割算法模型的建立

1.1? 粒子群算法（PSO）

算法原理：

假設在D維的目標搜索空間中，有N個粒子組成一個群落，其中第i個粒子表示為：

Xi=（Xi1，Xi2，…，XiD），i=1，2，…，N

第i個粒子的速度記為：

Vi=（Vi1，Vi2，…ViD），i=1，2，…，N

第i個粒子搜索到的最優(yōu)位置稱為個體極值，記為：

Pbest=（Pi1，Pi2，…，PiD），i=1，2，…N

整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為：

gbest=（Pg1，Pg2，…，PgD）

在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式來更新自己的速度和位置：

，

其中，C1和C2和為學習因子，也稱加速常數(shù)，W為慣性因子，rand1和rand2為[0，1]范圍內(nèi)均勻隨機數(shù)。

1.2? K-means聚類算法

1.2.1? 算法思想

K-Means聚類算法是以K為參數(shù)，將N個對象分為K個簇，使簇內(nèi)有較高的相似度，簇間的相似度較低。相似度通常使用歐式距離表示。

1.2.2? 歐氏距離

設數(shù)據(jù)集：

X={Xm|m=1，2，3，…，total}，其中，X中的樣本用d個描述屬性的A1，A2，…，Ad來表示，并且d個描述屬性都是連續(xù)性屬性。

數(shù)據(jù)樣本Xi=（Xi1，Xi2，…，Xid），Xj=（Xj1，Xj2， …，Xjd），其中Xi1，Xi2，…，Xid和Xj1，Xj2，…，Xjd分別是樣本Xi和Xj對應d個描述屬性A1，A2，…，Ad的具體取值。

樣本Xi和Xj之間的歐氏距離d（xi，xj）為：

d（xi，xj）=[2]。

1.3? 基于PSO-KMeans快速圖像分割算法模型

1.3.1? 算法原理

設在D維的像素矩陣搜索空間中，有N個像素矩陣元素組成一個群落，其中第i個像素矩陣元素表示為D維的向量：

Xi=（Xi1，Xi2，…，XiD），i=1，2，…，N

第i個像素矩陣元素的“飛行”速度也是D維的向量，記為：

Vi=（Vi1，Vi2，…，ViD），i=1，2，…N

第i個像素矩陣元素迄今為止搜索到的最優(yōu)位置稱為個體極值，記為：

Pbest=（Pi1，Pi2，…，PiD），i=1，2，…，N

整個像素矩陣群迄今為止搜索到的最優(yōu)位置為全局極值，記為：

gbest=（Pg1，Pg2，…，PgD）

在找到這兩個最優(yōu)值時，像素矩陣元素根據(jù)如下的公式來更新自己的速度和位置：

通過PSO算法將N個對象分為K個簇，并將其通過迄今為止搜索得到的最優(yōu)值回代到K-Means算法中作為初始聚類分割中心和初始分割類K，K-Means算法是以K為參數(shù)對圖像進行分割，使簇內(nèi)相似度較高，簇間較低。相似度用歐式距離表示。

PSO-KMeans快速圖像分割模型算法原理：開始導入原始圖像，圖像灰度化處理，獲取圖像像素矩陣，初始化每個像素矩陣元素的速度和位置，計算每個像素矩陣元素的適應值，求出像素矩陣每個元素的個體最優(yōu)，求解出整個像素矩陣的全局最優(yōu)質(zhì)，根據(jù)方程對元素粒子的速度進行優(yōu)化，根據(jù)方程對元素粒子的位置進行優(yōu)化，不滿足條件則重新優(yōu)化粒子速度與位置，滿足相關(guān)條件則輸出分割中心和分割個數(shù)K，分配各個數(shù)據(jù)到距離最近的分割中心，重新計算各個分割中心，不收斂則重新分配距離最近的分割中心，收斂則輸出分割結(jié)果。

2? 模型檢驗

通過PSO算法、K-Means算法、PSO-KMeans算法，分別對圖像進行分割，檢驗基于PSO-KMeans快速圖像分割算法模型的有效性和精準性。得到K-Means算法模型和PSO-KMeans快速分割算法模型的分割參數(shù)對比，如表1所示。

三種算法模型的運行時間（單位：ms），K-Means（58），PSO（91），PSO-KMeans（33）。

將K-Means算法模型和PSO-KMeans快速分割算法模型的迭代次數(shù)與目標函數(shù)值收斂關(guān)系進行比較，如圖1所示。

由圖中和分割結(jié)果數(shù)據(jù)來看，PSO-KMeans快速分割算法模型能夠有效地對原始“l(fā)ena.jpg”圖像進行分割，分割的時間有較大的提升。K-Means算法運行耗時58 ms，PSO-KMeans算法運行耗時33 s。且算法實現(xiàn)了更快的收斂，K-Means算法收斂迭代7次，而PSO-KMeans算法收斂只迭代2次。

3? PSO-KMeans快速分割算法模型圖像分割應用

針對圖像分割應用可參考原始未分割圖像“Jobs.jpg”，如圖2所示，將基于PSO-KMeans快速分割算法模型圖像分割方法應用到該圖像的分割上，得到結(jié)果如圖3所示。K-Means聚類算法模型無法對圖像進行準確的分割。

進一步檢驗本文所建立的基于PSO-KMeans快速分割算法模型的有效性和精準性。

通過對比兩種算法模型所能分割的圖像像素矩陣大小，256×256圖像兩者算法都可運行，574×450圖像K-Means不可運行，PSO-KMeans可運行。

得到基于PSO-KMeans快速分割算法模型的迭代次數(shù)與目標函數(shù)值收斂對比，如表2所示。

整理基于PSO-KMeans快速分割算法模型的迭代次數(shù)與目標函數(shù)值收斂關(guān)系，如圖4所示。

由圖4、表1、表2可知，PSO-KMeans快速分割算法模型能夠有效地對原始“Jobs.jpg”圖像進行分割，可以分割像素矩陣更大的圖像，并且算法收斂到最優(yōu)只迭代4次。

4? 結(jié)? 論

本文利用建立的基于PSO-KMeans圖像分割組合算法模型對圖片進行分割處理，并對其進行了結(jié)果分析，總結(jié)如下：通過檢驗數(shù)據(jù)和收斂比較圖可知，基于PSO-KMeans圖像分割組合算法模型的分割效果明顯，算法模型的收斂速度快、收斂次數(shù)小，算法模型的運行時間也更快;由圖像分割應用，基于PSO-KMeans圖像分割組合算法模型精準地實現(xiàn)了對圖像的分割?？梢苑指钕袼鼐仃嚫蟮膱D像，并且只經(jīng)過了4次迭代目標函數(shù)就收斂到了最優(yōu);基于PSO-KMeans快速分割算法模型解決了K-Means聚類算法具有初值選取不穩(wěn)定、需要提前給出K值等缺點。分割的圖像大小也更大，并且分割的效果和分割速度更快。

參考文獻：

[1] 孫越泓.基于粒子群優(yōu)化算法的圖像分割研究 [D].南京：南京理工大學，2010.

[2] 楚曉麗.K-Means聚類算法和人工魚群算法應用于圖像分割技術(shù) [J].計算機系統(tǒng)應用，2013，22（4）：92-94+103.

作者簡介：陳興志（1997.11-），男，漢族，云南昆明人，

本科，研究方向：應用數(shù)學;王代文（1999.05-），男，漢族，四川綿陽人，本科，研究方向：應用數(shù)學;劉乃瑤（1998.08-），女，漢族，吉林長春人，本科，研究方向：計算數(shù)學;樂文濤（1998.12-），男，漢族，四川南充人，本科，研究方向：計算數(shù)學;黃飛翔（1998.09-），男，彝族，云南昆明人，本科，研究方向：應用數(shù)學。