王甜甜 ，史衛(wèi)亞

（1 河南工業(yè)大學(xué)信息科學(xué)與工程技術(shù)學(xué)院 河南 鄭州 450001）

（2 河南工業(yè)大學(xué)人工智能與大數(shù)據(jù)學(xué)院 河南 鄭州 450001）

（3 河南工業(yè)大學(xué)糧食信息處理與控制教育部重點實驗室 河南 鄭州 450001）

0 引言

K-means作為一種經(jīng)典的基于劃分的聚類算法，它具有操作簡單、效率高、局部搜索性能好等優(yōu)勢[1]。但是傳統(tǒng)的K-means算法也存在很多的問題：（1）K值需要預(yù)先確定，但在實際中K值的選定是非常困難的；（2）K-means算法中相似度是以歐氏距離來度量的，因此遠(yuǎn)離群點的存在對算法結(jié)果影響較大[2]。針對這些問題，文獻(xiàn)[3]采用灰度梯度最大熵法從圖像中提取特征，再用K-means對圖像進(jìn)行分類，達(dá)到了很好的圖像分割效果；文獻(xiàn)[4]利用遺傳算法尋得K值，該算法在降低迭代次數(shù)的同時提高了準(zhǔn)確率。在分析已有的K-means改進(jìn)算法的基礎(chǔ)上，使用LBP算子提取圖像的紋理特征，再使用遺傳算法和K-means算法結(jié)合的方法對圖像進(jìn)行聚類。將本文算法與FCM和經(jīng)典K-means算法進(jìn)行對比實驗。實驗結(jié)果表明，改進(jìn)后的K-means算法的聚類效果優(yōu)于經(jīng)典K-means算法。

1 LBP特征提取

局部二值模式[5]（local binary pattern,LBP）是一種圖像紋理提取算法。本文通過LBP算子實現(xiàn)圖像特征提取的步驟如下：

（1）細(xì)分區(qū)域；

（2）將每個區(qū)域中心點的灰度值作為閾值，并與周圍的8個像素進(jìn)行比較。若周圍像素值較大，則被標(biāo)記為1；否則為0；

（3）計算每個區(qū)域的直方圖，并進(jìn)行歸一化處理。

（4）將步驟（3）得到的所有直方圖連接成為一個特征向量，即整幅圖的LBP紋理特征向量。LBP值計算如式（1）所示。

其中，(xc,yc)表示3*3鄰域的中心元素；ic表示中心像素值，ip表示鄰域像素值，S(ip-ic)是符號函數(shù)，即：

2 遺傳算法

遺傳算法（genetic algorithm，GA）是一種模仿大自然進(jìn)化規(guī)律（適者生存，不適者淘汰）的算法。該算法的構(gòu)成要素包括編碼、初始化種群、遺傳算子（如交叉、變異）、選擇策略和停止策略[6]。首先根據(jù)實際問題選擇合適的編碼方式，并根據(jù)問題規(guī)模確定種群的規(guī)模。然后根據(jù)問題設(shè)計對應(yīng)的適應(yīng)度函數(shù)，并設(shè)定終止條件。若滿足終止條件，則輸出結(jié)果；否則進(jìn)行選擇、交叉、變異運(yùn)算。上述流程如圖1所示。

圖1 遺傳算法流程圖

在遺傳算法的每個循環(huán)中，選擇、交叉和變異算子在尋優(yōu)過程中最為重要：

（1）選擇：選擇是將種群中的某些個體挑選出來用于繁衍下一代種群的新個體。

（2）交叉：兩個配對的染色體以設(shè)定的交叉概率對個體進(jìn)行交叉操作，其目的是通過交換二者的部分基因，不斷產(chǎn)生新的個體；

（3）變異：變異是允許每位個體以一個很小的概率改變自身。

3 基于遺傳算法的k-means 聚類

3.1 算法步驟

本文算法的基本步驟如下：

（1）為了方便后續(xù)步驟，將實驗所用的圖像統(tǒng)一尺寸為440*300，生成樣本集。

（2）使用LBP算法對樣本集進(jìn)行特征提取。

（3）使用遺傳算法找到最優(yōu)的K值。

（4）利用（3）中的K值，使用遺傳算法中的初始化找到最優(yōu)初始聚類中心。

（5）使用（3）（4）中的K值和初始聚類中心，對數(shù)據(jù)集進(jìn)行聚類操作。

（6）聚類結(jié)束。

3.2 實現(xiàn)步驟

本文采用基于聚類中心的浮點數(shù)編碼[7]，將類別中心點編碼為染色體。

類內(nèi)的距離[8]如式（3）所示。

其中，k代表類別的個數(shù)；mi代表第i類的樣本均值；代表第i類的第j個樣本；代表第i類的樣本個數(shù)。

類間的距離如式（4）所示。

其中，m代表全部樣本的均值向量。

適應(yīng)度函數(shù)定義如式（5）所示。平均類內(nèi)距離越小，類間距離越大，聚類效果越好，適應(yīng)度函數(shù)值越大[9]。

本文采用輪盤賭法[10]，使個體被選中的概率取決于其對應(yīng)的適應(yīng)度的大小，適應(yīng)度值越大，其參與后代繁殖的概率就越高。

4 實驗結(jié)果

本文算法的實驗環(huán)境為：Windows10操作系統(tǒng)、Python語言，系統(tǒng)的硬件環(huán)境為Inter(R) Core(TM)i5-7200U CPU 處理器。

本文使用了像素準(zhǔn)確率（pixel accuracy，PA）對圖像聚類效果進(jìn)行評估，PA用來計算被正確分類的像素個數(shù)和總像素數(shù)之間的比例，其計算公式如式（6）所示。

其中，k代表類別總數(shù)，pij代表真實像素類別為i的像素被預(yù)測為類別j的總數(shù)量；pii代表真實像素為i的像素被預(yù)測為類別i的總數(shù)量。

4.1 特征提取

本文首先對圖像的尺寸、顏色歸一化；然后采用LBP算法進(jìn)行特征提取，實驗結(jié)果如圖2所示。

圖2 特征提取圖

4.2 實驗結(jié)果及分析

本實驗將遺傳算子的交叉概率為0.3，變異概率為0.2，迭代次數(shù)為50。由遺傳算法的適應(yīng)度函數(shù)定義可知，適應(yīng)函數(shù)值越大，聚類效果越好。在分割3幅圖像時，迭代次數(shù)對應(yīng)的適應(yīng)度函數(shù)如圖3所示。從圖中可以看出，收斂代數(shù)均在30～40之間。

圖3 遺傳算法的收斂曲線

不同算法的分割結(jié)果如圖4所示，K-means對圖像邊緣的分割性能較差，無法精準(zhǔn)識別動物圖片的邊緣信息；FCM能夠識別邊緣信息，但是在細(xì)節(jié)分割方面效果較差；遺傳算法和K-means結(jié)合能進(jìn)一步完善對細(xì)節(jié)的分割性能，但是在紋理復(fù)雜的圖像中表現(xiàn)不如本文算法。方框中圈出的區(qū)域為本文算法優(yōu)于其他算法的區(qū)域。比較可得，本文算法在邊緣劃分和小區(qū)域目標(biāo)的劃分中占有優(yōu)勢。

圖4 不同算法分割實驗對比

從PA的定義可以看出，PA值越大，圖像聚類的效果越好。分析表1可得，在分割時間上，本文算法稍長于K-means算法和FCM算法，但是優(yōu)于沒有引入LBP算法的GA-K-means算法。從PA的值可得，客觀評價指標(biāo)與主觀分析結(jié)果一致，表明本文分割結(jié)果更接近于基準(zhǔn)分割。

表1 分割效果評估

5 結(jié)語

本文針對經(jīng)典K-means方法中存在的問題，提出了優(yōu)化方案。本文的改進(jìn)在于首先用LBP算子對圖像進(jìn)行特征提取，然后再使用改進(jìn)的K-means算法對圖像進(jìn)行分割。仿真實驗表明，本文算法優(yōu)于經(jīng)典的K-means方法和GAK-means算法，但是在運(yùn)行速度上稍遜于經(jīng)典的K-means算法。