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

第二章 矢量量化技术简介
2．1 数据压缩技术
2．1．1数据压缩技术的发展
数据压缩的研究过程一直有两个发展方向：一个是许多数学家所致力于的建立信源和数据压缩的数学模型，并从中找出衡量数据压缩质量的技术指标及最优压缩性能指标；另一个则是众多的工程技术人员所进行的工作，他们的研究重点为建立一个能实现数据压缩功能的系统，以服务于工程应用，或者对这些数据压缩系统进行分析或模拟，以确定它们的性能指标。
不论是理论研究还是工程实践，1977年以前，数据压缩作为信息论研究中的一项内容，主要是有关信息嫡，数据压缩比和各种编码方法的研究，即按某种方法对源数据流进行编码，使得经过编码的数据流比原数据流占用较少的空间。其中基于符号频率统计的霍夫曼编码具有良好的压缩性能，一直占据重要的地位，不断有基于霍夫曼编码的改进算法提出。
随着计算机技术的飞速发展，数据压缩作为解决海量信息存储和传输的支撑技术受到人们的极大关注。1977年，两位以色列科学家Jacob Ziv和Abraham Lempel发表了论文”A universal algorithm for sequential data compression”，提出了不同于以往的基于字典的压缩算法LZ77。1978年，又推出了改进算法LZ78。他们的研究把无失真压缩的研究推向了一个全新的阶段。
随着信号处理研究的不断的发展，数字图像信号、语音信号等都被大量的引入到有关的领域中。由于图像信息占用较多的存储空间，而图像通信又是目前非话业务的主流，因此数据压缩技术在图像通信中得到了最广泛的应用。
在图像编码中，最早研究的是预测编码，曾作为经典理论而登载于各种专著，并得到广泛的应用。近年来，随着神经网络理论的兴起，有人采用BP网进行非线性预测的尝试，并取得了较好的效果。
1969年，在美国举行首届”图形编码会议”，表明图像编码以独立的学科挤身于学术界。而变换编码在五年左右的时间内成为研究热点。变换编码中的DCT编码由于编码效果较好，运算复杂度适中等优点，已经发展成为目前国际图像编码标准的核心算法。
80年代中后期，众多研究者相继提出了在多个分辨率下表示图像的方案，主要的方法有：子代编码，金字塔编码，小波变换编码等。基于小波变换的方法具有较高的压缩性能，己发展为JPEG 2000的核心算法。在近年来的甚低码率的编码研究中，有一种称之为模型基的编码方法颇引人注意，这种方法压缩比高，但适用于场景比较简单的特定场合。
在1988年左右，有人提出了一种分形图像编码的压缩方案。这种方案思路新颖、压缩潜力大、并具有解码分辨率无关性等优点，是一种很有潜力的编码方法。
尽管用软件压缩方法可以较好地实现数据压缩的目的，但由于压缩算法的运算量较大，需要很高的运算速度和存储空间，这对现有系统来说是很大的负担。为了解决这个问题，人们在继续探索数据压缩技术的同时，着手研制生产高性能的芯片和系统。一般在对时间要求不高的场合采用软件压缩，而对运行速度有特殊要求的情况下，可使用硬件压缩。不过，目前硬件压缩的开销远远大于软件压缩的开销。
2．1．2 数据压缩技术的分类
数据压缩的研究已有几十年的历史，其间，人们提出了各种各样的压缩算法。在分类上，也存在几种不同的方法，有人按编码失真程度或者说按压缩过程的可逆性将数据压缩编码分为两种类型:无失真压缩编码 (Noiseless Coding)与有失真压缩编码 (Noise Coding)；有人按编码基建模的不同将数据压缩分成模型基编码和波形基编码；又有人将它分为第一代压缩编码和第二代压缩编码；还可按压缩技术所使用的方法进行分类，可分为预测编码(Predictive Coding)、变换编码(Transform Coding)和统计编码(Statistical Coding)三大类。目前，较为认可的是第一种分类方法。
1．无失真压缩
无失真压缩也可称之为冗余度压缩(Redundancy Compression)，在数字图象压缩中，有3种基本的数据冗余：编码冗余、像素间冗余以及心理视觉冗余。而无失真压缩就是利用数据的统计冗余进行压缩，除去或尽量除去数据中重复和冗余部分，而不丢失其中的任何信息，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5: 1这类方法广泛用于文本数据、程序和特殊应用场合的图像数据(如医学图像等)的压缩.由于压缩比的限制，仅使用无损压缩方法不可能解决图像和数字视频的存储和传输问题。
常用的无失真压缩技术有：哈夫曼编码，算术编码，游程编码，LZ编码等。
1）行程长度编码（RLE）
行程长度编码（run-length encoding）是压缩一个文件最简单的方法之一。它的做法就是把一系列的重复值（例如图象像素的灰度值）用一个单独的值再加上一个计数值来取代。比如有这样一个字母序列aabbbccccccccdddddd它的行程长度编码就是2a3b8c6d。这种方法实现起来很容易，而且对于具有长重复值的串的压缩编码很有效。例如对于有大面积的连续阴影或者颜色相同的图象，使用这种方法压缩效果很好。很多位图文件格式都用行程长度编码，例如TIFF，PCX，GEM等。
2）LZW编码
这是三个发明人名字的缩写（Lempel，Ziv，Welch），其原理是将每一个字节的值都要与下一个字节的值配成一个字符对，并为每个字符对设定一个代码。当同样的一个字符对再度出现时，就用代号代替这一字符对，然后再以这个代号与下个字符配对。LZW编码原理的一个重要特征是，代码不仅仅能取代一串同值的数据，也能够代替一串不同值的数据。在图像数据中若有某些不同值的数据经常重复出现，也能找到一个代号来取代这些数据串。在此方面，LZW压缩原理是优于RLE的。
3）霍夫曼编码
霍夫曼编码（Huffman encoding）是通过用不固定长度的编码代替原始数据来实现的。霍夫曼编码最初是为了对文本文件进行压缩而建立的，迄今已经有很多变体。它的基本思路是出现频率越高的值，其对应的编码长度越短，反之出现频率越低的值，其对应的编码长度越长。
2．有失真压缩
有失真压缩也可称为嫡压缩(Entropy Compression)，这是一种不可逆压缩。他利用了人类视觉对图像中的某些频率成分不敏感的特性，在压缩过程中会损失掉一部分信息，这样，其原始数据不能由压缩数据完全恢复出来。他是以丢失部分信息为代价而获得较高的压缩率。当然，为了确保恢复后的数据能基本保持原数据的特征，这种失真应该限制在某个规定的范围之内。无失真压缩主要有两大类型：特征抽取和量化方法，特征抽取的典型例子如指纹、汉字的模式识别，一旦抽取出足以有效表征与区分不同模式的特征参数，便可用它取代原始的图像数据，这一类方法一般是用于特定的环境。量化则是更为通用的熵压缩技术，除了直接对无记忆信源的单个样本做所谓的零记忆量化外，还可以对有记忆信源的多个相关样本映射到不同的空间，去除了原始数据中相关性后再做量化处理，由此又引出了预测编码和变换编码。
1）矢量量化编码
矢量量化编码利用相邻图象数据间的高度相关性，将输入图象数据序列分组，每一组m个数据构成一个m维矢量，一起进行编码，即一次量化多个点。根据仙农率失真理论，对于无记忆信源，矢量量化编码总是优于标量量化编码。
2）预测及内插编码
一般在图象中局部区域的象素是高度相关的，因此可以用先前的象素的有关灰度知识来对当前象素的灰度进行预计，这就是预测。而所谓内插就是根据先前的和后来的象素的灰度知识来推断当前象素的灰度情况。如果预测和内插是正确的，则不必对每一个象素的灰度都进行压缩，而是把预测值与实际象素值之间的差值经过熵编码后发送到接收端。在接收端通过预测值加差值信号来重建原象素。
3）变换编码
变换编码就是将图象光强矩阵（时域信号）变换到系数空间（频域信号）上进行处理的方法。在空间上具有强相关的信号，反映在频域上是某些特定的区域内能量常常被集中在一起，或者是系数矩阵的分布具有某些规律。我们可以利用这些规律在频域上减少量化比特数，达到压缩的目的。由于正交变换的变换矩阵是可逆的且逆矩阵与转置矩阵相等，这就使解码运算是有解的且运算方便，因此运算矩阵总是选用正交变换来做。