研究生课程论文格式.doc

五邑大学研究生实验报告 软计算方法及其应用20102011年度 第2学期题目： 遗传算法在图像处理中的应用院系：专业：八个1学号：姓名：任课教师： 成绩评定：完成日期： 年 月 日遗传算法在图像处理中的应用摘要：遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度运行、随机、自适应搜索算法。文章介绍了遗传算法的基本原理，分析了其特点。在图像处理领域有很多优化问题，实际上都等同于一个大范围搜索寻优间题，而最优化问题是遗传算法经典应用领域，因此遗传算法完全胜任在图像处理中优化方面的计算。本文主要研究了遗传算法在图像压缩中的应用策略。关键词：遗传算法，最优小波，图像压缩Abstract: Genetic algonitthm is a class of high collateral、atochastic selfreliance search algonithms witch based on mechanism of nature genetic.This paper introduce its principium and discussed them.There are many optimization problems in the field of digitalimage proeessing，all these problems can be generalized as the problem of searehing for aglobal optimal solution in a large solution spaee，which is the classic application field of genetie algorithm. On the major premise of feasibility of this theory，this artiele has done some further research work about the applieation of genetic algorithm for image compression.Keywords: Genetic algorithm， Optimal wavelet，image compression1、遗传算法的基本理论遗传算法的基本描述：算法开始于一个用染色体形式表达的初始解集，总是用前一代解集的解来生成后一代解集的解，整个过程有一个进化思想，那就是新的一代总是要比旧的一代要好。因此在选择产生新一代个体的父体时总是参照他们的适应值，适应值越大，再生的机会越大。进化的过程不断进行，直到满足终止条件，比如进化的代数或者适应值的改进趋势。1.1遗传算法的基本步骤:1：随机产生代表问题的n个可行解的n个染色体x构成的初始种群。2：计算种群中每一个染色体x的适应值f(x)。3：重复以下的步骤STEP4至6直到产生新的种群。4：按适应值越大，概率越大的原则从种群中选择两个父辈染色体。5：以一定的交叉概率交叉父辈染色体来形成新的后代染色体。6：以一定的变异概率变异新产生的后代染色体。7：检验终止条件是否满足，如果满足停止进化并返回当前种群中的最优解，不满足则返回。1.2遗传算法的基本操作遗传算法包括三个基本操作:选择，交叉和变异。这些基本操作又有许多不同方法。1选择(seleetion)选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。首先计算适应度：(l)按比例的适应度计算(proportional fitness assignment);(2)基于排序的适应度计算(rank-based fitness assignment)适应度计算之后是实际的选择，按照适应度进行父代个体的选择。可以挑选以下的算法。(1)轮盘赌选择(roulette wheel selection);(2)随机遍历抽样(stoehastie universal Sampling);(s)局部选择(local seleetion);(4)截断选择(trueation selection);(5)锦标赛选择(tournament Selection);2交叉(crossover)交叉是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有以下的算法:(1)实值交叉(real valued crossover)离散交叉(deserete crossover)中间交叉(intermediateerossover)算术交叉(arithmetie crossover)(2)二进制交叉(binary valued crossover)单点交叉(single-point crossover)多点交叉(multiple-point crossover)均匀交叉(uniform crossover)3变异(mutation)交叉之后的子代经历的变异是子代基因按小概率扰动产生的变化。依据个体编码的表示方法的不同，可以有以下的算法：(l)实值变异(2)二进制变异1.3遗传算法的特点遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象(集合、序列、矩阵、树、图、链和表)进行操作。搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化.采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求(如连通性、凸性等)，只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。遗传算法的优点是它并行性，在解空间的多个点同时进行搜索，因而很少陷入局部最优解。遗传算法比较容易实现，一旦你编了一个遗传算法程序，解决不同的问题时，往往你只需要修改编码方案和适应值函数就可以了，当然这个容易只是相对的，因为编码方案和适应值函数的选择有时候会变得很难。遗传算法的缺点是计算时间，比某些方法要稍微长一些，但是对于今天的高速计算机而言这并不是一个很大的问题。2、遗传算法在图像压缩中的应用图像压缩是一个很有发展前途的研究领域，这一领域的突破对于通信和多媒体事业的发展将具有深远的影响。因此，在图像压缩方面进行深入的研究很有意义。小波分析是当前数学中一个迅速发展的新领域，它同时具有理论深刻和应用十分广泛的双重意义。将小波分析用于图像压缩是小波分析应用的一个重要方面。它的特点是压缩比高，压缩速度快，压缩后能保持信号与图像的特征不变，且在传递中可以抗干扰，像新一代的静止图像国际压缩标准JPEG2000采用内核的就是小波变换。一般情况下，压缩图像时使用的是某一组特定的性质比较好的小波，来对所有的图像进行压缩，在特定的评价标准下，会有一些图像的压缩效果不太好。我们试图对每一幅图像去寻找一组特定的小波，使得在给定的评价标准下，将图像压缩到最好的情况。而事实上，这个问题等同于一个有较多局部最优解的大范围搜索问题，因此本章尝试将小波变换和遗传算法结合起来应用于图像压缩，包含了一系列的问题需要解决，如：选择合适的适应值函数，确定遗传算法的最佳参数，采用什么样的与小波相匹配的遗传算子等等。对于图像压缩编码，难题是很难确定哪种小波基是最优的，影响的因素太多因为诸如光滑性、小波基支撑的尺寸以及频率选择性等指标都很重要，在不同的要求下会产生不同的结果。另外，现在几乎所有的小波压缩编码器采用的都是可分离二维小波变换，这使得可把二维小波基的设计转化为一维小波基的设计。本文结合遗传算法提出了最优小波滤波器的构造方法。2.1最优小波滤波器构造的遗传算法最优小波滤波器构造的遗传算法实现：(l)染色体的编码方式我们寻求最优小波滤波器和，在不考虑其他硬件软件实现特性的要求下，浮点数编码是一种有效方式，由于考虑的紧支撑双正交小波滤波器，和要满足一系列条件，染色体的结构直接取决于这些条件，通过解这些条件构成的方程组，可以发现构成染色体的向量维数不会超过4。像构造满足5阶消失矩条件的8-8小波滤波器时，每个染色体用一个实数x就可以表示出来，并且x的有效取值范围为(-2.20)。 (2)初始种群的产生大部分染色体都采用随机方式产生，随机函数为double randval(double low，double high)double val;val=(double)(rand()/32768.0)*(high-low)+low;return(val);/rand()为C+语言的随机函数，随机产生0到32768之间的一个数，high为上限，low为下限，randval()随机产生law到high中的一个数。像8-8小波滤波器的初始种群用下述方式随机生成：void initialize(void)int j;for(j=o;jPOPSIZE;j+) /POPSIZE为种群规模populationj.fitness=0;/染色体适应值populationj.rfitness=0;/染色体选择概率populationj.cfitness=0; /染色体累积概率populationj.lower=-2.5; /染色体适应值下限populationj.upper=0;/染色体适应值上限populationj.gene=randval(populationj.lower，populationj.upper);/染色体适应值的随机初始化(3)适应值函数的构造我们的目标是寻求最优小波滤波器，从前面的讨论，可知影响这个最优标准的因素有很多，最终采用一个什么样的标准，要视具体情况来定.这里我们考虑有损压缩情况，而且只是要求在近似的压缩倍比情况下，图像经过小波变换编码解码以后，峰值信噪比达到最大。这里所说的近似的压缩倍指的是在对图像进行变换编码时，只是采用同一个编解码流程，而没有去严格控制压缩倍比，并且所有的质量损失集中在量化阶段，编码解码过程中认为没有质量损失。此时很自然地我们选择适应值函数为：其中为原图像像素值，为重构图像像素值。图2-3是适应值函数计算流程图。源图像数据小波变换量化编码解码小波逆变换重建图像数据图2-3适应值函数计算流程图。图2-3流程主要是通过量化压缩缩数据简单起见，我们选取四种量化策略:(l)全1量化：对小波变换之后的数据用1做量化因子进行量化；(2)4:1量化：对小波变换之后的数据的最外三层高频数据用4做其他层用1量化因子进行量化；(s)4:2:1量化：对小波变换之后的数据的最外三层高频数据用4次外三层高频数据用2其他层用1做量化因子进行量化；(a)8:4:1量化：对小波变换之后的数据的最外三层高频数据用8次外三层高频数据用4其他层用l做量化因子进行量化；图2-3流程中编码我们采用的是适合小波系数编码的嵌入式零树编码与算术编码器。(4)遗传算子的实现：采用适应于浮点数的算术交叉：如果，被选择交叉，产生的后代为过多次上机实验我们发现a=0.707，b=0.618时算法搜索性能较好。采用随机变异算子void mutate(void)int i;double x;for(i=0;iPMUTATION)populationi.gene=randval(populationi.lower，populationi.upper);/产生的随机数x若大于变异概率PMUTATION就执行变异操作采用基于染色体累积概率的轮盘选择算法：void select(void)int i，j;double p;for(i=0;iPOPSIZE;i+)r=rand()/32768.0;/随机产生一个浮点数r，if(rpopulation0.cfitness)newpopulationi=population0;/若rp1(累积概率)，则选择第一个染色体elsefor(j=O;j=populationj.cfitnessANDrpopul