基于矢量量化的图像压缩技术研究

《基于矢量量化的图像压缩技术研究》由会员分享，可在线阅读，更多相关《基于矢量量化的图像压缩技术研究（30页珍藏版）》请在装配图网上搜索。

1、题 目 基于矢量量化的 图像压缩技术研究 姓 名 王俊峰 学 号 20061000365 所在学院 信息科学技术学院 年级专业 2006级软件工程 指导教师 李碧 职称 副教授 完成时间 2010 年 5 月 4 日综合评定成绩： 指导教师评语（可另附A4纸）：评定成绩：指导教师签名： 日期：答辩小组意见（可另附A4纸）：评定成绩：答辩小组长签名： 日期：基于矢量量化的图像压缩技术研究王俊峰 信息学院 2006级软件工程摘要：矢量量化技术是一种具有广阔应用领域和发展前景的技术。矢量量化技术可以实现多维压缩，相比标量量化，具有明显的优越性，其拥有压缩比大、算法简单和失真小的优点。本文主要介绍矢量

2、量化技术在图像压缩领域的应用，其关键技术是码书设计和码字搜索。文章先介绍图像压缩技术的发展现状，并概要介绍各种图像编码技术。接着，通过介绍图像压缩技术的基本原理和标量量化技术，从而引出矢量量化技术，并介绍矢量量化图像编码的基本原理。文章重点介绍了矢量量化技术的关键环节，码书设计和码字搜索，描述了经典的码书设计方法LBG算法和各种改进的码书设计方法。以基于学习和研究的态度，文章最后进行了经典LBG算法和采用覆盖聚类方法的矢量量化仿真实验，并分析了二者的优缺点。关键词：矢量量化；图像压缩；现状；码书设计；码字搜索 Study of Image Compression Based OnVector

3、QuantizationWangJunfeng School of Informatics Guangdong University of Foreign StudiesAbstract: Vector quantization technique is a kind of broad application fields and development prospects of the technology。Compared to scalar quantization, vector quantization techniques can achieve multi-dimensional

4、 compression, it has obvious advantages, which has a compression ratio, and the algorithm is simple and distortion of small advantages. This article focuses on vector quantization image compression technology in the field of application, the key technologies are the codebook design and the codeword

5、searching.The article first describes the development of image compression technology, the status quo and overview of the various image coding techniques. Then, through the presentation of the basic principles of image compression technology and scalar quantization, which leads to vector quantizatio

6、n techniques, and introduced the basic principles of the vector quantization image coding. Article focuses on the main technologies of vector quantization, codebook design and the codeword searching, described the classic LBG algorithm for codebook design methods and a variety of improved codebook d

7、esign methods.Based on the attitude of learning and research，at last, conducted the classic LBG algorithm simulation and the vector quantization simulation by the method of covering clustering, and analyzed the advantages and disadvantages of both.Key words: Vector quantization；Image compression；Sta

8、tus quo；Codebook design；Codeword searching目 录摘 要.Abstract第一章图像压缩技术的现状11.1图像压缩技术的研究背景11.2图像压缩技术的可行性及各种数据冗余介绍11.3图像压缩技术常用的编码方法2第二章基于矢量量化的图像压缩编码原理42.1图像压缩技术的基本原理42.2矢量量化的引入52.3矢量量化技术的理论基础52.4矢量量化的性能评价理论62.5矢量量化的关键技术介绍82.6矢量量化的码书设计方法92.7常见的矢量量化器13第三章经典LBG算法实验与采用覆盖聚类方法的实验143.1经典LBG算法的仿真实验143.2去除空胞腔的改进LBG

9、算法173.3覆盖聚类方法的矢量量化仿真实验17第四章总结22参考文献.23致 谢.24III第一章 图像压缩技术的现状1.1 图像压缩技术的研究背景随着计算机信息技术和数字通信技术的不断高速发展，人类社会也在不断发展进步，人们的工作形式和生活习惯更是发生了翻天覆地的变化，同时对信息的形式和质量的要求也越来越丰富、越来越高。而作为信息技术和通信技术重要部分的多媒体技术和互联网技术，更是深刻地改变着人们的生活。在这两项技术没有发展形成之前，我们不可能像今天这样简单地敲打着键盘、点点鼠标就能够阅知天下事，更不可能实时地参加各种视频会议，总之，没有这些技术的发展，也就没有今天信息时代的高速发展，更别

10、谈如何影响着人们的生活。随着全球信息高速公路的建设，多媒体数据作为多媒体技术和互联网技术的主要承载内容，其存储和传输质量更为人们所关心，人们总希望其存储占用空间小、而传输速度快，并且随着技术的发展，要求也在不断地提高。图像是多媒体数据中信息表达最为丰富的方式，拥有直观形象、易懂、信息量大等特点。图像在计算机技术中是以数字形式表达的，并用像素值来表示图像的颜色信息。像素值用一定的二进制位数表示，位数越多图像信息越丰富。然而数字图像的数据量是非常巨大的。一幅简单的640480的24位真彩色图像的数据量大概是900KB，如果电影每秒是24帧，则一小时该尺寸电影所占空间高达72GB。这么庞大的数据量对

11、计算机的存储、计算能力和网络带宽的耗费都非常高，这对于希望能够高效便捷的获取多媒体信息的人们来说，都将是无法接受的。因而必须解决数字图像在实际应用中所面临的问题，而重要起因就是图像数据量太大，因此最直接有效的办法就是对图像进行压缩编码。所谓的图像压缩，就是指在保证图像质量的前提下，采用一些编码方法，将图像的位图信息转变成另外一种数据量较小的表达方式，即对图像的空间和时间信息进行压缩，去除图像的冗余数据，达到图像压缩的效果。1.2 图像压缩技术的可行性及各种数据冗余介绍图像数据之所以能够被压缩，首先是因为信息和数据是两个不同的概念，数据是信息的载体，只要数据可以较好地表达出信息的意思，在一定程度

12、上，就可以减少数据的大小。图像能被压缩就是得益于图像本身固有的这些特点。数据经常包含着一些与信息无关的部分，即冗余，而数据冗余对于信息来说，是可以去除的。数据之间存在着相关性，根据其相关性的不同，可以采用不同的压缩编码方法。同时人的眼睛是图像信息的接收端，因此可以利用人眼视觉对图像边缘的急剧变化不敏感，而对图像的亮度信息较为敏感，以及对颜色的分辨率较弱等因素来实现对图像进行压缩编码。这些可以被压缩的数据，统统称为冗余。图像数据压缩方法就是研究如何减少或去掉数据中的冗余部分以减少数据的存储空间。图像压缩中的数据冗余主要包括以下几种。空间冗余，它描述的是图像具有自相似的个性，即图像中某一点的颜色和

13、周围邻近的像素点的颜色值相等或相近。基于去除空间冗余的编码方法有行程编码方法和预测编码。编码冗余也叫信息熵冗余，是根据图像的编码冗余思想进行编码的，典型例子有赫夫曼编码和算术编码。视觉冗余产生的原因是因为人的眼睛对某些图像特征不敏感，所以这些特征信息可以不在图像数据中出现。其他几种冗余还有，时间冗余、知识冗余等。1.3 图像压缩技术常用的编码方法图像压缩目的是为了减少图像数据中的冗余信息，从而以更加高效的格式存储和传输数据，当前各种图像压缩方法，都是在围绕着如何减少数据冗余。常用的图像压缩编码有以下几种。行程编码，是根据信源符号连续重复出现的个数和信源符号的出现的位置，从而恢复出原始数据。其实

14、现简单，容易理解。赫夫曼编码的原理是，对于输入信号中出现次数多信元分配以较短的码字，而对出现次数少的信元分配较长的码字，使得对应码组的码长变小，从而达到压缩的效果。赫夫曼编码保证了码的唯一可用性，但由于编码长度可变而且不统一，导致译码时间长，硬件实现难度大。算术编码，其原理是按信源符号的概率序列在当前分析区间划分比例间隔，按此方法细化到各个比例间隔，以最后的当前分析区间内的任意一个数作为编码输出。算术编码实现比较复杂，但其效率比赫夫曼编码好。词典编码，用词语在词典中的位置号来代替词语，解码时，只要根据地址号将词典相应地址的词语读出来即可。词典编码虽然处理过程较为复杂，但是完全可逆，有较高的压缩

15、比，对机器硬件要求也不高，且可以压缩任何类型的数据。其它传统的编码方法还有预测编码和变换域编码等。传统编码的编码方法，一般是将信号经过某种映射变换成为数的序列，然后进行标量量化，再对其进行熵编码，而矢量量化编码则是把输入的数据分成许多互不重叠的组，将每组看作一个k维矢量，再根据按照某种算法生成的码书，查找与当前输入向量最相近的码字，作为该输入向量的量化结果，然后只要传输该码字的在码书中的索引即可，接收方根据码字索引所在码书中查找到对应的码字，重构输入向量。在这里是对矢量编码的简单介绍，在文章接下来的篇幅中，将具体详细介绍矢量量化编码的原理及经典矢量量化算法的实现。第二章 基于矢量量化的图像压缩

16、编码原理在深入探讨矢量量化图像编码原理压缩之前，先介绍下一般图像压缩技术方法的基本原理，从而更好地理解和区别矢量量化编码与其它压缩编码算法。2.1 图像压缩技术的基本原理信息理论是图像编码的主要理论依据之一。设某个无记忆独立信源xk，如果它出现的概率是pk，那么它包含的信息是： （公式1）其中I(xk)称为自信息量，它表明一个概率小的符号出现将带来更大的信息量，也就是说信息量与该符号的概率成反比。由N个符号集构成的离散信源的平均自信息量为： （公式2）这个平均自信息量H(X)称为信息熵，单位是“比特/符号”，用于衡量信息的不确定性，香农的信息论已经证明，信息熵是进行无失真编码的理论基础，而低于

17、此极限的无失真编码方法是不存在的。率失真理论则说明了，对于一个给定的信源分布与失真度量，在特定的码率下能达到的最小失真；或为了满足一定的失真限制，最小描述码率是多少。香农同时也给出了几条编码的基本定理，可变长无失真信源编码定理，有噪信道编码定理和有损信源编码定理。在通常情况下，图像压缩的一般流程可如下表示：采样量化编码图1在采样之前可以对图像进行某种变换，将图像信息集中分布到少数成分上，以便于图像的后续处理，变换可以使图像信息熵减少，因而图像的压缩率就能提高，变换是可逆的，常用的变换方法有离散余弦变换、离散傅里叶变换等。采样就是采集模拟连续图像的样本，是将时间上、幅值上都连续的模拟图像信号转换

18、成时间上离散、但幅值上仍连续的离散图像信号。由于采样后的离散图像还不是数值图像，必须进行量化处理，量化就是将离散图像的值表示为与其幅度成比例的整数。量化一般可以去除心理视觉冗余和视频图像的时间冗余。而编码的主要任务是利用图像信号的统计特性以及人的视觉心理特性对图像信号进行压缩，从而减少数据的空间存储量以方便处理与传输。2.2 矢量量化的引入量化是图像压缩中的重要环节。一般的量化过程是根据一组判决电平，每个判决电平覆盖一定的区间，而所有的判决电平将覆盖整个有效取值区间，量化便是将采样值与判决电平进行比较，若采样值的幅度落在某个判决电平的覆盖区间上，则规定该采样值取这个区间的代表值。量化模型有标量

19、量化和矢量量化。标量量化又叫一维量化，是一个多对一映射过程，其每次仅量化一个样本值。由于标量量化每次都是孤立地考虑一个模拟样本值并对其量化，经常忽略了样本值之间的相关性。为了合理利用样本之间的相关性，可以采用对多个样本进行联合量化的方法，用一个值代替一组相似的值，这样一来不仅可以减少量化误差，同时还提高了压缩比，这种方法便是矢量量化。再由于个人计算机的日益普及，多媒体数据量越来越大，与机器处理速度和网络带宽的矛盾越来越突出，因而希望有一种失真小、压缩比高、处理速度快、易于硬件实现的压缩编码算法。矢量量化技术凭借其压缩比大、解码简单等优点，引起了人们的极大关注，并在图像压缩等领域崭露头角。198

20、0年，LBG算法的提出，是矢量量化技术发展的一个重大的里程碑。其后，人们对矢量量化技术的关注和研究越来越深入，专家们以LBG算法为基础，将神经网络、遗传算法等结合到矢量量化技术的研究中，并取得一定的成效，使矢量量化器更加高效、快速。2.3 矢量量化技术的理论基础矢量量化是标量量化的推广也延伸，其应用领域正在逐步深入和提高。矢量量化在本质上是一个聚类算法，其码书的形成是一个不断迭代的过程。假设某一信源的样本序列共有个样本值，将其中每连续的K个样本值组成矢量，从而构成信源矢量集，其中每个矢量表示为，将K维欧几里德空间RK划分为J个互不相交的子空间，满足，。并设子空间的质心，即代表矢量为，则所有子空

21、间质心构成的向量集，就是矢量量化器的输出空间，称其为码书，是码字，J是码书的长度。对于待量化的输入矢量，如果，则有映射。因此，在矢量量化器实际编码时，只需要在发送端记录下代表矢量的下标索引i即可，并不需要发送整个代表矢量，所以矢量量化编码就是按照一定的失真测度，在码书中搜索出与输入矢量最匹配的码字，并记录下该码字的索引，而在传输时只需要传输该索引。而解码过程则更简单，只需要根据接收到的码字索引在码书中查找到该码字，并把它作为输入矢量的重构矢量。矢量量化器模型如下： 最近邻规则量化编码码书码书 图2图中的最近邻规则用来确定与输入矢量对应的码字，用某种测度准则计算出与该输入矢量最近的码字，来量化和

22、重构该输入矢量，从而可以确定输入矢量对应的码字。从矢量量化的定义可知道，一般情况下，码书长度J远小于输入矢量的样本总数，如果选取适当的码字维数和码书长度，就可以获得很大的压缩比，这说明了矢量量化压缩能力强。如果矢量量化的码书长度越长，即码字越多，则重构矢量的失真就会越小，只要根据给定的失真阈值，选取适当的码字数量，则该矢量量化可以达到很好的编码效果，因此选取适当的码字数量也是矢量量化的关键。不过矢量量化每输入一个矢量，都要和所有码字逐一进行比较，根据最近邻规则，搜索出最接近的码字，工作量比较大，因而寻求合适的码书搜索算法，也是矢量量化技术的关键环节。相比标量量化，矢量量化的优势是显然的，一个k

23、维的最佳矢量量化器的性能总是优于k个最佳标量量化器。2.4 矢量量化的性能评价理论作为一种技术，矢量量化器也需要进行性能评价，以确定该量化器的有效性和可靠性。矢量量化器的性能评价指标具体有压缩比、信噪比、编码速率、实现复杂度和失真测度等客观性评价标准以及主观性评价标准。2.4.1 压缩比、编码速率和比特率压缩比(CR) = 原数据比特率/编码后数据比特率。编码速率定义为每个输入采样所需要的平均比特数。如果码书大小为N，矢量维数为k，矢量量化器每个码字索引所占的比特数为log2N，所以每一维分量所占的比特数，即编码速率为r=(log2N)/k。若系统的输入信号是一个矢量序列，则每个输入矢量所需的

24、比特数为R=kr，并称该比特数为比特率或传输率。假设每个采样有M个电平，那么k维输入矢量空间大小则为MK，而码书只有N个码字，于是可得到最大压缩比为MK/N。按照一样的电平数，当采用标量量化时，每个采样需要log2M比特，而矢量量化时，每个采样仅需log2N/k比特。2.4.2 其它评价测度矢量量化编码过程实质上是输入矢量与码字的匹配过程。在模式匹配问题中，一个关键的问题就是重构矢量与输入矢量之间的差异的度量。假设一个输入矢量X的重构矢量为Y都定义在k维欧几里德空间上，因量化过程会产生失真，那么设该失真为d(X，Y)，且满足以下三个性质：正定性，对称性，三角不等式。以下是几种常见的失真测度方法

25、。(a)平方误差测度。通过输入矢量X与其对应的重构矢量Y=Q(X)的平方欧几里德距离可导出为均方误差，其公式为， （公式3）(b)Minkowshi测度矢量。X和Y的之间的p阶Minkowshi测度为， （公式4）三种常见的特殊测度为：当p=1时，L1(绝对误差)测度；当p=2时，L2(欧几里德)测度；当p为无穷大时，L (切比雪夫)测度。(c)假设有一幅MN的L级灰度图像，其原始图像像素值为，而重构图像像素值为，则有： 均方误差 （公式5） 信噪比 （公式6） 峰值信噪比 （公式 7）2.4.3 矢量量化的实现复杂度矢量量化的复杂度分为时间复杂度和空间复杂度，且复杂度随矢量维数的增加而呈指数

26、形式增加，这成为了高维矢量量化的实现障碍之一。时间复杂度，一般有两种衡量方法，假设码书大小为N，矢量维数为k。第一种，考虑到每个输入矢量所用到的乘法、加法和比较次数，则其复杂度为kN次乘法加(2k-1)N次加法再加(N-1)次比较。第二种，仅用乘法运算次数来度量量化一个输入矢量的复杂度，则复杂度为kN。至于空间复杂度，基本的穷尽搜索矢量量化器的空间复杂度为kN。虽然存储器的容量在不断增长，价格也在下降，但假如数据量很大，则读取数据的时间也将耗费很多，故空间复杂度也不能忽视。2.5 矢量量化的关键技术介绍在上文中提过，矢量量化器的设计有几个关键的环节，矢量量化器设计的成败和好坏基本取决于这几个关

27、键环节的设计是否有效，这些环节也正是矢量量化技术研究的关键点。这些关键技术包括码书设计、码字搜索和码字索引分配，其中码字索引分配是比较新的研究方向，文章将着重论述码书设计和码字搜索。2.5.1 码书设计矢量量化设计的首要问题和核心问题就是设计出性能好的码书。如果码书设计效果差，那么不仅是码书质量差，而且还导致整个设计系统的压缩效率和编码质量受到重大影响。码书设计的过程就是找到一种最佳方案，把M个训练矢量分成N类，并将各类的质心矢量作为码书的码字。然而当训练矢量数较大和分类较多的时候，搜索全部码书将会耗费巨大处理时间，这直接影响到矢量量化器的实用性，因而码书设计的目的就是寻求有效的算法的找到或接

28、近全局最优的码书，使失真最小，以提高码书的实用性，并降低计算复杂度。LBG算法是基于最佳矢量量化器的最佳划分和最佳码书的生成这两个条件的，该算法物理概念清晰、算法理论严谨、实现容易。但LBG算法存在着不足，首先是对初始码书的依赖性强，初始码书选取的好坏直接影响码书训练的收敛速度和码书最终的性能。其二由于LBG是基于聚类方法的，需要不断迭代，而每次迭代，需要从码书中查找到最近邻码字，这将耗费大量的存储空间和繁琐的计算时间。还有，就是码书的自适应力不强，无法自适应地跟踪图像信源的特性。而且最终码书只能收敛到基于训练矢量的局部最优，码书的生成速度也比较慢。LBG算法是无记忆的穷尽搜索矢量量化方法，虽

29、然可以获得质量较优的码书，但是码书形成的复杂度比较高，使得使用该码书的矢量量化编码的复杂度也高。针对以上这些问题，专家学者们提出了许多改进算法。这些改进算法主要是基于初始码书的选取，即改进码书的初始化技术，还有就是引进快速码字搜索算法和采用其他技术提高码书性能或加快设计速度的技术。这些算法都旨在提高矢量量化码书的质量和降低计算复杂度。2.5.2 码字搜索矢量量化设计的另一个关键技术，就是码字搜索技术。码字搜索，是指在已经给定码书的情况下，对于当前输入矢量，采用某种度量方法，在码书中搜索出与输入矢量之间失真最小的码字。在一般常规的全搜索编码矢量量化器中，假如码书长度为N，码字维数为k，那么当要为

30、一个输入矢量进行编码时，就必须进行N次距离计算和N-1次比较。上文中已经论述了，在采用平方误差测度时，矢量量化的时间和空间复杂度，如果码书较长，码字的维数也大的话，计算的复杂度将会变得很大。因此码字搜索算法研究的目的就是寻求快速有效的算法以减少计算复杂度，让搜索算法便于硬件的实现。根据穷尽搜索算法的缺点，专家提出了许多改进的快速搜索算法，算法有：基于不等式判据的快速码字搜索算法；基于变换域的快速码字搜索算法；基于金字塔结构的快速码字搜索算法等。矢量量化的快速码字搜索算法，是解决编码时计算复杂度高的方法之一，这些算法都在力求待量化矢量和码字之间距离与它们的一些低维特征量的不等式关系，以排除大量不

31、可能的码字，不过这得以增加较少的存储量为代价，但它们在很大程度上降低了计算复杂度，提高了搜索效率。2.6 矢量量化的码书设计方法一般情况下，基于穷尽搜索方法的矢量量化码书设计，能够得到较好的量化质量，因此很多改进的矢量量化器的设计都是以基于穷尽搜索方法矢量量化码书设计算法为基础，而该算法就是经典的LBG算法。研究码书的设计方法，目的就是为了寻求一个最优码书设计方法，以提高码书的质量，降低计算复杂度。2.6.1 矢量量化码书设计的最优条件矢量量化器的设计目的就是为了寻求一个K维矢量量化器Q(X)，使得待编码矢量序列的总体失真D最小，总体失真一般可以采用某种失真测度的统计平均值来描述，比如平方误差

32、测度的统计平均值。实际上，矢量量化器的工作原理，就是先找到一个码书和一个输入矢量空间的划分方法，码书是用于解码，矢量空间的划分则是为了编码，而最优矢量量化器就是指拥有最佳码书和最优划分的量化器，那么最优矢量量化器该满足怎样的条件呢。假设有一个矢量量化器，其输入矢量空间RK的N个划分为Ri=R1,R2,RN，其码书尺寸为N，码书为Y=Y1,Y2,YN，则可以按照给定码书的最优划分和给定划分的最优码书条件，来刻画最优矢量量化器需要满足的条件。最近邻条件：给定码书的最优划分条件，即给定了解码器的最优编码器条件。假如给定了码书，那么输入矢量空间的最优划分应该满足最近邻条件，即每个输入矢量应该划分到离它

33、最近的码字，或者是以离它最近的码字来重构该输入矢量。最近邻条件为：，它表明了在给定码书的条件下，输入矢量的最优空间划分是一个最小失真的映射，通常把该最优划分称为Voronoi划分，对应的子集Ri称为Voronoi胞腔。质心条件：给定划分的最优码书条件，即给定了编码器的最优解码器条件。假如给定了输入矢量空间的最优划分，那么在确定每个胞腔最优的量化点，即确定码书时，应该满足质心条件，由所有胞腔的质心构成最优码书。质心条件为：当给定了空间的划分后，最优码字Yi是对应胞腔Ri的质心，Yi=cent(Ri) 。零边界概率条件：是为了防止边界点的出现，所谓的边界点就是指一个输入矢量没有固定的最近邻码字，可

34、能同时与几个码字的距离相等。2.6.2 LBG算法及其初始码书生成算法LBG算法是基于最优矢量量化器最近邻条件和质心条件的实现码书设计的一种迭代算法。它通常是从按照某种方法生成的初始码书开始的，然后根据最近邻条件把每个输入训练矢量划分到离它最近的胞腔中，再根据质心条件，重新计算每个胞腔的质心，得出新一轮的码书，按照这种形式不断迭代，直到满足给定的限制条件后停止迭代，并得到最终的码书。而每次迭代总可以将平均失真降低一些，使码书的性能逐渐提高。假设给定矢量训练集X=X1,X2,XM，LBG算法的一般实现步骤如下:(a)给定初始参数和迭代停止条件。给定最大迭代次数T的值，当前迭代次数t=0，平均失真

35、D趋于无穷大，并给定相对误差值TermTh。(b)生成初始码书Y0。根据某种生成算法，得到初始码书，初始码书的选取很关键，直接影响到收敛速度和最终码书的质量。(c)按照某种距离测度方法，把当前码书的码字作为胞腔的质心，将当前的矢量训练集划分到离它们最近邻的胞腔中，得到新的胞腔划分。(d)计算当前胞腔划分的平均失真，公式为：，若前后两次平均失真的相对误差满足，或达到限制的迭代次数T，则停止算法，而当前码书就是所求的最终码书，否则转到下一个步骤，继续执行。(e)由当前的划分，根据质心条件，重新计算每个胞腔的质心，并将所有质心组成当前的码书。每个胞腔的质心为：，从而获得新的码书Y，并另迭代次数t加1

36、，重复步骤 (c)。LBG算法在实现时存在以下几个不足：在每次迭代时，训练矢量在码书中搜索与其最近邻的码字的过程中，占用大量的存储空间并耗费大量的繁琐计算；对初始码书依赖性太强，初始码书的好坏制约着码书训练的收敛速度和最终码书的性能；码书的自适应力不强。好的初始码书能较好地提高迭代生成的最终码书的性能，若初始码书的性能足够好，那么就能在很大程度上减少后面码书在迭代过程中所耗费的时间和空间占用。鉴于初始码书的选取对矢量量化器的性能有重大影响，专家学者们对此也提出了许多初始码书生成算法，以改进LBG算法的整体性能。包括随机编码、删除算法、成对最近邻算法、分裂法、分离平均初始码书算法等。随机编码是初

37、始码书生成算法中最简单、复杂度最小的算法，它根据输入矢量的分布随机选取N个训练矢量作为初始码书的码字。该算法实现的计算量小，同时也能防止空胞腔的出现，不过因为随机选取，可能选择一些不典型的矢量作为码书，以致有些胞腔分得过细，而有些却分得过粗糙，影响码书的性能。删除算法是有选择地从整个训练矢量集中删除训练矢量，直至剩下N个训练矢量，从而作为初始码字。成对最近邻算法其实也是一种删除算法，不过它相对比较复杂，性能却比较优越。它是采用不断合并胞腔的方法，直至合并到所需的N个胞腔。分裂法是一种基于乘积码思想的码书初始化生成算法。它的基本思想是让码书尺寸逐渐增加而维数不变，由小的码书生成较大的码书，直至符

38、合所需的条件。分离平均初始码书算法则是一种致力于脱离码书选取随机性的算法，基于矢量特征量排序的分离平均初始码书算法，则是该思想的一个升级算法。2.6.3 其它改进的矢量量化码书设计方法由于LBG算法在码书设计中存在许多不足，特别是迭代过程中耗费大量资源，于是人们便通过引入其它一些技术，融入到矢量量化的码书设计中，以提高矢量量化器的性能。比较常见的改进的码书设计算法有神经网络方法、基于小波变换的矢量量化、非线性插补矢量量化和基于随机优化技术的码书设计方法等。基于神经网络的码书设计算法，利用神经网络强大的学习能力，在学习过程中不断更新获胜神经元或者更新获胜神经元领域内的码字。该类型的算法有竞争学习

39、矢量量化码书设计算法、自组织特征映射算法等。基于小波变换的矢量量化，利用小波变换的特性，在编码中可以对高频部分大多数系数分配较小的比特，以达到压缩的目的，而在矢量量化时，则根据人眼系统对高频分量反应不敏感，而对低频反应敏感的特点，因此可减低低频分量的失真，即对低频区码率分配高些，以达到提高矢量量化器性能。非线性插补矢量量化，它采用将高维矢量映为一个减少维数的特征矢量，再通过对低维特征矢量镜像量化的方法，从而降低高维矢量量化的复杂度。基于随机优化技术的码书设计，解决了传统的搜索算法难以在众多的分类中找到全局最优的分类，采用随机优化技术，在不断向最终解迭代过程中，解的行进轨迹可加以扰动，从而使获得

40、全局最优解成为可能。基于该思想的码书设计算法有模拟退火算法、遗传算法和进化策略算法等。2.7 常见的矢量量化器常见的矢量量化器有穷尽搜索矢量量化器、约束矢量量化器、有限状态矢量量化器、预测矢量量化器和自适应矢量量化器等。穷尽搜索矢量量化器可以获得很好的量化结果，但其码书的生成复杂度高且编码过程复杂，例如LBG算法。因此研发低复杂度的矢量量化器，便成为了约束性矢量量化器等的研究目标。第三章 经典LBG算法实验与采用覆盖聚类方法的实验为了加深对矢量量化技术的理解，本章节将对经典的LBG算法进行仿真实验，通过实验了解矢量量化技术的核心思想，并用各种测度评价方法得出的实验数据，去真切体验LBG算法的优

41、缺点。同时，作者在阅读了各种矢量量化技术典籍和进行了LBG算法的仿真实验后，发现经典LBG算法实用化的最大阻碍在于码书生成时间太长，为解决这一情况和进一步了解矢量量化编码技术，作者尝试了一种体现LBG算法聚类思想的覆盖聚类矢量量化方法，并进行仿真实验，还用该实验得出的测度评价数据与经典LBG仿真实验的测度评价数据进行对比，比较两者之间的实际效果。作者本着学习和研究的态度去尝试用不同的方法，去研究矢量量化编码技术，以加深作者对矢量量化技术的认知。3.1 经典LBG算法的仿真实验为了对经典LBG算法有一个深入、透彻的理解，对其进行仿真实验。LBG算法是基于穷尽搜索的算法，以下是该算法仿真实验的内容

42、描述。3.1.1 仿真实验环境硬件平台：CPU，Intel core2，主频2GHz；内存，1.5G。软件平台：操作系统，Windows XP Professional SP3；编程工具：MATLAB 7.0。3.1.2 算法描述(a)初始化。清除MATLAB工作空间的内存数据，设置计时点time1，与算法接下来的计时点time2、time3，共同用于计算码书生成时间和编码时间；设置算法最大迭代次数nMaxIter=20，当前迭代次数nIter=0，给定可以让算法停止的失真相对误差阈值TermTh；设置码书长度为L，图像分割块大小为mn，m=4，n=4，每一个小方块都看成一个16维的矢量，从而

43、确定码字维数k为16。(b)读取训练图像，并对图像进行分割处理，生成矢量训练集。为了便以处理，假如图像是彩色的，则将其转为灰度值图像。其中图像的分块大小为44，并将每个图像分块转为k维矢量，所有k维矢量则构成矢量训练矩阵V，其中nBlockNumber=nRownCol为矢量训练矩阵V的行数。(c)根据矢量训练集，开始码书设计。采用随机选举法，先从nBlockNumber个训练矢量中，选取L个构成初始码书，并将初始码书保存到矩阵CodeBook，再根据最近邻条件，采用平方误差测度计算距离，将矢量训练集里的矢量划分到最近的类胞腔中，其中矩阵CluTemp，用于记录矢量训练集的当前胞腔划分，其中前

44、k列是本类所属各训练矢量的和，第k+1列用于记录类成员个数，从k+2列开始记录每类中各个所属训练矢量成员在矢量训练集V中的行序号。在每次迭代之后，根据质心条件，重新计算每个胞腔的质心，更新码书，然后计算每个类胞腔中的训练矢量与该类质心(即码字)的平均失真Di，再求出所有类之间的平均失真BetwCluD，失真测度同样采用平方失真测度。继续迭代，每次迭代时令nIter加1，直到满足迭代停止条件，即超过最大迭代次数或最近两次的失真相对误差小于TermTh，并得到最终码书。设置时间点time2，计算出码书的生成时间。(d)读取待编码的图像并进行编码。为处理方便，待量化编码的图像与矢量训练图像选取同一张

45、图像。同样，对待量化图像先进行分割变形处理，变成由k维矢量组成的矩阵，然后采用全搜索方法，每个矢量在码书中搜索出其最近邻的码字，并记录下该码字的索引号，将所有矢量的码字索引号保存在IDX矩阵中。(e)根据索引号，重构图像。根据IDX矩阵里的索引号，从码书中找出对应码字，重构矢量，并将重构矢量集进行变形转为原图像的排序模式。设置时间点time3，计算出图像编码所用的时间，并计算出各种测度评价数据。3.1.3 实验数据图3 矢量量化性能测试图片在矢量量化实验中，所采用的图片都是256256的8bits标准灰度图像，如图3，各个图像的细节复杂度都不一样，并通过多次实验，统计出以下数据。由于覆盖聚类算

46、法的码书长度是动态产生的，而经典LBG算法的码书长度是预先设置的，而码书长度的不一，直接影响到量化后的性能，为了让经典LBG算法与接下来的覆盖聚类算法，在进行性能对比时，有较好的可比性，故在实际实验中，各测试图片在经典LBG算法的码书长度将根据其在覆盖聚类算法中动态生成的码书长度的实际值进行设置，以方便两个算法的对比。表1 经典LBG算法实验数据测试图片(bmp格式)CMANPEPPERSLENNAKGIRL码书长度108989485码书生成时间(秒)14.484012.32809.609011.8590编解码时间(秒)0.68800.61000.59400.5470编码速率(bit/维)0.

47、42220.41340.40970.4006压缩比(倍)8/0.42=18.9519.3719.5519.97比特率(bit/矢量)6.75496.61476.55466.4094均方误差175.5198100.6031121.748482.1893信噪比(db)68.708665.652263.579361.4992峰值信噪比(db)25.687528.104727.276228.9826经典LBG算法实验效果图示例如下。 图3 待量化的原始图像 图4经典LBG算法量化后的图像小结：由以上数据和压缩后的图像质量可以看出，LBG矢量量化的压缩比高，从数据中可以看出，码书越短压缩比越高，图像质量

48、也不错，不过其最大的问题是码书生成时间长，主要是在码书生成中，迭代过程中耗费了大量的计算时间，还有在码书搜索时，由于采用了全搜索的方法，因而也影响了实时效果，专家学者们一直致力于研究的目标，就是为了寻求解决这些问题的方法。3.2 去除空胞腔的改进LBG算法在经典LBG算法程序运行过程序中，发现在重新计算每个胞腔类的质心时，偶尔会出现除数为0的错误，作者由此猜测，在划分胞腔的过程中，可能出现了没有包含任何训练矢量的空胞腔。因此对算法做了如下改进：即在重新计算每个胞腔类的质心的时候，如果每发现了一个空胞腔，则将该空胞腔删除，并将码书的长度L减1，从而达到去除空胞腔的效果。在实验中，由于空包腔的出现

49、概率比较小，故去除空包腔的改进LBG算法的实验数据同经典LBG仿真实验的数据差不多，因此不再赘述其实验数据。3.3 覆盖聚类方法的矢量量化仿真实验作者本着学习和研究的态度，在实现了经典LBG算法的仿真实验之后，尝试着以LBG算法中的聚类思想，用其它的方式去实现矢量量化的码书生成。于是在参考了许多矢量量化典籍和示例之后，尝试用覆盖聚类的方法来实现矢量量化的编码。该算法的核心思想就是：通过不断找出未聚类矢量中两个距离最短的矢量，以该距离的n倍和其中一个点为圆心，形成一个圆覆盖，并将该半径范围内的矢量都划分到该圆中，并且通过大圆吞并小圆的方法，防止圆的数目过多，而一个圆就是一个分类，圆的重心就是码字

50、，所有圆的重心就构成了码书。该算法的码书长度是根据图像细节复杂度动态变化的，图像细节越复杂，码书长度也就越长。3.3.1 仿真实验环境，与经典LBG算法仿真实验环境相同。3.3.2 算法描述(a)初始化：清除MATLAB工作空间的内存数据，设置计时点time1，与算法接下来的计时点time2、time3共同用于计算码书生成和编解码时间。图像分割块大小为mn，m=4，n=4，从而确定码字维数k为16。但没有限定最大迭代次数。(b)读取训练图像，并对图像进行分割处理，生成矢量训练集V。具体内容同经典LBG算法中的描述，故不赘述。(c)根据矢量训练集V，开始码书设计。根据矢量训练集V，求出所有训练矢

51、量的重心，并将其保存在meanVector矩阵中，初始化flagVector(i)=0，flagVector用于标记该矢量是否已经聚类，当flagVector里面的值全为1时，表示所有训练矢量都已经聚类完成，因而可以退出码书设计环节的循环。算法中Cluster用来标记分类的类别，而vectorCluster用于记录每个矢量当前属于哪个类。(d)根据矩阵flagVector，找出未聚类的矢量，并将其在训练矩阵V中的序号保存到矩阵nClassify中。从矩阵nClassify中，根据meanVector里的重心值计算绝对差，求出与nClassify记录的第一个矢量距离最近的矢量，以该矢量的重心为圆

52、心，以最短距离的s倍为圆心，形成一个圆覆盖。同样根据meanVector里的重心值计算绝对差，将所有在该覆盖范围内的未聚类矢量划归进该类，并将所有已划入该类的矢量在flagVector中的值标记为1，但假如该矢量已被聚类且在该类范围内，如果该矢量与其原来所属类的质心距离小于与当前重心的距离，那么则将该矢量划归到当前的类中，否则不变。接着，重新计算该类的重心，且将所有属于该类的训练矢量的总和记录在矩阵sumVector中。在每个新类形成的过程中，都会新建一个class(Cluster)结构，用于记录类的各种信息，包括属于该类的矢量的个数等。(e)由矩阵sumVector和class(Cluste

53、r)的分量numVector记录的属于当前圆类的矢量个数，求出该圆划分的代表矢量，即码字codeBook (Cluster，k)，由该码字重新计算出该圆的圆心，即码字的像素点均值。重复步骤(d)，直至所有矢量均已被圆所覆盖，即聚类。(f) 以下的编解码步骤同经典LBG算法仿真实验。3.3.3 实验数据在实验中，采用同经典LBG仿真实验的相同的图像，实验数据如下。表2测试图片(bmp格式)CMANPEPPERSLENNAKGIRL码书长度108989485码书生成时间(秒)2.2340 2.14102.11001.6880编解码时间(秒)0.7350 0.65600.65600.6090编码速率

54、(bit/维)0.42130.41310.40970.4006压缩比(倍)8/0.42=18.9819.3619.5219.97比特率(bit/矢量)6.74156.61476.55466.4094均方误差488.2708271.9690294.5057157.0853信噪比(db)64.158961.201659.588458.5672峰值信噪比(db)21.278123.815923.473826.2034覆盖矢量量化方法实验示例效果图如下。 图5 待量化的原始图像 图6 覆盖聚类算法量化后的图像3.3.4 覆盖聚类实验与经典LBG实验效果的分析对比(a) 码书生成时间分析由表3可以看出覆

55、盖聚类算法的码书生成速度比经典LBG算法的快了4至7倍，其主要原因是覆盖聚类算法消除了经典LBG算法中初始码书的选取对量化器收敛速度的影响，从而减少了迭代的复杂度，同时，该算法中的矢量距离测度是用矢量的重心均值来计算的，并且用绝对差来度量，而经典LBG是用平方差来度量，相比之下覆盖聚类算法减少了计算的复杂度，所以其码书生成速度快。(b) 均方误差(MSE)分析由表4可以看出覆盖聚类算法的均方误差比经典LBG算法的高出一倍多，失真比较大，所以该算法量化的图像比较粗糙、锯齿明显。该情况主要是因为覆盖聚类算法在聚类过程中，采用大圆逐渐吞并小圆的方式，在一般情况下，圆越大圆的重心在代表该圆覆盖的矢量时

56、与该矢量的误差也就越大，这就导致图像细节的部分被掩盖掉。还有，覆盖聚类算法的码书生成，是通过计算训练矢量的均值来进行的，虽然减少了计算复杂度，但因为用其均值来代表训练矢量，从而也加大了最终码书的误差。(c) 峰值信噪比(PSNR)分析由表5可以看出，覆盖聚类算法的峰值信噪比比经典LBG算法的低了5%，这是该算法均方误差大的一个体现，PSNR反应图像质量，一般情况下，PSNR数值越高，图像画面质量就越好。(d) 其它度量性能分析覆盖聚类算法与经典LBG算法的编解码部分的实现方法是一样的，编解码时间的出入主要在于码书长度的不同，而编码速率、压缩比也和码书长度有关，故这两个算法的这几个度量都得从控制

57、码书长度上着手，而在这方面作者暂未能思索出新的思路。 从实验数据中可以看出，覆盖聚类算法比经典LBG算法优越的地方主要在于码书的生成速度快，还有就是覆盖聚类算法会根据图像的细节复杂度的高低而动态地决定码书的长度，即算法可以自适应图像的细节复杂度，而经典LBG算法则必须固定码书长度，这对于当图像复杂度较低时是不必要的，浪费了计算量。不过覆盖聚类算法的失真较大、信噪比的效果也比经典LBG算法略逊一筹。从这些对比，一方面可以看出矢量量化技术本身的优越性，而另一方面也可看出矢量量化技术的可研究性，其研究意义重大。第四章 总结矢量量化技术的研究涉及多个领域，由于作者的知识面和领域知识深度有限，故论文中难

58、免存在许许多多的不足，在以后的学习中，还需要努力去开拓视野和深入研究。基于矢量量化的图像压缩技术虽然已被研究了多年，但至今仍未有一套成熟实用的矢量量化编码系统，但矢量量化技术作为一种拥有很大优越性的技术，仍然值得人们去研究专注，其主要突破口在于码书生成和码字搜索，近年来，人们将其它技术融入到矢量量化中来，已经取得相当的成绩，希望在不久的将来，可以取得更加好的成绩，以将矢量量化技术实用化。参考文献：1 姚敏等.数字图像处理M.机械工业出版社，2006.2 王新年，张涛.数字图像压缩技术实用教程M.机械工业出版社，2009.3 陈善学，李方伟.矢量量化与图像处理M.科学出版社，2009.4 龙脉工

59、作室，刘会灯，朱飞.MATLAB编程基础与典型应用M.人民邮电出版社，2008.5 求是科技.MATLAB7.0从入门到精通M.人民邮电出版社，2006.6 郑巍.基于矢量量化的图像压缩技术研究J.合肥工业大学硕士学位论文，20037 刘丹蕾，陈善学，韩静宇.矢量量化综述J.黑龙江科技信息，2008.8 马文龙.基于矢量量化的图像编码系统的设计J.西安理工大学学位论文，2005.9 凌 玲，凌卫新.聚类分析在彩色图像量化中的应用J.系统仿真学报，2001,13.10 马文龙，余宁梅等.图像块动态划分矢量量化J.计算机设计与图形学学报，2005,17（2）.11 张旭东，卢果栋等.图像编码基础和

60、小波压缩技术M.清华大学出版社，2004.12 美托马斯，林奇(著).吴家安，杜淑玲(译).数据压缩技术及其应用M.人民邮电出版社，1985.13 孙胜和，陆哲明.矢量量化技术及应用M.科学出版社，2002.14 朱永红.覆盖聚类算法的应用研究J.计算机技术与发展，2007,17(1).15 赵姝，张燕平，张铃等.覆盖聚类算法J. 安徽大学学报，2005.02.16 余战秋.基于覆盖的聚类算法研究J. 安徽大学学位论文，2005.17 美谭 斯坦巴赫(著)，范明等(译).数据挖掘导论图灵计算机科学丛书M. 人民邮电出版社，2006.致 谢本文能够顺利完成，在此我要特别感谢我的指导老师，李碧老师

61、。本文是我在李碧老师的悉心指导下完成的，他给了我很多的指导和修改意见，无论在文章的内容上还是格式上，他都给我提出了许多宝贵的想法，本文因此才得以完善，在此向老师致谢！24广东外语外贸大学毕业论文（设计）学术诚信声明本人郑重声明：所呈交的毕业论文（设计），是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文（设计）不包含任何其它个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者签名：日期： 年 月 日广东外语外贸大学毕业论文（设计）版权使用授权书本毕业论文（设计）作者同意学校保留并向国家有关部门或机构送交论文（设计）的复印件和电子版，允许论文（设计）被查阅和借阅。本人授权广东外语外贸大学可以将本毕业论文（设计）的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本毕业论文（设计）。保 密，在 年解密后适用本授权书。本论文（设计）属于不保密。（请在以上方框内打“”）毕业论文（设计）作者签名：