Fast Cosine Transform to Increase Speed-up and Efficiency of Karhunen-Loève Transform for Lossy Image Compression

Authors: Mario Mastriani, Juliana Gambini

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.

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

References:

[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).