A Fast VQ Codebook Generation Algorithm Based on Otsu Histogram Threshold

• Autorzy: Huang C-C. , Tsai D-S. , Horng G.
• Języki publikacji: EN

Abstrakty

EN

In vector quantization, the codebook generation problem can be formulated as a classification problem of dividing N_p training vectors into N_c clusters, where N_p is the training size of input vectors and N_c is the codeword size of codebook. For large Np and Nc, a traditional search algorithmsuch as the LBG method can hardly find the global optimal classification and needs a great deal of calculation. In this paper, a novel VQ codebook generation method based on Otsu histogram threshold is proposed. The computational complexity of squared Euclidean distance can be reduced to O(N_p log_2 N_c) for a codebook with gray levels. Our method provides better image quality than recent proposed schemes in high compression ratio. The experimental results and the comparisons show that this method can not only reduce the computational complexity of squared Euclidean distance but also find better codewords to improve the quality of the resulted VQ codebook.

Słowa kluczowe

EN

vector quantization; codebook generation; histogram thresholding; clustering; within class variance; between-class variance; LBG algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 3-4
• Strony: 563--579
• Opis fizyczny: Bibliogr. 20 poz., fot., tab., wykr.

Twórcy

autor

Huang C-C.

autor

Tsai D-S.

autor

Horng G.

• Department of Computer Science and Engineering National Chung Hsing University Taichung 402, Taiwan, ROC,

Bibliografia

• [1] Arifin, A. Z., Asano, A.: Image segmentation by histogram thresholding using hierarchical cluster analysis, Pattern Recognition Letters, 27(13), 2006, 1515-1521.
• [2] Bel, C. D., Gray, R. M.: An improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization, IEEE Trans. Communs., 33(10), 1985, 1132-1133.
• [3] Chang, C. C., Hu, C. Y.: An Improved Tree-Structured Codebook Search Algorithm for Image Compression, to appear in IEE Proceedings- Vision, Image and Signal Processing, 1999.
• [4] Chang, C. C., Lin, D. C., Chen, T. S. .: An Improved VQ Codebook Search Algorithm Using Principal Component Analysis, Journal of Visual Communication and Image Representation, 8(1), 1997, 27-37.
• [5] Chang, C. C., Wang, L. L.: A fast multilevel thres holding method based on low pass and high pass filtering, Pattern Recognition Letters, 18(14), 1997, 1469-1478.
• [6] Chen, T. S., Chang, C. C.: Diagonal Axes Method (DAM): A Fast Search Algorithm for Vector Quantization, IEEE Trans. on Circuits and System for Video Technology, 7(3), 1997, 555-559.
• [7] Cosman, P. C., Gray, R. M., Vetterli, M.: Vector Quantization of Image Subbands: A Survey, IEEE Trans. on Image Processing, 5(2), 1996, 202-225.
• [8] Equitz, W. H.: A New Vector Quantization Clustering Algorithm, IEEE Trans. Qn Acous., Speech, Signal Proc., ASSP-37, 1989, 1568-1575.
• [9] Gong, J., Li, L., Chen,W.: Fast recursive algorithms for two-dimensional thresholding, Pattern Recognition, 31(3), 1998, 295-300.
• [10] Gray, R. M.: Vector quantization, IEEE Acoust, Speech, Signal Processing Mag., Apr. 1984, 4-29.
• [11] Hammouche, K., Diaf, M., Siarry, P.: A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation, Computer Vision and Image Understanding, (109), 2008, 163-175.
• [12] Huang, C. M., Bi, Q., Harris, R. W.: Fast Full Search Equivalent Encoding Algorithms for Image Compression Using Vector Quantization, IEEE Trans. Communs., 37, 1992, 413-416.
• [13] Likas, A., Vlassis, N., Verbeek, J. J.: The global k-means clustering algorithm, Pattern Recognition, 36(2), 2003, 451-461.
• [14] Linde, Y., Buzo, A., Gray, R. M.: An Algorithm for Vector Quantizer Design, IEEE Trans. on Communs., COM-208, 1980, 84-95.
• [15] Nasrabadi, N. M., King, R. A.: Image Coding Using Vector Quantization: A Review, IEEE Trans. On Communs., 36, 1988, 957-971.
• [16] Oehler, K. L., Gray, R. M.: Combining Image Compression and Classification Using Vector Quantization, IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(5), 1995.
• [17] Otsu, N.: A Threshold Selection Method from Gray-Level Histograms, IEEE Trans. on System Man Cybernetics, SMC-9(1), 1979, 62-66.
• [18] Patane, G., Russo, M.: The Enhanced LBG Algorithm, Neural Networks, 14(9), 2001, 1219-1237.
• [19] Ra, S. W., Kim, J. K.: A Fast Mean-Distance-Ordered Partial Codebook Search Algorithm for Image Vector Quantization, IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing, 40(9), 1993, 576-579.
• [20] Shena, F., Hasegawa, O.: An adaptive incremental LBG for vector quantization, Neural Networks, 19(5), 2006, 694-704.