W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 26 Al-khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, vol.1, no.1,pp 26-37, (2005) The Determination of Critical-Sampling Scheme of Preprocessing for Multiwavelets Decomposition as 1st and 2nd Orders of Approximations. W. A. Mahmoud* Z. J. M. Saleh** N. K. Wafi* Electrical Engineering Dept / College of Engineering /University of Baghdad*. Information Engineering Dept ./ Al-Khwarizmi Engineering College / University of Baghdad** Abstract One of the important differences between multiwavelets and scalar wavelets is that each channel in the filter bank has a vector-valued input and a vector-valued output. A scalar-valued input signal must somehow be converted into a suitable vector-valued signal. This conversion is called preprocessing. Preprocessing is a mapping process which is done by a prefilter. A postfilter just does the opposite. The most obvious way to get two input rows from a given signal is to repeat the signal. Two rows go into the multifilter bank. This procedure is called “Repeated Row” which introduces oversampling of the data by a factor of 2. For data compression, where one is trying to find compact transform representations for a dataset, it is imperative to find critically sampled multiwavelet transforms schemes which this paper focuses on finding a simple and easy to follow algorithm for its computation. One famous multiwavelet filter used here 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. Using a computer program for the proposed method, an example test on Lena image is verified which shows image properties after a single level decomposition and the reconstructed image after reconstruction. Keyword: Discrete Multiwavelete Transform (DMWT), Inverse Discrete Multiwavelete Transform (IDMWT), Critical-Sampling, Schema of Processing. 1. Introduction As multiwavelet filter banks require a vector-valued input signal, there are a number of ways to produce such a signal from 2-D signal image data. Perhaps the most obvious method is to use adjacent rows and columns of the image data [6]. However, this approach does not work well for general multiwavelets and leads to reconstruction artifacts in the lowpass data after coefficient quantization [6]. This problem can be avoided by constructing “constrained” multiwavelets, which possess certain key properties. Unfortunately, the extra constraints are somewhat restrictive; image compression tests show that constrained multiwavelets do not perform as well as some other multifilters [2]. Another approach is to first split each row or column into two half-length signals, and then use these two half signals as the channel inputs into the multifilter. A naive approach, as Strela points out [6], is to simply take the odd samples for one signal and the even samples for the second signal This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 27 . 2. Multiwavelets Theory As in the scalar wavelet case, the theory of multiwvelets is based on the idea of multiresolution analysis (MRA), analyzing the signal at different scales or resolutions. The difference is that multiwavelets have several scaling functions. The standard multiresolution has one scaling function (t) [2]. 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 [7]. The multiwavelet two-scale equations resemble those for scalar wavelets:    k k ktHt )2(2)( (1)    k k ktGt )2(2)( (2) 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. Multifilter construction methods are already being developed to exploit them. However, the multi-channel nature of multiwavelets also means that the sub-band structure resulting from passing a signal through a multifilter bank is different. Sufficiently different, in fact, so that established quantization methods do not perform as well with multiwavelets as they do with wavelets [2]. One famous multiwavelet filter is the GHM filter proposed by Geronimo, Hardian, and Massopust [3]. The GHM basis offers a combination of orthogonality, symmetry, and compact support, which can not be achieved by any scalar wavelet basis [8]. According to Eqs.(1) and (2) the GHM two scaling and wavelet functions satisfy the following two-scale dilation equations:                k k kt kt H t t )2( )2( 2 )( )( 2 1 2 1     (3)                k k kt kt G t t )2( )2( 2 )( )( 2 1 2 1     (4) where Hk for GHM system are four scaling matrices H0, H1, H2, and H3, [9], , 2 1 20 9 0 25 3 , 210 3 20 1 5 4 25 3 10                            HH                             0 20 1 00 , 210 3 20 9 00 32 HH also, Gk for GHM system are four wavelet matrices G0, G1, G2, and G3, [9],                              0 210 9 2 1 20 9 , 10 3 210 1 210 3 20 1 10 GG                             0 210 1 0 20 1 , 10 3 210 9 210 3 20 9 32 GG There are four remarkable properties of the Geronomo-Hardin-Massopust scaling functions, as follows [2]:  They each have short support (the intervals [0,1] and [0,2]).  Both scaling functions are symmetric, and the wavelets form a symmetric/antisymmetric pair.  All integers translates of the scaling functions are orthogonal.  The system has second order of approximation. While the very first multiwavelet literature goes back further [7], some of the earliest developed multiresolution theory of multiwavelets can be found in a paper by Goodman et al. [10]. Strela's in his Ph.D. thesis [6] extends the theory of multiwavelets even further and presents it in terms of PR multifilter banks in both the time and frequency domains. The 2×2 matrix filters in our multiwavelet filter bank require vector inputs. Thus, a 1-D input signal must be transformed (5) (6) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 28 into two 1-D signals. This transformation is called pre-processing. For some multiwavelets, the pre-processing must be accompanied by an appropriate pre-filtering operation that depends on the spectral characteristics of the multiwavelet filters [11]. However, some multiwavelets obviate the pre-filtering (and the pre-processing) operation due to certain desirable properties of their basis functions; these multiwavelets are called balanced multiwavelets [1]. 3. A Critically-Sampled Scheme of Preprocessing: Approximation-Based Preprocessing A different way to get input rows for the multiwavelet filter bank is to preprocess the given scalar signal f [n]. For data compression, where one is trying to find compact transform representations for a dataset, it is imperative to find critically sampled multiwavelet transforms schemes [3]. A preprocessing algorithm based on the approximation properties of the continuous-time multiwavelets, which yields a critically sampled signal representation suggested by J. Geronimo and developed by V. Strela, P. Niels, and G. Strang [2]. Let the continuous-time function f (t) belong to the scale-limited subspace V0 generated by translates of the GHM scaling functions. This means that f (t) is a linear combination of translates of those functions [2]:   n nn ntvntvtf )()()( 2 )0( ,21 )0( ,1  (7) Suppose that the input sequence f [n] contains samples of f (t) at half-integers: ).2/1(]12[ ),(]2[  nfnfnfnf (8) 1(t) vanishes at all integer points. 2(t) is nonzero only at the integer 1. Sampling the eq. (8) at integers and half-integers gives: )0( ,22 )0( ,11 )0( 1,22 )0( 1,22 )2/1()2/1()2/3(]12[ )1(]2[ nnn n vvvnf vnf       The coefficients )0( ,2 )0( ,1 , nn vv can be easily found from (9): )1( ]22[ )2/1()1( ]2[)2/3(]22[)2/1(]12[)1( 2 )0( ,2 12 222)0( ,1        nf v nfnfnf v n n Taking into account the symmetry of 2(t), )1( ]22[ )2/1()1( ])2[]22[)(2/1(]12[)1( 2 )0( ,2 12 22)0( ,1        nf v nfnfnf v n n The eq. (11) give a natural way to get two input rows )0( ,2 )0( ,1 , nn vv starting from a given signal f [n]. To synthesize the signal on output, invert eq.(11) and recover eq.(9) [2]. 4. Multiwavelets Transform Computation: Basic Principles For computing Discrete Multiwavelet Transform, a transform matrix can be written as follows [12]:                 ..................... ...00 ...00 ...00 ...00 3210 3210 3210 3210 GGGG HHHH GGGG HHHH where Hi and Gi are the low- and high-pass filter impulse responses. They are 2-by-2 matrices which can be written as follows:                                 ........................... ........................... ...0000 ...0000 ...0000 ...0000 ............... ............... ............... ............... 1,10,11,10,1 1,00,01,00,0 1,10,11,10,1 1,00,01,00,0 1,10,11,10,1 1,00,01,00,0 1,10,11,10,1 1,00,01,00,0 1100 1100 1100 1100 1100 1100 1100 1100 GGGG GGGG HHHH HHHH GGGG GGGG HHHH HHHH By examining the transform matrices of the DAUB4 scalar wavelet [13] and the corresponding one of multiwavelets as shown in (12), one can see that in the multiwavelets transform domain there are first and second low- pass coefficients followed by first and second high pass filter coefficients rather than one low- pass coefficient followed by one highpass coefficient. Therefore, if we separate these four coefficients, there are four subbands in the transform domain [14]. (9) (10) (11) (13) (12) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 29 5. A General Procedure for Computing DMWT Using a Critically-Sampled Scheme of Preprocessing A general procedure can be made for computing a single-level 2-D discrete multiwavelets transform using GHM four multifilters and using a critically-sampled scheme of preprocessing (approximation-based scheme of preprocessing) described in sec.3. By using a critically-sampled scheme of preprocessing (approximation-based scheme of preprocessing), the DMWT matrix has the same dimensions of the input which should be a square matrix NN where N must be power of 2. Transformation matrix dimensions which should be equal to image dimensions after preprocessing will be NN for a critical-sampled scheme of preprocessing. There are two orders of approximation types of critically-sampled preprocessing 1st order and 2nd order approximations. For the eq.(10) and using GHM scaling function graph (Fig. 1a), values for 1(1/2), 2(1/2), 2(1) and 2(3/2) should be found for first order approximation. For any NN image matrix and using the eq. (10), 1st order approximation-based preprocessing can be summarized as follows where every two rows generate two new rows: a- For any odd row, row])-evenious(3/2)[prevrow]-evennext )[2/1( row]-oddsame)[1(( )2/1()1( 1 row-oddnew 22 2 12      (14) b-For any even-row, )1( row-evensame row-evennew 2  (15) It can be seen from Fig. 1a that the values of 1(t) and 2(t) are non-zero for t values of [0, 2]. Since these functions are generated from a 256 sample then: 1. 1(1/2) = the 64th value in the iterated vector of 1, 2. 2(1/2) = the 64th value in the iterated vector of 2 = 2(3/2), 3. 2(1) = the 128th value in the iterated vector of 2. substituting values of 1(1/2), 2(1) and 2(1/2) in Eqs.(14) and (15) for 1st order approximation results, row]-even previous)[11086198.0(row]-evennext )[11086198.0( row]-odd same)[373615.0(row-oddnew   (16) row]-evensame)[12(row-evennew  (17) for 2nd order approximation, Eqs. (16) and (17) become, row]-even previous)[28/3(row]-evennext )[88/3( row]-oddsame)[28/10(row-oddnew   (18) row]-evensame[row-evennew  (19) It should be noted that when computing the first odd row, the previous even-row in eq. (16) is equals to zero. In the same manner, when computing the last odd row, the next even-row in Eq. (16) is equals to zero. The same thing is valid for eq. (18). It is obvious now why the dimension of the resulting matrix after approximation-based preprocessing has the same dimension as before preprocessing. The following procedure for computing DMWT using approximation-based preprocessing is valid for both 1st and 2nd order of approximation with one exception of using Eqs.(16) and (17) for 1st order approximation preprocessing step and Eqs. (18) and (19) for 2nd order approximations preprocessing step: 1.Checking image dimensions: Image matrix should be a square matrix, NN matrix, where N must be power of 2. So checking input image dimensions is the first step of the transform procedure. If the image is not a square matrix some operation must be done to the image like resizing the image or adding rows or column of zeros to get a square matrix. 2.Constructing a transformation matrix: Using the transformation matrix (12) format, an N/2N/2 transformation matrix should be constructed using GHM low- and high-pass filters matrices given in (5) and (6) respectively. After substituting GHM matrix filter coefficients values as given by This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 30 (13), an NN transformation matrix results with same dimensions of input image dimensions after preprocessing. 3.Preprocessing rows: Approximation-based row preprocessing can be computed by applying Eqs. (16) and (17) to the odd- and even-rows of the input NN matrix respectively for the 1st order approximation preprocessing. For 2nd order approximation preprocessing, Eqs. (16) and (17) are replaced with Eqs. (18) and (19) for preprocessing odd- and even-rows of the input NN matrix respectively. Input matrix dimensions after row preprocessing is the same NN. 4. Transformation of image rows: i. Apply matrix multiplication to the NN constructed transformation matrix by the NN row preprocessed input image matrix. ii. Permute the resulting NN matrix rows by arranging the row pairs 1,2 and 5,6 …, N3, N2 after each other at the upper half of the resulting matrix rows, then the row pairs 3,4 and 7,8,…, N1,N below them at the next lower half. 5.Preprocess columns: to repeat the same procedure used in preprocessing rows, i. Transpose the row transformed NN matrix resulting from step 4. ii. Repeat step 3 to the NN matrix (transpose of the row transformed NN matrix) which results in NN column preprocessed matrix. 6.Transformation of image columns : transformation of image columns is applied next to NN column preprocessed matrix as follows: i. Apply matrix multiplication to the NN constructed transformation matrix by the NN column preprocessed matrix. ii. Permute the resulting NN matrix rows by arranging the row pairs 1,2 and 5,6 …, N3, N2 after each other at the upper half of the resulting matrix rows, then the row pairs 3,4 and 7,8,…, N1, N below them at the next lower half. 7.The Final Transformed Matrix: to get the final transformed matrix: i. Transpose the resulting matrix from column transformation step. ii. Apply coefficients permutation [15] to the resulting transpose matrix. The final DMWT matrix using approximation-based preprocessing has the same dimensions, NN, of the original image matrix. 6. A General Example for Computing DMWT Using a Critically-Sampled Scheme of Preprocessing To verify the general procedure for computing single-level DMWT using critically- sampled scheme of preprocessing, let’s take a general 2-D signal, for example any 88 matrix, and apply the following steps: 1. Let X be the input 2-D signal,                            7,76,75,74,73,72,71,70,7 7,66,65,64,63,62,61,60,6 7,56,55,54,53,52,51,50,5 7,46,45,44,43,42,41,40,4 7,36,35,34,33,32,31,30,3 7,26,25,24,23,22,21,20,2 7,16,15,14,13,12,11,10,1 7,06,05,04,03,02,01,00,0 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx X 2. For an 88 matrix input 2-D signal, X, construct a 44 (N/2N/2) transformation matrix ,W2, using GHM low- and high- pass filters,              1032 1032 3210 3210 2 GGGG HHHH GGGG HHHH W As GHM filters, H’s and G’s, are 22 matrices, the transformation matrix, W2, dimension after substituting filters coefficients values will be 88 (NN) matrix with same dimension of the input matrix after approximation-based preprocessing. (20) (21) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 31 3. Apply row preprocessing to the input 2-D matrix, X, using approximation-based preprocessing which results in a matrix, even odd even odd even odd even odd a rows preprocess even odd even odd even odd even odd 7,76,75,74.73,72,71,70,7 7,66,65,64.63,62,61,60,6 7,56,55,54.53,52,51,50,5 7,46,45,44.43,42,41,40,4 7,36,35,34.33,32,31,30,3 7,26,25,24.23,22,21,20,2 7,16,15,14.13,12,11,10,1 7,06,05,04.03,02,01,00,0 7,76,75,74.73,72,71,70,7 7,66,65,64.63,62,61,60,6 7,56,55,54.53,52,51,50,5 7,46,45,44.43,42,41,40,4 7,36,35,34.33,32,31,30,3 7,26,25,24.23,22,21,20,2 7,16,15,14.13,12,11,10,1 7,06,05,04.03,02,01,00,0                                                           aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx X i- 1st order approximation-based preprocessing, any odd row in the approximation preprocessed [a] matrix can be found from its corresponding odd row of [X] matrix with the even row previous and next to it in the [X] matrix. In the same manner any even row in [a] matrix can be found from its corresponding even row of [X] matrix. Using Eqs.,(16) and (17), this can be done as follows, ])[11086198.0(])[11086198.0( ])[373615.0( row-even previousrow-evennext row-oddsamerow-odd XX Xa   ])[12( row-evensamerow-even Xa  ii- 2nd order approximation-based preprocessing, any odd row in the approximation preprocessed [a] matrix can be found from its corresponding odd row of [X] matrix with the even row previous and next to it in the [X] matrix. In the same manner any even row in [a] matrix can be found from its corresponding even row of [X] matrix. Using Eqs.,(18) and (19), this can be done as follows, ])[28/3(])[28/3( ])[28/10( row-evenpreviousrow-evennext row-oddsamerow-odd XX Xa   ][ row-evensamerow-even Xa  4. Row transformation is performed as follows, i. let, [ z ]= [W2][a] (27) ii. permute [z],                            7,76,75,74,73,72,71,70,7 7,66,65,64,63,62,61,60,6 7,56,55,54,53,52,51,50,5 7,46,45,44,43,42,41,40,4 7,36,35,34,33,32,31,30,3 7,26,25,24,23,22,21,20,2 7,16,15,14,13,12,11,10,1 7,06,05,04,03,02,01,00,0 zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzxzzzz zzzzzzzz zzzzzzzz z                            7,76,75,74,73,72,71,70,7 7,66,65,64,63,62,61,60,6 7,36,35,34,33,32,31,30,3 7,26,25,24,23,22,21,20,2 7,56,55,54,53,52,51,50,5 7,46,45,44,43,42,41,40,4 7,16,15,14,13,12,11,10,1 7,06,05,04,03,02,01,00,0 zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzxzzzz zzzzzzzz zzzzzzzz p 5. Apply column transformation, i. transpose [p] matrix.                            7,77,67,37,27,57,47,17,0 6,76,66,36,26,56,46,16,0 5,75,65,35,25,55,45,15,0 4,74,64,34,24,54,44,14,0 3,73,63,33,23,53,43,13,0 2,72,62,32,22,52,42,12,0 1,71,61,31,21,51,41,11,0 0,70,60,30,20,50,40,10,0 t zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz p ii. preprocess [p]t in the same manner of preprocessing described in step 3 (i and ii) above to get [P] matrix. iii. let [b] = [W2][P] (30) iv. permute [b] to get [B] matrix which is 88 matrix also.                            7,7 7,6 7,5 7,4 7,3 7,2 7,1 7,0 6,7 6,6 6,5 6,4 6,3 6,2 6,1 6,0 5,7 5,6 5,5 5,4 5,3 5,2 5,1 5,0 4,7 4,6 4,5 4,4 4,3 4,2 4,1 4,0 3,7 3,6 3,5 3,4 3,3 3,2 3,1 3,0 2,7 2,6 2,5 2,4 2,3 2,2 2,1 2,0 1,7 1,6 1,5 1,4 1,3 1,2 1,1 1,0 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0,0 b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b                            7,7 7,6 7,3 7,2 7,5 7,4 7,1 7,0 6,7 6,6 6,3 6,2 6,5 6,4 6,1 6,0 5,7 5,6 5,3 5,2 5,5 5,4 5,1 5,0 4,7 4,6 4,3 4,2 4,5 4,4 4,1 4,0 3,7 3,6 3,3 3,2 3,5 3,4 3,1 3,0 2,7 2,6 2,3 2,2 2,5 2,4 2,1 2,0 1,7 1,6 1,3 1,2 1,5 1,4 1,1 1,0 0,7 0,6 0,3 0,2 0,5 0,4 0,1 0,0 b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b B 6. The final DMWT matrix [Y]results from apply the following: i. transpose [B] matrix to get [y] matrix ii. apply coefficients permutation to each of the four basic subbands of matrix [y] to get the final DMWT matrix [Y].                        7,76,75,74,73,72,71,70,7 7,66,65,64,63,62,61,60,6 7,56,55,54,53,52,51,50,5 7,46,45,44,43,42,41,40,4 7,36,35,34,33,32,31,30,3 7,26,25,24,23,22,21,20,2 7,16,15,14,13,12,11,10,1 7,06,05,04,03,02,01,00,0 ][ yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy y (31) (28) Permute Permute (24) (22) (23) (25) (26) (29) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 32                        7,75,76,74,73,71,72,70,7 7,55,56,54,53,51,52,50,5 7,65,66,64,63,61,62,60,6 7,45,46,44,43,41,42,40,4 7,35,36,34,33,31,32,30,3 7,15,16,14,13,11,12,10,1 7,25,26,24,23,21,22,20,2 7,05,06,04,03,01,02,00,0 ][ yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy yyyyyyyy Y 7. A Computer Test Two general computer programs computing a single-level DMWT using a critical-sampled scheme of preprocessing (1st and 2nd order approximation) are written using MATLAB v.6.5 for a general NN 2-D signal (or image). An example test is applied to “Lena” image by using this computer program of the proposed method for computing discrete multiwavelets transform using a critical-sampled scheme of preprocessing and the results are shown in Fig.2 and Fig.3for the 1st and 2nd order approximations respectively. As shown in both Figs.2 and 3, the original “Lena” image, Fig. 2a, and 3a dimensions are 512512 (NN). After a single-level of multiwavelets decomposition using a critical- sampled scheme of preprocessing, image dimensions will be a matrix of 512512 (NN) as shown in Figs. 2b and 3b. The upper-left most, L1L1, subband of 128128 dimension, is zoomed in as in Figs. 2c and 3c. 8. A General Procedure for Computing Inverse DMWT Using a Critically-Sampled Scheme of Postprocessing To reconstruct the original 2-D signal (NN matrix) from the discrete multiwavelets transformed 2-D signal the Inverse Discrete Multiwavelets Transform (IDMWT) should be used. A general procedure can be followed for computing a single-level 2-D discrete multiwavelets inverse transform using GHM four multifilters and using a critically-sampled scheme of postprocessing (approximation-based scheme of postprocessing). By using a critically-sampled scheme of preprocessing (approximation-based scheme of preprocessing), the DMWT matrix has the same dimensions of the input which should be a square matrix NN where N must be power of 2. So, to reconstruct the original NN matrix, a reconstruction matrix, which is the inverse (or transpose) of transformation matrix given (12), dimensions should be equal to critical-sampled preprocessed DMWT NN matrix dimensions. As there are two orders of approximation types of critically-sampled preprocessing, 1st order and 2nd order approximations, there are correspondingly two types of critically-sampled postprocessing methods that should be followed; one for each order of approximations. To compute a single-level 2-D Inverse Discrete Multiwavelets Transform using critically-sampled scheme of postprocessing, the next steps should be followed: 1. Coefficients Shuffling [15], which is applied to the DMWT NN matrix four basic subbands individually. For each subband, coefficients shuffling, shuffles columns first then rows. 2. Column reconstruction, i. Transpose the coefficients shuffled NN matrix. ii. Apply shuffling by arranging the row pairs 1,2 and 3,4,…,(N/2)1,N/2 of the coefficients shuffled NN matrix transpose to be the row pairs 1,2 and 5,6,…, N3, N2 of the resulting matrix and arranging the row pairs (N/2)+1,(N/2)+2 and (N/2)+3,(N/2)+4,…, N1,N of the coefficients shuffled 2N2N matrix transpose to be the row pairs 3,4 and 7,8,…, N1, N of the resulting matrix. iii. Multiply an NN reconstruction matrix (NN transformation matrix (12) transpose) with the resulting NN shuffled matrix from ii. 3. Postprocessing, a critical-sampled scheme of postprocessing can be computed as follows: i. 1st order approximation postprocessing: can be computed by applying the equations: Coff. Perm. (32) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 33 )373615.0(/ row]]-even previous)[11086198.0(row]-evennext [ )11086198.0(row]-odd same[[row-odd   (33) )12(row]/-evensame[row-even  (34) to the odd- and even-rows of the column reconstructed NN matrix respectively. ii. 2nd order approximation postprocessing: can be computed by applying the equations: )28/10(row]]/-even previous)[28/3( row]-evennext )[88/3(row]-oddsame[[row-odd   (35) row]-evensame[row-even  (36) to the odd- and even-rows of the column reconstructed NN matrix respectively. 4. Row reconstruction i. Transpose the postprocessed NN resultant matrix. ii. Apply shuffling by arranging the row pairs 1,2 and 3,4,…,(N/2)1,N/2 of the NN postprocessed resultant matrix transpose to be the row pairs 1,2 and 5,6,…, N3, N2 of the resulting matrix and arranging the row pairs (N/2)+1, (N/2)+2 and (N/2)+3, (N/2)+4,…, N1, N of the NN postprocessed resultant matrix transpose to be the row pairs 3,4 and 7,8,…, N1, N of the resulting matrix. iii. Multiply a NN reconstruction matrix (NN transformation matrix (12) transpose) with the resulting NN shuffled matrix from ii 5. Postprocessing, a critical-sampled scheme of postprocessing can be done by the same process of step 3 above which results in the NN original reconstructed 2-D signal matrix. 9. A General Example for Computing Inverse DMWT Using a Critically-Sampled Scheme of Postprocessing To verify IDMWT procedure in the previous section, apply it to the 88 matrix, [Y], given in (32) as the NN critically-sampled preprocessed DMWT matrix to reconstruct 88 matrix, [X], given in (20) as the NN original 2- D signal matrix as follows: 1. Apply coefficients shuffling to each subband of [Y] matrix of (32) which results in [y] matrix of (32). 2. Column reconstruction applied now to [y] matrix of (32), i. transpose [y] to get [B] matrix given in (31). ii. apply shuffling to [B] matrix given in (31) to have [b] matrix of (31) as a result of shuffling. iii. using [W2] matrix given in (21), [P] = [W2] t [b] (37) 3. Postprocessing [P] matrix results in [p]t given in (29). 4. Row reconstruction applied on [p] matrix, i. transpose [p] t matrix of (29) which results in [p] matrix of (28). ii. apply shuffling to [p] matrix given in (28) to get [z] matrix of (28) as a result of shuffling. iii. using [W2] matrix given in (21), [a] = [W2] t [z] (38) [a] is given in (22). 5. Critically-sampled postprocessing [a] matrix results in [X] of (20) which is the original reconstructed 2-D signal. 10. A Computer Test Two general computer programs computing a single-level IDMWT using a critical-sampled scheme of postprocessing (1st and 2nd postprocessing) are written using MATLAB v.6.5 for a general 2N2N 2-D decomposed image. An example test is applied to the decomposed Lena image shown in Figs.2b and 3b to reconstruct the original “Lena” image by using those computer programs of the proposed This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 34 method of computing inverse discrete multiwavelets transform using 1st and 2nd order approximations postprocessing respectively and the results is shown in Fig.4. 11. Conclusion Multiwavelets filter banks require a vector-valued input signal. This is another issue which is addressed when multiwavelets are used in the transform process. A scalar-valued input signal must somehow be converted into a suitable vector-valued signal. This conversion is called preprocessing. The most obvious way to get two input rows from a given signal is to repeat the signal using repeated row preprocessing (Over-sampled scheme of preprocessing). An approximation- based preprocessing algorithms have been also used as a critical-sampled scheme of preprocessing the signal. Using a critical-sampled scheme of preprocessing (Approximation-based preprocessing) ensures the same original image dimensions while using an over-sampled scheme of preprocessing (repeated row preprocessing) introduces an oversampling of data by a factor of 2 which doubles the original image dimensions. In the same time, the upper-left most subband (L1L1) of the decomposed image using critical- sampling scheme of preprocessing, which usually the 2nd, 3rd,… levels of decompositions are applied to it, has quarter dimensions of the original while the upper-left most subband (L1L1) of the decomposed image using an over-sampled scheme of preprocessing has half dimensions of the original. So that critical-sampled representation of the signal minimizes the redundancy for data compression applications. It should be mentioned here also that Discrete Multiwavelets Transform computation algorithm using a critical-sampled scheme of preprocessing (approximation-based preprocessing) should be applied to a matrix with a size at least equal to 88. Also matrix approximation scheme is the scheme that is chosen for multiwavelet compression. Such a scheme will keep the same size of the matrix to be transformed after preprocessing. (b) (a) Fig. 1: GHM Pair of , (a) Scaling Functions, (b) Multiwavelets. Fig.2: Lena Image, (a) Original, (b) After Single- Level of DMWT Using a Critical-sampled Scheme of Preprocessing(1st Order Approx.) and, (c) Zoomed In Upper-Left Most, L1L1 , Subband of (b). (a) (b) (c) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 35 (a) (b) Fig.3: Lena Image, (a) Original, (b) After Single-Level of DMWT Using a Critical-sampled Scheme of Prepro.(1st Order Approx.) and, (c) After Single-Level of DMWT Using a Critical-sampled Scheme of Prepro. (2nd Order Approx.) (b) Fig.4: (a) Reconstructed Lena Image Using IDMWT and 1st Order Approx. Postprocessing, (b) Reconstructed Lena Image Using IDMWT and 2nd Order Approx. Postprocessing, and (c)Original Lena Image (a) (c) (c) This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 36 12. References 1. Michael B. Martin, Applications of Multiwavelets to Image Compression, M.Sc. Thesis in Electrical Engineering, Virginia Polytechnic Institute and State University(Virginia Tech),Blacksburg, Virginia, June, 1999. 2. Vasily Strela, Peter Niels Heller, Gilbert Strang, Pankaj Topiwala, and Christopher Heil, The Application of Multiwavelet Filterbank to Image Processing, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 8, No. 4, pp(548-563),April 1999. 3. J. Geronimo, D. Hardin, and P. R. Massopust, Fractal Function and Wavelet Expansions Based on Several Functions, J. Approx. Theory, vol.78, pp(373-401), 1994). 4. Yun Q. Shi, Huifang Sun: Image and Video Compression for Multimedia Engineering, Fundamentals, Algorithms, and standards, CRC Press LLC, 2000. 5. Panrong Xiao: Image Compression By Wavelet Transform, M.Sc. Thesis, Dept. of Computer and Information Science, East Tennessee State University, August, 2001. 6. Vasily Strela, Multiwavelets: Theory and Applications, Ph.D. thesis, Massachusetts Institute of Technology, 1996. 7. Michael B. Martin and Amy E. Bell, Member, IEEE, New Image Compression Techniques Using Multiwavelets and Multiwavelet Packets, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 10, NO. 4, APRIL 2001. 8. Daubechies, Ten Lectures on Wavelets, pp.(251-254), SIAM, 1992. 9. V. Strela and A. T. Walden, Orthogonal and biorthogonal multiwavelets for signal denoising and image compression, Proc. SPIE, 3391:96-107, 1998. 10. T. N. T. Goodman and S. L. Lee, Wavelets of multiplicity r, Trans. of the Amer. Math. Society, 342(1):307-324, March 1994. 11. P. P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice Hall, Englewood Cli_s, NJ, first edition, 1993. 12. S. Dunn: Digital Color, http://davis.wpi.edu/~matt/courses/color. 13. K. Sayood, and Morgan Kaufmann, Introduction to Data Compression, lecture 01-2003 Spring Text Book, Second edition, Academic Press, http:// www.cs.sunysb.edu/~amohr/cse391/200 3-spring/ lectures/cse391-lecture01.pdf. 14. J. Ziv, A. Lempel: A Universal Algorithm for Sequential Data, Compression, IEEE Trans. Inform. Theory, 1977, vol. 23, no. 3, pp. 337- 343. 15. W. A. Mahmoud, Z. J. M. Saleh, and N. K. Wafi, A Simple and Easy to Verify Algorithm For Computing GHM Multiwavelets Transform and Inverse Transform Using an Over-Sampled Scheme of Preprocessing and Postprocessing Respectively, Journal of Engineering, College of Engineering, University of Baghdad, accepted for publication, EEN/68, 2004. !! !! !! !! !!This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ W. A. Mahmoud /Al-khwarizmi Engineering Journal ,vol.1, no. 1,PP 26-37 (2005) 37 !! !! !! !! œ! ƒ! ! !Œ!!!!!! !! ! ƒ! š!!!! ! œ! !Œ!ž !! ! !Œ!!Œ!! ! Œ!! œƒ!! !!!! ! š!Œ!! !! !! !Œ!¾ƒ!! !!Œ!! œ! š!!! ! !! ! Œ!! !!! !Œ!! ! !! œ!ƒ! !!!! Œ!!! !! !! !! !! !!!! ! š! !! ƒ! Œ!!ƒ!!!!!!!!!!!!!!!!!!!! š! !¾! ! !!œƒ!!Š!œ!!!!!!!!!!!!!!!! !!!! !! !¾ƒ!! !! Œ! !!!! !! !œ!!! ! ! !!!! ! !!! !!!!! !!! ! !!! !!!! !!!!!!!! !!!Ÿ! !Š!! ! !! !! ! !Ÿ! !!!! ! !!! !!! !!! ! ! ! !! ! !!!! ! !!! !! !!!!!!!! !!!Ÿ! !Š!! ! ! ! ! !Œ!!! !!!!!!!!!!! Œ! !! Œ! ! ! ! ! Œ!! Œ!! ¾œ! !Œ! ! œƒ! !! !¾! ! Œ! ¾ƒ! š!!Œ! ! !! !ƒ! ! !Œ! ! ! ƒ! ! !Œ! ¾ƒ! š!! ! ! œ! ƒ! ! !Œ! !!!!! ! ! ! ƒ! š!! ! ƒ!! ! œ!! !! œ! ƒŒ!! ƒ!!!! ! Œ!! ! Œ! ! Œ!! œƒ! !! !œ! !! ! ! !!ƒ!! ! ƒ!!!! !!¾ƒ! š!! ! ! !! Œ! ! œ!šƒ! ! ƒš! ! !! !šŒ! ! ! ! ! ! ! ! ! ! !!!! ! ƒ! œƒ!! !Œ! !! œ! ! Œ!! Œ ! ! Ž! œ! ! !Œ! ! œ! ƒ! ! !Œ!DMWT! !Ž! œ! ! ! ! ! Ž! ! ! Œ!! ¾œ! !Œ! ! œƒ! !! ! ! !Œ!! !! !Œ! !ƒ! !!!! ! !ƒ! ! ! !œ! ƒŒ! ! ! ! !!! ! •! ƒ!! !!! œƒ! ! ! Ž! œ! ! !! ! Ž! !! !!! ƒ! œƒ!! !Œ!!!º !!! ƒ! ! !!Œ!! !!! ƒ!! !!Œ!!!! !! ! !!!!! !!! ! !Œ!! ! !œ!! !Œ!!! !! !!Š! ! ! !! ! œ! ! !!!!!!!!!Š! ! ! !Œ!œ! ! ! !!!! !! !! !! ƒ!ž š! !Œ!!!!! œ! ! Œ!! Œ! !!!! !!! ! !ƒ!! !ƒ!! !!! œ! Œ!! ! !! œƒ! !! !Œ!! ! !! ƒŽ! !! !! !¾! ! š!!!! !ƒ! ! !Š! ! !!! Œ!!! ! !! !!Œ ! ƒ!œ! ! Œ! !!Œ! ! ! !œ!! !Œ! ¾œ! !!! œ!! ! !! !Œ! ! ! !!! ! !!! !! !! ¾! œ!!Œ! ! Œ!!! !! ! ƒ!œ! Œ! ! ! !! !! ¾! !!! ! !ƒ! ! !Œ!Ï! !!! ! !! !!Œ! ! !!!Œ! !!! ! ! ! š!Œ!! ! !! !! !Œ!! ! ƒ!! !!œ!!œ! œƒ!!! !!Œ!! œ!œ! š!! !Œ!! œ!š!!¾œš!! !!! !! !! ! ! !•! ƒ!! ! Œ!Š! ! ! !Œ!! ! ! !! Œ!! !!œ! !!!œ!!! ƒ!œ! ! Œ!! !! š!ƒ!!! Ž!Œ!! œ!!! œ! ! !!! !Œ!! ƒ!! !!! œ!ƒ!! !!! Ž!!•! !!!! ! !! !!! Œ!!! !!œ! !!œ! !!œƒ! !! !!! ƒ!! !œ! !!! ! ! ! ! !Œ!! ƒ! !! !! Ž!Œ!! !Œ! Œ!! ! ! ! !Œ! ! Œ! !!!! ! !!! ! !Œ! ! ! !œ!! !Œ! !! ! !! Ž! ! !!! ! !!! ! !Œ! ! ! !œ!! !Œ! ! !ƒ! ! ! ! Œ!! ƒ! !!!œ!! !!! ! ! !! ! ! !ƒ! ! ! ! ! ! ! ! ! œ! !! Œ! !! ! ! ! ! ! œ! !šŒ!! !! ! ! !! !! ! !Œ!! œ!œ! š!Œ!! ! !¾!!ƒ! ! !!Œ! ! ! ! š! ! !! !! !¾ƒ!! !!! ! š!!Œ!Œ!! ! ! !!œ! !œ! š!!DMWT! !Œ!! !œ! Œ!œ! !!Œ! !! ! ! ! œƒ! !! !Œ!! ƒ!! !!! œ!œ! š!! !!! !! Ž!Œ!¾ƒ!!!!! !! This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/