A Review Comparison of Wavelet and Cosine Image Transforms

Published Online September 2012 in MECS

The need for effective and standardized image compression techniques has increased drastically because of the recent advancement in digital imaging applications like desktop publishing [1] and high-definition television HDTV [2]. In addition, Image Compression also finds great application in transferring videos and images over the web to reduce data transfer time and resource consumption [3].These techniques make use of wavelet or cosine transform to obtain a set of coefficients further used for compression.

A number of methods have been proposed in the past based on DCT and DWT techniques. JPEG [4] and MPEG [5] are two famous examples of DCT compression technique. Another set of methods are based upon DWT technique. EZW (embedded zero trees wavelet algorithm) [6] is a famous DWT based method which generates bits in the bit stream in order of importance, further useful for image compression. SPIHT (set partitioning in hierarchical trees) [7] works by omitting entropy coding of the bit stream by arithmetic code while the SPECK (set partitioned embedded block coder algorithm) [8] works using Multi Wavelet for compression. The EBCOT (embedded block coding with optimized Truncation) [9] method exhibits state of the art compression performance producing a bit-stream with a rich feature set. As majority of the algorithms are based on DCT and DWT, these techniques form the backbone image compression industry. Hence, it becomes very important and essential to evaluate the superiority of one algorithm over the other.

DCT is a sinusoidal transform which approximates the information packing ability of the optimal Karhunen-Loeve transform to achieve compression. DCT can be implemented in a single integrated circuit, packing the information into lesser coefficients [10]. In addition, DCT also effectively minimizes the block appearance called blocking articraft. On the other hand, Discrete Wavelet Transformation (DWT) provides better visual quality and higher compression as it converts discrete signal from time domain into time frequency domain. The transformation product is set of coefficient organized in the way that enables not only spectrum analysis of the signal but also spectral behavior of the signal in time.

The paper presents a review comparison between

DCT and DWT compression techniques based on multiple important evaluation parameters like (i) mean squared error and SNR for different threshold values (ii) SNR values and mean squared error for different coefficients (iii) SNR values and mean squared error for different window size. In addition, the paper also makes two advanced studies (i) CPU utilization and compression ratio for different window sizes (ii) SNR and compression with different compression ratio. The experimentation is performed on multiple 8x8 jpeg images.

The remaining paper is organized as follows. Section II presents the data compression transforms used in the paper III section states the results while section IV concludes the simulations performed in the paper.

• II.    DATA COMPRESSION USING TRANSFORMS

Data storage is an important requirement for digital computers due to the increasing load in data. Due to increasing need for data storage, compression techniques have been used to effectively reduce the size of data like image and audio without the loss of crucial information.

The basic image compression process can be explained by a codec in which the coder compresses the image and decoder reconstructs the image as shown in fig 1.

Figure 1. General process of compression and data transfer

The input image is fed into the system in which the coder creates a compressed representation of the input. The compressed representation is transmitted and later image is reconstructed with the help of decoder. The aim of the system is to keep irrelevant information out of the representation so that less space is required. Two types of transforms are mainly used for image compression as described below [11].

• A. Discrete cosine transform

Discrete cosine transform separates the images into frequencies with large variance. Further, the Quantization step discards the less important frequencies leading to reduction in data. Further, the reconstruction step uses only the most important frequencies to retrieve the image. The distortion contained by the reconstructed steps can be adjusted during the compression stage.

Summary of the process [12] is described below:-

• 1.    Image is divided into 8*8 blocks of pixels.

• 2.    DCT is applied to each block working from left to right, top to bottom.

• 3.    Through each block each block is quantised.

• 4.    The image obtained from the array of the compressed blocks is stored into a smaller space.

The discrete cosine transforms can be divided on the basis of dimensionality mainly into two dimensions, one dimensional and two dimensional.

• a) . 1 D discrete cosine transform

For a set of n real numbers s(x), x=0, 1… n-1 the discrete cosine transform is given by n-1

S(u) = V2 / n C(u) ^s(x) cos x=0

(2х+Т)и П

2 n

C ( u ) = 2 ² for u = 0

= 1 otherwise u = 0,.. n

The DCT can be obtained as the product of the vector (input list s(x)) and the n*n orthogonal matrix. The transformed sets of elements are derived by the dot (.) product of list s(x) and a basis vector. The n*n orthogonal matrix’s constitute the basis vectors. Each of the basis vectors corresponds to a particular sinusoid of a single frequency [13]. The constants are decided such that the basis vectors are orthogonal and normalized.

The above Discrete Cosine Transform is used to compress the one dimension data i.e. audio wave. We need to study the two dimensional Discrete Cosine Transform for image compression.

• b) . 2 D discrete cosine transform

The two dimensional DCT for an n*m matrix is computed as shown. The 1D DCT is applied to each and every row of s and again to each column of the result. The transform is represented as shown

m-1 n-1         (2x +1)u П   (2y +1)u П

S(u) = V2/ nm C(u)C(v) >>  s(x,y) cos----------cos---------- u , v = 0,.. n

• У=0» Хз              2 n            2 n

C ( u ) = 2² foru = 0

= 1 otherwise                                                  (2)

Each element of the transformed matrix is a dot product of the input set and an n*m basis function. The outer product of two of the 1D basis vector constitutes each of the 2D basis matrices. If, each of the basis matrices can be assumed as an image. Each pixel in the DCT image shows the proportion of 2D basis functions present in the input image. The elements of the DCT output represent the magnitude of image component at different 2D frequencies. Using these coefficients we proceed further into the stages of compression of images. The DCT based compression depends on the two core techniques called Quantization and Entropy Coding.

Quantization in brief can be described as the process of reducing the number of possible values of quantities (coefficients), thereby decreasing the space required to store them. Entropy Coding is carried out to represent the quantized data in a more compact nature [14].

• B. Discrete wavelet transform

The wavelet algorithm is based on multi-resolution analysis. The transform consists of convoluting signal against specific instances at various time scales and positions. The transform is achieved by decomposing the signal into two components each carrying the information of the source signal. The transform can be treated like a filter bank. The filters banks come in pairs - one low pass filter and one high pass filter. The signal from the low pass filter contains slow changing component of signal, which is very much similar to the original signal. Fast changing component is obtained through the high pass filter. Modeling the time changes scale can be done by shifting the position of wavelet while the frequency modeling is performed by changing the time scale. Since most of the processed signal data is stored discretely we need not perform convolutions at every position and characteristic scale of wave resulting into Discrete Wavelet Transform (DWT). The common approach while performing the discrete transform is dyadic scheme. That is we increase the step and scale spacing between wavelets by a multiple of two at each step.

DWT represents a signal using orthonormal basis which considers an infinite countable set of wavelets. We denote the wavelet basis as { ^ Д t )□ k e Z Л n e Z } , the pair  of DWT transform is represented  as:

да ( даЛ

x(t )=Z|Z( dk, A, (t ))| k=-да \ n=-да dk,n = ^°k,n ( t ) , - ( t ))

= H OTk, n ( t ) X ( t ) dt

Where { d_k ^} represent the wavelet coefficients. The DWT can be used to describe any signal using a coefficient set with two countable indices: { dk,n k e Z Л п e Z }

• III.    RESULTS

This section elaborates and compares the results obtained for image compression using DCT and DWT algorithms. The simulations are performed on a Pentium core 2 duo 1.83 GHz machine. The algorithms are analyzed on the basis of (i) mean squared error and SNR for different threshold values (ii) SNR values and mean squared error for different coefficients (iii) SNR values and mean squared error for different window size. In addition, the paper also makes two advanced studies (i) CPU utilization and compression ratio for different window sizes (ii) SNR and compression with different compression ratio.

DCT and DWT are applied on sample images as shown in Fig. 2. Table. 1 represents the SNR and mean squared error for different threshold values on application of DCT on sample images. Similarly, table. 2 presents the SNR and mean squared error for variations in threshold values on application of DWT on sample images

Signal to Noise ratio with respect to the variation in threshold value is analyzed in fig. 3. It is observed that the signal to noise ratio decreases with increase in threshold value for both DCT and DWT. Generally for all threshold values, SNR of DWT compression is more than SNR of DCT compression and SNR values decreases as threshold value increases.

Mean Squared Error (MSE) is defined as the square of differences in the pixel values between the corresponding pixels of the two images. Mean Squared Error (MSE) with respect to the variation in threshold value is analyzed in fig. 4. Mean square error (MSE) of DCT compression is always more than Mean square error of DWT compression for all sample images moreover Mean square error increases as rise in threshold values.

CPU utilization with respect to window size is presented in fig. 5 (a). In case of CPU utilization, it is almost same for both DCT and DWT compression although it first decreases and the remains constant as window size increases.

Compression ratio with respect to window size is presented in fig. 5 (b) and 5 (c). If we look up at compression ratio (i.e. compression efficiency) For DCT compression it steadily increases as window size increases after that it falls instantaneously .but in case of DWT compression Technique, compression steadily decreases as window size increases.

Signal to Noise ratio is computed for variation with respect to number of coefficients in fig. 5 (d). In DCT compression SNR raises slowly as number of coefficients increases, but there is sudden jump to high SNR values, which improves image quality. It is almost same for DWT although the SNR is relatively greater than DWT for all values of coefficients.

Mean square error (MSE) is computed for variation with respect to window size as shown in fig. 5 (e). For DCT compression mean squared error goes on increasing constantly as window size increases, while in case of DWT compression MSE first decreases then slowly increases as window size increases.

Original image             DC T Compression D^T Compression

Figure 3. (a) Graphical representation of SNR with respect to threshold value for DCT and DWT compression for image “BIKE” (b) Graphical representation of SNR with respect to threshold value for DCT and DWT compression for image “CAR” (c) Graphical representation of SNR with respect to threshold value for DCT and DWT compression for image “TIGER” (d) Graphical representation of SNR with respect to threshold value for DCT and DWT compression for image “TURTLE”.

Figure 4. (a) Graphical representation of Mean squared error (MSE) with respect to threshold value for DCT and DWT compression for image

“BIKE” (b) Graphical representation of Mean squared error with respect to threshold value for DCT and DWT compression for image “CAR” (c) Graphical representation of Mean squared error with respect to threshold value for DCT and DWT compression for image “TIGER” (d) Graphical representation of Mean squared error with respect to threshold value for DCT and DWT compression for image “TURTLE”.

Figure 5. (a)Graphical representation of CPU utilization with different values of window size for both DCT and DWT compression (b) Graphical representation of compression(compression ratio) with varying values of window size for DCT compression (c) Graphical representation of compression(compression ratio) with varying values of window size for DWT compression (d) Graphical representation of SNR with variation in No. of coefficient (for quantization) for DCT compression (e) Graphical representation of Mean squared error with different values of window size for both DCT and DWT compression (f) Graphical representation of SNR with respect to change in window size for DCT and DWT compression

Figure 6.  (a) Graphical representation of SNR (signal to noise ratio) with variation in compression ratio for DCT compression (b) Graphical representation of SNR (signal to noise ratio) with variation in compression ratio for DWT compression

Table 1. DCT compression results for all images in terms of SNR and mean squared error for different threshold values.

Image name	Threshold value	Signal to noise ratio (SNR)	Mean     Squared error(MSE)
Bike	20	38.129	10.003
	40	35.293	19.220
	60	33.432	29.501
	SO	32.188	39.289
	100	31.392	47.192
Car	20	36.946	13.135
	40	33.151	31.469
	60	30.979	51.896
	SO	29.424	74.241
	100	28.164	99.126
Tiger	20	32.625	35.521
	40	30.710	55.212
	60	29.642	70.612
	SO	28.802	85.667
	100	28.209	98.201
Turtle	20	33.102	31.831
	40	29.225	77.712
	60	27.214	123.483
	SO	26.004	163.170
	100	25.051	203.221

Table 2. DWT compression represented on different 8x8 jpeg images of bike, car, tiger and turtle in terms of SNR and mean squared error for different threshold values

Image name	Threshold value	Signal     to noise      ratio (SNR)	Mean    Squared error(MSE)
Bike	20	38.810	8.552
	40	35.365	18.902
	60	34.270	24.321
	80	33.173	31.312
	100	32.434	37.124
Car	20	37.223	12.201
	40	33.303	30.391
	60	31.228	49.001
	80	40.276	67.102
	100	28.827	85.176
Tiger	20	32.631	35.478
	40	31.139	50.023
	60	30.184	62.316
	80	29.315	76.120
	100	28.769	86.314
Turtle	20	33.285	30.515
	40	29.528	72.483
	60	27.411	118.001
	80	26.196	156.112
	100	25.295	192.117

Signal to Noise ratio is also computed for variation with respect to window size as shown in fig. 5 (f). SNR decreases in DCT compression with respect to window size increment. While in DWT compression with respect to window size increment SNR increases then there is sudden fall and then smoothly decreases.

The section makes another interesting analysis for signal to noise ratio for variation with respect to compression ratio as shown in fig. 6. SNR decreases as compression ratio increases in smoothly zig-zag way in DCT compression method leading to bad image quality. While SNR increases as compression ratio increases then sudden falls then goes on falling at slow rate. It is observed in case for DCT the signal to noise ratio decreases with increase in compression ratio while in case of DWT the signal to noise ratio increases until compression ratio 5 and then decreases after that.

• IV.    CONCLUSION

The section presents a brief summary of the experimentation conducted in this paper. Two major image compression techniques DCT and DWT were experimented on four 8x8 jpeg images. It is observed from the experimentation that the image quality using 8x8 DCT block at higher threshold values decreases rapidly while for DWT the reduction of image quality is slow. In case of low threshold values DCT and DWT both perform equally well. The image quality is degraded with increase in window size for DCT while the image quality increases with increment in window size in case of DWT. It is computationally efficient to have a bigger window size for compression because of which DWT is faster than DCT. In addition, DWT permits better localization in spatial and frequency domain while DCT is incapable of any such ability. Hence DWT should be preferred over DCT for image compression.

• [1]    What You See Is Pretty Close to What You Get: New h&j, pagination program for IBM PC, Seybold Report on Publishing Systems, 13(10), February 13, 1984, pp. 21-2.

• [2]    Robert P. Seidel,The State of the DTV / HDTV Transition in the United States CBS - SMPTE Technical Conference, New York City, November 2003.

• [3]    J.F.Hercus and K. A.Hawick, Compression of Image Data and Performance Tradeoffs for Client/Server Systems, Technical Report DHPC-029,January 1997.

• [4]    Wallace, G. 1991. The JPEG still picture compression standard, Communications of the ACM 34(4): 30-44.

• [5]    Puri, A. 1992. Video coding using the MPEG-1 compression standard, Society for Information

Display Digest of Technical Papers 23: 123-126.

• [6]    J. M. Shapiro, Embedded Image Coding Using Zerotrees of Wavelet Coefficients IEEE Trans. on Signal Processing, Vol. 41, No. 12, pp. 3445 – 3462, Dec. 1993

• [7]    Said A, Pearlman WA. A new fast and efficient image codec based on set partitioning in hierarchical trees, IEEE Transactions on Circuits and Systems for Video Technology 1996;6 pp 243–50.

• [8]    Sudhakar Radhakrishnan, Jayaraman Subramaniam, Novel Image Compression Using Multiwavelets with SPECK Algorithm, The International Arab Journal of Information Technology, Vol. 5, No. 1, January 2008,pp. 45-51.

• [9]    David Taubman,High Performance Scalable Image Compression with EBCOT, IEEE Trans. Image Process., vol. 9, num. 7, pp. 1151-1170, 2000.

• [10]    K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantages, Applications, Academic Press, Boston, 1990.

• [11]    Rafael C. Gonzalez, Richard Eugene,Digital image processing, Edition 3, 2008, page 466.

• [12]    Ken cabeen and Peter Gent,Image Compression and the Descrete Cosine Transform, Math 45, College of the Redwoods.

• [13]    Kamrul Hasan Talukder and Koichi Harada, Discrete Wavelet Transform for Image Compression and A Model of Parallel Image Compression Scheme for Formal Verification, Proceeding of the World Congress on Engineering 2007 Vol I, WCE 2007, July 2-4 2007, London, U.K.

• [14]     http://www.vectorsite.net/ttdcmp 2.html.

• [15]    Amara Graps, An Introduction to Wavelet, IEEE computational science & engineering Summer 1995,vol. 2,num. 2.

  
  
  

Amarjot Singh is a Research Engineer with Tropical Marine Science Institute at National University of Singapore (NUS). He completed his Bachelors in Electrical and Electronics Engineering from National      Institute      of

Technology Warangal. He is the recipient of Gold Medal for Excellence in research for Batch 2007-2011 of Electrical Department from National Institute of Technology Warangal. He has authored and coauthored 48 International Journal and Conference Publications. He holds the record in Asia Book of

Records (India Book of Record Chapter) for having "Maximum Number (18) of International Research Publications by an Undergraduate Student". He has been awarded multiple prestigious fellowships over the years including the prestigious Gfar “Research Scholarship” for Excellence in Research from Gfar Research Germany and “Travel Fellowship” from Center for International Corporation in Science (CICS), India. He has also been recognized for his research at multiple international platforms and has been awarded 3rd position in IEEE Region 10 Paper Contest across Asia-Pacific Region and shortlisted as world finalist (Top 15) at IEEE President Change the World Competition. He is the founder and chairman of Illuminati, a potential research groups of students at National Institute of Technology Warangal (Well Known across a Number of Countries in Europe and Asia). He has worked with number of research organizations including INRIA-Sophia Antipolis (France), University of Bonn (Germany), Gfar Research (Germany), Twtbuck (India), Indian Institute of Technology Kanpur (India), Indian Institute of Science Bangalore (India) and Defense Research and Development Organization (DRDO), Hyderabad (India). His research interests involve Computer Vision, Computational Photography, Motion Tracking etc.