《图像压缩编码方法》课件第4章

第4章全局最优码本的获取的研究4.1矢量量化的一般概念4.2经典算法LBG4.3模糊矢量量化方法4.4初始码本的生成4.5实验模拟和分析4.6基于小波变换的矢量量化编码

4.1矢量量化的一般概念

矢量量化(VectorQuantization，VQ)是标量量化的自然发展产物，它是相对于一维情形下的标量量化(ScalarQuantization)提出的，其有效地利用了矢量各分量间的四种相关性：线性依赖性、非线性依赖性、概率密度函数的形状以及矢量维数来进行去相关处理，而标量量化只利用了线性依赖和概率密度函数的形状。因此，矢量量化在保证一定的图像质量的条件下可获得较高的压缩比。现在已把矢量量化作为一种独立的编码手段来考虑，而不仅仅是一种量化技术。从本质来看，VQ是一种聚类分析的方法，即根据有限的矢量集Y={Yi，Yi∈Rk，i=1，…，N}，将欧氏空间Rk按某种矢量度量划分为不相交的子空间{Ri，i=1，…，N}，这种划分应该为Y的最邻近域(nearestneighbor)划分，即Voronoi划分。任何一个输入矢量X均可以按这种划分归为某一子空间，并且用Yi表示。X是由像素方块组成的输入矢量，编码器的输出为二进制序号in，该in在解码端指定了重构矢量的序号。如果码率为固定码率bbit输入矢量，则in的长度为b。对于变码率的情况，序号的长度也是可变的，此时b为平均码长。压缩图像可由这些in来描述，因为它们所要求的比特数比原始图像少。对于一个k维的矢量量化器可以定义为k维欧氏空间Rk到其有限子集Y的映射Q，即Q：Rk→Y，其中Y在VQ中称为再生矢量集或再生码本。从这种编码角度理解，这一映射也可看成是由两部分组成：第一部分由输入矢量X按某种矢量度量准则 产生码本中对应d(X，Yi)最小的索引in，称为编码器；另一部分则完成根据索引in产生再生矢量Yi的工作，称为解码器。显然，Yi应是失真度量d(X，Yi)下X的最佳逼近。它们的理论根据是Shannon的率失真编码理论。该理论指出：不论信源有无记忆，组编码总是优于单个编码的。当编码长度(即矢量维数)K→∞时，矢量量化编码可以达到率失真边界，K越大，离率失真边界越近，这为矢量量化编码的研究奠定了良好的理论基础。从理论上说，在矢量量化编码中高维矢量编码比低维矢量编码有更好的编码效果，但是当数据为k阶相关时，任何高于k维的高维矢量编码也仅能以k维矢量编码的平均编码熵为下限。从而就信息熵的意义上说，VQ编码的矢量维数k最高不应高于相关阶数。但它们的分布概率都未知，它们的相关阶数也不知道。从另一方面来说，码矢搜索的复杂度也是很高的(因为矢量量化编码的复杂度随矢量维数成指数增长),这在实际系统中是不允许的。要利用高维矢量量化编码，可以采用两种解决办法，一种是对全局搜索VQ，编码器通过穷尽搜索得到最近的码矢；另一种是对码矢进行限制，使其在k维空间只能以某种特定方式分布，从而使最近邻的搜索更快，或者更快地搜索到一个与最近邻差异不大的码矢。格形矢量量化即属于后一种方法，它通过构造多级码本降低矢量量化的时间复杂度。树结构矢量量化、多级矢量量化、分类矢量量化、有限状态矢量量化、分层矢量量化都属于后一种方法。与此相对应，矢量量化器的码本构造方法也分为两种，格形矢量量化器以格点作为量化矢量，把信号空间划分为胞腔，因此其码本构造实际就是格的构造，这可以根据李代数理论进行。由于格点和胞腔是有规律的，格形矢量量化器的码本构造较容易，而且可以使用维数。格形矢量量化方法的主要缺点是码本仅仅对服从均匀分布的信源是最优的。法国M.Barland等人提出的基于小波分解的塔式格形矢量量化(PyramidLattic，PLVQ)方法是目前较实用的一种中低比特率图像方法，它对标准图像Lena进行编码，当压缩比为45.8时，重构图像PSNR值为30.3dB。另一种码本构造方法是聚类分析的码本训练方法，如常用的LBG算法等。这种方法的优点是不需知道信源的特性，适用性较强。其主要的一些问题是：

(1)在计算过程中假设X是稳定的和各态历经的，而这种假设并不一定满足；

(2)优化量化器是对于训练向量集{x1，x2，…，xn}而言的，对于实际的最终码本是否最优的，的确还很难说，这还要依赖于训练向量集的代表性到底真实到何种程度；

(3)由于优化分割的过程并没有什么数据结构方面的规则或限制，而是自由进行的，这使得将来对码本进行组织时遇到了极大的困难；

(4)在某些情况下甚至根本无法找到真正具有代表性的训练序列，因此寻找其他优化算法的探索一直没有间断。

这些问题，带来了一些不足，使码本的训练和码矢的搜索时间复杂度较大。基于训练的矢量量化的另一个显著特点是压缩系统性能高度依赖于码本。码本的代表性以及训练方法的选择紧密相关。因此，设计一个好的码本是VQ系统的关键问题。

4.2经典算法LBG

第一个实用化的矢量量化器是由Linde等人在1980年提出的，这是至今仍在广泛应用的算法。LBG算法其实相当于Lloyd-Max方法的多维推广。对于希望设计一个k维N码字空间矢量量化器，要求Y0={y(0)1，y(0)2，…，y(0)N}是由随机方法给出的一个初始码本，其对应的量化器记为Q0。若能够找到一种新的码本Y1={y(1)1，y(1)2，…，y(1)N}，使D1(Q1)=E{d(x，Q1(x))}≤D0(X0)=E{d(X，Q0)}，其中Q1为Y1所对应的量化器，则我们说量化器Q被优化了一次。重复这个过程去寻找Y1，Y2，…，Ym。对于一个事先给定的迭代门限值ε，若有

则认为该量化器已经是完成了优化的。

LBG算法(概率分布F分布)具体步骤：

(1)初始化。给定N，ε≥0，Y0={y(0)1，y(0)2,…,y(0)N}，F，置m=0，D1=∞。

(2)对于Ym={y(m)1，y(m)2，…，y(m)N}，计算Dm(Qm)=E{d(X，Qm(X))}。

(3)若 ，停止。(4-1)

(4)寻找 ；i=1，2，…，N}，令Ym=X(φ(y))，m=m+1，返回(2)。

LBG算法中步骤(4)的φ(Ym)是对符号集(码字集)Ym重新进行优化分割， ；i=1，2，…，N}是对重新分割所得到的Ri，i=1，2，…，N统计计算其质心 。

由于步骤(3)进行优化φ，即

Dm(φ(Ym))<Dm－1(φ(Ym－1)) (4-2)

它并不需要知道输入矢量的概率，在这种情况下，LBG算法第(2)步改为计算(4-3)采用LBG算法设计的VQ编码器有以下缺点：

(1)最终码本只收敛到一个局部最佳点。LBG不能保证得到的码本相对训练集是全局最优的，尤其是对训练集之外的数据。

(2)最终码本的形成与初始码本的选取非常有关，最终码本能否接近全局最优，常常取决于初始码本的选择，至今并没有一种很好的初始码本选取方法。

(3)LBG方法生成的码本是无序的，因此给最优化搜索器设计带来很多困难，搜索算法十分复杂，运算量巨大。除此之外，当采用LBG算法设计的VQ系统用于图像编码时，在压缩比较大时，图像的边缘不能完整地恢复，边缘退化十分严重，影响了图像的主观质量。为了克服LBG算法的这些缺点，需要研究初始码本的选择(初始码本的选择恰当与否直接决定了迭代的收敛速度和最终的失真度程度)。传统的初始码本生成方法有三种：

(1)随机法：从训练序列中随机选取N个矢量构成初始码本；

(2)分裂法：从第一个码字开始，通过分裂的方法将码本扩大一倍，再用LBG算法求得最优解，如此重复直至码本大小符合要求为止；

(3)乘积法：利用多个低维码本做乘积运算来获得高维码本。设有m个码本Ci，i=1，2，…，m。每个码本含有ni个ki维矢量，则乘积码本按下式生成：

这些方法中，随机选择法固然简单，但其性能通常也是最差的，最常用的是分裂法，它性能虽比乘积法略差，但计算量比乘积法要少得多，因而在计算量与性能之间取得了良好的折衷。

因此，改进全局最优码本的思路有两条：其一是通过改进算法来实现；其二是通过选择靠近最优解附近的初始码本实现。 4.3模糊矢量量化方法

码本训练本质上是一个优化过程。近年来基于神经网络的优化技术为全局最优码本的获取提供了一条有效的路径，但计算复杂，难以达到全局最优解。目前典型的方法有模拟退火训练方法和模糊矢量量化(FVQ)方法。模拟退火方法是通过在码本训练过程中适当增加随机扰动，使搜索跳出局部极值区域而达到全局最优解。模拟退火方法的一个显著缺点是算法收敛较慢，训练时间较长。FVQ方法是将每个码矢作为一个模糊集，每个训练矢量以隶属函数的测度分配给各个码矢。若被考虑的训练矢量是一超球体的中心，则存在重叠的超球体保证了所有训练矢量与新码矢的形成，有效地降低了设计结果对初始码本的依赖。

FVQ方法通过逐步收缩重叠来实现训练矢量，逐步由软决定向硬决定转变。为了使训练结果不会陷入局部极小值，并且训练速度较快，FVQ的设计应注意三个方面的问题：(先设矢量维数为n，码本Y={Y1，Y2，…，YK}，大小为K，训练集为X={X1，X2，…，XN}，大小为N(N

K)。)

(1)训练矢量从软决定向硬决定的转变应根据聚类过程中超球体的收缩来判决。具体地说，令Ivi是在第v次迭代中的中心为训练矢量Xi的超球体的收敛含的码矢集合。第v+1次迭代时训练矢量Xi的超球体所包含的码矢Yj应满足与Xi的距离小于Xi与Yj的平均距离：(4-4)＞＞式中N(Ivi)是Ivi中元素的数目，则

当Ivi只包含一个码矢时，训练矢量由模糊状态转变为确定状态。

(2)隶属函数的选取。隶属函数μj(Xi)表示了训练矢量Xi对第j个码矢代表的类的隶属度：(4-5)(4-6)

码本公式：(4-7)(4-8)

(3)判别阈值e和e'的选择。其中e'是所有训练矢量转变为硬判断模式的失真变化率阈值，而e'是算法停止的失真变化率阈值。条件e'>e可以保证FVQ算法不停止软判断模式而落入局部极小值。

在模糊矢量量化算法中，收敛过程是由软判断转向硬判断的结合思想，如果把每个码本矢量看做一个聚类，那么Xi则分别隶属于球内所有的聚类。算法开始时，每个训练矢量隶属于所有聚类，这就意味着所有训练矢量初始的超球体完全重叠。在收敛过程中，超球体逐渐缩小，超球体相互重叠部分也越来越小，即训练矢量越来越明确地分配给某个聚类。当超球体缩小到只包含一个聚类时，则训练矢量唯一地分配配给此聚类，这个训练矢量也就完成了从软判断向硬判断的转变。这样，随着大部分训练矢量逐渐从软判断转变到硬判断，所计算的失真度总和也越来越小，当失真度总和小于阈值e'

时，将还没有转变到硬判断的训练矢量强制向硬判断转变。最后，经过硬判断(LBG算法)的迭代最终达到允许的失真阈值e而结束该算法。

4.4初始码本的生成

从数字角度而言，码本设计的实质上是一个高维空间的优化，优化的结果是使码本中的码矢逐步收敛到训练序列相应的不动点上，同时给出了相应的最佳划分。根据码本的形成过程，码本设计可分为两个阶段：初始码本的生成和初始码矢的优化；虽然此算法对初始码本的依赖性降低，但是初始码本的好坏直接影响训练的时间，也影响着整个VQ系统的性能，因此节省训练时间虽不能直接克服VQ在高速运用下的困难，但仍是很有意义的。

由矢量量化理论，构造最佳矢量量化器的必要条件是：

(1)划分条件。输入矢量即空间被划分成N个Vornoir域，即

(2)形心条件。码字是相应的Vornoir域的形心，即

以及(4-9)(4-10)(4-11)对于均匀方差(MSE)失真测度，这个条件可以表述为相应的Vornoir域的算术均值。其中X为k维欧氏空间Rk的矢量，Yi为每个Vornoir的码字(中心)。D为码本平均失真。矢量量化器可以定义为一个映射Q，它将k维欧氏空间矢量点X映射为子集Y，Q：Rk→Y，Y为码本，因此，Q(X)=Yi为k维量化器。C

={Ci：i=1，2，…，K}是相关的空间划分，且满足

和Ci∩Cj=Φ，i≠j，失真度D为(4-12)其中，X为训练向量，p(X)=p(x1，x2，…，xk)是X的联合概率密度函数。d(X，Y)为

由失真D(Q)公式可得

其中Di表示区域Ci所对应的子误差，各区域子误差可表示为(4-13)(4-14)(4-15)模糊矢量量化算法的最终结果是使D(Q)最小，当各子误差Di最小时其总误差也最小，但由于各子区域划分是相互制约、相互影响的，由开始时它们之间相互重叠，到最后各子区域不重叠的过程，是漫长的过程。因此，这过程的收敛速度，甚至找到使各子区域误差和为全局最小的区域划分，都与码本的初始好坏有关。

模糊矢量量化算法训练过程是一个聚类的过程，聚类的目标是将数据聚类，使得类内的类似性最大，而类与类之间的相似性尽量小。但在模糊矢量量化法中，它们的相似程度由隶属度大小表示，不完全是由1和0表示，而是由0和1之间的数字表示，这样表示相似程度比LBG算法更精确、更完善。在应用中，FVQ的缺陷在于：

(1)在算法中，码本的初始值选定的好坏直接影响聚类的结果，有可能算法收敛到一个局部的极值点，从而使得无论迭代多少次也不能满足类中的数据的距离小于一个特定值的要求，另外如果随机指定的初值分布处于多个初值在某一个极值点附近，而某些极值点附近无初值，则就会漏掉可能的聚类点。

(2)聚类的个数需要指定。针对以上缺陷，为了获得高性能码本，不得不寻找合适的初始码本，这包括极值点附近无初值点和极值点附近太多初值点的改善。我们提出了一种比较合适的最小距离黄金聚类算法来生成初始码本。我们知道，同类码本不仅要求形状相似，而且要求它们之间的距离比较小，这类似地貌学的分类，不仅形状雷同，而且它们的海拔大致相同。因此，以它们最小距离合并成一类。参考最优分割法——黄金分割，合并规则是根据它们分别与别的码本距离之和大小占的比例。黄金分割法的计算复杂度远远低于分裂法，效果也有提高，具体步骤如下：

(1)设迭代次数k=0，全体训练集都是码本，则初始码本大小为M，计算各码本距离，得到一个M×M距离矩阵Dk(Dk一定为对角元素为0的对称矩阵，即dij=dji，djj=0)。

(2)合并码矢产生新码本。寻找Dk矩阵中的最小值，设

其为dij。分别求第i、j列的数之和为 ，根据

它们大小的比较，决定新码本的重心偏向第i码本还是偏向第j码本，利用黄金分割法求得新码本。

若 ，则新码本的重心偏向第i码

本，新码本矢量为YM－k=0.618Yi+0.318Yj(Yi、Yj分别为第i、j

码本的矢量)；若 ，则新码本矢量Yk=0.5

(Yi+Yj)，再删去第i，j码本对应的两行两列，计算新码本与其他码本之间的距离。然后，在Dk添加最后一行、最后一列新码本YM－k所对应的距离，得到一个(M－k－1)×(M－k－1)维矩阵Dk+1。

(3)k=k+1，若新码本大小M－k等于预定码本大小N，则停止计算，否则转到步骤(2)。

我们以标准图像lena(256×256×8bits)为训练，直接进行矢量量化编码。用PentiumⅢ800CPU，64M内存，非训练集是五幅标准图像(Girl、Boat、Goldhill、Babare、Babood)的平均值。用分裂法和最小距离黄金聚类法的两种实验结果作一对比。表4.1列出了实验结果对比数据。

从表4.1中可以看出，最小距离黄金聚类法比分裂法在编码时间上有所减小，在峰值信噪比上也有不少的提高；但是在高压缩比时，采用最小距离黄金聚类法，重构图像效果不好，方块效应明显，如图4.1所示。表4.1矢量量化编码实验结果对比图4.1实验结果

4.5实验模拟和分析

本实验所采用的6幅标准测试图像均为512×512×8bits的灰度图像，分别为Lena、Girl、Goldhill、Boat、Barbara和Babood图像，如图4.2所示。通过其VQ编码结果来比较不同方法的压缩效果。图4.2标准图像在矢量量化编码中，将每幅图像划分为16384个4×4块,码本为256。在FVQ方法中，m=4，e=10－4，e′=10－2。采用lena和Golhill图像为训练图像，其他的图像为非训练图像。所有数值都采用平均值。表4.2是各种码本训练方法的性能比较。表4.2各种码本训练方法的性能比较

由表4.2可见，除了需要的时间多于LBG方法以外，从总体上说，FVQ方法优于LBG方法。由此可以看出，FVQ方法的计算量大于LBG方法，即FVQ方法计算比较复杂。分裂法无论在时间性能还是在PSNR上都不如最小距离黄金聚类法。从图4.3可以看出，视觉上分不出明显的差异，但是最小距离黄金聚类法与FVQ方法重构的图像质量略好于分裂法与LBG方法重构的图像质量。图4.3实验结果 4.6基于小波变换的矢量量化编码

在图4.1(b)中，可以看出明显的方块效应。为了消除矢量量化技术带来方块效应的现象，进一步提出了一种基于小波变换的矢量量化的混合编码。

用8bit灰度图像进行矢量量化编码，设码本尺寸为M，编码码率为R，矢量的维数为N，则这些变量之间有如下关系式：

即M=2RN。由上式可知，M、R和N之间是相互约束的。当码本尺寸M受限时，编码率和矢量维数均不能太大，这种结果会严重影响矢量量化的性能。因此，在各种矢量量化算法中，码本受限问题都成为编码效率提高的障碍。码本的生成是设计矢量量化系统的一个关键问题。

小波变换具有很好的去相关能力，但与传统变换有本质的区别。在DCT变换中，一般在图像分块的基础上进行，虽然频域的局域性极佳，具有很高的分辨率，但是，时域的局域却很差，即使在整幅图像上进行变换，在变换域中一般都不保留原图像的空间特性，必然造成计算量大，给编码效率带来问题。而小波变换则不同，小波变换能够在整幅图像上进行变换，其计算量虽然比分块基础上的DCT变换略大，但也是在同一个数量级上，而且小波变换的变换域中的每个子带对应一定的频带，并保持了原图像的空间特性，随分解层次的提高，不同分解级的子带图像具有一定的相似性，这些都为编码效率提高奠定了基础。由于传统变换采用图像的分块技术，在高压缩比时难以避免图像的块效应，同时分块也制约了图像压缩比的提高，而小波变换一般不会出现图像的块效应，可以实现高的压缩比。因此，通过小波变换，图像的冗余度和编码复杂度大大减小。小波变换编码的关键在于量化，而根据统计的结果，一般高频的小波系数近似服从均值为0的高斯分布，高频系数存在一定的弱相关，近似为不相关；同一方向的各高频子图在视觉上存在相似的轮廓。由于利用小波变换的特性，提出许多算法，如零树编码、基于塔式网格矢量量化的小波变换编码和空间-频率量化的图像编码等方法，取得了可喜的成绩。

小波图像的特点：LLj是图像的小波变换的低频部分，即能量主要集中部分。HLj、LHj和HHj是图像的小波变换的高频部分，其主要包含了图像的边缘、轮廓和某些纹理的信息，代表图像的细节变化。HL1、HL2和HL3可以认为是在水平方向用高通滤波器，而垂直方向用低通滤波器得到的，它反映了垂直方向的边缘信息，从不同的分辨率上反映本身自相似性。因此其小波变换后保留了原图像的空间局部特性，从而在HL1、HL2、HL3之间视觉上存在相似性，体现了相似的边缘和纹理特性。本书以一方向为整体，进行矢量量化编码。由于它们是图像同一个边缘、轮廓和纹理信息在一方向、不同尺度和不同分辨率下由细到粗的描述，它们之间存在着一定的关系，其中它们在这些频带中对应边缘、轮廓和纹理相对位置都是相同的，这样小波图像为最小距离黄金法编码信息提供了理论基础。但是，由前面讨论可知：各级小波变换的能量各不相同，各层的距离不能等同看待，必须根据信息大小来加权。这样就较好地体现系数之间的相关性和重要地位，避免了由于小波图像系数空间的松散分布所带来的编码冗余和复杂度。子图在编码中的权重值应通过多幅图像的编码实验得到的。同一方向相邻