一种结合遗传算法和最大类间方差法的图像分割新方法

韩海峰

(忻州师范学院 数学系，忻州 034000)



一种结合遗传算法和最大类间方差法的图像分割新方法

韩海峰

(忻州师范学院 数学系，忻州 034000)

传统的一维图像Otsu方法，只能对图像的灰度信息进行处理，对空间信息、像素等部分不能得到处理，因此在图像受到噪声或其他干扰时灰度直方图中的波峰、波谷会呈现不明显的分布，造成分割失误.本文结合遗传算法和最大类间方差法的图像分割新方法,是以遗传算法确定阀值空间中的最优阀值，最大类间方差法确定图像背景和目标图像之间的灰度方差面的最大值，避免受到噪声等因素的干扰.通过仿真实验发现该图像分割方法可降低分割时间,分割质量较好，发展前景广阔.

遗传算法；图像分割；最大类间方差法

0 引 言

随着科技的不断发展，阀值分割技术也得到了极大的拓展，许多图像分割方式都是在阀值分割技术的基础上被提出的.其中包括：最大熵原理(the maximum entropy principle)、最大类间方差法、最小误差法以及最小偏态法.最大类间方差(Otsu)是以统计原理为基础的判决方法，该项判决方法不需要经过人工设定，系统可自动选取阀值，这种判决方法具有运算简单、分割速度快等优势.也正因为这些优势使它成为使用频率最高的图像分割法.在Otsu阈值法中可选出类间方差中最大从一项，实现图像中背影和目标图像的切割.在过去，一维图像Otsu法只能处理图像中的灰度信息，在空间信息、像素部分不能得到处理，因此在图像受到噪声或其他干扰时灰度直方图中的波峰、波谷会呈现不明显的分布，造成分割失误.在该项问题中，我国刘建庄教授提出了二维Otsu法，二维Otsu法是以二维直方图的形式选择无灰度级、平均灰度级的阀值，阀值从一维发展至二维，与一维相比二维Otsu法的抗噪声干扰能力更强，图像分割效果也强于一维，大大提高了图像分割质量.

遗传算法(Genetic Algorithm)是以生活遗传机制以及自然选择以模型而来的一种择优算法，这种算法可自行处理且鲁棒性(robustness)强，目前已被广泛应用在图像处理、图像识别、工业优化控制等领域.本文通过分析传统Otsu阀值的处理原理，将遗传算法融入Otsu阀值并进行仿真实验探讨了这一形式的有效性.

1 图像分割及其常用方法

图像分割常被应用与计算机模式和模式识别中，其中目标检测、特征筛选、目标识别等操作都是通过图像分割技术实现的.图像分割指的是将目标图像与背景图像分离，让用户能在一个图像中成功的选取出自己感兴趣的那部分.图像分割技术中包括许多种方式，其中有阀值法、边缘检测法、区域跟踪法等.在这三种图像分割技术中,区域跟踪法和边缘检测法对图像质量要求偏高，需要目标图像与背景图像存在明显的灰度变化才能应用.但是在实际的状况下，许多图像的灰度因素难以特别明显，导致分割准确值的偏离过大.但阀值法对图像质量要求一般且运作简单、性能稳定等，目前被广泛地应用在图像分割中.

1.1 灰度阀值分割法

灰度阀值分割法是一种常见的并行处理技术，它是图像分割中应用最广泛的一种，阀值的分割过程实际上是输入图像f到输出图像g的变换，公式如下：

(1)

其中，T为阀值，在物体的图像元素g(i，j)=0的背景的图像元素g(i，j)=0.可见，图像阀值算法的关键是确定最优阀值阈.

1.2 区域跟踪法

区域跟踪法是以区域生长为基础，将相似性质的像素集合成区域.在每个需要分割的区域中寻找种子像素为生长.在种子像素周围与其有相同性质的像素结合在种子像素的区域中.然后将种子像素中得出新像素为种子像素，再进行以上操作直到无符合条件的像素被筛选出，此时一个区域被形成了.区域跟踪法有一个明显的特点，它的运算步骤简单，处理均匀联通的对象时可得到较好的分割效果.但是区域跟踪法也有缺点，噪声对它的影响较大，种子点需要人为的进行设置，否则很容易有空洞区域的存在，导致分割效果不佳.

1.3 边缘检测法

边缘检测法是图像分割中的一种，它是检测结构突变、灰度等级的方法，它代表某一区域的结束，另一区域的开始，这种不连续的性质称为边缘.不同的图像具有不同的灰度，在边界部分一般具有明显的边缘，以边缘特征进行分割图像.在分割图像上常应用一阶微分算子，其中包括：罗伯茨算子(Roberts算子)、Sobel算子、Prewitt算子等，二阶微分算子有Kirsh算子、拉普拉斯算子(Laplace算子)等.在实际的运作中一般以微分算子的小区域模板作为代表，其中微分运算是通过模版、图像卷积来展现的.这些算子对噪声的敏感性偏高，但是只适合噪声小且简单图像.

2 最大类间方差法图像分割方法

2.1 最大类间方差法图像分割

最大类间方差法是由日本学者Nobuyuki Otsu在1979年提出的，Otsu算法是在灰度直方图的基础上用最小二乘法原理推导出来的最佳分割阀值.通过计算目标图像与背景图像的最大方差的灰度阀值分离目标图像与背景图像，选择尺寸为M×N的原图像，在此设图像灰度级为L，同时与原图像相邻的图像领域平均灰度级为L，在原始图像在坐标(x,y)的位置上标记象素灰度值，记作i，并用f(x,y)标记，在图像(x,y)坐标位置的k×k位置平均灰度值记作j，用g(x,y)表示，可推导出下列公式：

(1)

在公式(1)中，假设图像宽度为m，图像高度为n，可得出：

(2)

其中，i=0,1,…,L-1;j=0,1,…,L-1

二维直方图的平面如图1所示，Ⅰ区为目标图像，Ⅲ区为背景图像，Ⅰ区与Ⅲ区呈对角线分布；Ⅱ区为边界线，Ⅳ区为噪声，Ⅱ区与Ⅳ区远离对角线.利用二维Otsu法在Ⅰ区与Ⅲ区筛选出最佳阀值，从而保障目标图像与背景图像的信息量最大化.

图1 二维直方图

若Ⅰ区与Ⅲ区是以不同的概率分布的，那么阀值为(s,t)，而出现两类的概率为：

(3)

两类均值向量为：

(4)

(5)

由此可知二维直方图的总均值向量为：

(6)

与对角线相距较远的Ⅱ区和Ⅳ区在一般情况下概率为0，可设i和j在两个区域内：i=1,2,…,s和j=t+1,2,…,L，则可知以下关系公式：

w0+w1≈1,μT=w0μ0+w1μ1

(7)

类间离散度测度以矩阵SB(s,t)的轨迹表示，得出：

trSB=w0((μ0j-μTj)2+(μ0i-μTi)2)+((μ1j-μTj)2+(μ1i-μTi)2)

(8)

最佳阀值(s*,t*)可满足下列式子：

(9)

2.2 最大类间方差法图像分割的缺点

通过上述分析可见，在传统运算中Otsu阈值需要通过以下过程才能完成：①遍历整个图像的灰度值，运算各个灰度值的类间方差.②排序类间方差，以图像尺寸和运算量的正比关系排列.由此可见，传统Otsu阈值方法的步骤繁琐且运算量大.但分割阀值的确定是Otst图像分割算法中不可或缺的部分.遗传算法中可在全局中进行搜索,对阀值进行智能化筛选，可大大降低传统Otsu阈值的计算量，提高图像分割运作效率.本文通过传统Otsu阈值结合遗传算法，以智能化筛选减少运算量，寻求最优Otsu阈值，实现图像分割的运作效率的提高.

3 结合遗传算法和最大类间方差法的图像分割新方法

3.1 遗传算法

遗传算法是美国J.Holland教授在1975年第一次提出，是一种模拟达尔文进化论中遗传学和自然选择为原理产生的一种搜索算法，在处理复杂问题上具有优越性.它的特点是只对在对象结构中操作，遗传算法与自然选择中优胜劣汰的原则类似，将待处理问题的解看作染色体，每个染色体为待处理问题的解.染色体形成特定的种群为解的搜索范围，每个个体的适应度由函数运算得出，得出的值越大则解也相对较优.在求解的步骤中有选择、变异等操作,加速染色体适应新环境,进而出现新的染色体群，在不断的更新中得到相对最优解.

3.2 结合遗传算法和最大类间方差法的图像分割新方法

最大类间方差法的求解可在空间阀值中，寻找到最优解，阀值的解使图像背景和目标图像之间的灰度方差值最大.本文通过遗传算法在阀值空间中进行快速计算、最优解寻找等，可快速的寻找到符合最大类间方差标准的最优阀值，具体过程如图2所示.

基于遗传算法的Ostu算法可分为如下操作步骤：

步骤1：个体范围的划分，实际图像分割灰度值在0～255的范围内，因此种群个图灰度值的范围也在0～255之内，代表每个灰度值的数字通过随机产生.

步骤2：适应度函数的确定，在Ostu算法中的背景图像与目标图像间的方差比例与分割的准确率呈正比，也就是说个体的适应度值越大，性能越好，个体适应度函数为：

f(t)=w1(t)×w2(t)×(u1(t)-u2(t))2

(10)

步骤3：选择操作，本文采用遗传算法中两两竞争的法则，在上一代种群中的个体，作为父代进行对比，个体适应值<父代适应值则淘汰，个体适应值>父代适应值可进入下一轮竞争群体内.

步骤4：交叉操作，本文采用两点交叉的方式，在选择后的2个作为父母，在交叉概率Pc产生2个新个体，两点交叉可增加算法中的随机性，进而获取局部最优值.

步骤5：变异操作，通过变异概率Pm对每个个体的变异进行处理，在变异操作下个体多样性增加.

步骤6：结束条件，经过连续的多代操后，最优适应度值未达最大进化代数或无改变时，系统停止操作，则最佳分割阀值为最高适应度值的个体.

图2 遗传算法的Ostu算法流程图

4 仿真实验

4.1 参数设置

4.2 分割效果比较

采用传统的Ostu算法的图片分割效果如图4所示，遗传算法优化的Ostu算法分割效果如图5所示.

图3 原始图

图4 传统的Ostu算法效果

图5 改进的Ostu算法效果

对比图4和图5的分割效果可知，传统算法经过改进后与遗传算法结合，所得到的图像更为清晰，目标图像边界更为明显，则表明遗传算法优化的Ostu算法优于传统的Ostu算法.

4.3 算法性能比较

对图3 、图4、 图5的分割效果进行对比，对比项目包括：计算次数、计算时间、最优阈值等，分别衡量阀值的获取和寻优的用时，比较结果见表1.

经对比分析可见，传统Ostu算法在计算次数、计算时间、最优阈值方面均逊色于遗传算法的Ostu图像分割算法.由此可知，遗传算法的Ostu图像分割算法在图像分割效果、处理用时等方面均具有优势，是一种较为理想的图像分割方法.

表1 3幅图像的算法性能比较

5 结 论

传统的一维图像Otsu法只能处理图像中的灰度信息，在空间信息、像素部分不能得到处理，因此在图像受到噪声或其他干扰时灰度直方图中的波峰、波谷会呈现不明显的分布，造成分割失误.本文遗传算法和最大类间方差法的图像分割新方法是以遗传算法确定阀值空间中的最优阀值，最大类间方差法确定图像背景和目标图像之间的灰度方差面的最大值，避免受到噪声等因素的干扰，在得到良好分割效果的同时降低了分割时间，其发展前景广阔.

[1] 许良凤,林 辉,罗 珣,等.基于并行遗传算法的Otsu双阈值医学图像分割[J].工程图学学报,2011,32(2):88-92.

[2] 扶 晓,刘 劲,赵 蕾.基于遗传算法的最佳直方图熵图像分割算法研究[J].电脑编程技巧与维护,2011(18):101+103-101,103.

[3] 孙艳歌,邵 罕.基于改进遗传算法的最优阈值图像分割算法[J].信息系统工程,2010(6):25-25,27.

[4] 张月琴,胡 斌.基于遗传神经网络的图像分割[J].电脑开发与应用,2011,24(2):16-18.

[5] SUN Pengfei , REN Hong'e , DONG Benzhi.Partial Minimum Error Thresholding Method of Cavity Image Combined with Genetic Algorithm[J].Computer Engineering and Applications,2012,48(7):169-171.

[6] Xue Lanyan,Cheng Li.IMAGE SEGMENTATION BASED ON THE METHOD OF THE MAXIMAL VARIANCE AND THE IMPROVED GENETIC ALGORITHM[J].Computer Applications and Software,2008,25(2):221-222,247.

[7] JIN Lu , FU Meng-Yin.Images Segmentation Based on Genetic Kernel Fuzzy C-Means Clustering Algorithm[J].Pattern Recognition and Artificial Intelligence,2013,26(2):205-210.

[8] LI Xian-yang,HUANG Chan.A Novel Method for Image Segmentation Based on Improved OTSU and Improved Genetic Algorithm[J].Laboratory Research and Exploration,2012(12):57-61,112.

A New Image Segmentation Method Combining Genetic Algorithm and Otsu Method

HAN Hai-feng

(Mathematics Department,Xinzhou Teachers College, Xinzhou 034000,China)

The traditional one-dimensional image Otsu method can only process the image grayinformation, and cannot get treatment on spatial information and pixel part.Ttherefore the image is affected by noise or other disturbances in the gray histogram of wave crest and trough which show the distribution is not obvious, resultingin insegmentation errors. In this paper, combining the image of genetic algorithm and Otsu segmentation method, the genetic algorithm is used to determine the optimal threshold threshold in the space Otsu method is used to determin the maximum of gray value variance sufacc between the background image and target image so as to, avoid noise interference and other factors. The simulation experiment shows that the image segmentation method can reduce the time of segmentation the segmentation quality is good,and the prospects of development are broad.

genetic algorithm; image segmentation; Otsu method

2014-12-02

韩海峰(1981-)，男，硕士，助教，研究方向：数学理论与算法分析.

TP391.41

A

1671-119X(2015)02-0043-04