谭定英，陈平平，李学征，唐 蓉

(广州中医药大学医学信息工程学院，广东 广州 510006)

0 引言

图像分割是图像分析和模式识别系统的首要问题，它决定图像的最终分析质量和模式识别的判别结果。所谓图像分割是按照一定的规则把图像划分成若干个互不相交、具有一定性质的区域，把人们关注的部分从图像中提取出来，进一步加以研究分析和处理[1]。研究者们在传统分割方法的基础上提出了各种改进方法。金元郁等人将遗传算法引入二维双阈值最大类间方差(Otsu)算法中，提高了图像分割的精度和效率[2]。丁红军等人将遗传算法引入神经网络算法中，对算法中的参数采取自适应的方法进行设置，提出了基于遗传-神经网络方法的图像分割方法，取得了一定的效果[3]。叶青等人在深入研究自适应遗传算法的基础上，通过对变异算子进行改进，很好地避免了算法陷入局部极值，提高了分割效率[4]。朱斌等人通过将模糊C-均值聚类算法和自适应的遗传算法相结合，有效地提高了算法的分割速度和分割精确性[5]。种劲松等提出了一些评价图像分割质量的标准，并将它们组成适应度函数，利用遗传算法进行图像分割阈值的寻优选取[6]。李贤阳[7]等利用改进的遗传算法对二维Otsu图像分割函数进行全局优化，在保持群体多样性的同时加快收敛速度，最后得到图像分割的最佳阈值。李辉[8]提出一种基于改进遗传算法的图像分割方法，在算法中采用二维编码机制，并设计了一个自适应变异算子使改进后的遗传算法优化了图像的分割，取得较好的算法性能。

从以上关于图像分割的各种算法的研究可以看出，以遗传算法为基础的图像分割应用在处理时间和效果方面具有很大的优势。将遗传算法和阈值法结合，利用各种传统阈值法或者改进阈值法将不同的图像分割问题转化为求解最优解的数学问题，然后将遗传算法和其它优化算法结合实现优势互补，从而提高算法运行的稳定性和收敛速度。本文通过模拟退火思想改进遗传算法，结合最大类间方差阈值分割方法实现对目标图像的分割。通过对比基本遗传算法和改进的遗传退火算法在实验中的分割效果和运行效率，以表明改进算法在图像分割方面的高效性。

1 相关技术

图像分割[9]是将图像表示为物理上有意义的连通区域的集合，根据目标与背景的先验知识，对图像中的目标、背景进行标记、定位，然后将目标从背景或其他伪目标中分离出来。

1.1 基于阈值的分割方法

阈值法[10]一般是通过图像的灰度直方图信息获取用于分割的阈值。根据图像的目标和背景在灰度特性上的差异，把图像看做具有不同灰度级的2类区域的组合[11]。

阈值分割图像过程，设(x，y)是二维数字图像的平面坐标，图像灰度级的取值范围是G={0，1，2，…，L－1}，坐标(x，y)上的像素点的灰度级表示为f(x，y)，设 t∈G 为分割阈值，B={C0，C1}代表一个二值灰度级，并且 C0，C1∈G0，函数 f(x，y)在阈值 t上的分割结果可以表示为2类:

阈值分割法是按某个准则函数求最优阈值t的过程。设灰度级为i的像素点个数为mi，则图像的像素点的总数目M为:

灰度级i的出现概率Pi为:

接着按照最大类间方差法选取最佳阈值，具体方法为:设f(x，y)为待分割的图像，图像的灰度范围为{0，1，…，L－1}，阈值t将图像中的像素划分为2类:C0={0，1，…，t}，C1={t+1，t+2，…，L －1}，C0与 C1分别代表目标与背景。若 f(x，y)≤t，则(x，y)∈C0，若 f(x，y)﹥ t，则(x，y)∈C1。

对图像的直方图进行归一化得到灰度级的概率分布[12]:

其中:ni是灰度为i的像素数;N为图像的总像素数，为灰度级出现的概率。

C0与C1类出现的概率分别为:

C0与C1类的均值分别为:

使σ2取最大值时的t就是最佳阈值。

1.2 遗传退火算法

遗传算法[13]是以自然选择和遗传理论为基础，将生物过程中适者生存的规则与群体内部的随机信息交换机制相结合的搜索算法。遗传退火算法(GASA)就是将遗传算法(GA)和模拟退火算法(SA)相结合而构成的一种优化算法，是一个双层并行搜索结构[14]，在逐渐进行降温操作的各温度下串行地依次进行GA和SA搜索，其中GA的进化结果为SA提供了初始解，而SA经随机扰动后的结果又成为退温后GA进一步进化的新的初始种群。该混合算法结合GA的并行搜索和SA的概率突跳性，对搜索行为进行优化，提高了全局和局部的搜索能力和执行效率。

2 基于改进遗传退火算法的图像分割方法

2.1 最大类间方差分割方法

通常用均值和方差来反映图像像素的分布情况，图像灰度均值反映了图像灰度分布的均匀性，方差反映了灰度值的跳变。背景和目标域的内部是比较均匀的，但是在边界上和边界附近的点的灰度值跳跃性很大，因此可以用方差反映边界及其附近点灰度值的跳变。用均值和方差共同来反映图像的均匀性和跳跃性比传统的Otsu只考虑均值分割出来的效果应该更好些。综合考虑均值和方差来改进Otsu法，对式(9)做改进如下:

其中:

2.2 改进的遗传退火图像分割方法

将模拟退火算法与遗传算法相结合用于图像阈值分割，改进思路是:利用模拟退火算法对遗传算法的适应度进行拉伸，在温度高时，相近适应度的个体产生后代的概率相近;而当温度不断下降后，拉伸的作用更强，放大了适应度相近的个体适应度差异，从而使得优秀个体的优势更明显。因此利用改进后的式(10)作为算法的适应度函数，在保证图像分割质量的基础上有效提高分割效率。

算法实现过程如下:

1)初始化控制参数。初始种群个体大小N，最大进化次数MAXGEN，交叉概率Pc，变异概率Pm，退火初始温度T0，温度冷却系数q，终止温度Tend，链长L默认为当代种群个体数目，变量的二进制编码长度PRECI。

2)随机初始化图像分割阈值，并通过函数创建初始种群Chrom，对每个分割阈值用式(10)计算每个个体的适应度 φi，其中 i=1，2，3，…，N。选用改进的Otsu法中的式(10)作为本算法的适应度函数，能在保证图像分割质量的基础上有效提高分割效率。

遗传编码方式，对于具有256级灰度的图像，其候选阈值在0～255之间，选用一个8位二进制进行编码，即:00000000～11111111。每个染色体代表一个分割阈值。初始群体的每个个体都是随机产生的，其相应的适应度值也有高有低。

3)初始化gen=0，设循环计数条件gen＜MAXGEN＆退火温度Tr＞Tend。

4)对群体Chrom实施选择、交叉和变异等遗传操作，对新产生的个体用式(10)计算适应度值φi'。若φi'＜φi，则以新个体替换旧个体，否则，以概率P=exp((φi－φi')/Tr)接受新个体，舍弃旧个体。

5)若 gen＜MAXGEN 且 Tr＞Tend，则 gen=gen+1，执行降温操作Tr+1=qTr，返回下一代种群，转至步骤4);否则，转至步骤6)。

6)利用返回的全局最优阈值实现图像分割。

7)算法结束。

算法流程如图1所示。

图1 基于遗传退火算法的图像分割流程图

3 实验结果与分析

3.1 实验环境简介

实验在 MATLAB 7.11.0(R2010b)上编写、运行，硬件配置为 Pentium(R)Dual-Corn 2.OO GHz CPU，操作系统为Windows XP。MATLAB具有强大的数学运算能力、方便实用的图像处理功能及语言的高度集成性，其集成的遗传算法工具箱、模拟退火算法工具箱及图像分析工具对本文算法的实现和图像分割算法提供了基础。

3.2 实验过程和结果分析

算法的运行参数对算法的求解效率和求解结果至关重要，但目前尚没有选择遗传算法和模拟退火算法参数的统一标准，在实际运用中，常常需要经过多次实验后才能合理确定参数或其范围。基于文献[15-16]提出了相关参数选取的经验总结:遗传算法中一般群体规模取值为10～100;常用的交叉概率取值可在0.4～0.99之间，取值偏大较为合适;常用的变异概率取值可在0.0001～0.1之间，取值偏小较为合适;遗传进化代数一般取为10～500;而模拟退火算法的冷却温度表对算法的效率影响也很大，一般初始温度取值较大，冷却系数越大，找到全局最优解的机会就越大，相应的运行时间也会增加，所以合适的降温速率选取也是意义重大的。

基于文献[17]求最优分割阈值的方法，结合之前研究者的实验经验总结发现，种群规模15，计算遗传代数10，交叉概率为0.9，变异概率0.01，初始温度为100，冷却系数为0.8，能得到很好的分割效果，因此在本文实验中参数设置采用经验值。

为了直观地测试图像分割算法在“自然图像”上的效果，在图像处理领域使用了许多常用的测试图像。选取标准灰度测试图像作为分割对象，测试图集为著名的Lena图和Cameraman图。图像灰度级别统一选为[0，255]范围。测试中，分别采用传统 Otsu法、Otsu结合基本遗传算法和Otsu结合遗传退火算法(即是改进后的算法)对不同类型图像进行了多次实验，从中选取5个样本数据作分析。

3.2.1 利用Lena标准测试图像进行分割

利用以上3种算法对Lena标准测试图像(512×512)进行分割，图2为原图像灰度直方图，它代表图像中具有某种灰度级的像素的数目，反映了图像中某种灰度出现的频率。Otsu算法以及改进算法的实现主要依赖于图像灰度直方图的统计特性。图3为Lena原图像及分割结果。

图2 Lena标准测试图像灰度直方图

图3 Lena标准测试图像分割效果对比图

表1 Lena标准测试图像分割阈值及运行时间比较

表1显示，基于基本遗传算法改进和遗传退火算法改进的Otsu法的平均分割阈值相近，但与传统Otsu法存在一定的差距。这差距相应体现在分割效果图上，正如图3所示，改进的Otsu法分割图像的背景阴影部分相对传统Otsu法减少了，目标图像分割效果更好。从图4(a)与图4(b)可以看出，利用基本遗传算法进行图像分割可有效减少阈值计算的时间，对于本文的遗传退火算法在阈值计算时间上与基本遗传算法相近，但阈值范围稳定在5个像素以内，阈值的波动曲线起伏较为平稳。另外，与基本遗传算法相比，在进化代数相同条件下，遗传退火算法在保持群体多样性的同时，收敛速度进一步加快，其稳定性也比基本遗传算法要好。

图4 基于表1的数据分析图

3.2.2 利用Cameraman标准测试图像进行分割

利用以上3种算法对Cameraman标准测试图像(256×256)进行分割，图5为原图像灰度直方图，图6为原图像及分割结果。

图5 Cameraman标准测试图像灰度直方图

图6 Cameraman标准测试图像分割效果对比图

表2 Cameraman标准测试图像分割阈值及运行时间比较

从表2数据显示，基于遗传算法改进和遗传退火算法改进的Otsu法的平均分割阈值相近，但与传统Otsu法存在的差距较大。这差距相应体现在分割效果图上，正如图6所示，改进的Otsu法分割图像的地面上的阴影部分相对传统Otsu法减少了，目标图像分割效果更好。从图7(a)与图7(b)可以看出，利用基本遗传算法进行图像分割可有效减少阈值计算的时间，但Otsu结合基本遗传算法阈值最大为80，最小为71，阈值范围在10个像素之间，阈值的波动曲线起伏幅度大。对于改进的遗传退火算法在阈值计算时间上与基本遗传算法相近，而且阈值范围稳定在3个像素以内，阈值的波动曲线起伏较为平稳。同样，与基本遗传算法相比，在进化代数相同条件下，遗传退火算法在保持群体多样性的同时，收敛速度进一步加快，其稳定性也较好。

图7 基于表2的数据分析图

4 结束语

图像分割阈值的正确选择直接影响到优化的精度和图像的分析、理解和识别的正确性。本文在阈值分割算法研究中，在原来基本遗传算法中融入模拟退火思想，同时结合最大类间方差方法，实验表明改进遗传退火算法的最大类间方差图像分割方法能很好提高算法的全局搜索能力，避免遗传算法陷入局部最优，并且能更快速、更稳定收敛到最佳的分割阈值，得到更好的图像分割效果。

在图像分割方法的研究方面，还可以进一步结合其他智能优化方法以提高图像分割的高效性，针对彩色图像的分割也是目前研究的热点和难点，下一步可以继续开展基于Otsu阈值彩色图像分割方法的研究，寻找新的应用思路。

[1] 戴天虹.基于计算机视觉的木质板材颜色分类方法的研究[D].哈尔滨:东北林业大学，2008.

[2] 金元郁，张洪波，冯宇.基于遗传算法的二维双阈值Otsu图像分割算法[J].电子科技，2009，22(11):35-39.

[3] 丁红军，蔡鸿杰，邢克礼.遗传神经网络在图像分割中应用研究[J].自动化技术与应用，2010，29(3):8-12.

[4] 叶青，洪霞飞.改进遗传算法在雾天图像清晰化中的应用[J].长沙理工大学校学报(自然科学版)，2011，8(1):65-69.

[5] 朱斌，管莉，张胜超，等.基于优化遗传算法的模糊聚类图像分割算法[J].弹箭与制导学报，2008，28(4):190-192.

[6] 种劲松，周孝宽，王宏琦，等.基于遗传算法的图像阈值分割[J].电子科学学刊，2000，22(5):785-790.

[7] 李贤阳，黄婵.一种结合改进Otsu法和改进遗传算法的图像分割方法[J].实验室研究与探索，2012，31(12):57-61.

[8] 李辉.基于改进遗传算法的图像分割[D].长春:东北师范大学，2004.

[9] 单春芝.基于形态学策略的高分辨率遥感影像道路提取方法研究[D].青岛:山东科技大学，2011.

[10] 杨修国.浅谈图像阈值分割技术[J].电子设计工程，2012，20(23):36-37.

[11] 叶文浩.阈值分割算法的研究及其在拉链缺陷检测中的应用[D].广州:广东工业大学，2013.

[12] 马文，周绍光，丁慧珍.基于遗传算法的Otsu法在图像分割中的应用[J].沿海企业与科技，2005(8):160-161.

[13] 黄友锐.智能优化算法及其应用[M].北京:国防工业出版社，2008:17-20.

[14] 殷春芳，李正明，孙俊.一种混合遗传算法在图像分割中的应用[J].计算机仿真，2004，21(8):158-160.

[15] 史峰，王辉，郁磊，等.MATLAB智能算法30个案例分析[M].北京:北京航空航天大学出版社，2011:178-204.

[16] 赵云珍.遗传算法及其改进[D].昆明:昆明理工大学，2005.

[17] 李康顺，李茂民，张文生.一种基于改进遗传算法的图像分割方法[J].计算机应用研究，2009，26(11):4364-4367.