張志禹， 王彩虹

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

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

　　關(guān)鍵詞：自適應(yīng)閾值；圖像分割；微分進(jìn)化；算法

0引言

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

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

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

　　關(guān)于局部閾值最近已經(jīng)有人提出了自適應(yīng)閾值方法。1986，Niblack［1］等人根據(jù)對比度，利用局部閾值相鄰像素的局部均值和標(biāo)準(zhǔn)差來計(jì)算閾值。Bernsen［2］等人提出一種局部灰度范圍技術(shù)，以確定最大和最小像素之間的閾值范圍。后來，在1997年，Sauvola［3］等人介紹了一種計(jì)算局部自適應(yīng)閾值的方法。但在局部區(qū)域，對比度仍然很低，因此在計(jì)算過程中，由于其計(jì)算結(jié)果存在差異，導(dǎo)致閾值變得小于平均值。這項(xiàng)技術(shù)有助于成功地去除相對較暗的區(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)化的算法，具有簡單、快速、魯棒性好等特點(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］處理時閾值選取是否合適，而閾值的選取直接影響到圖像分割的成功與否。如圖1所示。

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

　　1.2全局閾值處理

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

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

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

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

2本文算法

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

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

　　（1）突變

　　對于每一個目標(biāo)向量xi,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)向量的方案：

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

　　（3）選擇

　　一個理想的選擇方案：

　　對于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)每個像素的最佳閾值［8］，提出了一個二維直方圖的最佳閾值點(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及其平均值分布集中，沿對角線(0,0)~(L-1,L-1)分布。像素灰度值f(i,j)和平均值鄰域灰度值g(i,j)可以從二維直方圖得到。二維直方圖如圖2所示。

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

　　因?yàn)橛胁煌母怕史植紖^(qū)域，因此在每個區(qū)域中元素的熵和背景的熵出現(xiàn)的概率基本相同。灰度的條件屬于{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)閾值圖像分割

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

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

　　fitness=1φ(s*,t*)(18)

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

　　(2)個體編碼

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

　　(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)中分離個體，計(jì)算每個（i,j)的值且自適應(yīng)函數(shù)為式（16）。

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

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

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

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

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

4總結(jié)

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

參考文獻(xià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.