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

1、2021/8/141 第四章 矢量量化技术 (Vector Quantization VQ)(Vector Quantization VQ)4.1 概述 4.2 矢量量化的基本原理4.3 矢量量化的失真测度4.4 矢量量化的最佳码本设计4.5 矢量量化系统2021/8/1424.1 概述一、矢量量化的应用二、标量量化和矢量量化的区别2021/8/143v矢量量化（矢量量化（VQVQ，即，即Vector QuantizationVector Quantization）是一种是一种极其重要的信号压缩方法。极其重要的信号压缩方法。VQVQ在语音信号处理中占在语音信号处理中占十分重要的地位。广泛应用于

2、语音编码、语音识别十分重要的地位。广泛应用于语音编码、语音识别和语音合成等领域。和语音合成等领域。v量化分为两类：量化分为两类： * * 标量量化标量量化：将取样后的信号值逐个地进行量化。：将取样后的信号值逐个地进行量化。 * * 矢量量化矢量量化：将若干取样信号分成一组，即构成一：将若干取样信号分成一组，即构成一个矢量，然后对此矢量一次进行量化。个矢量，然后对此矢量一次进行量化。v凡是要用量化的地方都可以采用矢量量化凡是要用量化的地方都可以采用矢量量化。2021/8/144 矢量量化技术技术是一种数据压缩和编码技术，矢量量化技术技术是一种数据压缩和编码技术，矢量量化压缩技术的应用领域非常广阔

3、，如军事部门矢量量化压缩技术的应用领域非常广阔，如军事部门和气象部门的卫星和气象部门的卫星( (或航天飞机或航天飞机) )遥感照片的压缩编码遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储与传输、数和实时传输、雷达图像和军用地图的存储与传输、数字电视和字电视和DVDDVD的视频压缩、医学图像的压缩与存储、的视频压缩、医学图像的压缩与存储、网络化测试数据的压缩和传输、语音编码、图像识别网络化测试数据的压缩和传输、语音编码、图像识别和语音识别等等和语音识别等等 。一、矢量量化的应用2021/8/145 v矢量量化是实现矢量量化是实现数据压缩数据压缩的一种有效方法，早在的一种有效方法，早在50

4、50和和6060年代就被用于语音压缩编码。直到年代就被用于语音压缩编码。直到7070年代线性年代线性预测技术被引入语音编码后，矢量量化技术才活跃预测技术被引入语音编码后，矢量量化技术才活跃起来。起来。8080年代初，矢量量化技术的理论和应用研究年代初，矢量量化技术的理论和应用研究得到迅速发展。得到迅速发展。v采用矢量量化技术对信号波形或参数进行压缩处理，采用矢量量化技术对信号波形或参数进行压缩处理，可以获得很好的效益，使存储要求、传输比特率需可以获得很好的效益，使存储要求、传输比特率需求或计算量需求降低求或计算量需求降低. .2021/8/146 整个动态范围被分成若干个小区间，每个小区间整个

5、动态范围被分成若干个小区间，每个小区间有一个代表值，量化时落入小区间的信号值就用这个有一个代表值，量化时落入小区间的信号值就用这个代表值代替，或者叫被量化为这个代表值。这时的信代表值代替，或者叫被量化为这个代表值。这时的信号量是一维的，所以称为标量量化。号量是一维的，所以称为标量量化。二、标量量化和矢量量化的区别采样采样量化量化x xa a(t)(t)x xa a(nT)(nT)x(n)x(n)x xa1a1x x1 1x xk kx xakakx xak+1ak+1x xk+1k+1x xL Lx xaLaLx xaL+1aL+1x(n)=Qxx(n)=Qxa a(nT)(nT)。 1.标量

6、量化：2021/8/1472 2 - - -2-2 2 2 标量量化标量量化2021/8/1482. 矢量量化： 若干个标量数据组成一个矢量，若干个标量数据组成一个矢量，矢量量化是矢量量化是对矢量进行量化，和标量量化一样，它把矢量空间对矢量进行量化，和标量量化一样，它把矢量空间分成若干个小区域，每个小区域寻找一个代表矢量，分成若干个小区域，每个小区域寻找一个代表矢量，量化时落入小区域的矢量就用这个代表矢量代替，量化时落入小区域的矢量就用这个代表矢量代替，或者叫被量化为这个代表矢量。例如，所有可能的或者叫被量化为这个代表矢量。例如，所有可能的二维矢量就构成了一个平面，将平面分成二维矢量就构成了一

7、个平面，将平面分成7 7个小区个小区域。域。 2021/8/149Y Y1 1Y Y2 2Y Y3 3Y Y4 4Y Y5 5Y Y6 6Y Y7 7x1x2Y Yi i（x x1i 1i ,x,x2i2i）代表矢量代表矢量2021/8/1410采用矢量量化的效果优于标量量化的原因？采用矢量量化的效果优于标量量化的原因？ 矢量量化能有效的应用矢量中各分量之间的矢量量化能有效的应用矢量中各分量之间的四种相互关联性质来消除数据中的冗余度。这四种相互关联性质来消除数据中的冗余度。这四种相互关联的性质是线性依赖四种相互关联的性质是线性依赖( (相关性相关性) )、非、非线性依赖线性依赖( (统计不独立

8、统计不独立) )、概率密度函数的形状、概率密度函数的形状和矢量量化的维数，而标量量化仅能利用线性和矢量量化的维数，而标量量化仅能利用线性依赖和概率密度函数的形状来消除冗余度。依赖和概率密度函数的形状来消除冗余度。2021/8/1411 假设声道滤波器传输函数用假设声道滤波器传输函数用4 4个系数来描述，个系数来描述，又假设声道只能为又假设声道只能为4 4个可能的形状之一。这意味着个可能的形状之一。这意味着只存在只存在4 4组可能的声道滤波器传输函数。组可能的声道滤波器传输函数。 现在考虑对每一个滤波器系数单独进行标量量现在考虑对每一个滤波器系数单独进行标量量化，需要化，需要2bit2bit，每

9、一分析帧需要，每一分析帧需要8 8个比特来进行编个比特来进行编码。码。3、标量量化与矢量量化的区别、标量量化与矢量量化的区别2021/8/1412 如果我们知道只有如果我们知道只有4 4种可能的声道形状，与种可能的声道形状，与4 4个可能的声道滤波器系数组成的矢量相对应，在个可能的声道滤波器系数组成的矢量相对应，在这种情况下，一个分析帧，只需要这种情况下，一个分析帧，只需要2bits2bits对对4 4个滤个滤波器系数进行编码，这样降低了所需的比特数。波器系数进行编码，这样降低了所需的比特数。矢量量化就是利用数据之间的相关性来降低所需矢量量化就是利用数据之间的相关性来降低所需的比特率。的比特率

10、。第一种声道滤波器系数第一种声道滤波器系数第二种声道滤波器系数第二种声道滤波器系数第三种声道滤波器系数第三种声道滤波器系数第四种声道滤波器系数第四种声道滤波器系数2021/8/14134.2 矢量量化的基本原理一、一、矢量量化的基本原理矢量量化的基本原理二、矢量量化在语音通信中的应用二、矢量量化在语音通信中的应用三、矢量量化在语音识别中的应用三、矢量量化在语音识别中的应用四、四、矢量量化的关键之处矢量量化的关键之处2021/8/14141.1.矢量的定义一、矢量量化的基本原理 若干个标量数据组成一个矢量，标量的个数就为若干个标量数据组成一个矢量，标量的个数就为矢量的维数。如语音信号某一帧中提取

11、的声道参数，矢量的维数。如语音信号某一帧中提取的声道参数，共共K K个个,X,Xi i=a=ai1i1,a,ai2i2,a,aiKiK 。则。则X Xi i是一个是一个K K维矢量。设维矢量。设共有共有N N个个K K维矢量维矢量X=XX=X1 1,X,X2 2,X,XN N,其中第其中第i i个矢量为个矢量为X Xi i，i=1,2,Ni=1,2,N。以此类推，。以此类推，N N个语音帧，每帧中共有个语音帧，每帧中共有K K个个声道参数，共组成声道参数，共组成N N个个K K维矢量。维矢量。a a1111,a,a1212,a,a1K1Ka aN1N1,a,aN2N2,a,aNKNK第第1 1

12、帧帧第第N N帧帧2021/8/1415X X1 1=a=a1111,a,a1212,a,a1K1KX X2 2=a=a2121,a,a2222,.,a,.,a2k2kX XN N=a=aN1N1,a,aN2N2,.,a,.,aNkNkN个矢量，每个矢量的维数为个矢量，每个矢量的维数为K2021/8/1416 所有所有K K维矢量构成了一个空间为维矢量构成了一个空间为R RK K，无遗漏地划，无遗漏地划分成分成J J个互不相交的子空间个互不相交的子空间R R1 1,R,R2 2RRJ J , ,将将R Rj j称为胞腔。称为胞腔。在每一个子空间在每一个子空间R Rj j找一代表矢量找一代表矢量

13、Y Yj j，则，则J J个代表矢量个代表矢量可以组成的矢量集为：可以组成的矢量集为： Y=YY=Y1 1,Y,Y2 2,Y,YJ J 构成了一个矢量量化器，构成了一个矢量量化器，Y Y叫做叫做码本，码本，J J称为码本长度称为码本长度, Y, Yj j称为码字，有：称为码字，有：Y Yj j=y=yj1j1,y,yj2j2,y,yjKjK ，j=1,2,Jj=1,2,J。2.2.矢量空间的划分2021/8/1417举例 以以K=2K=2为例来说明。当为例来说明。当K=2K=2时，所得到的是二维时，所得到的是二维矢量。所有可能的二维矢量就构成了一个平面。第矢量。所有可能的二维矢量就构成了一个平

14、面。第i i个二维矢量记为：个二维矢量记为： X Xi i=x=xi1i1,x,xi2i2 。先把这个平面。先把这个平面划分成划分成J J块互不相交的子区域，从每个子区域中找块互不相交的子区域，从每个子区域中找出一个代表矢量。如出一个代表矢量。如J=7J=7。2021/8/1418Y Y1 1Y Y2 2Y Y3 3Y Y4 4Y Y5 5Y Y6 6Y Y7 7x1x2码本码本 Y=YY=Y1 1,Y,Y2 2,Y,YJ J 码本长度码本长度 J=7J=7码字码字 Y Yj j=x=xj1j1,x,xj2j2 ，j=1,2,Jj=1,2,J2021/8/1419 维数为维数为k k，码本长度

15、为，码本长度为J J的矢量量化器的矢量量化器Q Q定义：定义：从从k k维欧几里德空间维欧几里德空间R Rk k到一包含到一包含N N个输出个输出( (重构重构) )点点的有限集合的有限集合C C的映射，的映射， Q Q：R Rk kCC，其中，其中C=yC=y1 1 ,y ,y2 2 , ,y, ,yJ J y yi i R Rk k，i i1,J1,J 集合集合C C称作称作码本或码书码本或码书，码本长度码本长度为为J J 。 码本的码本的J J个元素称作个元素称作码字码字或码矢量，它们均或码矢量，它们均为为R Rk k中的矢量，中的矢量，K K维矢量。维矢量。 矢量量化器定义：矢量量化器

16、定义：2021/8/1420 当给矢量量化器输入一个任意矢量当给矢量量化器输入一个任意矢量X Xi i进行矢量进行矢量量化时，矢量量化器首先判断它属于哪个子空间，量化时，矢量量化器首先判断它属于哪个子空间，然后输出该子空间的代表矢量然后输出该子空间的代表矢量Y Yj j。矢量量化过程就。矢量量化过程就是用是用Y Yj j代替代替X Xi i的过程。的过程。 Y Yj jQ(XQ(Xi i) 1) 1 j j J 1J 1 i i N N3.3.矢量量化的过程矢量矢量量化器量化器X Xi iY Yj j2021/8/1421 当给矢量量化器输入一个任意矢量当给矢量量化器输入一个任意矢量X Xi

17、i进行矢进行矢量量化时，矢量量化器首先判断它属于哪个子空量量化时，矢量量化器首先判断它属于哪个子空间，如何判断就是要依据一定的规则，选择一个间，如何判断就是要依据一定的规则，选择一个合适的失真测度，分别计算每个码字代替合适的失真测度，分别计算每个码字代替X Xi i所带所带来的失真，当确定产生最小失真的那个码字来的失真，当确定产生最小失真的那个码字Y Yj j时，时，就将就将X Xi i量化成量化成Y Yj j， Y Yj j就是就是X Xi i的重构矢量（和恢复的重构矢量（和恢复矢量）。矢量）。4.判断规则2021/8/1422X Xi i=a=ai1i1,a,ai2i2,a,aiKiK Y

18、 Y2 2Y Y1 1= y y1111,y,y1212,y,y1K1K Y Y2 2= y y2121,y,y2222,y,y2K2K Y YJ J= y yJ1J1,y,yJ2J2,y,yJKJK 矢量量化器矢量量化器（码本）（码本）最小失真最小失真计算失真计算失真2021/8/1423x4矢量量化矢量量化3 3231322 21343411 134 码书码书码字码字c0码字码字c1码字码字c2码字码字c3索引索引00d(x,c0)=5d(x,c1)=11d(x,c2)=8d(x,c3)=8x412)(),(iiicxCXd2021/8/1424图像编码例子：图像编码例子：原图象块（原图象

19、块（4灰度级）灰度级） x 0 1 2 3码书码书C y0, y1 , y2, y3 y0 y1 y2 y3d(x,y0)=25d(x,y1)=5d(x,y2)=25d(x,y3)=46码字码字y1最接近输入矢量图象块最接近输入矢量图象块 x，故用索引，故用索引“01”编码编码2021/8/1425标量量化是维数为标量量化是维数为k=1的矢量量化。一般矢量量化均的矢量量化。一般矢量量化均指指k1多维量化。多维量化。一个一个k维最佳矢量量化器的性能总是优于维最佳矢量量化器的性能总是优于k个最佳标量个最佳标量量化器。量化器。在相同的编码速率下，矢量量化的失真明显比标量量在相同的编码速率下，矢量量化

20、的失真明显比标量量化的失真小；而在相同的失真条件下，矢量量化所需化的失真小；而在相同的失真条件下，矢量量化所需的码速率比标量量化所需的码速率低得多。的码速率比标量量化所需的码速率低得多。由于矢量量化的复杂度随矢量维数成指数形式增加，由于矢量量化的复杂度随矢量维数成指数形式增加，故矢量量化的复杂度比标量量化的复杂度高故矢量量化的复杂度比标量量化的复杂度高。 标量量化和矢量量化比较标量量化和矢量量化比较2021/8/1426二、矢量量化在语音通信中的应用 通信系统中有通信系统中有两个完全相同的码本两个完全相同的码本，一个在编码，一个在编码器（发送端），另一个在解码器（接收端）。每个码器（发送端），

21、另一个在解码器（接收端）。每个码本包含本包含J J个码字个码字Y Yj j, ,每个码字是一个每个码字是一个K K维矢量。维矢量。VQVQ编码器编码器的运行原理是根据输入矢量的运行原理是根据输入矢量X Xi i从编码器码本中选择一从编码器码本中选择一个与之失真误差最小的码字个与之失真误差最小的码字Y Yj j ，输出就是该码字的下，输出就是该码字的下标标j j，是一个数字，因而可以通过任何数字信道传输，是一个数字，因而可以通过任何数字信道传输或任何数字存储器来存储。或任何数字存储器来存储。2021/8/1427特征特征矢量矢量形成形成语音语音信号信号帧帧Xi码本码本Y1Y2YJVQ编码编码器器

22、传输传输或或存储存储jVQ译码译码器器jYj码本码本Y1Y2YJ矢量量化在语音通信中的应用矢量量化在语音通信中的应用2021/8/1428如在编码速率为如在编码速率为2.4kbit/s的的LPC声码器中，将每声码器中，将每帧的帧的10个预测系数加以个预测系数加以10维的矢量量化，编码速维的矢量量化，编码速率降低到率降低到800bit/s，而语音质量没有下降。，而语音质量没有下降。2021/8/1429特点：特点：传输存储的不是矢量本身而是其序号，所以传输存储的不是矢量本身而是其序号，所以据有高保密性能据有高保密性能收发两端没有反馈回路，因此比较稳定收发两端没有反馈回路，因此比较稳定矢量量化器的

23、关键是编码器的设计，译码器矢量量化器的关键是编码器的设计，译码器只是简单的的查表过程。只是简单的的查表过程。2021/8/1430三、矢量量化在语音识别中的应用 先对系统中的每个字，做一个码本作为该字先对系统中的每个字，做一个码本作为该字的参考（标准）模板的参考（标准）模板, ,共有共有M M个字，故共有个字，故共有M M个码个码本，组成一个模板库。本，组成一个模板库。 识别时，对于任意输入的语音特征矢量序列识别时，对于任意输入的语音特征矢量序列X XX1 , X2 , , XNX1 , X2 , , XN，计算该序列中每一个，计算该序列中每一个特征矢量对模板库中的每个码本的总平均失真量特征矢

24、量对模板库中的每个码本的总平均失真量误差，找出最小的失真误差对应的码本（代表一误差，找出最小的失真误差对应的码本（代表一个字），将对应的字输出作为识别的结果。个字），将对应的字输出作为识别的结果。2021/8/1431特征矢量序列特征矢量序列 X XXX1 1 , X, X2 2 , , X, , XN N 模板库模板库 Y Y1 1 , Y, Y2 2 , , Y, , YM M特征矢量特征矢量序列形成序列形成任意任意语音语音X X码本码本Y Y1 1Y Y2 2Y YM M计算计算失真误差失真误差判决判决输出结果输出结果Y Yi i 每一个字做一每一个字做一个码本，共个码本，共M M个字个

25、字模板库模板库2021/8/1432四、矢量量化的关键之处 1. 1. 码本设计。关键在于如何划分码本设计。关键在于如何划分J J个区域边个区域边界。这需要大量的输入信号矢量，经过统计实验界。这需要大量的输入信号矢量，经过统计实验才能确定，这个过程称为才能确定，这个过程称为“训练训练”或或“学习学习”。 应用聚类算法，按照一定的应用聚类算法，按照一定的失真度准则失真度准则（失真测度），对训练的数据进行对训练的数据进行分类分类，从而把训，从而把训练数据在多维空间中划分成一个以码字为中心的练数据在多维空间中划分成一个以码字为中心的胞腔，常用的是胞腔，常用的是LBGLBG算法来实现。算法来实现。20

26、21/8/1433 2. 2. 码字搜索。未知矢量的量化。按照选定的码字搜索。未知矢量的量化。按照选定的失真度准则（失真度准则（失真测度），），把未知矢量，量化把未知矢量，量化为失真度最小的码字。为失真度最小的码字。 失真测度就是两矢量之间的距离。失真测度就是两矢量之间的距离。2021/8/14344.3 矢量量化的失真测度一、失真测度的定义二、欧式距离测度三、线性预测失真测度四、识别失真测度2021/8/1435一、失真测度的定义 失真测度（距离测度）就是将输入矢量失真测度（距离测度）就是将输入矢量X Xi i用码本用码本重构矢量重构矢量Y Yj j来表征时所产生的来表征时所产生的误差或失真

27、的度量方法误差或失真的度量方法，它可以描述两个或多个模型矢量之间的相似程度。它可以描述两个或多个模型矢量之间的相似程度。常用的失真测度为欧氏距离测度、加权欧氏距离测常用的失真测度为欧氏距离测度、加权欧氏距离测度和识别失真测度。度和识别失真测度。2021/8/1436失真测度的选择失真测度的选择:1 1 必须在主观评价上有意义必须在主观评价上有意义, ,即小的失真对应好的主观即小的失真对应好的主观评价质量评价质量. .2 2 必须在数学上易于处理必须在数学上易于处理, ,能实现实际的系统设计能实现实际的系统设计. .3 3 必须可计算必须可计算, ,并保证平均失真并保证平均失真D D存在存在.

28、.2021/8/1437二、欧式距离测度K K维特征矢量：维特征矢量： X Xi ixxi1 i1 , x, xi2 i2 , , x, , xiKiK Y Yj jyyj1 j1 , y, yj2 j2 , , y, , yjKjK KiiiyxKYXd122)(1),(1.1.均方误差欧式距离均方误差欧式距离2021/8/1438KiiiyxKYXd11|1),(2.2.绝对值平均误差绝对值平均误差3.3.加权欧氏距离测度加权欧氏距离测度211(,)( )()Kiiid X Yw ixyK2021/8/1439码字码字(K=9,Y)(K=9,Y)123456789输入特输入特征矢量征矢量(

29、k=9,X)(k=9,X)133467889绝对值平均误差绝对值平均误差: :d d1 1(x,y)(x,y)(0+1+0+0+1+1+1+0+0)/9=4/9(0+1+0+0+1+1+1+0+0)/9=4/92021/8/1440优点：优点：简单、易于处理和计算，且主简单、易于处理和计算，且主观评价上有意义。观评价上有意义。缺点缺点:欧式距离测度不能应用于线性预欧式距离测度不能应用于线性预测系数构成的矢量。测系数构成的矢量。2021/8/1441三、线性预测失真测度 当语音信号特征矢量是使用线性预测方法求当语音信号特征矢量是使用线性预测方法求出的出的LPCLPC系数时，不宜直接用欧氏距离系数

30、时，不宜直接用欧氏距离, ,因为仅因为仅由预测器系数的差值不能完全表征这两个语音由预测器系数的差值不能完全表征这两个语音信息的差别。应该直接用预测系数所描述的信信息的差别。应该直接用预测系数所描述的信号模型的功率谱来进行比较。号模型的功率谱来进行比较。2021/8/1442222)()()(jpjeAeXf 当预测器的阶数当预测器的阶数 ，信号与模型，信号与模型完全匹配时，信号功率谱为：完全匹配时，信号功率谱为： p信号的功率谱信号的功率谱预测误差能量预测误差能量预测逆滤波器的频率响应预测逆滤波器的频率响应Itakura-Saito（板仓（板仓-斋藤）距离，即斋藤）距离，即I-S距离距离202

31、1/8/1443222)()()( jpjeAeXf 12ln),(aRaffdTIS相应的，设码书中某重构矢量的功率谱为相应的，设码书中某重构矢量的功率谱为则定义则定义Itakura-Saito距离为距离为2021/8/1444R R是输入语音信号的是输入语音信号的(p(p1)1)（p+1p+1）自相关矩）自相关矩阵阵,., 121pTaaaa输入语音信号的预测系数矢量输入语音信号的预测系数矢量,., 1)(21pTaaaa码字预测系数矢量码字预测系数矢量12ln),(aRaffdTIS2p码书重构矢量预测误差功率码书重构矢量预测误差功率2021/8/1445 这种失真测度是针对线性预测模型

32、、用最大似然准则推导出来，所以特别适用于LPC参数，描述语音信号的情况，常用于LPC编码中。由此又推导出两种线性预测失真测度，他们比I-S距离具有更好的性能，即对数似然比失真测度和模型失真测度。 注：这两种失真测度都仅仅比较两矢量的功率谱，而没有考虑其他能量信息。2021/8/1446RaaaRaYXdTTLLR)(ln),(1.1.对数似然比失真测度对数似然比失真测度R R是输入语音信号的是输入语音信号的(p(p1)1)（p+1p+1）自相关矩）自相关矩阵阵,., 121pTaaaa输入语音信号的预输入语音信号的预测系数矢量测系数矢量,., 1)(21pTaaaa码字预测系数矢量码字预测系数

33、矢量2021/8/1447)0()2()()2()0() 1 ()() 1 ()0(nnnnnnnnnRpRpRpRRRpRRRR2021/8/14481)(),(RaaaRaYXdTTM2. 2. 模型失真测度模型失真测度R R是输入语音信号的是输入语音信号的(p+1)(p+1)（p+1p+1）自相关矩阵）自相关矩阵,., 121pTaaaa输入语音信号的预输入语音信号的预测系数矢量测系数矢量,., 1)(21pTaaaa码字预测系数矢量码字预测系数矢量2021/8/1449四、识别失真测度四、识别失真测度)(),(),(EEgffdEfdLLR 加权因子加权因子输入信号矢量的归一化能量输入

34、信号矢量的归一化能量码书重构矢量的码书重构矢量的归一化能量归一化能量 )()()(0)(FFddxxxxxxxxxxg对数似然比失真测度对数似然比失真测度2021/8/1450当两矢量的能量接近时（即当两矢量的能量接近时（即 ），忽略能），忽略能量差异引起的影响；量差异引起的影响；当两矢量能量相差很大时，即进行线性加权；当两矢量能量相差很大时，即进行线性加权；而当能量差超过门限而当能量差超过门限 时，则为固定值。时，则为固定值。dxEE Fx)(),(),(EEgffdEfdLLR 2021/8/14514.4 矢量量化的最佳码本设计一、最佳码本设计的原则二、LBG算法三、码字搜索2021/8

35、/1452矢量量化的关键技术矢量量化的关键技术码本设计码本设计码字搜索码字搜索.x训练集合训练集合XM 训练矢量训练矢量.码本码本Cy1y2yNN 个码字个码字.xd(x,y1)d(x,y0)d(x, yN-1)min d(x,yj)码本码本Cy0y1yN-1在矢量量化编码中，关键是码本的建立（划分区间）和码字搜索算法（确定量化矢量）。2021/8/1453v码本的生成算法有两种类型：码本的生成算法有两种类型： 一种是已知信源分布特性的设计算法；一种是已知信源分布特性的设计算法； 另一种是未知信源分布，但已知信源的一列具另一种是未知信源分布，但已知信源的一列具有代表性且足够长的样点集合（即训练

36、序列）的设有代表性且足够长的样点集合（即训练序列）的设计算法。计算法。 可以证明，当信源是矢量平衡且遍历时，若训可以证明，当信源是矢量平衡且遍历时，若训练序列充分长则两种算法是等价的。练序列充分长则两种算法是等价的。2021/8/1454 所谓最佳设计，就是从大量信号样本中训所谓最佳设计，就是从大量信号样本中训练出好的码本；从实际效果出发寻找到好的失练出好的码本；从实际效果出发寻找到好的失真测度定义公式；用最少的搜索和计算失真的真测度定义公式；用最少的搜索和计算失真的运算量运算量, ,来实现最大可能的平均信噪比。来实现最大可能的平均信噪比。一、最佳码本设计的原则2021/8/1455 最佳码本

37、的设计，就是在一定条件下，使得失真测最佳码本的设计，就是在一定条件下，使得失真测度度d(X,Y)d(X,Y)的统计平均最小。需满足下列条件：的统计平均最小。需满足下列条件： （1 1） VoronoiVoronoi分割条件分割条件( (最邻最邻近近准则准则Nearest Nearest Neighbor Rule):Neighbor Rule):对信号空间的分割应满足对信号空间的分割应满足);,(),(:liYXdYXdRXSilKl根据该条件对信号空间进行最佳划分，得到根据该条件对信号空间进行最佳划分，得到Sl称为称为一个胞腔。一个胞腔。2021/8/1456所有选择码字所有选择码字Y Yl

38、的输入矢量的输入矢量X X的集合为的集合为S Sl， Y Yl是是S Sl中所中所有矢量的质心。有矢量的质心。根据这两条原则，这个算法就是根据这两条原则，这个算法就是LBGLBG算法。算法。JiliYXdYXdRXSilKl, 1,);,(),(:（2）Centroid质心条件质心条件子空间分割固定后，子空间分割固定后，Voronoi胞元的质心就胞元的质心就是量化器的码字是量化器的码字llSYXEYllSYXEY2021/8/1457 对于一般的失真测度和信源分布，很难找到质对于一般的失真测度和信源分布，很难找到质心的计算方法，但对于一般的分布和常用的均方失心的计算方法，但对于一般的分布和常用

39、的均方失真测度，可以证明真测度，可以证明 lSXllXNY1N Nl为集合中矢量的个数为集合中矢量的个数2021/8/1458xxxxxxxxxxxiSKS),(),(:ikKkYXdYXdRXSkYiYkSXkkXNY1iSXiiXNY12021/8/1459质心的形成质心的形成2021/8/1460 LBG LBG算法是一种递推算法，从一个事先选定的算法是一种递推算法，从一个事先选定的初始码本开始迭代。把训练序列按照码本中的元素初始码本开始迭代。把训练序列按照码本中的元素根据最邻近准则分组，对每一分组找质心，得到新根据最邻近准则分组，对每一分组找质心，得到新的码本，又作为初始码本，再进行分

40、组，重复上述的码本，又作为初始码本，再进行分组，重复上述过程，直到系统性能满足要求和不再有明显的改进过程，直到系统性能满足要求和不再有明显的改进为止。为止。二、LBG算法2021/8/1461初始码本的选择初始码本的选择 1 1 随机选取法：从训练序列中随机选取随机选取法：从训练序列中随机选取J J个矢量作个矢量作为初始码字，从而构成初始码本。为初始码字，从而构成初始码本。.x.训练集合训练集合X . .初始码本初始码本J=2J=2个码字个码字2021/8/1462（1 1）求出）求出S S中全体训练序列的质心中全体训练序列的质心（2 2）然后在）然后在S S中找一个与此质心的失真测度最大的中

41、找一个与此质心的失真测度最大的矢量矢量 ，再在再在S S中找一个与中找一个与 的失真测度最大的矢量的失真测度最大的矢量（3 3）以）以 和和 为基准，根据最邻近准则，进行为基准，根据最邻近准则，进行S S的划分，得到两个子集的划分，得到两个子集 和和 ，求其质心；，求其质心；（4 4）对这两个子集分别按同样方法进行处理，可以）对这两个子集分别按同样方法进行处理，可以得到四个子集。依次类推，经过得到四个子集。依次类推，经过r r次分裂，得到次分裂，得到J=2J=2r r 个子集，分别求子集的质心，得到个子集，分别求子集的质心，得到J J个初始码字，构个初始码字，构成初始码本。成初始码本。2 2

42、分裂法分裂法01YiiXYXd),(max01kikXXXd),(maxiXiXkXiSKS2021/8/1463xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx质心质心xxxxxxxxxxxiiXYXd),(max01xxxxxxxxxxxkikXXXd),(maxiSKSkSXkXNY111分裂分裂1 1次，得到次，得到2 2个码字个码字J=2 2J=2 2个码字的初始码本构成个码字的初始码本构成),(),(:ikkXXdXXdSXSSiSXiXNY112SXXNY1012021/8/1464 该方法用若干个低维数的码书作为乘积码，求得所需的该方法用

43、若干个低维数的码书作为乘积码，求得所需的高维数的码书。高维数的码书。 如要设计一个高维数的码书，可以简单地用如要设计一个高维数的码书，可以简单地用2 2个低维数个低维数的码书做乘积来获得。即用维数为的码书做乘积来获得。即用维数为k1k1，大小为，大小为M1M1的码书乘以的码书乘以维数为维数为k-k1k-k1，大小为，大小为M2M2的码书，得到一个的码书，得到一个k k 维码书，其大小维码书，其大小为为M=M1M=M1* *M2M2。 例如：要设计一个维数例如：要设计一个维数k=8k=8，大小为，大小为M=256M=256的初始码书，的初始码书，可以由可以由2 2个小码书相乘得到，其中一个维数为

44、个小码书相乘得到，其中一个维数为6 6，大小为，大小为1616，另一个维数为另一个维数为2 2，码书大小为，码书大小为1616。3 乘积码书法乘积码书法2021/8/1465 第一步：初始化。第一步：初始化。给定全部参考矢量集合给定全部参考矢量集合S S，设定失真控制门限设定失真控制门限 , ,初始码本初始码本 ，设置总失真设置总失真 ，初始迭代次数初始迭代次数m=1m=1，最大迭代次数为，最大迭代次数为L L。 最佳码本的设计最佳码本的设计00201JYYY(0)D2021/8/1466第二步：迭代。第二步：迭代。（1 1）根据最邻近准则将）根据最邻近准则将S S分成分成J J个子集，个子集

45、，（2 2）计算总失真）计算总失真mJmmSSS21JlJiliYXdYXdRXSmimlKml, 1;, 1,);,(),(:11 JlSXmlmmlYXdD11),(2021/8/1467（3 3）计算新码字：每一个码字为其对应子集的质心。）计算新码字：每一个码字为其对应子集的质心。（4 4）计算相对失真改进量，）计算相对失真改进量， 与与失真控制门限比较，失真控制门限比较， 转入（转入（5 5）；）； 转入（转入（6 6）。）。（5 5）若）若m m大于大于L L，则转入，则转入(6)(6)，否则，否则m+1m+1，转入，转入(1)(1)（6 6）得到最终的码书）得到最终的码书mJmmY

46、YY21mlSXlmlXNY1mmmmDDD|1mmmJmmYYY212021/8/1468xxxxxxxxxxxxxxxxxxxxxSxxxxxxxxxxxxxxxxxxxxx14131211SSSSJ=4,m=104030201YYYY4, 2 , 1,);,(),(:001liliYXdYXdRXSilKl 4101),(lSXlmlYXdDxxxxxxxxxxxxxxxxxxxxx新码字新码字14131211YYYY1101|DDD 1ifm+1=2m+1=2重新开始重新开始2021/8/146924232221SSSS4, 2 , 1,);,(),(:112liliYXdYXdRXS

47、ilKl 4122),(lSXlmlYXdD新码字新码字24232221YYYY2212|DDD 2ifm+1=3m+1=3重新开始重新开始14131211YYYYxxxxxxxxxxxxxxxxxxxxxJ=4,m=2xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx2021/8/14702021/8/14712021/8/1472 矢量量化系统中码本的形成是一个优化问题，即通过迭代矢量量化系统中码本的形成是一个优化问题，即通过迭代运算使得系统的目标函数对全部训练矢量而言的平均量化误差运算使得系统的目标函数对全部训练矢量而言的平均量化误差达到最小值达到最小值

48、. .但是这个目标函数在但是这个目标函数在J J个码字矢量构成的状态空间个码字矢量构成的状态空间中是一个非凸函数，它有许多局部极小值，其中只有一个是优中是一个非凸函数，它有许多局部极小值，其中只有一个是优化目标所要达到的全局最小值化目标所要达到的全局最小值. .由于由于LBGLBG算法是一种最陡下降算算法是一种最陡下降算法法, ,所以其迭代结果使目标函数落入哪个极小值只能取决于码字所以其迭代结果使目标函数落入哪个极小值只能取决于码字矢量的初值矢量的初值, ,这就很难保证该算法给出的结果达到目标函数的全这就很难保证该算法给出的结果达到目标函数的全局极小值局极小值. . 解决这个问题的方法是码本设

49、计的优化解决这个问题的方法是码本设计的优化. . 最佳码本的设计方法之一：遗传算法最佳码本的设计方法之一：遗传算法(Genetic (Genetic Algorithm,GAAlgorithm,GA）是借鉴生物界自然选择和自然遗传机制的随机）是借鉴生物界自然选择和自然遗传机制的随机化搜索算法。化搜索算法。2021/8/1473三、码字搜索三、码字搜索1.全搜索全搜索2.快速搜索算法（二叉树形搜索）快速搜索算法（二叉树形搜索）2021/8/14742021/8/1475码字搜索算法码字搜索算法v码字搜索码字搜索是矢量量化中的一个最基本问题，矢量量化过程本身实际上就是一个搜索过程，即搜索出与输入最

50、为匹配的码矢。2021/8/1476v矢量量化中最常用的搜索方法是全搜索算法和树搜索算法。全搜索算法与码本生成算法是基本相同的，在给定速率下其复杂度随矢量维数K以指数形式增长，全搜索矢量量化器性能好但设备较复杂。树搜索算法又有二叉树和多叉树之分，它们的原理是相同的，但后者的计算量和存储量都比前者大，性能比前者好。树搜索的过程是逐步求近似的过程，中间的码字是起指引路线的作用，其复杂度比全搜索算法显著减少，搜索速度较快。由于树搜索并不是从整个码本中寻找最小失真的码字，因此它的量化器并不是最佳的，其量化信噪比低于全搜索。2021/8/1477 一般矢量量化系统在进行矢量量化时一般矢量量化系统在进行矢

51、量量化时, ,需要需要计算码本中每一个码字矢量与输入矢量之间的失计算码本中每一个码字矢量与输入矢量之间的失真真, ,通过比较找出最小失真作为输入矢量与码本通过比较找出最小失真作为输入矢量与码本的失真的失真, ,或者通过找最小失真确定输入矢量的重或者通过找最小失真确定输入矢量的重构矢量构矢量. .随着码本和码字维数的增大随着码本和码字维数的增大, ,完成一次全完成一次全搜索的计算量也变大搜索的计算量也变大, ,实时性变差实时性变差. . 例如：码书中有例如：码书中有 M M 个码字，码字与输入矢个码字，码字与输入矢量的维数是量的维数是k k ，那么完成一次全搜索的计算量是：，那么完成一次全搜索的

52、计算量是：乘法运算乘法运算 kMkM，加法运算，加法运算 （2k-12k-1）M M 次，比较运次，比较运算（算（M-1M-1）次。）次。1、全搜索、全搜索VQ2021/8/1478时间复杂度时间复杂度: M(2k-1)次加法次加法, kM 次乘法和次乘法和M-1 次比次比较（每个输入矢量）较（每个输入矢量）如何降低复杂度如何降低复杂度:采用约束结构采用约束结构; 采用快速码字搜索采用快速码字搜索算法算法最近邻最近邻搜索搜索索引索引码书码书输入输入 矢量矢量.y1y2yNxd(x,y2)d(x,y1)码书码书C d(x, yN)min d(x,yj) d(x,yj)=(x1- yj1)2+ (

53、x2- yj2)2+ +(xk- yjk)2(2k-1)(2k-1)次加法，次加法，k k次乘法次乘法2021/8/14792、二叉树形搜索、二叉树形搜索X先与先与Y0和和Y1比较比较,计算出失真计算出失真d(X, Y0)和和d(X, Y1)，如果，如果后者较小，则走下支路，同时送后者较小，则走下支路，同时送“1”输出；如此类推，输出；如此类推，最后到达，则送出标号最后到达，则送出标号101。输入矢量输入矢量X中间码字中间码字Y1Y0Y00Y01Y10Y11Y000Y001Y010Y011Y100Y101Y110Y111树形搜索可以分为二叉树树形搜索可以分为二叉树和多叉树和多叉树.利用该方法可以利用该方法可以减少运算量减少运算量.如果原来码本尺寸为如果原来码本尺寸为8, 在在二叉树搜索方法中，码本二叉树搜索方法中，码本包含了包含了14个码字个码字.2021/8/1480图中各层的码字，用下面的方法得到：图中各层的码字，用下面的方法得到： 如如J=8，已知码本中，已知码本中8个码字，则按最邻近的原