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

0

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

　　关键词: 图像分割  遗传算法  优生算子  新个体

　　图像处理在工业自动化、在线产品检验、生产过程控制、遥感、生物医学图像分析和保安监视等方面得到了广泛的应用。在各种图像应用中,对图像目标的提取、测量等都离不开图像分割。分割的准确性直接影响后续任务的有效性,因此图像分割具有十分重要的意义。

　　遗传算法具有全局搜索能力,是一种迭代式的优化算法,在分割图像时常用来帮助确定最佳分割阈值。将模糊C-均值算法与遗传算法结合用于图像分割可得到比较好的结果。本文提出一种适合于图像分割的遗传算法,并在初始化种群、变异操作和引进新个体方面提出了新的观点和方法。实验结果证明效果显著。

1  适用于图像分割的改进遗传算法

1.1 算法的基本原理

1.1.1 编  码

　　基于坐标位置的阈值分割法(阈值曲面方法)具有抗噪声能力强的特点,对一些用单阈值分割法不易分割的图像(如目标和背景的灰度有梯度变化的图像)有较好的效果。实验中,选用阈值曲面方法来进行遗传编码。将染色体编码成以各象素的分割阈值为元素的二维矩阵,也就是将基因座排成二维数组,每个基因座对应图像的一个象素,基因座上的等位基因是该对应象素的分割阈值,这样每个染色体代表一个阈值曲面。由于阈值是[0,255]内的整数,所以算法采用整数编码。这样所有染色体构成包括256M*N个阈值曲面的解空间。

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