语音信号处理第四章矢量量化技术

.,第四章矢量量化技术(VectorQuantizationVQ),4.1概述4.2矢量量化的基本原理4.3矢量量化的失真测度4.4矢量量化的最佳码本设计4.5矢量量化系统,.,4.1概述,一、矢量量化的应用二、标量量化和矢量量化的区别,.,矢量量化（VQ，即VectorQuantization）是一种极其重要的信号压缩方法。VQ在语音信号处理中占十分重要的地位。广泛应用于语音编码、语音识别和语音合成等领域。量化分为两类：*标量量化：将取样后的信号值逐个地进行量化。*矢量量化：将若干取样信号分成一组，即构成一个矢量，然后对此矢量一次进行量化。凡是要用量化的地方都可以采用矢量量化。,.,矢量量化技术技术是一种数据压缩和编码技术，矢量量化压缩技术的应用领域非常广阔，如军事部门和气象部门的卫星(或航天飞机)遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储与传输、数字电视和DVD的视频压缩、医学图像的压缩与存储、网络化测试数据的压缩和传输、语音编码、图像识别和语音识别等等。,一、矢量量化的应用,.,矢量量化是实现数据压缩的一种有效方法，早在50和60年代就被用于语音压缩编码。直到70年代线性预测技术被引入语音编码后，矢量量化技术才活跃起来。80年代初，矢量量化技术的理论和应用研究得到迅速发展。采用矢量量化技术对信号波形或参数进行压缩处理，可以获得很好的效益，使存储要求、传输比特率需求或计算量需求降低.,.,整个动态范围被分成若干个小区间，每个小区间有一个代表值，量化时落入小区间的信号值就用这个代表值代替，或者叫被量化为这个代表值。这时的信号量是一维的，所以称为标量量化。,二、标量量化和矢量量化的区别,采样,量化,xa(t),xa(nT),x(n),xa1,x1,xk,xak,xak+1,xk+1,xL,xaL,xaL+1,x(n)=Qxa(nT)。,1.标量量化：,.,2,-,-2,2,标量量化,.,2.矢量量化：,若干个标量数据组成一个矢量，矢量量化是对矢量进行量化，和标量量化一样，它把矢量空间分成若干个小区域，每个小区域寻找一个代表矢量，量化时落入小区域的矢量就用这个代表矢量代替，或者叫被量化为这个代表矢量。例如，所有可能的二维矢量就构成了一个平面，将平面分成7个小区域。,.,x1,x2,Yi（x1i,x2i）,代表矢量,.,采用矢量量化的效果优于标量量化的原因？,矢量量化能有效的应用矢量中各分量之间的四种相互关联性质来消除数据中的冗余度。这四种相互关联的性质是线性依赖(相关性)、非线性依赖(统计不独立)、概率密度函数的形状和矢量量化的维数，而标量量化仅能利用线性依赖和概率密度函数的形状来消除冗余度。,.,假设声道滤波器传输函数用4个系数来描述，又假设声道只能为4个可能的形状之一。这意味着只存在4组可能的声道滤波器传输函数。现在考虑对每一个滤波器系数单独进行标量量化，需要2bit，每一分析帧需要8个比特来进行编码。,3、标量量化与矢量量化的区别,.,如果我们知道只有4种可能的声道形状，与4个可能的声道滤波器系数组成的矢量相对应，在这种情况下，一个分析帧，只需要2bits对4个滤波器系数进行编码，这样降低了所需的比特数。矢量量化就是利用数据之间的相关性来降低所需的比特率。,第一种声道滤波器系数第二种声道滤波器系数第三种声道滤波器系数第四种声道滤波器系数,.,4.2矢量量化的基本原理,一、矢量量化的基本原理二、矢量量化在语音通信中的应用三、矢量量化在语音识别中的应用四、矢量量化的关键之处,.,1.矢量的定义,一、矢量量化的基本原理,若干个标量数据组成一个矢量，标量的个数就为矢量的维数。如语音信号某一帧中提取的声道参数，共K个,Xi=ai1,ai2,aiK。则Xi是一个K维矢量。设共有N个K维矢量X=X1,X2,XN,其中第i个矢量为Xi，i=1,2,N。以此类推，N个语音帧，每帧中共有K个声道参数，共组成N个K维矢量。,a11,a12,a1K,aN1,aN2,aNK,第1帧,第N帧,.,X1=a11,a12,a1KX2=a21,a22,.,a2kXN=aN1,aN2,.,aNk,N个矢量，每个矢量的维数为K,.,所有K维矢量构成了一个空间为RK，无遗漏地划分成J个互不相交的子空间R1,R2RJ,将Rj称为胞腔。在每一个子空间Rj找一代表矢量Yj，则J个代表矢量可以组成的矢量集为：Y=Y1,Y2,YJ构成了一个矢量量化器，Y叫做码本，J称为码本长度,Yj称为码字，有：Yj=yj1,yj2,yjK，j=1,2,J。,2.矢量空间的划分,.,举例,以K=2为例来说明。当K=2时，所得到的是二维矢量。所有可能的二维矢量就构成了一个平面。第i个二维矢量记为：Xi=xi1,xi2。先把这个平面划分成J块互不相交的子区域，从每个子区域中找出一个代表矢量。如J=7。,.,x1,x2,码本Y=Y1,Y2,YJ码本长度J=7码字Yj=xj1,xj2，j=1,2,J,.,维数为k，码本长度为J的矢量量化器Q定义：从k维欧几里德空间Rk到一包含N个输出(重构)点的有限集合C的映射，Q：RkC，其中C=y1,y2,yJyiRk，i1,J集合C称作码本或码书，码本长度为J。码本的J个元素称作码字或码矢量，它们均为Rk中的矢量，K维矢量。,矢量量化器定义：,.,当给矢量量化器输入一个任意矢量Xi进行矢量量化时，矢量量化器首先判断它属于哪个子空间，然后输出该子空间的代表矢量Yj。矢量量化过程就是用Yj代替Xi的过程。YjQ(Xi)1jJ1iN,3.矢量量化的过程,矢量量化器,Xi,Yj,.,当给矢量量化器输入一个任意矢量Xi进行矢量量化时，矢量量化器首先判断它属于哪个子空间，如何判断就是要依据一定的规则，选择一个合适的失真测度，分别计算每个码字代替Xi所带来的失真，当确定产生最小失真的那个码字Yj时，就将Xi量化成Yj，Yj就是Xi的重构矢量（和恢复矢量）。,4.判断规则,.,Xi=ai1,ai2,aiK,Y2,Y1=y11,y12,y1K,Y2=y21,y22,y2K,YJ=yJ1,yJ2,yJK,矢量量化器（码本）,最小失真,计算失真,.,x,4,矢量量化,3,3,2,码书,码字c0,码字c1,码字c2,码字c3,索引00,d(x,c0)=5d(x,c1)=11d(x,c2)=8d(x,c3)=8,x,.,图像编码例子：原图象块（4灰度级）x0123码书Cy0,y1,y2,y3y0y1y2y3,d(x,y0)=25d(x,y1)=5d(x,y2)=25d(x,y3)=46,码字y1最接近输入矢量图象块x，故用索引“01”编码,.,标量量化是维数为k=1的矢量量化。一般矢量量化均指k1多维量化。一个k维最佳矢量量化器的性能总是优于k个最佳标量量化器。在相同的编码速率下，矢量量化的失真明显比标量量化的失真小；而在相同的失真条件下，矢量量化所需的码速率比标量量化所需的码速率低得多。由于矢量量化的复杂度随矢量维数成指数形式增加，故矢量量化的复杂度比标量量化的复杂度高。,标量量化和矢量量化比较,.,二、矢量量化在语音通信中的应用,通信系统中有两个完全相同的码本，一个在编码器（发送端），另一个在解码器（接收端）。每个码本包含J个码字Yj,每个码字是一个K维矢量。VQ编码器的运行原理是根据输入矢量Xi从编码器码本中选择一个与之失真误差最小的码字Yj，输出就是该码字的下标j，是一个数字，因而可以通过任何数字信道传输或任何数字存储器来存储。,.,特征矢量形成,语音信号帧,Xi,VQ编码器,传输或存储,j,VQ译码器,j,Yj,矢量量化在语音通信中的应用,.,如在编码速率为2.4kbit/s的LPC声码器中，将每帧的10个预测系数加以10维的矢量量化，编码速率降低到800bit/s，而语音质量没有下降。,.,特点：传输存储的不是矢量本身而是其序号，所以据有高保密性能收发两端没有反馈回路，因此比较稳定矢量量化器的关键是编码器的设计，译码器只是简单的的查表过程。,.,三、矢量量化在语音识别中的应用,先对系统中的每个字，做一个码本作为该字的参考（标准）模板,共有M个字，故共有M个码本，组成一个模板库。识别时，对于任意输入的语音特征矢量序列XX1,X2,XN，计算该序列中每一个特征矢量对模板库中的每个码本的总平均失真量误差，找出最小的失真误差对应的码本（代表一个字），将对应的字输出作为识别的结果。,.,特征矢量序列XX1,X2,XN模板库Y1,Y2,YM,特征矢量序列形成,任意语音,X,码本Y1Y2YM,计算失真误差判决,输出结果Yi,每一个字做一个码本，共M个字,模板库,.,四、矢量量化的关键之处,1.码本设计。关键在于如何划分J个区域边界。这需要大量的输入信号矢量，经过统计实验才能确定，这个过程称为“训练”或“学习”。,应用聚类算法，按照一定的失真度准则（失真测度），对训练的数据进行分类，从而把训练数据在多维空间中划分成一个以码字为中心的胞腔，常用的是LBG算法来实现。,.,2.码字搜索。未知矢量的量化。按照选定的失真度准则（失真测度），把未知矢量，量化为失真度最小的码字。失真测度就是两矢量之间的距离。,.,4.3矢量量化的失真测度,一、失真测度的定义二、欧式距离测度三、线性预测失真测度四、识别失真测度,.,一、失真测度的定义,失真测度（距离测度）就是将输入矢量Xi用码本重构矢量Yj来表征时所产生的误差或失真的度量方法，它可以描述两个或多个模型矢量之间的相似程度。常用的失真测度为欧氏距离测度、加权欧氏距离测度和识别失真测度。,.,失真测度的选择:1必须在主观评价上有意义,即小的失真对应好的主观评价质量.2必须在数学上易于处理,能实现实际的系统设计.3必须可计算,并保证平均失真D存在.,.,二、欧式距离测度,K维特征矢量：Xixi1,xi2,xiKYjyj1,yj2,yjK,1.均方误差欧式距离,.,2.绝对值平均误差,3.加权欧氏距离测度,.,绝对值平均误差:d1(x,y)(0+1+0+0+1+1+1+0+0)/9=4/9,.,优点：简单、易于处理和计算，且主观评价上有意义。,缺点:欧式距离测度不能应用于线性预测系数构成的矢量。,.,三、线性预测失真测度,当语音信号特征矢量是使用线性预测方法求出的LPC系数时，不宜直接用欧氏距离,因为仅由预测器系数的差值不能完全表征这两个语音信息的差别。应该直接用预测系数所描述的信号模型的功率谱来进行比较。,.,当预测器的阶数，信号与模型完全匹配时，信号功率谱为：,信号的功率谱,预测误差能量,预测逆滤波器的频率响应,Itakura-Saito（板仓-斋藤）距离，即I-S距离,.,相应的，设码书中某重构矢量的功率谱为,则定义Itakura-Saito距离为,.,R是输入语音信号的(p1)（p+1）自相关矩阵,输入语音信号的预测系数矢量,码字预测系数矢量,码书重构矢量预测误差功率,.,这种失真测度是针对线性预测模型、用最大似然准则推导出来，所以特别适用于LPC参数，描述语音信号的情况，常用于LPC编码中。由此又推导出两种线性预测失真测度，他们比I-S距离具有更好的性能，即对数似然比失真测度和模型失真测度。,注：这两种失真测度都仅仅比较两矢量的功率谱，而没有考虑其他能量信息。,.,1.对数似然比失真测度,R是输入语音信号的(p1)（p+1）自相关矩阵,输入语音信号的预测系数矢量,码字预测系数矢量,.,.,2.模型失真测度,R是输入语音信号的(p+1)（p+1）自相关矩阵,输入语音信号的预测系数矢量,码字预测系数矢量,.,四、识别失真测度,加权因子,输入信号矢量的归一化能量,码书重构矢量的归一化能量,对数似然比失真测度,.,当两矢量的能量接近时（即），忽略能量差异引起的影响；当两矢量能量相差很大时，即进行线性加权；而当能量差超过门限时，则为固定值。,.,4.4矢量量化的最佳码本设计,一、最佳码本设计的原则二、LBG算法三、码字搜索,.,矢量量化的关键技术,码本设计码字搜索,.,.,.,.,.,.,x,训练集合X,M训练矢量,.,.,.,.,.,.,.,码本C,y1,y2,yN,N个码字,.,.,.,.,.,.,.,x,d(x,y1),d(x,y0),d(x,yN-1),mind(x,yj),码本C,y0,y1,yN-1,在矢量量化编码中，关键是码本的建立（划分区间）和码字搜索算法（确定量化矢量）。,.,码本的生成算法有两种类型：一种是已知信源分布特性的设计算法；另一种是未知信源分布，但已知信源的一列具有代表性且足够长的样点集合（即训练序列）的设计算法。可以证明，当信源是矢量平衡且遍历时，若训练序列充分长则两种算法是等价的。,.,所谓最佳设计，就是从大量信号样本中训练出好的码本；从实际效果出发寻找到好的失真测度定义公式；用最少的搜索和计算失真的运算量,来实现最大可能的平均信噪比。,一、最佳码本设计的原则,.,最佳码本的设计，就是在一定条件下，使得失真测度d(X,Y)的统计平均最小。需满足下列条件：（1）Voronoi分割条件(最邻近准则NearestNeighborRule):,对信号空间的分割应满足,根据该条件对信号空间进行最佳划分，得到Sl称为一个胞腔。,.,所有选择码字Yl的输入矢量X的集合为Sl，Yl是Sl中所有矢量的质心。根据这两条原则，这个算法就是LBG算法。,（2）Centroid质心条件,子空间分割固定后，Voronoi胞元的质心就是量化器的码字,.,对于一般的失真测度和信源分布，很难找到质心的计算方法，但对于一般的分布和常用的均方失真测度，可以证明,Nl为集合中矢量的个数,.,x,x,x,x,x,x,x,x,x,x,x,.,质心的形成,.,LBG算法是一种递推算法，从一个事先选定的初始码本开始迭代。把训练序列按照码本中的元素根据最邻近准则分组，对每一分组找质心，得到新的码本，又作为初始码本，再进行分组，重复上述过程，直到系统性能满足要求和不再有明显的改进为止。,二、LBG算法,.,初始码本的选择,1随机选取法：从训练序列中随机选取J个矢量作为初始码字，从而构成初始码本。,.,.,.,.,.,.,x,.,.,.,.,训练集合X,初始码本J=2个码字,.,（1）求出S中全体训练序列的质心（2）然后在S中找一个与此质心的失真测度最大的矢量，再在S中找一个与的失真测度最大的矢量（3）以和为基准，根据最邻近准则，进行S的划分，得到两个子集和，求其质心；（4）对这两个子集分别按同样方法进行处理，可以得到四个子集。依次类推，经过r次分裂，得到J=2r个子集，分别求子集的质心，得到J个初始码字，构成初始码本。,2分裂法,.,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,质心,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,分裂1次，得到2个码字,J=22个码字的初始码本构成,S,.,该方法用若干个低维数的码书作为乘积码，求得所需的高维数的码书。如要设计一个高维数的码书，可以简单地用2个低维数的码书做乘积来获得。即用维数为k1，大小为M1的码书乘以维数为k-k1，大小为M2的码书，得到一个k维码书，其大小为M=M1*M2。例如：要设计一个维数k=8，大小为M=256的初始码书，可以由2个小码书相乘得到，其中一个维数为6，大小为16，另一个维数为2，码书大小为16。,3乘积码书法,.,第一步：初始化。给定全部参考矢量集合S，设定失真控制门限,初始码本，设置总失真，初始迭代次数m=1，最大迭代次数为L。,最佳码本的设计,.,第二步：迭代。（1）根据最邻近准则将S分成J个子集，（2）计算总失真,.,（3）计算新码字：每一个码字为其对应子集的质心。（4）计算相对失真改进量，与失真控制门限比较，转入（5）；转入（6）。（5）若m大于L，则转入(6)，否则m+1，转入(1)（6）得到最终的码书,.,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,S,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,J=4,m=1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,新码字,if,m+1=2重新开始,.,新码字,if,m+1=3重新开始,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,.,.,.,矢量量化系统中码本的形成是一个优化问题，即通过迭代运算使得系统的目标函数对全部训练矢量而言的平均量化误差达到最小值.但是这个目标函数在J个码字矢量构成的状态空间中是一个非凸函数，它有许多局部极小值，其中只有一个是优化目标所要达到的全局最小值.由于LBG算法是一种最陡下降算法,所以其迭代结果使目标函数落入哪个极小值只能取决于码字矢量的初值,这就很难保证该算法给出的结果达到目标函数的全局极小值.解决这个问题的方法是码本设计的优化.最佳码本的设计方法之一：遗传算法(GeneticAlgorithm,GA）是借鉴生物界自然选择和自然遗传机制的随机化搜索算法。,.,三、码字搜索,1.全搜索2.快速搜索算法（二叉树形搜索）,.,.,码字搜索算法,码字搜索是矢量量化中的一个最基本问题，矢量量化过程本身实际上就是一个搜索过程，即搜索出与输入最为匹配的码矢。,.,矢量量化中最常用的搜索方法是全搜索算法和树搜索算法。全搜索算法与码本生成算法是基本相同的，在给定速率下其复杂度随矢量维数K以指数形式增长，全搜索矢量量化器性能好但设备较复杂。树搜索算法又有二叉树和多叉树之分，它们的原理是相同的，但后者的计算量和存储量都比前者大，性能比前者好。树搜索的过程是逐步求近似的过程，中间的码字是起指引路线的作用，其复杂度比全搜索算法显著减少，搜索速度较快。由于树搜索并不是从整个码本中寻找最小失真的码字，因此它的量化器并不是最佳的，其量化信噪比低于全搜索。,.,一般矢量量化系统在进行矢量量化时,需要计算码本中每一个码字矢量与输入矢量之间的失真,通过比较找出最小失真作为输入矢量与码本的失真,或者通过找最小失真确定输入矢量的重构矢量.随着码本和码字维数的增大,完成一次全搜索的计算量也变大,实时性变差.例如：码书中有M个码字，码字与输入矢量的维数是k，那么完成一次全搜索的计算量是：乘法运算kM，加法运算（2k-1）M次，比较运算（M-1）次。,1、全搜索VQ,.,时间复杂度:M(2k-1)次加法,kM次乘法和M-1次比较（每个输入矢量）如何降低复杂度:采用约束结构;采用快速码字搜索算法,最近邻搜索,索引,码书,输入矢量,.,.,.,.,.,.,.,y1,y2,yN,x,d(x,y2),d(x,y1),码书C,d(x,yN),mind(x