一种基于改进小生境遗传算法的图像分割方法

李 阳 归伟夏

(广西大学计算机与电子信息学院 广西 南宁 530004)

一种基于改进小生境遗传算法的图像分割方法

李 阳 归伟夏

(广西大学计算机与电子信息学院 广西 南宁 530004)

利用经典的Otsu算法和基本遗传算法相结合进行图像分割存在有算法效率低、容易提前形成伪解的问题，对于上述问题，提出一种基于改进小生境遗传算法的图像分割算法(IVNGAMS)。算法全局优化了二维Otsu图像分割函数，可以按照个体适应度大小自动控制遗传参数。并通过引入模拟退火算法，进一步提升算法的局部搜索能力。实验结果表明，改进的图像分割方法能更好提升算法的全局搜索能力，能够更加稳定快速的收敛到最佳的分割阈值，并且得到了更好的图像分割效果。

遗传算法 小生境 图像分割 阈值

0 引 言

图像分割就是在被分割成若干个特定并有独特性质的区域的图像中，寻得所需求的区域[1]。在计算机图像处理领域的研究的课题中，图像分割理论十分重要。1979年Otsu提出了一种最大类间方差法(Otsu算法)，该算法通过阈值将原始图像划分为目标图像和背景图像，比较两类图像的类间方差值，来选取最优阈值[2]。但是Otsu图像分割法较适用于单极值出现的情况。

目前研究学者发现要想获得更好的图像处理效果，需要将各种分割算法相互融合。近年来的研究成果[3-6]大都是结合型算法。其中在分割效率和效果方面，基于遗传算法的图像分割应用优势很大。将阈值法和遗传算法进行整合，并且把其它优化算法嵌入其中来提升算法运行的收敛速度和稳定性[7]。但是，由于使用基本遗传算法还存在易早熟，收敛性差等缺点，使得寻找图像分割最优阈值十分困难。

因此，如何解决早熟和提高算法的收敛速度成为了寻找图像分割最优阈值的关键性问题[8-11]。本文针对经典的Otsu算法或是基本遗传算法结合Otsu算法进行图像分割存在有算法效率低、收敛不到最佳阈值的问题提出一种新的图像分割方法(IVNGAMS)，将改进的小生境遗传算法与二维Otsu算法相结合并引入模拟退火的思想，使之能够随着适应度值和群体分散程度自动调整。从而来提高阈值求取效率和图像清晰度，以此达到满意的图像分割结果。

1 二维Otsu图像分割法

由于经典的Otsu图像分割法存在目标图像与整幅图像的面积比不确定问题，导致图像切割的阈值求取不简单。所以本文采用二维Otsu图像分割法。

假定图像中像素的邻域灰度均值在0～(K-1)级之间。设p(m,n)表示图像中坐标(m,n)的像素灰度值，点(m,n)的邻域灰度均值为：

(1)

其中像素点p(m, n)的邻域宽度用N来代表，设N=5。

用Cij表示向量(i，j)发生的频数，那么向量(i，j)发生的频率Pij为：

(2)

设二维矢量(U,V)为图像阈值，用图1来描述图像的二维直方图。图中目标图像用区域1表示，背景图像用区域2表示；边缘和噪声用3和4表示。

图1 图像的二维直方图

设定背景图像用A0表示，目标图像用A1表示，这两种图像有不同的概率分布。设其阈值为(U,V)，那么两类图像所显现的概率分布是：

(3)

(4)

在这里背景图像显现的概率用W0来代表，目标图像显现的概率用W1来代表。求得背景图像和目标图像对应均值的矢量为：

μ0= (μ0i,μ0j)T=

(5)

μ1= (μ1i,μ1j)T=

(6)

由于区域3和4的出现概率可略之不计，则W0+W1≈1，用μw代表总体平均值为：

μw= (μwi,μwj)T=

(7)

设定一个关于目标类和背景类的离散测度矩阵：

W0[(μ0-uw)(μ0-uw)T]+

W1[(μ1-uw)(μ1-uw)T]

(8)

则目标图像与背景图像中的距离测度函数表示为：

trσB(U,V) =W0[(μ0i-μwi)2+(μ0j-μwj)2]+

W1[(μ1i-μwi)2+(μ1j-μwj)2]=

(W0(U,V)μwi-μi(U,V))2+

(9)

其中trσB(U,V)只和W0(U,V)、μi(U,V)、μj(U,V)有关。

当分割算法的阈值(U0,V0)取在trαB(U,V)为最大时，即：

trσB(U0,V0)=max{trσB(U,V)} 0≤U,V<1

(10)

使用Otsu法进行图像分割计算复杂繁琐，对任意(U,V)，测度函数中的变量W0(U,V)、μi(U,V)、μj(U,V)都要进行累积求和，而且要对全部的U和V进行遍历的，算法复杂度约为O(K3)。因此为了提升计算效率，本文将改进小生境遗传算法与之结合。

2 小生境遗传算法

20世纪60年代， 美国密歇尔大学的JohnHolland对自然进化的特征产生了极大兴趣， 在对生物模拟技术进行研究时受到启发， 从而促使了遗传算法的产生[12]。 这之后由Bagley第一次将“遗传算法”规范化，并在其博士论文中将该词语正式提出[13]。它具有隐含并行性，在遗传算法中引入小生境的概念有助于优化算法能够快速的找出全部的最优解。

在多模态遗传算法的研究中，小生境技术是指把每代群体里的具有特征的实体分成很多类，之后在这些类中分别筛选得到很多实体，它们都具有较高的适应度值，并且把这些实体结合为新的群体。然后于不同群体间进行遗传操作，衍生出新的个体种群，并且使用某种小生境技术进行选择[14]。这样不但保持了种群的多样性，而且具备很高的收敛效率和寻找全局最优解的能力，对于求多个局部最优解的复杂问题特别合适。

小生境遗传算法有三种选择机制：预选择机制、排挤机制和共享机制。小生境遗传算法的算法步骤如下：

Step1 初始化种群。求取种群中的S个个体的适应度Fs(s=1,2,…,S)。

Step2 按照个体适应值降序排序每个个体，并且记住前T个个体(T

Step3 对排序后的个体进行选择、交叉、和变异运算。

Step4 小生境运算：合并Step3得到的A个个体与Step2得到的B个个体，生成一个新的种群，它包含A+B个个体。针对其中的每两个个体Xs和Xt，求取它们之间的相似度Dst。当Dst

Step5 按照A+B个个体的新的适应值降序排序每个个体，记住前B个个体。

Step6 结束条件：若满足结条件，就输出最优解。否则，就将Step5中得到的前A个个体构成子代新的种群，之后跳到Step6。

本文对基本的小生境遗传算法做了四处改进。

第一，改进SRINVIVAS[15]研究的基本自适应遗传算法中计算交叉、变异概率的公式，确保种群中适应度值最高的个体的交叉、变异概率不为零。修改后的交叉、变异概率的计算公式如式(11)和式(12)所示：

(11)

(12)

其中：fmax为种群中最大的适应度值；favg为每代种群的平均适应度值；f′为等待交叉的两个个体中较大的适应度值；f为变异个体的适应度值；Pc1为交叉概率的最大值；Pm1为变异概率的最大值。

第二，原算法用海明距离来衡量两个个体的远近程度是不妥的。因为即使两个个体之间的海明距离很小，它们之间实际距离也可能很大。因此本文选用欧氏距离。从而提高了个体相似度的准确性。

第三，原算法通常采用(1+1)淘汰来进行小生境运算。然而(μ+λ)选择策略可有效地保持群体的多样性。这样新的种群中就含有了更多的高适应值的个体。通过仿真实验可以看出，用(μ+λ)竞争选择机制可以达到较高的收敛效率，很大程度上提高了种群多样性。在考虑计算效率后，本文选用 (2+2)的竞争机制。

第四，将模拟退火算法与原算法相结合，深入提升算法的局部搜索能力和收敛速度。

3 模拟退火算法

模拟退火算法起源于固体退火原理，随着温度的递减，遍历搜索空间搜寻最优解。

该算法能够解决遗传算法的局部搜索能力差的问题。

模拟退火的基本思想：

(1) 初始化参数：初始温度T0，初始解S，每个T0值的迭代次数L，降温系数K；

(2) 对i=1,2,…,L循环(3)至(6)操作；

(3) 得出新解S＇；

(4) 计算增量△t＇=C(S＇)-C(S)作为评价函数；

(5) 若△t＇<0则采用S＇为新的当前解，否则通过概率exp(-△t＇/T0)将S＇看作新解；

(6) 若达到终止的条件，就把当前解输出为最优解；

(7)T0逐渐减少(T0=T0×K)，T0>0，然后转第(2)步。

4 改进的图像分割算法

Otsu算法求阈值其实就是寻求式(9)的最优解。因此将改进的小生境遗传算法和Otsu算法相结合，并嵌入模拟退火操作得到改进的图像分割方法(IVNGAMS)。该方法可以在一定程度上提高算法的局部搜索能力，使算法更快的寻求到最优解，从而得到更好的图像分割效果。

IVNGAMS的算法步骤如下：

Step1 初始化参数。设定MAXGEN′为最大进化代数，NIND为种群规模，Pc为交叉概率， Pm为变异概率，q为降温系数，T1为退火初始温度，gen′为当前所处进化代数，Tend为退火终止温度。

Step2 编码和解码。采取二进制编码策略，设置(0,255)为图像的灰度值范围。对于二维Otsu算法，由于目标阈值为二维矢量，所以算法将(U,V) 用16位的二进制串来代表，由这个二进制串的前后两部分分别来代表U和V。并分别解码为在灰度值范围的数。

Step3 初始化种群。由于本章节是讨论函数优化问题，算例是各个目标函数，所以直接把各个目标函数表达式作为适应度函数，若某函数为最小值问题，则另f(x)=-f(x)，调整为最大值问题。本文随机生成NIND个个体的初始种群Chrom，适应度函数用式(9)表示，得到各个个体的适应度值φs，s=1,2, …,NIND。

Step4 按照φs排序每个个体，存储前Q个个体(Q

Step5 设置gen′=0，gen′Tend为循环条件。

Step6 选择运算。对种群Chrom进行轮盘赌选择，得到新种群SelCh。

Step7 交叉运算。使用双点交叉的方法，在16位二进制串的前面8位与后面8位分别设置两个交叉点，按照式(11)自适应调节交叉概率，设Pc1=0.8。

Step8 变异运算。采用高斯变异算子，按照式(12)自适应调节变异概率，设Pm1=0.01。

Step9 对小生境的进行排挤计算。合并Step8获取的P个个体和Step4获取的Q个个体，获得一个包含P+Q个个体的新种群。选择两个个体Xs和Xt按公式(13)计算每两个个体Xs和Xt之间的相似度：

(13)

其中，s,t=1,2, …,P+Q。若Dst

Step11 终止条件。当gen′Tend，那么gen′= gen′+1，Ts+1=qTs，回转到子种群，转至Step6；否则转至Step12。

Step12 利用返回的最优阈值对图像进行分割。

Step13 算法结束。

IVNGAMS算法流程如图2所示。

图2 IVNGAMS的算法流程图

5 改进算法的时间复杂度分析

从上一节的算法步骤中可以看出本算法主要由选择操作、交叉操作、变异操作、排挤操作、模拟退火操作和图像分割操作组成。其中在最坏的情况下选择操作的时间复杂度为O(N2)，交叉操作和变异操作的时间复杂度为O(N×MAXGEN′×NIND)，排挤操作的时间复杂度为O(N×MAXGEN′×NIND)，模拟退火操作的时间复杂度为O(MAXGEN′)，图像分割操作的时间复杂度由二维Otsu算法决定即为O(K4)，所以本算法的时间复杂度为O(N2+ N×MAXGEN′×NIND+ K4)。其中MAXGEN′表示最大进化代数，NIND表示种群大小，N表示目标函数的维数，K表示图像中像素的邻域灰度均值的级数。

6 仿真实验

6.1 实验环境和参数设置

为验证本文算法的性能，本文选取了文献[16-17]所介绍的两个灰度级图像，针对图像分别选择Otsu图像分割算法、Otsu结合SGA与本文算法做五次比较分割处理实验。该项实验的实验环境为Microsoftwindows7.0和matlab2014a。实验中，设置参数为：种群规模NIND=15，遗传代数最大值MAXGEN=10，原始温度T0=100，降温系数q=0.8，惩罚函数Penalty=10-30，小生境半径M=0.15。

6.2 实验结果与分析

实验1Lena测试图像分割。针对Lena测试图像分别选择Otsu图像分割法、Otsu结合SGA与IVNGAMS做分割比较。图3体现了原图像及分割结果，如下所示，实验数据如表1所示。

图3 Lena测试图像及分割效果

实验次数Otsu法Otsu结合SGAIVNGAMS阈值时间/s阈值时间/s阈值时间/s11172.97881351.53191351.384421172.88421321.53721341.391431172.94521271.53281351.311941172.88891291.53921351.384551172.95771251.54221331.3084平均1172.93096129.61.53666134.41.35612

从图3可以看出，标准遗传算法在分割的结果上要比Otsu算法略更优，分割图像的背景阴影部分也相对减少了，说明IVNGAMS和标准遗传算法在分割结果上相近。表1显示，将SGA与Otsu算法结合进行图像分割相比Otsu算法很大程度上提升了获取最优阈值的效率，阈值在9个像素之间波动。然而IVNGAMS不但在阈值获取效率上比遗传算法略有提升，而且阈值范围在2个像素之间。相比于标准遗传算法，本文算法在进化同等代数后可以确保种群的多样性并且提高了收敛效率，更加稳定。

实验2 Car测试图像分割。针对Car测试图像分别选择Otsu图像分割法、Otsu结合SGA与IVNGAMS做分割比较。图4体现了原图像及分割结果，如下所示，实验数据如表2所示。

图4 Car测试图像及分割效果

实验次数Otsu法Otsu结合SGAIVNGAMS阈值时间/s阈值时间/s阈值时间/s1891.05811070.75411070.54462891.06561080.74021080.53973891.06051100.74821080.53794881.06951060.75051070.54265891.05611050.74641080.5369平均891.06196107.20.74788107.60.54034

从图4可以看出，标准遗传算法在分割的结果上要比Otsu算法略优，分割图像中的车牌号也相对清晰了，说明IVNGAMS和SGA在分割结果上相近。表2显示，将SGA与Otsu算法结合进行图像分割相比Otsu算法很大程度上地提升了获取最优阈值的效率，阈值在5个像素之间波动。然而IVNGAMS不但在阈值获取效率上比遗传算法略有提升，而且阈值范围在2个像素之间。相比于标准遗传算法，IVNGAMS在进化同等代数后可以确保种群的多样性并且提高了收敛效率，更加稳定。

7 结 语

本文利用改进的小生境遗传算法全局优化了二维图像分割函数，并通过结合模拟退火算法提出一种IVNGAMS算法，算法确保了种群多样性并提升了收敛效率并更加稳定。仿真实验的实验结果表明，IVNGAMS的阈值运算效率比Otsu图像分割法提高了很多，比标准遗传算法也略有提高。阈值范围稳定在2个像素之间，可以迅捷精确地对图像进行分割处理，实用性较高。在图像分割方法的研究方面，还可以与其他智能优化算法相结合来提升分割效率，而且针对彩色图像分割的研究也是图像分割研究重点，之后可以进行深入研究。

[1] 章毓晋.图像工程(上册)——图像处理[M].2版.北京:清华大学出版社,2006.

[2] 张自嘉,岳邦珊,潘琦,等.基于蚁群和自适应滤波的模糊聚类图像分割[J].电子技术应用,2015,41(4):144-147.

[3] 李银松.基于遗传算法的图像分割方法[D].北京:北京交通大学,2014.

[4] 黄倩.基于粒子群优化聚类的SAR图像分割方法研究[D].西安:西安电子科技大学,2014.

[5] 王雪.基于遗传算法的医学图像分割技术的研究[D].长春:长春理工大学,2013.

[6] 刘辰龙.基于遗传算法的水声图像技术研究[D].哈尔滨:哈尔滨工程大学,2013.

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

[8] 王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[9] 李婷.云模型在图像分割领域的应用研究[D].太原:太原理工大学,2015.

[10] 谢佩军.一种基于膜计算的遗传算法图像分割方法[J].工业控制计算机,2015,28(4):92-94.

[11]AntoniolG,CeccarelliM.Microarrayimagegriddingwithstochasticsearchbasedapproaches[J].ImageandVisionComputing,2007,25(2):155-163.

[12]LinS,KernighanBW.AnEffectiveHeuristicAlgorithmfortheTraveling-Salesmanproblem[J].OperationsResearch,1973,21(2):498-516.

[13] 韩瑞锋.遗传算法原理与应用实例[M].北京:兵器工业出版社,2010.

[14]CavicchioDJ.AdaptiveSearchUsingSimulatedEvolution[D].AnnArbor,MI,USA:UniversityofMichigan,1970.

[15] 玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,2000.

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

[17] 于霞霞,何朗,黄樟灿.基于模拟退火并行算法的二维熵多阈值分割[J].武汉理工大学学报,2015,37(1):116-120.

AN IMAGE SEGMENTATION METHOD BASED ON IMPROVED NICHE GENETIC ALGORITHM

Li Yang Gui Weixia

(SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,Nanning530004,Guangxi,China)

The classical Otsu algorithm and the basic genetic algorithm combined with image segmentation have the problem of low efficiency and easy to form pseudo solution in advance. For this problem, an image segmentation algorithm based on improved niche genetic algorithm (IVNGAMS) is proposed. The algorithm optimizes the two-dimensional Otsu image segmentation function globally, and automatically adjusts the genetic parameters according to the individual fitness. And the simulated annealing algorithm is introduced to further improve the local search ability. The experimental results show that the improved image segmentation method can improve the global search ability, and can converge to the optimal segmentation threshold more stably and quickly, and obtain better image segmentation effect.

Genetic algorithm Niche Image segmentation Threshold

2016-01-22。国家自然科学基金项目(61363002)；广西教育厅科研基金项目(LX2014002)。李阳，硕士生，主研领域：智能计算。归伟夏，副教授。

TP301.6

A

10.3969/j.issn.1000-386x.2017.04.034