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

动态聚类算法及模拟退火算法 主讲：王茂芝 副教授 wangmz@cdut.edu.cn 目录 动态聚类算法:C-均值算法或K-均值算法 矢量量化图像压缩编码方法 程序实例 模拟退火算法 回归分析及其它 MATLAB编程简述 课外任务 参考文献 上机实习 1 内容简述 图像压缩编码概述 矢量量化编码 2：图像压缩编码概述 2.1：图像压缩编码的必要性和可能性 2.2：图像压缩编码的一般框图 2.3：图像压缩编码的基本方法 2.4：图像压缩编码的国际标准 2.1：图像压缩编码的必要性和可能性 以指纹库为例，若以512×512×8 bit 的灰度图像来存储一个手指的指纹，一个40万人的指纹库，每人十指，则共需1000GB的存储量。 图像信号可以压缩的根据来自两个方面：一方面是图像信号中存在大量冗余度可供压缩，并且这种冗余度在解码后还可无失真地恢复；另一方面可以利用人的视觉特性，在不被主观视觉觉察的容限内，通过减少表示信号的精度，以一定的客观失真换取数据压缩。 图像信号的冗余度存在于结构和统计两方面。图像信号结构上的冗余度表现为很强的空间（帧内的）和时间（帧间的）相关性。信号统计上的冗余度来源于被编码信号概率密度分布的不均匀。 2.2：图像压缩编码一般框图 2.3：图像压缩编码的基本方法 统计编码、预测编码、变换编码、子带编码、模型编码、分形编码、序列图像的运动估值和运动补偿、小波变换编码、矢量量化编码、数学形态学方法、人工神经网络方法 2.4：图像压缩编码的国际标准 静像压缩编码标准：J PEG系列 动像压缩编码标准：MPEG系列 会议电视和甚低码率压缩标准：H.26X系列 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个组的代表为yj，j=0，1，…，N-1。而压缩，就是图像中的数据矢量，如果属于第j个组，则这个数据矢量就用这个组的代表矢量yj代替，这时的编码就是在相应的位置上记下编号j，而不必记下矢量yj本身。集合{yj，j=0，1，…，N-1}称为码书。其中N称为码书长度，或码书大小。 3.2：矢量量化的数学实质 从数学的观点，矢量量化可以定义为从k维欧几里德空间Rk到其一个有限子集C的映射，即Q：Rk-C，其中C={C1,C2,…,CN | Ci∈Rk }称为码书。Ci称为码字。该映射满足：Q（V|V∈Rk ，V=（v1,v2,…,vk））= Ci，其中Ci=（Ci1, Ci2,…, Cik）为码书C中的码字，并满足 其中， 为矢量V与码字Cj之间的失真测度。 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算法的收敛效果才比较理想。但由于受计