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

1、动态聚类算法及模拟退火算法主讲：王茂芝 副教授目录n动态聚类算法:C-均值算法或K-均值算法n矢量量化图像压缩编码方法n程序实例n模拟退火算法n回归分析及其它nMATLAB编程简述n课外任务n参考文献n上机实习1 内容简述n图像压缩编码概述图像压缩编码概述n矢量量化编码矢量量化编码2：图像压缩编码概述：图像压缩编码概述2.1：图像压缩编码的必要性和可能性：图像压缩编码的必要性和可能性2.2：图像压缩编码的一般框图：图像压缩编码的一般框图2.3：图像压缩编码的基本方法：图像压缩编码的基本方法2.4：图像压缩编码的国际标准：图像压缩编码的国际标准2.1：图像压缩编码的必要性和可能性：图像压缩编码的

2、必要性和可能性以指纹库为例，若以以指纹库为例，若以5125128 bit 的灰度图的灰度图像来存储一个手指的指纹，一个像来存储一个手指的指纹，一个40万人的指纹库，每万人的指纹库，每人十指，则共需人十指，则共需1000GB的存储量。的存储量。 图像信号可以压缩的根据来自两个方面：一方面图像信号可以压缩的根据来自两个方面：一方面是图像信号中存在大量冗余度可供压缩，并且这种冗是图像信号中存在大量冗余度可供压缩，并且这种冗余度在解码后还可无失真地恢复；另一方面可以利用余度在解码后还可无失真地恢复；另一方面可以利用人的视觉特性，在不被主观视觉觉察的容限内，通过人的视觉特性，在不被主观视觉觉察的容限内，

3、通过减少表示信号的精度，以一定的客观失真换取数据压减少表示信号的精度，以一定的客观失真换取数据压缩。缩。 图像信号的冗余度存在于结构和统计两方面。图图像信号的冗余度存在于结构和统计两方面。图像信号结构上的冗余度表现为很强的空间（帧内的）像信号结构上的冗余度表现为很强的空间（帧内的）和时间（帧间的）相关性。信号统计上的冗余度来源和时间（帧间的）相关性。信号统计上的冗余度来源于被编码信号概率密度分布的不均匀。于被编码信号概率密度分布的不均匀。 2.2：图像压缩编码一般框图：图像压缩编码一般框图2.3：图像压缩编码的基本方法：图像压缩编码的基本方法统计编码、预测编码、变换编码、子带编码、模统计编码、

4、预测编码、变换编码、子带编码、模型编码、分形编码、序列图像的运动估值和运动补偿、型编码、分形编码、序列图像的运动估值和运动补偿、小波变换编码、矢量量化编码、数学形态学方法、人小波变换编码、矢量量化编码、数学形态学方法、人工神经网络方法工神经网络方法2.4：图像压缩编码的国际标准：图像压缩编码的国际标准 静像压缩编码标准：静像压缩编码标准：J PEG系列系列 动像压缩编码标准：动像压缩编码标准：MPEG系列系列 会议电视和甚低码率压缩标准：会议电视和甚低码率压缩标准：H.26X系列系列3：矢量量化编码：矢量量化编码3.1：矢量量化的基本思想：矢量量化的基本思想3.2：矢量量化的数学实质：矢量量化

5、的数学实质3.3：矢量量化的：矢量量化的LBG算法及其性能算法及其性能3.4：LBG算法的缺陷算法的缺陷3.5：模拟退火的物理背景：模拟退火的物理背景3.6：模拟退火算法能量下降示意及描述：模拟退火算法能量下降示意及描述3.7：基于模拟退火的：基于模拟退火的LBG改进算法改进算法3.8：改进算法的几点说明：改进算法的几点说明3.9：算法分析：算法分析3.10：实验及结论：实验及结论3.1：矢量量化的基本思想：矢量量化的基本思想 把图像看成是一串数据，设这一串数据大小为把图像看成是一串数据，设这一串数据大小为m，把它截成把它截成M段（一般每段相等，例如为段（一般每段相等，例如为k），即把），即把

6、m个个数据变成了数据变成了M个矢量，再把这个矢量，再把这M个矢量分成个矢量分成N组，对每组，对每个组挑选一个数据矢量作为这个组的代表，例如第个组挑选一个数据矢量作为这个组的代表，例如第j个个组的代表为组的代表为yj，j=0，1，N-1。而压缩，就是图。而压缩，就是图像中的数据矢量，如果属于第像中的数据矢量，如果属于第j个组，则这个数据矢量个组，则这个数据矢量就用这个组的代表矢量就用这个组的代表矢量yj代替，这时的编码就是在相代替，这时的编码就是在相应的位置上记下编号应的位置上记下编号j，而不必记下矢量，而不必记下矢量yj本身。集合本身。集合yj，j=0，1，N-1称为码书。其中称为码书。其中N

7、称为码书称为码书长度，或码书大小。长度，或码书大小。3.2：矢量量化的数学实质：矢量量化的数学实质 从数学的观点，矢量量化可以定义为从从数学的观点，矢量量化可以定义为从k维欧几维欧几里德空间里德空间Rk到其一个有限子集到其一个有限子集C的映射，即的映射，即Q：Rk-C，其中其中C=C1,C2,CN | CiRk 称为码书。称为码书。Ci称为码称为码字。该映射满足：字。该映射满足：Q（V|VRk ，V=（v1,v2,vk）= Ci，其中，其中Ci=（Ci1, Ci2, Cik）为码书）为码书C中的码字，中的码字，并满足并满足 其中，其中， 为矢量为矢量V与码字与码字Cj之间的失真测度。之间的失真

8、测度。 ),(min),(1jNjiCVdCVd),(jCVd3.3：矢量量化的：矢量量化的LBGLBG算法算法 LBG算法是算法是Y.Linde，A.Buzo与与R.M.Gray在在1980年给出的矢量量化算法，以后有许多人进行了改年给出的矢量量化算法，以后有许多人进行了改进。其思想是：对于一个训练序列，先找出其中心，进。其思想是：对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书，再把训练序列按码书再用分裂法产生一个初始码书，再把训练序列按码书中的元素分组，对这一分组再找每组的中心得到新的中的元素分组，对这一分组再找每组的中心得到新的码书，转而把新码书作为初始码书再进行上述过程直码

9、书，转而把新码书作为初始码书再进行上述过程直到满意为止。到满意为止。 LBG算法的性能续n同时，为了更形象地对比算法性能并得到算法的有关结论，把LBG算法在三种不同初始码书情况下迭代搜索过程中的总平均失真数据变化过程绘成曲线，得到总平均失真迭代收敛图。图1是在收敛阈值=0.0005时LBG算法在三种不同初始码书情况下迭代寻优搜索过程中的总平均失真下降曲线图对比。其中（a）为等间隔法的收敛效果图；（b）为三种不同初始码书对应的收敛效果图，+表示随机法、o表示等间隔法、*表示分裂法。续n由表1和图1可得到如下结论：n是LBG算法对初始码书敏感。因为三种不同初始码书生成方法得到的初始码书在LBG算法

10、作用下收敛到不同的结果，这可从表1中三个对比指标的实验结果得到清楚地反映。反映在图1（b）中为三条不同的收敛曲线。续n是初始码书有“优、劣”之分。这是因为：从LBG的算法原理（实质就是动态聚类）可以看出，LBG算法需要一个足够大的能大致反映输入矢量的概率分布情况训练样本集，在这个前提下，LBG算法的收敛效果才比较理想。但由于受计算量的限制，无法使用很大的训练样本集，通常的做法是假设图像是各态经历的，因而可取若干副典型的图像作为训练图像。从而导致越能反映“输入矢量的概率分布”的初始码书其性能必然越好这一结论。换句话说，初始码书的“优、劣”可以通过其对输入矢量的概率分布的反映这一指标来度量。根据这

11、一思路以及表1的实验结果可以发现：等间隔方法是一种性能优良（能大致反映输入矢量的概率分布）并且操作简便（计算量远远低于性能相当的分裂法）的初始码书生成方法。反映在图1（b）中为等间隔法的收敛曲线介于随机法和分裂法之间，但接近于分裂法的收敛曲线。续n是LBG算法虽然能够收敛，但容易陷入局部最优。这一点可从表1中三种不同初始码书生成方法在不同收敛阈值条件下的实验结果对比得到解释。如对于等间隔法，当收敛阈值由0.005变为0.0005时，其峰值信噪比总改善了不到0.1 dB（0.0635dB），总平均失真也只改善了11左右，但迭代次数却增加了20次；同样地，当收敛阈值由0.0005变成0.00005

12、时，其峰值信噪比改善了不到0.01 dB（0.0071dB），总平均失真也只改善了1左右，但迭代次数却增加了17次。导致这种结果的原因就是LBG算法在迭代寻优的过程中陷入了一种局部最优而趋于收敛。关于这一点在图1中可以得到进一步的证实：反映在图1中表现为迭代10次之后收敛速度明显下降，迭代到20次后几乎已经陷入局部最优，所以收敛曲线的后段趋于平直。也就是说，在这种情况下，再次迭代搜索对于算法性能的提高和改善是有限的，甚至是没有必要的。3.4：LBG算法的缺陷算法的缺陷 经典的码书设计算法经典的码书设计算法LBG算法，由于它具有如下算法，由于它具有如下缺陷：一是尽管缺陷：一是尽管LBG算法能够保

13、证收敛，但不能保证算法能够保证收敛，但不能保证收敛到全局最优点；二是收敛到全局最优点；二是LBG算法的收敛结果对初始算法的收敛结果对初始码书的选择敏感；三是码书中存在永不使用的码本。码书的选择敏感；三是码书中存在永不使用的码本。本文针对矢量量化中码书设计实质就是搜索本文针对矢量量化中码书设计实质就是搜索“全局全局”最优解的这一点上，引入模拟退火思想对经典的最优解的这一点上，引入模拟退火思想对经典的LBG算法进行改进。算法进行改进。 3.5：模拟退火的物理背景：模拟退火的物理背景在物理学中，对固体物质进行退火处理时，通常在物理学中，对固体物质进行退火处理时，通常先将它加温溶化，使其中的粒子可以自

14、由地运动，然先将它加温溶化，使其中的粒子可以自由地运动，然后随着物质温度的下降，粒子也形成了低能态的晶格。后随着物质温度的下降，粒子也形成了低能态的晶格。若在凝结点附近的温度下降速度足够慢，则固体物质若在凝结点附近的温度下降速度足够慢，则固体物质一定会形成最低能量的基态。对于组合优化问题来说，一定会形成最低能量的基态。对于组合优化问题来说，它也有类似的过程，也就是说物理中固体物质的退火它也有类似的过程，也就是说物理中固体物质的退火过程与组合优化问题具有类似性。组合优化问题也是过程与组合优化问题具有类似性。组合优化问题也是在解空间寻求花费函数最小（或最大）的解。在解空间寻求花费函数最小（或最大）

15、的解。 3.6：模拟退火算法能量下降示意及描述：模拟退火算法能量下降示意及描述 该能量函数曲线上有两个极小点该能量函数曲线上有两个极小点A和和B，其中，其中A为一局部极小点，为一局部极小点，B为为一全局极小点。如果我们将一小球一全局极小点。如果我们将一小球（代表系统的初态）放在如图所示（代表系统的初态）放在如图所示的位置，那么通过系统状态的改变，的位置，那么通过系统状态的改变，能量必将到达极小点能量必将到达极小点A。如果我们在。如果我们在系统中引入噪声，使整个系统产生系统中引入噪声，使整个系统产生振动，那么小球可能从振动，那么小球可能从A的附近被摇的附近被摇到到B的附近。一种可行的方法是：先让

16、系统剧烈振动，的附近。一种可行的方法是：先让系统剧烈振动，使小球脱离使小球脱离A，然后轻轻摇，使小球逐步到达，然后轻轻摇，使小球逐步到达B，这样，这样就寻找到了能量函数的全局极小值。就寻找到了能量函数的全局极小值。3.7：基于模拟退火的：基于模拟退火的LBG改进算法改进算法由于矢量量化码书设计的数学实质就是寻找一个由于矢量量化码书设计的数学实质就是寻找一个具有全局意义下的最优解。无论是用聚类的观点还是具有全局意义下的最优解。无论是用聚类的观点还是神经网络的观点，所解决的都是一个全局寻优的策略神经网络的观点，所解决的都是一个全局寻优的策略或者说方法的问题。模拟退火算法对于解决大规模、或者说方法的

17、问题。模拟退火算法对于解决大规模、非线性的全局寻优问题具有较好的性能。在此，把非线性的全局寻优问题具有较好的性能。在此，把“最优最优”的度量映射为模拟退火中的能量函数，具体的度量映射为模拟退火中的能量函数，具体地说，就是把对码书的评价函数地说，就是把对码书的评价函数总失真函数映射成总失真函数映射成退火算法中的能量函数。从而，只需在退火算法中的能量函数。从而，只需在LBG算法的第算法的第（2）步后面加入模拟退火算法就可以构成基于模拟退）步后面加入模拟退火算法就可以构成基于模拟退火算法的火算法的LBG改进算法。改进算法。 3.8：改进算法的几点说明：改进算法的几点说明1）扰动因子的引入和度量扰动因

18、子的引入和度量2）随机扰动策略的制定和扰动量的确定）随机扰动策略的制定和扰动量的确定3）退火过程中稳定性判据）退火过程中稳定性判据4）温度的控制）温度的控制3.9：算法分析：算法分析模拟退火算法用模拟退火算法用Metroplis算法产生组合优化问题解算法产生组合优化问题解的序列，并由的序列，并由Metroplis准则对应的转移概率准则对应的转移概率 ：)()(),)()(exp()()(,1)(ifjftjfififjfjiPi3.10：实验及结论：实验及结论通过引入模拟退火算法对传统的通过引入模拟退火算法对传统的LBG算法进行改进，算法进行改进，在收敛阈值为在收敛阈值为=1.25e-5时，达到如下效果：时，达到如下效果：收敛收敛速度没有因为退火的引入而提高，反而降低了速度没有因为退火的引入而提高，反而降低了3次搜索，次搜索，这是通过退火过程中参数有效控制而达到的；这是通过退火过程中参数有效控制而达到的；有效有效地改善了解的质量，总平均失真减少了地改善了解的质量，总平均失真减少了8.23左右；左右；一定程度上改善了图像质量，一定程度上改善了图像质量，PSNR提高了提高了0.1742dB。 II 回归分