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

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

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

中圖分類號(hào)：TP391.4? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

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

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

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

1.1? 粒子群算法（PSO）

算法原理：

假設(shè)在D維的目標(biāo)搜索空間中，有N個(gè)粒子組成一個(gè)群落，其中第i個(gè)粒子表示為：

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

第i個(gè)粒子的速度記為：

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

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

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

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

gbest=（Pg1，Pg2，…，PgD）

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

，

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

1.2? K-means聚類算法

1.2.1? 算法思想

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

1.2.2? 歐氏距離

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

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

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

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

d（xi，xj）=[2]。

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

1.3.1? 算法原理

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

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

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

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

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

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

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

gbest=（Pg1，Pg2，…，PgD）

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

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

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

2? 模型檢驗(yàn)

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

三種算法模型的運(yùn)行時(shí)間（單位：ms），K-Means（58），PSO（91），PSO-KMeans（33）。

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

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

3? PSO-KMeans快速分割算法模型圖像分割應(yīng)用

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

進(jìn)一步檢驗(yàn)本文所建立的基于PSO-KMeans快速分割算法模型的有效性和精準(zhǔn)性。

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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