遗传算法在图像处理中的应用

课 程： 新技术讲座 题 目：遗传算法在图像处理中的应用姓 名： 学 号： 目录摘要21.引言32.遗传算法的基本原理和基本性质33.遗传算法在图像处理中的应用53.1在图像增强中的应用53.2在图像恢复中的应用63.3在图像分割中的应用73.4在图像压缩中的应用83.5在图像匹配中的应用94.遗传算法在图像处理中的问题及发展方向10参考文献10遗传算法在图像处理中的应用摘要 遗传算法是一种模拟生命进化机制，基于生物自然选择与遗传机理的随机搜索与优化方法。近几年来，遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中，这种算法得到快速发展，尤其是在计算机科学人工智能领域中。本文将在系统并且深入的介绍遗传算法基本理论的基础上，重点综述遗传算法在数字图像处理中的主要应用，深入研究目前遗传算法在图像处理领域中存在的问题，并对这些问题作出了一些个人的见解，阐述了遗传算法在图像处理应用的发展方向。关键词 ：遗传算法，数字图像处理Abstract  Genetic Algorithm is a simulation of the life evolution mechanism, random search and optimization method which is based on the natural selection and genetic mechanism.In recent years,due to the enormous potential of solving complex optimization problems and the successful applications in the industrial field,the Genetic Algorithm developed rapidly, Especially in the field of artificial intelligence in computer science. This article not only describes the basic theoretical foundation of genetic algorithms,but also focus on Genetic Algorithm in digital image processing.Moreover,it studies the problems of the Genetic Algorithm in the field of image processing and the direction of development in the future，Moreover, the author elaborates the personal opinion in the end.keyword ：Genetic Algorithm, Digital image processing1.引言遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。尤其是对研究智能领域的人来说，遗传算法的身影更是无处不在，在智能传感，机器学习，模式识别，计算智能，图像理解等课程中，对遗传算法在各个领域的应用都有所提及。 图像处理(image processing)，用计算机对图像进行分析，以达到所需结果的技术。又称影像处理。图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组，该数组的元素称为像素，其值为一整数，称为灰度值。图像处理技术的主要内容包括图像压缩，增强和复原，匹配、描述和识别3个部分。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像处理一般指数字图像处理。图像处理是计算机视觉中德一个重要研究领域，然而，在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，从而影响图像的效果。于是，研究者就开始探索怎么样才能使这些误差最小从而使计算机视觉达到实用化的重要要求，最终，遗传算法凭借其在这些图像处理中的优化计算方面独特的优势成为各种算法的佼佼者，得到了广泛的应用。2.遗传算法的基本原理和基本性质遗传算法是具有“生成+检测”的迭代过程的搜索算法，它的基本处理流程图如下图所示。由上图可知，遗传算法模拟了自然选择和遗传进化中发生的繁殖、交配和突变现象，从任意一个初始种群出发，通过随机选择、交叉和变异操作，产生新的更适应环境的个体，使群体进化到搜索空间中越来越好的区域。这样一代一代不断繁殖、进化，最后收敛到一群最适应环境的个体上，求得问题的最优解。遗传算法对于复杂的优化问题无需建模和复杂运算，只要利用遗传算法的三种算子就能得到最优解。GA把问题的解表示成染色体（也称串），GA的求解步骤如下：（1）参数编码。这个要素是要建立一个空间映射，就是问题的解空间与编码空间的映射，每个不同的候选解用有一个单独的串号。（2）初始群体的设定。将种群进行初始化。（3）适应度函数的设计。在种群中，将每个个体的染色体进行解码，变成适合计算式适应度的函数形式。（4）选择。将适应度大的个体作为优秀个体繁殖下一代，适应度越大被选择繁殖下一代的可能性也就越大。（5）交叉。将选中的两个用于繁殖下一代的位置相同个体的位置进行交叉互换。（6）变异。按照基因突变的概率翻转串中的基因。（7）重复步骤（4）到步骤（6）使得结果满足已设定的遗传条件。GA结构较为简单，算法也不复杂，但是又具有良好的选择效果，具有自适应性、子组织性和自学习性等特点，具有许多其它算法没有的优点，主要有：（1）GA 是对参数编码进行操作, 而非对参数本身, 减少约束条件的限制, 如连续性、可导性、单峰性等。（2）GA 是多点搜索, 减少了陷于局部优解的风险。（3）GA 仅用适应度函数来指导搜索, 不需要其他推导和附加信息, 对问题依赖性小。（4） GA 的寻优规则是概率性的而非确定性的。研究者们在应用GA 过程中也不断研究改进GA的性能，使GA更能满足时代的需要，比如在选择策略中提出了精英选择、稳态选择和竞争选择等新的机制; 在变异环节提出了两点、多点和一致变异作为传统一点变异的改进和补充; 在编码环节中应用格雷码和动态编码等克服传统二进制编码和定点十进制整数编码所就带来的问题; 此外, 还提出自适应技术动态改变GA 控制参数, 克服采取传统的静态控制参数策略引起的多样性和收敛性不均衡问题, 以及用梯度方法、单纯型法或模拟退火方法精细调整的混合GA, 以提高算法的收敛速度; 用均匀分布的初始群体代替随机产生的初始种群; 研究了分布式GA、迁徙GA 和并行GA等, 进一步推动了GA 的发展。3.遗传算法在图像处理中的应用3.1在图像增强中的应用图像增强技术是将不清晰的图像经过优化处理变成一张比之前更加清楚，或者变成一张使得特点更加鲜明的照片，以便于对图像再进行后期的加工。目前图像增强方法主要包括将图像进行某种变换的频域法和对直接对原始图像进行处理的空域法两种。而基于遗传算法的图像增强技术的实现则是利用遗传的选择方法找到一个最优或者局部最优的方法。具体的操作方法是，首先将每一个目标值设置一个基位，用实数进行编码，这样问题就转化成求解这个目标基位组合的题目。然后，对适应度进行设计，适应度设计为个体进化提供动力，在设置适应度的时候既要考虑图像的整体和局部的质量问题，也要将结构和细节考虑进去。再后，对遗传算子进行设计，先根据前面设置的适应度值将个体从大到小进行排列，从中选择优秀的个体进入下一个程序当中；为了防止遗传算法在计算的过程中过早收敛，对种群的多样性进行保护，在计算过程中采用交叉操作的方法产生新的个体；对进化方向进行微调，采用变异操作的方法，对一个被选中的变异操作来说，就是采用“1”“0”和“1”“0”的方式进行变异。最后，设置算法的结束条件，一般算法的结束条件就是迭代次数达到了最大进化代数或者最大适应度的值变化不明显。例如，对于一幅数字图像f(.),f(x,y)是图像在x行y列的像素值。f(x,y)为增强后的图像在对应点的像素值。则有：其中g(.)是一个对比度扩展函数。m(x,y)为x行y列处像素值占在它的某个邻域内的局部均值。K>0是一个控制参数，其大小直接影响到图像的处理质量。因此，数字图像的增强过程可以转化为寻找求最优参数k的过程。进而，可用遗传算法按照上述过程进行寻优。3.2在图像恢复中的应用图像恢复就是把一个退化(或劣化)图像尽量恢复到它的原始面目, 是数字图像处理中的一个重要分支。目前已提出许多有效的图像恢复方法, 如逆滤波法、维纳滤波法、奇异值分解伪逆法、最大熵恢复法等 。由于引起图像退化的原因未知或不能用函数表达, 使得上述方法面临较多的约束问题或是计算量过大问题, 由于难以确定退化函数h, 限制了其实际应用的效果。GA 用于灰度图像的恢复, 一般将染色体编码成以各像素的灰度值为元素的2维矩阵, 即一个染色体就代表一幅图像, 每个基因对应一个像素, 采用自然数编码。每个个体的适应度函数为其中, f i 为个体i代表的推测恢复图像, g 为观测到的退化图像, h 为退化过程, 函数值越大表示个体越好。在交叉操作时一般采用窗口交叉, 即在父代染色体矩阵中选择相同大小的窗口, 进行交换。变异操作采用临近小范围内的平均值替换需要变异的某一基因值。此外，GA也用于彩色图像的恢复，并且取得了很好的效果。基于GA 的图像恢复方式, 突破了原有的理论,而且其开放的结构易于与其他方式融合, 如与模糊逻辑相结合的模糊GA 等。利用GA 恢复图像不仅较好的克服了噪声的影响, 而且使图像更平滑, 边缘没有条纹效应, 视觉效果好。强大的全局搜索能力是遗传算法图像恢复方法行之有效的主要原因。3.3在图像分割中的应用图像分割是自动目标识别的关键和首要步骤，其目的是将目标和背景分离，为计算机视觉的后续处理提供依据。目前图像分割的方法很多，常用的包括阈值法、边缘检测法和区域跟踪法。其中域值法是图像分割的最常用方法。当前常用的域值分割方法如最小误差阈值法、最大类别方差法（Otsu 法）以及最佳直方图熵法。下面我们以Kapur 等人提出的最佳熵法（KSW 熵法）为例讨论遗传算法在图像分割中的应用。KSW熵法是一种不需要先验知识，而且对于非理想双峰直方图的图像也可以较好分割的方法。其缺点是在确定阈值时，尤其是确定多阈值时，计算量很大。将信息论中Shannon 熵概念用于图像分割时，测量图像灰度直方图的熵，由此找出最佳阈值，其出发点是使图像中目标与背景的信息量最大。根据shannon 熵的概念，对于灰度范围0,1,255的直方图，其熵测量为其中pi为第i个灰度出现的概率。设阈值t将图像划分为目标与背景两类，则令 由阈值t 分为A,B 两类后，两类的概率分布分别为p0/pt, pt,