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

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

束道胜 P201002117

1 引 言

遗传算法( genetic algorithm, GA)是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的进化原则。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出,其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用中越来越展示出优越性。

图像处理是计算机视觉中的一个重要研究领域,在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求, GA 在这些图像处理中的优化计算方面找到了用武之地,目前已在图像分割、图像恢复、图像重建、图像检索和图像匹配等方面得到了广泛的应用。

2 遗传算法的原理、基本性质和改进

GA把问题的解表示成染色体(也称串) , GA的求解步骤如下:

(1) 编码 定义问题的解空间到染色体编码空间的映射,一个候选解(个体)用一串符号表示。

(2) 初始化种群 在一定的限制条件下初始化种群,该种群是解空间的一个子空间。

(3) 设计适应度函数 将种群中的每个染色体解码成适于计算机适应度函数的形式,计算其数值。

(4) 选择 根据适应度大小选择优秀个体繁殖下一代,适应度越高,则选择概率越大。

(5) 交叉 随机选择两个用于繁殖下一代的个体的相同位置,在选中的位置实行交换。

(6) 变异 对某个串中的基因按突变概率进行翻转。

(7) 从步骤4开始重复进行,直到满足某一性能指标或规定的遗传代数。 步骤1、2和3是实际应用中的关键,步骤4～步骤6进行3种基本基因操作,选择实现

了适者生存的原则;交叉可以组合父代中有价值的信息,产生新的后代,以实现高效搜索;变异的作用是保持群体中基因的多样性,防止求解过程过早收敛。

GA简单,鲁棒性好,具有自组织性、自适应性、自学习性和本质并行的突出特点。和其他优化搜索算法相比, GA具有以下独特的性质:

(1) GA是对参数编码进行操作,而非对参数本身,减少约束条件的限制,如连续性、可导性、单峰性等。

(2) GA是多点搜索,减少了陷于局部优解的风险。

(3) GA仅用适应度函数来指导搜索,不需要其他推导和附加信息,对问题依赖性小。

(4) GA 的寻优规则是概率性的而非确定性的。

学者们在应用GA过程中也不断研究改进GA的性能。比如在选择策略中提出了精英选择、稳态选择和竞争选择等新的机制;在变异环节提出了两点、多点和一致变异作为传统一点变异的改进和补充;在编码环节中应用格雷码和动态编码等克服传统二进制编码和定点十进制整数编码所就带来的问题;此外,还提出自适应技术动态改变GA 控制参数,克服采取传统的静态控制参数策略引起的多样性和收敛性不均衡问题,以及用梯度方法、单纯型法或模拟退火方法精细调整的混合GA,以提高算法的收敛速度;用均匀分布的初始群体代替随机产生的初始种群;研究了分布式GA、迁徙GA和并行GA等,进一步推动了GA的发展。

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

3. 1 基于遗传算法的图像分形压缩

分形图像压缩的最基本的思想起源是:具有自相似性的几何体可以用一组简单的代数关系式表达。主要理论基础是迭代函数系统理论和拼贴定理[ 17, 18 ] ,要解决的问题是当把被压缩的图像作为吸引子时如何得到IFS(迭代函数系统)的参数。将图像互不重叠的小块称为值域块,将可以部分重叠的较大尺寸的块称为定义域块。对每个值域块进行编码时,就是寻找一个定义域块以及一个仿射变换w ,该变换把定义域块映射到值域块,并使经过映射后的定义域块与值域块的距离在某种度量值下最小,所有值域块对应的压缩映射集构成一个PIFS(部分迭代函数系统) , PIFS的所有参数就是图像的分形码。由于图像中所有定义域块的集合太 大,分形压缩搜索非常耗时,应用GA能有效解决分形压缩的最优匹配问题。GA与分形图像压缩编码的结合要解决的关键问题是要构造一个适当的适应

度函数。张等人用区域块左上角的坐标x, y 和区域块的旋转变换z (共有8种旋转)进行染色体编码;陈等人在搜索最优定义域块时使用的两个参数是定义域块相对

于值域块位移的水平和垂直分量( xi , yi ) ,用10位二进制串对其进行编码,每个参数用5 位编码;吴等人提出了一种带分类的编码法,这样的编码具有特征集中,搜索速度快的特点,能够改进遗传算法的速度,克服分形压缩中分类匹配算法的局部最优和随机搜索问题。GA应用于分形图像压缩,提高了压缩比和压缩精度,由于在高压缩比下信噪比有较大的改善,故也可用于低比特率的图像压缩[ 22 ] 。而且, GA具有能并行计算的特点,可降低分形的计算时间,快速找到最优解。但是,实验中的控制参数很多,大部分是依赖经验得到,因此,如何自适应地控制这些参数,进一步提高压缩比和解码质量,还有待于研究和探讨。由于GA的良好特性,它与分形结合的应用前景将会是很广阔的。

3. 2 基于遗传算法的图像分割

图像分割是图像处理中的重要问题,也是计算机视觉研究中的经典难题。图像分割是将目标和背景分离,为后继图像分类、识别等提供准备。常用的分割方法包括阈值法、边缘检测法和区域跟踪法[ 1 ] ,其中阈值法是最常用的方法。目前已有众多的阈值选取方法,如最大类间方差法(Otsu) 、最佳直方图熵法、最小误差阈值法和矩量保持法等。GA用于图像分割领域一般有两种情况:一是 帮助现存的图像分割算法在参数空间内搜索参数;二是在候选的分隔空间内搜索最优的分隔方案。针对第一种情况多数学者利用GA的全局搜索性加速或优化现有的阈值分割算法,常用来帮助确定分割阈值。一般每个染色体用8位二进制串表示,代表一个阈值。由适应度值进行染色体优胜劣汰的选择,经过不断进化,得到了最佳阈值。其关键问题是适应度函数的设计。文献采用Otsu法进行图像分割时的质量测试公式作为适应度函数;文献采用图像的熵计算公式来计算适应度;文献用最小误差概率作为适应度函数来搜索最优阈值,其收敛性远远高

于传统的最小误差准则方法。对于小目标图像分割,文献在染色体中又加入了一个参数,即“目标在图像中所占比例的可能范围”,克服了传统P2title法要求已知目标所占确切比例的缺陷。文献在原单阈值分割GA中,加入待分割目标区域的位置、长度和高度参量。在染色体中分别用5个8位代表这些参量。文献在图像分割时的阈值计算上引入GA,提高了效率。文献给出了一个可以适应动态环境的图像分割系统,将成像条件等环境变量引入图像分割过程,采用GA在由分割参数组成的多维空间进行高效搜索,找到最优的分割参数集,从而赋予系统一定的自适应和学习能力。文献[ 30 ]提出了一种基于概率划分、模糊划分和熵理论的图像分割的三级阈值方法。模糊区域的宽度和属性由最大模糊熵定义,而找到所有6个模糊参数的最优组合用GA来实现。文献提出可在严重噪声情况分割细胞图像的并行GA,用GA来调整细胞轮廓模型的参数以便找到最好的匹配。针对第2种情况,文献呈现

了一种新的基于区域的灰度图像分割方法,该方法使用基于模糊测度的遗传算法,首先提出了一个模糊有效函数,用来测量细小的分割区域之间及内部的疏密程度和沿着所有区域边界的强度;然后应用GA去搜索一个可用的区域分割,这个分割能够使分裂和融合过程所生成的区域的质量达到最佳。染色体的结构如图2所示。把边缘检测问题转化为在所有可能的边缘空间中最小化一个目标代价函数,使用专门的算子进化染色体。文献给出一种基于分布式GA的非监督图像分割方法( SR) 。最终的分割结果来自于种群中各单元之间基于个体适应度的竞争的副产品,即整个染色体的规模作为一个分割的结果。此外,文献[ 35 ]将遗传寻优过程也用于图像的边缘检测,取得了很好的效果。

3. 3 基于遗传算法的图像匹配

图像匹配在近几十年来一直是人们研究的热点和难点,算法也很

多,一般分为基于灰度相关、基于特征、基于模板以及基于变换域的匹配。其中模板匹配是最常见的方法。传统的相关匹配算法是将模板在图上逐像素平移并计算相关值,相关值最大处即为匹配最佳处。该方法匹配精度高,算法稳定,但计算量大,难以用于实时性要求高的场合。图像相关匹配穷尽搜索的总计算量如下:总计算量=相似性测量函数的计算量×搜索位置数引入GA解决相关匹配的速度问