资源描述：
《一种矢量量化编码的快速搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第29卷第3期光学技术Vol.29No.32003年5月OPTICALTECHNIQUEMay2003文章编号:10021582(2003)03032304一种矢量量化编码的快速搜索算法孙文军,郝志航(中国科学院长春光学精密机械与物理研究所,长春130022)摘要:提出了一种矢量量化编码的快速匹配算法。利用码书的拓扑结构和柯西施瓦兹不等式的性质推导出了消除不必要匹配操作的条件,并根据这个条件提出了快速搜索算法。实验结果表明,该算法不仅明显降低了矢量编码过程的复杂程度,同
2、时也保证了与全搜索编码相同的图像编码质量。与其它搜索方法的操作次数和存储空间进行了比较。关键词:矢量量化;L2范数塔形结构;快速搜索匹配;图像压缩中图分类号:O157.4;TP391文献标识码:AAfastsearchalgorithmforvectorquantizationencodingSUNWenjun,HAOZhihang(CangchunInstituteofOptics,FineMechanicsandPhysicsChineseAcademyofSciences,Chanchun130022,China)Abstrac
3、t:AfastalgorithmtospeeduptheclosestcodewordsearchmatchingprocessinVQ(vectorquantization)encodingispresented.ByusingpyramidstructureofthecodebookandCauchySchwarzinequality,aconditionofremovingunnecessarymatchingoperationsfromthesearchprocedurewasderived,thenthefastsearcharit
4、hmeticisproposedbasedonthisremovingcondition.Experimentresultsshowthattheproposedsearchalgorithmsignificantlyreducestheencodingcomplexityaskeepingthesameencodingqualityasthatoffullsearcharithmetic.Thecomparisonofproposedalgorithmwithexistingsearchalgorithminthenumberofoperatio
5、nandmemoryspaceisgiven.Keywords:vectorquantization;L2normpyramid;fastsearchmatching;imagecompression以解码了。1引言由于编码器为了找到最佳匹配的码字,通常要矢量量化在语音和图像编码中得到了广泛的应计算输入矢量与码书中的所有码字之间的欧氏距离用。由于其良好的率失真性能,使信号得到了有效(全搜索法FullSearchAlgorithm),所以每个输入矢K地压缩。通常矢量量化被定义为k维欧氏空间R量要进行K#N次操作,而且随矢量的维数和码书中的矢量Q
6、到该空间有限子集Y的映射,Y=长度的增加而增加。由于算法复杂度的影响,使得{yi},i=1,2,,N为复制的矢量集,被称为码本矢量量化在实时压缩系统中的应用受到限制。码书,N为码本长度。首先图像被分为一些块子集为了解决上述问题,已有很多文献提出了快速(用矢量表示),然后每个k维输入矢量x={x1,搜索匹配方法。这些方法大致可分为有损和无损两x2,,xk}与码本中的码字进行比较,得到最佳匹类:有损方法一般通过限制码书的长度来减小计算配,即量化完成Q(X)=ybm=(ybm1,ybm2,,复杂度,得到的压缩效果比全搜索方法还要差;无损ybmk)。
7、x与yiY之间的失真定义为方法的压缩效果与全搜索法压缩效果持平。Bei和KGray通过改进局部距离来消除PDE(partialdistance22d(x,yi)=!(xk-yik)=∀x-yi∀(1)elimination),提出了排除所有相对于输入矢量的局k=1x的最佳匹配ybm应满足部失真大于当前所能提供的最小失真的所有码字。d(x,ybm)=mind(x,yi)(i=1,2,,N)(2)一般情况下,用PDE与其它有效的编码方法相结合只要传输最佳匹配码字ybm的索引代替矢量传来进一步加速编码过程。另外,三角不等式消除到解码器便得到了压
8、缩。解码器与编码器有相同的TIE(triangleinequalityelimination)一般被用来减小码书,解码器只
