基于LBP算子和GA-K-means的圖像分割算法

王甜甜 ，史衛亞

（1 河南工業大學信息科學與工程技術學院 河南 鄭州 450001）

（2 河南工業大學人工智能與大數據學院 河南 鄭州 450001）

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

0 引言

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

1 LBP特征提取

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

（1）細分區域；

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

（3）計算每個區域的直方圖，并進行歸一化處理。

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

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

2 遺傳算法

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

圖1 遺傳算法流程圖

在遺傳算法的每個循環中，選擇、交叉和變異算子在尋優過程中最為重要：

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

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

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

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

3.1 算法步驟

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

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

（2）使用LBP算法對樣本集進行特征提取。

（3）使用遺傳算法找到最優的K值。

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

（5）使用（3）（4）中的K值和初始聚類中心，對數據集進行聚類操作。

（6）聚類結束。

3.2 實現步驟

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

類內的距離[8]如式（3）所示。

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

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

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

適應度函數定義如式（5）所示。平均類內距離越小，類間距離越大，聚類效果越好，適應度函數值越大[9]。

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

4 實驗結果

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

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

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

4.1 特征提取

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

圖2 特征提取圖

4.2 實驗結果及分析

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

圖3 遺傳算法的收斂曲線

不同算法的分割結果如圖4所示，K-means對圖像邊緣的分割性能較差，無法精準識別動物圖片的邊緣信息；FCM能夠識別邊緣信息，但是在細節分割方面效果較差；遺傳算法和K-means結合能進一步完善對細節的分割性能，但是在紋理復雜的圖像中表現不如本文算法。方框中圈出的區域為本文算法優于其他算法的區域。比較可得，本文算法在邊緣劃分和小區域目標的劃分中占有優勢。

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

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

表1 分割效果評估

5 結語

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