基于遗传算法的图像分割
摘要：图像分割是模式识别与图像分析的预处理阶段，是图像处理到图像分析的关键步骤，也是一种基本的计算机视觉技术，在图像识别与图像分析中具有重要的意义。本文介绍了图像分割的一般模型、基于阈值选取的图像分割方法，讨论了遗传算法的概念、实现过程、数学理论基础、特点、应用及发展前景。鉴于遗传算法的优化原理，提出了一种基于遗传算法的图像分割方法，该方法将遗传算法引入图像分割，利用遗传算法的快速寻优特点，优化了求解阈值的过程，极大地减少了计算量和存储空间。
关键词：遗传算法，图像分割，阈值
The Image Segmentation Based on Genetic Algorithm
Abstract: Image segmentation, as the pretreatment of the pattern recognition and image analysis, as the key step
of the image processing to image analysis, and also as one computer vision technology, is very important on
image recognition and image analysis. This paper introduces the general model of image segmentation, and image
segmentation method based on the threshold value, and discusses the concept, the realization process of genetic
algorithm, mathematics theory foundation, characteristics, application and development prospect.In view of the
optimization of genetic algorithm, this paper proposes a image segmentation method based on genetic algorithm,
the genetic algorithm is introduced into image segmentation, the method using the fast optimization characteristics
of genetic algorithm, optimization of the process of solving the threshold, greatly reduce the amount of calculation
and storage space.
Key words: genetic algorithm, image segmentation, threshold
1．引言
遗传算法是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。对此，科学家进行了大量的研究工作，并成功地将它们运用于各种类型的优化问题。在分割复杂图像时，人们往往采用多参量进行信息融合，在多参量参与最优值的求取过程中，优化计算是最重要的。把自然进化的特征应用到计算机算法中，将能解决很多困难。遗传算法的出现为解决这类问题提供了新而有效的方法，它不仅可以得到全局最优解，而且大量缩短了计算时间。
2.图像分割
2.1图像分割的一般模型
图像分割是依据图像的灰度、颜色或几何性质将图像中具有特殊含义的不同区域区分开来，这些区域是互不相交的，每一个区域都满足特定区域的一致性。比如对同一物体的图像，一般需要将图像中属于该物体的像素（或物体特征像素点）从背景中分割出来，将属于不同物体的像素点分离开。分割出来的区域应该同时满足：
1、分割出来的图像区域具有均匀性。
2、分割出来的图像区域具有连通性。
3、相邻分割区域之间针对选定的某种差异显著性。
4、分割区域边界应该规整，同时保证边缘的空间定位精度。
假设一幅图像中所有像素的集合为F ，有关均匀性的假设为 P (.)。分割定义把F
划分为若干子集 {S1,S2,„,Sn}，其中每个子集都构成一个空间连通区域。以上四个条件进行数学描述，即：
如果加强分割区域的均匀性约束，分割区域很容易产生大量的空白和不规整的边缘；若过分强调分割后不同区域之间的性质差异，则会造成非同质区域的合并和丢失一部分有意义的边界。图像分割和机器视觉界的研究者们为了研究满足上述定义的分割算法做了长期的努力。图像分割的算法都是针对某一类型的图像或某一具体应用的，通用方法和策略仍面临巨大的困难，同时并不存在一个判断分割是否成功的客观标准，因此，图像分割被认为是计算机视觉的一个瓶颈。
图像分割方法可以大致分为四个方面：
1、利用图像灰度统计信息的方法，典型的有一维直方图阈值化方法和二维直方图阈值化方法。
2、利用图像空间区域信息和光谱信息的图像分割方法，典型的包括区域分裂-合并生长法、纹理分割法和多光谱图像分割法等。
3、利用图像中灰度变化最强烈的区域信息方法——边缘检测方法，这一类方法是
Marr理论中主要倡导的方法，它在图像分割研究领域中占的比例最大，典型的有 Canny
算法，Marr-Hildreth 算法和基于多尺度的边缘检测方法。
4、利用图像分类技术进行图像分割的像素分类方法。典型的有统计分类方法、模糊分类方法与神经网络分类方法等。
2.2 基于阈值选取的图像分割方法
阈值的方法实质是利用图像的灰度直方图信息得到用于分割的阈值。基于阈值选取的图像分割方法是提取目标物体与背景在灰度上的差异，把图像分为具有不同灰度级的目标区域和背景区域的组合。
阈值分割方法大致可分为：
1、单阈值的方法：用一个阈值区分背景和目标；
2、双阈值的方法：用两个阈值区分背景和目标；
3、半阈值的方法：大于（或小于）阈值部分为白，其余保留原灰度；
4、多阈值的方法：又称自适应门限方法，据多峰灰度直方图，区分背景和多个目标；
通常单阈值、双阈值的方法是利用整幅图像的整体信息，而多阈值分割法则是利用局部图像的信息。
2.2.1直方图阈值
1、双峰直方图
一幅含有一个灰度与背景有明显差异的图像包含有两个峰的灰度直方图，这两个峰分别对应于对象内部与外部较多数目的点。两峰之间的波谷对应于对象边缘附近相对较少数目的点。对于双峰直方图的情况，可根据峰的形状确定阈值。如，将分割阈值取在直方图的谷底位置，一般取在波谷的正中位置，这种方法称为双峰谷底法。该方法简单，但不能用于灰度直方图峰值相差悬殊且平坦波谷的那些图像。
有一条不成文的约定，即图像中的对象像素一般少于背景像素。因此，对象与背景不能简单地以二值化后的值是 0 还是 1 来判定。
2、多峰直方图
多峰直方图图像一般比较复杂，通常内含多种对象，每个峰对应一个对象，单次二值化对它没有多大意义。一种有效的算法称为循环分解法，这种算法首先根据图像特征将图像分成几个子图像，例如通过二值化分成两个子图像，然后再在子图像内作进一步的分解，直到不能再分解为止。这种算法需要制作一些模板，分解只在模板定义的区域中进行。这种算法充分考虑了图像的局部特性，可以获得比较精细的分割。 多峰直方图图像二值化时，阈值一般可取在分割后两类像素点接近的波谷处。
3、单峰直方图
单峰直方图的图像也是在图像处理中经常遇见，但是缺乏有效的分割方法。微分处理后得到的梯度（边缘）图像大都属于这种类型。单峰直方图图像一般可分为下面两种情况：
(1) 双峰直方图图像的两个峰的位置过于接近，以至波形中部失去了下凹的波谷。
(2) 背景与对象区域面积相差悬殊，对象区域无法在直方图中构成波峰。
对于情况(1)，阈值可选择在波形的“肩部”，即选在波形底部斜率由陡向平的转折处。对于情况(2)，可先在波形的“肩部”确定一个位置，将对应于背景区域的最大峰消除，然后用循环分解法进行分割。为了避免不利影响，通常将作为边框或边缘图中的 0 背景（或它们的反相值 255）排除在直方图统计之外。
2.2.2最大熵阈值
将信息论中熵的概念应用于图像分割时,通过分析图像灰度直方图的熵，找到最佳阈值。
设分割阈值为，i为灰度i出现的概率，i∈{0 ,1,2,„,L−1}，L-1i=0Pi=1。定义目标O用来描述 {0 ,1,„,τ}的灰度分布，背景B 用来描述 {τ + 1,τ+2,„,L−1}的灰度分布，则它们的概率分布为：
定义与这两个概率分布相关的熵为：
式中
定义准则函数（）为H (O)与H (B)之和，即：
使准则函数（）取最大值的灰度级τ即是所求出的最优阈值*，即：
2.2.3 二维最大熵阈值 通过图像的一维灰度直方图选取阈值应用于最大熵法虽然处理速度快，但由于噪声干扰和照明等因素的影响，使得图像的一维灰度直方图没有明显的峰和谷时，为此利用一维灰度值分布选取的阈值往往难以获得满意的分割效果，甚至还可能产生错误的分割。为此，许多学者在一维灰度直方图阈值分割算法上引入了图像的二次统计特性，达到改善图像的分割质量。
设原图像X={mnx}的灰度级数为 L ，大小为 M×N，由X采用3×3或5×5点阵平滑得到的平滑图像为Y={mny}，它的灰度级数和大小也为L和M×N。由X和Y可以构成一个二元组（像素的灰度级和该像素的邻域平均灰度级），每一个二元组属于二维平面上的一个点。称二元组
为图像 X 的“广义图像”。
设 X 的广义图像(X,Y)中二元组 (i,j)出现的总数为ijf显然
(i,j)出现的频率为
图 2.1 二维直方图的灰度平面
设 A区和B 区具有不同的概率分布，用
A区和B 区的后验概率对各区域的概率进行归一化，使分区熵之间具有可加性。若阈值设在 (s,t)，则
定义离散二维熵为
则A区和B区的二维熵分别为
式中
定义熵的判别函数为
（2.2） （2.1）
（2.3）
（2.4）
（2.5）
（2.6） （2.7）
（2.8）
（2.9）
（2.10）
（2.11）
（2.13） （2.12）
（2.14）
（2.15）