Codebook Generation for Vector Quantization on Orthogonal Polynomials based Transform Coding

Authors: R. Krishnamoorthi, N. Kannan

Abstract:

In this paper, a new algorithm for generating codebook is proposed for vector quantization (VQ) in image coding. The significant features of the training image vectors are extracted by using the proposed Orthogonal Polynomials based transformation. We propose to generate the codebook by partitioning these feature vectors into a binary tree. Each feature vector at a non-terminal node of the binary tree is directed to one of the two descendants by comparing a single feature associated with that node to a threshold. The binary tree codebook is used for encoding and decoding the feature vectors. In the decoding process the feature vectors are subjected to inverse transformation with the help of basis functions of the proposed Orthogonal Polynomials based transformation to get back the approximated input image training vectors. The results of the proposed coding are compared with the VQ using Discrete Cosine Transform (DCT) and Pairwise Nearest Neighbor (PNN) algorithm. The new algorithm results in a considerable reduction in computation time and provides better reconstructed picture quality.

Keywords: Orthogonal Polynomials, Image Coding, Vector Quantization, TSVQ, Binary Tree Classifier

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

References:

[1] Jain A.K., "Image Data Compression: A Review," Proc. IEEE, Vol. 69, No. 3, pp. 349 - 389, 1981.
[2] G.K. Wallace, "The JPEG Still Picture Compression Standard," Communications of ACM Vol. 34, pp.31-44, 1991.
[3] N. Ahamed, T. Natarajan and K.R. Rao, "Discrete Cosine Transform," IEEE Transactions on Computer, Vol. 23, pp. 90-93, 1974.
[4] R.C. Reininger and J. Gibson, "Distribution of 2-Dimensional DCT Coefficients for Images," IEEE Transactions on Communications. Vol. 31, pp. 835-839, 1983.
[5] H.C. Andrews, "Computer Techniques in Image Processing," Academic Press, New York, 1970.
[6] W.K. Pratt, W.H. Chen and L.R. Welch, "Slant Transform Image Coding," IEEE Transactions on Communications, Vol. 22, pp. 1075- 1093, 1973.
[7] A. Habibi and P.A. Wintz, "Image Coding by Linear Transformation and Block Quantization," IEEE Transactions on Communications Technology. Vol.19, pp. 50-62, 1971.
[8] P.A. Wintz and M.Tasto, "Image Coding by Adaptive Block Quantization," IEEE Transactions on Communications Technology, Vol. 19, pp. 957-972, 1971.
[9] Whelche. J.E, Jr., and Guinn, D.F., "The Fast Fourier Hadamard Transform and its Use in Signal Representation and Classification," Eascon 1968 convention record, pp. 561-573, 1988.
[10] Henderson. K.W, "Some Notes on Walsh Functions," IEEE Transactions on Electronic Computers. Vol. EC-13, No.1, pp. 50-52, 1964.
[11] Y. Linde, A. Buzo and R.M. Gray, "An algorithm for Vector Quantizer Design," IEEE Transactions on Communications, Vol. 28, pp 84-95, January 1980.
[12] R.M.Gray, "Vector Quantization", IEEE ASSP Magazine, pp. 4-29, April 1984.
[13] Hsieh.C.H. , Lu.P.C. and Chung. J.C, "Fast Codebook Generation Algorithm for Vector Quantization of Images", Pattern Recognition Letter, 12, pp. 605-609. 1991.
[14] Hsieh. C.H., "DCT based Codebook Design for Vector Quantization of Images", IEEE Transactions on Circuits and Systems, Vol. 2, pp. 401- 409, 1992.
[15] Sangeetha Ramakrishnan, Kenneth Rose and Alen Gersho, "Constrained Storage Vector Quantization with a Universal Codebook", IEEE Transactions on Image Processing, Vol. 7, No. 6, pp. 785 - 793, June 1998.
[16] P.A.Chou, T.Lookabaugh, and R.M.Gray, "Optimal pruning with applications to tree-structured source coding and modeling," IEEE Transactions on Information Theory, Vol. 35, pp. 299 - 316,1989.
[17] N.Moayeri, D.L.Neuhoff, and W.E.Stark, "Fine-Coarse vector quantization," IEEE Transactions on ASSP, Vol. 39, pp. 1503-1515, 1991.
[18] Peter Vprek and A.B. Bradley, "An improved algorithm for Vector Quantizer Design", IEEE Signal Processing Letters, Vol. 7, No. 9, pp 250-252, September 2000.
[19] W.Equitz "A new vector quantization clustering algorithm", IEEE Transactions on ASSP, vol. 37, pp.1568-1575, Oct. 1989.
[20] S.Q.Yun and K.S.Fu, "A method for design of binary tree classifiers," Pattern Recognition, Vol. 16, pp. 509-603, 1983.
[21] Y.K.Lin and K.S.Fu, "Automatic classification of cervical cells using a binary tree classifier," Pattren Recognition, vol. 16, pp. 69-80, 1983.
[22] X.Li and R.C.Dubes , "Tree classifier design with a permutation statistic," Pattern Recognition, Vol. 19, pp. 229-235, 1986.
[23] P.Swain and W.Meisel, "The decision tree classifier design and potential," IEEE Transactions on Geosci. Electron., Vol. 15, pp. 142- 147, 1977.
[24] A.V.Kulkarni and L.N.Kanal, "An optimization approach to hierarchical classifier design," in Proceedings Third International joint Conference on Pattern Recognition, pp.459-466, 1976.
[25] H.J.Payne and W.S.Meisel , "An algorithm for constructing optimal binary decision trees," IEEE Transactions on Computers, Vol. 26, pp. 905-916, 1977.
[26] M.W.Kurrzynski, "The optimal strategy of a tree classifier," Pattern Recognition, Vol. 16, pp. 81-87, 1983.
[27] A.V.Kulkarni, "On the mean accuracy of hierarchical classifiers," IEEE Transasctions on Computers, Vol. 27, pp. 771-776, 1978.
[28] R. Krishnamoorthi and P. Bhattacharayya, "A new data compression Scheme using Orthogonal Polynomials", IEEE Proceedings on International Conference on Information, Communication and Signal Processing, Nanyang Technology University, Singapore, Vol-I, pp- 490-494, 1997.
[29] R.Krishnamoorthi "Transform coding of monochrome images with a statistical design of experiments approach to separate noise" Pattern Recognition Letters Vol.28, pp. 771-777. 2007.
[30] R.Krishnamoorthi, "A unified framework orthogonal polynomials for Edge detection, Texture Analysis and Compression incolor images," Ph.D. Thesis, I.I.T, Kharagpur, 1998.