第6章-矢量量化剖析.ppt

第6章矢量量化,“十二五”普通高等教育本科国家级规划教材,第六章矢量量化,6.1矢量量化的基本原理,6.2最佳矢量量化器,本章目录结构,6.3矢量量化器的设计算法及MATLAB实现,概述,“十二五”普通高等教育本科国家级规划教材,第六章矢量量化,概述,“十二五”普通高等教育本科国家级规划教材,第六章矢量量化,“十二五”普通高等教育本科国家级规划教材,概述,率-失真理论指出，利用矢量量化，编码性能有可能任意接近率-失真函数，其方法是增加维数k；该理论指出了矢量量化的优越性。率-失真理论在实际应用中的重要指导意义：常作为一个理论下界与实际编码速率相比较，分析系统还有多大的改进余地。但是，率-失真理论是一个存在性定理而非构造性定理，因为它没有指出如何构造矢量量化器。,“十二五”普通高等教育本科国家级规划教材,概述,矢量量化技术的发展历程,最佳矢量量化问题,Steinhaus,1956年,如何划分量化区间及求量化值问题,Loyd和Max,1957年,提出实际矢量量化器,Buzo,1978年,LBG算法,Linde,Buzo和Gray,1980年,“十二五”普通高等教育本科国家级规划教材,概述,6.1矢量量化基本原理,“十二五”普通高等教育本科国家级规划教材,第六章矢量量化,1.定义：矢量量化是先把信号序列的每K个样点分成一组，形成K维欧氏空间中的一个矢量，然后对此矢量进行量化。,语音信号处理,图像信号处理,移动通信,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,xnX1X2X3X4Xn图6.14维矢量形成示意图,图示输入信号序列xn，每4个样点构成一个矢量（取K=4），共得到n/4个4维矢量：X1，X2，X3，Xn/4,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,矢量量化就是先集体量化X1，然后量化X2，依次向下量化。下面以K=2为例说明其量化过程。,图6.2矢量量化示意图,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,2.几个概念量化矢量(或称重构矢量)：利用最小失真原则，分别计算用量化矢量Yi（i=1，2，7）替代X所带来的失真，其中最小失真所对应的那个矢量Yj，就是模拟矢量X的量化矢量。码书：量化矢量构成的集合称为码书(Codebook)。码字：码书中的每个矢量Yj（i=1，2，N）称为码字(Codeword)。,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,3.矢量量化的基本原理矢量量化就是把一个K维模拟矢量映射为另一个K维量化矢量的过程。其数学表达式为式中：X输入矢量；信源空间；Rkk=1，2，K，K维欧氏空间；Y量化矢量(码字或码矢)；输出空间(即码书)；Q(.)量化符号；N码书的大小(即码字的数目)。,（6-1）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,矢量量化系统通常可以分解为两个映射的乘积式中是编码器，它是将输入矢量映射为信道符号集中的一个元；是译码器，它是将信道符号映射为码书中的一个码字Yi。即,（6-2）,（6-3）,（6-4）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,有了失真测度，就可以根据矢量量化的定义来具体设计矢量量化器了。通常用最小失真的方法最近邻法NNR来设计，也就是要满足下式：式中：IN=1,2,i,，N；N码书的大小；符号表示当且仅当（充分必要条件）,（6-5）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,图6.3矢量量化器实现框图,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,1.失真测度失真测度的选择直接影响矢量量化系统的性能。失真测度是以什么方法来反映用码字Yi代替信源矢量X时所付出的代价。这种代价的统计平均值(平均失真)描述了矢量量化器的工作特性，即式中E表示求期望。,（6-6）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,常用的失真测度有如下几种：,（6-7）,（6-8）,（6-9）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,特点,必须在主观评价上有意义，即小的失真对应好的主观质量评价；,必须在数学上易于处理，能导致实际的系统设计；,3.必须可计算并保证平均失真D=ED(X,Q(X)存在；,4.采用的失真测度，应使系统容易用硬件实现。,要使所选用的失真测度有实际意义，必须要求它具有以下几个特点：,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,2.编码速率矢量量化器的速率定义为式中：表示每个码字的编码比特数；N码书的大小(即码字的数目)；K维数。信道中传输速率RT与矢量量化器速率r的关系为式中为抽样速率。,（6-10）,（6-11）,“十二五”普通高等教育本科国家级规划教材,6.1矢量量化基本原理,6.2最佳矢量量化器,“十二五”普通高等教育本科国家级规划教材,第六章矢量量化,1.码书设计设计出性能优良的码书是矢量量化的首要问题。码书设计过程是寻求一种最佳方案把训练矢量分成指定大小类别的过程。假设训练矢量数为M，待生成的码书包含N（Nd(X,Y1)，则走下支路（下子树），到了节点Y1处送出1码至信道；若d(X,Y0)d(X,Y1)，则走上支路（上子树），到了节点Y0处送出0码至信道。,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,第二步若上一步走的是下支路，那么在节点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。,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,2.树结构的设计树搜索矢量量化器的编码器是由树型码书和相应的搜索算法构成的。这种矢量量化器译码器的码书和编码器的码书不同。译码器是采用数组型码书，下图是它的原理图。设计树结构（找出各层的码字）的方法有两种：一种是从树叶开始设计；另一种是从树根开始设计。,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,图6.8树搜索矢量量化器原理框图,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,（1）从树叶开始设计的办法,四层二叉树矢量量化器维数为K，第四层有N=8个码字（树叶数）。第一步假定第四层的8个码字，已由前面设计码书的方法得到了。将这些码字，按码字距离最近配对的原则（因为是二叉树型），得到：Y000,Y001,Y010,Y011,Y100,Y101,Y110,Y111,并把它们放在相应的树叶位置上。,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,第二步求出这些码字对的中心，如Y000，Y001的中心为Y00。总共得到四个中心：Y00，Y01，Y10，Y11，并把它们放在第三层上。第三步将第三层上的码字仍按最近距离原则配对，得到Y00，Y01，Y10，Y11。再求出码字对中心Y0与Y1并将它们放在第二层上.这种树形码书总的尺寸为N0=8+4+2=14，即共有14个码字，而译码端的码字大小就是树叶数N=8。,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,(2)从树根开始设计的方法,以四层二叉树为例，具体设计步骤如下：,“十二五”普通高等教育本科国家级规划教材,6.3矢量量化器的设计算法及MATLAB实现,3.树搜索矢量量化器的复杂度,树搜索矢量量化器的特点是以适当提高空间复杂度来降低时间复杂度。在搜索时间上，二叉树的搜索速度最快，全搜索最慢。在存储量上，二叉树多于全搜索。由于树搜索并不是从整个码书中寻找最小失真的码字，因此它的量化器并不是最佳的，也就是说树搜索矢