语音信号处理课件第七章.ppt

第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维欧氏空间中的一个矢量，然后对此矢量进行量化。,xn X1 X2 X3 X4 Xn/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（Nearest Neighbor Rule)）来设计矢量量化器，也就是要满足下式： 式中 IN=1,2,i,N； N 码书的大小； 符号 表示充分必要条件。,矢量量化器的工作过程是： 在编码端，输入矢量X与码本中的每一个或部分码字进行比较，分别计算出它们的失真。搜索到失真最小的码字Yj 的序号(或此码字在码本中的地址)，并将j的编码信号通过信道传送到译码端；在译码端，先把信道传送来的编码信号译成序号j，再根据序号（或码字Yj 所在地址），从码本中查出相应的码字Yj 。Yj 是输入矢量X的重构矢量。,矢量量化系统通常可以分为两个映射的乘积 式中:是编码器，它是将输入矢量 映射为信道符号集IN=i1, i2, , iN中的一个元素ij ； 是译码器，它是将信道符号集ij映射为码书中的一个码字Yi 。即,( X )= ij X， ij IN (ij )= Yi ij IN Yi YN,矢量量化定义: 把一个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=log N表示每个码字的编码比特数； 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.1 LBG算法 设计矢量量化器的主要任务是设计码书。码字数目N给定时，由Linde，Buzo，和Gray三人1980年首次提出矢量量化器的一个设计算法，通常称为LBG算法。,已知训练序列设计算法的具体步骤如下： 给定初始码书 ，即给定码书大小N和码字 ，并置n=0，设起始平均失真 D(-1)，给定计算停止门限（01）。,已知训练序列的LBG设计算法：, 用码书 为已知形心，根据最佳划分原则把 训练序列TS= 划分为N个胞腔，即：, 计算平均失真与相对失真。 平均失真为 式中 ， 相对失真为 若 ，则停止计算，当前的码书 就是设计好的码书 ，否则进行第步。, 利用 计算这时划分的各胞腔的形心，由这N个新形心 构成新的码书 ，并置n=n+1，返回第步再进行计算，直到 ,得到所要求的码书 为止。,2 初始码书的选定与胞腔的处理 初始码书如何选取，对最佳码书设计很有影响。下面介绍初始码书选取方法。 （1）随机选取法 这种方法最先用于K-均值聚类算法中，它是从训练序列中随机选取N 个矢量作为初始码字,构成初始码书 。,优点： (1)不用初始化计算，可以大大减少计算时间； (2)初始码字选自训练序列中，无空胞腔问题。 缺点： (1)可能会选到一些非典型的矢量作为码字； (2)会造成在某些空间把胞腔分得过细，而有些 空间分的太大。 以上缺点会导致码书中有限个码字得不到充分利 用，设计的矢量量化器性能可能较差。,（2）分裂法 1980年由Linde,Buzo和Gray提出，具体步骤如下： 计算所有训练序列TS的形心，将此形心作为第 一个码字 ； 选一个合适参数A乘以码字 ，形成第二个码字 ; 以码字 、 为初始码书，即： 用所述LBG算法，去设计仅含2个码字的码书 。, 将码书 中2个码字 分别乘以合适的参数B，得到4个码字 ； 以这4个码矢为基础，按步骤3去构成含4个码字的码书，再乘以合适的参数以扩大码字数目。如此反复，经log2N次设计，就得到所要求的有N个码字的初始码书 。,（3）空胞腔和随机选择法中非典型矢量的处理 去空胞腔分裂法。 首先把某空胞腔中的形心去掉，然后将最大的胞腔 分裂为2个小胞腔。分裂方法如下： （a）用一个合适的参数A去乘以原形心 ，得到2个码字：,（b）以 2个码字来划分这个大胞腔，构成2个小胞腔 :, 非典型码字的处理。 随机选择法存在一些非典型矢量，此时可采用下面办法来处理： （a）重新选择随机初始码字，直到没有非典型码字为止； （b）把这种胞腔中少数矢量分别归并到邻近的各个胞腔中，再用分裂法把其中一个最大的胞腔分裂为2个小胞腔。,矢量量化器的复杂度 矢量量化与标量量化相比，其主要缺点是复杂度随维数的增大而成指数式增加，这是实现高维数矢量量化的主要障碍。,7.5 降低复杂度的矢量量化系统,在信号处理中，复杂度有两种： 时间复杂度单位时间内所需要的计算量，它包括加（减）法、乘法和比较运算的次数； 空间复杂度存储容量。 矢量量化器复杂度的度量，应该以时间复杂度和空间复杂度进行度量。 对降低复杂度的研究，可朝两个方向进行： 一：寻找好的快速算法； 二：使码书结构化，以减小搜索量和存储量。,7.5.1 树搜索矢量量化器 1 树搜索原理 下面以二叉树为例说明树搜索原理。 二叉树结构图中，以树根第一层为起点，第二层有2个节点（Y0，Y1）；第三层有4个节点（Y00，Y01，Y10，Y11）；第四层（此树的最后一层）有8个节点，这层上的节点又称为树叶。,树型编码过程中，只计算部分矢量失真，就可以解决下一步搜索的子树。编码时的走步控制原则为 0 当上子树的节点失真最小时 控制逻辑值= 1 当下子树的节点失真最小时,具体量化步骤如下： 第一步 分别计算输入矢量X与Y0、Y1的失真 d (X,Y0)和d(X,Y1)并且比较它们的大小。 若 d (X,Y0) d(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，Y10），则走上支路，到Y10处送出0码至信道；反之，就走下支路，到了Y11处，送出1码至信道。,第三步 若刚才走的是上支路，那么在节点Y10处分别计算失真d（X，Y100）和d（X，Y101），并且比较它们的大小，若d（X，Y100） 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