基于组合码字的矢量量化编码算法*

南京大学学报(自然科学版) ›› 2011, Vol. 47 ›› Issue (5): 559–565.

基于组合码字的矢量量化编码算法*

胡云1,2，谢俊元1，王崇骏1**

出版日期:2015-04-29 发布日期:2015-04-29
作者简介: (1南京大学计算机科学与技术系，南京，210093; 2.淮海工学院计算机工程学院，连云港，222005)
基金资助:
国家自然科学基金(61105069)，江苏省自然科学基金(BK2008190)

A combinational encoding algorithm for vector quantization

Hu Yun ^1,2，Xie Jun-Yuan¹，Wang Chong一Jun¹

Online:2015-04-29 Published:2015-04-29
About author: (1 .Department of Computer Science and Technology, Nanjing University, Nanjing, 210093，China
2. School of Computer Engineering, Huaihai institute of Technology, Lianyungang, 222005，China)

摘要/Abstract

摘要： 传统的矢量量化编码方法总是将待编码矢量以码书中唯一的最匹配码字作为其近似输出矢量，以实现数据压缩的目的.这种方法对远离码字的矢量无法避免显著的误差.木文提出组合编码的矢
量量化方法，其思想是对远离码字的矢量进行主辅组合编码，对主码字编码造成的误差通过辅码字加以补偿.实验表明，该方法在很小降低压缩比率的条件卜显著提高了矢量编码精度，能够在信号处理等领
域发挥有效作用.

Abstract: Vector quantization is an important technology in the field of information and coding theory. Traditionally, all the vector quantization algorithms encode a vector by assigning just one optimal matching codeword
as its representative to attain the objective of data compressing. However, for vectors lay far away from the code words, this strategy will introduce significant error inevitably because of the intrinsic shortage of code words in the
codebook, In depth encoding experiments using LBU algorithm on standard test images we have conducted showed that remarkable errors were introduced at the encoding stage，which was unrecoverable after image encoding
finished.This paper put forward a combinational encoding algorithm which employs main and adjuvant code words to encode such kind of vectors. At the encoding stage，the algorithm first finds the optimal code word for the vector
and，meanwhile, computes the mean error introduced threshold threshold. for the error, the scheme square filters out vectors that by the vector quantization algorithm. by setting have mean square errors large than the admitted
For such kind of vectors，a scheme of error adjusting is proposed. In the scheme，all code words along with the residual vector arc normalized onto the unit sphere and the most similar unit vector can be found. by finding
the most similar unit vector, the prospective adjuvant codeword can be determined. With the prospective adjuvant codcword in hand，error introduced by the optimal main codeword can be adjusted by a factor of such prospective
adjuvant codeword. Scheme on how to find prospective adjuvant codeword and value of factor is discussed in detail in the paper. Sets of experiments show that our method can notably improve the accuracy of vector encoding with a
small portion lose of the rate of compressing.The purposed encoding strategy is worthy for further research in such fields as signal processing and image compressing.

胡云1,2，谢俊元1，王崇骏1**. 基于组合码字的矢量量化编码算法*[J]. 南京大学学报(自然科学版), 2011, 47(5): 559–565.

Hu Yun ^1,2，Xie Jun-Yuan¹，Wang Chong一Jun¹
. A combinational encoding algorithm for vector quantization
[J]. Journal of Nanjing University(Natural Sciences), 2011, 47(5): 559–565.

参考文献

[1]Gcrsho A，Gray R M. Vector quantization and signal compression. Boston; Kluwer Academic Publishers. 1991，307一372.
[2] Sikora T.Trends and perspectives in image and video coding. Proceedings of IEEE Digital Ob ject Identifier, 2005，93(1):6一17.
[1]Linde Y，Yuzo A，Cray R M. An algorithm for vector quantizer design, IEEETransactions on Communications, 1980，28(1):702一710.
[2]K aukoranta T，Franti P，Ncvalainncm OVee for quantization by lazy pairwise nearest neigh bor method. Optical Engineering, 1999，28 (11):1862-1868.
[3]Huang 8 H，Chen S H. Fast encoding algo- rithm for VQ-based image coding. Electronics Letters，1990，26(19):1618一1619.
[4]Wu K S, Lin J C. Fast VQ encoding by an effi- cient kick-out condition, IEEE Transactions on Circuits and Systems, 2000，10(1):59一62.
[5]Pan J S, Lu Z M, Sun S H. An efficient enco- ding algorithm for vector quantization based on sub-vector technique, IEEE Transactions on Image Procession, 2003，12(3):265一270.
[6]Chen Y，Hwang B, Chiang C. Fast VQ code book search algorithm for grayscalc image cod ing, Image and Vision Computation, 2008，26 (5). 657一666.
[7]Kekre H B, Sarode TK. Br-levl vector quanti zation method for codebook generation. Raise H.The 2^nd international Conference on Emer ging Trends in Engineering and Technology Nagpur India. IEEE Computer Society, 2009:866-872.
[8]Kekre H B, Shah K，Sarode T K，et al. Per- formance comparison of vector quantization technique:KFCG with LBG, existing trans forms and PCA for face recognition, lnterna- tional Journal of Information Retrieval，2009，2 (1).64 ~71
[9]Yang MT，Ding J P，Wang Q H. A new enco- ding method for reducing quantizatiorrerror of phase-only computci-generated holograms. Journal of Nanjing University(Natural Sci- ences),2002, 38(6):842-849(杨茂FR , J剑
平，土其和.减小纯位相型计算全息图量化误差的一种新编码方法.南京大学学报(自然科学),2002，38C6} :8r12一8r19}.
[10]Syafalni 1，Sallch M F M. Multistage lattice vector quantization with adaptive normalization for wavclet based image coding. European Jour- nal of Scientific Research, 2010，4l(1): 48一56.
[11]Chen Y J，Guan T，Wang C. Approximate nca rest neighbor search by residual vector quantiza tion. Sensors，2010，10(12):11259一11273.
[12]Bouttcfroy P，Bouzcrdoum I. M, Bcghdadi A，et al. Multi-resolution mcarrshift algorithm for vector quantization. James A S, Michael W M. Proceedings of the 2010 Data Compression Con- ference. Washington DC，USA, IEEE Comput- cr Society, 2010，523一531.
[13]Barnes C F, Rizvi S A，Nasrabadi N M. Ad vances in residual vector quantization;A re view. IEEE Transactions on Image Processing,1996，5(2):226一262.
[14]Chatterjee S, Sreenivas T V. Reduced complex- ity two stage vector quantization. Digital Signal Processing, 2009，19(3):176一190.
[15]Barnes C F, Rizvi S A，Nasrabadi N M. Ad vances in residual vector quantization A re view. IEEE Transactions on Image Processing,1996，5(2):226一262.
[16]Chattcrjee S, Srccnivas T V. Reduced complex- ity two stage vector quantization. Digital Signal Processing, 2009，19(3):176一190.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed