Fast Cosine Transform to Increase Speed-up and Efficiency of Karhunen-Loève Transform for Lossy Image Compression
In this work, we present a comparison between two
techniques of image compression. In the first case, the image is
divided in blocks which are collected according to zig-zag scan. In
the second one, we apply the Fast Cosine Transform to the image,
and then the transformed image is divided in blocks which are
collected according to zig-zag scan too. Later, in both cases, the
Karhunen-Loève transform is applied to mentioned blocks. On the
other hand, we present three new metrics based on eigenvalues for a
better comparative evaluation of the techniques. Simulations show
that the combined version is the best, with minor Mean Absolute
Error (MAE) and Mean Squared Error (MSE), higher Peak Signal to
Noise Ratio (PSNR) and better image quality. Finally, new technique
was far superior to JPEG and JPEG2000.
[1] S. A. Khayam, The Discrete Cosine Transform (DCT): Theory and
Application Technical Report, WAVES-TR-ECE802.602, 2003.
[2] W. B. Pennebaker and J. L. Mitchell, "JPEG - Still Image Data
Compression Standard," New York: International Thomsan Publishing,
1993.
[3] Strang G., "The Discrete Cosine Transform," SIAM Review, Volume
41, Number 1, pp.135-147, 1999.
[4] R. J. Clark, "Transform Coding of Images," New York: Academic Press,
1985.
[5] H. Radha, "Lecture Notes: ECE 802 - Information Theory and Coding,"
January 2003.
[6] A. C. Hung and TH-Y Meng, "A Comparison of fast DCT algorithms,"
Multimedia Systems, No. 5 Vol. 2, Dec 1994.
[7] G. Aggarwal and D. D. Gajski, "Exploring DCT Implementations," UC
Irvine, Technical Report ICS-TR-98-10, March 1998.
[8] J. F. Blinn, "What's the Deal with the DCT," IEEE Computer Graphics
and Applications, July 1993, pp.78-83.
[9] C. T. Chiu and K. J. R. Liu, "Real-Time Parallel and Fully Pipelined 2-D
DCT Lattice Structures with Application to HDTV Systems," IEEE
Trans. on Circuits and Systems for Video Technology, vol. 2 pp. 25-37,
March 1992.
[10] M. A. Haque, "A Two-Dimensional Fast Cosine Transform," IEEE
Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-33
pp. 1532-1539, December 1985.
[11] M. Vetterli, "Fast 2-D Discrete Cosine Transform," ICASSP '85, p.
1538.
[12] F. A. Kamangar and K. R. Rao, "Fast Algorithms for the 2-D Discrete
Cosine Transform," IEEE Transactions on Computers, v C-31 p. 899.
[13] E. N. Linzer and E. Feig, "New Scaled DCT Algorithms for Fused
Multiply/Add Architectures," ICASSP '91, p. 2201.
[14] C. Loeffler, A. Ligtenberg, and G. Moschytz, "Practical Fast 1-D DCT
Algorithms with 11 Multiplications," ICASSP '89, p. 988.
[15] P. Duhamel, C. Guillemot, and J. C. Carlach, "A DCT Chip based on a
new Structured and Computationally Efficient DCT Algorithm," ICCAS
'90, p. 77.
[16] N. I. Cho and S. U. Lee, "Fast Algorithm and Implementation of 2-D
DCT," IEEE Transactions on Circuits and Systems, vol. 38 p. 297,
March 1991.
[17] N. I. Cho, I. D. Yun, and S. U. Lee, "A Fast Algorithm for 2-D DCT,"
ICASSP '91, p. 2197-2220.
[18] L. McMillan and L. Westover, "A Forward-Mapping Realization of the
Inverse DCT," DCC '92, p. 219.
[19] P. Duhamel and C. Guillemot, "Polynomial Transform Computation of
the 2-D DCT," ICASSP '90, p. 1515.
[20] A. K. Jain, "Fundamentals of Digital Image Processing," New Jersey:
Prentice Hall Inc., 1989.
[21] R. C. Gonzalez and P. Wintz, "Digital Image Processing," Reading. MA:
Addison-Wesley, 1977.
[22] W. L. Briggs and H. Van Emden, The DFT: An Owner-s Manual for the
Discrete Fourier Transform, SIAM, 1995, Philadelphia.
[23] Hsu H. P., Fourier Analysis, Simon & Schuster, 1970, New York.
[24] Tolimieri R., An M. y Lu C., Algorithms for Discrete Fourier Transform
and convolution, Springer Verlag, 1997, New York.
[25] Tolimieri R., An M. y Lu C., Mathematics of multidimensional Fourier
Transform Algorithms, Springer Verlag, 1997, New York.
[26] Claveau F. y Poirier M., "Real time FFT based cross-covariance method
for vehicle speed and length measurement using an optical sensor,"
ICSPAT 96, pp.1831-1835, Boston, MA, Oct.1996.
[27] D. Zhang, and S. Chen, "Fast image compression using matrix K-L
transform," Neurocomputing, Volume 68, pp.258-266, October 2005.
[28] R.C. Gonzalez, R.E. Woods, Digital Image Processing, 2nd Edition,
Prentice- Hall, Jan. 2002, pp.675-683.
[29] -, The transform and data compression handbook, Edited by K.R. Rao,
and P.C. Yip, CRC Press Inc., Boca Raton, FL, USA, 2001.
[30] B.R. Epstein, et al, "Multispectral KLT-wavelet data compression for
landsat thematic mapper images," In Data Compression Conference,
pp. 200-208, Snowbird, UT, March 1992.
[31] K. Konstantinides, et al, "Noise using block-based singular value
decomposition," IEEE Transactions on Image Processing, 6(3), pp.479-
483, 1997.
[32] J. Lee, "Optimized quadtree for Karhunen-Loève Transform in
multispectral image coding," IEEE Transactions on Image Processing,
8(4), pp.453-461, 1999.
[33] J.A. Saghri, et al, "Practical Transform coding of multispectral
imagery," IEEE Signal Processing Magazine, 12, pp.32-43, 1995.
[34] T-S. Kim, et al, "Multispectral image data compression using classified
prediction and KLT in wavelet transform domain," IEICE Transactions
on Fundam Electron Commun Comput Sci, Vol. E86-A; No.6, pp.1492-
1497, 2003.
[35] J.L. Semmlow, Biosignal and biomedical image processing: MATLABBased
applications, Marcel Dekker, Inc., New York, 2004.
[36] S. Borman, and R. Stevenson, "Image sequence processing,"
Department, Ed. Marcel Dekker, New York, 2003. pp.840-879.
[37] M. Wien, Variable Block-Size Transforms for Hybrid Video Coding,
Degree Thesis, Institut f├╝r Nachrichtentechnik der Rheinisch-
Westfälischen Technischen Hchschule Aachen, February 2004.
[38] E. Christophe, et al, "Hyperspectral image compression: adapting SPIHT
and EZW to anisotopic 3D wavelet coding," submitted to IEEE
Transactions on Image processing, pp.1-13, 2006.
[39] L.S. Rodríguez del Río, "Fast piecewise linear predictors for lossless
compression of hyperspectral imagery," Thesis for Degree in Master of
Science in Electrical Engineering, University of Puerto Rico, Mayaguez
Campus, 2003.
[40] -. Hyperspectral Data Compression, Edited by Giovanni Motta,
Francesco Rizzo and James A. Storer, Chapter 3, Springer, New York,
2006.
[41] B. Arnold, An Investigation into using Singular Value Decomposition as
a method of Image Compression, University of Canterbury Department
of Mathematics and Statistics, September 2000.
[42] S. Tjoa, et al, "Transform coder classification for digital image
forensics", IEEE Int. Conf. Image Processing, September 2007.
[43] M. Mastriani, Decorrelación espacial, rápida y de alta eficiencia para
compresión de imágenes con perdidas, Ph.D. dissertation, Computer
Department, Buenos Aires University, March 12th, 2009.
[44] B. Britanak, P. Yip, and K. R. Rao, "Discrete cosine and sine transforms:
General properties, fast algorithms and integer approximations,"
Academic Press, N.Y., 2006.
[45] M. Mastriani, Compresi├│n r├ípida y eficiente de im├ígenes, appear in 11º
Argentine Symposium on Technology, August 30th to September 3,
2010, Buenos Aires, Argentina.
[46] MATLAB® R2008a (Mathworks, Natick, MA).
[1] S. A. Khayam, The Discrete Cosine Transform (DCT): Theory and
Application Technical Report, WAVES-TR-ECE802.602, 2003.
[2] W. B. Pennebaker and J. L. Mitchell, "JPEG - Still Image Data
Compression Standard," New York: International Thomsan Publishing,
1993.
[3] Strang G., "The Discrete Cosine Transform," SIAM Review, Volume
41, Number 1, pp.135-147, 1999.
[4] R. J. Clark, "Transform Coding of Images," New York: Academic Press,
1985.
[5] H. Radha, "Lecture Notes: ECE 802 - Information Theory and Coding,"
January 2003.
[6] A. C. Hung and TH-Y Meng, "A Comparison of fast DCT algorithms,"
Multimedia Systems, No. 5 Vol. 2, Dec 1994.
[7] G. Aggarwal and D. D. Gajski, "Exploring DCT Implementations," UC
Irvine, Technical Report ICS-TR-98-10, March 1998.
[8] J. F. Blinn, "What's the Deal with the DCT," IEEE Computer Graphics
and Applications, July 1993, pp.78-83.
[9] C. T. Chiu and K. J. R. Liu, "Real-Time Parallel and Fully Pipelined 2-D
DCT Lattice Structures with Application to HDTV Systems," IEEE
Trans. on Circuits and Systems for Video Technology, vol. 2 pp. 25-37,
March 1992.
[10] M. A. Haque, "A Two-Dimensional Fast Cosine Transform," IEEE
Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-33
pp. 1532-1539, December 1985.
[11] M. Vetterli, "Fast 2-D Discrete Cosine Transform," ICASSP '85, p.
1538.
[12] F. A. Kamangar and K. R. Rao, "Fast Algorithms for the 2-D Discrete
Cosine Transform," IEEE Transactions on Computers, v C-31 p. 899.
[13] E. N. Linzer and E. Feig, "New Scaled DCT Algorithms for Fused
Multiply/Add Architectures," ICASSP '91, p. 2201.
[14] C. Loeffler, A. Ligtenberg, and G. Moschytz, "Practical Fast 1-D DCT
Algorithms with 11 Multiplications," ICASSP '89, p. 988.
[15] P. Duhamel, C. Guillemot, and J. C. Carlach, "A DCT Chip based on a
new Structured and Computationally Efficient DCT Algorithm," ICCAS
'90, p. 77.
[16] N. I. Cho and S. U. Lee, "Fast Algorithm and Implementation of 2-D
DCT," IEEE Transactions on Circuits and Systems, vol. 38 p. 297,
March 1991.
[17] N. I. Cho, I. D. Yun, and S. U. Lee, "A Fast Algorithm for 2-D DCT,"
ICASSP '91, p. 2197-2220.
[18] L. McMillan and L. Westover, "A Forward-Mapping Realization of the
Inverse DCT," DCC '92, p. 219.
[19] P. Duhamel and C. Guillemot, "Polynomial Transform Computation of
the 2-D DCT," ICASSP '90, p. 1515.
[20] A. K. Jain, "Fundamentals of Digital Image Processing," New Jersey:
Prentice Hall Inc., 1989.
[21] R. C. Gonzalez and P. Wintz, "Digital Image Processing," Reading. MA:
Addison-Wesley, 1977.
[22] W. L. Briggs and H. Van Emden, The DFT: An Owner-s Manual for the
Discrete Fourier Transform, SIAM, 1995, Philadelphia.
[23] Hsu H. P., Fourier Analysis, Simon & Schuster, 1970, New York.
[24] Tolimieri R., An M. y Lu C., Algorithms for Discrete Fourier Transform
and convolution, Springer Verlag, 1997, New York.
[25] Tolimieri R., An M. y Lu C., Mathematics of multidimensional Fourier
Transform Algorithms, Springer Verlag, 1997, New York.
[26] Claveau F. y Poirier M., "Real time FFT based cross-covariance method
for vehicle speed and length measurement using an optical sensor,"
ICSPAT 96, pp.1831-1835, Boston, MA, Oct.1996.
[27] D. Zhang, and S. Chen, "Fast image compression using matrix K-L
transform," Neurocomputing, Volume 68, pp.258-266, October 2005.
[28] R.C. Gonzalez, R.E. Woods, Digital Image Processing, 2nd Edition,
Prentice- Hall, Jan. 2002, pp.675-683.
[29] -, The transform and data compression handbook, Edited by K.R. Rao,
and P.C. Yip, CRC Press Inc., Boca Raton, FL, USA, 2001.
[30] B.R. Epstein, et al, "Multispectral KLT-wavelet data compression for
landsat thematic mapper images," In Data Compression Conference,
pp. 200-208, Snowbird, UT, March 1992.
[31] K. Konstantinides, et al, "Noise using block-based singular value
decomposition," IEEE Transactions on Image Processing, 6(3), pp.479-
483, 1997.
[32] J. Lee, "Optimized quadtree for Karhunen-Loève Transform in
multispectral image coding," IEEE Transactions on Image Processing,
8(4), pp.453-461, 1999.
[33] J.A. Saghri, et al, "Practical Transform coding of multispectral
imagery," IEEE Signal Processing Magazine, 12, pp.32-43, 1995.
[34] T-S. Kim, et al, "Multispectral image data compression using classified
prediction and KLT in wavelet transform domain," IEICE Transactions
on Fundam Electron Commun Comput Sci, Vol. E86-A; No.6, pp.1492-
1497, 2003.
[35] J.L. Semmlow, Biosignal and biomedical image processing: MATLABBased
applications, Marcel Dekker, Inc., New York, 2004.
[36] S. Borman, and R. Stevenson, "Image sequence processing,"
Department, Ed. Marcel Dekker, New York, 2003. pp.840-879.
[37] M. Wien, Variable Block-Size Transforms for Hybrid Video Coding,
Degree Thesis, Institut f├╝r Nachrichtentechnik der Rheinisch-
Westfälischen Technischen Hchschule Aachen, February 2004.
[38] E. Christophe, et al, "Hyperspectral image compression: adapting SPIHT
and EZW to anisotopic 3D wavelet coding," submitted to IEEE
Transactions on Image processing, pp.1-13, 2006.
[39] L.S. Rodríguez del Río, "Fast piecewise linear predictors for lossless
compression of hyperspectral imagery," Thesis for Degree in Master of
Science in Electrical Engineering, University of Puerto Rico, Mayaguez
Campus, 2003.
[40] -. Hyperspectral Data Compression, Edited by Giovanni Motta,
Francesco Rizzo and James A. Storer, Chapter 3, Springer, New York,
2006.
[41] B. Arnold, An Investigation into using Singular Value Decomposition as
a method of Image Compression, University of Canterbury Department
of Mathematics and Statistics, September 2000.
[42] S. Tjoa, et al, "Transform coder classification for digital image
forensics", IEEE Int. Conf. Image Processing, September 2007.
[43] M. Mastriani, Decorrelación espacial, rápida y de alta eficiencia para
compresión de imágenes con perdidas, Ph.D. dissertation, Computer
Department, Buenos Aires University, March 12th, 2009.
[44] B. Britanak, P. Yip, and K. R. Rao, "Discrete cosine and sine transforms:
General properties, fast algorithms and integer approximations,"
Academic Press, N.Y., 2006.
[45] M. Mastriani, Compresi├│n r├ípida y eficiente de im├ígenes, appear in 11º
Argentine Symposium on Technology, August 30th to September 3,
2010, Buenos Aires, Argentina.
[46] MATLAB® R2008a (Mathworks, Natick, MA).
@article{"International Journal of Electrical, Electronic and Communication Sciences:52107", author = "Mario Mastriani and Juliana Gambini", title = "Fast Cosine Transform to Increase Speed-up and Efficiency of Karhunen-Loève Transform for Lossy Image Compression", abstract = "In this work, we present a comparison between two
techniques of image compression. In the first case, the image is
divided in blocks which are collected according to zig-zag scan. In
the second one, we apply the Fast Cosine Transform to the image,
and then the transformed image is divided in blocks which are
collected according to zig-zag scan too. Later, in both cases, the
Karhunen-Loève transform is applied to mentioned blocks. On the
other hand, we present three new metrics based on eigenvalues for a
better comparative evaluation of the techniques. Simulations show
that the combined version is the best, with minor Mean Absolute
Error (MAE) and Mean Squared Error (MSE), higher Peak Signal to
Noise Ratio (PSNR) and better image quality. Finally, new technique
was far superior to JPEG and JPEG2000.", keywords = "Fast Cosine Transform, image compression, JPEG,JPEG2000, Karhunen-Loève Transform, zig-zag scan.", volume = "4", number = "1", pages = "69-11", }
