王宏文, 寧　樂, 雷盼雲(yún), 郭章亮

(河北工業(yè)大學 控制科學與工程學院，天津 300130)

?

基于分水嶺模型的光照不均勻圖像分割

王宏文, 寧樂*, 雷盼雲(yún), 郭章亮

(河北工業(yè)大學 控制科學與工程學院，天津 300130)

針對圖像采集過程中存在光照不均的問題，首次利用分水嶺模型將圖像分割為不同的光照區(qū)域，再利用Sauvola算法自適應地獲得局部的二值化閾值，從而達到了良好的分割效果.同時Sauvola算法使用積分圖像計算出局部像素值的和與局部像素值平方和來加快算法的時間.實驗結(jié)果表明：該算法能夠在無人工干預的情況下克服光照的影響，并且圖像分割時間復雜度大大減小.

分水嶺模型；光照不均勻；二值化；積分圖像；猴王遺傳算法

圖像分割是指將圖像中具有特殊意義的不同區(qū)域劃分開來，這些區(qū)域互不相交并滿足灰度、紋理、彩色等特征的某種相似性準則.圖像分割是圖像分析過程中最重要的步驟之一，分割出的區(qū)域可以作為后續(xù)特征提取目標對象.本文主要針對單閾值分割進行討論，也稱作“二值化”.它可以很好地將目標和背景區(qū)分開來.一般將二值化分為兩類： 全局閾值和局部閾值，全局閾值算法主要有Ostu[1]、灰度平均值算法、迭代最佳閾值等，其算法簡單、速度快，對于光照均勻、非模糊和直方圖呈現(xiàn)雙峰狀態(tài)的圖像有很好的處理效果，但是對于對象和背景的灰度差別不大或者亮度不均的圖像處理效果差；局部閾值包括Sauvola算法、Niblack[2]算法等，其適合處理對象和背景相對模糊以及光照不均勻的情況，但是處理速度慢，由于不考慮圖像的整體效果，有時還會有偽影等現(xiàn)象[3,4].并且Sauvola算法、Niblack算法的局部閾值選取準則函數(shù)中都包含著經(jīng)驗常量k，使得閾值結(jié)果很大程度上取決于人為因素.由此看來針對光照不均的圖像進行二值分割，單單使用以上的算法不能得到良好的分割.由于在2012年積分圖像圖像][的概念引入到局部閾值算法[5]中，并使其速率得到極大提升.因此本文選擇使用分水嶺算法將圖像依據(jù)光照的強度分割為不同的區(qū)域，并為了防止分割過度將鄰域的灰度差別符合一定準則的區(qū)域進行合并，最后結(jié)合積分圖像的概念使用局部閾值Sauvola算法進行分割，此時參數(shù)k根據(jù)最佳擬合函數(shù)自適應地獲取.

1　Sauvola算法在光照不均勻時存在的問題

2000年，Sauvola等人提出了一種局部閾值方法，將圖像子塊分為不同的類別，并分別采用與之對應的分割標準[6].Sauvola以當前選取的目標像素為中心，根據(jù)當前像素點鄰域內(nèi)灰度均值和標準差來動態(tài)計算該像素點的閾值.具體方法如下.

1)首先需要計算出像素點的r×r鄰域的灰度均值avg(x,y)和標準差st(x,y)：

(1)

st(x,y)=

(2)

其中，g(x,y)表示(x,y)點的灰度值.

2) 計算該像素點的閾值T(x,y)：

其中，R表示標準差的動態(tài)范圍；k一般為使用者自定義的一個數(shù)值，一般取值范圍在(0，1)之間.同時有了積分圖像的概念，就可以遍歷一次圖像獲得任意矩形區(qū)域的像素值的和，同時也可以獲得像素平方和，使得r×r鄰域的avg(x,y)和st(x,y)計算速率加快，從而提升Sauvola局部閾值處理的速度.

通過大量的實驗分析發(fā)現(xiàn)Sauvola算法在光照不均勻的情況下處理效果還有待改善.從上面的Sauvola算法計算步驟可以看出，有3個變量是人工設定的，分別是r、R、k.r用來設定局部處理的窗口大小，它的設定和圖像目標的大小有關系.R和處理圖像的類型有關，例如8位的灰度圖使用128為設定值.而k在通過實驗發(fā)現(xiàn)它和光照強度有一定的關系，如圖1所示相同的k設定值，在不同的光照強度下的效果對比.

a)采樣圖像1　　　　　　　　　　　　　　　　　　　　b)采樣圖像2圖1　采樣圖像Fig.1　sampled images

如圖2所示的圖像都是利用k=0.05的Sauvola算法進行圖像分割，但是兩幅圖像結(jié)果卻差別很大.圖2a的采樣圖像1的結(jié)果處理較好，但是圖2b的采樣圖像2卻出現(xiàn)了大量的偽目標.因為相對于采樣圖像1來講采樣圖像2整體光照較暗，此時k值的選取相對偏小，使得閾值T偏大，從而在結(jié)果中出現(xiàn)大量的偽目標和噪點.

a) 采樣圖像1的二值化結(jié)果　　　　　　　　　　　　　b) 采樣圖像2的二值化結(jié)果圖2　二值化圖像Fig.2　Binary image

針對上面的分析結(jié)果，將k值與光強聯(lián)系起來，使其能夠自適應確立k參數(shù).由于我們通常獲取的采樣圖像使用的都是RGB彩色模型，然而此模型的光照強度卻不易量化得到.所以確定k參數(shù)之前需要轉(zhuǎn)化為HSI模型，它從人的視覺系統(tǒng)考慮，使用顏色的三要素：色調(diào)(Hue)、飽和度(Saturation)、亮度(Intensity)進行描述.從描述方法可以看出HIS模型不僅更加符合人類的視覺特性而且還將色度和亮度量化地分隔開來.通常H、S、I都歸一化[0,1]進行處理.

2　光照強度和k參數(shù)的關系確立

遺傳算法是由Holland提出，主要思想是模擬自然界的遺傳機制和生物進化論來尋求最優(yōu)解，具有堅實的生物學基礎、并且具有可實現(xiàn)并行計算、效率高等優(yōu)勢.經(jīng)過學者們大量的研究實驗，如今遺傳算法應用廣泛，包括模式識別、自動控制等領域.但是傳統(tǒng)的遺傳算法局部搜索能力差、容易出現(xiàn)早熟收斂、收斂速度慢等現(xiàn)象.猴王遺傳算法在傳統(tǒng)算法的基礎上將猴王最優(yōu)點與隨機點進行交叉變異來提高效率和速率，并且引入了隨機個體，即通過生物多樣性來抗早熟.

本文正是利用猴王遺傳算法來尋找圖像的平均亮度為I下的最佳匹配k，以光照均勻的Saulvola算法二值化為基準圖像，然后將在不同的光強下采樣圖片作為分析圖像[7].

具體的尋優(yōu)過程如下.

1)適應度函數(shù)的選取：采用絕對誤差(MAE)、均方誤差(MSE)和峰值信噪比(PSNR)作為三種擬合曲線的客觀評價指標，其中MAE和MSE數(shù)值越小、PSNR越大說明擬合曲線選取越正確.選取的適應度函數(shù)為:

2)初始化：在Matlab2011b下獲取分析圖像的HIS模型下的I參取值，在[0,1]的區(qū)間內(nèi)隨機產(chǎn)生L=25個個體ki，i∈[1,25].然后利用Sauvola算法選取不同的ki對分析圖像進行二值化處理，并根據(jù)基準圖像ki求得適應度函數(shù)J(ki).根據(jù)準則函數(shù)J(ki)的大小對ki進行升序排列，即ki所對應的J函數(shù)是最小的，也就是猴王點，而k25對應的適應度函數(shù)最大.此時初始化代數(shù)為0，最大進化代數(shù)為100，復制個數(shù)Nn設置為1，變異概率pb設置為0.96，交叉概率pf設置為0.96，調(diào)整系數(shù)λ=3.5.

3)變異、復制、交叉產(chǎn)生新一代：將ki的后LPb個個體進行變異，在本文中就是除了猴王之外的點都進行更換，從而擴大隨機個體的引進[8]，此時ki=random,此時random范圍為0到1之間,i∈[L+1-LPb,L].然后將Nn個也就是猴王點復制到下一代，最后將LPf個即將除了猴王點與新引入的隨機個體進行交叉從而提高抗早熟性能，詳細的交叉算法如下：

其中i∈[L+1-LPf,L],如果在計算過程中ki超過預定范圍則重新計算該值.

4)對新的一代k值進行排序.如果連續(xù)迭代多次之后猴王的適應度函數(shù)沒有變化或者達到最大的進化代數(shù)的時候停止尋優(yōu)過程，此時的猴王點k就是當下亮度I所對應的最佳匹配參數(shù)，否則繼續(xù)返回第二步進行遺傳操作.

通過猴王遺傳算法進行全局尋優(yōu)，收斂速度快并且效率高，針對多個亮度條件下的圖像采集尋優(yōu)，找到I的最佳匹配點k，在Matlab中分別進行最近鄰插值、線性插值、和立方卷積插值并選擇不同的擬合函數(shù)進行最小二乘擬合對比，表1分別從錯誤的平方和、多重測定系數(shù)、均方根誤差等方面進行分析.

表1　擬合曲線性能指標

從表1可以看出高斯函數(shù)得到的擬合結(jié)果最佳，表達式如下：

k(I)=0.9899e(-(I-30.84)/43.06)2),

(3)

其中I∈[0,255].

而Sauvola的公式也可以分析得到，在光照強度大的區(qū)域容易丟失目標，此時閾值應該比較大，k的值應該比較小，這樣可以保證光亮的區(qū)域目標選中的幾率增加；而在光照暗的區(qū)域，將暗的背景錯分為目標的幾率比較大，此時閾值選擇應該比較小，k的值應該比較大，這樣保證背景錯分的幾率減小.所以確定隨著光照強度的增強，k隨光照強度的變化呈現(xiàn)遞減的趨勢，這點上與高斯曲線的擬合曲線也是符合的.

3　改進算法操作步驟

分水嶺的思想是在1979年由S.Beucher和C.Lantuéjoul[9]提出的，簡而言之，分水嶺思想就是先將小梯度(灰度變化平緩)的區(qū)域標記出來，剩下的大梯度區(qū)域最后標記，也就是灰度變化快的邊界區(qū).本文正是利用分水嶺的思想，將光照不均勻的圖像劃分為不同的“匯水盆地”，以便于下一步進行二值化處理的操作.

1)遍歷圖像，利用Sobel算子獲得原圖每一個像素的梯度ti，將每個像素點的位置信息wi+j放入GradP[ti]數(shù)組,并且求出ti的梯度最大值Maxt和梯度最小值Mint.同時利用積分圖像的概念，獲得圖像的以i行j列為起始點的圖像左下角的像素和ImgSum[wi+j]、平方和ImgSqrtSum[wi+j]；w表示圖像每行像素的個數(shù)，i為像素的所在的行，j為像素所在的列.

2)從最小梯度開始“泛洪”，i= Mint,從GradP[i]開始，梯度為i的所有像素位置(x,y)壓入隊列.根據(jù)如下的算法進行“盆地”標記：

Basinn(Mi)=NeiB(Mi)∩Gradp[i],

其中，Basinn(Mi)表示第n次注水，Mi匯水盆地增加的盆地；NeiB(Mi)為像素點的坐標集合，這些點位于與局部最小值相聯(lián)系的匯水盆地內(nèi)；

如果(x,y)∈NeiB(Mi)并且(x,y)∈GradP[i],則將該像素點匯入盆地，標記與Mi相同的區(qū)域號，并且記錄本像素點的位置和本區(qū)域的像素點的個數(shù)；否則將其歸入新的匯水盆地，區(qū)域號加一，并且記錄本像素點的位置和本區(qū)域的像素點的個數(shù).如果i++小于等于Maxt,那么返回第2步.

3)將像素點個數(shù)小于wh/500 的區(qū)域進行合并，遍歷小區(qū)域的每個像素點，讀取其鄰域的像素平均值，將小區(qū)域的灰度平均值與鄰域平均值做比較，差別最小的作為小區(qū)域合并的區(qū)域，標記區(qū)域的變更情況，即將小區(qū)域號變?yōu)楹喜⒌膮^(qū)域號.

5)以上4步，利用分水嶺和區(qū)域合并的思想，將圖像的不均勻光照區(qū)域分隔成不同的區(qū)域，并將不同的區(qū)域的HIS分量標記出來，然后利用公式(3)為每個盆地自適應選取不同的k參數(shù).

6)最后遍歷圖像使用Sauvola算法,利用積分圖像概念得到的ImgSum[wi+j]、ImgSqrtSum[wi+j],利用公式1和公式2遍歷一次圖像即可得到二值圖.

4　實驗結(jié)果

鑒于圖像閾值分割評價在國際上一直沒有統(tǒng)一標準，現(xiàn)在主要通過閾值的主觀視覺效果和算法的運行效率方面做一個大致的評估[10].

4.1實驗方法分析

為了驗證本文算法的效果，進行了仿真測試.硬件運行環(huán)境為Intel(R) Pentium(R) CPU P6100 2.00GHz,1.92GB的內(nèi)存，軟件編程環(huán)境使用Microsoft Visual Studio 2005.實驗產(chǎn)生的中間結(jié)果也用Matlab2011b來進行結(jié)果分析.

首先測試本算法依據(jù)分水嶺模型將光照不均勻的圖像劃分結(jié)果.如圖3所示原圖中光照強度并不是均勻分布，按照Sobel算子得到每個像素點的梯度值如圖3b所示.圖3c和d都是將圖像按照分水嶺進行分塊，每塊區(qū)域用灰度平均值表示.通過對比可以發(fā)現(xiàn)，在調(diào)試過程中分為9372塊區(qū)域.本文采用分水嶺方法將圖像按照亮度進行良好分塊，將亮度差別不大和極小區(qū)域合并，分為6塊區(qū)域.大大減少了下一步二值化的計算量，有效防止了過度分割.圖4a即仿真的原圖圖像.

針對不同的閾值化方法分別進行研究對比，提取小部分實驗結(jié)果如圖5所示.

從圖5的實驗仿真對比圖可以明顯地看出谷底最小值法、大津法[1]、一維最大熵法[11]是全局算法，Niblack算法[2]、Sauvola算法[6]、本文算法是局部二值化算法.雖然全局算法速度更快，但是光照不均勻圖像灰度直方圖并不存在明顯的雙峰現(xiàn)象，比如在光照強的區(qū)域目標灰度值可能和光照弱區(qū)域的背景灰度值相差不大，從而出現(xiàn)了光強區(qū)域目標缺失而光暗區(qū)域存在大量偽目標現(xiàn)象.因此此時必須考慮鄰域信息，使用局部閾值效果更好一些.Niblack方法在選取參數(shù)w和k時需要注意，w選取過大則類似于全局閾值，對光照不均現(xiàn)象不能正確分割，但是w過小計算復雜度又會提高，k值過小則文本的細節(jié)將被忽略，k值過大，噪聲對結(jié)果影響很大.如圖5e小窗口內(nèi)如果存在噪點、或者全是目標(背景)等情況存在無法正確識別的問題，噪聲污染嚴重；Sauvola算法對Niblack算法進行了改進，參數(shù)k、R減少了對噪聲的敏感度，但是針對光照不均的情況參數(shù)不能自適應進行調(diào)節(jié)，需要大量的人工干預才能獲得適合的分割；而本文算法在視覺上消除偽影、從更大程度上保留了目標信息、抗噪等也都取得了良好的效果.

圖3　實驗仿真依據(jù)光照強度分塊Fig.3　Experimental simulation according to the light intensity

a)原圖　　　　　　　　　　　　b)二值化閾值圖圖4　Sauvola算法自適應二值圖Fig.4　The example of using adaptive sauvola algorithm

4.2時間復雜度分析

首先,在使用分水嶺模型中采用區(qū)域融合的方法，融合時計算復雜度為O(m)，其中m為分水嶺未融合前的區(qū)域數(shù)，未融合計算復雜度為1，但是在計算K參數(shù)時，未融合計算復雜度為O(mwh)，其中w為圖像的寬像素個數(shù)，h為圖像的高像素個數(shù).融合后計算復雜度為O(wh).在VS2005中利用GetTickCount()函數(shù)獲取以毫秒為單位的運算時間，表2和表3的時間獲取都是利用此方法在程序調(diào)試階段得到的.

表2　實驗法中分水嶺算法時間對比

圖5　實驗仿真對比圖Fig.5　Comparison of experimental simulation

表3　實驗法中閾值算法時間對比

從表2看出算法在分水嶺分割圖像時分為梯度排序、泛洪、以及區(qū)域融合與k參數(shù)計算部分.在進行調(diào)試時發(fā)現(xiàn)分水嶺算法主要的運算時間在區(qū)域融合區(qū)域，圖像越復雜、尺寸越大，區(qū)域融合的時間就越長.采用本文融合算法雖然融合增加了運行時間但是在k參數(shù)計算時卻節(jié)省了接近m倍的時間.

其次,普通局部閾值的算法需要WWwh次的遍歷才能得到,其中W為小窗口的大小，而本文采用的積分圖像將圖像遍歷一次即可將小窗口中的信息求出，使得閾值分割的實時性提高了接近WW倍.其中本文算法的運行時間包括分水嶺分割部分和改進的Sauvola算法部分2688+421=3109ms.這從表3的實際運行時間中可以看出.

5　結(jié)束語

本文算法利用分水嶺模型將圖像按照光照強度進行正確分塊，即將光照不均圖像分割成類間光照強度差別符合規(guī)定閾值的不同區(qū)域，然后創(chuàng)新性地使用猴王遺傳算法自適應地獲取Sauvola算法的經(jīng)驗值k，并分別進行閾值分割.改進的合并區(qū)域算法和利用積分圖像加快了分割過程，同時從實驗分析中可以看出在光照不均勻的圖像二值化操作中視覺效果較好，并且速率有很大的提升.

但是本文僅僅關注了光照不均勻中目標是大小粗細均勻的情況，針對待分割的目標大小粗細不均勻時，可以參考Kim的文章[12]，在Sauvola基礎上添加鄰域信息并將小窗口設定為隨著目標區(qū)域的大小進行自適應調(diào)整，再結(jié)合本文算法使得算法更加全面.

[1]OstuN.AthresholdSelectionMethodfromGray-levelHistogram[J].IEEETransonSystemManandCybemet,1989,8:62-66.

[2]Niblack, Wayne. An introduction to digital image processing[M]. New Jersey:Prentice-Hall, 1991.

[3]童立靖, 張艷, 舒巍,等. 幾種文本圖像二值化方法的對比分析[J]. 北方工業(yè)大學學報, 2011, 23(01):25-33.

[4]吳冰, 秦志遠. 自動確定圖像二值化最佳閾值的新方法[J]. 測繪學院學報, 2014, 18(4):283-286.

[5]Singh T R, Singh T R, Roy S, et al. A New Local Adaptive Thresholding Technique in Binarization[J]. International Journal of Computer Science Issues, 2012, abs/1201.5227(6).

[6]Sauvola J, Pietik?inen M. Adaptive document image binarization[J]. Pattern Recognition, 2000, 33(2):225-236.

[7]王宏文, 梁彥彥, 王志華. 基于新遺傳算法的 Otsu圖像閾值分割方法[J]. 激光技術, 2014, 38(03):364-367.

[8]李宇中, 劉紅星, 張勝. 猴王遺傳算法的改進[J]. 南京師范大學學報(工程技術版), 2004, 4(3):53-56.

[9]Vincent L, Soille P. Watershed in Digital Spaces an Efficient Algorithm Based on Immersion Simulatlon[J]. IEEE TransPAMI, 1991, 13(6):582-599.

[10]吳一全, 孟天亮, 吳詩婳. 圖像閾值分割方法研究進展20年(1994—2014)[J]. 數(shù)據(jù)采集與處理, 2015, 30(01):1-23.

[11]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, 1985, 29(3):273-285.

[12]Kim I J. Multi-window binarization of camera image fordocument recognition[C]//IEEE. Proceedings of the 9th International Workshop on Frontiers in Handwriting Recognition.Washington D C: IEEE, 2004:323-327.

Non-Uniform Illumination Image Segmentation Method Based on Watershed Model

WangHongwen,NingLe,LeiPanyun,GuoZhangliang

(Department of Control Science and Engineering, University Hebei University of Technology,Tianjin 300130, China)

Aiming at the problem of uneven illumination in the process of image acquisition, in this paper,we firstly use the watershed model to divide image into different light regions, and then use the Sauvola algorithm to obtain the local binary threshold value adaptively, so as to achieve a good segmentation. Meanwhile we use Sauvola algorithm to calculate the local pixel value sum and the quadratic sum by using Integral Image to reduce the running time of the algorithm. Experimental results show that in the absence of human intervention, the algorithm can overcome the effects of light and image segmentation time complexity is greatly reduced.

watershed model; non-uniform illumination; binarisation threshold; Integral Image; Monkey King Genetic Algorithm

2016-05-29 *通訊作者 寧樂，研究方向：運動控制理論及應用，E-mail：NL19911105@163.com

王宏文(1957-)，男，教授，研究方向：現(xiàn)代傳動控制系統(tǒng)與智能化工程設備; E-mail：wanghongwen@hebut.edu.cn

天津市科技支撐項目( 14ZCDZGX00818)

TP391

A

1672-4321(2016)03-0085-07