基于鏈?zhǔn)礁?jìng)爭(zhēng)遺傳算法的KSW熵的圖像分割*

曹 靜， 王 元， 婁澤坤， 冷鵬飛

(河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475000)

基于鏈?zhǔn)礁?jìng)爭(zhēng)遺傳算法的KSW熵的圖像分割*

曹 靜， 王 元， 婁澤坤， 冷鵬飛

(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南開封475000)

針對(duì)最佳熵閾值圖像分割算法過(guò)程中計(jì)算復(fù)雜度高的問(wèn)題，提出了一種基于鏈?zhǔn)礁?jìng)爭(zhēng)遺傳算法的最佳熵閾值確定法(KSW熵法)的圖像分割算法。通過(guò)將3個(gè)鄰域的鏈?zhǔn)礁?jìng)爭(zhēng)引入到常規(guī)遺傳算法框架下，實(shí)現(xiàn)特征選擇過(guò)程；將改進(jìn)的遺傳算法應(yīng)用到最佳閾值圖像分割算法中，完成對(duì)閾值的尋優(yōu)過(guò)程。仿真實(shí)驗(yàn)結(jié)果與分析表明：算法在分割速度和效果上均優(yōu)于傳統(tǒng)的最佳閾值圖像分割算法和單純的遺傳優(yōu)化最佳閾值圖像分割算法。

圖像分割； 最佳閾值圖像分割； 遺傳算法； 鏈?zhǔn)礁?jìng)爭(zhēng)

0 引 言

圖像分割是一種將圖像分割成若干個(gè)具有特定性質(zhì)的區(qū)域，是不同區(qū)域之間的差別盡可能明顯的圖像處理方法[1]。傳統(tǒng)的圖像分割方法分為閾值法圖像分割、邊緣檢測(cè)法圖像分割、區(qū)域生長(zhǎng)法圖像分割、模糊理論圖像分割及數(shù)學(xué)形態(tài)學(xué)圖像分割等。由于其應(yīng)用目的不同，且圖像特征不同，這些方法均存在一定的局限性。其中，閾值方法因其簡(jiǎn)單且穩(wěn)定的性能成為了圖像分割中最基本的技術(shù)之一[2]。Ostu N等人[3]針對(duì)控制圖像分割造成的信息損失提出了基于信息論熵準(zhǔn)則的圖像閾值自動(dòng)選取方法解決了閾值分割中門限的選取問(wèn)題，優(yōu)于常用的灰度差直方圖法。但由于多數(shù)圖像并不可以簡(jiǎn)單的一分為二，因此對(duì)于灰度等級(jí)分布谷底不明顯的復(fù)雜圖像，利用單一Otsu準(zhǔn)則無(wú)法將目標(biāo)可靠、穩(wěn)定地從圖像中分割出來(lái)。為解決上述問(wèn)題，Kapur，Sahoo和Wong等人[4]提出了最佳熵閾值確定性圖像分割算法,簡(jiǎn)稱KSW算法。無(wú)需利用先驗(yàn)知識(shí)，且即使是非理想雙峰直方圖的圖像也可進(jìn)行處理，然而，其在確定多閾值時(shí)，計(jì)算復(fù)雜度過(guò)大，分割圖像所需時(shí)間較長(zhǎng)。根據(jù)以上問(wèn)題，種勁松等人[5]提出了基于遺傳算法的最佳熵閾值圖像分割法(GA-KSW算法)，利用遺傳算法的魯棒性、并行性和自適應(yīng)性的特點(diǎn)，將其與KSW算法有效地結(jié)合，縮短了尋找閾值的時(shí)間。但是該算法利用了傳統(tǒng)遺傳算法容易令圖像分割過(guò)程陷入“早熟”，圖像分割效果并不理想。

本文針對(duì)上述問(wèn)題，提出了一種基于鏈?zhǔn)礁?jìng)爭(zhēng)遺傳算法的KSW熵的圖像分割處理算法(L-GA-KSW熵算法)。

通過(guò)對(duì)常規(guī)遺傳算法加入三個(gè)鄰域的鏈?zhǔn)礁?jìng)爭(zhēng)[6]，改進(jìn)特征選擇過(guò)程；然后將改進(jìn)后的遺傳算法應(yīng)用到最佳閾值圖像分割上，克服了傳統(tǒng)遺傳算法在閾值圖像分割中的不足。

1 KSW熵算法[7，8]

根據(jù)Shannon熵的概念，對(duì)于灰度范圍為{0,1,…,l,-1}的圖像，其直方圖熵的定義為

(1)

式中pi為第i個(gè)灰度出現(xiàn)的概率。在單閾值情況下，設(shè)閾值t將圖像劃分為目標(biāo)與背景兩類，則令

(2)

(3)

有閾值t分為A和B兩類后,則這兩類的概率分布列分別為

(4)

(5)

則目標(biāo)與背景的熵H0(t)和HB(t)分別為

(6)

(7)

圖像的總熵H(t)為H0(t)和HB(t)之和，即

H(t)=H0(t)+HB(t)

(8)

最佳閾值t*為使得圖像的總熵取得最大值

(9)

在多閾值情況下，設(shè)S1,S2,…,Sk為分割閾值，且有S1

(10)

S2，…,Sk)

(11)

(12)

(13)

2 L-GA-KSW熵算法設(shè)計(jì)

GA[9]全局尋優(yōu)能力較強(qiáng)且具有較好的魯棒性。但是由于標(biāo)準(zhǔn)GA容易陷入局部最優(yōu)和“早熟”等，為了改進(jìn)GA，文中采用鏈?zhǔn)礁?jìng)爭(zhēng)策略尋找最優(yōu)KSW閾值,通過(guò)鏈?zhǔn)街悄荏w相互競(jìng)爭(zhēng)、變異和交叉等方式有效地保持了種群個(gè)體的多樣性，從而能夠獲得更準(zhǔn)確的結(jié)果和更快的收斂速度。算法設(shè)計(jì)如下:

1)初始化GA中的參數(shù)(包括迭代次數(shù)、種群規(guī)模、交叉和變異概率的選擇等)以及種群選擇的適應(yīng)度函數(shù)。

2)采用輪盤賭法選擇若干滿足適應(yīng)度函數(shù)要求的染色體組成新種群作為父本。

3)通過(guò)GA的交叉、變異對(duì)父本進(jìn)行處理，產(chǎn)生新一代種群。

4)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)值，引入三個(gè)鄰域的鏈?zhǔn)礁?jìng)爭(zhēng)，對(duì)個(gè)體的適應(yīng)值進(jìn)行三個(gè)鄰域比較進(jìn)行特征選擇，產(chǎn)生新的種群。

5)重復(fù)步驟(2)～步驟(4)，使染色體不斷變化，直到進(jìn)化代數(shù)完成，記錄每一代進(jìn)化中最好的適應(yīng)度值。

6)終止準(zhǔn)則：規(guī)定當(dāng)算法執(zhí)行到最大代數(shù)(終止條件)或經(jīng)過(guò)100代進(jìn)化，群體中的最高適應(yīng)度值仍未發(fā)生變化(穩(wěn)定條件)時(shí)，算法停止運(yùn)行，具有最高適應(yīng)度值的個(gè)體即為分割閾值。

步驟(4)是本文引入的鏈?zhǔn)礁?jìng)爭(zhēng)策略對(duì)個(gè)體的適應(yīng)值進(jìn)行三個(gè)鄰域的比較，完成特征選擇。當(dāng)掃描到第一個(gè)個(gè)體時(shí)，其前一個(gè)體為最后個(gè)體，下一個(gè)體為第二個(gè)個(gè)體，同理當(dāng)掃描到最后一個(gè)個(gè)體時(shí)，其前一個(gè)體為倒數(shù)第二個(gè)個(gè)體，下一個(gè)體為第一個(gè)個(gè)體。將相鄰的三個(gè)個(gè)體作為適應(yīng)值存放在鄰域寄存器中，找出相鄰三個(gè)個(gè)體中的最小適應(yīng)值以及對(duì)應(yīng)的個(gè)體，則當(dāng)前個(gè)體不變；否則，將此最小適應(yīng)值對(duì)應(yīng)的個(gè)體與當(dāng)前掃描的個(gè)體比較，相同位不變；不同位則隨機(jī)生成0～1之間的隨機(jī)數(shù)。

基于以上分析，給出算法的編碼方案如下：對(duì)于單閾值圖像分割，由于圖像灰度值在0～255之間，故將各個(gè)染色體編碼為8位二進(jìn)制碼，其代表某個(gè)分割閾值。當(dāng)圖像中存在多個(gè)分割目標(biāo)時(shí)采用多閾值分割，文中針對(duì)雙閾值分割進(jìn)行程序設(shè)計(jì)，將單閾值分割中的8位二進(jìn)制碼串改為16位，前8位代表一個(gè)門限值，后8位代表另一個(gè)門限值。雙閾值分割屬于多參數(shù)遺傳程序設(shè)計(jì)，本文設(shè)置種群數(shù)20，繁殖代數(shù)為100。

3 仿真結(jié)果

仿真場(chǎng)景硬件設(shè)置為HP 286，內(nèi)存4 GBWindows 7，仿真軟件為Matlab 2012a。為測(cè)試L-GA-KSW算法的有效性和優(yōu)越性，選擇原始Lena圖像，加噪聲的Lena圖像以及Rice圖像作為仿真對(duì)象。為使加入L-GA-KSW熵算法更有說(shuō)服力，選擇標(biāo)準(zhǔn)的KSW熵算法、標(biāo)準(zhǔn)GA優(yōu)化KSW熵算法(GA-KSW熵算法)和文中提出L-GA-KSW熵算法進(jìn)行了對(duì)比實(shí)驗(yàn)。遺傳算法交叉概率0.8，變異概率0.1， 種群數(shù)20。

圖1中的3類圖像分別為L(zhǎng)ena標(biāo)準(zhǔn)原始圖像、加噪聲的Lena和加噪聲的Rice。分別用KSW熵算法、GA-KSW熵算法、L-GA-KSW熵算法分割，結(jié)果如圖2～圖4。

圖1 仿真對(duì)象

圖2 原始Lena圖像分割結(jié)果

圖3 加噪Lena圖像分割結(jié)果

圖4 原始Rice圖像分割結(jié)果

從表1和表2中可以看出，利用加入L-GA-KSW熵算法對(duì)Lena圖像、加噪聲的Lena圖像、Rice圖像進(jìn)行分割所用時(shí)間明顯少于標(biāo)準(zhǔn)KSW熵算法和GA-KSW熵算法實(shí)驗(yàn)結(jié)果表明，L-GA-KSW算法將分割效果及處理速度進(jìn)行了優(yōu)化，得到了更好的分割效率，且魯棒性更好。

表1 3種算法分割閾值結(jié)果

表2 3種算法圖像分割時(shí)間 s

4 結(jié) 論

實(shí)驗(yàn)結(jié)果表明:本文提出的算法提高了圖像的分割效果、提高了圖像分割算法的魯棒性、縮短了圖像分割時(shí)間，有利于圖像的實(shí)時(shí)處理。通過(guò)實(shí)驗(yàn)對(duì)比本文提出的算法優(yōu)于傳統(tǒng)的KSW算法和GA-KSW熵算法。

[1] 宋家慧.基于遺傳算法的最大熵閾值的圖像分割[J].信息化研究,2005,31(2):60-63.

[2] Pal N R,Pal S K.A review on image segmentation techniques[J].Pattern Recognition,1993,26(9):1277-1294.

[3] Ohtsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems Man & Cybernetics,1979,9(1):62-66.

[4] Kapur J N,Sahoo P K,Wong A K C.A new method for gray-level picture thresholding using the entropy of the histogram[J].Computer Vision Graphics & Image Processing,1980,29(3):273-285.

[5] 種勁松,王宏琦.基于遺傳算法的最佳熵閾值圖像分割法[J].北京航空航天大學(xué)學(xué)報(bào),1999,25(6):747-750.

[6] 曾孝平,李勇明,王 靖,等.基于競(jìng)爭(zhēng)策略的鏈?zhǔn)街悄荏w遺傳算法用于特征選擇的研究[J].系統(tǒng)仿真學(xué)報(bào),2008,20(8):1973-1979.

[7] 謝鵬鶴,楊恢先,王緒四.基于最大累積剩余熵的紅外圖像分割[J].傳感器與微系統(tǒng),2011,30(7):34-37.

[8] 倫向敏,侯一民.運(yùn)用迭代最大熵算法選取最佳圖像分割閾值[J].計(jì)算機(jī)工程與設(shè)計(jì),2015(5):1265-1268.

[9] 李敏強(qiáng).遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社,2002.

ImagesegmentationofKSWentropicbasedonchaincompetitivegeneticalgorithm*

CAO Jing， WANG Yuan， LOU Ze-kun， LENG Peng-fei

(SchoolofComputerandInformationEngineering,HenanUniversity,Kaifeng475000,China)

Aiming at the problem of high computational complexity in the process of the optimal entropic threshold image segmentation algorithm,propose an image segmentation algorithm based on link-like competition genetic algorithm for optimum entropy thresholding method,i.e.KSW entropy(L-GA-KSW).In the process of algorithm realization,feature selection process is realized by introducing the chain competition of 3 neighboring chains into the framework of conventional genetic algorithm;then,the improved genetic algorithm is applied to the optimal threshold image segmentation algorithm to achieve threshold optimizing.Simulation results and analysis show that the algorithm is superior to the traditional image segmentation algorithm and the simple genetic optimization threshold image segmentation algorithm in segmentation speed and effect.

image segmentation; optimal threshold image segmentation; genetic algorithm(GA); link-like competition

10.13873/J.1000—9787(2017)11—0128—03

TP 391

A

1000—9787(2017)11—0128—03

2016—09—29

國(guó)家科技支撐計(jì)劃課題資助項(xiàng)目(2015BAK01B06)

曹 靜(1992-),女，碩士研究生，研究方向?yàn)閿?shù)字圖像處理。