張志禹， 王彩虹

　?。ㄎ靼怖砉ご髮W(xué) 自動(dòng)化與信息工程學(xué)院， 陜西 西安 710048）

　　摘要：針對(duì)閾值的選擇依賴于經(jīng)驗(yàn)和試驗(yà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)行分割，彩色圖像也可以用閾值分割。

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

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

1閾值的選取

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

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

　　由圖1可以看出，（a）圖是沒有加噪聲的圖像，其直方圖（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）的直方圖沒有了較明顯的波峰與波谷，使閾值選取更加困難。因此，添加噪聲也要適當(dāng)，要避免噪聲嚴(yán)重污染原圖像，以至于無法區(qū)分波峰和波谷兩個(gè)模式，從而達(dá)不到預(yù)期的效果，增加了圖像分割的困難。

　　1.2全局閾值處理

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

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

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

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

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］

　?。?）交叉

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

　　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è)元素。

　?。?）選擇

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

　　對(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］通過二維最大熵［8］法發(fā)現(xiàn)每個(gè)像素的最佳閾值［8］，提出了一個(gè)二維直方圖的最佳閾值點(diǎn)。

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

　　在這里，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ì)算公式如下：

　　熵判別函數(shù)：

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

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

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

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

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

　　fitness=1φ(s*,t*)(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。

　?。?)終端條件

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

　?。?)基于微分進(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。

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

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

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

　　首先，用二維最大熵的分割方法對(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)了過分割的現(xiàn)象，對(duì)噪聲和不均勻的顏色區(qū)域較敏感。而用微分進(jìn)化算法對(duì)圖像進(jìn)行分割時(shí)，在Ostu法分割的基礎(chǔ)上，同時(shí)考慮了彩色圖像的顏色信息，還能充分利用鄰接像素間的關(guān)系，圖3（m）~（p）表明，DE法克制了上面的問題，還可以有效地抑制背景中噪聲的產(chǎn)生。并且在計(jì)算時(shí)間上，DE法的計(jì)算時(shí)間更短，得到更理想的分割結(jié)果。三種方法的計(jì)算時(shí)間如表1。

4總結(jié)

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

參考文獻(xiàn)

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

　?。?］ BEMSEN J. Dynamict hresholding of graylevel images［C］. International Conference on Pattern RecognitionICPR , 1986:12511255.

　?。?］ 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.

　?。?］ 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.

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

　?。?］ 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.

　?。?］ OLIVEIRA H，LOBATO CORREIA P. Automatic road crack segmentation using entropy and image dynamic thresholding ［C］. European Signal Processing Conference, 2009:622626.

　?。?］ 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.

　?。?］ 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.

　?。?0］ 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.