第三章第二讲矢量量化

1、VECTOR QUANTIZA TION矢量量化(Vector Quantization)一.矢量量化初步1. 基本原理2. 设计码本 (LBG)3. 量化二矢量量化进一步1. 分裂矢量量化 (Splitted VQ)2. 多极矢量量化 (Cascaded VQ)3. 树形矢量量化器4. 其它各种类型矢量量化器三. 几个矢量量化的工程实现问题21. 分级矢量量化中的多路径搜索问题2. 用模拟退火 (Simulated Annealing)算法训练最佳码本矢量量化的应用1VECTOR QUANTIZA TION一. 矢量量化初步1. 基本原理结论：在信息论中已证明，矢量量化优于标量量化。矢量量化

2、是先将 K个（K _2）个采样值形成K维空间Rk中的一个矢量，然后将这个矢量一次进 行量化。它可以大大降低数码率。基础是信息论的分支：率失真（畸变）理论对于一定的量化速率 R（以每个采样信号平均所用的量化比特数来衡量，bit/采样），量化失真D（以量化信号与原信号之间的误差均方值和原信号均方值之比来衡量）是一定的。矢量量化总是优于标量量化的。这是因为矢量量化有效地应用了矢量中各分量间的四种相 互关联的性质：线性依赖性，非线性依赖性，概率密度函数的形状以及矢量维数。定义：1）源：若将M *个信号采样组成的信源序列中每K个为一组分为 M 个随机矢量，构成信源空间X =X1，X2,，Xm ?（ X在

3、K维欧氏空间RK中），其中第j个矢量可记为X j =洛，X2, xj， j =1,2, ,M。K'n2）子空间：把R无遗漏地划分成N = 2个互不相交的子空间 R1, R2 / , Rn，满足：NUs =rk丿i士Ri Rj =0, i = j3）码本：在每个子空间Ri中找一个代表矢量 Yi，令恢复矢量集为：丫 丫，丫2,，Yn二丫也叫输出空间、码本或码书（Code Book），Yi称为码矢（Code Vector）或码字（Code Word），丫内矢量的数目 n ,则叫做码本长度。4）码本搜索：当矢量量化器输入任意矢量Xj RK时，它首先判断Xj属于那个子空间，然后输出该子空间R的代

4、表矢量丫丫 丫 RK,i =1,2,N几矢量量化过程就是用Yj代表Xj ,即Yi =Q X j ,1乞i乞N , 1岂j乞M。式中Q为量化函数。5）完整系统：VQ编译码的全过程完成一个从K维欧氏空间RK到RK空间中有限子集的映射：Q : R K _： X > Y 山飞,，丫n ?。发端完成映射C:XI二讣2, N匚收端完成映射D:I > Y，矢量量化Q则是C和D的结合。图1中给出了这种映射关系。- 编码X > I- 解码I t Y图1矢量量化示意图3VECTOR QUANTIZA TION6）矢量量化的比特率：log 2 NR 二K:log 2 N ：每个矢量所需要的编码比特

5、数:K：每个矢量所包含的信号样点数:K=1时,VQ退化成SQ波形量化采样频率为10kHz、振幅量化为16bit的语音信号的传输速率是： 16x10000=160,000bit/s（bps）。波形特征参数量化对阶数为10、每秒100个特征矢量（如频谱包络参数），如振幅量化也为 16bit 的话，其传输速率是：16x100x10=16,000bit/s。波形特征参数矢量量化：设L = 1024 （40种语音单位，每个对应25种变形），即为了指定码本中任意码矢需要10bit，则对每秒100个特征矢量的传输需率就为 1,000bit/s。7）矢量量化的特点：压缩能力强。一定产生失真，但失真易控制：X的

6、分类越细，失真越小。由于X j和Yj都是K计算量大：每输入一个X j ,都要和N个Yj逐一比较，搜索出畸变最小的。维矢量，故搜索的矢量运算，工作量大。-VQ是定长码。2. 设计码本1）目的：在VQ中，码本的生成是一个关键。若设计K维N级码本，则要根据M L失真最小的准5VECTOR QUANTIZA TION#VECTOR QUANTIZA TION则，分别决定如何对 RK进行划分，以得到合适的N个胞腔（Cell） Ci , 1乞i乞N ；以及求出Ci ,1乞i乞N的代表矢量Yi , 1乞i乞N。最佳量化就要满足使其平均失真d q最小，即D Q = mind X ,Y F2）原则：最佳多维量化

7、器必须满足K分割条件：对R的分割应满足(Voronoi 分割)#VECTOR QUANTIZA TION#VECTOR QUANTIZA TIONR X RK : d(X ,YJ 岂 d (X ,Yj) : i = j?#VECTOR QUANTIZA TION质心（Centroid）条件：当子空间分割 X -巳固定时，Voronoi胞腔的质心就是量化器的码字, 即Yj= E 取 X R 1矢量徒是胞腔Ci的质心。对于最佳胞腔的分割、最佳质心的计算与畸变的度量准则有关。对于均方误差准则及加权均方误差准则，胞腔Ci的质心Y :1YPx2XCi表示胞腔Ci中元素的个数，即胞腔 Ci中有Ci个X。矢

8、量量化由码本丫和划分Ri的条件唯一确定。当码本确定后，分割就可以通过最近邻域准则（NNR-Nearest Neighbor Rule）唯一确定。最佳量化器q的设计也就是最佳码本 Y的设计。通常采用迭代类 聚的方法。3）训练码本的LBG算法Linde, Buzo和Gray将标量最优量化的 M L算法推广到了多维空间LBG算法。图2、图3分别给出已知训练序列和已知信源分布特性的算法流程图。a）初始化条件：给出- 码本长度N-初始码本 Yn , &（° ）,丫（°】,，丫（° 1 计算停止门限；，01初始平均失真D ' '训练序列 Ts Xn；

9、n =1,2,M ? M J7VECTOR QUANTIZA TION#VECTOR QUANTIZA TION（开甘算停止门限巧覺. f弊闔霜鬻翻JYi. 了疋少糾r , -1彳卫伫否是（蟻 束）图2已知训练序列的算法流程图b）用码本Yn n为已知质心，根据最佳划分原则把训练序列T胞腔，即= 'Xn； n = 1,2, ,M 划分为 N 个nSjl=叹 d（X ,Yj ）兰 d（X ,Yj9VECTOR QUANTIZA TION#VECTOR QUANTIZA TION其中 i = j,YYj Yn ,X Ts , j =1,2, N 。c）计算平均失真与相对失真r A1 K其中

10、d Xr，Yd Xr,k，ym,kK k J_-平均失真：巾=汰囲严,丫是K维输入矢量xr的量化畸变。若 6 n乞；，则停止计算，当前码本即是设计好的码本 Yn，否则进行d）生成新码字-计算这时划分的各胞腔的质心，可由下式计算F Si :集合Si中元素的个数-由这n个新质心匕（2）,丫（2厂，丫（心门构成新的码本ynD- 设置 n=n+1-返回2）再进行计算，直到D C*）兰E，得到所要求的码本 Yn =Y（n N为止。4）初始码本的生成LBG算法：总失真单调下降的算法 要求：避免陷入局部最小点 方法：a）随机选取法b）分裂法分裂原则扰乱系数距离最大原则c）综合法（合并法）5）失真测度1）基本

11、定义：失真测度是反映用码字 丫代替信源矢量x所付出的代价。这种代价的统计平均值描述了矢量量化器的工作特性，即D = E d X , Q X 12）常用失真测度:平方失真测度:2 2d X,丫二 X _YXi _Yii加权平方失真测度：d(X,Y )=(X -Y J W (X -Y )W :正定加权矩阵。绝对误差失真测度：d X,Y一丫八 Xi -Yi与被量化矢量信号意义相关的失真测度:例如反映语音谱包络的预测 (LP)矢量，定义频谱失真为,fl11 rd10 log 10 log d:打 °P)曰(co)式中P(.)是原始LP能量谱，F?()是量化后的LP能量谱似然比失真测度 板仓-

12、斋田失真测度3. 矢量量化的量化过程全搜索码本中有N个码字，每个码字为 K维矢量,完成一次搜索的计算代价:(欧氏距离)加法：N(2K-1)次乘法:NK次比较:N-1次树形搜索的矢量量化系统图4-5二叉鞫捜索方法11VECTOR QUANTIZA TION#VECTOR QUANTIZA TION二叉树或多叉树#VECTOR QUANTIZA TION优点：降低运算量缺点：增加存储量衰4订三更鞫擡哄与全銀*方玉的性糜比较 11U. 比较唾算r1'1151 i * -L；.|r i最桂栓度胡L Hi ,全体:二3 a2(/-1)(-14)F_-”仝，UN :水喪中J为科本尺寸。二. 矢量量

13、化进一步分裂矢量量化（Splitted VQ） !=树搜索矢量量化器分裂矢量量化：首先将一个K维矢量分裂成P（ P>1 ）个子矢量，然后对各个子矢量分别独立进行矢量化。对于一个实用的 vq系统，例如用 20个比特对10个LSF进行量化。如果用全搜索方案，码本容量 将达到220 *10 （LSF矢量为10维），无论是从码本的存储容量还是搜索的运算量，在现有的硬件条件下难 以实时实现。如果采用分裂矢量量化算法，将10维的LSF矢量分裂为两个5维的矢量，分别用10比特进行VQ，这样，码本容量降为2* 210 *5。由此可见分裂矢量量化可以大大降低了码本的存储量和最佳矢量搜索的计算量。2. 多极

14、矢量量化 （Cascaded VQ）1）多级矢量量化器的构造多级矢量量化器可以较大幅度的降低矢量量化器的计算复杂度和存贮量。多级矢量量化器由码本大小分别为N , N 2，,Nm ,的m个小码本构成。图4所示的是m级矢量量化器的编码器原理图。13VECTOR QUANTIZA TION图4多级矢量量化器的编码器m级矢量量化器的量化原理：第一级矢量量化器是量化原始输入矢量X，在码本1中找到失真最小的码字Yi，并将其下标i编码送到信道中。第二级量化器的输入矢量是：原始输入矢量X与第一级输出矢量Y之差的误差矢量e X -Y。 e,在码本2中找到失真最小的码字E j1，并将其下标jl编码送到信道中。第三

15、级 量化器 的输入矢 量是：第二级的 输入矢 量ei与第二级的输 出矢量E j1之差的误 差矢量 e2 = e, - E j,。同样e2在码本3中找到失真最小的码字E j2，并将其下标j2编码送到信道中。依此类推，第m级量化器的输入矢量e(m/)与第(m-1)级的输出矢量E j(m之差的误差矢量 e(m)=e(m<)- Ej(m)。e(mJ)在码本m中找到失真最小的码字Ej(1)，并将其下标j(m-1)的编码信号送到信道中。这样，信道中传输的将是i,j1,j2,jm等下标的编码信号。m这m个小码本，等价于一个 码本尺寸为N二 Ni的全搜索矢量量化器的码本，并称此全搜索矢i =1量量化器为

16、与此m级矢量量化器相当的量化器。2) 多级矢量量化器码本的设计多级矢量量化器各级码本设计仍可采用LBG算法，只是训练序列有所不同。下面给出一个m级矢量量化器的码本设计算法。(a)第一级码本设计设第一级码本大小为 N1，训练序列TS的长度为M (即有M个训练矢量)。采用 LBG算法进行计算，得到第一级码本Yj(i =1,2,，N1)。(b)第二及多级码本设计第二级码本仍按 LBG算法进行设计。不过它的训练序列是第一级矢量量化器的误差信号e1长度仍为M。同样用LBG算法进行类聚、递归，得到第二级码本的N2个码字Eji(j =1,2,., N 2)。余者类推。例如设计一个 LSF参数的三级矢量量化器

17、：在实际算法中，采用16万帧以上的训练序列 TS进行训练，三级矢量量化，分别是7比特，7比特和6比特。同样用20比特对LSF矢量进行编码，码本容量降为(27 +27 +26)*10,相对于分裂矢量量化，存储量降低了 60%，相应的搜索计算量也大大减少。而合成语音质量与相同比特的分裂矢量量化基本相当。多级矢量量化系统无论在减少搜索计算量方面，还是减少码本储存量方面都有可观的改进。3. 模糊矢量量化减少码本的量化误差模糊聚类(Fuzzy Clustering)模糊k均值聚类，隶属度函数4. 其它各种类型矢量量化器全搜索矢量量化器sparsity)o 节约计算量(稀疏码本 o 节约存储量固定预测矢量

18、量化器乘积码矢量量化器o 增益/o 均值/自适应矢量量化器自适应预测矢量量化器三. 几个矢量量化的工程实现问题1. 分级矢量量化中的多路径搜索问题在分级矢量量化中，每一级量化过程都是在所定义的最小误差意义下最优的。但多级量化作为一个整体并 不一定是最优的。然而要用全路径搜索的方法找出全局最优，运算量巨大。现阶段的硬件无法满足实时运 算的要求。所以工程上采用搜索路径数为 M的部分路径搜索分级矢量量化。例如：1) 在第一级搜索中找到误差测度最小的M个码字，并保留对应的 M个误差矢量。2) 在第二级搜索中分别以这 M个误差矢量为输入矢量，分别进行码本搜索。找到并保留M个(输入 误差矢量、码字和输出误

19、差矢量)搜索路径，这些路径所对应的误差测度也是最小的。3) 整个分级搜索完成时，就保留了M条完整的从第一级到最后一级的搜索路径。从中挑选一条最终误差测度最小的路径上的码字序列作为分级矢量量化的输出。以4级，每级码本大小为128,搜索路径数为8为例。共要进行128+8*128*3=3200次误差测度计算， 而传 统搜索需要128*4=512次误差测度计算。以部分增加计算量为代价从工程上逼近全局最优量化。2. 用模拟退火(Simulated Annealing)算法训练最佳码本2VQ码本的形成也是一个优化问题。就是通过一种迭代预算使对全部训练矢量而言的平均量化畸变(目标 函数)达到最小值。但这个目

20、标函数在由 M个码字矢量构成的状态空间中是一个非凸函数，它有很多极小值，其中一个是全局最小值，其它都是局部最小值。由于LBG算法中每次迭代目标函数总是下降的，是一种最陡下降算法(Steepest descend Algorithm)。LBG迭代预算的结果是目标函数落入哪一个极小值取决于 码本中码字矢量初值的设置。工程上很难保证LBG算法给出的结果达到目标函数的全局最小点。解决这一问题的一种方法，可以形象的表示为，将系统状态通过加扰，从局部最小点拔出来。这种算法称为“随 机松弛算法”，简记为SR算法(Stochastic Relaxation)。SR算法中最重要的是一种“模拟退火算法”，简记为SA算法(Simulated Annealing)。SA算法能够从理论上严格证明，在满足一定条件下， 保证目标函数收敛到全局最小点的概率为1。以解码器扰动 SA算法为例：1) 设系统的状态(码本内容)用S表示，系统的目标函数(平均畸变)用E表示，E是S的函数，记为E(S)。 设迭代的节拍为 m, m=1,2,3,。设第m次节拍时系统状态为 Sm。设二(Sm)是对Sm机型某种随机扰动后的状态。这种扰动的