数字视频通信-dvt05b图像的量化

门爱东教授

第5讲

率失真理论

量化

2本章内容Outlines标量量化的原理量化失真的客观度量Loy-Max量化器—最佳均方量化器(MMSE)均匀量化器高分辨率量化近似熵约束量化器矢量量化3量化模拟信号数字化中的量化：在实际中，信号的波形都是典型的连续幅度和连续时间，因此模数（A/D）变换用来产生波形的离散表示形式。经过抽样后的样值在幅度上仍然是连续的，幅度量化过程是用来把可能的幅度数目限制到有限个数目。由于幅度量化在很大程度上决定了系统总失真，以及把波形传送到接收端所必需的比特率。因此，量化是数字通信中关键的过程。量化在图象领域常有两种用途一是将模拟信号转变成数字信号，以便于随后进行数字处理，一般采用线性量化器，量化区间均匀划分，以区间的中间值做量化输出值。另一种用途是数据压缩，如在DPCM系统中对预测差值的量化，这种场合常用不均匀量化。量化类型标量(Scalar)量化：对每一个样值做独立的量化。矢量(Vector)量化：由K个样值构成K维空间的一个矢量，然后对其进行一次性量化。4标量量化的原理量化实质上可以看作是一个映射的过程。将所有取值落在Ri

范围内的输入信号映射到输出一点yi

上。5标量量化器的设计量化器的设计要求，通常设计量化器有下述两种情况：给定量化分层级数L，使得量化误差D最小。限定量化误差D，确定分层级数L，满足以尽量小的平均比特数表示量化输出，即码率R最小。标量量化又可分为:均匀量化、非均匀量化和自适应量化非均匀量化特性曲线均匀量化特性曲线6量化噪声（误差）输入x与输出

y之间的误差是量化过程中所固有的，称为量化误差。量化误差(噪声）是数字小信号失真的主要来源。量化处理是多个对一个的处理过程，是个不可逆过程，有信息丢失，或者说，会产生量化噪声。不同于信道噪声或热噪声，量化噪声不是随机引入的，一般说来，它与被量化的信号相关。度量量化误差时，首先需要一个衡量的标准，比如，均方误差准则（MSE）、绝对值误差准则等。下面的讨论都基于广泛使用的均方误差准则。7量化的失真测度均值表示，设输入随机变量x

的概率分布函数为p(x)。d[x,Q(x)]

用均方误差表示，称为均方量化误差

(Meansquaredquantizationerror,MSQE)。设量化Q(x)={yi，Ri，i=1，…，L}，则失真D为:8Lloyd-Max标量量化器-最佳均方量化器MMSE问题：信号x

的概率密度函数为p(x)

，设计一个

L

个输出电平的量化器，以均方误差作为评判标准，使其最小：结果：Lloyd-Max最佳均方量化器（MMSE，Lloyd1957;Max1960）L-1

个判决电平(门限)精确地位于输出电平之间的中点→最近邻L

个量化输出电平位于p(x)函数在两个连续判决门限之间的质心必要条件，但不充分9证明：根据上节讲述的量化失真度量公式，得

现在要对此多元方程求D的极小值，根据拉格郎日极值定理，分别对xi

及yi

求偏导，并使之为0，得：求解上述方程得：Lloyd-Max标量量化器10下面进一步分析最佳均方量化器的三个主要特点：设y=Q(x)

，量化误差ε=y-x=Q(x)–x

，则Lloyd-Max标量量化器特性量化误差的均值为0，量化误差无直流分量量化误差和重建信号不相关，正交量化误差的方差为输入、输出信号方差的差值，因此，量化输出信号方差减少A.K.Jain，Fundamentalsofdigitalimageprocessing，p10311证明：(1)Lloyd-Max标量量化器特性令则(2)输出电平位于p(x)函数在两个连续判决门限之间的质心12说明：（1）E[ε]=0，量化误差没有直流分量。用ε=x-Q[x]=x–y

替换，得到E[x]=E[y]。这表明MMSE量化器的输出电平y是输入电平x的的无偏估计。（2)E[Q(x)ε]=0，量化误差正交于量化器的输出电平。（3）E[ε2]=σε2=σx2-σy2

，做数学代换得到，如图所示，经过最佳量化器以后，信号的均方差减小了f(B)

倍。当输入信号的均方差σx2=1时，f(B)

就等于B比特最佳量化器的均方失真。Lloyd-Max标量量化器特性(3)前面已经证明：13Lloyd-Max标量量化器的设计基本思想：前面介绍的最佳量化器条件，即最小均方误差（MMSE）量化器的最近邻条件和质心条件。给定xi

，可以计算对应的最佳yi给定yi

，可以计算对应的最佳xi显然，判决电平xi

和量化电平yi

的求解是一个相互依赖的过程。问题：如何同时计算最佳的xi

和yi

？答案：迭代，或查表法14Lloyd-Max标量量化器设计的迭代法迭代法就是选择参量，以同时达到最佳分区（最邻近条件）和最佳码表（质心条件）的算法。Lloyd-Max迭代算法的具体步骤如下：

15Lloyd-Max算法举例Ix是均值为0，方差为1的高斯分布，即x~N(0,1)设计一个4电平的量化器，使得失真D*

最小用Lloyd-Max算法得到最佳量化器判决电平（边界）：-0.98,0,0.98量化（重建）水平：–1.51,-0.45,0.45,1.51Lloyd-Max标量量化器设计的迭代法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP114-11616收敛情况初始化A：判决边界为：–3,0,3初始化B：判决边界为：–1/2,0,1/2Lloyd-Max标量量化器设计的迭代法在两种情况下，经过6次迭代后，17Lloyd-Max算法举例IIx是均值为0，方差为1的Laplacian分布设计一个4电平的量化器，使得失真D*

最小用Lloyd-Max算法得到最佳量化器判决电平（边界）：-1.13,0,1.13量化（重构）水平：-1.83,-0.42,0.42,1.83一个好的预测器输出的预测差值信号通常满足0周围高峰值的分布，如Laplacian分布Lloyd-Max标量量化器设计的迭代法18初始化A：判决边界为：–3,0,3初始化B：判决边界为：–1/2,0,1/2收敛情况在两种情况下，经过6次迭代后，Laplacian分布的尾巴更长，外侧步长大；同时，内侧步长小，因为在中心附近概率大。Lloyd-Max标量量化器设计的迭代法194比特Laplacian最优量化器当输入方差小于假定方差，SNR下降很快。均方量化噪声MSQE减小，因为过载噪声减小。但是由于输入方差小，SNR中的信号/噪声比率减小很快。当输入方差大于假定方差，均方量化噪声MSQE相应增大，但是由于输入信号的能量增大，信号/噪声比率减小缓慢。当真实的数据方差和假设的方差不匹配时造成的影响Lloyd-Max标量量化器设计的迭代法20当信号x

的概率密度函数p(x)

不是均匀分布时，需要采用上述的反复迭代方法设计最佳均方量化器。这种迭代过程是比较麻烦的，Max已经针对不同分布的p(x)，计算出了最佳量化电平和判决电平。在某些情况可以直接套用。Lloyd-Max标量量化器设计的查表法判决门限输出电平21Lloyd-Max标量量化器设计的查表法22Lloyd-Max标量量化器设计的查表法已知输入信号x

的概率密度函数p(x)

为均匀分布、高斯分布、拉普拉斯或雷利分布，且均值E[x]=0，标准方差σx

=1时，得到最佳量化器量化电平yk(k=1,2,.,L)标准表。问题：当随机变量x’

的均值μ=E[x’]≠0，标准差σx’≠1时，如何由标准表转换出相应的量化电平？具体步骤如下图：23均匀量化器当信号x

的概率密度函数p(x)

在整个范围内是均匀分布时，即p(x)

为常数c时，上述Lloyd-Max最佳均方量化器变为均匀量化器，其输出的量化电平为：

判决电平仍为：（在输入区间上等间隔分布）

表明：对于均匀分布，均匀量化是最佳量化器对应输入信号区间(xi-1，xi）的中值，换言之，量化电平是判决电平xi-1

和xi

的算术平均值。量化电平是等间隔分布的。24均匀量化器当输出电平数L为偶数时，为中升型(Midrise)均匀量化器，0不是是一个输出电平；L为奇数时，为中平型(Midtread)均匀量化器，0是一个输出电平，图像、视频和音频中常采用的。当输入信号具有直流分量时，将其直流分量减去，然后通过图示的关于原点奇对称的均匀量化器，最后再将其直流分量加上。LL=4LL=525以均匀分布的均匀量化器为例输入：均匀分布的信源，幅度有界[a,b]，则pdf为输出：L个等间隔电平（L

又称为量化级数，L=2R）量化步长：判决电平和量化电平：颗粒失真（GranularNoise）：

均匀量化误差与输入信号的关系如图。处在均匀量化范围内的量化误差大小为[-0.5△,+0.5△]，称之为颗粒失真，或者颗粒噪声，表示为Dgran颗粒失真和过载失真26平均颗粒失真：代入得颗粒失真和过载失真27若输入信号x先经过归一化处理，使其范围在x∈[0,1]，即b-a=1，则上面等式成为：信噪比为：说明：量化级数每增加1bit，则步长减小一半，均方量化噪声减为¼，SNR增加6dB。人眼视觉对图像中变化不大、较为均匀的区域（低频）比较敏感，而对细节（高频）部分的敏感程度相对较弱。因此，通常对图像信号中的低频部分采用较大的量化级数。颗粒失真和过载失真28变暗、只保留轮廓1比特量化：[0,127]64[128,255]1962比特量化：边界：{[0,64,128,196,255}重构水平{32,96,160,2243比特量化例：81,2,3bits/pixel颗粒失真和过载失真2929颗粒失真和过载失真当分布不再是均匀分布时，需要考虑信源的pdf不同分布的信源，均匀量化时的SNR和最优步长30输入信号幅度为无界(-∞,∞)时在两个区间（-∞,x1]和[xL-1,∞)产生过载失真

Dol

（OverloadNoise）；在其它的

L-2

个区间(x1,xL-1)产生颗粒噪声，即量化失真大小在[-0.5△,+0.5△]内的误差。一般而言，颗粒失真幅度相对较小、产生的概率随着输入样值的不同而不同；过载失真幅度大，但只要量化器的负载因子γ设计合理，其产生的概率非常小。假设输入随机信号零均值、对称量化器，则该均匀量化器的噪声D为：颗粒失真和过载失真31颗粒失真和过载失真负载因子γ定义为：负载因子确定了无过载失真的量化器的最大半幅度范围，即（0，xoe）。xoe是被量化信号的均方根σx

的倍数，常常取值xL-1

或者yL，或者对于常用的对称量化器取xoe=(xL-1-x1)/2。负载因子的典型取值范围是2~4。例如，p(x)

为高斯分布，当γ=2时，其过载概率P{|x|≥xoe}为0.46；当γ=4时，其过载概率为0.000064，此时的过载失真可忽略。负载因子反映输入信号和量化器之间的匹配程度。在实际应用中，必须调整输入信号的电平增益以获得合适的负载因子，以保证均匀量化器的信噪比；换言之，均匀量化器的性能对输入信号电平很敏感。因此，当输入信号的功率电平范围未知或者是时变信号时，需要高分辨率的量化器，以保证得到满意的性能指标。

32输入信源：Gaussian，均值为0，4比特Gaussian均匀量化器当输入方差小于假定方差，SNR下降很快，MSQE减小，因为过载噪声减小，但是由于输入方差小，SNR中的信号/噪声比率减小很快。当输入方差大于假定方差，MSQE相应增大，但是由于输入信号的能量增大，信号/噪声比率减小很慢颗粒失真和过载失真方差不匹配的影响8电平量化器SNR设计的步长逐渐比“正确的”步长大，性能下降很快（类似方差比预计的方差小）33高分辨率量化近似在一般高分辨率（或高码率）量化时，L≥32

则在信号x

的概率密度函数p(x)

的不同分段区间内，可用常数代替，如下图所示：p(x)

可用分段恒常数代替，每一区间均匀量化xp(x)xi’ixi-1xipx)≈p(xi’)均匀量化对于输入是均匀分布的信号而言是最佳量化器（MMSE）；当输入信号不是均匀分布时，也可以使用均匀量化器，只要量化级数L足够高，其效果近似于MMSE。与MMSE量化器相比，均匀量化器的优点是设计实现简单，可以避免求解MMSE的非线性方程组。34高分辨率量化近似基于上述近似简化，根据最小均方误差准则得到的量化电平yi

，正好是均匀量化器的条件，即：证明：

利用近似条件

对

yi

求偏导，使，可解得：证毕。

35高分辨率量化近似设，则其中

称这种量化方法为高分辨率近似最佳均匀量化器。结论：对于方差为σ2

的高斯信源，下面文献证明，其均匀量化误差为:一般性结论：均匀量化误差具有形式，其中，c为常数，取决于信号概率密度函数。也称为Panter

andDite公式。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP125，p12636Lloyd-Max量化器是对固定码率编码的优化，对于变字长（变码率）编码，怎样做更好？量化的三个部分选择判决边界选择重构电平（量化电平）选择码字前面讨论的：给定L个重构电平，以均方量化误差(MSQE)最小来衡量量化器的性能，所有区间用固定码率编码：log2L

比特。现在讨论另一个问题：用码率R(bit/sample）或者“熵”衡量量化器的性能采用同样设计的量化器(Lloyd-Max量化器)，对量化输出用变长码编码。考虑判决的选择会影响码率，重新设计量化器（熵约束量化器）。熵约束标量量化器37低码率情况下，定长码与熵编码之间的差异并不大高码率情况下，定长码与熵编码之间的差异增大Laplacian分布的32电平均匀量化器，定长码需5比特，熵编码只需3.779比特定长码与均匀量化输出熵编码之间的差异大于定长码与非均匀量化输出熵编码之间的差异非均匀量化器在大概率区域步长小，在小概率区域步长大使得每个区间的概率相近增大非均匀量化输出的熵分布越接近均匀分布，上述差异越小。NumberofLevels定长码(bit)GaussianLaplacianUniformNonUniformUniformNonUniform421.9041.9111.7511.72862.4092.4422.1272.207832.7592.8242.3942.4791643.6023.7653.0633.4733254.4494.7303.7794.427Outputentropiesinbitspersamplesforminiummeansquarederrorquantizes熵约束标量量化器对Lloyd-Max量化器的输出进行熵编码38熵约束标量量化器

Entropy-constrainedScalarquantizer,

ECSQ用量化器输出结果的熵作为码率的度量对量化输出电平用熵编码技术编码量化器输出电平的熵定义为所以输出电平yi

的选择不影响码率，只影响失真。但判决边界xi

既影响失真，也影响码率，因此需要引入一个参数λ均方量化误差MSQEP.A.Chou,T.Lookabaugh,R.M.Gray,“Entropy-constrainedvectorquantization,”IEEETrans.SignalProcessing,vol.37,no.1,pp.31-42,Jan1989熵约束标量量化器39给定码率限制H(Q)≤R0，求得{xi},

{yi}和二进制码字，使Lagrange代价函数最小：太复杂，不能直接求解用迭代法求解

在最小化

J(λ)中λ

的作用较大的λ

H(Q)的权重更大只保留较小的熵H(Q)随着λ的增加减小可以用二分法求解最佳的λ

，使得H(Q)=R

H(Q)熵约束标量量化器40ECSQ算法（二重循环）选择一个初始的λ≥0（外层循环，控制码率H(Q)）初始化所有的yi，j=0，D0=∞（里层循环，控制失真D）计算判决边界：更新所有的yi

：更新pi

：计算MSE：若，转第8步；否则j=j+1，转第3步若，调整λ，转第2步熵约束标量量化器JPEG2000：ImageCompression，Fundamentals，StandardsandPracticebyDavidS.Taubman，p10541ECSQ算法的应用(I)x是均值为0，方差为1的高斯分布，即x~N(0,1)设计一个R≈2的ECSQ，使得期望失真D*最小11个区间（[-6，6]内）：几乎是均匀

定长编码：熵约束标量量化器SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP121-12342所有的实验中使用相同Lagrange乘子λ初始化A：初始化为15个均匀区间

初始化区间数量足够多，

在迭代过程逐步减少

初始化B：初始化为4个均匀区间

对于给定的λ值，初始的区间数目太少，在迭代20次时没有达要求的量化器性能R=2熵约束标量量化器43ECSQ算法的应用(II)x是均值为0，方差为1的Laplacian分布设计一个R≈2的ECSQ，使得期望失真D*最小21个区间（[-10，10]内），几乎是均匀的熵约束标量量化器44熵约束标量量化器所有的实验中使用相同Lagrange乘子λ初始化A：初始化为25个均匀区间

初始化区间数量足够多，

在迭代过程逐步减少

初始化B：初始化为4个均匀区间

对于给定的λ值，初始的区间数目太少，在迭代20次时没有达要求的量化器性能R=245高码率下ECSQ的性能对均方量化误差(MSQE)和高码率（高分辨率），均匀量化器（紧跟熵编码）是最佳的

[Gish,Pierce,1968]由前所述，如果概率密度函数不是均匀分布的，那么所得到的最佳量化器是一个非均匀量化器。H.GishandJ.N.Pierce,“Asymptotically.efficientquantizing,”IEEETrans.Inform.Theory,.vol.IT-14,pp.676-683,Sept.1968.

非均匀量化器可由一个均匀量化器和压扩器表示，希望找到一个最佳的压扩函数，使得在给定的失真下熵最佳。非均匀量化器的非线性程度可以由压扩曲线c(x)表示，其动态范围为[-xmax,xmax]、级数为L，当L足够大时，c(xk)的斜率，即c(xk)在xk

处的导数c‘(xk)近似为均匀量化器和非均匀量化器的量化台阶之比：其中Δk=xi+1-xi

是第k个量化台阶46高码率下ECSQ的性能在高码率下（L足够大），每个量化区间[xi,xi+1]内p(x)近似为常数，且yi

取xi

和xi+1

的平均值，则每个量化区间内的均方量化误差为：总的均方量化误差为：IntroductiontoDataCompressionbyKhalidSayood，p263当Δi

较小时，求和表示为积分47高码率下ECSQ的性能同样，在高码率下（L足够大），每个量化区间内概率密度函数p(x)近似为常数，则量化器输出电平为yi

的概率为：量化器输出电平的熵：IntroductiontoDataCompressionbyKhalidSayood，p26748当Δi

较小时，高码率下ECSQ的性能微分熵，近似为量化器输入信号x

的熵H(X)IntroductiontoDataCompressionbyKhalidSayood，p26749高码率下ECSQ的性能令则所以，则变成拉格朗日函数的极值问题：IntroductiontoDataCompressionbyKhalidSayood，p26750

所以如果使用边界条件得到这就是均匀量化器所对应的压扩器特性，为线性所以，高码率下，最优量化器为均匀量化器将该压扩函数的导数代入高码率下ECSQ的性能51码率为失真-码率函数为是Shannon下界的，即高码率的均匀ECSQ量化器的SNR与Shannon下界差1.53dB（对任何平滑pdf）高码率下ECSQ的性能JPEG2000：ImageCompression，Fundamentals，StandardsandPracticebyDavidS.Taubman，p10652相同码率R下，ECSQ的失真比Lloyd-Max量化器更小高码率下ECSQ的性能Gaussian信源的量化器均匀量化器+熵编码53高码率下ECSQ的性能Gaussian信源的量化器JPEG2000：ImageCompression，Fundamentals，StandardsandPracticebyDavidS.Taubman，p10954高码率、IID信源的Lloyd-Max量化器和熵约束量化器的MSE失真—码率函数均可以表示为：缩放因子ε2

的数值均匀1Laplacian9/2=4.5gaussian√(3π)/2=2.721高码率下ECSQ的性能ECSQ熵约束最佳量化器ECSQ是在给定H(Q)的条件下，求判决电平和输出电平，使得均方量化误差σd2为最小。在ECSQ量化器和熵编码联合优化中，将熵H(Q)看成“码率”，那么无论在失真约束下最小化码率，还是在码率约束下最小化失真，均匀量化都是或接近于最佳的。因此，在图像和视频压缩标准中，都采用了均匀量化器和熵编码联合的方法。JPEG2000：ImageCompression，Fundamentals，StandardsandPracticebyDavidS.Taubman，p108Lloyd-Max55自适应量化器思想不是静态方法，而是与真实数据的统计特性相适应均值、方差、pdf前向自适应(离线)将信源分块分析块的统计特性设置量化方案边信道（Sidechannel）后向自适应(在线)基于量化器输出自适应无需边信道56前向自适应量化器（FAQ）选择块大小：折中太大分辨率不够，不能抓住输入的变化延迟增大太小需要传输更多的边信息假设均值为0方差估计FAQ问题：需要缓存分析统计特性，造成延时边信息的同步57例：语音量化16比特3比特定长码失真较大前向自适应量化器（FAQ）男声“test”IntroductiontoDataCompressionbyKhalidSayood，24558例：语音量化（2）16比特3比特FAQ块大小：128个样本标准方差进行8比特量化，并传送给接收端失真较小红色区域还有提升空间前向自适应量化器（FAQ）59改进的前向自适应量化器（FAQ）迄今为止，我们假设均匀pdf改进假设均匀pdf，但记录每块的最大/最小值例：Sena图像

8×8块每个像素3比特量化每个块中边信息最大值/最小值各用8bit表示，则每个像素平均为每个像素共：3.25bits/pixel和原始图像几乎难以区别对于高码率，前向自适应量化是个非常好的选择原始图像：8bits/pixel量化：3.25bits/pixel60后向自适应量化器（BAQ）观察解码器只能看到量化器的输出只能根据量化器输出进行自适应问题只根据输出，如何减少不匹配信息如果知道pdf，这是可能的……耐心：观察长时间的量化器输出，推测是否发生了不匹配现象如果匹配，落入某区间的概率与预定的pdf一致，否则，发生了不匹配现象。失配时，如果步长比应有的步长小，输入落入外侧区间的数目偏大；相反，输入落入内侧区间的数目偏大。Jayant量化器不需要观察长时间的量化器输出，在观察单个输出后就可调整量化步长，Jayant称之为“quantizationwithonewordmemory”。61嵌入式量化器动机：不同码率、不同质量的可伸缩（scalable）解码随着比特流的解码，渐近地精化重构数据对低带宽有用是JPEG2000的一个关键特征嵌入式量化：低码率量化器的区间被再分割，以产生更高码率的量化器，即高码率的量化器嵌入在低码率量化器中。通常，只有其中一个量化器是最优的(除了均匀量化外)。可以通过截断量化索引获得较粗糙的量化EmbeddedscalarquantizersQ0,Q1andQ2,ofrateR=1,2,and3bits/sample62例1：均匀量化器嵌入式量化器63例2：Deadzonequantizer假设deadzone量化器的量化区间的索引用4个比特表示如果收到了所有4个比特步长为Δ如果只收到了前3个比特步长为2Δ如果只收到了前2个比特步长为4Δ嵌入式量化器6464例3：高斯分布的Lloy-Max量化器、2bit和3bit最优量化器是非最优的嵌入量化的性能损失嵌入式量化器65矢量量化VectorQuantization主要内容基本思想标量量化的不足之处定长码VQ的LBG算法变长码VQ的CLG结构化VQ树结构VQ（Tree-structuredVQ）格型量化（Latticequantization）网格编码量化（Trelliscodedquantization,TCQ）IntroductiontoDataCompressionbyKhalidSayood66矢量量化矢量量化编码是图像、语音等编码技术中采用的一种量化编码方法。矢量量化编码方法一般是有失真编码方法。压缩符号串比压缩单个符号在理论上可产生更好的效果如图像和声音的相邻数据项一般存在相关性矢量量化：量化时不是处理信源单个符号，而是一次处理一组符号（矢量）得到更好的压缩性能：码率/失真更小矢量量化编码解码框图67矢量量化以图像编码为例查表搜索距离最近的码字非对称编码：编码：在输入与码本匹配过程中需大量计算解码：只需查表68矢量量化——码率码书（codebook）中共有K个码字（codeword），则表示码字索引需log2K比特假设矢量大小为L个样本，因此码率（表示每个样本所需比特）为例：对8比特256级的灰度图像进行矢量编码每个矢量大小为L=4×4，用K=1024个码字的码书对图像进行矢量量化则码率为R=[log2K]/L=10/16=0.63bpp压缩比为：8:0.63=12.8:1可以通过对码字索引采用熵编码技术得到更高的压缩比69矢量量化——失真采用均方误差作为量化失真度量定义：码书C，包含K个码字矢量Yj输入矢量X与码字矢量Yj最近，量化输出Yj定义为其中量化区域（判决边界）：表示所有可以被Yj

量化的输入矢量iff

当且仅当70矢量量化问题：为什么矢量量化(VQ)比标量量化（SQ）好？怎样产生码书？对每个输入矢量，怎样找到与其最匹配的码字？标量量化效率可以继续提升利用样本之间的相关性即使不存在相关性，通过降低量化中存在的两种误差（噪声）过载误差（边界处）颗粒误差71SQ不足VQ优势优势1：相关性的利用。在相同的给定码率下，矢量量化比标量量化具有更低的失真。例：考虑量化信源的两个样本（重量和身高）重量和身高各用3bit均匀量化，共6bit比特率：3比特/样本每个样本8个量化电平若对每个样本采用均匀标量量化，则2-D样本空间被分成64个长方形均匀区域（Voronoi区域）身高和体重的关系，在一定身高[40,80英寸]和重量[40,240磅]范围内各用3bit均匀量化。72若考虑二者之间的相关性（例如身高和体重），对x1、x2

一起量化，则输出点数量一样，但输出点位于输入的聚集区域。实际中，一个80英寸身高40磅体重，或者身高42英寸体重200磅的人，很少出现。因此，图中的均匀量化效率不高。一个人的身高和体重是相关的，不再单独量化，在同样的量化比特数时，为输入提供了更细致的量化。SQ不足VQ优势SQ不足VQ优势对于有记忆信源，样本之间具有线性或非线性相关。在优化的VQ设计中，把N维空间划分为量化单元时，可以利用这些相关性。Gauss-Markov过程，相关系数ρ=0.9L=2二维矢量量化，采用熵约束矢量量化（ECVQ）的CLG算法（见后），CLG算法中Lagrange参数λ取不同的2个值。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P14574SQ不足VQ优势对于有记忆信源，高码率的矢量量化可以获得相关增益。Gauss-Markov过程，不同的相关系数N维矢量量化视频信号具有很强的相关性VQ具有更高的相关增益在视频编码中，如何更好地利用像素间的相关性，是最重要的之一实际中，标量量化和预测编码或线性变换、熵编码联合，也可以利用信源的相关性。75优势2：空间填充SpaceFillingAdvantage分析表明，更高的N维标量量化最终把N维空间划分成N维超矩形（间距的笛卡尔乘积）。但对于矢量量化，我们有很大的自由去选择量化单元的形状。获得的编码增益叫SpaceFillingAdvantage.例：考虑Laplacian分布的8量化电平的一维的均匀标量量化器，已知△=0.7309，同一个输入落入不同量化区间的概率是不同的，例如：直接扩展到x1、x2

轴，得到2D输入的量化器当量化器有两个输入x1、x2

时，构成如图的两维量化器，圆点表示两维样本的量化输出。各区间的概率不同，例如最右上区域的概率：SQ不足VQ优势IntroductiontoDataCompressionbyKhalidSayood76上述最右上区域概率非常小，几乎不可能发生，简单地将它放在别处，可能更有用。若将其移到概率最大区域—原点附近，得到修正的量化器SQ不足VQ优势但如果对标量量化器做类似操作，将3.5Δ移至原点，则两种情况下信源的均方值一样，SNR增加了，意味着均方误差减少。这种SNR提高是否有意义取决于特定应用，但重要的是通过微小的改变，得到了正面的效果。改变了中心位置的量化图案，不再是均匀量化了。对原来是非均匀的量化器做同样的处理，会得到类似的结果。矢量量化修正的矢量量化77另一种修正方案，不改变点的位置，而是保留等概线|x1|+|x2|=5Δ

内的点：60个点没有改变等概线内部的量化形状，只改变了量化器的外部边界。去掉原来8×8空间64个点中不满足条件的12个点(圆形标注)增大过载概率增加8个（方形标注），不是原来8×8=

64个点里面的减少过载概率减少的负载概率

>增大的负载概率

总过载概率减小SNR:11.44dB

12.22dB这样获得的好处称为边界增益矢量维数增加，过载噪声进一步减少。塔式/球形VQ的原型SQ不足VQ优势787878SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P143例：单位方差的高斯

iid

信源的二维矢量量化，码率R=2bit/样本LBG算法的第8和49次迭代的量化结果：8次迭代后，矢量量化和标量量化的SNR近似相等（9.3dB），因为矢量量化单元近似为矩形，标量量化器也可构造出来49次迭代后，矢量量化单元形状在中心位置近似为正六边形，VQ

SNR增加到了9.67dB，但标量量化无法产生这样的图案更高的码率，收敛趋于更完美的正六边形。SQ：标量量化SQ不足VQ优势例：单位方差的均匀分布的iid

信源的二维矢量量化，A=10标量量化：K=10，码率（熵）为3.32bit/样本，SNR为19.98VQ的LBG算法：L=2，K=100时，达到上述码率3.32bit/样本最终，VQ聚类趋于正六边形，SNR也提高到了20.08dB。由于单元密集，获得的空间填充增益与输入信号的分布或统计相关性无关。

空间填充增益的上界是1.53dB，如果矢量量化器的维数趋于无穷，对高码率VQ，可以渐进达到此增益上限。797979SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P143SQ不足VQ优势8080优势3：分布形状ShapeAdvantage优化的VQ量化单元将更适应于信源概率密度分布下图显示了高斯和拉普拉斯iid信源的VQ维数和失真之间的关系。在实际中，可以利用标量量化器和熵编码的联合，也可以获得shapeadvantage。在上述三个优势种，空间填充是VQ独有的，相关和分布形状是SQ和VQ都可以利用的，只是SQ需要和其它技术结合。

SQ不足VQ优势81优势4：颗粒噪声颗粒失真标量量化：由量化步长决定矢量量化：由量化区域大小和形状决定立方体区域vs.球形区域体积相同时，在所有的形状中，球形区域的最大颗粒误差最小体积相同时，在所有的形状中，球形量化区域的平均颗粒误差最小面积：1边长：1最大误差：面积：1半径=最大误差=SQ不足VQ优势参见DavidS.Taubman《JPEG2000：ImageCompression，Fundamentals，StandardsandPractice》，p117，3.4.1节82定长码的矢量量化—LBG算法对于定长码的矢量量化器，可以将相应的定长码的标量量化的Lloyd-Max算法推广到矢量量化，所以亦称为推广的Lloyd算法(GeneralizedLloydAlgorithm,GLA)[Linde,Buzo,Gray,1980]，亦称为LBG算法给定训练集：收集的训练集需有代表性码字(量化输出电平)判决边界训练矢量量化区域QuantizationCell83定长码的标量量化的Lloyd-Max算法初始化所有的量化电平更新所有的判决边界：计算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否则k=k+1，更新所有的yj(k)

：转到第2步84定长码的VQ的LBG算法初始化所有的量化电平更新所有的判决边界：计算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否则

k=k+1，更新所有的Yj(k)

：转到第2步这个算法非常不实用，因为计算失真需要积分，以及质心位于n维矢量的畸形区域。通常，这些积分计算非常困难，使得它更多的是学术兴趣。更实际的算法是带训练集的LBG算法，用求和代替积分。85LBG算法（带训练集）给定训练集T={X1,X2,…,XN}，初始化所有的量化电平更新所有的量化区域：计算训练矢量和量化电平之间的平均失真MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否则

k=k+1，更新所有的Yj(k)

：同聚类中的K-means聚类（假设没有量化区域是空类）86举例LBG1HeightWeight721806512059119641506516257887217544416211460110569170172HeightWeight14550245117375117480180LBG算法训练样本集初始码书87LBG算法最后的矢量量化器一次迭代后的矢量量化器失真：60.1788LBG算法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P138举例LBG2：高斯

iid信源，单位方差二维矢量量化器，即L=2个样本，K=16个码字，相当于每个样本2

bit（标量）R=(log2K)/L=2LBG算法的初始化、第8和49次迭代的量化结果8989LBG算法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P138相同码率(R=2bit/样本)的标量量化和矢量量化性能比较：8次迭代后，两者失真近似（9.3dB），因为矢量量化单元近似为矩形，标量量化器也可构造出来49次迭代后，矢量量化单元形状，标量量化器是无法产生的，因此矢量量化SNR增加到了9.67dB。比SQ高0.37dB。SQ：标量量化9090LBG算法举例LBG3：高斯iid

信源，单位方差，二维矢量量化器，即L=2个样本，K=256个码字，相当于每个样本4

bit（标量）R=(log2K)/L=4LBG算法的第49次迭代的量化单元和重建矢量量化失真：49次迭代后，标量量化SNR20.64dB，比VQ低0.9dB。表明更高的码率R，VQ比SQ有更高的SNR增益。919191LBG算法举例LBG4：拉普拉斯iid

信源，单位方差，二维矢量量化器，即L=2个样本K=16，R=2bit/样本，VQSNR=8.87dB，比相同码率的SQ高1.32dBK=256，R=4bit/样本，VQSNR=19.4dB，比SQ高1.84dB。92LBG算法优化过程能保证收敛，但可能收敛于局部极小值非常依赖于初始码书的选取初始码书的选取随机选择：重复多次，取失真最小的结果分裂：从一个类开始，每次将失真最大/数量最多的类分裂成两个合并：从N个类开始，每次将两个失真最小的类合并空类的问题：去掉空类，并将失真最大/数量最多的类分裂成两个93LBG用于图像压缩每块大小为L=4×4，用K=16,64,256,1024个码字的码书对图像进行矢量量化码率：Sinan图像训练得到码书原始图像94LBG用于图像压缩传输码书（overhead）的bit消耗：K=1024,overhead=2,为编码内容码率(0.625)的3倍用通用码书，无需传码书，但质量可能稍差收集代表性的训练集CodebookSizeBitsforaCodewordBits/PixelCompressionRatioOverheadinBits/Pixel1640.2532:10.031256460.37521.33:10.12525680.316:10.51024100.62512.8:12.095LBG算法的缺陷码字中缺少结构编码复杂性高：需要全搜索存储要求高，码书指数增长例：目标码率：R比特/样本每个矢量包含L个样本(如4×4像素一起编码，则L=16)码字索引：RL比特码书中可能的码字有2RL

个码字例：R=0.25比特/样本，L=16个样本/矢量每个码字索引需RL=4比特码书中共有24=16个词条R=2比特/样本，L=16个样本/矢量每个码字索引需RL=32比特码书中共有232=40亿个词条在高码率下，VQ不太实用熵编码的矢量量化熵约束矢量量化

entropy-constrainedvectorquantizer，ECVQ为熵编码矢量量化，扩展了熵约束的Lloyd-Max算法（ECSQ），称为

Chou-Lookabaugh-Gray(CLG)[1989]Lagrangian代价函数：给定码率下使得失真D最小平均码字长度作为熵H，即类似于ECSQ，ECVQ判决边界和量化电平的必要条件96P.A.Chou,T.Lookabaugh,R.M.Gray,“Entropy-constrainedvectorquantization,”IEEETrans.SignalProcessing,vol.37,no.1,pp.31-42,Jan198997ECVQ的CLG算法对于足够大的训练集{xn}和给定的拉格朗日参数λ初始化所有的量化电平更新所有的判决边界：更新量化电平计算平均码长计算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否则

k=k+1，转到第2步98989898ECVQ的CLG算法举例ECVQCLG：高斯和拉普拉斯iid

信源，单位方差，二维矢量量化器，即L=2个样本，作为熵的平均码率为R=2bit/样本高斯分布，ECVQ的SNR比相同码率的ECSQ高0.26dB拉普拉斯分布，ECVQ的SNR比ECSQ高0.37dB高斯拉普拉斯9999999999性能比较不同维数的CLG和标量量化的性能比较Gauss-Markov信源，相关系数ρ=0.9维数L=2,5,10和100的VQ标注为“VQK=L(e)”L=100时，理论上VQ性能已非常逼近R(D)限。事实上，当维数L趋于无穷时，VQ渐进达到率失真界限。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P147100100100100100100性能比较矢量量化可以解释为一个最通用的有时真源编码系统。每个源编码系统可映射为一个矢量量化。尽管具有很好的编码效率，但矢量量化很少用于视频编码主要原因是复杂一是巨大的码书存储，特别是当视频编解码器需要不同码率时，这更成为问题；二是计算复杂，相对于标量量化，要想获得一个率失真下最好的重建矢量，需要大量的计算。减少存储和计算复杂度的方法是利用结构化约束的矢量量化器，例如Tree-structuredVQ，TransformVQ，MultistageVQ，Shape-gainVQ，LatticecodebookVQ，PredictiveVQ。实际中，视频编解码更多是采用中平型均匀量化器，然后结合熵编码和线性预测或变换编码，去利用信源分布形状和统计相关性。而矢量量化，包括哪些结构化的VQ，相对于获得的好处而言，还是太复杂了。101改进的矢量量化树结构（Tree-structured）矢量量化搜索快，但存储量大格型矢量量化LatticeVQ网格编码矢量量化（TrellisCodedVQ）102树结构VQ在码书组织中引入结构，快速决定哪个部分包含所需输出矢量（重构电平）通过搜索一系列小码书降低搜索复杂性，复杂性线性增长logK但需要更多存储（约两倍）：测试矢量(testvector)103树结构VQ可以通过Linde等提出的分裂方法实现首先将所有训练集视为一个类，计算类中心（均值）作为测试矢量和输出水平将一个类分裂成两个子类，子类中心为将原父中心的均值分别+/-一个扰动LBG算法中也是采用类似分裂方法解决初值问题其他：剪枝码书减小码率减小但失真可能增大104格型VQ在前面的讨论中，我们知道球形量化区域是最佳的（颗粒噪声最小）但球形填充（tile）要么有重叠，要么有空洞需要找到某种高效的量化区域结构化码字，以近似球体并填满球体结构化：省存储/计算量小有规律格型Lattice球体：颗粒误差最小Lattice：令为L维线性独立的L维矢量，集合中为整数，则集合为一个lattice105格型VQLattice量化器：将lattice点集的子集作为VQ的输出点最近邻LatticeVQ：Λ的基本量化区域：0

附近的单元106举例：D2lattice性质：对所有的lattice点，菱形量化区域格型VQ107举例：A2lattice:六边形量化区域：2D上最佳格型VQ108格型VQ的性质不必存储码字比LBG算法更容易找到最近邻但是，Lattice量化器没有了LBG聚类的性质设计准则：最小化颗粒误差对2-DVQ，六边形lattice是最佳的对Gaussian信源，熵编码的lattice量化器离D(R)边界有1.36dB109TrellisCoded量化（TCQ）计算效率高的矢量量化中等计算复杂度理论优势：对任何平滑pdf，熵编码的TCQ能在任何码率下达到D(R)函数的0.2dB以内（性能超过24维以下的最佳lattice量化）基于TrellisCodedModulation(TCM)TCQ在JPEG2000II中用到110Trellis编码网格(trellis)是一个有限状态机随时间的进化例：一个带有二进制I/O的4状态的有限状态机T0和t1为移位寄存器状态表示为t1t04个状态状态转换图u/z1z0111Trellis编码在状态转换图中加入时间因素112Trellis编码