基于矢量量化编码的数据压缩算法的研究分析

摘 要

伴随着通讯与信息科技的迅猛发展，数据压缩技术己经成为信息时代人们工作与科研的有力工具。数据压缩技术，作为信息论研究中的一个重要课题，一直受到人们的广泛关注。矢量量化技术作为数据压缩领域里的一个重要分支，以它压缩比高、编码速度快、算法简单清晰等良好的特性，在图像压缩等领域都已成为有力的手段和方法。
本文以矢量量化在静止图像方面的应用为研究目标，介绍了矢量量化的定义，基本理论、相关概念及发展现状，重点讨论研究了矢量量化的三大关键技术–码书生成和码字搜索和码字索引分配。详细阐述了码书设计算法中的LBG算法和最大下降MD算法；快速码字搜索中的基于不等式快速码字搜所和码字索引分配中的BAS算法和禁止搜索码字索引算法等。
最后总结分析了现有典型的算法和改进算法并提出了自己的基于矢量量化算法的实现方法，编程实现了一个完整的数据压缩软件，取得了较好的效果。

关键词： 数据压缩，矢量量化，LBG
ABSTRACT
第一章 绪论
1．1 课题的研究背景及意义
1．1．1 研究背景
随着计算机和大规模集成电路的飞速发展，数字信号分析和处理技术得到很大发展，并已经广泛应用于通信、雷达和自动化等领域。数字信号的突出优点是便于传输、存储、交换、加密和处理等。一个模拟信号f(t)，只要它的频带有限并允许一定的失真，往往可以经过采样变成时间离散但幅值连续的采样信号f(n)。对于数字系统来说，f(n)还需经过量化变成时间和幅值均离散的数字信号x(n)。
通信系统有两大类：一类是传输模拟信号f(t)的模拟通信系统；另一类是传输数字信号x(n)的数字通信系统。在任何数据传输系统中，人们总希望只传输所需要的信息并以最小失真或者零失真来接收这些信息。人们常用有效性（传输效率）和可靠性（抗干扰能力）来描述传输系统的性能。与模拟通信系统相比，数字通信系统具有抗干扰能力强，保密性好，可靠性高，便于传输、存储、交换和处理等优点。在数字通信中，码速率高不仅影响传输效率，而且增加了存储和处理的负担。
上个世纪八、九十年代，计算机技术和网络技术取得了飞速的发展，人类社会进入到了前所未有的信息化时代。随着信息时代的来临人们对通信业务的要求不断增长，在日常生活中，大量的信息数据需要传输、存储和处理。科学实验表明，人类从外界获取的知识之中，有80%以上都是通过视觉感知获取的。眼睛获取的是图像信息，和语音、文字等信息相比，图像包含的信息量更大、更直观、更确切，因而具有更高的使用效率和更广泛的适应性，一幅图胜过千言万语， 图像信息是人类认识世界、自身的重要源泉。所以在信息数据中，绝大部分数据都是图像数据，而图像数据的传输常常要占用很大的带宽，需要很大的存储空间，因而怎样对图像数据进行行之有效地传输是一个极具挑战性的课题。
数字图像中包含的数据量十分巨大，例如，800 x 600分辩率的真彩色图像，其数据量为800 x 600 x 3=1440000字节，约1.4MB；而一分钟CD音质的音频文件一般需要l OMB左右的存储空间。在视频传输中PAL制式(25帧/秒)下，画面分辨率为640 x 480下，真彩色(24位)的图像序列，播放1秒钟的视频画面数据量为：640 x 480 x 3 x 25 = 23,040,000字节，相当于存贮一千多万个汉字所占用的空间。如此庞大的数据量，给图像的传输、存贮、传输线的传输率(带宽)以及计算机的处理速度等增加巨大的压力。由此可见，对降低传输成本，增加数据传输的可靠性，不断满足人们对信息传输的需求，图像压缩都具有十分重要的作用。为了解决好这个问题，我们就必须对图像进行编码压缩，在保证一定图像质量的前提下，有效地减少传输时所需的数据量和占用的频带。
1．1．2 研究意义
图像压缩就是在没有明显失真的前提下，将图像的位图信息转变成另外一种能将数据量缩减的表达形式，即去处冗余信息。首先，尽管图像中数据量很大，但其行、列以及帧间都具有极强的相关性或冗余信息。即一个象素的灰度值，总是和它周围的象素的灰度值有着某种关系，可以由它们推算表示出来，应用某种方法提取或减少它们之间的这种相关性，即可实现图像压缩。其次，大部分图像视频信号的最终接收者都是人眼，而人类的视觉系统是一种高度复杂的系统，它能从极为杂乱的图像中抽象出有意义的信息，并以非常精练的形式反映给大脑。人眼对图像中的不同部分的敏感程度是不同的，如果去除图像中对人眼不敏感或意义不大的部分，对图像的主观质量是不会有很大影响的，也实现了图像压缩。正由于图像压缩的必要性和可能性，图像压缩编码研究成为一个越来越活跃的领域。在诸如基于Internet的多媒体通信、可视电话、数字电视，多媒体计算机等领域得到了广泛的应用。
1．2课题研究现状
矢量量化的基本理论早在二十世纪六七十年代已有人关注，而在二十世纪八十年代开始逐步完善起来。矢量量化是分组量化的一种，受到广泛注意和使用的分组量化方法是由黄和舒尔泰斯于1963年首先提出来的，他们指出分组量化的实现方法:首先与正交矩阵相乘将相关的采样变换为不相关的采样，然后再在每组固定的总比特数限制下，将不同的量化比特数目分配给每个不相关的采样值。1979年，格尔肖在他的论文中详细阐述了分组量化的一般性理论，它将贝内特早年关于均方误差准则的量化模型推广到分组量化中。
将矢量量化技术推向研究高潮和推广应用应归功于1980年由Linde. Buzo和Gray提出来的一种有效的LBG矢量量化码书设计方法，该文献己经成为矢量量化的经典文献，是矢量量化技术发展的基石。
在20多年历程中，学者们在以下五个方面对矢量量化技术展开研究：
1. 针对基本矢量量化器复杂度大和比特率固定的缺点，开发其它类型的矢量量化器；
2. 针对基本矢量量化器的LBG码书设计算法容易陷入局部极小、初始码书影响优化结果和计算量大的缺点，学者们引入了神经网络、优化理论、模糊集合等技术，提出了各种各样的码书设计算法；
3.在矢量量化编码场合中，针对基本矢量量化器的穷尽搜索编码算法的计算量大和比特率固定的缺点，提出各种各样的快速码字搜索算法和变比特率码字搜索算法；
4. 矢量量化技术的应用；
5. 考虑到信道噪声将会在矢量量化解码端引入额外失真，学者们开始研究码字索引分配算法以减少由于信道噪声引起的失真。
1．3 课题研究内容
1. 研究内容
1）对数据压缩的基本理论、技术标准、评价方法进行研究和分析
2）对基于矢量量化的数据压缩算法及其衍生算法进行逻辑上的分析和比较
3）选择矢量量化算法中的一种算法进行实现，完成一个完整的数据压缩软件
2. 本文结构安排
第一章为绪论，主要介绍了课题的研究背景，简要地阐述课题的研究意义最后，总结了本论文的研究内容。
第二章中，首先对数据压缩作了简要的综述；然后介绍了矢量量化数据压缩算法的起源，发展和相关的数学模型及理论基础；最后写了矢量量化的关键技术和矢量量化技术指标。
第三章是对矢量量化算法的研究，首先分别论述了矢量量化的三大关键技术的算法，介绍了码书设计中的LBG算法和最大下降算法；码字搜索算法中的基于不等式的快速码字搜索算法和等均值等方差最近邻搜索算法；码字索引分配算法中的BSA算法和禁止搜索码字索引算法。
第四章是矢量量化算法的实现。详细介绍了矢量量化算法的实现过程，并对实验结果进行了分析和评价。