语音信号处理课件第七章

第7章矢量量化,7.1概述,1,7.2矢量量化基本原理,7.3最佳矢量量化器,3,7.4矢量量化器的设计算法及MATLAB实现,4,7.5降低复杂度的矢量量化系统,5,2,7.1概述,量化分为两大类：标量量化和矢量量化。标量量化：把抽样后的信号值逐个进行量化。矢量量化：将k(k2)个抽样值形成K维空间Rk中的一个矢量，然后将此矢量进行量化，。矢量量化优于标量量化，为不可逆压缩方法，具备比特率低、解码简单、失真较小的优点。矢量量化广泛应用于图像、语音压缩编码、移动通信、语音识别、文献检索及数据库检索等领域。,矢量量化的理论基础是仙农的率-失真理论。率-失真理论指出，利用矢量量化，编码性能有可能任意接近率-失真函数，其方法是增加维数k；该理论指出了矢量量化的优越性。率-失真理论在实际应用中的重要指导意义：常作为一个理论下界与实际编码速率相比较，分析系统还有多大的改进余地。但是，率-失真理论是一个存在性定理而非构造性定理，因为它没有指出如何构造矢量量化器。,矢量量化技术的发展历程,最佳矢量量化问题,Steinhaus,1956年,如何划分量化区间及求量化值问题,Loyd和Max,1957年,提出实际矢量量化器,Buzo,1978年,LBG算法,Linde,Buzo和Gray,1980年,7.2矢量量化基本原理7.2.1矢量量化的定义（1）定义：矢量量化是先把信号序列的每K个样点分成一组，形成K维欧氏空间中的一个矢量，然后对此矢量进行量化。,xnX1X2X3X4Xn/4,图示输入信号序列xn，每4个样点构成一个矢量（取K=4），共得到n/4个4维矢量：X1，X2，X3，Xn/4,矢量量化就是先集体量化X1,然后量化X2，依次向下量化。下面以K=2为例说明其量化过程。,（2）几个概念量化矢量(或称重构矢量)：利用最小失真原则，分别计算用量化矢量Yi（i=1，2，7）替代X所带来的失真，其中最小失真所对应的那个矢量Yj，就是模拟矢量X的量化矢量。码书：量化矢量构成的集合称为码书(Codebook)。码字：码书中的每个矢量Yj（i=1，2，N）称为码字(Codeword)。,7.2.2失真测度失真测度的选择直接影响矢量量化系统的性能。失真测度是以什么方法来反映用码字Yi代替信源矢量X时所付出的代价。这种代价的统计平均值(平均失真)描述了矢量量化器的工作特性，即式中E表示求期望。,常用的失真测度有如下几种：平方失真测度这是最常用的失真测度，易于处理和计算，且在主观评价上有意义，即小的失真值对应好的主观评价质量。,绝对误差失真测度主要优点：计算简单，硬件容易实现。加权平方失真测度式中T矩阵转置符号；W正定加权矩阵。,要使所选用的失真测度有实际意义，必须要求它具有以下几个特点：1.必须在主观评价上有意义，即小的失真对应好的主观质量评价；2.必须在数学上易于处理，能导致实际的系统设计；3.必须可计算并保证平均失真D=ED(X,Q(X)存在；4.采用的失真测度，应使系统容易用硬件实现。,7.2.3矢量量化器通常用最小失真的方法-最近邻准则NNR（NearestNeighborRule)）来设计矢量量化器，也就是要满足下式：式中IN=1,2,i,N；N码书的大小；符号表示充分必要条件。,矢量量化器的工作过程是：在编码端，输入矢量X与码本中的每一个或部分码字进行比较，分别计算出它们的失真。搜索到失真最小的码字Yj的序号(或此码字在码本中的地址)，并将j的编码信号通过信道传送到译码端；在译码端，先把信道传送来的编码信号译成序号j，再根据序号（或码字Yj所在地址），从码本中查出相应的码字Yj。Yj是输入矢量X的重构矢量。,矢量量化系统通常可以分为两个映射的乘积式中:是编码器，它是将输入矢量映射为信道符号集IN=i1,i2,iN中的一个元素ij；是译码器，它是将信道符号集ij映射为码书中的一个码字Yi。即,(X)=ijX，ijIN(ij)=YiijINYiYN,矢量量化定义:把一个K维模拟矢量的有序集（称为信源矢量集合）中的某个矢量X映射为N个量化矢量构成的有限集（码书或码本）中的某个矢量（码字或码矢）Y，这种映射称为矢量量化。,一个矢量量化器可以表示成以下三个部分：码书：空间划分：S=映射：q：其中，Si是Rk的一个子集且满足矢量量化器Q()的性能，以其输入矢量X和输出矢量Y=q(X)的失真平均值而定，失真平均值为：,D(Q,F)=Ed(X,Y)=Ed(X,q(X),补充：矢量量化与标量量化的比较矢量量化是把一个K维模拟矢量映射为一个K维量化矢量。标量量化实际是维数K=1的矢量量化。一般情况下，矢量量化均指K2的多维量化。与标量量化的两个主要步骤相对应，矢量量化首先要将抽样值构成的矢量即K维空间的无穷多点划分成有限个胞腔，然后从每一个胞腔取一个代表值，凡是落入该胞腔的矢量均用该代表值进行量化。,与标量量化比较，矢量量化还具有如下特点：（1）矢量量化是把量化矢量（码字）分别存储在编码器和译码器两端的码书中，在信道中传输的并不是输入矢量X的量化矢量Y本身，而是码字Y的下标j的编码信号；（2）在相同的速率下，矢量量化的失真比标量量化的失真明显的小；（3）在相同的失真条件下，矢量量化所需要的速率比标量量化所需的速率低的多；,（4）矢量量化是一种多维模式匹配、多维优化过程，而标量量化是一维模式匹配、一维优化过程。一般来说，用一维优化是得不到多维优化的结果的。（5）矢量量化的复杂度随维数成指数增加，所以矢量量化的复杂度比标量量化的复杂度高。归结起来，正如率-失真理论所指出的，组编码总是优于单个输出的逐个编码的，当编码长度K趋于无穷大时，可以达到率失真界。,7.3最佳矢量量化1.最佳矢量量化器的概念矢量量化器的速率定义为：r=B/K=(logN)/K（bit/样值或每维）式中B=logN表示每个码字的编码比特数；N码书的大小；K维数。,最佳矢量量化器的概念:给定条件下，失真最小的矢量量化器，称为这个条件下的最佳矢量量化器。给定矢量量化器的码书大小N，求最小失真式中QN为所有码书大小为N的K维矢量量化器的集合。,2.设计最佳矢量量化器的必要条件一是在给定码书的条件下，寻找信源空间的最佳划分，使平均失真最小；二是在给定划分的条件下，寻找最佳码书，使平均失真最小。（1）最佳划分给定码书，可以用最近邻准则NNR得到最佳划分。图7.4为最佳划分示意图。,图7.4最佳划分示意图,最佳划分定义：信源空间中任一点X,若XSj，当且仅当矢量X与码字Yj的失真小于X和其它码字失真，即：则Sj为最佳划分。Voronoi划分：把信源空间划分成与码书大小相同的N个区间Sj(j=1,2,N)。这种划分称为Voronoi划分。Voronoi胞腔：Voronoi划分对应子集Sj(j=1,2,N)称为Voronoi胞腔(Cell)，简称胞腔。,（2）最佳码书给定了划分Si（并不是最佳划分）后，为了使码书的平均失真最小，码字Yi必须为相应划分Si(i=1，2，N)的形心，即：式中min-1表示选取的Yi使平均失真Ed(X,Y)|XSi为最小的Y。,对于由训练序列定义的样点分布和常用的均方失真测度，形心由下式给出：式中|Si|表示集合Si中元素的个数（即Si集中有|Si|个X）。,7.4矢量量化器的设计算法及MATLAB实现7.4.1LBG算法设计矢量量化器的主要任务是设计码书。码字数目N给定时，由Linde，Buzo，和Gray三人1980年首次提出矢量量化器的一个设计算法，通常称为LBG算法。,已知训练序列设计算法的具体步骤如下：给定初始码书，即给定码书大小N和码字，并置n=0，设起始平均失真D(-1)，给定计算停止门限（0d(X,Y1)，则走下支路（下子树），到了节点Y1处送出1码至信道；若d(X,Y0)d(X,Y1),则走上支路（上子树），到了节点Y0处，就送出0码至信道。,第二步若上一步走的是下支路，那么在节点Y1处，再计算输入矢量X与节点Y10、Y11的失真d（X，Y10）和d（X，Y11），并且比较它们的大小。若d（X，Y10）d（X，Y101）,则走下支路，到了树叶Y101处送出1码到信道。Y101便是输入矢量X的量化矢量，在信道中传输的符号是101。反之则走上支路，到了树叶Y100处，送出0码到信道。Y100便是X的量化矢量，在信道中传输的是符号100。,2树结构的设计树搜索矢量量化器的编码器是由树型码书和相应的搜索算法构成的。这种矢量量化器译码器的码书和编码器的码书不同。译码器是采用数组型码书，图7.8是它的原理图。设计树结构（找出各层的码字）的方法有两种：一种是从树叶开始设计；另一种是从树根开始设计。,图7.8树搜索矢量量化器原理框图,（1）从树叶开始设计的办法,四层二叉树矢量量化器维数为K，第四层有N=8个码字（树叶数）。第一步假定第四层的8个码字，已由前面设计码书的方法得到了。将这些码字，按码字距离最近配对的原则（因为是二叉树型），得到：Y000,Y001,Y010,Y011,Y100,Y101,Y110,Y111,并把它们放在相应的树叶位置上。,第二步求出这些码字对的中心，如Y000，Y001的中心为Y00。总共得到四个中心：Y00，Y01，Y10，Y11，并把它们放在第三层上。第三步将第三层上的码字仍按最近距离原则配对，得到Y00，Y01，Y10，Y11。再求出码字对中心Y0与Y1并将它们放在第二层上.这种树形码书总的尺寸为N0=8+4+2=14，即共有14个码字，而译码端的码字大小就是树叶数N=8。,(2)从树根开始设计的方法,以四层二叉树为例，具体设计步骤如下：第一步求出整个训练序列的形心，作为初始码书。用一个合适的参数A去乘，得到另一个码字。而后以与为初始码字，将训练序列按一定失真测度划分为两个胞腔，再计算出两个胞腔的形心Y0与Y1。用这种分裂法得到的Y0，Y1便是第二层地个码字。,第二步再用上述分裂法，得到第三层的4个码字Y00，Y01，Y10，Y11。这样继续下去，一直计算到树叶为止。从上面的叙述不难看出，树搜索的过程是逐步求近似值的过程，中间的码字只起指引路线的作用。,3树搜索矢量量化器的复杂度,树搜索矢量量化器的特点是以适当提高空间复杂度来降低时间复杂度。在搜索时间上，二叉树的搜索速度最快，全搜索最慢。在存储量上，二叉树多于全搜索。由于树搜索并不是从整个码书中寻找最小失真的码字，因此它的量化器并不是最佳的，也就是说树搜索矢量量化器的性能比全搜索矢量量化器的性能差。通常可以适当选择各层的树叉型数，在搜索速度、存储量及质量三者之间得到一种折衷。,7.5.2多级矢量量化器系统,多级矢量量化器系统由若干个普通的矢量量化器系统级联而成，如图7.9所示，它的第一级是一个包括M1个码字的矢量量化器系统。对每一个输入矢量X，矢量量化编码器1按最近邻准则找到一个码字Yi(1)并计算出X与此码字的误差矢量。这个误差矢量即是第二级矢量量化器系统的输入。,这样一级级地推导就可以构成一个级联系统。整个矢量量化编码器的输出即是各级联矢量量化编码器的输出码字的编号，而矢量量化译码器则可以根据这些编号恢复原始的输入矢量。多级矢量量化系统无论在减少搜索计算量方面还是减少码字存储量方面都有可观的改进，它的缺点是在同样的码书容量下，其平均量化失真大于全搜索矢量量化系统。,7.5.3波形/增益矢量量化器,编码器解码器图7.10波形/增益矢量量化器原理框图,对时域波形进行矢量量化时，将待量化矢量的波形和增益分开，分别进行矢量量化和标量量化。设输入矢量为X，其增益为，具有非零增益矢量的波形为S=X/g。采用平方误差失真测度，则输入矢量和量化矢量间的失真为,和分别是增益和波形矢量S的量化结果。,VQ编码可分两步使上式达到最小。首先在VQ码书中找到一个码字，使其与输人矢量的点积达到最大值；然后在增益标量量化码书中寻找一个与最为接近的增益值(即使达到最小)。将和对应的编号传到解码器中。后者通过查表将作为解码输出。,7.5.4分离均值矢量量化器,分离均值矢量量化器先将输入矢量的平均值分离出来，以较低的速率对均值进行标量量化，然后对去掉均值的输入矢量进行矢量量化。其码书的设计过程描述如下：第一步根据原始训练序列计算矢量均值，对均值矢量选择合适的标量量化方法进行量化。第二步从原始训练序列矢量中减去对应矢量的量化均值，形成残差训练序列，使用LBG算法对该序列进行训练求得残差码书。,7.5.5有记忆的矢量量化,前面两节介绍的都属于无记忆的矢量量化情况。因为在量化每一矢量时，都不依赖于此矢量之前或之后的任何矢量。与之相反，如果能利用过去的输入矢量的信息，来决定当前的输入矢量应该用哪一个码书进行比较，那么，通过机器的“记忆”，人们就可以利用矢量之间的相关性，来提高矢量量化的性能。有记忆的矢量量化又称反馈型的矢量量化，它是多