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

王豐斌

(信陽農(nóng)林學(xué)院 信息工程學(xué)院， 河南 信陽 464000)

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

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

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

1 K-means算法

K-means算法常用于圖像分割，傳統(tǒng)的K-means算法基于歐式距離劃分，優(yōu)化目標(biāo)函數(shù)E為樣本點(diǎn)到所屬簇類中心的距離平方和，即聚類誤差平方和，優(yōu)化目標(biāo)函數(shù)表達(dá)式為

(1)

式中：xij為第i類第j個(gè)樣本；Ni為第i類的樣本個(gè)數(shù)；ci為第i類的聚類中心；k為聚類數(shù)目.K-means算法經(jīng)過反復(fù)迭代，可計(jì)算新的聚類中心，即

(2)

當(dāng)E最小時(shí)，迭代結(jié)束.對K-means聚類算法分析可知，聚類結(jié)果的好壞受初始聚類中心的影響比較大，如果初始聚類中心點(diǎn)在選取時(shí)包含相同的初始點(diǎn)，則會出現(xiàn)錯(cuò)誤.

2 自適應(yīng)人類學(xué)習(xí)優(yōu)化算法

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

自適應(yīng)人類學(xué)習(xí)優(yōu)化算法采用二進(jìn)制編碼，每個(gè)個(gè)體用一串二進(jìn)制碼表示.每個(gè)個(gè)體隨機(jī)初始化為包含“0”和“1”的二進(jìn)制碼，該二進(jìn)制碼代表人類想要學(xué)習(xí)的知識.根據(jù)人類的學(xué)習(xí)過程，人類在剛開始學(xué)習(xí)知識，由于沒有任何的先驗(yàn)知識，人類的初始學(xué)習(xí)過程一般是一種隨機(jī)學(xué)習(xí)過程.隨機(jī)學(xué)習(xí)算子可以表示為

(3)

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

當(dāng)人類學(xué)習(xí)到一定程度時(shí)，人類具有一定的先驗(yàn)知識，此時(shí)人類的學(xué)習(xí)過程會根據(jù)以往的經(jīng)驗(yàn)知識來避免錯(cuò)誤，提高自身學(xué)習(xí)能力.用IKD(individual knowledge database)來表示人的知識庫，其表達(dá)式為

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

(4)

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

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

(5)

個(gè)體整個(gè)學(xué)習(xí)過程包括隨機(jī)學(xué)習(xí)算子、個(gè)體學(xué)習(xí)算子、社會學(xué)習(xí)算子，整個(gè)學(xué)習(xí)過程可表示為

(6)

式中：pr為隨機(jī)學(xué)習(xí)的概率；pi-pr為個(gè)體學(xué)習(xí)的概率；1-pi為社會學(xué)習(xí)的概率.pi、pr這兩個(gè)參數(shù)對于平衡三種算子的學(xué)習(xí)起著至關(guān)重要的作用，對算法性能的影響較大.根據(jù)不同問題調(diào)節(jié)pi、pr這兩個(gè)參數(shù)值.為了提高搜索效率，減少參數(shù)設(shè)置的工作量，采用如下自適應(yīng)策略，即

(7)

(8)

式中：prmin、pimin為pr、pi的最小值；prmax、pimax為pr、pi的最大值；Ite為當(dāng)前迭代次數(shù)；Itemax為最大迭代次數(shù).

3 自適應(yīng)人類學(xué)習(xí)優(yōu)化與K-means聚類算法

3.1 聚類策略與適應(yīng)度函數(shù)

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

(9)

粒子適應(yīng)度的方差反應(yīng)了AHLO算法的收斂度，其表達(dá)式為

(10)

在AHLO算法迭代過程中，粒子適應(yīng)度值會趨于平穩(wěn)，這時(shí)方差會穩(wěn)定在一個(gè)確定的區(qū)域.所以當(dāng)方差趨于確定區(qū)域時(shí)，可認(rèn)為AHLO算法已經(jīng)趨于最優(yōu)解附近，此時(shí)利用K-means算法進(jìn)行局部尋優(yōu).

3.2 算法流程

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

4 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)采用CPU為Intel(R) Core 2 CPU@2.30 GHz，內(nèi)存為4 GB的計(jì)算機(jī)，操作系統(tǒng)為Windows 7，編譯軟件為Matlab 2014a.

4.1 AHLO-Kmeans算法性能測試

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

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

表1 數(shù)據(jù)集參數(shù)Tab.1 Dataset parameters

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

從表2中可以看出，Kmeans算法由于受初始聚類中心的影響，聚類的標(biāo)準(zhǔn)差較大，穩(wěn)定性較差.PSO-Kmeans算法利用PSO算法改善了初始聚類中心的選擇，改善了Kmeans均值算法的穩(wěn)定性，但是相比AHLO-Kmeans算法，PSO-Kmeans算法的標(biāo)準(zhǔn)差仍然比本文算法的標(biāo)準(zhǔn)差大，這是因?yàn)锳HLO算法相比PSO算法，全局尋優(yōu)能力更強(qiáng)，更加逼近聚類中心，而PSO算法有時(shí)會陷入局部最優(yōu)，全局搜索能力相對較差.

4.2 圖像分割

4.2.1 灰度圖像分割

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

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

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

數(shù)據(jù)集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算法常應(yīng)用于農(nóng)業(yè)圖像的分割中，本文利用AHLO-Kmeans算法對楊梅圖像、荔枝圖像、蘋果圖像、草莓圖像進(jìn)行分割，其中聚類個(gè)數(shù)為3，驗(yàn)證本文算法的實(shí)用性.首先將圖像由RGB空間轉(zhuǎn)換到Lab空間，然后對a、b分量進(jìn)行聚類分割，分割效果如圖3所示，其中，第一列為原始圖像，第二列為分割圖像，第三列為提取的水果圖像.

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

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

5 結(jié) 論

圖像分割技術(shù)被廣泛應(yīng)用于機(jī)器視覺和計(jì)算機(jī)視覺領(lǐng)域.本文提出了一種結(jié)合自適應(yīng)人類學(xué)習(xí)優(yōu)化與K均值算法的聚類算法.該算法在初始化K均值聚類中心之前，利用自適應(yīng)人類學(xué)習(xí)優(yōu)化算法的全局搜索能力，快速逼近全局最優(yōu)聚類中心，然后將自適應(yīng)人類學(xué)習(xí)優(yōu)化算法輸出的聚類中心作為K均值算法的初始聚類中心進(jìn)行迭代尋優(yōu).將本文算法與傳統(tǒng)K均值算法、PSO-Kmeans算法進(jìn)行對比發(fā)現(xiàn)，本文算法穩(wěn)定性更好，聚類標(biāo)準(zhǔn)差更低，聚類效果更佳.將本文算法應(yīng)用于灰度圖像與彩色圖像的分割，獲得的PSNR值更高，具有較強(qiáng)的實(shí)用價(jià)值.