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

2009-9-19 09:36:47 3090

0 基于改进遗传算法的图像分割方法提出一种应用于图像分割的改进遗传算法,算法中引入了优生算子、改进的变异算子和新个体,避免了局部早熟,提高了收敛速度和全局收敛能力。　　关键词: 图像分割遗传算法优生算子新个体　　图像处理在工业自动化、在线产品检验、生产过程控制、遥感、生物医学图像分析和保安监视等方面得到了广泛的应用。在各种图像应用中,对图像目标的提取、测量等都离不开图像分割。分割的准确性直接影响后续任务的有效性,因此图像分割具有十分重要的意义。　　遗传算法具有全局搜索能力,是一种迭代式的优化算法,在分割图像时常用来帮助确定最佳分割阈值。将模糊C-均值算法与遗传算法结合用于图像分割可得到比较好的结果。本文提出一种适合于图像分割的遗传算法,并在初始化种群、变异操作和引进新个体方面提出了新的观点和方法。实验结果证明效果显著。 1 适用于图像分割的改进遗传算法 1.1 算法的基本原理 1.1.1 编码　　基于坐标位置的阈值分割法(阈值曲面方法)具有抗噪声能力强的特点,对一些用单阈值分割法不易分割的图像(如目标和背景的灰度有梯度变化的图像)有较好的效果。实验中,选用阈值曲面方法来进行遗传编码。将染色体编码成以各象素的分割阈值为元素的二维矩阵,也就是将基因座排成二维数组,每个基因座对应图像的一个象素,基因座上的等位基因是该对应象素的分割阈值,这样每个染色体代表一个阈值曲面。由于阈值是[0,255]内的整数,所以算法采用整数编码。这样所有染色体构成包括256MN个阈值曲面的解空间。 1.1.2 初始化种群* 　　为了加快收敛速度,可以在种群初始化阶段进行改进,引入优生操作算子,即先用传统阈值分割方法产生一个阈值作为种子阈值T0,用该种子阈值T0产生一个等阈值平面。再对阈值平面叠加随机扰动,得到阈值曲面: 　　　　如此重复,直至完成K个带有随机扰动阈值曲面的初始化个体。random(x,y)为一随机函数,可产生一个随机数r(x 1.1.3 设计适应度函数　　设计一个好的适应度函数,对一个进化算法是否成功起决定性作用,尤其对图像阈值分割的遗传算法。因为到目前为止,并没有一个适合所有图像的统一模式的阈值分割。所以其适应度函数的设计并无严格限制,有很多种构造适应度函数方法。不同的构造方法,达到的效果也不同。在实验中,采用如下的适应度函数构造方法。利用一种Hopfield网络的能量函数: 　　　　　其中,R(x,y)是拉普拉斯操作数运算的结果。E1可以看作是拉普拉斯表达式的能量形式,已证明对阈值曲面应满足R(x,y)=0,即E₁=0。E₂、E₃和E₄都是一致性度量。E₂越小表示相邻象素的分割阈值应该越接近;E₃越小表示原始图梯度和阈值曲面梯度的拓扑结构越相近;E₄越小表示原始图灰度曲面和阈值曲面的拓扑结构越相近;E₃和E₄的引入有助于消除伪目标。当网络收敛接近最优解时上述能量函数均趋向于最小值。但由于遗传算法按最大适应度准则搜索,所以实际应用中要先对各项能量函数分量归一化并取反,即定义适应度函数F(Fitness): 　　　　上式中C1～C4是归一化因子,依次取值为: 1.1.4 交叉　　考虑到图像处理的特殊性,选用窗*叉方法进行操作,也就是把2个染色体基因中的多段同时进行交叉。 1.1.5 变异　　在实验的基础上,采用了整数编码变异,同时考虑到图像数据相邻象素相关性强的特点,定义如下变异操作: 　　　　上式中,g_mn表示需进行变异操作的基因,m、n分别为该基因在染色体二维矩阵(M×N)中的行、列位置。t为系数,可根据需要设为不同值。上式表示,当基因g_mn需要变异操作时,构造以g_mn为中心,以2t为边长的矩形,用该矩形内所有基因的平均值替换g_mn的值。值得注意的是,由(1)式的结构可知,处于染色体边缘的基因不能进行变异操作,但由于欲分割的目标一般处于图像中央,所以略去这些基因对分割结果影响不大。 1.1.6 引入新个体　　为了保持种群多样性,避免局部早熟,考虑引入一个特殊操作数。考虑到图像数据的特殊性,把该操作数定义为:当父代染色体经过交叉和变异后生成子代种群C₁,以C₁中各染色体的基因的平均值为基因值,生成一个新个体(X_new),然后用该个体替换C₁中的最差个体从而生成新的子代种群。X_new定义如下: 　　　　值得注意的是,由于图像数据的基因值是二维矩阵,因此基因值的平均值是指各矩阵同一位置元素的平均值。 1.2 算法步骤　　(1)确定控制参数,包括种群规模、变异率、交叉率和世代数。(2)初始化种群。先用迭代法生成种子阈值T0,然后生成阈值平面,再通过随机加扰完成种群初始化。(3)用适应度函数评价父代染色体并排序,保留最优染色体。(4)选择、交叉和变异,生成子代种群C1。(5)引入新个体,生成新的子代种群。(6)判断是否满足收敛条件,若满足则输出结果,并退出;否则,转入步骤(3)。 2 应用实例 2.1 参数设定及程序实现　　实验中,采用256级灰度图像,图像尺寸为128×128(单位为象素)。种群规模为100,平均叠代次数为822,交叉率为0.2,变异率为0.01。所有程序都是用VC++6.0在Win98环境下编译完成。部分程序实现方法如下。　　(1)设计一个新类Class GASegment。所有的遗传操作都被分别设计成函数模块,以成员函数的形式封装在类GASegment中。(2)染色体设计成结构体Struct genotype。结构体genotype中定义了染色体基因值、变异率和交叉率等变量。(3)种群初始化在构造函数GASegment(LONG temp)中实现。(4)定义一个全局API函数。　　BOOL WINAPI GaSegmentMain(LPSTR lpDIBBits,LONG lWidth,LONG lHeight);调用该API函数实现一次遗传分割操作。 2.2 实验结果　　叠代法分割与遗传分割的实验测试结果如图1所示。可以看出,改进的遗传分割算法的分割效果明显优于传统叠代法。 3 结论　　本文提出的遗传分割算法充分考虑了图像数据本身的特殊性,从提高全局搜索能力和收敛速度出发,加入了三个新的操作策略。算法在初始化种群阶段引入了优生算子,而且改进的变异操作使遗传算法的收敛速度大大提高。在形成新种群阶段引入新个体避免了局部早熟,提高了全局收敛能力。以基于坐标的阈值分割方法为基础进行二维实数编码,采用窗*叉方法,利用Hopfield网络的能量函数形式来构造适应度函数。实验结果表明,改进遗传分割算法的分割效果明显优于传统分割算法。 0
2009-9-19 09:36:47　　评论淘帖0 举报相关推荐 • 遗传算法的基本原理基于遗传算法的图像分割 1 • 基于遗传算法的彩色图像多阈值分割 24 • 基于改进遗传算法应用于图像边缘选取 1 • 什么是遗传算法？ 1534 • 基于改进遗传算法的路网路径优化方法 10 • 基于改进遗传算法的蜂窝网络区域配置方法 25 • 基于改进遗传算法的云计算优化 6 • 基于改进遗传算法的唯相波束形成方法 0 • 交互式遗传算法的改进方法及应用 17 • 基于自适应量子遗传算法和二维OTSU的图像分割方法 9