基于矢量量化编码的数据压缩算法的研
究与实现 二
转自：.4矢量量化的关键技术及技术指标 2.4.1矢量量化的关键技术
矢量量化的三大关键技术是【8】：码书设计、码字搜索和码字索引分配。其中前两项最关键。
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)【11】等。在本文的讨论中，我们主要是灰度图像作为测试数据来源。我们的矢量量化技术的应用也主要是针对灰度图像的，因此以L级灰度图像为例，我们给出个指标的定义：设一副L级灰度图像有WXH个像亲，Xij为原始图像像素值，Yij为恢复图像像素值，那么结过如下公式所示：
(2.15) (2.16) (2.17)
第三章矢量量化的算法研究 3.1矢量量化码书设计算法的研究 3.1.1经典的LBG算法
如前所述，在矢量量化器的构造过程中，码本设计是最初的也是最重要的部分，根据各种码本设计算法的思想和迭代过程，我们可以将码本设计问题归结为Lloyd算法的两条基本准则【12】：
1.最佳划分准则(Optimal Partition)
对于给定的码本利用最近邻条件对训练矢量集进行重新划分。将每个训练矢量映射到与它之间失真最小的码字，最后形成一组以现有码本中的码字为中心的最佳划分。设训练矢量集为：