Fast Codevector Search Algorithm for 3-D Vector Quantized Codebook

Authors: H. B. Kekre, Tanuja K. Sarode

Abstract:

This paper presents a very simple and efficient algorithm for codebook search, which reduces a great deal of computation as compared to the full codebook search. The algorithm is based on sorting and centroid technique for search. The results table shows the effectiveness of the proposed algorithm in terms of computational complexity. In this paper we also introduce a new performance parameter named as Average fractional change in pixel value as we feel that it gives better understanding of the closeness of the image since it is related to the perception. This new performance parameter takes into consideration the average fractional change in each pixel value.

Keywords: Vector Quantization, Data Compression, Encoding, Searching.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333236

References:

[1] Jeng-Shyang Pan, Zhe-Ming Lu, and Sheng-He Sun.: ÔÇÿAn Efficient Encoding Algorithm for Vector Quantization Based on Subvector Technique-, IEEE Transactions on image processing, vol 12 No. 3 March 2003.
[2] R. M. Gray.: ÔÇÿVector quantization-, IEEE ASSP Marg, Apr. 1984, pp. 4- 29.
[3] Y. Linde, A. Buzo, and R. M. Gray.: ÔÇÿAn algorithm for vector quantizer design," IEEE Trans. Commun.-, vol. COM-28, no. 1, 1980, pp. 84-95.
[4] A. Gersho, R.M. Gray.: ÔÇÿVector Quantization and Signal Compressio-, Kluwer Academic Publishers, Boston, MA, 1991.
[5] C. D. Bei and R. M. Gray.: ÔÇÿAn improvement of the minimum distortion encoding algorithm for vector quantization-, IEEE Trans. Commun.,vol. 33, no. 10, pp. 1132-1133, Oct. 1985.
[6] Momotaz Begum, Nurun Nahar, Kaneez Fatimah, M. K. Hasan, and M. A. Rahaman: ÔÇÿAn Efficient Algorithm for Codebook Design in Transform Vector Quantization-, WSCG-2003, February 3-7, 2003.
[7] Robert Li and Jung Kim: ÔÇÿImage Compression Using Fast Transformed Vector Quantization-, IEEE Applied Imagery Pattern Recognition Workshop, 2000 Proceedings 29th Volume , Issue , 2000 Page(s):141 - 145.
[8] Zhibin Pan; Kotani, K.; Ohmi, T., ÔÇÿEnhanced fast encoding method for vector quantization by finding an optimally-ordered Walsh transform kernel-, ICIP 2005, IEEE International Conference, Volume 1, Issue, 11-14, Page(s): I - 573-6, Sept. 2005.
[9] Guan, L., and Kamel, M. : ÔÇÿEqual-average hyperplane partitioning method for vector quantization of image data-, Patt. Recognit. Lett., 1992, pp. 693-699.
[10] Lee, H., and Chen, L. H. : ÔÇÿFast closest codevector search algorithms for vector quantization-, Signal Process., 1995, 43, pp. 323-331.
[11] Z. Li, and Z.- M. Lu. : ÔÇÿFast codevector search scheme for 3D mesh model vector quantization-, Electron. Lett., 2008, 44, pp. 104-105.
[12] Princeton University, "3D model search engine", http://shape.cs.princeton.edu
[13] Chin-Chen Chang, Wen-Chuan Wu, " Fast Planar-Oriented Ripple Search Algorithm for Hyperspace VQ Codebook", IEEE Transaction on image processing, vol 16, no. 6, June 2007.
[14] C. C. Chang and T. S. Chen, "New tree-structured vector quantization with closest-coupled multipath searching method," Opt. Eng., vol. 36, no. 6, pp. 1713-1720, Jun. 1997.
[15] C. C. Chang and I. C. Lin, "Fast search algorithm for vector quantization without extra look-up table using declustered subcodebooks," IEE Proc. Vis., Image, Signal Process., vol. 152, no. 5, pp. 513-519, Oct.2005.
[16] C. C. Chang, D. C. Lin, and T. S. Chen, "An improved VQ codebook search algorithm using principal component analysis," J. Vis. Commun. Image Represent., vol. 8, no. 1, pp. 27-37, Mar. 1997.
[17] C. C. Chang, F. J. Shiue, and T. S. Chen, "Tree structured vector quantization with dynamic path search," in Proc. Int. Workshop on Multimedia Network Systems, Aizu, Japan, pp. 536 -541, Sep. 1999.
[18] R. M. Gray and Y. Linde, "Vector quantization and predictive quantizers for gauss-markov sources," IEEE Trans. Commun., vol. 30, no. 2, pp. 381-389, Feb. 1982.
[19] C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, "Fast full-search equivalent encoding algorithms for image compression using vector quantization," IEEE Trans. Image Process., vol. 1, no. 3, pp. 413-416, Jul. 1992.
[20] Y. C. Hu and C. C. Chang, "An effective codebook search algorithm for vector quantization", Imag. Sci. J., vol. 51, no. 4, pp. 221-234, Dec. 2003.
[21] C. H. Lee and L. H. Chen, "High-speed closest codeword search algorithm for vector quantization," Signal Process., vol. 43, no. 3, pp.323-331, May 1995.
[22] L. Torres and J. Huguet, "An improvement on codebook search for vector quantisation", IEEE Trans. Commun., vol. 42, no. 2, pp. 208-210, Feb. 1994.
[23] S. J. Wang and C. H. Yang, "Hierarchy-oriented searching algorithms using alternative duplicate codewords for vector quantization mechanism," Appl. Math. Comput., vol. 162, no. 234, pp. 559-576, Mar. 2005.
[24] S. C. Tai, C. C. Lai, and Y. C. Lin, "Two fast nearest neighbor searching algorithms for image vector quantization," IEEE Trans. Commun., vol. 44, no. 12, pp. 1623-1628, Dec. 1996.
[25] C. Bei, R.M. Gray, ÔÇÿÔÇÿAn improvement of the minimum distortion encoding algorithm for vector quantization--, IEEE Trans. Commun.33, 1985, pp. 1132-1133.
[26] S.H. Huang, S.H. Chen, ÔÇÿÔÇÿFast encoding algorithm for VQ-based image coding--, Electron. Lett. Vol. 26, issue 19, 1990, pp. 1618-1619.
[27] W. Li, E. Salari, ÔÇÿÔÇÿA fast vector quantization encoding method for image compression--, IEEE Trans. Circ. Syst. Vid. Vol 5, 1995, pp. 119-123.
[28] C.H. Hsieh, Y.J. Liu, ÔÇÿÔÇÿFast search algorithms for vector quantization of images using multiple triangle inequalities and wavelet transform--, IEEE Trans. Image Process. Vol. 9, issue 3, 2000, pp. 321-328.
[29] S.W. Ra, J.K. Kim, ÔÇÿÔÇÿA fast mean-distance-ordered partial codebook search algorithm for image vector quantization--, IEEE Trans. Circuits- II, vol. 40, issue 9, 1993, pp. 576-579.
[30] K.S. Wu, J.C. Lin, ÔÇÿÔÇÿFast VQ encoding by an efficient kick-out condition--, IEEE Trans. Circ. Syst. Vid., vol.10, issue 1, 2000, pp. 59- 62.
[31] J.S. Pan, Z.M. Lu, S.H. Sun, ÔÇÿÔÇÿAn efficient encoding algorithm for vector quantization based on subvector technique--, IEEE Trans. Image Process. Vol 12, issue 3, 2003, pp. 265-270.
[32] B.C. Song, J.B. Ra, ÔÇÿÔÇÿA fast algorithm for vector quantization using L2- norm pyramid of codewords--, IEEE Trans. Image Process. Vol. 4, issue 12, 2002, pp. 325-327.
[33] Z. Pan, K. Kotani, T. Ohmi, ÔÇÿÔÇÿFast encoding method for vector quantization using modified L2-norm pyramid--, IEEE Signal Process. Lett. Vol. 12, issue 9, 2005, pp. 609-612.
[34] Y. Chen, B. Hwang, C. Chiang, "Fast VQ codebook search algorithm for grayscale image coding", Image and Vision Compu. 26, 2008, pp. 657- 666.
[35] Dr. H. B. Kekre, Ms. Tanuja K. Sarode, "Binary Tree Based Fast Search Algorithm for Closest Codevector in the Codebook for Vector Quantization", SPIT-IEEE Colloquium 2007, SPCE, Mumbai, 4th - 5th February 2007.
[36] Shu-Chuan Chu, Zhe-Ming Lu, Jeng-Shyang Pan, "Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding", Information Sciences, 177, 2007, pp. 734-746.
[37] Jim Z.C. Lai, Yi-Ching Liaw, and Julie Liu, "A fast VQ codebook generation algorithm using codeword displacement" , Pattern Recogn. vol. 41, no. 1, pp 315-319, 2008.
[38] Y.C. Liaw, J.Z.C. Lai, W. Lo, Image restoration of compressed image using classified vector quantization, Pattern Recogn. vol. 35, No. 2, pp 181-192, 2002.
[39] N.M. Nasrabadi, Y. Feng, Image compression using address vector quantization, IEEE Trans. Commun. vol. 38 No. 12, pp. 2166-2173, 1990.
[40] J. Foster, R.M. Gray, M.O. Dunham, Finite state vector quantization for waveform coding, IEEE Trans. Inf. Theory vol. 31, No. 3, pp. 348-359, 1985.
[41] T. Kim, Side match and overlap match vector quantizers for images, IEEE Trans. Image Process. vol. 1, No. 2, pp. 170-185, 1992.
[42] J.Z.C. Lai, Y.C. Liaw, W. Lo, Artifact reduction of JPEG coded images using mean-removed classified vector quantization, Signal Process. vol. 82, No. 10, pp. 1375-1388, 2002.
[43] K.N. Ngan, H.C. Koh, Predictive classified vector quantization, IEEE Trans. Image Process. vol. 1, No. 3, pp. 269-280, 1992.
[44] C.H. Hsieh, J.C. Tsai, Lossless compression of VQ index with search order coding, IEEE Trans. Image Process. vol. 5, No. 11, pp. 1579- 1582, 1996.
[45] J.Z.C. Lai, J.Y. Yen, Inverse error-diffusion using classified vector quantization, IEEE Trans. Image Process. vol. 7, No. 12, pp. 1753- 1758, 1998.
[46] P.C. Chang, C.S. Yu, T.H. Lee, "Hybrid LMS-MMSE inverse halftoning technique", IEEE Trans. Image Process. vol. 10, No. 1, pp. 95-103, 2001.
[47] C. Garcia and G. Tziritas, "Face detection using quantized skin color regions merging and wavelet packet analysis," IEEE Trans. Multimedia, vol. 1, no. 3, pp. 264-277, Sep. 1999.
[48] H. Y. M. Liao, D. Y. Chen, C. W. Su, and H. R. Tyan, "Real-time event detection and its applications to surveillance systems," in Proc. IEEE Int. Symp. Circuits and Systems, Kos, Greece, pp. 509-512, May 2006.
[49] J. Zheng and M. Hu, "An anomaly intrusion detection system based on vector quantization," IEICE Trans. Inf. Syst., vol. E89-D, no. 1, pp. 201- 210, Jan. 2006.
[50] Ahmed A. Abdelwahab, Nora S. Muharram, "A Fast Codebook Design Algorithm Based on a Fuzzy Clustering Methodology", International Journal of Image and Graphics, vol. 7, no. 2 pp. 291-302, 2007.