1遗传算法在数字图像中的应用摘要:遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法。本文将在系统介绍遗传算法的基本理论基础上,重点综述其在数字图像处理领域的主要应用,探讨目前遗传算法在图像处理领域中存在的问题及其在今后的发展方向。关键词:遗传算法,数字图像处理Abstract:Geneticalgorithmisarandomsearchandoptimizationmethodbasedonnaturalselectionandgeneticmechanismofthelivingbeings。ThispaperdiscussesandsurveysthestatusandadvancesinGeneticalgorithmresearch,thebasicalgorithms,theory,implementationtechniquesofGAareoutlinedfirst,thenmanyapplicationsofGeneticalgorithminimageprocessingfieldarereviewed,atlastseveralkeyproblemsinthisfieldarediscussedaswellastheirdevelopmentinthefuture。Keywords:geneticalgorithm,digitalimageprocessing21引言:遗传算法(geneticalgorithm,GA)是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的进化原则。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出,其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用中越来越展示出优越性。图像处理是计算机视觉中的一个重要研究领域,在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求,GA在这些图像处理中的优化计算方面找到了用武之地,目前已在图像分割、图像恢复、图像重建、图像检索和图像匹配等方面得到了广泛的应用。本文将从遗传算法的理论和技术两方面描述遗传算法的主要特点、基本原理以及各种改进算法,介绍了遗传算法在数字图像处理领域中的应用。2遗传算法的基本原理遗传算法是建立在自然选择和群体遗传学机理基础上的随机迭代和进化,具有广泛适用性的搜索方法,具有很强的全局优化搜索能力。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和变异现象,根据适者生存、优胜劣汰的自然法则,利用遗传算子(选择、交叉和变异)逐代产生优选个体(即候选解),最终搜索到较优的个体。经典遗传算法的计算流程如图1所示。从图中可以看出,遗传算法是一种种群型操作,该操作以种群中的所有个体为对象。具体求解步骤如下:1)参数编码:遗传算法一般不直接处理问题空间的参数而是将待优化的参数集进行编码,一般总是用二进制将参数集编码成由0或1组成的有限长度的字符串。2)初始种群的生成:随机地产生n个个体组成一个群体,该群体代表一些可能解的集合。GA的任务是从这些群体出发,模拟进化过程进行择优汰劣,最后得出优秀的群体和个体,满足优化的要求。3)适应度函数的设计:遗传算法在运行中基本上不需要外部信息,只需依据适应3度函数来控制种群的更新。根据适应度函数对群体中的每个个体计算其适应度,为群体进化的选择提供依据。设计适应度函数的主要方法是把问题的目标函数转换成合适的适应度函数。4)选择(复制):按一定概率从群体中选择M对个体,作为双亲用于繁殖后代,产生新的个体加入下一代群体。即适应于生存环境的优良个体将有更多繁殖后代的机会,从而使优良特性得以遗传。选择是遗传算法的关键,它体现了自然界中适者生存的思想。5)杂交(交叉):对于选中的用于繁殖的每一对个体,随机地选择同一整数n,将双亲的基因码链在此位置相互交换。交叉体现了自然界中信息交换的思想。6)变异:按一定的概率从群体中选择若干个个体。对于选中的个体,随机选择某一位进行取反操作。变异模拟了生物进化过程中的偶然基因突变现象。对产生的新一代群体进行重新评价、选择、杂交和变异。如此循环往复,使群体中最优个体的适应度和平均适应度不断提高,直至最优个体的适应度达到某一界限或最优个体的适应度和平均适应度值不再提高,则迭代过程收敛,算法结束。GA的搜索能力主要是由选择和杂交赋予的,变异算子则保证了算法能搜索到问题解空间的每一点,从而使算法达到全局最优。7)从步骤4开始重复进行,直到满足某一性能指标或规定的遗传代数。步骤1、2和3是实际应用中的关键,步骤4~步骤6进行3种基本基因操作,选择实现了适者生存的原则;交叉可以组合父代中有价值的信息,产生新的后代,以实现高效搜索;变异的作用是保持群体中基因的多样性,防止求解过程过早收敛。GA简单,鲁棒性好,具有自组织性、自适应性、自学习性和本质并行的突出特点。和4其他优化搜索算法相比,GA具有以下独特的性质:(1)GA是对参数编码进行操作,而非对参数本身,减少约束条件的限制,如连续性、可导性、单峰性等。(2)GA是多点搜索,减少了陷于局部优解的风险。(3)GA仅用适应度函数来指导搜索,不需要其他推导和附加信息,对问题依赖性小。(4)GA的寻优规则是概率性的而非确定性的。3遗传算法在数字图像处理领域的应用3.1遗传算法用于图像分割图像分割是图像处理中的重要问题,也是计算机视觉研究中的经典难题。图像分割是将目标和背景分离,为后继图像分类、识别等提供准备。常用的分割方法包括阈值法、边缘检测法和区域跟踪法,其中阈值法是最常用的方法。目前已有众多的阈值选取方法,如最大类间方差法(Otsu)、最佳直方图熵法、最小误差阈值法和矩量保持法等。其中域值法是图像分割的最常用方法。GA用于图像分割领域一般有两种情况:一是帮助现存的图像分割算法在参数空间内搜索参数;二是在候选的分隔空间内搜索最优的分隔方案。针对第一种情况多数学者利用GA的全局搜索性加速或优化现有的阈值分割算法,常用来帮助确定分割阈值。一般每个染色体用8位二进制串表示,代表一个阈值。由适应度值进行染色体优胜劣汰的选择,经过不断进化,得到了最佳阈值。其关键问题是适应度函数的设计。下面我们以Kapur等人提出的最佳熵法(KSW熵法)为例讨论遗传算法在图像分割中的应用。KSW熵法是一种不需要先验知识,而且对于非理想双峰直方图的图像也可以较好分割的方法。其缺点是在确定阈值时,尤其是确定多阈值时,计算量很大。将信息论中Shannon熵概念用于图像分割时,测量图像灰度直方图的熵,由此找出最佳阈值,其出发点是使图像中目标与背景的信息量最大。将信息论中Shannon熵概念用于图像分割时,测量图像灰度直方图的熵,由此找出最佳阈值,其出发点是使图像中目标与背景的信息量最大。本文作者曾将最大熵原则用于PCNN神经网络进行图像分割,亦取得了很好的效果。根据shannon熵的概念,对于灰度范围{0,1,…,l-1}的直方图,其熵测量为510lTiiiHpLnp其中ip为第i个灰度出现的概率。设阈值t将图像划分为目标与背景两类,则令0tppiti0lnttiiiHpp由阈值t分为A,B两类后,两类的概率分布分别为p0/pt,pt,…,pl/pl;pt+1/(1-pt),pt-2/(1-pt),…,pt-1/(1-pt),与每个分布有关的熵分别为HA(t)和HB(t)01(t)lnlntittAtititppHHpppP11(t)lnln(1)111liiTtBtittttppHHHpppp图像的总熵H(t)为HA(t)和HB(t)之和,即:(t)lnp(1p)1tTtttttHHHHpp当该函数取最大值时即为图像的最佳分割,因此将其作为遗传算法中的适应度函数。3.2遗传算法用于图像匹配图像匹配是图像处理中一个重要的课题,在计算机视觉、运动目标跟踪与识别、序列图像压缩中运动补偿、医学图像处理等领域有广阔的应用前景。在对图像的理解中,匹配技术起着重要的作用,是实现图像理解的基础。图像匹配包括模板匹配、目标匹配和动态模式匹配,其中模板(子图像或窗)匹配是最常见的匹配方法。提高图像匹配的精度和计算速度一直是研究的热点。传统的序贯相似性检测算法(SSDA)是将模板在图上逐像素平移并计算相关值,相关值最大处即为匹配最好处。该方法匹配精度高,算法稳定,但计算量大,难以用于实时性要求高的场合。近年来改进的SSDA算法、幅度排序相关算法和分层搜索的序贯判决算法等,在快速性方面效果并不明显。一些学者还提出了快速傅立叶变换(FFT)的相关算法,即通过快速傅立叶分析,将相关运算变换到频域中进行,但相关系数的计算在频域内难以实现。图像相关匹配穷尽搜索的总计算量如下:总计算量=相似性测量函数的计算量×搜索位置数6引入GA解决相关匹配的速度问题,通过减少搜索位置的数目来减少相关的总计算量。同时在匹配精度性方面也取得了较好的效果,且算法较稳定。应用GA进行相关匹配的染色体一般长16bits,分别用8bits来表示相关匹配的位置参数(i,j),适应度函数可使用某种相似测度计算。3.3遗传算法用于图像增强对于图像增强,曾经有一些学者将遗传规划(GP)用于彩色图像的增强处理,采取专家目视解释的方法评价图像质量,还不算很成功。一般来说,对于图像增强技术而言,进化算法有一下缺点:(1)利用全局观点进行图像的增强处理,通常忽略了图像的局部信息,造成增强效果欠佳。(2)需要人工干预,不能自动完成图像增强任务。将图像增强过程看作是一个图像序列的优化过程,则图像增强的过程实际上是一个寻优过程,这遗传算法的基本思想是一致的。下面简要介绍一下遗传算法用于图像增强的一种思想。基于遗传算法的图像增强技术的实现过程是一个寻找控制参数的最优或次优解的过程。因此,基于遗传算法的图像增强技术首先是一个选择图像参数模型的过程。采用J。S。LEE提出的图像参数模型,对于一幅数字图像f(●),f(x,y)是图像在x行y列的象素值。f’(x,y)为增强后的图像在对应点的象素值。则有:'(x,y)g(m(x,y))k(f(x,y))m(x,y))f其中g(●)是一个对比度扩展函数。m(x,y)为x行y列处象素占在它的某个领域内的局部均值。K0是一个控制参数,其大小直接影响到图像的处理质量。因此,数字图像的增强过程可以转化为寻找求最优参数k的过程。可用遗传算法进行寻优。3.4基于遗传算法的图像恢复图像恢复就是把一个退化(或劣化)图像尽量恢复到它的原始面目,是数字图像处理中的一个重要分支。目前已提出许多有效的图像恢复方法,如逆滤波法、维纳滤波法、奇异值分解伪逆法、最大熵恢复法等。由于引起图像退化的原因未知或不能用函数表达,使得上述方法面临较多的约束问题或是计算量过大问题,由于难以确定退化函数h,限制了其实际应用的效果。7GA用于灰度图像的恢复,一般将染色体编码成以各像素的灰度值为元素的2维矩阵,即一个染色体就代表一幅图像,每个基因对应一个像素,采用自然数编码。每个个体的适应度函数为F(fi)=g-h*fi2,其中,fi为个体i代表的推测恢复图像,g为观测到的退化图像,h为退化过程,函数值越大表示个体越好。在交叉操作时一般采用窗口交叉,即在父代染色体矩阵中选择相同大小的窗口,进行交换。变异操作采用临近小范围内的平均值替换需要变异的某一基因值。将GA应用于图像的重建还是一个正在探索的课题,目前给出的方法都是有益的尝试,存在一些问题,比如速度一般较慢、重建出的图像边缘不清等,还需要进一