第三章 第二讲 矢量量化

 矢量量化(Vector Quantization)

一．矢量量化初步

1.基本原理

2.设计码本 (LBG)

3.量化

二．矢量量化进一步

1.矢量量化 (Splitted VQ)

2.多极矢量量化 (Cascaded VQ)

3.树形矢量量化器

4.其它各种类型矢量量化器

三. 几个矢量量化的工程实现问题

1.分级矢量量化中的多路径搜索问题

2.用模拟退火 (Simulated Annealing) 算法训练最佳码本[2]

四. 矢量量化的应用

一．矢量量化初步

1. 基本原理

结论：在信息论中已证明，矢量量化优于标量量化。

❑矢量量化是先将个()个采样值形成维空间中的一个矢量，然后将这个矢量一次进行量化。它可以大大降低数码率。

❑基础是信息论的分支: 率失真(畸变)理论

 对于一定的量化速率R(以每个采样信号平均所用的量化比特数来衡量，bit/采样)，量化失真D(以量化信号与原信号之间的误差均方值和原信号均方值之比来衡量)是一定的。

 矢量量化总是优于标量量化的。这是因为矢量量化有效地应用了矢量中各分量间的四种相互关联的性质：线性依赖性，非线性依赖性，概率密度函数的形状以及矢量维数。

定义：

1)源：若将个信号采样组成的信源序列中每个为一组分为个随机矢量，构成信源空间(在维欧氏空间中)，其中第个矢量可记为，。

2)子空间：把无遗漏地划分成个互不相交的子空间，满足：

3)码本：在每个子空间中找一个代表矢量，令恢复矢量集为：。也叫输出空间、码本或码书(Code Book)，称为码矢(Code Vector)或码字(Code Word)，内矢量的数目，则叫做码本长度。

4)码本搜索：当矢量量化器输入任意矢量时，它首先判断属于那个子空间，然后输出该子空间的代表矢量。矢量量化过程就是用代表，即，  。式中为量化函数。

5)完整系统：VQ编译码的全过程完成一个从维欧氏空间到空间中有限子集的映射：    

。

发端完成映射：

，

收端完成映射：        

，

矢量量化则是和的结合。图1中给出了这种映射关系。

 编码 

 解码 

图1 矢量量化示意图

6)矢量量化的比特率：

 : 每个矢量所需要的编码比特数

 K: 每个矢量所包含的信号样点数

 K=1时, VQ退化成SQ

波形量化

       采样频率为10kHz、振幅量化为16bit的语音信号的传输速率是：      

       16x10000=160,000bit/s(bps)。

     ·波形特征参数量化

       对阶数为10、每秒100个特征矢量（如频谱包络参数），如振幅量化也为16bit

       的话，其传输速率是：16x100x10=16,000bit/s。

波形特征参数矢量量化：设L = 1024（40种语音单位，每个对应25种变形），

       即为了指定码本中任意码矢需要10bit，则对每秒100个特征矢量的传输需率

       就为1,000bit/s。

7)矢量量化的特点：

 压缩能力强。

 一定产生失真, 但失真易控制：X的分类越细，失真越小。

 计算量大：每输入一个，都要和N个逐一比较，搜索出畸变最小的。由于和都是K维矢量，故搜索的矢量运算，工作量大。

 VQ是定长码。

2. 设计码本

1)目的：在VQ中，码本的生成是一个关键。若设计K维N级码本，则要根据M－L失真最小的准则，分别决定如何对进行划分，以得到合适的N个胞腔(Cell)，；以及求出，的代表矢量，。最佳量化就要满足使其平均失真最小，即

2)原则：最佳量化器必须满足

▪分割条件：对的分割应满足 (Voronoi 分割)

▪质心 (Centroid)条件：当子空间分割固定时，Voronoi胞腔的质心就是量化器的码字，即

矢量是胞腔的质心。对于最佳胞腔的分割、最佳质心的计算与畸变的度量准则有关。对于均方误差准则及加权均方误差准则，胞腔的质心：

                表示胞腔中元素的个数，即胞腔中有个X。

矢量量化由码本和划分的条件唯一确定。当码本确定后，分割就可以通过最近邻域准则 (NNR-Nearest Neighbor Rule) 唯一确定。最佳量化器的设计也就是最佳码本的设计。通常采用迭代类聚的方法。

3)训练码本的LBG算法

Linde, Buzo和Gray将标量最优量化的M－L算法推广到了空间LBG算法。图2、图3分别给出已知训练序列和已知信源分布特性的算法流程图。

a)初始化条件：给出

 码本长度N

 初始码本， 

 计算停止门限， 

 初始平均失真

 训练序列

 迭代初值

图2 已知训练序列的算法流程图

b)用码本为已知质心，根据最佳划分原则把训练序列划分为个胞腔，即

其中，。

c)计算平均失真与相对失真

 平均失真: 

其中，是K维输入矢量的量化畸变。

 相对失真: 

 若, 则停止计算，当前码本即是设计好的码本，否则进行

d)生成新码字

 计算这时划分的各胞腔的质心，可由下式计算

：集合中元素的个数

 由这个新质心构成新的码本

 设置 n=n+1

 返回 2) 再进行计算，直到  , 得到所要求的码本为止。

4) 初始码本的生成

LBG算法: 总失真单调下降的算法

要求: 避免陷入局部最小点

方法: 

a) 随机选取法

b) 法

原则

扰乱系数

距离最大原则

c) 综合法(合并法)

5) 失真测度

1)基本定义：失真测度是反映用码字代替信源矢量所付出的代价。这种代价的统计平均值描述了矢量量化器的工作特性，即

2)常用失真测度：

▪平方失真测度：

▪加权平方失真测度：

W：正定加权矩阵。

▪绝对误差失真测度：

▪与被量化矢量信号意义相关的失真测度：

例如反映语音谱包络的预测(LP)矢量，定义频谱失真为，

式中是原始LP能量谱， 是量化后的LP能量谱

▪似然比失真测度

▪板仓-斋田失真测度

3. 矢量量化的量化过程

    全搜索

    码本中有N个码字，每个码字为K维矢量,完成一次搜索的计算代价:(欧氏距离)

    加法: N(2K-1)次

    乘法: NK次

    比较: N-1次

    树形搜索的矢量量化系统

二叉树或多叉树

优点: 降低运算量

缺点: 增加存储量

二．矢量量化进一步

矢量量化 (Splitted VQ) != 树搜索矢量量化器

矢量量化：首先将一个K维矢量成P（P>1）个子矢量，然后对各个子矢量分别进行矢量化。

对于一个实用的VQ系统，例如用 20个比特对10个LSF进行量化。如果用全搜索方案，码本容量将达到*10 (LSF矢量为10维)，无论是从码本的存储容量还是搜索的运算量，在现有的硬件条件下难以实时实现。如果采用矢量量化算法，将10维的LSF矢量为两个5维的矢量，分别用10比特进行VQ，这样，码本容量降为2**5。

由此可见矢量量化可以大大降低了码本的存储量和最佳矢量搜索的计算量。

2．多极矢量量化 (Cascaded VQ)

1) 多级矢量量化器的构造

    多级矢量量化器可以较大幅度的降低矢量量化器的计算复杂度和存贮量。多级矢量量化器由码本大小分别为, ,...,， 的m个小码本构成。图4所示的是m级矢量量化器的编码器原理图。

图4  多级矢量量化器的编码器

    m级矢量量化器的量化原理：第一级矢量量化器是量化原始输入矢量X，在码本1中找到失真最小的码字，并将其下标i编码送到信道中。第二级量化器的输入矢量是：原始输入矢量X与第一级输出矢量之差的误差矢量。在码本2中找到失真最小的码字，并将其下标j1编码送到信道中。第三级量化器的输入矢量是：第二级的输入矢量与第二级的输出矢量之差的误差矢量。同样在码本3中找到失真最小的码字，并将其下标j2编码送到信道中。依此类推，第m级量化器的输入矢量与第(m-1)级的输出矢量之差的误差矢量。在码本m中找到失真最小的码字，并将其下标j(m-1)的编码信号送到信道中。这样，信道中传输的将是i,j1,j2,...,jm等下标的编码信号。

    这m 个小码本，等价于一个码本尺寸为的全搜索矢量量化器的码本，并称此全搜索矢量量化器为与此m级矢量量化器相当的量化器。

2) 多级矢量量化器码本的设计

    多级矢量量化器各级码本设计仍可采用LBG算法，只是训练序列有所不同。下面给出一个m 级矢量量化器的码本设计算法。

 (a) 第一级码本设计     

            设第一级码本大小为，训练序列TS的长度为M（即有M个训练矢量）。采用LBG算法进行计算，得到第一级码本。

(b) 第二及多级码本设计        

            第二级码本仍按LBG算法进行设计。不过它的训练序列是第一级矢量量化器的误差信号，长度仍为M。同样用LBG算法进行类聚、递归，得到第二级码本的个码字。余者类推。

    例如设计一个LSF参数的三级矢量量化器：在实际算法中，采用16万帧以上的训练序列TS进行训练，三级矢量量化，分别是7比特，7比特和6比特。同样用20比特对LSF矢量进行编码，码本容量降为 (++)*10，相对于矢量量化，存储量降低了60%，相应的搜索计算量也大大减少。而合成语音质量与相同比特的矢量量化基本相当。    

多级矢量量化系统无论在减少搜索计算量方面，还是减少码本储存量方面都有可观的改进。

3. 模糊矢量量化

减少码本的量化误差

模糊聚类(Fuzzy Clustering)

模糊k均值聚类，隶属度函数

4．其它各种类型矢量量化器

 全搜索矢量量化器

o节约计算量（稀疏码本 sparsity）

o节约存储量

 固定预测矢量量化器

 乘积码矢量量化器

o增益/

o均值/

 自适应矢量量化器

 自适应预测矢量量化器

三. 几个矢量量化的工程实现问题

1. 分级矢量量化中的多路径搜索问题

在分级矢量量化中，每一级量化过程都是在所定义的最小误差意义下最优的。但多级量化作为一个整体并不一定是最优的。然而要用全路径搜索的方法找出全局最优，运算量巨大。现阶段的硬件无法满足实时运算的要求。所以工程上采用搜索路径数为M的部分路径搜索分级矢量量化。例如：

1)在第一级搜索中找到误差测度最小的M个码字，并保留对应的M个误差矢量。

2)在第二级搜索中分别以这M个误差矢量为输入矢量，分别进行码本搜索。找到并保留M个（输入误差矢量、码字和输出误差矢量）搜索路径，这些路径所对应的误差测度也是最小的。

3)整个分级搜索完成时，就保留了M条完整的从第一级到最后一级的搜索路径。从中挑选一条最终误差测度最小的路径上的码字序列作为分级矢量量化的输出。

以4级，每级码本大小为128，搜索路径数为8为例。共要进行128+8*128*3=3200次误差测度计算，而传统搜索需要128*4=512次误差测度计算。以部分增加计算量为代价从工程上逼近全局最优量化。

2. 用模拟退火 (Simulated Annealing) 算法训练最佳码本[2]

VQ码本的形成也是一个优化问题。就是通过一种迭代预算使对全部训练矢量而言的平均量化畸变（目标函数）达到最小值。但这个目标函数在由M个码字矢量构成的状态空间中是一个非凸函数，它有很多极小值，其中一个是全局最小值，其它都是局部最小值。由于LBG算法中每次迭代目标函数总是下降的，是一种最陡下降算法(Steepest descend Algorithm)。LBG迭代预算的结果是目标函数落入哪一个极小值取决于码本中码字矢量初值的设置。工程上很难保证LBG算法给出的结果达到目标函数的全局最小点。解决这一问题的一种方法，可以形象的表示为，将系统状态通过加扰，从局部最小点拔出来。这种算法称为“随机松弛算法”，简记为SR算法(Stochastic Relaxation)。SR算法中最重要的是一种“模拟退火算法”，简记为SA算法(Simulated Annealing)。SA算法能够从理论上严格证明，在满足一定条件下，保证目标函数收敛到全局最小点的概率为1。以解码器扰动SA算法为例：

1)设系统的状态(码本内容)用S表示，系统的目标函数(平均畸变)用E表示，E是S的函数，记为E(S)。设迭代的节拍为m, m=1,2,3, …。设第m次节拍时系统状态为。设是对机型某种随机扰动后的状态。这种扰动的大小由系统温度T决定。记为第m个节拍时系统的温度。迭代开始时，设置的很高，系统处于“熔融”状态。随着m的增加，逐渐降低，系统逐渐“冷却”。如果降温速度足够慢，系统将进入全局最小点。

2)设置初始码本，将码字随机分布在整个空间中,随机的程度受初始温度控制。

3)利用传统LBG算法，进行划分聚类，求质心，生成新码字的迭代运算，直到平均畸变的变化小于某个阈值。这是E(S)进入某个极小值。相当与金属处于结晶状态。

4)将码本中的每个码字都加上一个随机矢量扰动，扰动的程度受当前温度控制。相当于金属的重新加热。生成了新的码本。这时的系统已经跳出了那个极小点。

5)m = m + 1，如果m < 预定节拍数，则转入3)继续迭代。否则转入6)。

6)结束迭代，输出码本。只要系统温度下降的足够慢，系统将进入全局最小点，相当与金属的最佳结晶状态。

然而，这个方法的计算开销太大。工程上一般将第3步省略为只进行一次LBG迭代，而且温度下降公式采用速降规范：,。推荐下降系数0.9。一些实验结果表明，使用简化SR-D算法可以比LBG算法，在相同平均失真的情况下，将码本的规模缩小1倍，也就是节约了1个比特。

图5 SR-D算法中畸变函数随温度变化图

四。 矢量量化的应用

    语音编码、语音合成、语音识别和说话人识别领域

2.4Kbps的线性预测声码器的基础上，将每帧的10个反射系数加以10维的矢量量化，可使编码速率降低到800bps，而语音质量基本未下降。