动态聚类算法及模拟退火算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,目录,动态聚类算法:C-均值算法或K-均值算法,矢量量化图像压缩编码方法,程序实例,模拟退火算法,回归分析及其它,MATLAB编程简述,课外任务,参考文献,上机实习,1,内容简述,图像压缩编码概述,矢量量化编码,2：图像压缩编码概述,2.1：图像压缩编码的必要性和可能性,2.2：图像压缩编码的一般框图,2.3：图像压缩编码的基本方法,2.4：图像压缩编码的国际标准,2.1：图像压缩编码的必要性和可能性,以指纹库为例，若以5125128 bit 的灰度图像来存储一个手指的指纹，一个40万人的指纹库，每人十指，则共需1000GB的存储量。,图像信号可以压缩的根据来自两个方面：一方面是图像信号中存在大量冗余度可供压缩，并且这种冗余度在解码后还可无失真地恢复；另一方面可以利用人的视觉特性，在不被主观视觉觉察的容限内，通过减少表示信号的精度，以一定的客观失真换取数据压缩。,图像信号的冗余度存在于结构和统计两方面。图像信号结构上的冗余度表现为很强的空间（帧内的）和时间（帧间的）相关性。信号统计上的冗余度来源于被编码信号概率密度分布的不均匀。,2.2：图像压缩编码一般框图,2.3：图像压缩编码的基本方法,统计编码、预测编码、变换编码、子带编码、模型编码、分形编码、序列图像的运动估值和运动补偿、小波变换编码、矢量量化编码、数学形态学方法、人工神经网络方法,3：矢量量化编码,3.1：矢量量化的基本思想,3.2：矢量量化的数学实质,3.3：矢量量化的LBG算法及其性能,3.4：LBG算法的缺陷,3.5：模拟退火的物理背景,3.6：模拟退火算法能量下降示意及描述,3.7：基于模拟退火的LBG改进算法,3.8：改进算法的几点说明,3.9：算法分析,3.10：实验及结论,3.1：矢量量化的基本思想,把图像看成是一串数据，设这一串数据大小为,m,，把它截成,M,段（一般每段相等，例如为,k,），即把,m,个数据变成了,M,个矢量，再把这,M,个矢量分成,N,组，对每个组挑选一个数据矢量作为这个组的代表，例如第,j,个组的代表为,y,j,，,j,=0，1，,N,-1。而压缩，就是图像中的数据矢量，如果属于第,j,个组，则这个数据矢量就用这个组的代表矢量,y,j,代替，这时的编码就是在相应的位置上记下编号,j,，而不必记下矢量,y,j,本身。集合,y,j,，,j,=0，1，,N,-1称为码书。其中,N,称为码书长度，或码书大小。,3.2：矢量量化的数学实质,从数学的观点，矢量量化可以定义为从,k,维欧几里德空间,R,k,到其一个有限子集,C,的映射，即,Q,：,R,k,-C,，其中,C,=,C,1,C,2,C,N,|,C,i,R,k,称为码书。,C,i,称为码字。该映射满足：,Q,（,V,|,V,R,k,，,V,=（,v,1,v,2,v,k,）=,C,i,，其中,C,i,=（,C,i1,C,i2,C,ik,）为码书,C,中的码字，并满足,其中，为矢量,V,与码字,C,j,之间的失真测度。,3.3,：矢量量化的LBG算法,LBG算法是Y.Linde，A.Buzo与R.M.Gray在1980年给出的矢量量化算法，以后有许多人进行了改进。其思想是：对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书，再把训练序列按码书中的元素分组，对这一分组再找每组的中心得到新的码书，转而把新码书作为初始码书再进行上述过程直到满意为止。,LBG算法的性能,续,同时，为了更形象地对比算法性能并得到算法的有关结论，把LBG算法在三种不同初始码书情况下迭代搜索过程中的总平均失真数据变化过程绘成曲线，得到总平均失真迭代收敛图。图1是在收敛阈值=0.0005时LBG算法在三种不同初始码书情况下迭代寻优搜索过程中的总平均失真下降曲线图对比。其中（a）为等间隔法的收敛效果图；（b）为三种不同初始码书对应的收敛效果图，+表示随机法、o表示等间隔法、*表示分裂法。,续,由表1和图1可得到如下结论：,是LBG算法对初始码书敏感。因为三种不同初始码书生成方法得到的初始码书在LBG算法作用下收敛到不同的结果，这可从表1中三个对比指标的实验结果得到清楚地反映。反映在图1（b）中为三条不同的收敛曲线。,续,是初始码书有“优、劣”之分。这是因为：从LBG的算法原理（实质就是动态聚类）可以看出，LBG算法需要一个足够大的能大致反映输入矢量的概率分布情况训练样本集，在这个前提下，LBG算法的收敛效果才比较理想。但由于受计算量的限制，无法使用很大的训练样本集，通常的做法是假设图像是各态经历的，因而可取若干副典型的图像作为训练图像。从而导致越能反映“输入矢量的概率分布”的初始码书其性能必然越好这一结论。换句话说，初始码书的“优、劣”可以通过其对输入矢量的概率分布的反映这一指标来度量。根据这一思路以及表1的实验结果可以发现：等间隔方法是一种性能优良（能大致反映输入矢量的概率分布）并且操作简便（计算量远远低于性能相当的分裂法）的初始码书生成方法。反映在图1（b）中为等间隔法的收敛曲线介于随机法和分裂法之间，但接近于分裂法的收敛曲线。,续,是LBG算法虽然能够收敛，但容易陷入局部最优。这一点可从表1中三种不同初始码书生成方法在不同收敛阈值条件下的实验结果对比得到解释。如对于等间隔法，当收敛阈值由0.005变为0.0005时，其峰值信噪比总改善了不到0.1 dB（0.0635dB），总平均失真也只改善了11左右，但迭代次数却增加了20次；同样地，当收敛阈值由0.0005变成0.00005时，其峰值信噪比改善了不到0.01 dB（0.0071dB），总平均失真也只改善了1左右，但迭代次数却增加了17次。导致这种结果的原因就是LBG算法在迭代寻优的过程中陷入了一种局部最优而趋于收敛。关于这一点在图1中可以得到进一步的证实：反映在图1中表现为迭代10次之后收敛速度明显下降，迭代到20次后几乎已经陷入局部最优，所以收敛曲线的后段趋于平直。也就是说，在这种情况下，再次迭代搜索对于算法性能的提高和改善是有限的，甚至是没有必要的。,3.4：LBG算法的缺陷,经典的码书设计算法LBG算法，由于它具有如下缺陷：一是尽管LBG算法能够保证收敛，但不能保证收敛到全局最优点；二是LBG算法的收敛结果对初始码书的选择敏感；三是码书中存在永不使用的码本。本文针对矢量量化中码书设计实质就是搜索“全局”最优解的这一点上，引入模拟退火思想对经典的LBG算法进行改进。,3.5：模拟退火的物理背景,在物理学中，对固体物质进行退火处理时，通常先将它加温溶化，使其中的粒子可以自由地运动，然后随着物质温度的下降，粒子也形成了低能态的晶格。若在凝结点附近的温度下降速度足够慢，则固体物质一定会形成最低能量的基态。对于组合优化问题来说，它也有类似的过程，也就是说物理中固体物质的退火过程与组合优化问题具有类似性。组合优化问题也是在解空间寻求花费函数最小（或最大）的解。,3.6：模拟退火算法能量下降示意及描述,该能量函数曲线上有两个极小点,A,和,B,，其中,A,为一局部极小点，,B,为,一全局极小点。如果我们将一小球,（代表系统的初态）放在如图所示,的位置，那么通过系统状态的改变，,能量必将到达极小点,A,。如果我们在,系统中引入噪声，使整个系统产生,振动，那么小球可能从,A,的附近被摇,到,B,的附近。一种可行的方法是：先让系统剧烈振动，使小球脱离,A,，然后轻轻摇，使小球逐步到达,B,，这样就寻找到了能量函数的全局极小值。,3.7：基于模拟退火的LBG改进算法,由于矢量量化码书设计的数学实质就是寻找一个具有全局意义下的最优解。无论是用聚类的观点还是神经网络的观点，所解决的都是一个全局寻优的策略或者说方法的问题。模拟退火算法对于解决大规模、非线性的全局寻优问题具有较好的性能。在此，把“最优”的度量映射为模拟退火中的能量函数，具体地说，就是把对码书的评价函数总失真函数映射成退火算法中的能量函数。从而，只需在LBG算法的第（2）步后面加入模拟退火算法就可以构成基于模拟退火算法的LBG改进算法。,3.8：改进算法的几点说明,1）,扰动因子的引入和度量,2）随机扰动策略的制定和扰动量的确定,3）退火过程中稳定性判据,4）温度的控制,3.9：算法分析,模拟退火算法用Metroplis算法产生组合优化问题解的序列，并由Metroplis准则对应的转移概率：,3.10：实验及结论,通过引入模拟退火算法对传统的LBG算法进行改进，在收敛阈值为=1.25e-5时，达到如下效果：收敛速度没有因为退火的引入而提高，反而降低了3次搜索，这是通过退火过程中参数有效控制而达到的；有效地改善了解的质量，总平均失真减少了8.23左右；一定程度上改善了图像质量，,PSNR,提高了0.1742,dB,。,II 回归分析及其它,回归分析,农作物施肥效果分析(CMCM-92A),判别分析,蠓虫分类(AMCM-89A):神经网络,方差分析与相关分析,主成分分析(降维技术),参考文献,1 李尚志.数学建模竞赛教程M.江苏教育出版社,1996.,2 梅长林,范金城.数据分析方法M.高等教育出版社,2006.,3 郭科.多元数理统计方法及其应用M.电子科技大学出版社,2006.,III Matlab编程简述,数值处理入门(见PDF),编程入门(见PDF),图形处理:插值与拟合(见PDF),程序实例:科学计算(见WORD),一点说明,关于提问,建议先思索,强调独立解决问题,提倡讨论和交流,论坛:资源共享与经验交流平台,提问,可以在论坛上谈经验与感受等,资源共享,IV 课外任务,参考文献,1 李尚志.数学建模竞赛教程M.江苏教育出版社,1996.,2 梅长林,范金城.数据分析方法M.高等教育出版社,2006.,3 郭科.多元数理统计方法及其应用M.电子科技大学出版社,2006.,4 杨建刚.人工神经网络实用教程M.浙江大学出版社,2001.,5 其它关于MATLAB教程的书籍或电子资料.,上机任务,Matlab科学计算程序实现,Matlab插值与拟合方法以及简单数理统计分析,Matlab函数以及脚本m文件编写与程序调试,各种数据分析方法的程序实现或软件实现(回归、判别、聚类、主成分、方差分析、相关分析等),模拟退火算法实现(随机数产生),