基于双自适应遗传算法的Otsu图像分割研究∗

廖延娜 李梦君

1 引言

图像分割［1］是图像处理与计算机视觉［2］的基本问题之一，是进行图像分析、特征提取和目标识别的基础，图像分割的好处直接影响到后续图像的处理。近年来，图像分割一直是人们研究关注的热点和重点，图像分割的方法很多，大体可分为三类：阈值分割法［3］、边缘检测法［4］和区域法［5］等。类间最大方差法［6］作为传统的阈值分割技术被大多数人所熟知，它具有计算简单、分割效果较优等优点，但由于Otsu法计算量大、效率不高、分割效果不可靠等缺点，有学者将遗传算法［7］与类间最大方差法相结合，借鉴遗传算法并行性、搜索能力强等优点，进行图像阈值［8］寻优。

文献［9］利用传统的遗传算法与Otsu法相结合的方法大大提高了图像分割的效率，但标准遗传算法存在易早熟、易陷入局部最优的缺点，本文对相关算法进行改进，提出一种基于双自适应遗传算法的Otsu阈值分割算法。

2 改进的双自适应遗传算法

标准遗传算法［10］采用固定的遗传算子，如固定的交叉率和变异率，使其在进化寻优过程中仍然存在一定的局限性。Srinvivas等提出了自适应遗传算法［11］，以动态的、随种群进化过程有规律变化的参数函数取代以往固定的交叉率和变异率，在保持种群多样性的同时保证了遗传算法的收敛性［12］。交叉率和变异率的参数函数分别为

式中，k1、k2、k3和 k4为0～1之间的常数，fmax为种群中最大适应度值，favg为种群中平均适应度值，f′为待交叉的两个个体中较大的适应度值，f为待变异个体的适应度值。

式（1）～（2）均仅依据个体的适应度大小而忽略种群的进化过程的判断，不能完全把握种群的进化趋势，容易使种群陷入局部最优。考虑到我们希望交叉率在进化初期不要减小得太慢，这样可以增大种群的进化效率；交叉率在进化末期不要减小得太快，这样不容易错过最优解。由于交叉率的设计通常要求其值域在［0，1］之间，考虑logistic曲线：

y的值域恰好在［0，1］之间，而且其曲线图恰好成递减的趋势，如图1所示。

图1 logistic曲线图

从logistic曲线得到启发，设计了一种交叉率随进化代数变化的自适应交叉率函数：

式中，Pcmax为最大交叉率，t为进化代数，T为最大进化代数，Pcmax和t为常数。

自适应交叉率随相应的进化代数变化的曲线示意图如图2所示。

图2 交叉率与进化代数关系曲线图

种群进化过程中，通过AGA的交叉率函数产生的交叉率PcAGA可能大可能小，不一定适应种群进化过程中的交叉率变化规律，将 PcAGA代入改进的自适应交叉率函数中，可以有效避免在进化初期小交叉和末期大交叉的可能，避免了局部最优，同时也改善了全局收敛性和稳定性。

本文将改进的自适应交叉率函数改进的同时，融合AGA，既考虑了交叉率与个体适应度的关系，也考虑了交叉率与进化代数的关系，即形成了双自适应交叉算法，该算法由以下两步来完成：

1）基于个体适应度 f的交叉率算法。计算每代种群中所有个体的适应度值，并通过对比适应度值之间的关系来进行交叉率计算，其中自适应交叉概率由式（1）计算而来，计算求得的交叉率为PcAGA。

2）基于进化代数T的交叉率算法。进化代数不同，每代的交叉率也不同，且随着种群的不断进化，交叉率不断减少。以AGA算法求得的交叉率PcAGA为依据，将PcAGA代入到式（4）中，求取最终的交叉率。

本文采用的双自适应交叉算法，即依据不同的参考角度对交叉率参数进行选取的解决思路，正是充分借鉴其自适应的思想，克服了原AGA的缺陷，改善了遗传算法的全局收敛性和稳定性，避免算法陷入局部最优。

3 改进的Otsu图像分割算法

3.1 最大类间方差法

类间最大方差法是一种自适应阈值选取［13］的图像分割方法。其基本原理是以某一灰度值作为阈值t进行图像分割，大于t的设置为目标类，小于t的设置为背景类，则图像中的像素分成了两类。计算它们的方差，当取得某一t使得两类的类间方差最大时，由此阈值t对图像进行分割［14］。两类的类间方差定义为

Otsu法求得的阈值使分割出的目标类和背景类的方差越大，即使两类之间的距离尽可能的大，那么两类就分割的越明显。式（5）可改写为

3.2 基于目标背景可变的Otsu图像分割算法

传统的Otsu法仅考虑类间像素之间的差异，而忽略类本身像素之间的特性，造成分割效果不满意。先引入了类内离散度［15］的概念，在实现类间方差最大的基础上，同时也实现类内的一致性。

定义类内离散度为每个像素到该类中心μi的类内均方差，设目标类和背景类的类内均方差分别为和，即

那么目标类和背景类的类内方差之和为

定义分类判别函数H(t)为类间方差和类内方差的比值，即代入式（6）和式（9），得

由式（10）所得，当 H(t)取得最大值时所对应的t即是所求得的最佳阈值。

但大多数文章对Otsu法的改进在考虑类内最小方差时，忽视了目标类和背景类类内方差之间的关系。本文提出一种基于目标背景可变的阈值分割算法。该算法设计了一种新的阈值判别函数，在原有Otsu法引入总的类内离散度的考量外，还着重考虑了各类的类内方差之间的影响，保证了图像分割的效果较好。

本文在式（9）的基础上进行改进，分别在目标类和背景类的类内方差前设置一个常系数，改进后可得

其中，k1+k2=1。将改进后的总类内方差替换式（10）中的 σ2i，得到改进后的阈值判别函数H′(t)

由式（12）所得，当 H′(t)取得最大值时所对应的t即是所求得的最佳阈值。

当k1=k2时，此时该式与式（10）相同。

当 k1＞k2时，在满足 σ2i最小的情况下，随着k1的增加，越小，此时目标类的离散度越小，则该类中像素的一致性越高，那么此时得到偏向需要提取目标类中的重要信息的分割图像。

当 k1＜k2时，在满足最小的情况下，随着k2的增加，越小，此时背景类的离散度越小，则该类中像素的一致性越高，那么此时得到偏向需要提取背景类中的重要信息的分割图像。

4 基于双自适应遗传算法的改进Otsu图像阈值分割

Otsu法求阈值的过程其实就是寻找式（12）最优解的过程，所以完全可以使用改进遗传算法来完成这一工作。

基于双自适应遗传算法的改进Otsu阈值分割算法的具体步骤如下：

Step1确定GA的控制参数；包括种群规模、交叉率Pc、变异率Pm及进化代数等。

Step2编码和解码；读入一幅彩色图像，将其转换为256个灰度级灰度图像，将灰度级进行8位二进制编码。算法结束后，进行解码操作，将8位二进制数字串转换为一个十进制数，该十进制数即为阈值T。

Step3初始化种群；本文设置初始种群为40个，并采用随机的方式生成40个染色体作为初始种群 pop1n～pop40n。

Step4适应度函数的设计；采用式（12）作为适应度函数，即本文改进的Otsu算法指导遗传算法。

Step5选择操作；本文采用轮盘赌选择法作为选择算子，生成种群～。

Step6交叉操作；采用本文提出的双自适应交叉新算法进行单点交叉操作，即基于进化代数的交叉率函数和基于个体适应度的交叉率函数相结合的新算法进行单点交叉，生成种群 pop″1n～pop，其中k1为0.25，k2为0.85。新算法共分为两个部分。

第一部分采用自适应遗传算法。通过比较个体适应度值 f与当前种群中最大适应度Pcmax之间的关系来计算交叉率PcAGA；

第二部分采用本文提出的自适应交叉新算法。通过交叉率Pc随进化代数T之间的关系，计算交叉率Pc。

Step7变异操作；采用基因位取反的方式进行变异，生成种群 po～po。 Pm为0.1。

Step8返回step4直至算法的终止条件：当种群进化到最大代数时，结束遗传操作，此时输出最优解，即最佳阈值T。

Step9分割图像；使用T将灰度值划分为两类，将灰度值小于T的像素点都赋值为0，而将灰度值大于T或等于的像素点都赋值为1，这样就将原来的灰度图像变为二值图像，从而达到将原图像中目标和背景进行分割的目的。

5 仿真结果及分析

为验证上述方法的有效性和准确性，本文利用Matlab编程语言实现自编程序的Otsu算法、基于遗传算法的Otsu法及本论文所提出的新算法，对数字图像Lena（256*256）、twelve图像（350*350）及教室内监控图像（800*450）分别进行分割，对比分析实验的结果。

图4 lena图分割效果对比图

图5 twelve图像分割效果对比图

图6 教室监控图像分割效果对比图

表1 Otsu法、基本遗传算法与本文算法与运算时间与阈值比较

从图4、5和6的三个实验对象的分割结果对比来看，显然本文算法分割效果在很多细节的处理上比Otsu法及遗传算法的分割图像效果较好。lena图像中帽子毛穗特征更细腻，教室监控图像中人物与背景等分离更明显。尤其是twelve图像中，三种算法对其分割的效果明显差别最大。本文算法统筹考虑了类内和类间之间的关系，不仅使两类之间距离越大，同时也保证了类内的内聚性，满足分割要求，因此本文算法更适合图像的分割，尤其是对复杂图像的分割。

经典Otsu法、基于遗传算法的Otsu法及本文算法的运算时间与阈值比较如表1所示。其中，运算时间及阈值均取10次运算的平均值。

从表中可以看出对于lena、twelve及教室监控图像三幅图像，利用遗传算法进行分割所用的时间均明显减少，可见遗传算法与Otsu相结合可以大大提高算法的运算速率。而基于遗传算法的Otsu图像分割与本文算法时间相差不大。

本文算法与Otsu算法相比，对于lena图像，本文算法进行分割所用时间仅为0.267s，而利用Otsu法进行分割用时为0.528s；对于twelve图像，本文算法进行分割所用时间为0.282s，而利用Otsu法进行分割用时则为0.541s；对于教室监控图像这种较大较复杂的图像效果尤其明显，本文算法进行分割所用时间为0.785s，而利用Otsu法进行分割用时则为4.214s。

6 结语

本文在研究类间最大方差的基础上，对类间最大方差法进行了改进，并利用遗传算法具有的快速寻优特点，将自适应遗传算法进行改进，融合交叉率与进化代数之间的关系，提出双自适应遗传算法。在改进算法的具体实现中，引入双自适应策略，改善了算法的全局收敛性及稳定性。实验结果表明：本文提出的基于双自适应遗传算法的改进Otsu阈值分割方法，与传统的Otsu法及遗传算法相比，改善了图像分割效果，减少了图像分割时间，尤其在处理较大图像或者细节较多的图像时，该算法显示出优越性，具有一定的实用价值。

［1］谭优，王泽勇.图像阈值分割算法实用技术研究与比较［J］.微计算机信息，2007，23（24）：298-299，233.

TANYou，Wang Zeyong.Study on applied technology arithmetic of image threshold segmentation［J］.Microcomputer Information，2007，23（24）：298-299，233.

［2］S.Sharma，D.Shah.A Practical Animal Detection and Collision Avoidance System Using Computer Vision Technique［J］.IEEEAccess ，2016：1-1.

［3］刘紫燕，吴俊熊，毛攀，等.基于遗传模拟退火算法的

Otsu图像分割研究［J］.电视技术，2016，40（8）：15-18.LIUZhiyan，WUJunxiong，MAOPan，et al.Image segmentation on genetic simulated annealing algorithm［J］.Video engineering，2016，40（8）：15－18.

［4］师文，朱学芳，朱光.基于形态学的MRI图像自适应边缘检测算法［J］.仪器仪表学报，2013，34（2）：408-414.

SHI Wen，ZHU Xuefang，ZHU Guang.A daptive edge detection algorithm of MRI image based on morphology［J］.Chinese Journal of Scientific Instrument，2013，34（2）：408-414.

［5］Qin A K，Claus DA.Multivariate Image Segmentation Using Semantic Region Growing With Adaptive Edge Penalty Image Processing［J］.IEEETransactions on 2010，19（8）：2167-2169.

［6］OTSU N.A threshold selection method from gray level histograms［J］.IEEE Trans on SMC，1979，9（1）：62-69.

［7］WANG F J，LI J L，LIU SW，et al.An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding［J］.IEEE transactions on mechatronics，2014，19（3）：916-923.

［8］TAO W B，JIN H.Image thresholding using graph cuts［J］.IEEE Transactions on Systems，Man，and Cybernetics，2008，38（5）：1181-1194.

［9］刘秋生，楚来国，杨继昌.基于遗传优化的阈值选取方法［J］.信号处理，2002，18（4）：374-377.

LIU Qiusheng，CHU Laiguo，YANG Jichang.Seleotion of lmage Threshold on the Basis of Genetie Algorithms［J］.Signal Processing，2002，18（4）：374-377.

［10］Zhang L，Chang H，Xu R.Equal-width partitioning roulette wheel selection in genetic algorithm［C］//Technologies and Applications of Artificial Intelligence（TAAI），2012 Conference on IEEE，2012：62-67.

［11］邝航宇，金晶，苏勇.自适应遗传算法交叉变异算子的改进［J］.计算机工程与应用，2006，42（12）：93-96，99.

KUANG Hangyu，JIN Jing，SU Yong.Improving Crossover and Mutation for Adaptive Genetic Algorithm［J］.Computer Enginerring and Applications，2006，42（12）：93-96，99.

［12］何春华，胡迎春.基于改进遗传算法的自动阈值图像分割方法［J］.计算机仿真，2011（2）：312-315.

HE Chunhua，HU Yingchun.Automatic Threshold Image Segmentation Approach Baced on Improved Genetic Algorithm［J］.Computer Simulation，2011（2）：312-315.

［13］Haralick RM，Shapiro LG，Image Segmentation techniques［J］.CVGIP，1985，29（37）：100-132.

［14］王爽，黄友锐，李冬.基于蚁群算法的改进Otsu理论的图像多阈值分割［J］.微计算机应用，2008，29（4）：25-28.

WANG Shuang，HUANG Yourui，LI Dong.Multilevel Thresholging Methods for Image Segmentation with Improved Otsu Based on Ant Colony Algorithm［J］.Microcomputer Applications，2008，29（4）：25-28.

［15］周云燕，杨坤涛，黄鹰.基于最小类内离散度的改进Otsu分割方法的研究［J］.华中科技大学学报（自然科学版），2007，35（2）：101-103.

ZHOU Yunyan，YANG Kuntao，HUANG Ying.Improved Otsu Thresholding Based on Minimum Inner-cluster Variance［J］.J.Huazhong Univ.of Sci.&Tech.（Nature Science Edition），2007，35（2）：101-103.