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

图2.1 数据压缩技术的分类
2．1．3 数据压缩算法的度量标准
对于一种数据压缩算法的性能，有一定的衡量标准，为了后面几章描述的方便，也为不至于产生歧义，对这些标准作以简单的介绍。
1．算法性能评价
1）压缩比（CR：Compression Ratio）：
压缩比定义为原始数据量与压缩后量的比值，即
压缩比 = 原始数据量/压缩后量
2）计算复杂度：
计算复杂度可以用算法处理一定量数据所需的基本运算次数来度量。如处理一帧有确定的分辨率和颜色数的图像所需的加法次数和乘法次数。
压缩算法分为编码部分和解码部分，如果两者的计算复杂度大至相当，则算法称为对称的，反之称为非对称的。
2．图像质量评价
1）均方误差（MSE）
对于模拟信号，设原始数据为x(t)，编码、解码后的数据为y(t)，二者之差为e(t)，即e(t) = x(t) - y(t)。则e(t)的方差如公式2.1所示：
（2.1）
通常误差均值μe=0， 又称为均方误差（Mean Squared Error）。
2）信噪比（SNR）：
对于离散信号，设原始数据为 ，编码、解码后的数据为 ，它们的差值为 的均方误差为 ，信噪比（Signal to Noise Ratio）定义为原始数据方差 与重建数据误差方差 的比值如公式2.2所示：
（2.2）
3）峰值信噪比（PSNR）：
对于离散图像数据，在信噪比的计算中常用图像数据中的最大值xmax来代替均方根值бx，得到峰值信噪比如公式2.3所示
（2.3）
2．2 矢量量化的定义及理论基础
2．2．1 矢量量化的起源及发展
矢量量化基本理论早在20世纪六七十年代己有人关注，八十年代开始逐步发展完善起来。1956年，Steinhaus第一次系统阐述了最佳矢量量化问题；1978年，Buzo第一个提出实际的矢量量化器。1980年，Linde, Buzo和Gray将Loyd-Max算法推广，提出了一种有效的矢量量化码书设计算法一一LBG算法，将矢量量化技术的研究和推广应用推向了高潮，成为矢量量化技术发展的里程碑。
在20多年的发展历程中，人们全面研究了矢量量化的理论和应用，开发了多种类型的矢量量化器。虽然矢量量化技术研究已经日趋成熟，但仍存在很多有待解决的问题，如矢量量化码书标准与编码对象密切相关，不同应用场合下码书结构、尺寸以及矢量维数都不相同。矢量量化的压缩标准也一直没有提出。目前的研究大多停留在理论方面，各种优化的矢量量化器的硬件实现还有待于进一步的研究。因此，有关矢量量化技术的研究还有很多工作要做。
矢量量化在20多年的发展历程中，主要是从以下几方面得到了发展：
(1) 矢量量化器的研究，对基本矢量量化器复杂度大和比特率固定的缺点，开发其它类型的矢量量化器；
(2) 矢量量化码书设计算法研究：针对基本矢量量化器的LBG码书设计算法 容易陷入局部极小、初始码书影响优化结果和计算量大的缺点，学者们引入神经 网络、优化理论、模糊集合等技术，提出了各种各样的码书设计算法；
(3) 矢量量化码字搜索算法研究：在矢量量化编码场合中，针对基木矢量量 化器的穷尽搜索编码算法的计算量大和比特率固定的缺点提出各种各样的快速 码字搜索算法和变化特率码字搜索算法；
(4) 矢量量化码字索引分配算法研究：考虑到信道噪声将会在矢量量化解码端引入额外失真，学者们开始研究码字索引分配算法以减少信道引起的失真。
2．2．2 矢量量化的定义及理论基础
1. 定义
一个维数为k，尺寸为N的矢量量化器可以定义为从k维欧儿里得空间 到一个包含N个输出(重构)点的有限集合C的映射Q，表示为公式（2.4）：
（2.4）
其中， 。
C是重构码字矢量集合，称为码书，其尺寸(大小)为N。码书的N个元素Yi称为码字或者码矢量，它们均为k维欧几里得空间 中的矢量。输入矢量空间 通过尺寸为N的矢量量化器Q后，被分割成N个互不重叠的区域又称为胞腔，这个过程称为输入矢量空间的划分。对 胞腔 定义为公式（2.5）：
（2.5）
2. 理论基础
矢量量化的理论基础是香农的率失真理论。1948年，香农定义了信道容量，并证明只要编码速率不超过信道容量，符号就能以任意小的差错概率在该信道中传输。1959年，香农定义了率失真函数R(D)，并证明只要R(D)不超过信道容量就能保证接收端的失真不超过给定阈值D。在数学上，R (D)定义为在给定失真D的条件下，系统所能够达到的最小码速率。对于幅值离散的信源， R(D)定义如下公式（2.6）所示:
（2.6）
其中， ，平均失真满足公式2.7：
（2.7）
式中d(X,Y)是失真测度，它表示输出采样值Y再现原始采样值X所引入的失真， P(Y/X)表示在己发送X的情况下接收到Y的概率。R(D)的单位为比特/采样。同样，也可以定义失真率函数D(R)，它是率失真函数的逆函数，其含义为在定速率不超过R的条件下，系统所能够达到的最小失真，它是在维数k趋向无穷大时Dk(R)的极限，即 。
香农理论表明在速率受限的条件下或在平均失真受限的情况下，通信系统所能达到的最优性能。率失真函数通常又被作为理论最优值，如果一个系统的性能低于理论最优值，则一定可用更好的编码技术获得系统性能的改善；如果一个系统的性能接近理论最优值，则此系统已接近最优，无法再做太多改善；一个系统的性能不可能优于理论最优值。由香农理沦可知，理论上，矢量量化技术只要不断的增加矢量的维数k，编码的性能就可任意接近率失真函数，使系统性能达到最优。因此，香农的率失真理论指出了矢量量化技术的优越性，是矢量量化技术的理论基础。
2．3 矢量量化的相关概念
2．3．1 数学模型
设有一个信源采样数据序列，我们把每K个数据分成一组，每组数据都记录成矢量形式 (i =1,2 ,…,N )，称x为输入矢量。设 为一个K维输入矢量的集合。
再把T划分成M( N)个子空间 ，即各子空间满足公式(2.8)：
(2.8)
通常，我们把这M个子空间称为Voronoi胞腔(Cells)，或者简称胞腔，有时也把它称为一个分类或分区。在每个胞腔R，中我们再找到一个代表元Yi,我们称所有这些代表元组成的集合C=( )为码书(Codebook)。这些代表元也称为码字(Codeword)集合1= (1,2,…, M}称为码字的索引集合。一个矢量量化器包括编码器和解码器两部分。编码器主要包括一个码书和一个量化器。
量化器Q(X)定义如式(2.9)：
Q: T C；
当X 时，Q (X)= Yi (i=1 ,2,…,M). (2.9)
其中，Q(X)是一个多对一的函数，因此它是不可逆的。解码器主要包括一个与编码器相同的码书和一个码字检索器 (i)。
码字检索器 (i)定义如式（2.10）：
: I C；
(i) = Yi，i=1,2,…,M. (2.10)
矢量量化的模型如下图2.2所示：
编码时：对任意一个输入的K维矢量X，计算Q(X)的值Yi，通过传输信道发送码字Yi的索引i到解码器端。
解码时：对输入的一个索引号i，查找码书中对应的码字Yi，输出Yi作为整个系统对矢量X的压缩恢复值。
图2.2矢量量化器结构示意图
2．3．2 量化器Q(x)相关问题
我们可以看出矢量量化可以等价于一个聚类问题。但如何聚类却有很多种方法。在上文我们说当 时，Q(X)= Yi；(i=1 ,2,…,M)。这是用胞腔来定义Q(X)。反过来，也可以用Q(X)和码字Yi来定义胞腔Ri，如式（2.11）所示:
（2.11）
当然，最初必须有一个明确的Q{X〕的定义。
如何判断 昵？通常定义一个失真测度函数 (实数域)，d (X,Yi)表示用Yi来代表X时产生的误差。我们用它来判断一个矢量X到底属于那个胞腔:
当d (X,Y
因此，在这里量化器的主要工作就是利用失真测度函数d进行最近邻码字收索。有时候我们也把d(X,Yi)称作X与Yi之NJ的距离。
2．3．3 失真测度函数
我们要求失真测度函数满足以下两个条件：
(1)正定性： 当且仅当 X=Y时d( X,Y)=0；
(2)对称性： ；
有时候我们也加上第三个条件：
(3)三角不等式： ；
失真测度函数通常选择线性赋范空间中的范数，根据范数的定义，它们都满足上面三个条件。在本文中若无特殊声明，我们的d(X,Y)就取最常用的2范数的平方，即K维欧几里德空间中的距离的平方： ，我们把这个测度又称为平方误差测度。它虽然不满足三角不等式但是 却是满足全部这三个条件的。
事实上，判断一个矢量X属于哪个胞腔可以有很多种标准，在本文中，我们仅仅依据最近邻(NN: Nearest Neighbor)准则为判断标准。利用矢量失真函数d，我们再定义一个胞腔失真函数：
D: Voronoi Cells R (实数域)；
X为处理矢量。
因为我们通常处理的数据量都是有限的，所以有限个实数之和也是有限的，从而D(Ri)是有限的。那么我们系统的总失真就如式（2.12）所示：
（2.12）
有时为方便起见，我们也把Er记为Er(C)，C为码书，把D(Ri)记为D(Ri, Yi), Yi为Ri的代表元。显而易见的，Er是越小越好。
2．4 矢量量化的关键技术及技术指标
2．4．1 矢量量化的关键技术
矢量量化的三大关键技术是：码书设计、码字搜索和码字索引分配。其中前两项最关键。
1. 码书设计
矢量量化的首要问题是设计出性能好的码书。如果没有码书，那么编码将成为无米之炊。假设采用平方误差测度作为失真测度，训练矢量数为M，目的是生成含N (N M)个码字的码书，则码书设计过程就是寻求把M个训练矢量分成N类的一种最佳方案(如:使得均方误差最小)，而把各类的质心矢量作为码书的码字。可以证明在这种条件下各种可能的码书个数为Num C，Num C满足公式2.13：
（2.13） 其中C为组合数。通过测试所有码书的性能可以得到全局最优码书。
然而，在N和M比较大的情况下，搜索全部码书是根本不可能的。为了克服这个困难，文献中各种码书设计方法都采取搜索部分码书的方法得到局部最优或接近全局最优的码书。所以研究码书设计算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码书以提高码书的性能，并且尽可能减少计算复杂度。
2. 码字搜索
矢量量化码字搜索算法是指在码书已经存在的情况下，对于给定的输入矢量，在码书中搜索与输入矢量之间失真最小的码字。给定大小为N的码书C，如果矢量x与码字A之间的失真测度为d(x,y)，则码字搜索算法的目的就是找到码字Y，使得失真测度满足公式2.14:
（2.14）
如果采用平方误差测度，对于k维矢量，每次失真计算需要k次乘法，2k一1次加法，从而为了对矢量x进行穷尽搜索编码需要Nk次乘法，N(2k -1)次加法和N-1次比较。可以看出，计算复杂度由码书尺寸和矢量维数决定。对于大尺寸码书和高维矢量，计算复杂程度将很大。研究码字搜索算法的主要目的就是寻求快速有效的算法以减少计算复杂程度，并且尽量使得算法易于用硬件实现。
3. 码字索引分配
在图示的矢量量化编码和解码系统中，如果信道有噪声，则信道左端的索引i经过信道传输可能输出索引J而不是索引i，从而将在解码端引入额外失真。为了减少这种失真，可以对码字的索引进行重新分配。如果书大小为N，则码字索引分配方案一共有N!种。码字索引分配算法就是在N!种码字索引分配方案中寻求一种最佳的码字索引分配使由信道噪声引起的失真最小。然而，当N较大时，测试N!种码字索引分配方案是不可能的。为了克服这个困难，各种码字索引分配方法都采用局部搜索算法，往往只能得到局部最优解。所以研究码字索引分配算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码字索引分配方案以减少由信道噪声引起的失真，并尽可能减少计算复杂度和搜索时间。
2．4．2 矢量量化技术指标
1. 矢量量化压缩率
从矢量量化器的工作原理我们看出，码书确定之后，传输或者存储的压缩数据只是一系列码字的索引，这些索引本身并不包含原始数据的任何信息。因此矢量量化的压缩率很大，其比特率 bit/采样，也就是说压缩倍数为 B为原始采样数据所用比特(bit)数。
举例来说，当E=8, M= 256, K=64时，压缩率r=0.015625 bits/采样。压缩倍数为64。这样的压缩倍数显然很可观了从压 缩 率 与压缩倍数的计算公式我们看出，M一般是2的幂次。再例如，码书大小为150,码字索引要用8bits码书大小为256，码字索引也要用8bits.两种码书大小得到的数据压缩率相同，但后者压缩性能显然更好，所以一般我们用256而非150个码字，大小为2a的码书又称为q比特码书。
2. 信号恢复性能指标
通常信号质量有均方误差(MSE)，信噪比(SNR)，峰值信噪比(PSNR) 等。在本文的讨论中，我们主要是灰度图像作为测试数据来源。我们的矢量量化技术的应用也主要是针对灰度图像的，因此以L级灰度图像为例，我们给出个指标的定义：设一副L级灰度图像有WXH个像亲，Xij为原始图像像素值，Yij为恢复图像像素值，那么
结过如下公式所示：
（2.15）
（2.16）
（2.17）
第三章 矢量量化的算法研究
3．1 矢量量化码书设计算法的研究
3．1．1 经典的LBG算法
如前所述，在矢量量化器的构造过程中，码本设计是最初的也是最重要的部分，根据各种码本设计算法的思想和迭代过程，我们可以将码本设计问题归结为Lloyd算法的两条基本准则：
1. 最佳划分准则(Optimal Partition)
对于给定的码本 利用最近邻条件对训练矢量集进行重新划分。将每个训练矢量映射到与它之间失真最小的码字，最后形成一组以现有码本中的码字为中心的最佳划分。设训练矢量集为：
则训练矢量集的最佳分类 满足公式（3.1）：
式中，i,j= 1,2,…,N （3.1）
如果存在D(x,yi )= D (x,yj ), 则将训练矢量归入码字yi的集合。
通常把这种最佳划分称为Voronoi划分，对应的子集凡称为Voronoi胞腔。设训练矢量x为k维的 ，如果用平方误差测度用来表征训练矢量x和码字yi之间的失真，即：
（3.2）