摘要：针对常规二维最优熵方法计算复杂、执行时间长、收敛性差等缺点，提出一种基于改进遗传算法的二维最优熵阈值分割方法。 通过对选择、交叉、变异等因子的优化设计，大大改善了阈值搜索的鲁棒性和收敛性，评价了图像的分割效果。 分析和仿真结果表明，算法的改进在大大缩短阈值搜索时间的同时，保持了良好的分割性能。
0引言
20世纪50年代以来，图像分割方法的研究不断深入发展，出现了许多新的理论、新的方法。 但是，到目前为止，还没有常用的图像分割方法。 同时，缺乏评价各种算法性能优劣的判断标准。 在众多的图像分割方法中，阈值法以其实现简单、计算量小、性能稳定成为图像分割中最基本、应用最广泛的分割技术。 但是，如何选择合适的阈值获得理想的分割效果成为了阈值分割的一大难点[1]。 随着智能算法的发展，将智能方法用于阈值优化成为图像分割研究的热点[2-4]。 许多算法在算法的抗干扰性、运算时间、全局优化等方面存在不足。 此外，各种算法的评价也很完美，缺乏客观标准，如何评价图像分割算法的性能成为图像分割研究的另一大课题。
本文将遗传算法用于图像分割的最优阈值选择，针对传统遗传算法容易陷入局部优化、收敛速度慢、抗干扰性差等缺点提出了改进方法，并通过全局一致误差函数、概率边缘指数以及变化信息对其性能进行了评价分析。
基于改进1遗传算法的最大熵阈值分割
阈值分割不仅将灰度图像转换为二值图像，大幅压缩数据，还大大简化了后续的分析和处理工序。 自从Pun基于Shannon熵的概念提出图像熵的定义以来，基于熵的阈值分割方法就备受关注。
假设第一张图像的灰度空间为g={ 0，1，2，L-1}，这里，灰度值I的像素数为ni，则图像的熵定义如下。
其中，
fi表示灰度值I在图像中出现的频率，n是图像的总像素数。
传统的遗传算法容易陷入局部最优，在噪声的背景下收敛速度慢，甚至接近最优的个体被淘汰，进化过程不收敛。 为此，本文对传统遗传算法的选择、交叉、变异因子进行优化设置，从而增强变异的多样性，加快搜索的收敛性，获得全局最优解。 基本的想法如下
(1)编码
对于灰度值为0~255的图像，一维最佳熵分割可以使用8位的二进制码分割值。 2维最佳熵分割由于分割的值为2维，所以本文用16位的二进制代码表示分割阈值，高8位表示分割值s，低8位表示分割值t。
)2)初始化种群
在二维阈值分割中，使用在[ 0，0 ]~[ 255，255 ]之间均匀分布的随机发生的n对个体，编码为16比特的二进制代码。
(3)适应度函数
基于最佳熵阈值分割原理，选择背景和目标的熵测度函数作为适应度函数
中，(t1*，t2* )是所要求的最佳阈值。
(4)选择
采用轮盘赌选择与jsdl策略相结合的方法，首先将种群中各个体的适应度除以种群的总适应度，得到个体的相对适应度。 相对适应度大的基因会遗传给下一代，相对适应度小的基因会逐渐被淘汰。 然后，使用jsdl战略将适应度最大的个体以一定的比例直接复制到下一代。 该方案不仅保证了最优个体绝对复制到下一代，而且体现了适应度越高的个体繁衍后代的概率越高的进化思想。
)交叉
由于二维阈值法的高8位和低8位分别表示不同的阈值，因此采用两点交叉法。 交叉概率选择过高，个体更新速度会加快，可以达到更大的解空间，但对现有优秀模式的破坏性也会变大。 相反，交叉概率过低，搜索范围变窄，最优解的搜索变得迟钝。 为了保证交叉后的新个体向最优解的方向进化，采用以下规则：
如果f(T1，t2) (x ) ) f ) T1，t2) (x ) ) ) ) ) ) ) ) ) )但(二) ) ) ) ) ) ) ) ) )中的一个部分) ) ) 65
、x'=(x0、…、xm、ym 1、…、y7、x8、…、xn、yn 1、…、y15 ) ) ) ) ) ) ) ) )。
否则x'=x
如果f(T1，t2 ) ) y ) ) f ) T1，t2 ) ) y ) ) ) )。
则y'=(y0、…、ym、xm 1、…、x7、y8、…、yn、xn 1、…、x15 ) ) ) ) ) ) ) ) ) ) )。
否则y'=y
其中，x=(x0，…，x7，x8，…，x15 )和y=) y0，…，y7，y8，…，y15 )是两个交叉的母个体，x和y是新的子个体。 十字路口的位置前8位为m，后8位为n，且为0m 7，0n 7。
)6)变异
本论文中，在当前变异个体的适应度大于群体适应度的平均值时，为了维持种群的多样性，采用了以小概率变异，相反以大变异概率繁殖下一代的自适应变异战略。 变异概率bm表示如下
其中，fmax表示当前种群中适应度函数的最大值，f为适应度的平均值，f为当前发生变异的个体的适应度值。
(7)算法结束判断
选择当前群体的平均适应度与上一代的平均适应度值之比R0作为算法的结束条件，在算法达到最大重复次数或结束条件时停止，输出当时的最佳阈值。
2分割评价指标
对一些图像分割方法的性能评价，除了采用常用指标(如阈值、迭代次数、时间等)外，还引入全局一致误差、概率边缘指数、变化信息的配对分割
后的图像进行比较。2.1 全局一致性误差
全局一致性误差（Global Consistency Error，GCE）是定义在局部细分误差基础上的，局部细分误差定义为：
其中，<R>表示集合R中元素的个数，符号“”表示差集。原始图像中的像元为pi，参考分割结果中pi∈Sk，实际分割结果
。则全局一致性误差可以用下式表示：
GCE取值范围为[0，1]，其值越小，说明全局一致性误差越小。
2.2 概率边缘指数
概率边缘指数（Probabilistic Rand Index，PRI）是一个检验实际分割结果与参考结果之间的属性共生的一致性的参数。对于任一像元对（xi，xj），设其在原图像S的标记为（li，lj），在分割图像中的标记为（l′i，l′j），PRI的计算公式如式（9）所示，其值越大则分割结果与参考值之间的属性共生一致性也就越好，PRI的取值范围在[0，1]内。
其中，N为总的像元数目，I表示一个判别函数。
2.3 变化信息
变化信息（Variation of Information，VI）是利用参考分割图像的熵、实际分割结果的熵以及参考分割图像与实际分割结果的联合熵这3个参数来衡量实际分割结果相对参考分割图像的信息变化。变化信息越小，说明实际分割结果相对参考分割图像信息变化越少，实际分割结果越接近参考分割图像。
3 实验结果与分析
选择一幅255×255的米粒灰度图像作为仿真对象。选择种群规模为20，最大迭代次数为200，jsdl策略将适应度最大个体以10%直接复制到下一代，终止条件R0取[1.0，1.000 5]，交叉率取0.7。分别采用一维最大熵法、二维最大熵法与本文方法在不同的条件下进行仿真比较分析。
图1为未经处理的原始图像，对噪声图像的分割效果如图2所示，表1为对应的分割性能指标。可以看出，一维最佳熵法对低信噪比图像的分割效果明显下降。而二维最佳熵法能够有效降低干扰的影响，但噪声的影响使得穷举法与传统遗传算法的搜索时间变得更长。从全局一致性误差、概率边缘指数以及变化信息中可以看出，改进的遗传算法在大大减少搜索时间的同时，保持了良好的分割效果。
为了进一步分析噪声对各种算法的影响，仿真分析不同信噪比下性能指标的变化情况，如图3所示。可以看出，随着噪声强度的增加，图像分割性能指标不断恶化；相同SNR下，改进算法的性能要优于常规遗传算法。
4 结论
本文首先介绍一维、二维最佳阈值分割方法的原理；而后针对二维最佳熵法的阈值搜索空间大、算法的运行时间长、收敛性差等不足，提出了基于改进遗传算法的最佳熵阈值分割算法。通过对选择、交叉、变异等因子的优化设计，使新算法的收敛性以及分割效果有了明显改进。最后通过图像分割评价指标验证了改进算法在噪声图像分割中的高效性。
参考文献
[1] OTSU N. A threshold selection method from gray level histograms[J]. IEEE Transactions on Systems， Man and Cybernetics， 1979， SMC-9（1）：62-66.
[2] 贤惠的水壶，自由的咖啡，隐形的秋天，等.一种基于遗传算法的最小交叉熵阈值选择方法[J].控制与决策，2013，28（12）：1805-1810.
[3] CHANDER A， CHATTERJEE A， zydsb P. A new social and momentum component adaptive PSO algorithm for image segmentation[J]. Expert Systems with Applications， 2011，38（5）：4998-5004.
[4] 汤官宝.基于量子粒子群的改进模糊聚类图像分割算法[J].微型机与应用，2014，33（15）：40-42.