微分進(jìn)化的自適應(yīng)彩色圖像閾值分割

張志禹， 王彩虹

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院， 陜西 西安 710048)

微分進(jìn)化的自適應(yīng)彩色圖像閾值分割

張志禹， 王彩虹

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院， 陜西 西安 710048)

針對(duì)閾值的選擇依賴于經(jīng)驗(yàn)和試驗(yàn)的問(wèn)題，提出了結(jié)合微分進(jìn)化算法和二維最大熵算法得到圖像自適應(yīng)閾值的方法。該方法首先利用全局閾值法中的迭代法得到圖像的閾值并初次對(duì)圖像進(jìn)行分割，然后利用微分進(jìn)化算法并且結(jié)合二維最大熵閾值進(jìn)行適應(yīng)度的計(jì)算、個(gè)體編碼、終斷條件等計(jì)算圖像的自適應(yīng)閾值，最后對(duì)測(cè)試的圖像應(yīng)用微分進(jìn)化算法實(shí)現(xiàn)對(duì)圖像的正確分割。采用微分進(jìn)化算法可以準(zhǔn)確地對(duì)圖像進(jìn)行分割，是一個(gè)比較高效的方法，有效地提升了分割效果。與現(xiàn)有的自適應(yīng)閾值分割算法相比，本文算法縮短了計(jì)算時(shí)間。閾值分割不僅可以對(duì)灰度圖像進(jìn)行分割，彩色圖像也可以用閾值分割。

自適應(yīng)閾值；圖像分割；微分進(jìn)化；算法

0 引言

最近幾年在圖像分割方面出現(xiàn)了許多新思路、新方法和改進(jìn)算法，并將圖像分割法分為閾值分割法、邊緣檢測(cè)法、區(qū)域提取法3類。

閾值圖像分割主要分為全局閾值和局部閾值兩類。

全局閾值法指利用全局信息對(duì)整幅圖像求出最優(yōu)分割閾值, 可以是單閾值, 也可以是多閾值，當(dāng)物體和背景像素的灰度分布十分明顯時(shí)可以使用全局閾值對(duì)圖像進(jìn)行分割。而常用的全局閾值法有迭代法、最大類間方差法等。

關(guān)于局部閾值最近已經(jīng)有人提出了自適應(yīng)閾值方法。1986，Niblack[1]等人根據(jù)對(duì)比度，利用局部閾值相鄰像素的局部均值和標(biāo)準(zhǔn)差來(lái)計(jì)算閾值。Bernsen[2]等人提出一種局部灰度范圍技術(shù)，以確定最大和最小像素之間的閾值范圍。后來(lái)，在1997年，Sauvola[3]等人介紹了一種計(jì)算局部自適應(yīng)閾值的方法。但在局部區(qū)域，對(duì)比度仍然很低，因此在計(jì)算過(guò)程中，由于其計(jì)算結(jié)果存在差異，導(dǎo)致閾值變得小于平均值。這項(xiàng)技術(shù)有助于成功地去除相對(duì)較暗的區(qū)域的背景。在2011年，文獻(xiàn)[4]提出一種計(jì)算局部閾值的方法。該方法使用了積分求和技術(shù)，在圖像中找到與圖像大小無(wú)關(guān)的鄰域像素的局部均值。Niblack和Bernsen的方法需要通過(guò)圖像的大小來(lái)計(jì)算自適應(yīng)閾值。

本文中運(yùn)用到的微分進(jìn)化算法[5]是一種新的基于群體的隨機(jī)優(yōu)化方法，也是一種新的進(jìn)化全局優(yōu)化的算法，具有簡(jiǎn)單、快速、魯棒性好等特點(diǎn)。廣泛應(yīng)用于含有搜索和優(yōu)化任務(wù)的問(wèn)題中。進(jìn)化算法是基于經(jīng)過(guò)編碼的一組向量，利用一些進(jìn)化機(jī)制，依據(jù)適者生存的法則，通過(guò)多次迭代，找到問(wèn)題的最優(yōu)解。在非線性和不可微的連續(xù)空間問(wèn)題上優(yōu)于其他進(jìn)化方法。

1 閾值的選取

1.1 噪聲在閾值分割中的作用

可以憑直覺(jué)判斷灰度圖像[6]處理時(shí)閾值選取是否合適，而閾值的選取直接影響到圖像分割的成功與否。如圖1所示。

圖1 原圖和加了椒鹽噪聲的圖及其所對(duì)應(yīng)的直方圖

由圖1可以看出，(a)圖是沒(méi)有加噪聲的圖像，其直方圖(d)可以看成由兩個(gè)波峰模式組成，將該圖像分割為兩個(gè)區(qū)域是很容易的，只需在兩個(gè)波峰之間任意取一個(gè)閾值，就可以達(dá)到分割的效果。(b)中加了參數(shù)為0.3的椒鹽噪聲，(e)是其對(duì)應(yīng)的直方圖，由(e)圖可以看出兩個(gè)波峰之間出現(xiàn)了一個(gè)波谷，因此，更有利于閾值的選取。(c)圖中加了參數(shù)為0.8的椒鹽噪聲，明顯看出圖(c)被污染得很嚴(yán)重，其相應(yīng)的直方圖為(f)，將圖(f)和圖(e)進(jìn)行對(duì)比可以看出，圖(f)的直方圖沒(méi)有了較明顯的波峰與波谷，使閾值選取更加困難。因此，添加噪聲也要適當(dāng)，要避免噪聲嚴(yán)重污染原圖像，以至于無(wú)法區(qū)分波峰和波谷兩個(gè)模式，從而達(dá)不到預(yù)期的效果，增加了圖像分割的困難。

1.2 全局閾值處理

選取閾值的一種方法是目視檢查直方圖。另一種選擇閾值的方法是反復(fù)試驗(yàn)，挑選不同的閾值，直到觀測(cè)者覺(jué)得產(chǎn)生了較好的結(jié)果為止。全局閾值將整個(gè)圖像的灰度閾值設(shè)置為常數(shù)。

首先，為閾值T選一個(gè)初始估計(jì)值，然后利用全局閾值中的迭代法來(lái)得到最終的閾值T。

而閾值處理后的圖像g(x,y)定義為：

(1)

其中，f(x,y)為點(diǎn)(x,y)的像素值，g(x,y)為分割后的圖像，T為全局閾值，在這里通過(guò)迭代法來(lái)獲取全局閾值。

2 本文算法

2.1 微分進(jìn)化算法

一組優(yōu)化的參數(shù)被稱為一個(gè)單獨(dú)的向量，它由一個(gè)N維參數(shù)向量表示。一個(gè)單獨(dú)的向量xi,G(i=1,2,…,NP-1)組成了參數(shù)向量，G為迭代次數(shù)。

(1)突變

對(duì)于每一個(gè)目標(biāo)向量xi,G，一個(gè)突變的矢量根據(jù)下式生成：

vi,G+1=xr1,G+F(xr2,G-xr3,G)，r1≠r2≠r3≠I

(2)

其中隨機(jī)選擇指標(biāo)r1,r2,r3∈[1,NP]

(2)交叉

目標(biāo)向量與突變的載體混合使用得到以下試驗(yàn)向量的方案：

ui,G+1=(u1i,G+1,u2i,G+1,…,uDi,G+1)

(3)

j=1,2,…,D，r(j)∈[0,1]是一個(gè)統(tǒng)一的第j個(gè)評(píng)價(jià)隨機(jī)數(shù)產(chǎn)生器。CR∈[0,1]是交叉率。rndn(i)∈(1,2,…,D)是一個(gè)隨機(jī)選擇的指標(biāo)確保用戶界面，ui,G+1從vi,G+1中獲得至少一個(gè)元素。

(3)選擇

一個(gè)理想的選擇方案：

(4)

對(duì)于j=1,…,D，如果試驗(yàn)矢量ui,G+1比理想矢量xi,G+1更具有價(jià)值，則從理想矢量xi,G+1建立試驗(yàn)矢量ui,G+1，否則，保留理想矢量xi,G+1的價(jià)值。

2.2 二維最大熵閾值

Abutaleb[7]通過(guò)二維最大熵[8]法發(fā)現(xiàn)每個(gè)像素的最佳閾值[8]，提出了一個(gè)二維直方圖的最佳閾值點(diǎn)。

就灰度圖像而言，灰度圖像f(x,y)的像素為(x,y)，g(x,y)是平均灰度鄰域大小為k×k和以像素(x,y)為中心鄰區(qū)的灰度圖像。平均灰度鄰域值定義為：

(5)

在這里，1≤x+m≤N,1≤y+n≤N,M和N為圖像的高度和寬度，被設(shè)置為奇數(shù)。

二維直方圖N(i,j)被定義為像素的灰度值f(x,y)=i和平均灰度值范圍g(x,y)=j,其中i,j=0,1,……,L-1。每一組元素值(i,j)，其像素灰度是i，平均灰度值為j。假設(shè)像素值(i,j)出現(xiàn)的概率是fij,則定義概率分布pij為：

pij=fij/M×N

(6)

圖2 二維直方圖

這里，i,j=0,1,…,L-1,因?yàn)榛叶鹊母怕史植紁ij及其平均值分布集中，沿對(duì)角線(0,0)～(L-1,L-1)分布。像素灰度值f(i,j)和平均值鄰域灰度值g(i,j)可以從二維直方圖得到。二維直方圖如圖2所示。

如圖2所示，區(qū)域A表示對(duì)象，區(qū)域B表示背景，區(qū)域C和區(qū)域D是遠(yuǎn)離對(duì)角線和噪聲的區(qū)域，因此，最佳閾值[9]是用二維最大熵方法得到的區(qū)域A和區(qū)域B，同時(shí)也可以確定圖像的對(duì)象和背景分布。

因?yàn)橛胁煌母怕史植紖^(qū)域，因此在每個(gè)區(qū)域中元素的熵和背景的熵出現(xiàn)的概率基本相同?；叶鹊臈l件屬于{0,1,2,…,L-1}和二維閾值{s,t}(0≤s,t≤L-1,s,t∈N)。其中，區(qū)域A和區(qū)域B的概率計(jì)算公式如下：

(7)

二維熵：

(8)

二維元素熵：

(9)

背景的熵：

(10)

其中

(11)

熵判別函數(shù)：

φ(s,t)=H(A)+H(B)

(12)

在式(10)中，也涉及到了區(qū)域C和區(qū)域D出現(xiàn)的可能性,考慮噪聲式的可能性是很小的，幾乎可以忽略，所以可以將區(qū)域C和區(qū)域D的可能性設(shè)置為0。

PB=1-PA,HB=HL-HA

(13)

(14)

(15)

因此，方程(12)可以改變?yōu)椋?/p>

(16)

從而可以得到最佳的閾值{s,t}：

(17)

2.3 基于微分進(jìn)化的自適應(yīng)閾值圖像分割

(1)自適應(yīng)函數(shù)的計(jì)算

自適應(yīng)[11]函數(shù)值決定個(gè)體的選擇進(jìn)化算法。在本文中，定義了自適應(yīng)函數(shù)

(18)

在這里φ(s*,t*)是最大的閾值。

(2)個(gè)體編碼

在本文的方法中，個(gè)體編碼元組(s,t)，因?yàn)橹挥袃晌辉M(s,t)，所以從n元組得到每個(gè)個(gè)體，而個(gè)體被看作是

(s1,t1,s2,t2,…,sn,tn)

(19)

在本文的實(shí)驗(yàn)中，n被設(shè)置為10。

(3)終端條件

這里設(shè)定的最大迭代次數(shù)為100，或者直到結(jié)果發(fā)生變化。

(4)基于微分進(jìn)化的閾值圖像分割[10]算法

步驟1：讀取圖像數(shù)據(jù)，設(shè)置鄰域大小k=3。

步驟2：設(shè)置參數(shù)交叉率、比例因子、種群規(guī)模與終止準(zhǔn)則。

步驟3：計(jì)算聯(lián)合概率，pij與(5)。

步驟4：生成初始種群如式(17)。

步驟5：變異和交叉操作

步驟5.1：突變(1)；

步驟5.2：交叉(2)；

步驟5.3：從(i,j)中分離個(gè)體，計(jì)算每個(gè)(i,j)的值且自適應(yīng)函數(shù)為式(16)。

步驟6：如果迭代達(dá)到終止準(zhǔn)則,輸出最大值(i,j)，退出迭代算法，否則返回步驟5。

接下來(lái)，通過(guò)實(shí)驗(yàn)來(lái)說(shuō)明閾值分割方法同樣也可以應(yīng)用在彩色圖像上。

3 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試本文方法的有效性，選用了4組圖像作為測(cè)試圖像，如圖3(a)～(d)所示。并與兩種常用的閾值圖像分割方法進(jìn)行對(duì)比，分別為最大熵法和Ostu(最大類間方差法)。

圖3 3種算法對(duì)4組測(cè)試圖像的分割結(jié)果

首先，用二維最大熵的分割方法對(duì)4組測(cè)試圖像進(jìn)行分割。其次，用Ostu方法的最佳全局閾值處理4組測(cè)試圖像，如圖3所示。Ostu法對(duì)圖像分割最優(yōu)閾值進(jìn)行優(yōu)化處理，極大縮短了搜索圖像閾值計(jì)算時(shí)間，與傳統(tǒng)的枚舉法Ostu方法相比,在計(jì)算時(shí)間上具有顯著的優(yōu)勢(shì)。該方法不僅能得到理想的分割結(jié)果,而且計(jì)算量減少很多,達(dá)到了快速分割的目的。從圖3(e)～(h)可以看出最大熵法出現(xiàn)了很明顯的欠分割。從圖3(i)～(j)可以看出Ostu法已經(jīng)對(duì)4組測(cè)試圖像做了很好的背景與目標(biāo)的分割，出現(xiàn)了過(guò)分割的現(xiàn)象，對(duì)噪聲和不均勻的顏色區(qū)域較敏感。而用微分進(jìn)化算法對(duì)圖像進(jìn)行分割時(shí)，在Ostu法分割的基礎(chǔ)上，同時(shí)考慮了彩色圖像的顏色信息，還能充分利用鄰接像素間的關(guān)系，圖3(m)～(p)表明，DE法克制了上面的問(wèn)題，還可以有效地抑制背景中噪聲的產(chǎn)生。并且在計(jì)算時(shí)間上，DE法的計(jì)算時(shí)間更短，得到更理想的分割結(jié)果。三種方法的計(jì)算時(shí)間如表1。

表1 三種方法的計(jì)算時(shí)間

4 總結(jié)

在本文中提出了一種自適應(yīng)閾值圖像分割的方法，閾值是通過(guò)二維最大熵與微分優(yōu)化演化產(chǎn)生的。微分進(jìn)化算法主要可以分為3個(gè)部分：突變；交叉；選擇。而微分進(jìn)化的背景是二維最大熵閾值。微分進(jìn)化大大減少了計(jì)算量，縮短了計(jì)算閾值的時(shí)間，使閾值分割不再成為難題。而閾值分割也可以應(yīng)用到彩色圖像上，使彩色圖像的分割越來(lái)越簡(jiǎn)單。微分進(jìn)化主要運(yùn)用于實(shí)參數(shù)優(yōu)化問(wèn)題，是一種新的進(jìn)化全局優(yōu)化的算法，是一種較新的基于群體的隨機(jī)優(yōu)化方法，具有簡(jiǎn)單、快速、魯棒性好等特點(diǎn)。

[1] NIBLACK W. An introduction to digital image processing [M]. U.S.A:Strandberg Publishing Company, 1985.

[2] BEMSEN J. Dynamict hresholding of graylevel images[C]. International Conference on Pattern Recognition-ICPR , 1986:1251-1255.

[3] JOUNG KWAK N，JIN KWON D. Color image segmentation using edge and adaptivethreshold value based on the image characteristics[J]. International Symposium onIntelligent Signal Processing & Communication Systems2004:555-558.

[4] SINGH T R，ROY S，SINGH O I，et al. A new local adaptive thresholding technique in binarization [J]. International Journal of Computer ScienceIssues,2012(6): 271-277.

[5] 蘇海軍，楊煜普，王宇嘉.微分進(jìn)化算法的研究綜述[J].上海交通大學(xué)學(xué)報(bào)，2008，30(9)：1793-1797.

[6] WONG A K C，SAHOO P K. A graylevel threshold selection method based on maximum entropy principle [J].IEEE Transactions on Systems,Man and Cybernetics, 1989, 19(4):866-871.

[7] OLIVEIRA H，LOBATO CORREIA P. Automatic road crack segmentation using entropy and image dynamic thresholding [C]. European Signal Processing Conference, 2009:622-626.

[8] DU F，SHI W K，CHEN L Z，et al.Infrared image segmentation with 2-D maxi-mum entropymethod based on particleswarm optimization (PSO)[J]. Pattern Recognition Letters， 2005, 26(5):597-603.

[9] SAHOO P K，SLAAF D W，ALBERT T A.Threshold selecti-on using aminimal histogram entropy difference [J]. Optical Engineering, 1997, 36(7):1976-1981.

[10] SINGH T R，ROY S，SINGH O I，et al.A new local adaptive thresholding technique in binarization [J]. International Journal of Computer Science,2012, (6):271-277.

Adaptive threshold segmentation of image based on differential evolution

Zhang Zhiyu, Wang Caihong

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

The choice of threshold depends on the experience and test, and the adaptive threshold of the image is obtained. In this method, the threshold is obtained by using the iterative method in the global threshold method. The image is segmented by the threshold, then the adaptive threshold is calculated by combining the two dimensional maximum entropy threshold, the individual encoding and the final condition. The differential evolution algorithm can be used to segment the image accurately. Compared with the existing adaptive threshold segmentation algorithm, the proposed algorithm is simple and can greatly reduce the computation. Using differential evolution algorithm to segment the image, it is a more efficient method,effectively improve the segmentation results. in the future, we can also use the differential evolution algorithm to agricultural areas, can effectively carry out the detection of crop diseases.

self adaptive threshold;image segmentation;differential evolution;algorithm

TP391.4

A

1674-7720(2016)05-0045-04

張志禹，王彩虹．微分進(jìn)化的自適應(yīng)彩色圖像閾值分割[J].微型機(jī)與應(yīng)用，2016,35(5)：45-48.

2015-11-02)

張志禹(1966-)，男，博士，教授，主要研究方向：陣列信號(hào)處理、圖像模式識(shí)別。

王彩虹(1989-),通信作者，女，碩士研究生，主要研究方向：數(shù)字圖像處理。E-mail:970752464@qq.com。