Multiparametric Wavelet Transforms

Abstract

The main goal of the paper is to show that wavelet transforms and packets have the multiparametric representation in the form of a product of the rotation Jacobi matrices. These representations we call the third and the fourth canonical multiparametric form. Each multiparametric wavelet transform (MPWT) depends on several free Jacobi parameters. When parameters are changed multiparametric transform is changed too taking form of all known and unknown orthogonal wavelet transforms. It gives unified approach to describing a wide set of cyclic orthogonal wavelet transforms and endows with adaptive properties of those transforms.

Keywords

• Wavelet transforms
• fast algorithms
• Jacobi rotation

-

where L  2D . Let m  log2 2D be the smallest positive integer such that 2m1  2D  2m . Let WDT2n h0, h1,..., hL1  nrm11AWT2nr1[h0, h1,..., hL1] I2n2nr1  be arbitrary cyclic wavelet transform, written in stairs-like form. 2 2.1

Third canonical form of MPWT

Multiparametric presentation of atomic wavelet transforms In order to find multiparametric form of wavelet transform we will use the Jacobi rotations. For that we should define the (2n  2n) sparse rotation matrix on an angle  in the plane spanned on i and j basis vectors, where c  cos   and s  sin   : 1   CSi, j ( )  i  0

 j  0    0 i 0 c s 0 j 0 s c 0 0   0 .  0   1 ( 2 ) (3) The angle  0 can be chosen such a way that the coefficient h5  0 in the zeroth and fourth rows in the left product of matrix (3) by CS0,4 ( 0 ) . In this case coefficient h4 will be zero in the same rows too. That is, coefficients are zeroed by couples. The wavelet transform WDT2n is factorized into a product of sparse matrixes, named stairs-like atomic wavelet transform AWT2n h0 , h1, , hL1  . We will multiply the wavelet transform matrix AWT2n h0 , h1, , hL1  by CSi, j ( ) matrix sequentially with such choice of angles  that product CSik , jk (k ) CSi0, j0 (0 )AWT2n h0, h1, , hL1 will be permutation matrix or unit matrix. As an example, we have taken the atomic Daubechies-6 8  8 -matrix:  h0 h1 h2 h3 h4 h5   h0 h1 h2 h3 h4 h5   h4 h5 h0 h1 h2 h3  AWT8 h0,h1,h2,h3,h4,h5    hh52 hh34 hh34 hh52 h1 h0 h0 h1 .

 h1 h0 h5 h4 hh53 hh24 hh13 hh02   h3 h2 h1 h0 h5 h4  if the angle is chosen such that c0h5s0h00 , where c0  cos 0 and s0  sin 0  .

CS3,7(0)CS2,6(0)CS1,5(0)CS0,4(0)AWT8h0,h1,h2,h3,h4,h5     h2 h3    h1 h0 h3 h2 h1 h0 h0 h1 hh02 hh13 h2 h3 

h0 h1 h2 h3  h3 h2 h1 h0 0 h1  AWT8h0,h1,h2,h3.

h h3 h2 h1 h0 h3 h2   (5) As a result we get a new atomic matrix AWT8 h0,h1,h2,h3 with four coefficients. To get the atomic matrix with two coefficients we should iterate foregoing procedure: CS0,7(1)CS3,6(1)CS2,5(1)CS1,4(1)AWT8 h0,h1,h2,h3  AWT8 h0,h1. (6) Reiteration of this procedure on matrix AWT8 h0,h1 results in:

CS1,7(2)CS0,6(2)CS3,5(2)CS2,4(2)AWT8 h0,h1  P8, (7) where P8 is a quasipermutation matrix (there are only 1 or 1 in every row and in every column of it). As the final result we get: CS1,7(2)CS0,6(2)CS3,5(2)CS2,4(2) CS0,7(1)CS3,6(1)CS2,5(1)CS1,4(1) CS3,7(0)CS2,6(0)CS1,5(0)CS0,4(0)AWT8 h0,h1,h2,h3,h4,h5  P8. (8) From here we obtain the multiparametric representation of the atomic wavelet transform matrix:

AWT8 h0, h1, h2, h3, h4, h5   CS3,7 (0 )  CS2,6 (0 )  CS1,5 (0 )  CS0,4 (0 )  CS0,7 (1)  CS3,6 (1)  CS2,5 (1)  CS1,4 (1)  CS1,7 (2 )  CS0,6 (2 )  CS3,5(2 )  CS2,4 (2 )  P8  T80  0   T81  1   T82  2   P8, where ci  cos  i  , si  sin  i  , i  0,1,2 and every matrix T8  i  is the product of the following sparse rotation sin/cos – matrixes:

T800   CS3,70  CS2,60  CS1,50  CS0,40  , T810   CS0,70  CS3,60 CS2,50 CS1,40  ,

T820   CS1,70  CS0,60 CS3,50 CS2,40 .

Let us clarify regularity in the sequences of index’s couples. If r is a number of an iteration within atomic function in multiparametric presentation and i is a number of the matrix T2in   i  , the rule of index’s couples generating could be defined as follows: k  i, k  2nr  .

2nr 0, 4 1, 5 2, 6 3, 7 where T –matrixes are the products of multiplying of CS -matrixes. This result is general and valid for any  2r  2r  atomic matrix:

 D1  P2r   T2ir  i    AWT h0, h1, , h2D1  ,  i0 

 0  AWT h0, h1, , h2D1    iD1T2ir  i   P2r .

(9) (10) (11) (12) (13) It is the multiparametric representation of the atomic orthogonal wavelet transform matrix. 2.2

Multiparametric representations of wavelet transforms and wavelet packets Let’s begin with consideration of 16 16 Daubechies-4 wavelet transform. In the matrix form it is the product of the following atomic matrixes:

WDT16h0, h1, h2, h3   AWT4I12 AWT8I8 AWT16 .

Every atomic matrix AWT4 , AWT8 , AWT16 can be represented in multiparametric form:

AWT4  T40 0  T41  1  P4 , AWT8  T80 0  T81  1  P8 ,

AWT16  T106 0  T116  1  P16.

Therefore,

WDT16 h0, h1, h2, h3   T40 0 T41  1  P4  I12   T80 0 T81 1  P8  I8    0    T106  0  T116   1  P16     T4i (i )  P4  I12  

 i1   0    0      T8i (i )  P8  I8     T1i6 (i )  P16  .

 i1   i1  It is two-parametric form of Daubechies-4 wavelet transform. It is possible to obtain all the transforms of WDT16 h0, h1, h2, h3  -type by changing the angles  0 and 1 . All the atomic matrices in multiparametric representation of wavelet transform are characterized by the same set of angle-parameters. And all the angles have equal values in each atomic matrix and have to be chosen synchronously. Of course, it is possible to use different angles sets in different atomic matrixes and to change them not synchronously, but in this case we will get heterogeneous wavelet transforms. The most general expression for multiparametric presentation of wavelet transform is the following:

WDT2n [h0, h1,..., h2D1]  nrm11  iD01T2inr1(i )  P2nr1 I2n2nr1 ,  where  is addition modulo 2nr . The last expression presents any wavelet trans2nr form in multiparametric form. We will call it the third canonical form. (14) (15) (16) (17) The classical wavelet transform with coefficients h0 , h1,..., h2D1 is constructed from atomic wavelet transforms according to the following rule:

nm1

WDT2n [h0, h1,..., h2D1]  r1 AWT2nr1 [h0, h1,..., h2D1]I2n2nr1 .

The atomic transform is used only once within each iteration in (18). In fact, the atomic transform could be repeated not more then 2n / 2nr1  2r1 times. Let sr  (s1r , s2r ,..., str ,..., s2rr1 ) be a binary 2r 1 -digital integer. Every binary digit str controls the t th position of the matrix AWT2nr 1 in the rth iteration sparse matrix.

A WT str A WT2nr1 , 2nr1    I2nr1 , str  1, str  0.

All such matrices form a packet of atomic matrices

2r1 AWP2snr   AWT2ntr1  AWT2n1r1  AWT2n2r1  ...  AWT2sn2rrr11.

sr sr sr t1 Using atomic packets AWT str

2nr1 , we obtain discrete controlled wavelet packet s1,s2 ,...,snm1 WDP2n

[h0, h1,..., h2D1 ]  nrm11AWP2snr   nrm11 2tr11AWT2sntrr1   nrm11 AWT2sn1rr1  AWT2sn2rr1  ...  AWT2sn2rrr11  s1   s11  , s2   s12 , s22  , s3   s13 , s23 , s33 , s43  , ..., with discrete binary

parameters snm   snm , s2nm ,..., s2nnmm1 .

2 But AWT2sntrr1   0 i str  iD1 T2nr1(i ) 

 we obtain the third multiparametric representation of wavelet packets

sr

P2ntr1 . Substituting this expression in (21), s1,s2 ,...,snm1 WDP2n h0, h1,..., h2D1   nm1 2r1 0 T2inr1(φi ) str r1  t1  iD1 

sr  P2ntr1  . (22)   Multiparametric wavelet packets represent a generalization of multiresolution decomposition and comprise the entire family of subband (tree) decomposition. Wavelet packet best basis selection can be very efficient realize with help of multiparametric wavelet packets. (18) (19) (20) (21) 2.3 The direct multiparametric wavelet transform (MPWT) is defined by expression: nm1  D1  

WDT2n [h0, h1,..., h2D1 ]  r1  i0 T2Dnri11( Di1 )  P2nr 1 I2n 2nr 1 . This is the orthogonal matrix and so its inverse matrix coincides with its transpose one. Transposing of the left and the right sides of equation (23) gives expression for inverse matrix. To do this operation we rewrite expression (23) in more compact form:

Then

WDT2n  nlog2 L1  r1 AWT2nr1 I2n 2nr1 .

  nlog2 L1 WDT2tn    r1

t AWT2nr1 I2n 2nr1      n  AWT2tr I2n 2r  .

rlog2 L  D1  But AWT2r  i0 T2Dr i1 ( Di1 ) P2r , therefore (23) (24) (25) (26) (27) (28) since T( )t  T( ) . Substituting (26) into (24), we get

D1 AWT2tr P2tr i0 T2ir (i ),

n  t D1 

WDT2n1WDT2tn  rq P2r i0 T2ir (i )I2n 2r .

Every matrix T2inr 1 ( i ) is the product of commutative rotation CS -matrixes in the case of direct wavelet transform:

2nr 1 T2Dnir11 ( Di1 ) 

k 0 2r 11 Tir (i )  2 k 0

CSk  i,k 2nr ( Di1 ),

2nr

CSk 2r1(Di1),k 2r 1 (i ).

Substituting (28) into (27), we get the final expression for inverse wavelet transform: WDT2n1 h0, h1,..., h2D1   WDT2n1  0,1,..., D1   where P n is the permutation matrix of ideal 2-adic mixing, which swaps the rows of 2 atomic matrix in stairs-like form AWT2n h0 , h1, , h5  according to the rule The atomic matrixes, which we took up below, were recorded with the “normal” order of rows. That means the averaging h -rows is situated before the differencing g -rows within the atomic matrix. The fourth canonical form of MPWT can be found with using the cyclic presentation of atomic matrix:  h0  g0    CAT8 h0 , h1, , h5    h4  g4  h2  g2 h1 g1 h5 g5 h3 g3 h2 g2 h0 g0 h4 g4 h3 g3 h1 g1 h5 g5 h4 g4 h2 g2 h0 g0 h5 g5 h3 g3 h1 g1 h4 g4 h2 g2 h0 g0    h5  g1  hg5   P8AWT8 h0 , h1, , h5 , 3  g3  h1  (29) (30) (31) (32)  0 1   0 2r1 

In order to find third canonical form of multiparametric wavelet transforms we used the Jacobi rotation matrix CSi, j ( ) . In this case to find fourth canonical form of MPWT we will use the sparse rotation matrix with reflection in the plane spanned on i and j basis vectors. We will designate this matrix as CSiR, j ( ) and its definition is: We will multiply matrix CAT2n h0 , h1, , h2D1  sequentially with rotation-reflection matrixes CS0R1 0  , CS2R3  0  , , CS2RD2,2D1 0  choosing angles  in such way as to product will be the matrix CAT n h0 , h1, , h2D3  with the new set of coeffi2 cients, which quantity less by two then in the source matrix. As an example we take the atomic transform CAT8 h0 , h1, , h5  above mentioned in (31).

Let us to iterate foregoing procedure on the just gotten new atomic matrix. As a result we get a block-permutation matrix with the orthogonal 2  2 blocks:

CS7R0 1 CS5R6 1 CS3R4 1 CS1R2 1   CAT8h0, h1, h2 , h3   CAT8h0, h1. (35) If we will use appropriate rotation-reflection matrixes, we could transform this matrix to permutation one:

CS0R1 2 CS6R7 2 CS4R5 2 CS2R3 2   CAT8h0, h1  1 1

1 CSiR, j ( )   1   i  0   j  0    0            1   1         C82 ,  1     (33) (34) (36) where C82 is the matrix of cyclic modulo 8 shift on two positions. Thus,

T822T811T800CAT8h0,h1, ,h5  C82, where Tini  is product of rotation-reflection matrixes CSkR,l i : 2

T822  CS0R12CS6R7 2CS4R5 2CS2R3 2 , T811  CS7R0 1CS5R6 1CS3R4 1CS1R2 1,

T800  CS6R7 0CS4R5 0CS2R3 0CS0R10 .

Since matrixes T2ini  are both symmetric and orthogonal, then 1 T2ini   Tini  . Therefore

2

CAT8h0,h1, ,h5  CAT80,1,2  1T800T811T822C82, (39) so the atomic wavelet transform matrix can be represented as the following product:

AWT8h0,h1, ,h5  AWT8 0,1,2  1P8 T800 T811T822 C82. (40) Let us to construct the multiparametric form of wavelet transform WT16h0,h1, ,h5 . Since WT16h0,...,h5AWT8h0,...,h5I8AWT16h0,...,h5, then

WT160,1,21P8T800T811T822C82I8

1P16T1060T1161T1262C126.

This result is general and valid for any 2n 2n  atomic matrix: D1  AWT nh0,h1,...,h2D1  AWT n0,1,...,D1  1DP2nTini CDn1  2 2 2 2  i0

 D12n11  1DP2n  CSiR2k,i2k1i CDn1.

 i0 k0 2n 2n  2  Taking into account (18), we get the following multiparametric presentation of cyclic orthogonal wavelet transform, which we call the fourth canonical form:

WDT2n[0,1,...,D1]  1Dnlorg21L1P2nr1 Di01T2inr1i C2Dnr11 I2n2nr1 . (43) Similarly, we get the expression for MPWP, substituting (42) into (24): (37) (38) (41) (42) WDP2n [0 ,1,..., D1]  nlorg21L1  t2r1   1DP2nr1 Di01 T2inr1 i C2Dnr11 .

The inverse multiparametric wavelet transform The matrix AWT2n 0,1, , D1  is the orthogonal matrix and its inverse matrix coincides with its transpose one. Therefore, in order to get expression for inverse multiparamteric atomic wavelet transform, we should transpose the left and the right sides of the equation (42):   D1  t AWT n10,1, , D1   AWT2tn 0,1, , D1   1DP2n    T2in i    CDn1   2   i0  2   1D CDn1 t  D1 t t   2  i0 T2in i  P2tn  1D C2Dn1 t  Di01 T2Dni1 Di1  P2tn . (45) Since TDn i1  Di1  is the product of symmetric and orthogonal rotation-reflection 2 t matrixes CSkR,l Di1  , then equation T2Dni1Di1  T2Dni1Di1  is valid. Hence AWT tn  0 ,1, , D1    1D CDn1 t D1 TDni1 Di1  Ptn . 2  2  i0 2  2 (46) Substituting (45) into (26) we get the expression for inverse MPWT:

WDT2n1[0 ,1,..., D1]   1Drlong2 L C2Dr1 t Di01 T2Dri1 Di1  P2tr I2n 2r . (47) In much the same manner we get the expression for inverse wavelet packets:

WDP2n1[0 ,1,...,D1]  1Drlong2 L  t2r1  C2Dr1 t Di01 T2Dri1Di1 P2tr . (48) 4

MPWT compression properties estimation In order to estimate compression properties of multiparametric orthogonal wavelet transform we have conducted experiments for revealing dependency of spectra’s coefficients entropy E D 0 ,1, , D  on quantity of angle-parameters D and values of angle-parameters i . We use the entropy of spectra’s coefficients, quantized to inteparametric transform) is shown on figure 1. In this paper we defined the new representation of orthogonal wavelet transform, named multiparametric form of cyclic orthogonal wavelet transform. This form is the product of sparse rotation matrixes and it describes fast algorithm for cyclic wavelet transforms. Defined representation of wavelet transform depends on finite set of free parameters, which could be changed independently of one another. For each set of parameters values we get the unique cyclic orthogonal wavelet transform. All of that makes the base for uniform presentation of all same transforms.

Acknowledgments

References

This work was supported by the Ural Federal University's Center of Excellence in ”Quantum and Video Information Technologies: from Computer Vision to Video Analytics” (according to the Act 211 Government of the Russian Federation , contract 02 . A03 . 21 .0006).

1. Daubechies , I. , Sweldens , W. Factoring wavelet transforms into lifting steps . J.Fourier Anal. Appl. , 4 ( 3 ): 247 - 269 , 1998 .

2. Daubechies , I. Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics , Philadelphia, PA, 1992 , 68 p.