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

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

基于鏈式競爭遺傳算法的KSW熵的圖像分割*

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

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

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

圖像分割； 最佳閾值圖像分割； 遺傳算法； 鏈式競爭

0 引 言

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

本文針對上述問題，提出了一種基于鏈式競爭遺傳算法的KSW熵的圖像分割處理算法(L-GA-KSW熵算法)。

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

1 KSW熵算法[7，8]

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

(1)

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

(2)

(3)

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

(4)

(5)

則目標與背景的熵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è)計

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

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

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

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

4)計算種群中每個個體的適應(yīng)值，引入三個鄰域的鏈式競爭，對個體的適應(yīng)值進行三個鄰域比較進行特征選擇，產(chǎn)生新的種群。

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

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

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

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

3 仿真結(jié)果

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

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

圖1 仿真對象

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

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

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

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

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

表2 3種算法圖像分割時間 s

4 結(jié) 論

實驗結(jié)果表明:本文提出的算法提高了圖像的分割效果、提高了圖像分割算法的魯棒性、縮短了圖像分割時間，有利于圖像的實時處理。通過實驗對比本文提出的算法優(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é)報,1999,25(6):747-750.

[6] 曾孝平,李勇明,王 靖,等.基于競爭策略的鏈式智能體遺傳算法用于特征選擇的研究[J].系統(tǒng)仿真學(xué)報,2008,20(8):1973-1979.

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

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

[9] 李敏強.遺傳算法的基本理論與應(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

國家科技支撐計劃課題資助項目(2015BAK01B06)

曹 靜(1992-),女，碩士研究生，研究方向為數(shù)字圖像處理。