138 Al-Khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 138-145 (2008) Multiwavelet and Estimation by Interpolation Analysis Based Hybrid Color Image Compression Ali Hussien Miry Departement of Mechatroncis Engineering/Al-Khwarizmi Collage of Engineering/University of Baghdad E-mail: alihussien76@yahoo.com (Received 4 March 2008; accepted 21 July 2008) Abstract Nowadays, still images are used everywhere in the digital world. The shortages of storage capacity and transmission bandwidth make efficient compression solutions essential. A revolutionary mathematics tool, wavelet transform, has already shown its power in image processing. The major topic of this paper, is improve the compresses of still images by Multiwavelet based on estimation the high Multiwavelet coefficients in high frequencies sub band by interpolation instead of sending all Multiwavelet coefficients. When comparing the proposed approach with other compression methods Good result obtained. Keywords: Image Processing, MultiWavelet Transform. 1. Introduction With the increasing use of multimedia technologies, address needs and requirements of multimedia and Internet applications, many efficient image compression techniques, with considerably different features, have recently been developed. Image compression techniques exploit a common characteristic of most images that the neighboring picture elements [1-3]. The aim of image compression is to reduce the size of an image with or without loss of information (lossy or lossless compression). One of the most commonly used lossy compression methods is that of transform coding using one of the many images transforms available. The idea of any transform is to transform the image into a new domain, where the image is now represented (approximated) by a set of decorrelated coefficients. However, in order to achieve (lossy) compression, the coefficients containing less important information are removed while those with the most important information are kept. At this point, we can inspect qualitatively (visually) and quantitatively (signal to noise ratio) the compressed image by reconstructing it via the inverse transformation.[4] The discrete wavelet transform (DWT) is being increasingly used for image coding due to the fact that DWT supports features like progressive image transmission (by quality, by resolution). Although this advantage of the transform but may be obtain small Signal to noise ratio. This depended on the nature of the image. Algorithms based on wavelets have been shown to work well in image compression. Theoretically, Multiwavelets should perform even better due to the extra freedom in the design of multifilters [5]. This paper is organized as follows. Section 2 describes color images, the process of the Multiwavelets transform scheme and analysis all the filters and gives a brief overview of the interpolation theorems. The proposed algorithm based on Multiwavelets transform and interpolation is given in the section 3. Finally, conclusions are presented in Section 4. 2. Backgrounds 2.1 Color Image Each component or layer of the image can be viewed as a single channel image, which, under particular conditions, can be analyzed independently from the others. This is not the case mailto:alihussien76@yahoo.com Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 138-145 (2008) 139 for RGB space, because, if two channels are fixed, human visual perception is very sensitive to small changes of the value of the remaining channel .In a typical color image, the spatial intercomponent correlation among the red, green, and blue color components is significant. In order to achieve good compression performance, correlation among the color components is first reduced by converting the RGB image into a decorrelated color space [6].The color space conversion modules transforms Red Green Blue (RGB) encoded data into YCbCr coding. Y represents luminance (based on inverse gamma-distorted data) and CbCr represents chrominance [7].The advantage of converting the image into luminance-chrominance color space is that the luminance and chrominance components are very much decor related between each other the transformation from RGB to YCbCr is done based on the following mathematical expression[1,8]. )1...( 128 128 0 0813.0418.05.0 5.0331.0168.0 114.0587.0299.0                                             B G R C C Y r b Accordingly, the inverse transformation from YCbCr to RGB is done as [1, 8]. From eq. (2) we note that Cr=red component – luminance component And Cb=blue component – luminance component [1]. 2.2 Multiwavelet Transform Multiwavelets constitute a new chapter which has been added to wavelet theory in recent years. Recently, much interest has been generated in the study of the multiwavelets where more than one scaling functions and mother wavelet are used to represent a given signal [6].Multiwavelets bases have been investigated for several years now. With this generalization, it is possible to construct orthogonal (real-valued) bases for which the scaling functions have compact support, approximation order greater than 1, and symmetry, which is not possible with traditional wavelet bases [7]. )2...( 128 128 0 077.11 71.034.01 4.101                                            r b C C Y B G R Multiwavelets are very similar to wavelets but have some important differences. In particular, whereas wavelets have an associated scaling function Φ(t) and wavelet function Ψ(t) , multiwavelets have two or more scaling and wavelet functions. 2.3 Theory of Multiwavelets In particular, whereas wavelets have an associated scaling function (t) and wavelet function (t), multiwavelets have two or more scaling and wavelet functions. For notational convenience, the set of scaling functions can be written using the vector notation (t)[1(t), 2(t)… r(t)] T , where (t) is called the multiscaling function. Likewise, the multiwavelet function is defined from the set of wavelet functions as (t)[1(t), 2(t)… r(t)] T . When r=1, (t) is called a scalar wavelet, or simply wavelet. While in principle r can be arbitrarily large. The multiwavelets studied to date are primarily for r=2. The multiwavelet two-scale equations resemble those for scalar wavelets [9].     k k ktHt )2(2)( …(3)    k k ktGt )2(2)( …(4) Note, however, that {Hk} and {Gk} are matrix filters, i.e., Hk and Gk are r r matrices for each integer k. The matrix elements in these filters provide more degrees of freedom than a traditional scalar wavelet. These extra degrees of freedom can be used to incorporate useful properties into the multiwavelet filters, such as orthogonality, symmetry, and high order of approximation. The key, then, is to figure out how to make the best use of these extra degrees of freedom. One famous multiwavelet filter is the GHM filter proposed by Geronimo, Hardian, and Massopust. The GHM basis offers a combination of orthogonality, symmetry, and compact support, which can not be achieved by any scalar wavelet basis. According to Eqs. (3) and (4) the GHM two scaling and wavelet functions satisfy the following two-scale dilation equations[7]                k k kt kt H t t )2( )2( 2 )( )( 2 1 2 1     …(5)                k k kt kt G t t )2( )2( 2 )( )( 2 1 2 1     …(6) Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 1-7 (2008) 140 Where Hk for GHM system are four scaling matrices H0, H1, H2, and H3,                                                        0 20 1 00 , 210 3 20 9 00 , 2 1 20 9 0 25 3 , 210 3 20 1 5 4 25 3 32 10 HH HH Also, Gk for GHM system are four wavelet matrices G0, G1, G2, and G3,                                                            0 210 1 0 20 1 3 , 10 3 210 9 210 3 20 9 2 , 0 210 9 2 1 20 9 1 , 10 3 210 1 210 3 20 1 0 GG GG 2.4 Multiwavelet in Comparison with Wavelet The multiwavelet idea originates from the generalization of scalar wavelets. Instead of one scaling function and one wavelet, multiple scaling functions and wavelets are used. This leads to more degree of freedom in constructing wavelets. Therefore opposed to scalar wavelets, properties such as orthogonality, symmetry, vanishing moments, can be gathered simultaneously in multiwavelets, which are fundamental in signal processing. The increase in degree of freedom in multiwavelets is obtained at the expense of replacing scalars with matrices, scalar functions with vector functions and single matrices with block of matrices. However, prefiltering is an essential task which should be performed for any use of multiwavelet in the signal processing [9]. 2.5 Interpolation Interpolation is a process for estimating values that lie between known data points. It has important applications in areas such as signal and image processing [10]. Its most general form of this theorem is yi = interp1(x,y,xi,method). y is a vector containing the values of a function, and x is a vector of the same length containing the points for which the values in y are given. xi is a vector containing the points at which to interpolate. Method is an optional string specifying an interpolation method: Nearest Neighbor Interpolation This method sets the value of an interpolated point to the value of the nearest existing data point. Linear Interpolation This method fits a different linear function between each pair of existing data points, and returns the value of the relevant function at the points specified by xi. Cubic Spline Interpolation This method fits a different cubic function between each pair of existing data points, and uses the spline function to perform cubic spline interpolation at the data points. Nearest neighbor interpolation is the fastest method. However, it provides the worst results in terms of smoothness. Linear interpolation uses more memory than the nearest neighbor method, and requires slightly more execution time. Cubic spline interpolation has the longest relative execution time, although it requires less memory than cubic interpolation [11-13]. It produces the smoothest results of all the interpolation methods. You may obtain unexpected results, however, if your input data is non-uniform and some points are much closer together than others. Cubic interpolation requires more memory and execution time than either the nearest neighbor or linear methods. 3. Proposed Method The following steps are followed in the encoder phase: 1. Color space conversion:-in this step the color components RGB are transformed to YCbCr according to eq (1). 2. Multiwavelet transform:-in this step 2D Multiwavelet transform is applied on the input image according to eq (5) and eq (6) after resizing it to power of two [256 x 256]pixels. 3. Thresholding:- the Multiwavelet coefficients whose magnitude values are less than a prespecified value called (Threshold value) are set zero (discarding). So that the transformed image after thresholding will contains long strings of zeros Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 138-145 (2008) 141 4. Ommting some of Multiwavelet coefficients. After thresholding, most of Multiwavelet coefficients in high frequencies subbnads are zero (especially for high compression ratio).For this reason, some of the of Multiwavelet coefficients in these bands can be omitted by sending one coefficient only from each k coefficients, (where a k is positive integer, that affects on the compression ratio) Figures (1-7) show the original image, and their components Fig. 1. Original Image. Fig. 2. Blue Component. Fig. 3. Y Component. Fig. 4. Cr Component. Fig. 5. Red Component. Fig. 6. Green Component. Fig. 7. Cb Component. 3.1 Decompressed Decompression Steps The steps of decompression process are: Step 1: Estimating the missing Multiwavelet coefficient that lie in high frequency sub bands by using interpolation. Step 2: Inverse Multiwavelet transformation is applied on the image. Step 3: Inverse transformation from YCbCr to RGB is applied on the image. Figure 8 shows the flowchart of compressed procedure while figure 9 shows the decompressed procedure. 4. Simulation Results In this section, the implementation results and the performance of the proposed algorithm when compared to other available approaches are presented. The proposed algorithm is implemented using Matlab package with test images with size 256*256 pixels. Table No.1 shows different compression ratio (93%, 95%, 98%, 99%) and the PSNR in dB obtained using the proposed method and wavelet based compression for different color images As briefly discussed in Section 2.4, wavelet and muiltwavlet transform is a powerful signal processing algorithm, and thus many researchers have proposed different modified versions of that algorithm. In this research, multiwavelet and estimation by interpolation is implemented. As seen in Table 1, for most tested images, with the same compression ratio, the PSNR obtained from the proposed algorithm is greater than PSNR of other methods (wavelet and JPEG 2000). The difference between PSNR of a proposed method and other increase especially in high compression ratio (columns 2 and 3 of table 1). This is due to that Multiwavelet coefficients at very high compression are zero (or close to zero) and by interpolation the actual values of the Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 1-7 (2008) 142 coefficients or at least nearest to the actual values coefficients can be estimated. Fig. 8. Compression Procedure. Fig. 9. Decompression Procedure. Start Input Compressed Image 2D Multiwavelet For an Image 2D Inverse Multiwavelet For an Image Estimation the lost coefficients by interpolation Color Conversion from YCbCr to RGB End of Decompressed Start Input Compressed Image 2D Multiwavelet For a Image 2D Inverse Multiwavelet For a Image Estimation the lost coefficients by interpolation Color Conversion from YCbCr to RGB End of Decompressed Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 138-145 (2008) 143 Table 1 Compression Ratio vs. PSNR. Pic. No. Ratio PSNR(dB) 93% 95% 98% 99% Picture. 1 Proposed Algorithm 33.835 dB 31.8150 dB 24.872 dB 28.11 dB Wavelet 27.092 dB 26.7032 dB 23.8323 dB 21.8010 dB JPEG 2000 27.9 dB 27.6 dB 24.01 dB 22.2 dB 2 Proposed Algorithm 32.2 dB 30.4 dB 27.9 dB 26.5 dB Wavelet 31.5 dB 28.5 dB 24.1 dB 23.4 dB JPEG 2000 32 dB 28.9 dB 25.1 dB 23 dB 3 Proposed Algorithm 33.961 dB 33.2676 dB 31.8781 dB 30.0416 dB Wavelet 33.835 dB 31.8150 dB 23.8323 dB 28.11 dB JPEG 2000 33.7 dB 31.9 dB 28.9 dB 28.03 dB 5. Conclusions In this study, the compression approach for color images using the Multiwavelet and estimation by interpolation based mode of operation is proposed. Based on the simulation results obtained in this study, the proposed approach can achieve high- compression ratio with high SNR. Multiwavelet offers the advantages of combining symmetry, and orthogonality, properties not mutually achievable with scalar wavelet systems. However, Multiwavelet differ from scalar wavelet systems in requiring two or more input streams to the Multiwavelet filter bank According to the results in table (1), the obtained subjective tests show the superiority of the proposed algorithm when compared to the wavelet and JPEG 2000 approaches. An important advantage of this method appears at high compression ratio. The proposed algorithm performs even better for smoothness images because the interpolation methods can easily estimate the data smooth region. 6. References [1] M. Golner, W. Mikhael, “Region Based Variable Quantization for JPEG Image Compression” lEEE 2000. [2] M. LIN, “A Hardware Architecture for the LZW Compression and Decompression Algorithms Based on Parallel Dictionaries” International Symposium on VLSI Technology, Systems, and Applications, June 3–5, 2000. [3] M. TIAN, S. WEI, L. ZHI LIAO “An Investigation Into Using Singular Value Decomposition As A Method Of Image Compression” Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, Guangzhou, 18-21 August 2005 IEEE. Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 1-7 (2008) 144 [4] V. Strela, P. N. Heller, G. Strang, P. Topiwala, and C. Heil, “The application of multiwavelet filter banks to image processing”, IEEE Trans. Image Processing, vol. 8, pp. 548–562, Apr. 1999. [5] J. Tham, L.. Shen, S. Lee, and H. H. Tan, “A general approach for analysis and application of discrete multiwavelet transforms” IEEE Trans. Signal Processing, vol. 48, pp. 457– 464, Feb. 2000. [6] M. Moazam, A. Taheri, M. Pooyan” Multiwavelet and Biological Signal Processing”, Transactions on Engineering, Computing and Technology V2 December ISSN pp.1305-5313, 2004. [7] I. Selesnick,” Multiwavelet Bases with Extra Approximation Properties”, IEEE Trans. Inform.Theory, vol. 46, No.11, pp. 2898- 2908, NOVEMBER 1998. [8] T. Acharya, P.Tsai “JPEG2000 Standard for Image Compression Concepts, Algorithms and VLSI Architectures” A JOHN WILEY & SONS, INC., PUBLICATION, 2005. [9] B. Martin and A. Bell “New Image Compression Techniques Using Multiwavelets and Multiwavelet Packets “IEEE Trans. Image Processing, vol. 10, No.4, pp. 500–510, April 2001. [10] M. DEKKER, ”Numerical Methods for Engineers and Scientists” Second Edition, INC. NEW YORK. BASEL 2002. [11] Z. John, “An Introduction to Numerical Analysis For Electrical And Computer Engineers”. ,inc. publication 2004. [12] G. Collins, “Fundamental Numerical Methods and Data Analysis”, II 2003. [13] S. Conte, “Elementary Numerical Analysis” An Algorithmic Approach McGraw-Hill Book Company 1980. Ali Hussien Miry Al-Khwarizmi Engineering Journal, Vol. 4, No. 3, PP 138-145 (2008) 145 استخذاو متعذد تحويم انمويج وطريقة االستكمال نضغظ انصور انمهونة عهي حسين مري جايعت بغذاد / كهيت هُذست انخىاسصيي/ قسى هُذست انًيكاحشوَكس انخالصة في انىقج انحاضش اصبحج عًهيت خضٌ انصىس واسسانها حاخز اهخًايا بانغا وانعذيذ يٍ انبحىد حخطشق انً يسانت ضغظ انصىس حيذ يسخخذو يخعذد ححىيم انًىيج بشكم كبيش في هزا انًجال وفي هزا انبحذ َقخشح طشيقت جذيذة حعخًذ عهً هزا انخحىيم وكزنك عهً انخخًيٍ ورنك باسسال عذد قهيم يٍ يعايالث ححىيم يخعذد انًىيج ويٍ رى حخًيٍ انًعايالث انًفقىدة عىضا عٍ اسسانها . بىاسطت َظشياث االسخكًال .وانُخائج انًسخحصهت يٍ هزة انطشيقت حعخبش افضم يٍ انطشق االخشي وباالخص في َسب انضغظ انعانيت. جًعيا