论文部分内容阅读
【摘要】以矢量量化技术在图像压缩领域的应用作为研究目标,详细阐述了矢量量化码字搜索技术,分析了现有典型的穷尽搜索(full search,FS)算法,并针对FS算法的不足,提出一种部分失真搜索(partial distortion search,PDS)算法,减少了计算的时间复杂度,缩短了程序运行时间。实验结果表明,相对于穷尽搜索方法,计算量有明显降低,计算时间显著减少。
【关键词】矢量量化 图像压缩 码字搜索
【中图分类号】O183 【文献标识码】A 【文章编号】1009-9646(2008)08(b)-0227-02
1 引言
矢量量化(Vector Quantization)是一种高效的数据压缩技术,自从1980 年提出矢量量化器(Vector Quantizater) 码书设计的LBG算法[2]以来,矢量量化技术已经成功地应用到图像压缩中。矢量量化压缩中最核心的技术之一是码字搜索,码字的搜索速度直接影响到编码时间。这里主要研究矢量量化的码字搜索算法,它对码书结构[3]不作任何限制,但它能减少矢量量化器的时间复杂度。矢量量化编码过程最终归结为在给定码书中搜索与输入矢量最匹配码字的过程。
2 码字搜索
矢量量化码字搜索算法是指在码书已经存在的情况下,对于给定的输入矢量,在码书中搜索与输入矢量之间失真最小的码字。给定码书,其中N为码书尺寸,如果矢量x与码字yi之间的失真测度为d(x,yi),则码字搜索算法就是找到码字yp使。如果采用平方误差测度,对于k维矢量,每次失真计算需要k次乘法、N(2K-1)次加法和N-1次比较。可以看出,计算复杂度由码书尺寸和矢量维数决定。对于大尺寸码书和高维矢量,计算复杂程度将很大。研究码书搜索算法的主要目的就是寻求快速有效的算法以减少计算复杂程度,且尽量使算法易于用硬件实现。
穷尽搜索(Full Search,FS)算法[1]是一种最原始最直观的最近邻码字搜索算法,它需要计算输入矢量与所有码字之间的失真并通过比较找出失真最小的码字。由于每次失真计算需要k次乘法,2k-1次加法,故为了对矢量x进行编码需要Nk次乘法,N(2k-1)次加法和N-1次比较。由此可见,FS算法的计算复杂度由码书尺寸和矢量维数决定。高效率矢量量化编码(或识别)系统往往采用大码书和高维矢量,这时计算复杂度将非常大,故减少码字搜索的计算负担是非常必要的。此外,FS算法的编码比特率是固定的,为(log2N)/k。
3 部分失真搜索算法
部分失真搜索算法[1]是一种简单有效的最近邻搜索算法。在搜索过程中,它通过引入一个提前退出条件,以便较早地终止输入矢量和码字之间的失真计算。它的基本思想是:在计算某个码字与输入矢量之间失真测度的过程中始终判断累加的部分失真是否已超过目前的最小失真,一旦超出则终止该码字与输入矢量之间的失真计算。其基本原理为:
假定目前最小失真为
,
若 (3-1)
则(3-2)
在计算码字yi和输入矢量x的失真过程中,若满足不等式(3-1),则yi肯定不是x的最近码字,从而可以停止该失真計算而转入下一个码字的判断。PDS算法的效率在于:它以增加s次比较换得减少k-s次相乘和2(k-s)次相加。PDS算法的具体步骤如下:
(1)令。
(2)若i>N-1,终止算法,yp为矢量x的最近码字,p为码字索引;否则另d=0。
(3)。
(4) 若d>dmin,则i=i+1,转步骤2;否则转步骤5。
(5)若l部分失真搜索算法的效率是很有限的,但它不需要额外存储空间,没有附加的乘法计算量。PDS常常用于许多快速搜索算法的最后一步,以排除其他方法已经无法排除的码字。PDS算法的效率可通过码字排序进一步提高。这需要在码书设计时根据训练矢量计算每个码字的概率Pi------最接近训练矢量的码字yi的概率。码书中的码字按照Pi递减的顺序排列。这种安排可增加人们在最初阶段找出最近邻码字的概率,从而有利于节省计算时间。
3.1 改进的部分失真搜索算法
由上述讨论可知,PDS算法是简洁有效的搜索算法,它通常用来排除其他算法不能排除的码字,这种方法以增加s次比较的代价换得运算量减至k-s次乘法和2(k-s)次加法。这种算法适用于计算机体系,因为相对于乘法运算复杂度而言,比较运算复杂度可忽略。然而,PDS不太适于处理器体系,其比较运算量相对较大。为此,文献提出一中基于动态程序设计的改进部分失真搜索算法——DPPDS算法。这里要介绍的是PDS的另一种改进方法,该算法可确定从哪一维开始进行比较时最佳的,即在此之前一直累加部分失真而不对dmin和部分失真进行比较。令r为比较计算时间与维失真计算时间的比值,则改进的部分失真搜索算法的训练过程可描述为:
(1)令l=0
(2)令i=0,dmin=∞
(3)计算码字yi同训练矢量xl间的失真d。对于码字yi,若从分量yij初开始允许比较,计算所能节省的维失真数Mijl和所增加的比较次数Cijl。令。
(4)若i(5)若l
这里T为训练矢量数目。若
则对码字yi而言,在实际码字搜索算法中,比较应从第I(i)维开始。
将此改进的PDS算法同基于动态程序设计技术的PDS方法相结合,可得到一个更高效的算法,即改进的DPPDS算法。改进的DPPDS算法和DPPDS算法的差别在于:在改进的DPPDS算法中,“比较所应开始的维”由每个码字分别决定,而不是所有码字都从相同维处进行比较。假定Sij为在码字yi的分量yij处同T个训练矢量的成功比较矢量数。若在码字yi的分量yij处进行比较操作,则所需的维失真计算数目为
(3-3)
式中,k是维数,i=0,1,……N-1,N为码字个数
若先前的比较在分量yij处进行,则在码字yi的分量yit处进行比较所需的维失真计算次数如下:
(3-4)
所以,第i个码字的计算优势在于
(3-5)
然后,把动态程序技术与式(3-5)一起用到(3-6)中,即找出合适的维j以使下式最大:
(3-6)
式中,。
3.2 扩展部分失真搜索算法
文献提出了一种PDS算法的改进型是,即扩展部分失真搜索(Extended PDS,EPDS)算法。该算法能最大限度地减少乘法运算,从该意义上说EPDS算法是一种最优的PDS算法。EPDS算法可描述如下:
(1)令li=0,计算输入矢量x的第0维分量x0同码字yi的第0维分量yi0间的失真
其中,N为码字个数,li表示码字yi的第li维。
(2)找出
(3)若ls=k-1,则码字ys为最佳匹配码字并终止程序;否则令ls=ls+1,计算输入矢量x同码字ys间的第ls维失真,将结果同Ds相加,转步骤2。其中,k为输入矢量和码字的维数。
EPDS算法适用于计算机体系,因为其比较运算的复杂度同乘法运算相比可以忽略。然而,EPDS不太适合于某些DSP处理器,例如TMS320系列处理器,因为其比较运算的计算量比较大。
4 仿真结果
在不同的码书尺寸和矢量维数下,表1比较了FS算法和PDS算法的编码时间和平均失真计算。码书尺寸为256,矢量维数为4×4或8×8,所有算法均用于256灰度512×512 Lena图像编码。
实验结果表明,PDS算法的编码时间和平均失真都有明显减小。
参考文献
[1] 孙圣和,陆哲明. 矢量量化技术及应用[M]. 北京:科学出版社,2002.
[2] Linde ,A.Buzy,R. M. Gray. An algorithm for vector quantizater design[J].IEEE Trans. On Communs,1980,28.
[3] 王姝,卿粼波.矢量量化编码的码书设计研究[J].成都信息工程学院学报,2006,21(6).
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
【关键词】矢量量化 图像压缩 码字搜索
【中图分类号】O183 【文献标识码】A 【文章编号】1009-9646(2008)08(b)-0227-02
1 引言
矢量量化(Vector Quantization)是一种高效的数据压缩技术,自从1980 年提出矢量量化器(Vector Quantizater) 码书设计的LBG算法[2]以来,矢量量化技术已经成功地应用到图像压缩中。矢量量化压缩中最核心的技术之一是码字搜索,码字的搜索速度直接影响到编码时间。这里主要研究矢量量化的码字搜索算法,它对码书结构[3]不作任何限制,但它能减少矢量量化器的时间复杂度。矢量量化编码过程最终归结为在给定码书中搜索与输入矢量最匹配码字的过程。
2 码字搜索
矢量量化码字搜索算法是指在码书已经存在的情况下,对于给定的输入矢量,在码书中搜索与输入矢量之间失真最小的码字。给定码书,其中N为码书尺寸,如果矢量x与码字yi之间的失真测度为d(x,yi),则码字搜索算法就是找到码字yp使。如果采用平方误差测度,对于k维矢量,每次失真计算需要k次乘法、N(2K-1)次加法和N-1次比较。可以看出,计算复杂度由码书尺寸和矢量维数决定。对于大尺寸码书和高维矢量,计算复杂程度将很大。研究码书搜索算法的主要目的就是寻求快速有效的算法以减少计算复杂程度,且尽量使算法易于用硬件实现。
穷尽搜索(Full Search,FS)算法[1]是一种最原始最直观的最近邻码字搜索算法,它需要计算输入矢量与所有码字之间的失真并通过比较找出失真最小的码字。由于每次失真计算需要k次乘法,2k-1次加法,故为了对矢量x进行编码需要Nk次乘法,N(2k-1)次加法和N-1次比较。由此可见,FS算法的计算复杂度由码书尺寸和矢量维数决定。高效率矢量量化编码(或识别)系统往往采用大码书和高维矢量,这时计算复杂度将非常大,故减少码字搜索的计算负担是非常必要的。此外,FS算法的编码比特率是固定的,为(log2N)/k。
3 部分失真搜索算法
部分失真搜索算法[1]是一种简单有效的最近邻搜索算法。在搜索过程中,它通过引入一个提前退出条件,以便较早地终止输入矢量和码字之间的失真计算。它的基本思想是:在计算某个码字与输入矢量之间失真测度的过程中始终判断累加的部分失真是否已超过目前的最小失真,一旦超出则终止该码字与输入矢量之间的失真计算。其基本原理为:
假定目前最小失真为
,
若 (3-1)
则(3-2)
在计算码字yi和输入矢量x的失真过程中,若满足不等式(3-1),则yi肯定不是x的最近码字,从而可以停止该失真計算而转入下一个码字的判断。PDS算法的效率在于:它以增加s次比较换得减少k-s次相乘和2(k-s)次相加。PDS算法的具体步骤如下:
(1)令。
(2)若i>N-1,终止算法,yp为矢量x的最近码字,p为码字索引;否则另d=0。
(3)。
(4) 若d>dmin,则i=i+1,转步骤2;否则转步骤5。
(5)若l部分失真搜索算法的效率是很有限的,但它不需要额外存储空间,没有附加的乘法计算量。PDS常常用于许多快速搜索算法的最后一步,以排除其他方法已经无法排除的码字。PDS算法的效率可通过码字排序进一步提高。这需要在码书设计时根据训练矢量计算每个码字的概率Pi------最接近训练矢量的码字yi的概率。码书中的码字按照Pi递减的顺序排列。这种安排可增加人们在最初阶段找出最近邻码字的概率,从而有利于节省计算时间。
3.1 改进的部分失真搜索算法
由上述讨论可知,PDS算法是简洁有效的搜索算法,它通常用来排除其他算法不能排除的码字,这种方法以增加s次比较的代价换得运算量减至k-s次乘法和2(k-s)次加法。这种算法适用于计算机体系,因为相对于乘法运算复杂度而言,比较运算复杂度可忽略。然而,PDS不太适于处理器体系,其比较运算量相对较大。为此,文献提出一中基于动态程序设计的改进部分失真搜索算法——DPPDS算法。这里要介绍的是PDS的另一种改进方法,该算法可确定从哪一维开始进行比较时最佳的,即在此之前一直累加部分失真而不对dmin和部分失真进行比较。令r为比较计算时间与维失真计算时间的比值,则改进的部分失真搜索算法的训练过程可描述为:
(1)令l=0
(2)令i=0,dmin=∞
(3)计算码字yi同训练矢量xl间的失真d。对于码字yi,若从分量yij初开始允许比较,计算所能节省的维失真数Mijl和所增加的比较次数Cijl。令。
(4)若i(5)若l
这里T为训练矢量数目。若
则对码字yi而言,在实际码字搜索算法中,比较应从第I(i)维开始。
将此改进的PDS算法同基于动态程序设计技术的PDS方法相结合,可得到一个更高效的算法,即改进的DPPDS算法。改进的DPPDS算法和DPPDS算法的差别在于:在改进的DPPDS算法中,“比较所应开始的维”由每个码字分别决定,而不是所有码字都从相同维处进行比较。假定Sij为在码字yi的分量yij处同T个训练矢量的成功比较矢量数。若在码字yi的分量yij处进行比较操作,则所需的维失真计算数目为
(3-3)
式中,k是维数,i=0,1,……N-1,N为码字个数
若先前的比较在分量yij处进行,则在码字yi的分量yit处进行比较所需的维失真计算次数如下:
(3-4)
所以,第i个码字的计算优势在于
(3-5)
然后,把动态程序技术与式(3-5)一起用到(3-6)中,即找出合适的维j以使下式最大:
(3-6)
式中,。
3.2 扩展部分失真搜索算法
文献提出了一种PDS算法的改进型是,即扩展部分失真搜索(Extended PDS,EPDS)算法。该算法能最大限度地减少乘法运算,从该意义上说EPDS算法是一种最优的PDS算法。EPDS算法可描述如下:
(1)令li=0,计算输入矢量x的第0维分量x0同码字yi的第0维分量yi0间的失真
其中,N为码字个数,li表示码字yi的第li维。
(2)找出
(3)若ls=k-1,则码字ys为最佳匹配码字并终止程序;否则令ls=ls+1,计算输入矢量x同码字ys间的第ls维失真,将结果同Ds相加,转步骤2。其中,k为输入矢量和码字的维数。
EPDS算法适用于计算机体系,因为其比较运算的复杂度同乘法运算相比可以忽略。然而,EPDS不太适合于某些DSP处理器,例如TMS320系列处理器,因为其比较运算的计算量比较大。
4 仿真结果
在不同的码书尺寸和矢量维数下,表1比较了FS算法和PDS算法的编码时间和平均失真计算。码书尺寸为256,矢量维数为4×4或8×8,所有算法均用于256灰度512×512 Lena图像编码。
实验结果表明,PDS算法的编码时间和平均失真都有明显减小。
参考文献
[1] 孙圣和,陆哲明. 矢量量化技术及应用[M]. 北京:科学出版社,2002.
[2] Linde ,A.Buzy,R. M. Gray. An algorithm for vector quantizater design[J].IEEE Trans. On Communs,1980,28.
[3] 王姝,卿粼波.矢量量化编码的码书设计研究[J].成都信息工程学院学报,2006,21(6).
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”