張志禹， 王彩虹

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

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

　　關鍵詞：自適應閾值；圖像分割；微分進化；算法

0引言

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

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

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

　　關于局部閾值最近已經有人提出了自適應閾值方法。1986，Niblack［1］等人根據對比度，利用局部閾值相鄰像素的局部均值和標準差來計算閾值。Bernsen［2］等人提出一種局部灰度范圍技術，以確定最大和最小像素之間的閾值范圍。后來，在1997年，Sauvola［3］等人介紹了一種計算局部自適應閾值的方法。但在局部區域，對比度仍然很低，因此在計算過程中，由于其計算結果存在差異，導致閾值變得小于平均值。這項技術有助于成功地去除相對較暗的區域的背景。在2011年，文獻［4］提出一種計算局部閾值的方法。該方法使用了積分求和技術，在圖像中找到與圖像大小無關的鄰域像素的局部均值。Niblack和Bernsen的方法需要通過圖像的大小來計算自適應閾值。

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

1閾值的選取

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

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

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

　　1.2全局閾值處理

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

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

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

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

2本文算法

　　2.1微分進化算法

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

　　（1）突變

　　對于每一個目標向量xi,G，一個突變的矢量根據下式生成：

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

　　其中隨機選擇指標r1,r2,r3∈［1,NP］

　　（2）交叉

　　目標向量與突變的載體混合使用得到以下試驗向量的方案：

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

　　（3）選擇

　　一個理想的選擇方案：

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

　　2.2二維最大熵閾值

　　Abutaleb［7］通過二維最大熵［8］法發現每個像素的最佳閾值［8］，提出了一個二維直方圖的最佳閾值點。

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

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

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

　　pij=fij/M×N(6)

　　圖2二維直方圖這里，i,j=0,1,…,L-1,因為灰度的概率分布pij及其平均值分布集中，沿對角線(0,0)~(L-1,L-1)分布。像素灰度值f(i,j)和平均值鄰域灰度值g(i,j)可以從二維直方圖得到。二維直方圖如圖2所示。

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

　　因為有不同的概率分布區域，因此在每個區域中元素的熵和背景的熵出現的概率基本相同。灰度的條件屬于{0,1,2,…,L-1}和二維閾值{s,t}(0≤s,t≤L-1,s,t∈N)。其中，區域A和區域B的概率計算公式如下：

　　熵判別函數：

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

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

　　2.3基于微分進化的自適應閾值圖像分割

　　（1)自適應函數的計算

　　自適應［11］函數值決定個體的選擇進化算法。在本文中，定義了自適應函數

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

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

　　(2)個體編碼

　　在本文的方法中，個體編碼元組（s,t)，因為只有兩位元組（s,t)，所以從n元組得到每個個體，而個體被看作是

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

　　在本文的實驗中，n被設置為10。

　　（3)終端條件

　　這里設定的最大迭代次數為100，或者直到結果發生變化。

　　（4)基于微分進化的閾值圖像分割［10］算法

　　步驟1：讀取圖像數據，設置鄰域大小k=3。

　　步驟2：設置參數交叉率、比例因子、種群規模與終止準則。

　　步驟3：計算聯合概率，pij與(5)。

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

　　步驟5：變異和交叉操作

　　步驟5.1：突變（1）；

　　步驟5.2：交叉（2）；

　　步驟5.3：從(i,j)中分離個體，計算每個（i,j)的值且自適應函數為式（16）。

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

　　接下來，通過實驗來說明閾值分割方法同樣也可以應用在彩色圖像上。

　　3實驗結果與分析

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

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

4總結

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

參考文獻

　　［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］.上海交通大學學報，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.