矢量量化编码码字搜索探究

1、矢量量化编码码字搜索探究【摘要】以矢量量化技术在图像压缩领域的应用作为研究 目标，详细阐述了矢量量化码字搜索技术，分析了现有典型 的穷尽搜索(full search,fs)算法，并针对fs算法的不足, 提出一种部分失真搜索(partial distortion search,pds) 算法，减少了计算的时间复杂度，缩短了程序运行时间。实验 结果表明，相对于穷尽搜索方法，计算量有明显降低，计算时 间显著减少。【关键词】矢量量化图像压缩码字搜索【中图分类号】0183【文献标识码】a【文章编号】 1009-9646(2008)08(b)-0227-021引言矢量量化(vector quantizat

2、ion)是一种高效的数据压 缩技术，自从1980年提出矢量量化器(vector quantizater) 码书设计的lbg算法2以来，矢量量化技术已经成功地应用 到图像压缩中。矢量量化压缩中最核心的技术之一是码字搜 索，码字的搜索速度直接影响到编码时间。这里主要研究矢 量量化的码字搜索算法，它对码书结构3不作任何限制，但 它能减少矢量量化器的时间复杂度。矢量量化编码过程最终 归结为在给定码书中搜索与输入矢量最匹配码字的过程。2码字搜索矢量量化码字搜索算法是指在码书已经存在的情况下,对于给定的输入矢量，在码书中搜索与输入矢量之间失真最 小的码字。给定码书，其中n为码书尺寸，如果矢量x与码字 yi

3、之间的失真测度为d(x,yi),则码字搜索算法就是找到码 字yp使。如果采用平方误差测度，对于k维矢量，每次失真 计算需要k次乘法、n(2k-1)次加法和n-1次比较。可以看 出，计算复杂度由码书尺寸和矢量维数决定。对于大尺寸码 书和高维矢量，计算复杂程度将很大。研究码书搜索算法的 主要目的就是寻求快速有效的算法以减少计算复杂程度，且 尽量使算法易于用硬件实现。穷尽搜索(full search,fs)算法1是一种最原始最直 观的最近邻码字搜索算法，它需要计算输入矢量与所有码字 之间的失真并通过比较找出失真最小的码字。由于每次失真 计算需要k次乘法,2k-1次加法，故为了对矢量x进行编码需要nk

4、次乘法,n(2k-l)次加法和n-1次比较。由此可见,fs算 法的计算复杂度由码书尺寸和矢量维数决定。髙效率矢量量 化编码(或识别)系统往往采用大码书和高维矢量，这时计算 复杂度将非常大，故减少码字搜索的计算负担是非常必要 的。此外,fs算法的编码比特率是固定的，为(log2n)/k03部分失真搜索算法部分失真搜索算法1是一种简单有效的最近邻搜索算 法。在搜索过程中，它通过引入一个提前退出条件，以便较早 地终止输入矢量和码字之间的失真计算。它的基本思想是: 在计算某个码字与输入矢量之间失真测度的过程中始终判 断累加的部分失真是否已超过目前的最小失真，一旦超出则 终止该码字与输入矢量之间的失真计

5、算。其基本原理为：假定目前最小失真为若(3-1)m(3-2)在计算码字yi和输入矢量x的失真过程中，若满足不等 式(3-1),则yi肯定不是x的最近码字，从而可以停止该失真 计算而转入下一个码字的判断。pds算法的效率在于：它以增 加s次比较换得减少k-s次相乘和2(k-s)次相加。pds算法 的具体步骤如下：令。(2) 若i>n-l,终止算法,yp为矢量x的最近码字,p为码 字索弓1；否则另d=0o(3) o(4) 若d>dmin,则i=i+l,转步骤2；否则转步骤5。(5) 若1部分失真搜索算法的效率是很有限的，但它不需 要额外存储空间，没有附加的乘法计算量°pds常

6、常用于许多 快速搜索算法的最后一步，以排除其他方法已经无法排除的 码字。pds算法的效率可通过码字排序进一步提高。这需要在码书设计时根据训练矢量计算每个码字的概率pi 最接近训练矢量的码字yi的概率。码书中的码字按照pi递 减的顺序排列。这种安排可增加人们在最初阶段找出最近邻 码字的概率,从而有利于节省计算时间。3. 1改进的部分失真搜索算法由上述讨论可知,pds算法是简洁有效的搜索算法，它通 常用来排除其他算法不能排除的码字，这种方法以增加s次 比较的代价换得运算量减至k-s次乘法和2(k-s)次加法。这 种算法适用于计算机体系，因为相对于乘法运算复杂度而言, 比较运算复杂度可忽略。然而,p

7、ds不太适于处理器体系，其 比较运算量相对较大。为此，文献提出一中基于动态程序设 计的改进部分失真搜索算法一一dppds算法。这里要介绍的 是pds的另一种改进方法，该算法可确定从哪一维开始进行 比较时最佳的，即在此之前一直累加部分失真而不对dmin和 部分失真进行比较。令r为比较计算时间与维失真计算时间 的比值，则改进的部分失真搜索算法的训练过程可描述为:令1二0(2) 令 i=0, dmin=co(3) 计算码字yi同训练矢量xl间的失真do对于码字yi,若从分量yij初开始允许比较，计算所能节省的维失真数mijl和所增加的比较次数cijlo令。(4) 若 i (5)若 1这里t为训练矢量

8、数目。若则对码字yi而言，在实际码字搜索算法中，比较应从第i (i)维开始。将此改进的pds算法同基于动态程序设计技术的pds方法相结合，可得到一个更高效的算法，即改进的dppds算法。改进的dppds算法和dppds算法的差别在于：在改进的dppds 算法中，“比较所应开始的维”由每个码字分别决定，而不 是所有码字都从相同维处进行比较。假定sij为在码字yi 的分量yij处同t个训练矢量的成功比较矢量数。若在码字 yi的分量yij处进行比较操作，则所需的维失真计算数目为(3-3) 式中，k是维数,1=0,1,n-1,n为码字个数若先前的比较在分量yij处进行，则在码字yi的分量yit处进行比

9、较所需的维失真计算次数如下：(3-4) 所以，第i个码字的计算优势在于 (3-5)然后，把动态程序技术与式(3-5) 起用到(3-6)中，即 找出合适的维j以使下式最大：(3-6) 式中，。3.2扩展部分失真搜索算法文献提出了一种pds算法的改进型是，即扩展部分失真 搜索(extended pds,epds)算法。该算法能最大限度地减少 乘法运算,从该意义上说epds算法是一种最优的pds算法。 epds算法可描述如下：(1) 令li=o,计算输入矢量x的第0维分量xo同码字yi 的第0维分量yio间的失真其中，n为码字个数,li表示码字yi的第li维。找出(3)若is二k-l,则码字ys为最

10、佳匹配码字并终止程序; 否则令ls=ls+l,计算输入矢量x同码字ys间的第is维失真, 将结果同ds相加，转步骤2。其中，k为输入矢量和码字的维 数。epds算法适用于计算机体系，因为其比较运算的复杂度 同乘法运算相比可以忽略。然而,epds不太适合于某些dsp 处理器，例如tms320系列处理器，因为其比较运算的计算量 比较大。4仿真结果在不同的码书尺寸和矢量维数下，表1比较了 fs算法和 pds算法的编码时间和平均失真计算。码书尺寸为256,矢量 维数为4x4或8x8,所有算法均用于256灰度512x512 lena图像编码。实验结果表明,pds算法的编码时间和平均失真都有明 显减小。参考文献1 孙圣和，陆哲明.矢量量化技术及应用m.北京: 科学出版社,2002.2 linde ,a. buzy, r. m. gray. an algorithm for vector