矢量量化编码

矢量量化编码1.引言矢量量化是一种高效的数据压缩技术，它具有压缩比大、解码简单和失真较小等优点。自从1980年提出矢量量化器(VectorQuantizater)码书设计的LBG算法Lindeetal(1980)以来，矢量量化(VectorQuantization)技术Gray(1984)已经成功地应用到图像压缩和语音编码中。矢量量化压缩中最核心的技术是码书的设计，码书的优化性直接影响到压缩效率和图像复原质量。这里主要对码书设计算法进行讨论。首先介绍了经典的LBGf法及其在图像压缩中的应用；然后，针对LBGf法的不足，结合图像处理的特点，提出了改进的覆盖聚类算法，有效改善了系统性能。2.码书的设计码书设计是矢量量化压缩系统的关键环节。码书设计得越优化，矢量量化器的性能就越好。实际中，不可能单独为每幅待编码的图像设计一个码书，因此通常是以一些代表性图像构成的训练集为基础，为一类图像设计一个最优码书。从数学的观点看，矢量量化中的码书设计，实质是把系统的率失真函数看成目标函数，并使之在高维空间中成为最小的全局优化问题。假设采用平方误差测度作为失真测度，训练集中的矢量数为M目的是生成含N(NM个码字(码矢量)的码书。码书设计过程就是寻求把M个训练矢量分成N类的一种最佳方案(使均方误差最小)，而把各类的质心矢量作为码书的码字。可以证明，各种可能的码书个数为(1/N!)艺(一1)(N-i)CNiM，其中(为组合数。通过测试所有码书的性能可得到全局最优码书。然而，在N和M比较大的情况下，搜索全部码书是根本不可能的。为了克服这个困难，各种码书设计方法都采取搜索部分码书的方法得到局部最优或接近全局最优的码书。因此，研究码书设计算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码书以提高码书性能，并尽可能减少计算复杂度。3LBG算法描述经典的码书设计算法是LBG算法它是Y.Linde,A.Buzo与RMGray在1980年推出的，其思想是对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书A0,最后把训练序列按码书A0中的元素分组,找出每组的中心,得到新的码书,转而把新码书作为初始码书再进行上述过程,直到满意为止。LBG算法描述如下：(1) 初始化。给定码书有N个码字，失真阈值E,一个训练序列Xj;j=O,?,M一1，某个初始N级码本A0=yi=1,?,N，令=0,D-仁乂。给定An=yi;i=1,?,N，找到训练序列xj;j=0,?M一1关于An的最小失真划分P(A)=Si;i=1,?,N，其中Si=xj:d(xj,yj)=limd(xj,yj)，对任意L=1,2,?,N,计算出总平均失真Dn二D(An,P(An)=(1/M)艺limd(xj,y)。如果(Dn-1一Di)/Die,且An为最终的码本；停止，否则继续。(4)不改变空间划分，只修正各组的中心，得到新的码书X(P(An)=；X(sj);j=1,?,N,使得新码书对于当前向量空间划分的总失真最小。对于均方差误差标准,X(Sj)是当前向量空间划分的欧氏中心，即X(Sj)=1/(|Sj|),其中|sj|表示Sj中训练样本向量的个数。如果|Sj|=0,则令X(Sj)=yj,即码字不变。(5)An+i=X(sj)，令n=n+1，并转去执行步骤(2)。算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件,是劳埃德算法在矢量空间的推广,其特点为物理概念清晰、算法理论严密及算法实现容易。但是,它有3个主要缺点：在每次迭代的最佳划分阶段,从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算。(1) 初始码书的选择影响码书训练的收敛速度和最终码书的性能。(2) 码书的自适应能力不强。码书设计的第一个缺点可采用各种快速码字搜索算法来解决,但这些算法无法改善码书的性能。4改进的覆盖聚类算法由上所述，LBG!法是一个不断迭代、不断调整聚类中心的过程,聚类速度慢，初始点的选取对聚类结果的影响大。因此，针对LBG算法的不足和图像压缩的特征,采用另一种算法覆盖聚类算法。覆盖算法基本思想是求出一组领域,将相似度大的样本聚合在一起,将相似度小的样本分隔开来,达到聚类的效果。即给定一输入集K=X1,X2,?,Xk(K是维欧式空间的点集)，设K分为S个子集Kl=x1，x2，?Xm(1),Ks=Xm(s-1)+1，?,Xk每个子集就是一个覆盖。对于领域覆盖比较少的样本点采用最短距离法(这里采用欧式距离)进行聚类，这样形成椭球形覆盖领域，即选择圆心距离最近的一对覆盖合并成一个新覆盖。计算新覆盖和其他覆盖的圆心的距离，再将距离最近的两个覆盖合并。根据实际需要，重复以上合并步骤，每次减少一个覆盖，最终得到合理的覆盖划分，且所有相似点分布在一个领域(球形或者椭球形)。参照上面的聚类准则和欧式距离函数，并根据图像压缩特点和实际处理图像的情况，归纳出如下的改进覆盖聚类算法：(1) 求所有矢量的重心，矢量重心用该矢量中所含像素点灰度值的平均值来表示；取一个矢量，求此矢量重心与其它未聚类矢量重心的距离，找出最小距离对应的矢量作为类覆盖的圆心center；以这个最小距离的102倍(倍数可以根据实际情况改变)作为半径r，形成一个球覆盖，即根据各矢量重心将相应的矢量归于此类，同时记录类中的个数；求这个类的质心(质心定义与LB(算法中的相同)，以此得到一个码矢量和其对应的矢量；找离当前覆盖的圆心最远的矢量作为下一步覆盖的圆center；重复(2)一(6)直到所有的样本全部覆盖结束；对于包含点比较少的覆盖采用最短距离法合并，具体步骤如下： 对于要用最短距离法合并的覆盖，计算出两覆盖的圆心的距离；将离得最近的两个覆盖合并为一个新覆盖；更新其它覆盖与新覆盖的最短距离；根据实际需要，重复、步，确定最后的聚类数。(2) 结束。5实验结果及分析实验条件：矢量维数为4，以训练集中的13幅图象作为产生码书的图像，对“cman进行处理。其中产生码书时，请根据你的具体情况输入你所需要的训练集个数。实验环境：微型计算机：系统：MicrosoftWindoWSCPProfessional版本2002。编译平台：matlab6.5实验结果如图所示決Edt皆Insert世rdo背岸b4Flgju阳No.1产生码本的执行时间为7.331000secs测试图象的时间t为15secs压缩比：接近5咅；6.实验结论改进的覆盖聚类算法的优点主要解决了LBG!法难以解决的问题：初值的选取对系统的影响和聚类速度慢等问题。该算法是覆盖后求重心，再对覆盖做调整，得到新覆盖。因此，初值的选择对系统性能影响小于LB（算法对系统产生的影响；覆盖聚类大量减少了迭代次数，且只用最短距离法处理少量样本，聚类速度有较大提高。另外，覆盖聚类算法还可在事先不需知道聚类数目的情况下，根据实际需要确定聚类数目。