（计算数学专业论文）遗传算法在数字图像处理中的应用.pdf

o 1摘要y6 6 35 57i遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种新的全局优化搜索算法，具有简单通用、稳定性强、适于并行处理以及高效、实用等显著特点，在很多领域得到了广泛应用，另一方面，在图像处理领域有很多优化问题如图像压缩，模式识别，图像校准，图像分割，三维重建，图像检索等等，实际上都等同于一个大范围搜索寻优问题，而最优化问题是遗传算法经典应用领域，因此遗传算法完全胜任在图像处理中优化方面的计算。基于这个理论可行性的大前提，本文在吸取前人实践经验的基础之上，深入研究了遗传算法在图像压缩，模式识别两个问题中的应用策略，并得到了比较满意的结果。全文共分三章，在第一章首先简单介绍了遗传算法的研究历史，生物背景，继而简述了遗传算法的基本实现步骤和基本遗传算子的实现方案以及遗传算法的基本特点和目前的基本应用情况以及作者在应用遗传算法处理问题中的一点心得。在第二章首先简述与图像压缩相关的小波分析基础理论知识，涉及到小波得到发展的原因及其优点，连续小波，离散小波，二进小波具体形式定义，以及构造在正交小波的多分辨分析。然后阐述了紧支撑双正交小波及其在图像压缩具体应用方法之后，基于遗传算法对小波滤波器的构造方法进行的研究，提出了解决对任意特定图像进行压缩处理所需要的最优小波滤波器的构造问题，从而将遗传算法与小波压缩有机结合起来实现了图像的最优压缩。在第三章里，在分析模式识别问题的多参量目标优化的性质的基础上，分别就规则图形，复杂图形，图像层层深入地提出了遗传算法在图形图像的模式识别问题的实现策略。关键词：遗传算法，紧支撑双正交小波，最优小波，模式识别o 2a b s t r a c ti ig e n e t i ca l g o r i t h m ，a sac o m p u t a t i o n a lm o d e ls i m u l a t i n gt h eb i o l o g i c a le v o l u t i o np r o c e s so ft h eg e n e t i cs e l e c t i o nt h e o r yo fd a r w i n ，i saw h o l en e wg l o b a lo p t i m i z a t i o na l g o r i t h ma n di sw i d e l yu s e di nm a n yf i e l d sw i t hi t sr e m a r k a b l ec h a r a c t e r i s t i co fs i m p l i c i t y ic o m m o n a b i l i t y , s t a b i l i t y ，s u i t a b i l i t yf o rp a r a l l e lp r o c e s s i n g ，h i g h -e f f i c i e n c y ，a n dp r a c t i b i l i t y o nt h eo t h e rh a n d ) t h e r ea r em a n yo p -t i m i z a t i o np r o b l e m si nt h ef i e l do fd i g i t a li m a g ep r o c e s s i n g ，s u c ha si m a g ec o m p r e s s i o n ，p a t t e r n - r e c o g n i t i o n ，i m a g er e c t i f i c a t i o n ，i m a g es e g m e n t a t i o n ，3 di m a g er e c o v e r y ，i m a g ei n q u i r y ，a n do rs o i nf a c ta l lt h e s ep r o b l e m sc a nb eg e n e r a l i z e da st h ep r o b l e mo fs e a r c h i n gf o rag l o b a lo p t i m a ls o l u t i o ni nal a r g es o l u t i o ns p a c e ，w h i c hi st h ec l a s s i ca p p l i c a t i o nf i e l do fg e n e t i ca l g o r i t h m o nt h em a j o rp r e m i s eo ff e a s i b i l i t yo ft h i st h e o ry t h i sa r t i c l eb a s e do nt h ep r a c t i c eo ff o r e -r u n n e r s ，h a sd o n es o m ef u r t h e rr e s e a r c hw o r ka b o u tt h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mf o ri m a g ec o m p r e s s i o na n dp a t t e r n - r e c o g n i t i o nw i t has a t i s f a c t o r yr e s u l t t h i sa r t i c l ei sd i v i d e di n t ot h r e ep a r t t h ef i r s tc h a p t e ri n -t r o d u c e sr e s e a r c hh i s t o r yo fg e n e t i ca l g o r i t h ma n db i o l o g i c a lb a c k g r o u n db r i e f l ya tt h eb e g i n n i n g ，t h e nd i s c u s st h eb a s i cr e a l i z a t i o nm e t h o do ft h ea l g o r i t h m ，i t so p e r a t e r s ，i t sb a s i cc h a r a c t e r i s t i c ，i t sa p p l i c a t i o n sa sw e l la 8s o m et h o u g h t so ft h ea u t h o ra b o u th o wt ou s eg e n e t i ca l g o r i t h mt os o l v ep r o b l e m s i nt h es e c o n dc h a p t e r ，s o m er e l a t i v eb a s i ct h e o r i e si nw a v e l e ta n a l y s ei sf i r s tp r o p o s e di nb r i e f ，i n v o l v i n gt h ec a u s eo fd e v e l o p m e n to fw a v e l e tt h e o r y ( t h a tm e a n si t sg o o d ) 1t h ed e f i n i t i o no fc o n t i n u o u sw a v e l e t ，d i s c r e t ew a v e l e ta n dd y a d i cw a v e l e ta n dt h em u l t i r e s o l u t i o na n a l y s i sf o rc o n s t r u c t i n go r t h o g o n a lw a v e l e t t h e nt h eb i o r t h o g o n a lw a v e l e ta n dm e t h o do fi t sa p p l i c a t i o nf o ri m a g ei l l( ：) m p r e s s i o ni sd i s c u s s e d b a s e d0 1 1t h er e s e a r c ho fg e n e t i ca l g o r i t h mf o rt h ec o n s t r u c t i n gm e t h o do fw a v e l e tf i l t e r s ，t h em e t h o do fc o n s t r u c t i n go p t i m a lw a v e l e tf i l t e r sf o rt h es p e c i f i ci m a g ec o m p r e s s i o ni sp u tf o r w a r d ，s ot h ep r o b l e ma b o u ti m a g eo p t i m a lc o m p r e s s i o ni ss o l v e ds u c c e s s f u l l yw i t ht h ec o m b i n a t i o no fg e n e t i ca l g o r i t h ma n dw a v e l e tu s e di ni m a g ec o m p r e s s i o n i nc h a p t e rt h r e e ，a f t e rm a k i n gc l e a rt h ep r o p e r t yo fm u l t i v a r i a b l eo b j e c t i v eo p t i m i z a t i o no fp a t t e r n r e c o g n i t i o n ，r e a l i z a t i o nm e t h o d so fg e n e t i ca l g o r i t h m ，a p p l i c a t e df o rp a t t e r n - r e c o g n i t i o no ff i g u r e sa n di m a g e s ，a r ep u tf o r w a r ds e p a r a t e l ya n dg r a d u a l l yf o rr e g u l a rf i g u r e ) c o m p l i c a t e df i g u r ea n di m a g e k e yw o r d s ：g e n e t i ca l g o r i t h m ib i o r t h o g o n a lw a v e l e t ，o p t i m a lw a v e l e t ，p a t t e r n r e c o g n i t i o n第一章绪言1 1 前言l 。1 。1 遗传算法的研究历史遗传算法是演化计算的一个分枝，也是人工智能发展的一个重要领域。它是受达尔文进化理论的思想而激发的一种用进化思想来解决问题的方法。遗传算法研究的兴起是在8 0 年代末和9 0 年代初期，但它的历史起源可追溯至6 0 年代初期。早期的研究大多以对自然系统的计算机模拟为主。如f r a s e r 的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想；同时代，演化计算思想首先是由i r e c h e n b e r g 于2 0世纪6 0 年代在他的著作演化策略( ”e v o l u t i o ns t r a t e g i e s - 一书中提出来的，然后一些研究者发展了他们的思想。h o l l a n d 和d e j o n g的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，h o l l a n d 于1 9 7 5 年出版的著名著作自然系统和人工系统的适配( ”a d a p t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ”) 系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，d e j o n g 的重要论文遗传自适应系统的行为分析将h o l l a n d 的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗传操作技术。可以认为，d e j o n g 所作的研究工作是遗传算法发展过程中的一个里程碑。进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。此后至今遗传算法的应用领域不断扩大，遗传算法应用研究已从初期的组合优化求解拓展到了许多更新，更工程化的应用方面。1 1 1生物背景达尔文的g t 然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括l第一章绪言种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存。不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展遗传算法正是模拟达尔文的这种遗传选择和自然淘汰的生物进化过程的计算模型，是一种具有“生存+ 检测”的迭代过程的搜索算法它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容作为一种新的全局优化搜索算法，遗传算法以其简单通用、稳定性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果。并逐渐成为重要的智能算法之一。1 2遗传算法的基本理论1 2 1遗传算法的基本步骤遗传算法的基本描述t 算法开始于一个用染色体形式表达的初始解集，总是用前一代解集的解来生成后一代解集的解，整个过程有一个进化思想，那就是新的一代总是要比旧的一代要好因此在选择产生新一代个体的父体时总是参照他们的适应值，适应值越大，再生的机会越大。进化的过程不断进行，直到满足终止条件，比如进化的代数或者适应值的改进趋势遗传算法的基本步骤：驰2 遗传算法的基本理论s t e p i ：随机产生代表问题的1 2 个可行解的n 个染色体x 构成的初始种群。s t e p 2 ：计算种群中每一个染色体x 的适应值“x ) 。s t e p 3 ：重复以下的步骤s t e p 4 至6 直到产生新的种群。s t e p 4 ：按适应值越大，概率越大的原则从种群中选择两个父辈染色体。s t e p 5 ：以一定的交叉概率交叉父辈染色体来形成新的后代染色体。s t e p 6 ：以一定的变异概率变异新产生的后代染色体。s t e p 7 ：检验终止条件是否满足，如果满足停止进化并返回当前种群中的最优解，不满足则返回s t e p 2 1 2 2 遗传算法的基本操作遗传算法包括三个基本操作；选择，交叉和变异。这些基本操作又有许多不同方法，我们逐一介绍。1 选择( s e l e c t i o n )选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。首先计算适应度：( 1 ) 按比例的适应度计算( p r o p o r t i o n a lf i t n e s sa s s i g n m e n t ) ；( 2 ) 基于排序的适应度计算( r a n k - b a s e df i t n e s sa s s i g n m e n t ) 适应度计算之后是实际的选择，按照适应度进行父代个体的选择。可以挑选以下的算法。( 1 ) 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) ；( 2 ) 随机遍历抽样( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) ；( 3 ) 局部选择( 1 0 c a ls e l c e t i o n ) ；( 4 ) 截断选择( t r u c a t i o ns e l e c t i o n ) ；( 5 ) 锦标赛选择( t o u r n a m e n ts e l e c t i o n ) 2 交叉( c r o s s o v e r )交叉是结合来自父代交配种群中的信息产生新的个体。依据个体4第一章绪言编码表示方法的不同，可以有以下的算法：( 1 ) 实值交叉( r e a lv a l u e dc r o s s o v e r )离散交叉( d e s c r e t ec r o s s o v e r )中间交叉( i n t e r m e d i a t ec r o s s o v e r )算术交叉( a r i t h m e t i cc r o s s o v e r )( 2 ) 二进制交叉( b i n a r yv a l u e dc r o s s o v e r )单点交叉( s i n g l e - p o i n tc r o s s o v e r )多点交叉( m u l t i p l e - p o i n tc r o s s o v e r )均匀交叉( u n i f o r mc r o s s o v e r )3 变异( m u t a t i o n )交叉之后的子代经历的变异是子代基因按小概率扰动产生的变化依据个体编码的表示方法的不同，可以有以下的算法：( 1 ) 实值变异( 2 ) 二进制变异1 2 3 遗传算法的特点遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：搜索过程不直接作用在变量上，而是在参数集进行了编码的个体此编码操作，使得遗传算法可直接对结构对象( 集合、序列、矩阵、树、图、链和表) 进行操作搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则对搜索空间没有任何特殊要求( 如连通性、凸性等) ，只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。遗传算法的优点是它并行性，在解空间的多个点同时进行搜索，因而很少陷入局部最优解。遗传算法比较容易实现，一旦你编了一个遗传算法程序，解决不同的问题时，往往你只需要修改编码方案和适】3 遗传算法应用中的几个关键问题应值函数就可以了，当然这个容易只是相对的，因为编码方案和适应值函数的选择有时候会变得很难。遗传算法的缺点是计算时间，比某些方法要稍微长一些，但是对于今天的高速计算机而言这并不是一个很大的问题。1 2 4 遗传算法的应用情况遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛用于很多学科领域，经常被用来解决复杂问题，像n p 难题，机器学习，程序进化，甚至在艺术方面被用来生成图片和音乐。它的一些主要应用领域有t非线形动力系统一一数据预测和分析神经网络设计lisp 程序演化策略计划蛋白质分子形状研究tsp 和计划表图像创建1 3遣传算法应用中的几个关键问题基于文献 1 4 以及具体的实践经验，我们总结了遗传算法应用中的几个关键问题当我们打算应用遗传算法来解决某个问题，那么面临的第一个问题是当前问题适不适合用遗传算法来处理? 有一些问题，求解过程等同于在一个庞大的解空间中搜索，每一个解由问题的本身的函数值或适应值评估优劣在解空间寻找极值( 最大值或者最小值) ，通过统计搜索时间预知搜索空间的大小，当然很好，但是经常是我们只知道当中的一些点，而随着搜索的进行自动生成其他点。已经发展了很多搜索方法，比如枚举法，爬山法，随机法，处理一些问题特别是局部最优解非常少时这些方法非常有效。但是有些问题的6第一章绪。言解的搜索有时非常复杂，它有很多的局部最优解，而先前的算法如随机搜索法，爬山法，一旦陷入了某个局部最优解，就很难再跳出来，这个时候我们就应该考虑使用遗传算法来解决问题。但是必须记住，用遗传算法找到的解经常只是被认为是一个好的解，因为很可能没有办法证明它是真正的最优解。处理各种各样的问题时，总的基本步骤都差不多，但是各个步骤具体实现往往差异很大，这就需要创造性思维。我们面临的第二个问题是选择怎样的编码来实现染色体。这个首先与要解决的问题本身的特点密切相关，其次要使得交叉和变异这两个基本的遗传算子的易于实现。解决实际问题的实践中产生很多编码方案：( 1 ) 二进制编码( 2 ) 实值编码基于历史原因过去人们常常使用的是二进制编码，现在绝大部分相关研究使用的是性能相对较好的实值编码第三个问题；选择什么样的交叉和变异算子?整个遗传算法的实现过程中，可以说交叉和变异是相当重要的两个环节，算法的性能主要由这两个算子影响，在具体应用当中，要求具体问题具体分析，这里是一个要求见多识广和充分发挥主观能动性的地方第四个问题t 遗传算法的参数选择在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群规模，交叉率，最大进化代数，这些参数对遗传算法的性能都有很重要的影响对这些参数有以下建议：( 1 ) 种群规模：一般说来，较大数目的初始种群可以同时处理更多的解，因而更加容易找到全局最优解，但是实践表明，巨大的种群规模并不能提高算法的性能，因为每次再生的迭代时间会加长，好的种群规模大约为2 0 , , 1 0 0 ，好的种群规模与编码方案也有关系3 遗传算法应用中的几个关键问题7( 2 ) 交叉概率交叉概率的选择决定了交叉操作的频率，频率越高，可以越快地收敛到最有希望的最优解区域，因此通常选择较大的交叉率，一般为6 0 一9 0 不要设为1 0 0 因为太高的交叉概率会导致过早收敛。( 3 ) 变异概率变异概率相反通常应当很小，一般设为5 一2 5 若设为1 0 0 退化成随机搜索，这样极其不稳定，设为0 容易陷入局部最优点而导致早熟现象( 4 ) 最大进化代数最大进化代数作为一种模拟终止条件，一般视具体情况而定，计算量小的问题取1 0 0 ，- , , 5 0 0 即可，而计算量大的问题，可能取到1 0 0 0 0 等值。对于具体问题而言，衡量参数设置恰当与否，要依据多次运行的收敛情况和解的质量来判断如果调整参数难以有效的提高遗传算法的性能，则往往需要借助对基本遗传算法的改进，改进的手段可以是多方面的，如适应度比例的调整，引入白适应交叉率和变异率，尝试其他的遗传操作，甚至采用混合方法第二章遗传算法在图像压缩中的应用2 1背景图像压缩是一个很有发展前途的研究领域，这一领域的突破对于通信和多媒体事业的发展将具有深远的影响。因此，在图像压缩方面进行深入的研究很有意义。小波分析是当前数学中一个迅速发展的新领域，它同时具有理论深刻和应用十分广泛的双重意义。将小波分析用于图像压缩是小波分析应用的一个重要方面。它的特点是压缩比高，压缩速度快，压缩后能保持信号与图像的特征不变，且在传递中可以抗干扰，像新一代的静止图像国际压缩标准j p e g 2 0 0 0 采用内核的就是小波变换一般情况下，压缩图像时使用的是某一组特定的性质比较好的小波，来对所有的图像进行压缩，在特定的评价标准下，会有一些图像的压缩效果不太好。我们试图对每一幅图像去寻找一组特定的小波，使得在给定的评价标准下，将图像压缩到最好的情况。而事实上，这个问题等同于一个有较多局部最优解的大范围搜索问题，因此本章尝试将小波变换和遗传算法结合起来应用于图像压缩，这方面的工作很少有入在做，包含了一系列的问题需要解决，如：选择合适的适应值函数，确定遗传算法的最佳参数，采用什么样的与小渡相匹配的遗传算子等等2 。2 小波分析的基础知识参考文献【5 1 1 】，我们先简介图像处理中所需的小波分析的基础知识。2 2 1 从f o u r i e r 分析到小波分析f o u r i e r 分析是一种将基于时间的信号变换为基于频率的信号的数学方法，设f ( t ) 为r 上以2 7 r 为周期的函数，用三2 ( 0 ，2 丌) 表示为r 上以2 7 r 为周期并且在( 0 ，2 1 r ) 上平方可积函数的全体。f ( t ) 的一91 0第二章遗传算法在图像压缩中的应用维f o u r i e r 变换由下式定义g ( m ) ) = f ( s ) = 伫巾) e - i 2 r s t d t( 2 1 )其中i 2 1 。当f ( t ) 是模拟信号时，它的定义域在实直线上，称之为时域，其f o u r i e r 变换f ( s ) 的定义域也是实数域，称之为频域。f o u r i e r变换是一个线性积分变换，f ( s ) 的f o u r i e r 逆变换定义为9 1 ( f ( s ) ) = ，( ) = 二f ( s ) e i 2 v s t d t( 2 2 )所谓频谱分析本质上就是对f ( s ) 的加工，分析和滤波等处理，随着计算技术的迅速发展，在这方面已经发展了一套行之有效的频域分析方法但是频谱函数f ( s ) 是将信号f ( t ) 按照正交函数系e 越2 州展开，而i e 士i 2 r t i = 1 ，因此，频谱f ( s ) 的任一频点的值都必须由信号f ( t ) 在整个时域( 一。，o o ) 上的贡献来决定；反之，信号某点的值也是由频谱f ( s ) 在整个频域( 一。，o 。) 上的贡献来决定。在不少实际应用问题中，我们所关心的恰恰是信号在局部时间范围，频率在特定区段的变化特性。此时用f o u r i e r 分析方法往往不是非常有效为了克服这些缺点，同时又保持f o u r i e r 分析方法的优点，人们开创和发展了小波分析方法，让小波函数妒既具有局部特征，很快衰减到零。同时又能够覆盖整个时域( 一o 。，o o ) 2 2 2 连续小波变换上2 ( r ) 表示实数轴上可测函数组成的平方可积空间，函数妒( t ) 驴( r ) 的f o u r i e r 变换为每( u ) = 仁喇e - i w t d t( 2 3 )当妒) 满足完全重构条件( 或者恒分辨条件)= e 铧d w 一( 2 4 )时，称函数妒( t ) 为一个基本小波或母小波。由于u 在积分的分母上，因此必须有声( o ) = 0 号e 州d 忙0( 2 5 )2 2 小波分析的基础知识1 1将母小波砂( t ) 经过伸缩和平移后得州归。毛矽( 竿)( 0 叩锄)( 2 6 )称其为一个小波序列，每个妒瓯b ( t ) 称为一个小波基函数。其中变量a反映了一个特定基函数的尺度( 伸缩情况) ，变量b 指明了它沿x 轴的平移位置。对于任意的函数( i ( t ) l 2 ( r ) ) 的连续小波变换的定义w l ( a , b ) = ( m ) ，o , b ) = 。一 e 弛) 妒( 等) 出( 2 7 )其重构公式( 逆变换) 为巾) = 啄1ee 。一2 w i ( a , 6 ) 钆删d 。d b( 2 8 )信号f ( t ) 可以通过小波变换完全恢复。2 2 3 离散小波变换为了适合计算机处理，连续小波变换必须离散化。对连续的尺度参数a 和连续的平移参数b 进行离散化，一般选取a = n i s , b = 七丽b o ，其中j ，k z ，0 a o 1 , b o r ，对应的离散小波函数如下：锄，k ( t ) = n 芦砂( o t 一是6 0 )( 2 9 )2 2 3 1 二进小波如果存在两个正常数a 和b ( 0 a b d 啦= d z , 2 ) d = d t a ，n )上j1 = 1 ，2 ，( 2 3 6 )b 1d 1 ，d 1 ，2 d 1 ，r 1图2 - 2图像小波重构示意图2 4 基于遗传算法的最优小波滤波器构造方法2 4 1研究背景长期以来，就有不少的学者在进行小波滤波器构造方法的研究，如s m i t h ，b a r n w e l l 和m i n t z e r 首先构造出正交小波，随后，v a i d y a n a t h a n和h o a n g 对具有线形相位的双正交小波的研究工作，而在m a l l a t 构建多尺度分析的框架理论基础之后，d a u b e c h i e s 构造出了离散紧支撑正交小波滤波器，紧跟着v e t t e r l i ，h e r l e y , f e a u v e a u 和d a u b e c h i e s等人相继成功构造出双正交小波滤波器，这些构造方法，大部分都是基于矩阵分析然而，对于图像压缩编码，进一步的难题是很难确定哪种小波基是最优的，影响的因素太多因为诸如光滑性、小波基支撑的尺寸以及频率选择性等指标都很重要，在不同的要求下会产生不同的结果另外，2 4 基于遗传算法的最优小溲滤波器构造方法1 7现在几乎所有的小波压缩编码器采用的都是可分离二维小波变换，这使得可把二维小波基的设计转化为一维小波基的设计。在最优基的选择方面，研究者们已经做了大量的工作。u n s e r 1 2 1的研究表明样条小波对基于近似理论的编码应用较为有效。r i o u l 1 3 的实验结果说明在压缩应用中，正交基的光滑性比较重要。a n t o n i n i等人【1 4 的实验表明光滑性和消失矩都很重要，而且光滑性显得比消失矩要稍微重要一些。v e t t e r l i 和h e r l e y 1 5 1 又指出”正则性对信号处理的重要性如何仍然是一个公开问题。实际中常使用的小波基介于一阶和二阶连续可微，更多的光滑性似乎并不能对编码产生明显的改善。值得一提的是w a n gg u o q i u 在文【1 6 】中提出了一种全新的小波滤波器的矩阵构造方法，该方法很容易操作。也正是在该方法的基础，本文结合遗传算法提出了异于前述方法的最优小波滤波器的构造方法。驺4 2 最优小波滤波器构造的遗传算法实现( 1 ) 染色体的编码方式我们寻求最优小波滤波器t k ) 和 鲰 ，在不考虑其他硬件软件实现特性的要求下，浮点数编码是一种有效方式，由于考虑的紧支撑双正交小波滤波器，t 和f 鲰) 要满足一系列条件( 2 2 8 ) 一( 2 3 3 ) ，。染色体的结构直接取决于这些条件，由文【1 6 】知，通过解这些条件构成的方程组，可以发现构成染色体的向量维数不会超过4 像构造满足5 阶消失矩条件的8 _ 8 小波滤波器时，每个染色体用一个实数x 就可以表示出来，并且x 的有效取值范围为( 一2 2 一o ) 表2 1 为它所代表的滤波器的高通和低通系数。表2 - 18 - 8 小波滤波器的高通和低通系数1 8第二章遗传算法在图像压缩中的应用低通 )高通 鼽)( 5 9 5 + 5 7 6 x + 1 8 5 x 2 + 2 0 x 3 ) ( 1 6 ( ( 3 + g ) 2 ) ( 5 + z ) )( 5 9 5 + 5 7 6 x + 1 8 5 x 2 + 2 0 x 3 ) ( 1 6 ( ( 3 + z ) 2 ) ( 5 + 茁) )一( ( 9 + 5 x ) ( 2 s + 1 7 x + 3 x 2 ) ) ( 1 6 ( ( 3 + 茁) 2 ) ( 5 + 。) )x ( 1 7 - 4 - 1 2 x - 4 - 3 x 2 ) ( 1 6 ( ( 3 + z ) 2 ) ( 5 - 4 - z ) )( 1 7 + 1 2 x + 3 x 2 ) ( 1 6 ( ( 3 - 4 - ) 2 ) ( 5 + ) )( 1 7 + 1 2 x + 3 x 2 ) ( 1 6 ( ( 3 + z ) 2 ) ( 5 + z ) )x ( 1 7 + 1 2 x + 3 x 2 ) ( 1 6 ( ( 3 + 。) 2 ) ( 5 + 。) )一( ( 9 + 5 x ) ( 2 s + 1 7 x - 4 - 3 x 2 ) ) ( 1 6 ( ( 3 + z ) 2 ) ( 5 + z ) )- ( 3 5 + 1 0 x ) ( 3 2 ( 3 十茁) )( 3 5 - 4 - 1 0 x ) ( 3 2 ( 3 + z ) )- ( 1 4 + 5 x ) ( 3 2 ( 3 - 4 - z ) )x ( 3 2 ( 3 + z ) )1 ( 3 2 ( 3 + z ) )- 1 ( 3 2 ( 3 + 。) )( - x ) ( 3 2 ( 3 + 。) )( 1 4 + 5 x ) ( 3 2 ( 3 - 4 - 茁) )( 2 ) 初始种群的产生大部分染色体都采用随机方式产生，随机函数为d o u b l er a n d v a l ( d o u b l el o w ，d o u b l eh i g h )d o u b l ev a l ；v a l = ( ( d o u b l e ) ( r a n d 0 3 2 7 f i s 0 ) * ( h i g h - l o w ) ) + l o w ；r e t u r n ( v a l ) ； r a n d ( ) 为c + + 语言的随机函数，随机产生0 到3 2 7 6 8 之间的一个数。h i g h 为上限，l o w 为下限，r a n d v a l ( ) 随机产生l o w 到h i g h 中的一个数像8 - 8 小波滤波器的初始种群用下述方式随机生成tv o i di n i t i a l i z e ( v o i d )i n t j ；f o r ( j 0 0 p o p s j z 功+ + )p o p s i z e 为种群规模p o p u l a t i o n j f i t n e s s = 0 ；染色体适应值p o p u l a t i o n j r f i t n e s s = o ；染色体选择概率p o p u l a t i o n j e f i t n e s s = o ；染色体累积概率p o p u l a t i o n j 1 0 w e r = 2 ，5 ；染色体适应值下限p o p u l a t i o n j u p p e r = o ；染色体适应值上限p o p u l a t i o n j g e n e = r a n d v a l ( p o p u l a t i o n 【j 1 0 w e r ，p o p u l a t i o n j u p p e r) ；染色体适应值的随机初始化)( 3 ) 适应值函数的构造2 4 基于遗传算法的最优小波滤波器构造方法我们的目标是寻求最优小波滤波器，从前面的讨论，可知影响这个最优标准的因素有很多，最终采用一个什么样的标准，要视具体情况来定。这里我们考虑有损压缩情况，而且只是要求在近似的压缩倍比情况下，图像经过小波变换编码解码以后，峰值信噪比达到最大。这里所说的近似的压缩倍指的是在对图像进行变换编码时，只是采用同一个编解码流程，而没有去严格控制压缩倍比，并且所有的质量损失集中在量化阶段，编码解码过程中认为没有质量损失。此时很自然地我们选择适应值函数为：_ v lp s n r ( h ，g ) = 1 0 ( 1 0 9 1 02 5 5 2 n l 0 9 1 0 ( x i 一氟) 2 )( 2 3 7 )i = 0其中戤为原图像像素值，面；为重构图像像素值图2 - 3 是适应值函数计算流程图r o o o o o o _ 1 _ - l _ _ _ _ _ i _ _l 源图像数据卜- + i 小被变按i l 量化l_ - _ _ _ i _ - j _ - _ _ - j - _ i l _ _ 图2 - 3 是适应值函数计算流程图图2 - 3 流程主要是通过量化压缩缩数据，简单起见，我们选取四种量化策略；( 1 ) 全l 量化：对小波变换之后的数据用1 做量化因子进行量化；( 2 ) 4 ：1 量化：对小波变换之后的数据的最外三层高频数据用4 做其他层用l 量化因子进行量化；( 3 ) 4 ：2 ：l 量化：对小波变换之后的数据的最外三层高频数据用4 次外三层高频数据用2 其他层用1 做量化因子进行量化；( 4 ) 8 ：4 ：1 量化：对小波变换之后的数据的最外三层高频数据用8 次外三层高频数据用4 其他层用1 做量化因子进行量化；图2 - 3 流程中编码我们采用的是适合小波系数编码的嵌入式零树编码与算术编码器。2 0第二章遗传算法在图像压缩中的应用( 4 ) 遗传算子的实现：采用适应于浮点数的算术交叉：如果y o 被选择交叉，产生的后代为x l = a z o + ( 1 一a ) y oy l = b x o + ( 1 - b ) y 0经过多次上机实验我们发现a = 0 7 0 7 ，b = o 6 1 8 时算法搜索性能较好。采用随机变异算子v o i dm u t a t e ( v o i d )i n t i ；d o u b l ex ：f o r ( i = o ；i p m u t a t i o n )p o p u l a t i o n i g e n e = r a n d v a l ( p o p u l a t i o n i 1 0 w e r ，p o p u l a t i o n i u p p e r) ；产生的随机数x 若大于变异概率p m u t a t i o n 就执行变异操作)采用基于染色体累积概率的轮盘选择算法：v o i ds e l e c t ( v o i d )i r l ti , j ：d o u b l ep ；f o r ( i = o ；i p o p s i z e ；i + + )r = r a n d ( 1 3 2 7 6 8 o ；随机产生一个浮点数r ，i f ( r p o p u l a t i o n 0 c f i t n e s s ) n e w p o p u l a t i o n i = p o p u l a t i o n 0 ；若r p l ( 累积概率) ，则选择第一个染色体e l s ef o r 0 = 0 妇 = p o p u l a t i o n j c f i t n e s sa n dr p o p u l a t i o n f j + 1 c f i t n e s s )n e w p o p u l a t i o n i = p o p u l a t i o n 【j + 1 ；2 5 实验结果分析2 1若p j = r p j + l ( 累积概率) ，则选择第j + 1 个染色体)在进化过程中我们还采用了最优保存选择法。( 5 ) 实验表明种群规模取5 0 ，变异概率取0 2 ，交叉概率取0 9 ，迭代次数取2 0 0 ，算法性能稳定，每次计算都能找到最优饵。2 5 1 实验结果分析2 5 实验结果分析参考文献m ( 1 8 9 】，借助c + + 和m a t l a b 编程工具，我们对四幅5 1 2 ) ( 5 1 2 ，8 位灰度的b m p 图进行了实算g o l d h i l lb a r b a r a图2 4 原图像( 1 ) l e n a 的适应值函数图像考虑的是5 阶消失矩阵条件8 - 8 族小波，染色体x 只有一维的简单情形，取值范围( 一2 2 ，0 ) ，可以作出适应值函数图像。第二章遗传算法在图像压缩中的应用图2 - 5 图( a ) l e n a 的适应值函数图像由于比例的关系，我们只给出了含全局最优解( 1 0 3 5 ) 的区域( 一1 0 4 5 1 0 3 ) 的适应值函数图像，即使是在这个小区域上图2 - 5 也充分刻画出问题的多峰性质，这个说明了待解问题有多个局部最优解，而在多个局部最优解中去搜寻全局最优解，这也是正是遗传算法的长处所在。( 2 ) 计算结果表2 - 2 计算所得p s n rp s n rl e n am a n d r i l lg o l d h i l lb a r b a r a塞! ：! 盐篁逝堡鎏垫墨叁夔兰由表2 - 4 的参数代入表2 1 中可以得到各种量化策略下的& 8 族最优小波的高通和低通系数t25 实验结果分析表2 - 5 计算所得l e n a 压缩所用的最优滤波器高通系数表2 - 6 计算所得l e n a 压缩所用的最优滤波器低通系数：a l l l0 7 1 3 80 7 1 3 80 2 1 2 7 0 0 3 2 90 0 3 1 80 0 3 1 80 0 3 2 9 0 2 1 2 74 ：10 5 7 7 40 5 7 7 4 0 ，0 3 2 7 0 1 0 6 30 0 6 1 50 0 6 1 5 0 1 0 6 3 0 0 3 2 74 ：2 ：10 5 8 4 30 5 8 4 3 0 0 4 2 7 0 1 0 0 90 0 5 9 30 0 5 9 3 0 1 0 0 9 0 0 4 2 78 ：4 ：10 5 8 4 00 5 8 4 0 0 0 4 2 2 ，0 1 0 1 l0 0 5 9 40 0 5 9 4 0 1 0 1 1 0 0 4 2 2本章固定压缩比，基于p s n r 对8 - 8 族紧支撑双正交小波进行寻优，如果适当修改适应值函数的实现，那么该方法可以从压缩比和p s n r 结合的角度对其他各族小波进行寻优，且对于正交小波同样也是适用的，推广开来，对于小波分析理论应用的其他领域，遗传算法亦可以作为一个强有力的寻优工具。本文方法的特点就是以时间换取压缩效率，如能加快计算速度或将之应用于对时间相对要求不高的的领域，那么该方法的效率则会有显著提高。第三章遗传算法在模式识别中的应用3 1模式识别随着数字图像处理技术的发展和实际应用的需要，存在一类问题，例如要从遥感图像中分割出各种农作物，森林资