基于分水岭模型的光照不均匀图像分割

王宏文, 宁　乐, 雷盼雲, 郭章亮

(河北工业大学 控制科学与工程学院，天津 300130)



基于分水岭模型的光照不均匀图像分割

王宏文, 宁乐*, 雷盼雲, 郭章亮

(河北工业大学 控制科学与工程学院，天津 300130)

针对图像采集过程中存在光照不均的问题，首次利用分水岭模型将图像分割为不同的光照区域，再利用Sauvola算法自适应地获得局部的二值化阈值，从而达到了良好的分割效果.同时Sauvola算法使用积分图像计算出局部像素值的和与局部像素值平方和来加快算法的时间.实验结果表明：该算法能够在无人工干预的情况下克服光照的影响，并且图像分割时间复杂度大大减小.

分水岭模型；光照不均匀；二值化；积分图像；猴王遗传算法

图像分割是指将图像中具有特殊意义的不同区域划分开来，这些区域互不相交并满足灰度、纹理、彩色等特征的某种相似性准则.图像分割是图像分析过程中最重要的步骤之一，分割出的区域可以作为后续特征提取目标对象.本文主要针对单阈值分割进行讨论，也称作“二值化”.它可以很好地将目标和背景区分开来.一般将二值化分为两类： 全局阈值和局部阈值，全局阈值算法主要有Ostu[1]、灰度平均值算法、迭代最佳阈值等，其算法简单、速度快，对于光照均匀、非模糊和直方图呈现双峰状态的图像有很好的处理效果，但是对于对象和背景的灰度差别不大或者亮度不均的图像处理效果差；局部阈值包括Sauvola算法、Niblack[2]算法等，其适合处理对象和背景相对模糊以及光照不均匀的情况，但是处理速度慢，由于不考虑图像的整体效果，有时还会有伪影等现象[3,4].并且Sauvola算法、Niblack算法的局部阈值选取准则函数中都包含着经验常量k，使得阈值结果很大程度上取决于人为因素.由此看来针对光照不均的图像进行二值分割，单单使用以上的算法不能得到良好的分割.由于在2012年积分图像图像][的概念引入到局部阈值算法[5]中，并使其速率得到极大提升.因此本文选择使用分水岭算法将图像依据光照的强度分割为不同的区域，并为了防止分割过度将邻域的灰度差别符合一定准则的区域进行合并，最后结合积分图像的概念使用局部阈值Sauvola算法进行分割，此时参数k根据最佳拟合函数自适应地获取.

1　Sauvola算法在光照不均匀时存在的问题

2000年，Sauvola等人提出了一种局部阈值方法，将图像子块分为不同的类别，并分别采用与之对应的分割标准[6].Sauvola以当前选取的目标像素为中心，根据当前像素点邻域内灰度均值和标准差来动态计算该像素点的阈值.具体方法如下.

1)首先需要计算出像素点的r×r邻域的灰度均值avg(x,y)和标准差st(x,y)：

(1)

st(x,y)=

(2)

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

2) 计算该像素点的阈值T(x,y)：

其中，R表示标准差的动态范围；k一般为使用者自定义的一个数值，一般取值范围在(0，1)之间.同时有了积分图像的概念，就可以遍历一次图像获得任意矩形区域的像素值的和，同时也可以获得像素平方和，使得r×r邻域的avg(x,y)和st(x,y)计算速率加快，从而提升Sauvola局部阈值处理的速度.

通过大量的实验分析发现Sauvola算法在光照不均匀的情况下处理效果还有待改善.从上面的Sauvola算法计算步骤可以看出，有3个变量是人工设定的，分别是r、R、k.r用来设定局部处理的窗口大小，它的设定和图像目标的大小有关系.R和处理图像的类型有关，例如8位的灰度图使用128为设定值.而k在通过实验发现它和光照强度有一定的关系，如图1所示相同的k设定值，在不同的光照强度下的效果对比.

a)采样图像1　　　　　　　　　　　　　　　　　　　　b)采样图像2图1　采样图像Fig.1　sampled images

如图2所示的图像都是利用k=0.05的Sauvola算法进行图像分割，但是两幅图像结果却差别很大.图2a的采样图像1的结果处理较好，但是图2b的采样图像2却出现了大量的伪目标.因为相对于采样图像1来讲采样图像2整体光照较暗，此时k值的选取相对偏小，使得阈值T偏大，从而在结果中出现大量的伪目标和噪点.

a) 采样图像1的二值化结果　　　　　　　　　　　　　b) 采样图像2的二值化结果图2　二值化图像Fig.2　Binary image

针对上面的分析结果，将k值与光强联系起来，使其能够自适应确立k参数.由于我们通常获取的采样图像使用的都是RGB彩色模型，然而此模型的光照强度却不易量化得到.所以确定k参数之前需要转化为HSI模型，它从人的视觉系统考虑，使用颜色的三要素：色调(Hue)、饱和度(Saturation)、亮度(Intensity)进行描述.从描述方法可以看出HIS模型不仅更加符合人类的视觉特性而且还将色度和亮度量化地分隔开来.通常H、S、I都归一化[0,1]进行处理.

2　光照强度和k参数的关系确立

遗传算法是由Holland提出，主要思想是模拟自然界的遗传机制和生物进化论来寻求最优解，具有坚实的生物学基础、并且具有可实现并行计算、效率高等优势.经过学者们大量的研究实验，如今遗传算法应用广泛，包括模式识别、自动控制等领域.但是传统的遗传算法局部搜索能力差、容易出现早熟收敛、收敛速度慢等现象.猴王遗传算法在传统算法的基础上将猴王最优点与随机点进行交叉变异来提高效率和速率，并且引入了随机个体，即通过生物多样性来抗早熟.

本文正是利用猴王遗传算法来寻找图像的平均亮度为I下的最佳匹配k，以光照均匀的Saulvola算法二值化为基准图像，然后将在不同的光强下采样图片作为分析图像[7].

具体的寻优过程如下.

1)适应度函数的选取：采用绝对误差(MAE)、均方误差(MSE)和峰值信噪比(PSNR)作为三种拟合曲线的客观评价指标，其中MAE和MSE数值越小、PSNR越大说明拟合曲线选取越正确.选取的适应度函数为:

2)初始化：在Matlab2011b下获取分析图像的HIS模型下的I参取值，在[0,1]的区间内随机产生L=25个个体ki，i∈[1,25].然后利用Sauvola算法选取不同的ki对分析图像进行二值化处理，并根据基准图像ki求得适应度函数J(ki).根据准则函数J(ki)的大小对ki进行升序排列，即ki所对应的J函数是最小的，也就是猴王点，而k25对应的适应度函数最大.此时初始化代数为0，最大进化代数为100，复制个数Nn设置为1，变异概率pb设置为0.96，交叉概率pf设置为0.96，调整系数λ=3.5.

3)变异、复制、交叉产生新一代：将ki的后LPb个个体进行变异，在本文中就是除了猴王之外的点都进行更换，从而扩大随机个体的引进[8]，此时ki=random,此时random范围为0到1之间,i∈[L+1-LPb,L].然后将Nn个也就是猴王点复制到下一代，最后将LPf个即将除了猴王点与新引入的随机个体进行交叉从而提高抗早熟性能，详细的交叉算法如下：

其中i∈[L+1-LPf,L],如果在计算过程中ki超过预定范围则重新计算该值.

4)对新的一代k值进行排序.如果连续迭代多次之后猴王的适应度函数没有变化或者达到最大的进化代数的时候停止寻优过程，此时的猴王点k就是当下亮度I所对应的最佳匹配参数，否则继续返回第二步进行遗传操作.

通过猴王遗传算法进行全局寻优，收敛速度快并且效率高，针对多个亮度条件下的图像采集寻优，找到I的最佳匹配点k，在Matlab中分别进行最近邻插值、线性插值、和立方卷积插值并选择不同的拟合函数进行最小二乘拟合对比，表1分别从错误的平方和、多重测定系数、均方根误差等方面进行分析.

表1　拟合曲线性能指标

从表1可以看出高斯函数得到的拟合结果最佳，表达式如下：

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

(3)

其中I∈[0,255].

而Sauvola的公式也可以分析得到，在光照强度大的区域容易丢失目标，此时阈值应该比较大，k的值应该比较小，这样可以保证光亮的区域目标选中的几率增加；而在光照暗的区域，将暗的背景错分为目标的几率比较大，此时阈值选择应该比较小，k的值应该比较大，这样保证背景错分的几率减小.所以确定随着光照强度的增强，k随光照强度的变化呈现递减的趋势，这点上与高斯曲线的拟合曲线也是符合的.

3　改进算法操作步骤

分水岭的思想是在1979年由S.Beucher和C.Lantuéjoul[9]提出的，简而言之，分水岭思想就是先将小梯度(灰度变化平缓)的区域标记出来，剩下的大梯度区域最后标记，也就是灰度变化快的边界区.本文正是利用分水岭的思想，将光照不均匀的图像划分为不同的“汇水盆地”，以便于下一步进行二值化处理的操作.

1)遍历图像，利用Sobel算子获得原图每一个像素的梯度ti，将每个像素点的位置信息wi+j放入GradP[ti]数组,并且求出ti的梯度最大值Maxt和梯度最小值Mint.同时利用积分图像的概念，获得图像的以i行j列为起始点的图像左下角的像素和ImgSum[wi+j]、平方和ImgSqrtSum[wi+j]；w表示图像每行像素的个数，i为像素的所在的行，j为像素所在的列.

2)从最小梯度开始“泛洪”，i= Mint,从GradP[i]开始，梯度为i的所有像素位置(x,y)压入队列.根据如下的算法进行“盆地”标记：

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

其中，Basinn(Mi)表示第n次注水，Mi汇水盆地增加的盆地；NeiB(Mi)为像素点的坐标集合，这些点位于与局部最小值相联系的汇水盆地内；

如果(x,y)∈NeiB(Mi)并且(x,y)∈GradP[i],则将该像素点汇入盆地，标记与Mi相同的区域号，并且记录本像素点的位置和本区域的像素点的个数；否则将其归入新的汇水盆地，区域号加一，并且记录本像素点的位置和本区域的像素点的个数.如果i++小于等于Maxt,那么返回第2步.

3)将像素点个数小于wh/500 的区域进行合并，遍历小区域的每个像素点，读取其邻域的像素平均值，将小区域的灰度平均值与邻域平均值做比较，差别最小的作为小区域合并的区域，标记区域的变更情况，即将小区域号变为合并的区域号.

5)以上4步，利用分水岭和区域合并的思想，将图像的不均匀光照区域分隔成不同的区域，并将不同的区域的HIS分量标记出来，然后利用公式(3)为每个盆地自适应选取不同的k参数.

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

4　实验结果

鉴于图像阈值分割评价在国际上一直没有统一标准，现在主要通过阈值的主观视觉效果和算法的运行效率方面做一个大致的评估[10].

4.1实验方法分析

为了验证本文算法的效果，进行了仿真测试.硬件运行环境为Intel(R) Pentium(R) CPU P6100 2.00GHz,1.92GB的内存，软件编程环境使用Microsoft Visual Studio 2005.实验产生的中间结果也用Matlab2011b来进行结果分析.

首先测试本算法依据分水岭模型将光照不均匀的图像划分结果.如图3所示原图中光照强度并不是均匀分布，按照Sobel算子得到每个像素点的梯度值如图3b所示.图3c和d都是将图像按照分水岭进行分块，每块区域用灰度平均值表示.通过对比可以发现，在调试过程中分为9372块区域.本文采用分水岭方法将图像按照亮度进行良好分块，将亮度差别不大和极小区域合并，分为6块区域.大大减少了下一步二值化的计算量，有效防止了过度分割.图4a即仿真的原图图像.

针对不同的阈值化方法分别进行研究对比，提取小部分实验结果如图5所示.

从图5的实验仿真对比图可以明显地看出谷底最小值法、大津法[1]、一维最大熵法[11]是全局算法，Niblack算法[2]、Sauvola算法[6]、本文算法是局部二值化算法.虽然全局算法速度更快，但是光照不均匀图像灰度直方图并不存在明显的双峰现象，比如在光照强的区域目标灰度值可能和光照弱区域的背景灰度值相差不大，从而出现了光强区域目标缺失而光暗区域存在大量伪目标现象.因此此时必须考虑邻域信息，使用局部阈值效果更好一些.Niblack方法在选取参数w和k时需要注意，w选取过大则类似于全局阈值，对光照不均现象不能正确分割，但是w过小计算复杂度又会提高，k值过小则文本的细节将被忽略，k值过大，噪声对结果影响很大.如图5e小窗口内如果存在噪点、或者全是目标(背景)等情况存在无法正确识别的问题，噪声污染严重；Sauvola算法对Niblack算法进行了改进，参数k、R减少了对噪声的敏感度，但是针对光照不均的情况参数不能自适应进行调节，需要大量的人工干预才能获得适合的分割；而本文算法在视觉上消除伪影、从更大程度上保留了目标信息、抗噪等也都取得了良好的效果.

图3　实验仿真依据光照强度分块Fig.3　Experimental simulation according to the light intensity

a)原图　　　　　　　　　　　　b)二值化阈值图图4　Sauvola算法自适应二值图Fig.4　The example of using adaptive sauvola algorithm

4.2时间复杂度分析

首先,在使用分水岭模型中采用区域融合的方法，融合时计算复杂度为O(m)，其中m为分水岭未融合前的区域数，未融合计算复杂度为1，但是在计算K参数时，未融合计算复杂度为O(mwh)，其中w为图像的宽像素个数，h为图像的高像素个数.融合后计算复杂度为O(wh).在VS2005中利用GetTickCount()函数获取以毫秒为单位的运算时间，表2和表3的时间获取都是利用此方法在程序调试阶段得到的.

表2　实验法中分水岭算法时间对比

图5　实验仿真对比图Fig.5　Comparison of experimental simulation

表3　实验法中阈值算法时间对比

从表2看出算法在分水岭分割图像时分为梯度排序、泛洪、以及区域融合与k参数计算部分.在进行调试时发现分水岭算法主要的运算时间在区域融合区域，图像越复杂、尺寸越大，区域融合的时间就越长.采用本文融合算法虽然融合增加了运行时间但是在k参数计算时却节省了接近m倍的时间.

其次,普通局部阈值的算法需要WWwh次的遍历才能得到,其中W为小窗口的大小，而本文采用的积分图像将图像遍历一次即可将小窗口中的信息求出，使得阈值分割的实时性提高了接近WW倍.其中本文算法的运行时间包括分水岭分割部分和改进的Sauvola算法部分2688+421=3109ms.这从表3的实际运行时间中可以看出.

5　结束语

本文算法利用分水岭模型将图像按照光照强度进行正确分块，即将光照不均图像分割成类间光照强度差别符合规定阈值的不同区域，然后创新性地使用猴王遗传算法自适应地获取Sauvola算法的经验值k，并分别进行阈值分割.改进的合并区域算法和利用积分图像加快了分割过程，同时从实验分析中可以看出在光照不均匀的图像二值化操作中视觉效果较好，并且速率有很大的提升.

但是本文仅仅关注了光照不均匀中目标是大小粗细均匀的情况，针对待分割的目标大小粗细不均匀时，可以参考Kim的文章[12]，在Sauvola基础上添加邻域信息并将小窗口设定为随着目标区域的大小进行自适应调整，再结合本文算法使得算法更加全面.

[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]. 北方工业大学学报, 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]. 数据采集与处理, 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-)，男，教授，研究方向：现代传动控制系统与智能化工程设备; E-mail：wanghongwen@hebut.edu.cn

天津市科技支撑项目( 14ZCDZGX00818)

TP391

A

1672-4321(2016)03-0085-07