Fast VQ Codebook Generation Method Using Codeword Stability Check and Finite State Concept

• Autorzy: Tsai P. , Hu Y-C. , Yeh H-L.
• Języki publikacji: EN

Abstrakty

EN

The codebook design in the vector quantization scheme is important because it affects the image quality of the encoded image. The Linde-Buzo-Gray (LBG) codebook generation algorithm is well known and a popular choice among codebook users. However, a heavy computational complexity is consumed for the iteratively clustering process in the LBG algorithm. In this paper, the similarity of codewords in consecutive rounds of the LBG algorithm is exploited to reduce the computational complexity. By checking the stability of codewords, the status of each codeword in the codebook can be determined. Only the unstable codewords are refined to generate the new codebook. The proposed method can be further improved by cooperating with the finite state technique. Experimental results show that the computational complexity of the proposed method is reduced to about 4% of the LBG algorithm while achieving a slightly worse image quality.

Słowa kluczowe

EN

Linde-Buzo-Gray; LBG algorithm; codebook; stable codeword; finite state

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 3-4
• Strony: 447--463
• Opis fizyczny: bibliogr. 20 poz., fot., tab.

Twórcy

autor

Tsai P.

autor

Hu Y-C.

autor

Yeh H-L.

• Department of Computer Science and Information Management, Providence University, Taichung, 433, Taiwan,

Bibliografia

• [1] Linde, Y., Buzo, A., Gray, R. M. :An Algorithm for Vector Quantizer Design, IEEE Transactions on Communications, 28,1980, 84-95.
• [2] Nasrabadi, N. M., King, R. A. :Image Coding Using Vector Quantization: A Review, IEEE Transactions on Communications, 36(8), 1988, 957-971.
• [3] Gersho, A., Gray, R. M. : Vector Quantization and Signal Compression, Boston, MA: Kluwer Academic Publishers, 1992.
• [4] Lai,T. H., Guan. L. : Video Coding Algorithm Using 3-D DCT and Vector Quantization, Proceedings of IEEE International Conference on Image Processing, 1, 2002, 741-744.
• [5] Lin, S. D., Shie, S. C., Lee, K. Y. : Image Compression with Wavelet-Based Vector Quantization, IEICE Transactions on Information and Systems, E86-D(4), 2003, 763-767.
• [6] Miaou, S. G., Yen, H. L., Lin, C. L. : Wavelet-Based ECG Compression Using Dynamic Vector Quantization with Tree Codevectors in Single Codebook, IEEE Transactions on Biomedical Engineering, 49(7), 2002, 671-680.
• [7] Lu, Z. M., Xu, D. G., Sun, S. H. : Multipurpose Image Watermarking Algorithm Based on Multistage Vector Quantization, IEEE Transactions on Image Processing, 14(6), 2005, 822-831.
• [8] Katsavounidis, I., Kuo, C. C. J., Zhang, Z. : A New Initialization Technique for Generalized Lloyd Iteration, IEEE Signal Processing Letters,, 1, 1994, 144-146.
• [9] Chehwang, C. : Initial Codebook Design byModified SplittingMethod, IEE Electronics Letters, 38(12), 2002, 606-607.
• [10] Xiong,H., Swamy, M. N. S., Ahmad,M. O. : Competitive Splitting for Codebook Initialization, IEEE Signal Processing Letters, 11, 2004, 474-477.
• [11] Lin, Y. C., Tai. S. C.: A Fast Linde-Buzo-Gray Algorithm in Image Vector Quantization, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 45(3), 1998, 432-435. .
• [12] Chang, C. C., Hu, Y. C. : A Fast Codebook Training Algorithm for Vector Quantization, IEEE Transactions on Consumer Electronics,44(4), 1998, 1201-1208.
• [13] Chen, C. Q., : An Enhanced Generalized Lloyd Algorithm, IEEE Signal Processing Letters, 11(2), 2004, 167-170.
• [14] Bei, C., Gray, R. M. : An Improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization, IEEE Transactions on Communications, 33, 1985, 1132-1133.
• [15] Pan, J. S., Lu, Z. M., Sun, S. H. : An Efficient Encoding Algorithm for Vector Quantization Based on Subvector Technique, IEEE Transactions on Image Processing, 12(3), 2003, 265-270.
• [16] Hu, Y. C., Chang, C. C. : An Effective Codebook Search Algorithmfor Vector Quantization, Imaging Science Journal,51(4), 2003, 221-234.
• [17] Z. Pan, Z., Kotani, K., Ohmi, T. : Fast Encoding Method for Vector Quantization Using Modified L2-Norm Pyramid, IEEE Signal Processing Letters, 12(9), 2005, 609-612.
• [18] Chang, R. F., Chen, W. T., Wang, J. S. : A Fast Finite-State Algorithm for Vector Quantizer Design, IEEE Transactions on Signal Processing, 40(1), 1992, 221-225.
• [19] Momose, S., Sano, K., Suzuki, K., Nakamura, T.: FParallel Competitive Learning Algorithm for Fast Codebook Design on Partition Space, IEEE International Conference on Cluster Computing, 2004, 449-457.
• [20] Foster, F., Gray, R. M., Dunham, M. O. : Finite-state vector quantization of waveform coding, IEEE Transactions on Information Theory, 31, 1985, 348-359.