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

束道胜 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解决相关匹配的速度问

题,通过减少搜索位置的数目来减少相关的总计算量。同时在匹配精度性方面也取得了较好的效果,且算法较稳定。应用GA进行相关匹配的染色体一般长16bits,分别用8bits来表示相关匹配的位置参数( i, j) ,适应度函数可使用某种相似测度计算 。文献选择格雷码编码方案,同时为了提高不同类型目标匹配定位的精度和跟踪可靠性,采用多子模板匹配方法,图像以同样的方式划分,由各子模板与子图像分别进行相关匹配,仿真结果发现,速度有很大提高。文献[ 39 ]则在匹配过程中对GA的交叉概率和变异概率进行了改进,使之能随个体适应度变化,这样当群体收敛至局部极值附近时,增大变异概率,从而增加群体多样性,跳出局部解;而当群体在解空间分散时,则增大交叉概率,加快收敛速度,保证了向全局最优解逼近,又有了一定的收敛速度。将Hausdorff距离作为物体轮廓的相似性的测度,具体计算方法参见文 ,该方法能有效检测出具有平移、旋转和尺度变化的物体。文献在编码过程中以自然数代替二进制编码,认为二进制编码有如下缺点: (1) 不同尺寸图像,采用二进制编码的位数不可事先确定;

(2) 二进制交叉和变异后可能产生无对应可行解的个体,这些个体经解码处理后表示的解为无效解。此外自然数编码适合表示大范围的数,不需要编码和解码操作,提高运算速度。文献[ 42 ]应用GA进行目标的轮廓匹配。先给出目标的边缘,然后定义染色体为2D星形坐标轮廓,每个轮廓Si 用长度为8 的向量表示Si = [ r1 i ,θ1i , r2 i ,θ2 i , r3 i ,θ3i , xi , yi ],其中3对r,θ代表2D平面图像轮廓3个轴的极坐标, xi , yi 代表中心坐标。适应度函数取2D轮廓线与图像边缘的距离,最小者为最优解。文献[ 43 ]等提出了一个利用GA完成关系图匹配的框架。提高匹配的精度和计算速度一直是图像匹配研究的热点。图像相关匹配技术中引入GA主要解决相关匹配速度问题, GA 通过减少搜索位置的数目从而减少相关的总计算量。同时在匹配精度性方面也取得了较好的效果,而且算法较稳定。

3.4 遗传算法在基于内容图像检索中的应用

基于内容的图像检索方法是根据图像所包含的色彩、纹理、形状以及对象的空间关系等信息,通过建立图像的特征矢量,并将其作为图像的索引来进行图像检索的技术,其检索效果与图像特征矢量编码方式以及具体的图像检索方法都有密切关系。文献[ 44 ]提出了一种基于交互式遗传算法(IGA)的图像检索方法, IGA通过交互过程来获取用户对染色体的评价,并使用用户评价作为适应度值进行选择操作。系统以随机方式从图像库中抽取S幅图像作为交互式GA 的第一代样本群体,呈献给用户;用户依据每幅图像与自己的要求对象的相关性进行评价;系统根据用户的评价得到与每幅图像对应的染色体的适应度值对该染色体群体进行一系列的遗传操作。该方法具有简捷、高效的特点。用户只对适应度评估,不

参与个体的搜索过程,容易导致用户的疲劳和低速收敛。文献[ 45 ]提出 了一种可视化IGA模型(V IGA) ,用户通过对整个搜索过程加一个导向信号,引导遗传过程朝用户的主观情感方向发展。实验结果证明, V IGA 较一般的IGA有更快的收敛速度,对减轻用户疲劳有很好的作用。GA在基于内容的图像检索中主要是用来提取图像的特征向量,利用GA的全局寻优的特性,挖掘出图像最本质的信息,最终提高了检索的精度。同时,可视化的GA方法添加处于高适应度区域的个 体,有效地加快了遗传算法的收敛速度,在感性检索方面有很大的应用前景。

4 结 论

综上所述, GA作为一种有指导性的、鲁棒的随机化技术,非常适合在图像处理这样的巨量空间内搜索最优值。另外, GA由于其群体性操作,本质上具有很好的并行分布处理特性,尤其GA中各个个体的适应度计算可进行而彼此间无需任何通信,所以并行效率很高。它已经在图像处理领域取得了很好的成果,也受到越来越多的重视[ 46 ] 。但是也暴露出了在理论和应用技术上的许多不足和缺 陷。首先,尽管GA比其他传统搜索方法有更强鲁棒性,但它更擅长全局搜索而局部搜索能力却不足。研究发现, GA 可以极快的速度达到最优解的90%左右,要达到真正的最优解则需要花费很长的时间。因此,要兼顾收敛速度和解的品质两个指标,除了需要进一步改进基本理论和方法外,还要采用和神经网络、模拟退火、小波分析或其他方法结合的策略以提高GA的局部搜索能力,从而改善算法的性能。其次,在变量多、取值范围大或无给定范围时收敛速度下降,而且, GA中多数参数的选择未有定量方法,经常依赖经验得到,适应度标定方式多种多样,没有一个简洁、通用方法,不利于对GA的使用,因此其数学基础显得极为薄弱,尤其是缺乏深刻且具有普遍意义的理论分析。此外, GA的“早熟”现象即很快收敛到局部最优解而不是全局最优解问题极难处理。这些都是迄今为止GA最难解决的关键问题,需要亟待解决。否则,会GA 的进一步应用。

GA在图像处理方面的应用多数处于理论性仿真阶段,实际系统中的应用还比较少。如何针对图像处理方面的特点选择适用图像分析和处理的GA结构或合适的参数是今后进一步研究的内容。随着理论研究的深入,可以肯定, GA以其特有的算法特点使其在图像处理问题中的应用会越来越广;同时,广泛的数学方法和大的计算机模拟工具的出现,必将使GA研究取得长足的进展,使GA在图像处理中的作用更趋完善。