Multiparametric Wavelet Transforms Labunets .V.G.1, Komarov D.E.1 Ostheimer E.V.2 1 Ural Federal University, pr. Mira, 19, Yekaterinburg, 620002, Russian Federation komde93@gmail.com 2 Capricat LLC 1340 S. Ocean Blvd., Suite 209 Pompano Beach 33062 Florida USA katya@capricat.com 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 describ- ing a wide set of cyclic orthogonal wavelet transforms and endows with adap- tive properties of those transforms. Keywords: Wavelet transforms, fast algorithms, Jacobi rotation. 1 Introduction The wide class of orthogonal wavelet transforms WT can be defined by two sets of coefficients 1, 2: h 0 , h1 , …, hL 1 and g 0 , g 1 , …, g L 1 , where L  2 D is an even number. In fact WT is determined only by a set of h -coefficients h 0 , h1 , …,. hL 1 , since the second set of coefficients is usually assigned according to the rule g 0  h L 1 , g 1  h L  2 , …, g L 1  h 0 . For this reason we will designate wavelet transform as WDT2n  h 0 , h1 , , h L 1  . Coefficients h 0 , h1 ,…, hL 1 depend upon each other, because changing any coefficient from them requires changing the rest ones, if we wish are stayed in the orthogonal class of wavelet transforms. The coefficients, which we can change independently of one another, staying wavelet transform in the class of orthogonal transforms, will be called parameters in this paper. We will prove that multiparametric presentation of wavelet transform exists and that any orthogonal wavelet transform depends on D angle-parameters  0 , 1 , …,  D 1 : WDT2n  h 0 , h1, , h L 1   WDT2n  0 ,  1, ,  D 1  , (1) where L  2 D . Let m  log 2 2 D be the smallest positive integer such that m1 n m1  2 D  2 . Let WDT2n h0, h1,..., h L1    AWT nr 1 [h0, h1,..., h L1 ]  I n nr 1  m 2   r 1  2 2 2  be arbitrary cyclic wavelet transform, written in stairs-like form. 2 Third canonical form of MPWT 2.1 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   : i j 1 0 0 0     i 0 c s 0 (2) CSi, j ( )   .   j 0  s c 0     0 1   0 0 The wavelet transform WDT2n is factorized into a product of sparse matrixes, named stairs-like atomic wavelet transform AWT2n  h 0 , h1 , , h L 1  . We will multiply the wavelet transform matrix AWT2n  h 0 , h1 , , h L 1  by CSi , j ( ) matrix sequentially with such choice of angles  that product CSi , j (k )   CSi , j (0 )  AWT2n h0 , h1 , , hL1  will be permutation matrix or unit ma- k k 0 0 trix. 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     h2 h3 h4 h5 h0 h1  (3) AWT8  h 0 , h1 , h 2 , h 3 , h 4 , h 5    . h h 4 h3 h 2 h1 h 0  5   h5 h 4 h3 h 2 h1 h 0  h h 0 h5 h 4 h3 h 2   1  h3 h 2 h1 h 0 h5 h 4   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 CS 0,4 ( 0 ) . In this case coefficient h4 will be zero in the same rows too. That is, coefficients are zeroed by couples.  h0 h1 h2 h3 0 0     h0 h1 h2 h3 h4 h5   h4 h5 h0 h1 h2 h3     h2 h3 h4 h5 h0 h1  (4) CS 0,4 ( 0 )  AWT8  h 0 , h1 , h 2 , h 3 , h 4 , h 5      , 0 0 h3  h2 h1 h0    h5 h 4 h3 h 2 h1 h 0  h h 0 h5 h 4 h3  h 2   1  h3 h 2 h1 h 0 h5 h 4   if the angle is chosen such that c0 h5  s0 h0  0 , where c0  cos  0  and s0  sin  0  . CS3,7 (0 )  CS 2,6 (0 )  CS1,5 (0 )  CS 0,4 (0 )  AWT8  h 0 , h1 , h 2 , h 3 , h 4 , h 5    h0 h1 h2 h3     h0 h1 h2 h3   h0 h1 h2 h3    (5)  h2 h3 h0 h1   h3 h2 h1 h0   AWT8  h0 , h1 , h2 , h3  .    h3 h2 h1 h0   h h0 h3 h2   1  h3 h2 h1 h0    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: CS 0,7 (1 )  CS 3,6 (1 )  CS 2,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 )  CS 0,6 (2 )  CS3,5 (2 )  CS 2,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 )  CS 0,6 ( 2 )  CS 3,5 ( 2 )  CS 2,4 ( 2 )    CS 0,7 (1 )  CS 3,6 (1 )  CS 2,5 (1 )  CS1,4 (1 )    CS3,7 (0 )  CS 2,6 (0 )  CS1,5 (0 )  CS 0,4 (0 )   AWT8  h 0 , h1 , h 2 , h3 , h 4 , h5   P8 . (8) From here we obtain the multiparametric representation of the atomic wavelet trans- form matrix: AWT8  h 0 , h1 , h 2 , h 3 , h 4 , h 5   CS3,7 (0 )  CS 2,6 (0 )  CS1,5 (0 )  CS0,4 (0 )    CS0,7 (1 )  CS3,6 (1 )  CS 2,5 (1 )  CS1,4 (1 )   (9)  CS1,7 (2 )  CS0,6 (2 )  CS3,5 (2 )  CS 2,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  CS 2,6 0  CS1,50  CS0,4 0  , T810   CS 0,7 0  CS3,6 0  CS 2,50  CS1,4 0  , (10) T 0   CS1,7 0  CS 0,6 0  CS3,50  CS 2,4 0  . 8 2 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 T2i n   i  , the rule of index’s couples generating could be defined as fol-  lows: k  nr i, k  2 n  r . 2  0, 4 1, 4 2, 4 1, 5 2, 5 3, 5 2, 6 3, 6 0, 6 (11) 3, 7 0, 7 1, 7 k   k  4   k 4 1  k  4   k 4 2   k  4 We will get the same results if 16  16 -matrix AWT16  h 0 , h1 , h 2 , h 3 , h 4 , h 5  is cho- sen as the source atomic transform matrix with the identical set of coefficients. In order to zero the coefficients let us apply foregoing procedure to this matrix (compare the result with (9)): T162  2 T161  1 T160  0  AWT16  h 0 , h1, h 2, h3, h 4, h5   P16 , (12) AWT16  h 0, h1, h 2, h3, h 4, h5  T160   0 T161   1 T162   2 P16 , where T –matrixes are the products of multiplying of CS -matrixes. This result is general and valid for any  2 r  2 r  atomic matrix:  D 1  P2r    T2ir  i    AWT  h 0, h1, , h 2 D 1  ,  i 0   0  AWT  h0, h1, , h 2 D 1     T2ir   i   P2r . (13)  i  D 1  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  h 0 , h1, h 2 , h 3    AWT4 I12  AWT8 I8  AWT16 . (14) Every atomic matrix AWT4 , AWT8 , AWT16 can be represented in multiparametric form: AWT4  T40  0  T41   1  P4 , AWT8  T80   0  T81   1  P8 , (15) AWT16  T160   0  T161   1  P16 . Therefore, WDT16 h0, h1, h2, h3   T40  0  T41  1  P4  I12   T80  0  T81  1  P8  I8    0    T160   0  T161   1  P16     T4i (i )  P4  I12    i 1    0    0      T8i (i )  P8  I8     T16i (i )  P16  . (16)  i 1    i 1   It is two-parametric form of Daubechies-4 wavelet transform. It is possible to obtain all the transforms of WDT16  h 0 , h1, h 2 , h 3  -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 val- ues in each atomic matrix and have to be chosen synchronously. Of course, it is possi- ble 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: n  m 1  0   WDT2n [h0 , h1,..., h2 D 1 ]     Ti n  r 1 (i )  P n  r 1 I n n  r 1 , (17) 2 2 r 1  i  D 1  2 2  where  is addition modulo 2nr . The last expression presents any wavelet trans- 2n  r form in multiparametric form. We will call it the third canonical form. The classical wavelet transform with coefficients h0 , h1 ,..., h2 D 1 is constructed from atomic wavelet transforms according to the following rule: n  m 1 WDT n [h0, h1,..., h2 D 1 ]   AWT n  r 1 [h0, h1,..., h2 D 1 ]I n n  r 1 . (18) 2 r 1  2 2 2  The atomic transform is used only once within each iteration in (18). In fact, the atom- ic transform could be repeated not more then 2n / 2nr 1  2r 1 times. Let s r  ( s1r , s2r ,..., str ,..., s r r 1 ) be a binary 2r 1 -digital integer. Every binary digit str con- 2 trols the t th position of the matrix AWT n  r 1 in the r th iteration sparse matrix. 2 AWT2nr 1 , str  1, AWT stnr 1   r (19) 2  I 2nr 1 , str  0. All such matrices form a packet of atomic matrices 2 r 1 sr AWP2sn   AWT sntr1  AWT n1r1  AWT n2r1  ...  AWT n2rr11 r r sr sr (20) t 1 2 2 2 2 . r Using atomic packets AWT stnr1 , we obtain discrete controlled wavelet packet 2 n  m 1 nm1 [h0 , h1,..., h2 D 1 ]   AWP2sn  1 2 r WDP sn ,s ,...,s 2 r 1 (21)  2r 1 n  m 1  n  m 1     AWT sntr 1    AWT n1r 1  AWT n2r 1  ...  AWT n2rr11  r sr sr sr r 1  t 1 2  r 1  2 2 2   with discrete binary parameters s1   s11  , s 2   s12 , s22  , s3   s13 , s23 , s33 , s43  , ...,  sn m  s2n m , s2n m ,..., snnmm1 . 2  sr  0 str  t sr But AWT2nr 1    Ti n  r 1 ( i )  P nt  r 1 . Substituting this expression in (21),  i  D 1 2  2 we obtain the third multiparametric representation of wavelet packets  2r1 0  s r  t str n  m 1  nm1  0 1 2 D1   t 1   2nr 1 i  2nr 1  . (22) 1 2 WDP sn ,s ,...,s h , h ,..., h   Ti (  φ ) P r 1     i  D 1  2  Multiparametric wavelet packets represent a generalization of multiresolution decom- position 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. 2.3 The inverse multiparametric wavelet transform The direct multiparametric wavelet transform (MPWT) is defined by expression: n  m 1  D 1   WDT2n [h0 , h1,..., h2 D 1 ]     T Dn ri 11(  D i 1 )  P n  r 1 I n n  r 1 . (23) 2 2 r 1  i  0   2 2 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: n  log 2 L 1 WDT2n  r 1 AWT nr 1 I n nr 1 .  2 2 2  (24) Then  n log2 L 1 t  n WDT   AWT2nr 1 I 2n  2nr 1     AWT2tr I 2n  2r  . t (25)  r 1 2n  r log L   2  D 1  But AWT r   TDr i 1 (D i 1 )  P r , therefore 2  i 0 2  2 D 1 AWT tr Ptr  Tir (i ), (26) 2 2 2 i 0 since  T( )   T( ) . Substituting (26) into (24), we get t n  D 1  WDT n1WDT tn    Ptr  Tir (i )I 2n  2r . (27) r q   2 2 2 2 i 0 Every matrix T2i n  r 1 ( i ) is the product of commutative rotation CS -matrixes in the case of direct wavelet transform: 2n  r 1 T Dnir11 (  D  i 1 )   CS (  D  i 1 ), 2 k  i , k  2n  r k 0 2n  r (28) 2r 1 1 T (i )   CS i (i ). 2r k  ( D  i 1), k  2r 1 k 0 2r 1 Substituting (28) into (27), we get the final expression for inverse wavelet transform: WDT n1  h0 , h1,..., h2 D 1   WDT n1 0 , 1,...,  D 1   2 2  D 1 2r 1 1 n  (29)   P t r   CS r 1 (i ) , r q   2 k  ( D  i 1), k  2  i 0 k 0 2r 1 where  is addition modulo 2r1 . 2r 1 In much the same manner we get the expression of inverse wavelet packets:  2r  r 1   n D 1 2 1 WDP n [0, 1,..., D 1 ]   1   P r   CS t ( ) . (30) t 1  2  r  log2 L  2 k   D  i 1, k  2r 1 i    i 0 k 0 r 1 2 3 Fourth Canonical Form of MPWT 3.1 The direct multiparametric wavelet transform 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 h1 h2 h3 h4 h5     g0 g1 g2 g3 g4 g5   h0 h1 h2 h3 h4 h5     g0 g1 g2 g3 g4 g5  CAT8  h0 , h1 , , h5     P8AWT8  h0 , h1 , , h5  , (31) h h5 h0 h1 h2 h3   4   g4 g5 g0 g1 g2 g3  h h3 h4 h5 h0 h1   2  g2 g3 g4 g5 g0 g1   where P2n is the permutation matrix of ideal 2-adic mixing, which swaps the rows of atomic matrix in stairs-like form AWT2n  h0 , h1 , , h5  according to the rule 0 1 2 3 4 2r  2 2r  1  . (32)  0 2r 1 1 2r 1  1 2 2 r 1  1 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 CS iR, j ( ) and its definition is: i j 1 0 0 0     i 0 c s 0 (33) CS i , j ( )   . R   j 0 s c 0     0 1   0 0 We will multiply matrix CAT2n  h0 , h1 , , h2 D 1  sequentially with rotation-reflection matrixes CS R 01 0  , CS 0  , R 23 0  choosing angles  in such way , CS R 2 D  2,2 D 1 as to product will be the matrix CAT2  h0 , h1, , h2D 3  with the new set of coeffi- n 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). R CS 67 0 CS 45R 0 CS 23R 0 CS01R 0 CAT8 h0,..., h5    g 0 g1 g 2 g 3     h0 h1 h2 h3   g 0 g1 g 2 g 3    (34)  h0 h1 h2 h3    CAT8 h0 , h1, h2 , h3 . g 0 g1 g 2 g 3     h2 h3 h0 h1   g g 3 g 0 g1   2  h0 h1 h2 h3    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: R CS70 1  CS56R 1  CS34R 1  CS12R 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: R CS 012  CS67R 2  CS 45R 2  CS 23R 2   CAT8 h0, h1   1     1   1     1  (36)    C8 , 2 1    1  1     1    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 , (37) where T2in i  is product of rotation-reflection matrixes CS kR,l i  : T822   CS01 R 2  CS67R 2  CS45R 2  CS23R 2  , T81 1   CS70 R 1  CS56R 1  CS34R 1  CS12R 1  , (38) T800   CS67 R 0  CS45R 0  CS23R 0  CS01R 0  . Since matrixes T2in i  are both symmetric and orthogonal, then 1 T2in i   T2in i  . Therefore 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  I 8 AWT16 h0,..., h5  , then WT16 0 , 1, 2   1P8T80 0  T811  T82 2  C82 I8  (41)   1P16T160 0  T161 1  T162 2  C16 2 .  This result is general and valid for any  2 n  2 n  atomic matrix:  D 1  AWT2n  h0, h1,..., h2 D 1   AWT2n 0, 1,..., D 1    1 P2n   T2in i   C2Dn1  D  i 0    n1 D 1 2 1   1 P2n    CSiR 2 k ,i   2 k 1 i    C2Dn1 . D (42)  i 0 k 0 2 n 2 n  Taking into account (18), we get the following multiparametric presentation of cyclic orthogonal wavelet transform, which we call the fourth canonical form: n  log 2 L 1   D 1    WDT n [0 , 1,...,  D 1 ]   1    P  T2inr 1 i  C2Dnr11  I n n  r 1 . D 2nr 1 (43) 2 r 1   i 0   2 2  Similarly, we get the expression for MPWP, substituting (42) into (24): n  log 2 L 1  2r        1 D P nr 1  Tinr 1 i  CDnr11  . D 1 WDP n [0 , 1 ,...,  D 1 ]    2 (44) 2 r 1  t 1  2  i 0 2     3.2 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 mul- tiparamteric atomic wavelet transform, we should transpose the left and the right sides of the equation (42): t   D 1   AWT 1 2n 0,1, ,  D 1   AWT 0, 1, t 2n ,  D 1    1 P2n    T2in i    C2Dn1   D   i 0   (45) t t   t  t  D 1 D 1   1  C2Dn1    T2in i   P2tn   1  C2Dn1     T2Dn i 1 D i 1  P2tn . D D  i 0   i 0  Since T2Dn i 1  D i 1  is the product of symmetric and orthogonal rotation-reflection matrixes CS kR,l D i 1  , then equation T2Dni 1D i 1  T2Dni 1D i 1  is valid. Hence t t   D 1 AWT2tn 0 ,1 , , D 1    1  C2Dn1    T2Dn i 1 D i 1  P2t n . D (46)  i 0  Substituting (45) into (26) we get the expression for inverse MPWT: n  t  D 1   WDT n1[0 , 1 ,...,  D 1 ]   1    C2Dr1    T2Dr  i 1 D i 1  P2tr  I 2n  2r . (47) D 2 r  log 2 L   i 0   In much the same manner we get the expression for inverse wavelet packets:  2r    D 1 t  D 1 D i 1   n WDP n [0 , 1 ,..., D 1 ]   1    1 C2r   T2r D i 1 P2tr . D   t 1  (48)  i 0   2 r  log2 L   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 coef- ficients 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 inte- ger values, as the cost function. The form of the dependency E 2 0 , 1  (case of two- parametric transform) is shown on figure 1. Fig. 1. Entropy of spectra E 2 relative to parameters  0 and 1 for WDT28 0 , 1  . Test image is “Lena”. Figure 1 show that researched dependency has local and global minimums that cor- respond the best from the point of view of compression the wavelet transforms. 5 Conclusion 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. 6 Acknowledgments 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). 7 References 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.