Abstract：This paper summarizes various fast codeword search algorithms for vector quantization.These algorithms are classified into several classes according to their characteristics.Simulation,comparisons and analysis are done for various fast algorithms in terms of encoding time,average calculations,extra memory and off-line computation.Some modified algorithms or trains of thoughts are also presented in this paper.
孙圣和, 陆哲明, 刘春和. 快速最近邻矢量量化码字搜索算法[J]. 电子学报, 2001, 29(S1): 1772-1777.
SUN Sheng-he, LU Zhe-ming, LIU Chun-he. Fast Nearest-Neighbor Codeword Search Algorithms for Vector Quantization. Chinese Journal of Electronics, 2001, 29(S1): 1772-1777.
[1] Gersho A,Gray R M.Vector Quantization and Signal Compression[M].Boston:Kluwer Academic Publishers,1992.[2] Linde Y,Buzo A,Gray R M.An algorithm for vector quantizer design[J].IEEE Trans.,1980,COM-28(1):84-95.[3] Bei C D,Gray R M.An improvement of the minimum distortion encoding algorithm for vector quantization [J].IEEE Trans.,1985,COM-33(10):1132-1133.[4] Soleymani M R,Morgera S D.An efficient nearest neighbor search method [J].IEEE Trans.,1987,COM-35(6):677-679.[5] Cheng D,Gersho A,Ramamurthi B,Shoham Y.Fast search algorithms for vector quantization and pattem matching [A].International Conference on ASSP [C],1984:9.11.1-9.11.4.[6] Pan J S,Mclnnes F R,Jack M A.Bound for minkowski metric or quadratic metric applied to VQ codeword search [J].IEE Proceedings-Vision,Image and Signal Processing,1996,143(1):67-71.[7] Orchard M T.A fast nearest neighbor search algorithm [A].International Conference on ASSP [C],1991:2297-2300.[8] Vidal E.An algorithm for finding nearest neighbors in(approximately)constant average time [J].Pattern Recognition Letters,1986,54:145-157.[9] Li W,Salari E.A fast vector quantization encoding method for image compression [J].IEEE Transactions on Circuits and Systems for Video Technology,1995,5(2):119-123.[10] 陆哲明,潘正祥,孙圣和.一种矢量量化码书搜索的快速算法[J].电子学报,2000,28(2):133-135.[11] Guan L,Kamel M.Equal-average hyperplane partitioning method for vector quantization of image data [J].Pattern Recognition Letters,1992:693-699.[12] Pan J S,Huang K C.A new vector quantization image coding algorithm based on the extension of the bound for minkowski metric [J].PatternRecognition,1998,31(11):1757-1760.[13] Lee C H,Chen L H.Fast closest codeword search algorithm for vector quantization [J].IEE Processings-Vision,Image and Signal Processing,1994,141(3):143-148.[14] Ghosh D,Shivaprasad A P.Fast codeword search algorithm for realtime codebonk generation in adaptive VQ [J].IEE Processings-Vision,Image and Signal Processing,1994,144(5):278-284.[15] Baek S J,Jeon B K,Sung K M.A fast encoding algorithm for vector quantization [J].IEEE Signal Processing Letters,1997,4(12):325-327.[16] Xu R S,Lu Z M,Xu X M,Zhang W D.An efficient fast encoding algorithm for vector quantization [J].Journal of Shanghai JiaoTong University,2000,E-5(2):23-27.[17] Torres T,Huguet J.An improvement on codebook search for vector quantization [J].IEEE Trans.,1994,COM-42(2):208-210.[18] Wu K S,Lin J C.Fast VQ encoding by an efficient kick-out condition[J].IEEE Transactions on Circuits and Systems for Video Technology,2000,10(1):59-62.[19] Lin Y C,Tai S C.A fast Linde Buzo Gray algorithm in image vector quantization [J].IEEE Trans.Circuits and Systems l:Analog and Digital Signal Processing,1998,45(3):432-435.[20] Burt P J,Adelson E.The Laplacian pyramid as a compact image code[J].IEEE Trans.,1983,COM-31(4):532-540.[21] Wang L,Goldberg M.Reducod-difference pyramid:a data structure for progressive image transmission [J].Optical Engineering,1989,28(7):708-716.[22] Lee C H,Chen L H.A fast search algorithm for vector quantization using mean pyramids of codewords [J].IEEE Trans.,1995,COM-43(2/3/4):1697-1702.[23] Hwang W J,Chen B Y,Jeng S S.A fast vector quantization encoding method using wavelet transform [J].Pattem Recognition Letters,1997,18:73-76.[24] Pan J S,Lu Z M,Sun S H.Fast codeword search algorithm for image coding based on mean-variance pyramids of codewords [J].Electronics Letters,2000,36(3):210-211.[25] Lee C H,Chen L H.High-speed closest codeword search algorithms for vector quantization [J].Signal Processing,1995,43:323-331.[26] Hwang W J,Jeng S S,Chen B Y.Fast codeword search algorithm using wavelet transform and partial distance search techniques [J].Electronics Letters,1997,33(5):365-366.[27] Vetterli M,Kovaeevic J.Wavelets and Subband Coding [M].New York:Prentice Hall,1995.[28] Lu Z M,Pan J S,Sun S H.Efficient codeword search algorithm based on Hadamard transform [J].Electronics Letters,2000,36(16):1364-1365.
2001, Vol. 29 
