矢量量化

数字语音处理及MATLAB仿真张雪英编著1矢量量化器的设计算法及MATLAB实现1概述12矢量量化基本原理3最佳矢量量化器34矢量量化器的设计算法及MATLAB实现45降低复杂度的矢量量化系统52数字语音处理及MATLAB仿真张雪英编著21概述量化分为两大类：标量量化和矢量量化。标量量化：把抽样后的信号值逐个进行量化。矢量量化：将k(k≥2)个抽样值形成K维空间Rk中的一个矢量，然后将此矢量进行量化，。矢量量化优于标量量化，为不可逆压缩方法，具备比特率低、解码简单、失真较小的优点。矢量量化广泛应用于图像、语音压缩编码、移动通信、语音识别、文献检索及数据库检索等领域。数字语音处理及MATLAB仿真张雪英编著3矢量量化的理论基础是仙农的率-失真理论。率-失真理论指出，利用矢量量化，编码性能有可能任意接近率-失真函数，其方法是增加维数k；该理论指出了矢量量化的优越性。率-失真理论在实际应用中的重要指导意义：常作为一个理论下界与实际编码速率相比较，分析系统还有多大的改进余地。但是，率-失真理论是一个存在性定理而非构造性定理，因为它没有指出如何构造矢量量化器。数字语音处理及MATLAB仿真张雪英编著4矢量量化技术的发展历程最佳矢量量化问题Steinhaus1956年如何划分量化区间及求量化值问题Loyd和Max1957年提出实际矢量量化器Buzo1978年LBG算法Linde,Buzo和Gray1980年数字语音处理及MATLAB仿真张雪英编著52矢量量化基本原理2.1矢量量化的定义（1）定义：矢量量化是先把信号序列的每K个样点分成一组，形成K维欧氏空间中的一个矢量，然后对此矢量进行量化。nx数字语音处理及MATLAB仿真张雪英编著6{xn}X1X2X3X4Xn/4图示输入信号序列{xn}，每4个样点构成一个矢量（取K=4），共得到n/4个4维矢量：X1，X2，X3，…，Xn/4数字语音处理及MATLAB仿真张雪英编著7a2a1(a)SiS1Y2Y3Y4Y5Y6Y7Y1a2(b)图7.2矢量量化示意图Yia1矢量量化就是先集体量化X1,然后量化X2，依次向下量化。下面以K=2为例说明其量化过程。数字语音处理及MATLAB仿真张雪英编著8（2）几个概念量化矢量(或称重构矢量)：利用最小失真原则，分别计算用量化矢量Yi（i=1，2，……7）替代X所带来的失真，其中最小失真所对应的那个矢量Yj，就是模拟矢量X的量化矢量。码书：量化矢量构成的集合称为码书(Codebook)。码字：码书中的每个矢量Yj（i=1，2，……N）称为码字(Codeword)。数字语音处理及MATLAB仿真张雪英编著92.2失真测度失真测度的选择直接影响矢量量化系统的性能。失真测度是以什么方法来反映用码字Yi代替信源矢量X时所付出的代价。这种代价的统计平均值(平均失真)描述了矢量量化器的工作特性，即式中E[·]表示求期望。))](,([XXQdED数字语音处理及MATLAB仿真张雪英编著10常用的失真测度有如下几种：⑴平方失真测度这是最常用的失真测度，易于处理和计算，且在主观评价上有意义，即小的失真值对应好的主观评价质量。22,iidXYXYXY数字语音处理及MATLAB仿真张雪英编著11⑵绝对误差失真测度主要优点：计算简单，硬件容易实现。⑶加权平方失真测度式中T——矩阵转置符号；W——正定加权矩阵。kiiid1,YXYXYXYXYXYXW,Td数字语音处理及MATLAB仿真张雪英编著12要使所选用的失真测度有实际意义，必须要求它具有以下几个特点：1.必须在主观评价上有意义，即小的失真对应好的主观质量评价；2.必须在数学上易于处理，能导致实际的系统设计；3.必须可计算并保证平均失真D=E[D(X,Q(X))]存在；4.采用的失真测度，应使系统容易用硬件实现。数字语音处理及MATLAB仿真张雪英编著132.3矢量量化器通常用最小失真的方法-最近邻准则NNR（NearestNeighborRule)）来设计矢量量化器，也就是要满足下式：式中IN={1,2,……,i,……N}；N—码书的大小；符号表示充分必要条件。(,)(,)ijNXidXYdXYjI数字语音处理及MATLAB仿真张雪英编著14N维输入jmax信道jmaxXi矢量或存储器矢量量化原理框图计算最小距离),(minjiyxd找到相应角标jmax从码本找出minjy失真测度定义码本jyj=0,1……L-1码本jyj=0,1……L-1数字语音处理及MATLAB仿真张雪英编著15矢量量化器的工作过程是：在编码端，输入矢量X与码本中的每一个或部分码字进行比较，分别计算出它们的失真。搜索到失真最小的码字Yj的序号(或此码字在码本中的地址)，并将j的编码信号通过信道传送到译码端；在译码端，先把信道传送来的编码信号译成序号j，再根据序号（或码字Yj所在地址），从码本中查出相应的码字Yj。Yj是输入矢量X的重构矢量。数字语音处理及MATLAB仿真张雪英编著16矢量量化系统通常可以分为两个映射的乘积式中:α是编码器，它是将输入矢量映射为信道符号集IN={i1,i2,…,iN}中的一个元素ij；β是译码器，它是将信道符号集ij映射为码书中的一个码字Yi。即KRXQα(X)=ijX∈χ，ij∈INβ(ij)=Yiij∈INYi∈YN数字语音处理及MATLAB仿真张雪英编著17矢量量化定义:把一个K维模拟矢量的有序集（称为信源矢量集合）中的某个矢量X∈χ映射为N个量化矢量构成的有限集（码书或码本）中的某个矢量（码字或码矢）Y∈，这种映射称为矢量量化。KiNNRYYYY|,,,21KRN数字语音处理及MATLAB仿真张雪英编著18一个矢量量化器可以表示成以下三个部分：码书：空间划分：S=映射：q：其中，Si是Rk的一个子集且满足矢量量化器Q()的性能，以其输入矢量X和输出矢量Y=q(X)的失真平均值而定，失真平均值为：KiiNRYNiY,,,2,1|,NiSi,,2,1|,NsKR,()KiiSXRqXYSN,D(Q,F)=E[d(X,Y)]=E[d(X,q(X))]数字语音处理及MATLAB仿真张雪英编著19补充：矢量量化与标量量化的比较矢量量化是把一个K维模拟矢量映射为一个K维量化矢量。标量量化实际是维数K=1的矢量量化。一般情况下，矢量量化均指K≥2的多维量化。与标量量化的两个主要步骤相对应，矢量量化首先要将抽样值构成的矢量即K维空间的无穷多点划分成有限个胞腔，然后从每一个胞腔取一个代表值，凡是落入该胞腔的矢量均用该代表值进行量化。数字语音处理及MATLAB仿真张雪英编著20与标量量化比较，矢量量化还具有如下特点：（1）矢量量化是把量化矢量（码字）分别存储在编码器和译码器两端的码书中，在信道中传输的并不是输入矢量X的量化矢量Y本身，而是码字Y的下标j的编码信号；（2）在相同的速率下，矢量量化的失真比标量量化的失真明显的小；（3）在相同的失真条件下，矢量量化所需要的速率比标量量化所需的速率低的多；数字语音处理及MATLAB仿真张雪英编著21（4）矢量量化是一种多维模式匹配、多维优化过程，而标量量化是一维模式匹配、一维优化过程。一般来说，用一维优化是得不到多维优化的结果的。（5）矢量量化的复杂度随维数成指数增加，所以矢量量化的复杂度比标量量化的复杂度高。归结起来，正如率-失真理论所指出的，组编码总是优于单个输出的逐个编码的，当编码长度K趋于无穷大时，可以达到率失真界。数字语音处理及MATLAB仿真张雪英编著223最佳矢量量化1.最佳矢量量化器的概念矢量量化器的速率定义为：r=B/K=(logN)/K（bit/样值或每维）式中B=logN表示每个码字的编码比特数；N—码书的大小；K—维数。2数字语音处理及MATLAB仿真张雪英编著23最佳矢量量化器的概念:给定条件下，失真最小的矢量量化器，称为这个条件下的最佳矢量量化器。给定矢量量化器的码书大小N，求最小失真式中QN为所有码书大小为N的K维矢量量化器的集合。))](,([min)(XQXdENQQN数字语音处理及MATLAB仿真张雪英编著242.设计最佳矢量量化器的必要条件一是在给定码书的条件下，寻找信源空间的最佳划分，使平均失真最小；二是在给定划分的条件下，寻找最佳码书，使平均失真最小。（1）最佳划分给定码书，可以用最近邻准则NNR得到最佳划分。图7.4为最佳划分示意图。NNYYY,,,21数字语音处理及MATLAB仿真张雪英编著25图7.4最佳划分示意图•Y3S2•Y6•Y4•Y2•·•Y1•YjS1•YN••XSj•••••数字语音处理及MATLAB仿真张雪英编著26最佳划分定义：信源空间χ中任一点X,若X∈Sj，当且仅当矢量X与码字Yj的失真小于X和其它码字失真，即：则Sj为最佳划分。Voronoi划分：把信源空间划分成与码书大小相同的N个区间Sj(j=1,2,…,N)。这种划分称为Voronoi划分。Voronoi胞腔：Voronoi划分对应子集Sj(j=1,2,…,N)称为Voronoi胞腔(Cell)，简称胞腔。NiY),(),(|ijjYdYds且JNiji,数字语音处理及MATLAB仿真张雪英编著27（2）最佳码书给定了划分Si（并不是最佳划分）后，为了使码书的平均失真最小，码字Yi必须为相应划分Si(i=1，2，…N)的形心，即：式中min-1表示选取的Yi使平均失真E[d(X,Y)|X∈Si]为最小的Y。,min1iRiSdEkXYXYY数字语音处理及MATLAB仿真张雪英编著28对于由训练序列定义的样点分布和常用的均方失真测度，形心由下式给出：式中|Si|表示集合Si中元素的个数（即Si集中有|Si|个X）。1iisiSxYX数字语音处理及MATLAB仿真张雪英编著294矢量量化器的设计算法及MATLAB实现7.4.1LBG算法设计矢量量化器的主要任务是设计码书。码字数目N给定时，由Linde，Buzo，和Gray三人1980年首次提出矢量量化器的一个设计算法，通常称为LBG算法。数字语音处理及MATLAB仿真张雪英编著30已知训练序列设计算法的具体步骤如下：①给定初始码书，即给定码书大小N和码字{}，并置n=0，设起始平均失真D(-1)→∞，给定计算停止门限ε（0ε1）。)0(Ny)0()0(2)0(1,,,NYYY已知训练序列的LBG设计算法：②用码书为已知形心，根据最佳划分原则把训练序列TS={}划分为N个胞腔，即：()nNy)0()0(2)0(1,,,NYYY()(){|(,)(,)},,,(=1,2,,)njjinijNSXdXYdXYijYYyXTSjN数字语音处理及MATLAB仿真张雪英编著31开始给定码书大小N，初始码书YN(0)，训练序列TS={Xr|r=1,2,…,m}计算停止门限ε，置n=0，D(-1)→∞用给定码书Yn(n)划分成N个胞腔Sj(n)={X|d(X,Yj)?d(X,Yi)i≠j，Yi，Yj∈YN(n)}是图7.6已知训练序列的算法,min1∑1∈mrrndmDnNYXYY~1nnnnDDDD计算求出这时N个胞腔的形心构成新码书YN（n+1）,置n=n+1结束()≤~nD否YN=YN(n)数字语音处理及MATLAB仿真张雪英编著32③计算平均失真与相对失真。平均失真为式中，相对失真为若，则停止计算，当前的码书就是设计好的码书，否则进行第④步。),(min11)()(YXdmDrmryYnnNTSXrmr,......,2,1)()()1()(~nnnnDDDD)(~nD)(nNy)(nNNyy数字语音处理及MATLAB仿真张雪英编著33④利用计算这时划分的各胞腔的形心，由这N个新形心{}构成新的码书，并置n=n+1，返回第②