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
m1 n m1
2 D 2 . Let WDT2n h0, h1,..., h L1 AWT nr 1 [h0, h1,..., h L1 ] I n nr 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 , , hL1 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.
h0 h1 h2 h3 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 h3 h2 h1 h0
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
h0 h1 h2 h3
h0 h1 h2 h3
h0 h1 h2 h3
(5)
h2 h3 h0 h1
h3 h2 h1 h0 AWT8 h0 , h1 , h2 , h3 .
h3 h2 h1 h0
h h0 h3 h2
1
h3 h2 h1 h0
As a result we get a new atomic matrix AWT8 h0 , h1 , h2 , h3 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 h0 , h1 , h2 , h3 AWT8 h0 , h1 . (6)
Reiteration of this procedure on matrix AWT8 h0 , h1 results in:
CS1,7 (2 ) CS 0,6 (2 ) CS3,5 (2 ) CS 2,4 (2 ) AWT8 h0 , 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,50 CS0,4 0 ,
T810 CS 0,7 0 CS3,6 0 CS 2,50 CS1,4 0 , (10)
T 0 CS1,7 0 CS 0,6 0 CS3,50 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
nr
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 2nr . 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 / 2nr 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
AWT2nr 1 , str 1,
AWT stnr 1
r
(19)
2
I 2nr 1 , str 0.
All such matrices form a packet of atomic matrices
2 r 1
sr
AWP2sn AWT sntr1 AWT n1r1 AWT n2r1 ... AWT n2rr11
r r sr sr
(20)
t 1 2 2 2 2 .
r
Using atomic packets AWT stnr1 , we obtain discrete controlled wavelet packet
2
n m 1
nm1
[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 sntr 1 AWT n1r 1 AWT n2r 1 ... AWT n2rr11
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 ,..., snnmm1 .
2
sr
0
str t sr
But AWT2nr 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
2r1 0
s r
t str
n m 1
nm1
0 1 2 D1 t 1 2nr 1 i 2nr 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 nr 1 I n nr 1 .
2 2 2 (24)
Then
n log2 L 1
t
n
WDT AWT2nr 1 I 2n 2nr 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 n1WDT 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 Dnir11 ( 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 2r1 .
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, , h2D 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 CAT8h0 , h1, h2 , h3 CAT8h0, h1. (35)
If we will use appropriate rotation-reflection matrixes, we could transform this matrix
to permutation one:
R
CS 012 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,
T822 T811 T800 CAT8 h0 , h1 , , h5 C82 , (37)
where T2in i is product of rotation-reflection matrixes CS kR,l i :
T822 CS01
R
2 CS67R 2 CS45R 2 CS23R 2 ,
T81 1 CS70
R
1 CS56R 1 CS34R 1 CS12R 1 , (38)
T800 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 T800 T811 T822 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 T811 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 1P8T80 0 T811 T82 2 C82 I8
(41)
1P16T160 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 C2Dn1
D
i 0
n1
D 1 2 1
1 P2n CSiR 2 k ,i 2 k 1 i C2Dn1 .
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 T2inr 1 i C2Dnr11 I n n r 1 .
D
2nr 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 nr 1 Tinr 1 i CDnr11 .
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 C2Dn1
D
i 0 (45)
t
t t t
D 1 D 1
1 C2Dn1 T2in i P2tn 1 C2Dn1 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 T2Dni 1D i 1 T2Dni 1D i 1 is valid. Hence
t
t
D 1
AWT2tn 0 ,1 , , D 1 1 C2Dn1 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 C2Dr1 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.