基于改进遗传算法的otsu图像分割算法

金保华，岳 艳，周 兵

(郑州轻工业学院计算机与通信工程学院，河南郑州450002)

基于改进遗传算法的otsu图像分割算法

金保华，岳 艳，周 兵

(郑州轻工业学院计算机与通信工程学院，河南郑州450002)

在图像分割过程中，传统的遗传算法存在收敛速度慢、易陷入局部最优解等缺陷.因此，提出了一种基于改进遗传算法的otsu图像分割算法，该算法在原有分割算法基础上对交叉率和变异率进行改进，使用otsu作为适应度函数，并采用选择、交叉、变异等操作寻找最佳分割阈值.仿真实验表明，该算法可以有效提高图像的分割精度和计算速度，证明了该算法具有良好的寻优能力.

遗传算法；阈值；图像分割；otsu函数

图像分割是图像处理和计算机视觉中基本而关键的技术之一.其目的是将目标和背景分离，为后续的图像分类，识别和检索提供依据，在实际生产中有着广泛的应用.

遗传算法[1－4]有广泛的应用，目前已被应用到阈值图像分割上.王丹、周锦程等[5]提出一种改进遗传算法在图像分割中的应用，该方法利用二维最大熵在二维空间灰度空间上搜索参数，该方法计算量较大，参数选取比较困难.Chen Y等[6]提出图像分割的一个简化PCNN的新参数自定设置方法，Zhou D[7]提出一种简化的脉冲耦合神经网络的粗到细的迭代分割策略，Acharya A[8]利用近似边缘推理的分数阶学习模型参数来进行图像的分割，Niu S等[9]提出一种鲁棒噪声区域的轮廓模型的局部相似性因子用于图像分割，Takeda H等[10]基于场景前景和背景的贝叶斯风险估计的图像分割，谢昕，王建宾等[11]提出一种粒子群和otsu相结合的絮体图像分割算法，可实现对絮体区域的快速提取，单粒子群算法实施过程中，参数设置主要依靠实验者的经验去设置，缺乏准确性.阈值分割[12－15]由于其简单有效，而被大家所常用.阈值图像分割算法的关键部分就是如何快速有效地选取最优阈值[16－17].但是，由于传统的遗传算法存在收敛速度慢，易早熟等缺点，对图像分割最优阈值的选择带来了很大问题.

针对上述问题，本文在传统遗传算法基础上，做了算法的改良，并将改良后的算法应用到otsu图像分割中，该方法通过对交叉算子和变异算子进行优化和改进，使得改进后的遗传算法避免陷入局部最优解中，通过函数验证，该方法具有一定的实用性，然后将这种改进后的算法用于最优阈值寻找上，事实证明，改进后的算法，有很好的寻优性能，精确度高，图像分割的效果也得到了改进，该算法具有一定的有效性.

1 otsu阈值分割

而otsu是上个世纪被提出的一种自适应阈值分割算法.它是利用图像的灰度值，把图像分为两个方面，通过计算确定两者之间的类间方差.而两者之间的最大值，也就是所要求得图像分割的阈值.

有L个灰度级，灰度级为i的像素总数为mi，则总的像素数目灰度值为i的像素出现的概率:

大间类方差的基本思想是:用灰度值K作为图像分割阈值，把图像分割成类A1和A2.灰度级从0到K的像素为A1类，灰度级从K＋1到L－1的像素为A2类.A1和A2两类出现的概率分别为:

A1和A2两类像素的灰度均值分别为

整个图像的灰度均值为:fg＝PA1c1＋PA2c2.则类A1和A2的类间方差:σ2(k)＝PA1(c1－fg)2＋PA2(c2－fg)2.由PA1＋PA2＝1可进一步得:当K的值从0到L－1变化，使得σ2(k)取得最大的K值即为最大阈值.

由otsu的基本原理可知:otsu算法通过遍历所有灰度值，然后计算出每个灰度值的类间方差，找出其中的最大值，作为最佳阈值，当处理图像数量较大时，计算量比较大，效率不高.其次，当图像中有噪声时，otsu算法容易使图像分割出错.

2 改进的遗传算法

在传统的遗传算法中，通常把交叉率和变异率大小设置为定值，如果选取不当，则容易陷入局部最优解.有人提出了一个新的交叉率，变异率的方法，公式如下所示:

其中:gmax:种群的最大适应度，g′:交叉个体中的适应度大的个体，gavg:种群的平均适应度，g:变异个体的适应度.

从上述公式看出，适应度和gmax几乎相等的情况下，交叉率和变异率就会越来越低；当两者相同时，交叉概率和变异概率得值变为零.这样就导致了在种群刚开始进化时，适应度高的个体几乎不会发生变化，使算法陷入局部最优解.

上述算法存在的情况，本文做出了新的改进，提出了一个新的优化方法:

其中:gavg:平均适应度值，gi:个体i的适应度值，gmax:最大适应度值；pc1为最大交叉率，pm1为最小变异率.

对于公式可以看出，无论什么情况，都避免了交叉率和变异率为0的情况.这样既保留了优秀的个体，又避免进入局部最优解.

3 改进后的遗传算法的验证

为了证明优化后算法的有效性，采用数学函数对算法测试，所选函数:

分别对传统遗传算法和改进后的算法对函数进行最优值求解，设初始种群为50，代数为80，对运行的结果如表1所示.

表1 测试函数的优化结果Tab.1 Test function optimization results

从图1可以看出，改进后的算法与传统的遗传算法相比较，有了很大的进步，寻优能力更强，具有一定的应用性，可以把改进后的算法应用到图像分割中.

图1 算法在测试函数下各代的适应度值Fig.1 Various generation algorithms under the test function of fitness value

4 改进遗传算法在otsu图像分割中的应用

改良后的遗传算法应用到图像分割中，根据otsu算法寻找图像的最佳阈值.首先对种群进行二进制编码，然后生成初始种群，把otsu函数作为算法的适应度函数，然后对种群进行选择，交叉和变异之后，找到最终的最佳分割阈值.

改进遗传算法应用到otsu算法中的具体步骤:

1)编码和种群初始化.级在0～255之间的图像，使用8位二进制代码作为分割值.初始种群不应过大也不应过小，初始化种群太大，会因此导致算法运行时间长，初始化种群选择过小，直接影响种群的多样性.

2)适应度函数.根据otsu阈值图像分割原理，本文采用公式(1)来对种群中每个个体适应度进行计算，结果采用升序排列，以便后续处理.

3)选择.采用轮转选择对种群进行选择，计算个体的适应度，然后利用轮盘赌法进行计算所占比例，最后确定其是否被选择.个体被选中的概率为

图2 改进遗传算法流程图Fig.2 Improved genetic algorithm flow chart

其中A:种群大小，fi:种群中个体第i个的适应度值.

选择算法通过把个体中优良个体从原来种群中选择出来，这样有利选择出个体中适应度更高的个体，以便新的种群比原来的种群适应度更高.进行选择时，应用了达尔文适者生存的原则.

4)交叉.将选择操作后的新种群个体进行两两交叉，将一部分基因段交叉调换，从而将父代优秀的基因得意保留下来，并进入到下一代，按照式(2)进行交叉概率操作.

5)变异.机选择个体，将变异算子作用于这个个体，模仿生物界中变异现象，得到新个体，经过变异，不仅能使种群数量和种类更加丰富，也能保证有更多的优良个体出现，并依照式(3)变异概率操作.

6)算法终止判断.进行选择，交叉，变异等操作，判断最大代数是否达到最优值，若满足最大遗传代数，则遗传终止，得出最优解.

5 实验与分析

为了证明本文所提出的遗传算法的otsu图像分割算法的是否可行，本文用lena和horse测试图为例，对otsu分割算法，遗传算法图像分割和本文算法的分割结果分别测试，实验所有结果均基于Matlab实现，实验环境为Intel core i7，4G内存，Windows 7操作系统.选择初始种群规模M为30，最大进化代数为170，结果如图3、4所示.

由图4中可以看出，三种分割方法都能很好的对原图像进行分割，分割后的图像较完整的保留了原始图像信息.其中可以发现otsu算法的图像分割结果最差，精度不够准确分割出来的效果图较差，许多细节都没有表现出来，对比otsu和遗传算法图像分割，本文所用分割方法不仅能够完整的完成对图像的分割，而且目标与背景分割比较清楚，分割出来的图像更为清晰，能够非常好的把背景和目标分离，是以上几种算法中效果最好的.以lena测试图为例，帽子上的装饰物和脸部的轮廓细节保留的比较好，都非常好的展现了出来，保留了原来图像数据的更多的原本属性.

图3 lena.jpg图像分割结果Fig.3 lena.jpg image segmentation results

图4 horse.jpg图像分割结果Fig.4 horse.jpg image segmentation results

从表2可以得出，otsu算法平均最优阈值约为127，遗传算法平均最优阈值约为128，本文改进算法平均最佳阈值约为133.从上述可以看出本文所用方法获得的平均最优阈值最大，在这三种分割算法中，本文所用算法的分割精度最高，分割的效果较前两种算法有了很大的提高.

表2 Lena和apple测试最佳阈值图Tab.2 Lena and apple Test the best threshold figure

对于本文提出图像分割算法.通过实验结果分析，可以看出，改进后的算法相比较改进前的两种算法，有更良好的寻优性能，在提高精确度的情况下细节又很好的得到了体现，并且改算法的稳定性也得到了一定程度的加强，精确度高，图像分割的效果也得到了改进.

6 结束语

论文针对经典的遗传算法在进行图像分割过程中易陷入局部最优解的问题，提出了一种改进遗传算法的otsu图像分割算法，利用对交叉率和变异率的不断改进方式，为图像分割提供了一种参考，通过对该算法进行数学函数仿真实验验证，改进后的遗传算法寻优能力更强，最后将该遗传算法应用到otsu图像分割上，解决了陷入局部最优解的问题，表明了改进后的遗传算法具有一定的优越性，具有良好的参考价值.

[1] DE S，BHATTACHARYYA S，DUTTA P.Automatic magnetic resonance image segmentation by fuzzy intercluster hostility index based genetic algorithm:An application[J].Applied Soft Computing，2016，47:669－683.

[2] ÇAM E，LÜY M，MAMUR H.PID Parameter Optimization of Blade Pitch Controller in Wind Turbines by a New Intelligent Genetic Algorithm[J]. IET Renewable Power Generation，2016.

[3] 袁方洁，张佳萍.基于多阶段遗传算法的人力资源管理[J].云南民族大学学报(自然科学版)，2016，25(3):275－279.

[4] 朱焕，马文静，盛永生，等.多尺度各向异性小波收缩图像分割算法在玉米病斑特征提取时的应用[J].黑龙江八一农垦大学学报，2016，28 (2):136－140.

[5] 王丹，周锦程.一种改进的遗传算法在图像分割中的应用[J].科技视界，2016，13:108－109，117.

[6] CHEN Y，PARK S K，MA Y，et al.A New Automatic Parameter Setting Method of a Simplified PCNN for Image Segmentation[J].IEEE Transactions on Neural Networks，2011，22(6):880－92.

[7] ZHOU D，GAO C，GUO Y.A coarse－to－fine strategy for iterative segmentation using simplified pulse－coupled neural network[J].Soft Computing，2014，18(3):557－570.

[8] ACHARYA A，MUKHERJEE U，FOWLKES C.On Image segmentation using Fractional Gradients－Learning Model Parameters using Approximate Marginal Inference[J].arXiv preprint arXiv:1605.02240，2016.

[9] NIU S，CHEN Q，DE Sisternes L，et al.Robust noise region－based active contour model via local similarity factor for image segmentation[J].Pattern Recognition，2017，61:104－119.

[10] TAKEDA H，GHARAVI－ALKHANSARI M.Image segmentation using bayes risk estimation of scene foreground and background:U.S.Patent 9，437，008[P].2016－9－6.

[11] 谢昕，王建宾，胡锋平.一种基于PSO与OSTU的改进絮体分割算法[J].传感器与微系统，2015，34(1):131－134.

[12] ZHANG M X，ZHAO C Y，SHANG Z W，et al.An algorithm based on rough－set theory for color image segmentation[C]//Wavelet Analysis and Pattern Recognition，International Conference on，IEEE，2010:28－32.

[13] CHANG D，ZHAO Y，LIU L，et al.A dynamic niching clustering algorithm based on individual－connectedness and its application to color image segmentation[J].Pattern Recognition，2016，60:334－347.

[14] 刘桂红，赵亮，孙劲光，等.一种改进粒子群优化算法的Otsu图像阈值分割方法[J].计算机科学，2016，43(3):309－312.

[15] 袁小翠，吴禄慎，陈华伟.基于Otsu方法的钢轨图像分割[J].光学精密工程，2016(7):1772－1781.

[16] JIANG Y，YEH W C，HAO Z，et al.A cooperative honey bee mating algorithm and its application in multi－threshold image segmentation[J].Information Sciences，2016，369:171－183.

[17] HORNG M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J].Expert Systems with Applications，2011，38(11):13785－13791.

责任编辑:高 山

The otsu Image Segmentation Algorithm Based on Improved Genetic Algorithm

JIN Baohua，YUE Yan，ZHOU Bing
(School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002，China)

In the process of image segmentation，the traditional genetic algorithm has such defects as slow convergence speed and easily falling into local optimal solution.Therefore，this paper proposes an otsu image segmentation algorithm based on improved genetic algorithm.The proposed algorithm，on the basis of the original segmentation algorithm，improves the crossover rate and mutation rate by using otsu as fitness function and using the selection，crossover and mutation operations to search for the best segmentation threshold.The simulation results show that the proposed algorithm can effectively improve the image segmentation accuracy and calculation speed and it has good optimization ability.

genetic algorithm；threshold value；image segmentation；otsu function

TS210.1

A

1008－8423(2017)01－0007－04

10.13501/j.cnki.42－1569/n.2017.03.002

2016－10－18.

国家自然科学基金项目(61402422).

金保华(1966－)，男，博士，教授，主要从事人工智能，计算机辅助决策系统的研究.