基于AHLO與K均值聚類的圖像分割算法*

王豐斌

(信陽農林學院 信息工程學院， 河南 信陽 464000)

圖像分割是指將圖像中感興趣的區域從復雜的背景中提取出來的一種圖像處理技術.目前，圖像分割的方法多種多樣，如基于圖像邊緣的分割方法，基于閾值的分割方法，基于區域的分割方法等[1-6].基于K-均值聚類方法常用于圖像分割，如Moftah等[7]利用K-均值算法對醫療CT圖像進行分割取得了不錯的效果；Jumb等[8]提出了K-均值與閾值分割法結合的圖像分割法；徐黎明等[9]利用K-均值算法對楊梅采摘圖像進行分割，取得了良好的效果.但是K-均值聚類的方法本身存在著受初始聚類中心影響、容易陷入局部最優的缺點[10-11].

針對K-均值算法的這些缺點，一些學者提出了改進算法.Tzortzis等[12]提出了一種改進K-均值算法，將權重引入聚類中，使得簇類方差變小，分類效果提高.一些學者也嘗試將群智能算法與K-均值算法結合，提高K-均值算法的搜索性能.如Li和Younus等[13-14]將粒子群算法與K-均值算法結合，提高了K-均值算法的穩定性，并將其應用于圖像分割及檢索.

本文針對K-means存在受初始聚類中心影響大，容易陷入局部最優的缺點，將新型群智能算法自適應人類學習優化算法(AHLO)與K均值算法相結合，利用AHLO算法全局搜索能力強的特點，輸出逼近全局最優聚類中心的初始聚類中心，再利用K-均值算法進行局部搜索.將本文算法應用到圖像分割可提高K-均值算法分割圖像的穩定性.

1 K-means算法

K-means算法常用于圖像分割，傳統的K-means算法基于歐式距離劃分，優化目標函數E為樣本點到所屬簇類中心的距離平方和，即聚類誤差平方和，優化目標函數表達式為

(1)

式中：xij為第i類第j個樣本；Ni為第i類的樣本個數；ci為第i類的聚類中心；k為聚類數目.K-means算法經過反復迭代，可計算新的聚類中心，即

(2)

當E最小時，迭代結束.對K-means聚類算法分析可知，聚類結果的好壞受初始聚類中心的影響比較大，如果初始聚類中心點在選取時包含相同的初始點，則會出現錯誤.

2 自適應人類學習優化算法

Wang等[15-17]于2015年提出一種全局優化算法，即自適應人類學習優化算法(adaptive human learning optimization，AHLO)，該算法是一種群智能算法，通過模擬人類的學習行為機制對問題進行尋優，其具有設置參數少，收斂速度快，全局尋優能力強，不易陷入局部最小值的優點.自適應人類學習優化算法包含三種學習算子，分別為隨機學習算子、個體學習算子、社會學習算子.

自適應人類學習優化算法采用二進制編碼，每個個體用一串二進制碼表示.每個個體隨機初始化為包含“0”和“1”的二進制碼，該二進制碼代表人類想要學習的知識.根據人類的學習過程，人類在剛開始學習知識，由于沒有任何的先驗知識，人類的初始學習過程一般是一種隨機學習過程.隨機學習算子可以表示為

(3)

式中，rand()為0～1之間的隨機數.

當人類學習到一定程度時，人類具有一定的先驗知識，此時人類的學習過程會根據以往的經驗知識來避免錯誤，提高自身學習能力.用IKD(individual knowledge database)來表示人的知識庫，其表達式為

IKD=[ikd1，ikd2，…，ikdi，…，ikdN]
(1≤i≤N)

(4)

雖然人類可以通過自己學習知識來解決問題，但是當問題比較復雜時，人類學習過程比較漫長，需要花較長時間才能解決問題.但是當很多人一起學習一起解決問題時，可以極大提高效率，很多人的學習經驗就是社會知識庫.社會知識庫SKD(social knowledge database)的表達式為

SKD=[skd1，skd2，…，skdq，…，skdH]

(5)

個體整個學習過程包括隨機學習算子、個體學習算子、社會學習算子，整個學習過程可表示為

(6)

式中：pr為隨機學習的概率；pi-pr為個體學習的概率；1-pi為社會學習的概率.pi、pr這兩個參數對于平衡三種算子的學習起著至關重要的作用，對算法性能的影響較大.根據不同問題調節pi、pr這兩個參數值.為了提高搜索效率，減少參數設置的工作量，采用如下自適應策略，即

(7)

(8)

式中：prmin、pimin為pr、pi的最小值；prmax、pimax為pr、pi的最大值；Ite為當前迭代次數；Itemax為最大迭代次數.

3 自適應人類學習優化與K-means聚類算法

3.1 聚類策略與適應度函數

為了充分利用AHLO算法和K-means算法各自優勢，首先利用AHLO算法進行全局搜索，此時AHLO算法可以很大程度上靠近全局解子空間，在AHLO算法達到收斂后，利用K-means算法進行局部搜索，達到聚類的目的.對于AHLO算法，每個粒子的適應度值利用聚類誤差平方和計算.設有n個粒子，fi為第i個粒子的適應度值，fAvg為當前粒子適應度的平均值，其表達式為

(9)

粒子適應度的方差反應了AHLO算法的收斂度，其表達式為

(10)

在AHLO算法迭代過程中，粒子適應度值會趨于平穩，這時方差會穩定在一個確定的區域.所以當方差趨于確定區域時，可認為AHLO算法已經趨于最優解附近，此時利用K-means算法進行局部尋優.

3.2 算法流程

本文算法流程如圖1所示，具體步驟如下：1)初始化，設定人類學習種群數量和知識范圍；2)計算適應度值，保存個體知識庫和社會學習知識庫；3)進行隨機學習、個體學習、社會學習；4)根據適應度值更新個體學習知識庫和社會學習知識庫；5)計算平均適應度值和適應度方差；6)判斷適應度方差值是否大于閾值，如果沒有則重復步驟2)～5)過程；7)將AHLO算法的輸出作為K-means算法的初始聚類中心；8)計算聚類誤差平方和；9)更新聚類中心；10)判斷是否達到迭代次數，如果沒有則重復步驟8)、9)；11)輸出聚類中心.

4 實驗仿真與分析

實驗采用CPU為Intel(R) Core 2 CPU@2.30 GHz，內存為4 GB的計算機，操作系統為Windows 7，編譯軟件為Matlab 2014a.

4.1 AHLO-Kmeans算法性能測試

本文利用UCI標準數據集中的Iris、Balance-scale、Glass數據對算法性能進行測試，其數據參數如表1所示.AHLO-Kmeans算法參數設定為：種群規模為30，最大迭代次數為100，編碼長度為8位.粒子群算法參數設定為：種群規模為30，c1=2.1，c2=2.0，最大迭代次數為100.Iris中聚類數目k=3，Balance-scale中聚類數目k=3；Glass中聚類數目k=6.Kmeans、PSO-Kmeans，AHLO-Kmeans對數據集聚類的結果如表2所示.

圖1 算法流程圖Fig.1 Flow chart of algorithm

表1 數據集參數Tab.1 Dataset parameters

表2 各算法的聚類結果Tab.2 Clustering results of respective algorithm

從表2中可以看出，Kmeans算法由于受初始聚類中心的影響，聚類的標準差較大，穩定性較差.PSO-Kmeans算法利用PSO算法改善了初始聚類中心的選擇，改善了Kmeans均值算法的穩定性，但是相比AHLO-Kmeans算法，PSO-Kmeans算法的標準差仍然比本文算法的標準差大，這是因為AHLO算法相比PSO算法，全局尋優能力更強，更加逼近聚類中心，而PSO算法有時會陷入局部最優，全局搜索能力相對較差.

4.2 圖像分割

4.2.1 灰度圖像分割

本文利用Lena、camera、baboon、lake這四幅經典灰度圖像測試本文算法的聚類效果，分別對圖像進行聚類個數為k=2，k=5，k=7，k=9的聚類分割，AHLO-Kmeans算法的分割效果如圖2所示.從左往右依次為原始圖，聚類個數為2、5、7、9的圖像分割結果.為了衡量Kmeans算法、PSO-Kmeans算法、AHLO-Kmeans算法對圖像分割的好壞，用這3種算法對上述4幅經典圖像進行分割，實驗次數為20次，利用得到的平均峰值信噪比(PSNR)作為評價標準衡量各算法的好壞.實驗結果數據如表3所示.

從圖2的分割圖可以看出，AHLO-Kmeans算法的分割效果較好，邊緣清晰，各部分灰度區域分割比較均勻.從表3中的數據可以看出，在聚類個數比較少時，如k=2時，三種算法分割得到的PSNR值基本相同，但是隨著聚類個數的增加，Kmeans算法受初始聚類中心影響比較大，Kmeans算法分割得到的PSNR值最小，PSO-Kmeans對初始聚類中心的選擇有一定的改善，分割得到的PSNR值次之，而AHLO-Kmeans算法分割得到的PSNR值最大，表明本文算法對Kmeans算法初始聚類中心選擇改進效果最好，具有更好的聚類效果.

圖2 AHLO-Kmeans算法的分割結果Fig.2 Segmentation results by AHLO-Kmeans algorithm

數據集Kmeansk=2k=5k=7k=9PSO-Kmeansk=2k=5k=7k=9AHLO-Kmeansk=2k=5k=7k=9Lena8.57914.65415.63216.1348.57914.75415.71216.4658.57914.79615.79716.693camera8.92916.07917.32419.3108.92916.18817.45220.0138.92916.24317.55320.180baboon7.93913.11414.32114.9877.93913.13514.45315.0567.93913.21314.67315.127lake10.91717.01118.07618.21710.91717.03418.12418.34110.91717.15718.32818.535

4.2.2 彩色圖像分割

K-means算法常應用于農業圖像的分割中，本文利用AHLO-Kmeans算法對楊梅圖像、荔枝圖像、蘋果圖像、草莓圖像進行分割，其中聚類個數為3，驗證本文算法的實用性.首先將圖像由RGB空間轉換到Lab空間，然后對a、b分量進行聚類分割，分割效果如圖3所示，其中，第一列為原始圖像，第二列為分割圖像，第三列為提取的水果圖像.

圖3 彩色圖像分割結果Fig.3 Segmentation results of color images

從圖3的分割圖像可以看出，AHLO-Kmeans算法對于彩色圖像的分割效果比較好，能夠有效地分割出楊梅、荔枝、蘋果、草莓，分割輪廓也比較均勻，具有較強的實用性.

5 結 論

圖像分割技術被廣泛應用于機器視覺和計算機視覺領域.本文提出了一種結合自適應人類學習優化與K均值算法的聚類算法.該算法在初始化K均值聚類中心之前，利用自適應人類學習優化算法的全局搜索能力，快速逼近全局最優聚類中心，然后將自適應人類學習優化算法輸出的聚類中心作為K均值算法的初始聚類中心進行迭代尋優.將本文算法與傳統K均值算法、PSO-Kmeans算法進行對比發現，本文算法穩定性更好，聚類標準差更低，聚類效果更佳.將本文算法應用于灰度圖像與彩色圖像的分割，獲得的PSNR值更高，具有較強的實用價值.