张志禹， 王彩虹

　　（西安理工大学 自动化与信息工程学院， 陕西 西安 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.