Codebook Generation for Vector Quantization on Orthogonal Polynomials based Transform Coding
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:54595", author = "R. Krishnamoorthi and N. Kannan", title = "Codebook Generation for Vector Quantization on Orthogonal Polynomials based Transform Coding", 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", volume = "3", number = "11", pages = "2020-7", }
