Chapter 7

Wavelets and Multi-resolution

Processing
Background
 Image Pyramids
Total number of elements in a P+1 level pyramid for P>0 is
1 1 1 4 2
N (1   2  ...  P )  N
2

4 4 4 3
Example
 Subband Coding
An image is decomposed into a set of band-limited co
mponents, called subbands, which can be reassembled
to reconstruct the original image without error.
 Z-Transform
The Z-transform of sequence x(n) for n=0,1,2 i
s: 
n
X ( z)   x(n) z
n  

Down-sampling by a factor of 2:
x ( n )  x ( 2n )  X ( z )   X ( z )  X (  z )
1 1/ 2 1/ 2
down down
2
Up-sampling by a factor of 2:
 x ( n / 2), n  0,2,4...
x (n)  
up
 X up ( z )  X ( z 2 )
0 otherwise
 Z-Transform (cont’d)
If the sequence x(n) is down-sampled an
d then up-sampled to yield x^(n), then:
1
X ( z )   X ( z )  X (  z )
ˆ
From Figure 7.4(a),2 we have:

1 1
Xˆ ( z )  G0 ( z ) H 0 ( z ) X ( z )  H 0 (  z ) X (  z ) Xˆ ( z )   H 0 ( z )G0 ( z )  H1 ( z )G1 ( z ) X ( z )
2 2
1 1
 G1 ( z ) H1 ( z ) X ( z )  H1 (  z ) X (  z )   H 0 (  z )G0 ( z )  H1 (  z )G1 ( z ) X (  z )
2 2
 Error-Free Reconstruction
H 0 (  z )G0 ( z )  H1 (  z )G1 ( z )  0
H 0 ( z )G0 ( z )  H1 ( z )G1 ( z )  2

• Matrix expression
[G0 ( z ) G1 ( z )]H m ( z )  [2 0]

• Analysis modulation matrix Hm(z):

 H 0 ( z ) H 0 (  z )
Hm ( z )   
H
 1 ( z ) H 1 (  z ) 
G0 ( z ) 2  H1 (  z ) 

 G ( z )  det(H ( z ))  H (  z )
 1  m  0 
 FIR Filters
• For finite impulse response (FIR) filters, the d
eterminate of Hm is a pure delay, i.e.,
det( H m ( z ))  z  ( 2 k 1)
• Let =2 g0 (n )  ( 1) n h1 ( n )
g1 ( n )  ( 1) n 1 h0 ( n )
• Let =-2
g0 (n )  ( 1) n 1 h1 ( n )
g1 ( n )  ( 1) n h0 ( n )
 Bi-orthogonality
Let P(z) be defined as:
2
P ( z )  G0 ( z ) H 0 ( z )  H 0 ( z ) H1 (  z )
det( H m ( z ))
2
G1 ( z ) H1 ( z )  H 0 (  z ) H1 ( z )  P (  z )
det(H m ( z ))
Thus, G0 ( z ) H 0 ( z )  G0 (  z ) H 0 (  z )  2
Taking inverse z-transform:
 g (k )h (n  k )  (1)  g (k )h (n  k )  2 (n)
k
0 0
n

k
0 0

Or,  g (k )h (2n  k ) 
0 0 g0 (k ), h0 ( 2n  k )   (n )
k
 Bi-orthogonality (Cont’d)
It can be shown that:
g1 ( k ), h1 ( 2n  k )   ( n )

g0 (k ), h1 (2n  k )  0

g1 ( k ), h0 (2n  k )  0

Or, hi (2n  k ), g j (k )   (i  j ) (n ), i, j  {0,1}

Examples: Table 7.1
Table 7.1
2-D Case
Daubechies Orthonormal Filters
Example 7.2
 The Haar Transform
Oldest and simplest known orthonormal wav
elets.
T=HFH where
F: NXN image matrix,
H: NxN transformation matrix.
Haar basis functions hk(z) are defined over t
he continuous, closed interval [0,1] for k=0,
1,..N-1 where N=2n.
Haar Basis Functions
k  2 p  q  1 where 0  p  n  1,
q  0 or 1 for p  0,1  q  2 p for p  0

1
h0 ( z )  h00 ( z )  , z  [0,1]
N
 2 p / 2 ( q  1) / 2 p  z  ( q  0.5) / 2 p
1  p/2
hk ( z )  h pq ( z )   2 ( q  0.5) / 2 p  z  q / 2 p
N 
0 otherwise, z  [0,1]
Example
Multiresolution Expansions
Multiresolution analysis (MRA)
A scaling function is used to create a se
ries of approximations of a function or i
mage, each differing by a factor of 2.
Additional functions, called wavelets, ar
e used to encode the difference in infor
mation between adjacent approximation
s.
 Series Expansions
A signal f(x) can be expressed as a linear co
mbination of expansion functions:
f ( x)    ( x )
k
k k

Case 1: orthonormal basis:  j ( x ), k ( x )   jk

Case 2: orthogonal basis:  j ( x ),  k ( x )  0 j  k
k k
2 2 2
Case 3: frame: A f ( x )   ( x ), f ( x )  B f ( x )
 Scaling Functions
Consider the set of expansion functions co
mposed of integer translations and binary s
caling of the real, square-integrable functio
n, ,i.e., (x )
 j ,k ( x )  2 j / 2  ( 2 j x  k )

By choosing  wisely, {j,k(x)} can be made

to span L2(R)
Haar Scaling Function
 MRA Requirements
Requirement 1: The scaling function is orthog
onal to its integer translates.
Requirement 2:The subspaces spanned by th
e scaling function at low scales are nested wit
hin those spanned at higher resolutions.
Requirement 3:The only function that is com
mon to all Vj is f(x)=0
Requirement 4: Any function can be represen
ted with arbitrary precision.
Wavelet Functions
 Wavelet Functions
A wavelet function, (x), together with its i
nteger translates and binary scalings, spans
the difference between any two adjacent sc
aling subspace, Vj and Vj+1.

 j ,k ( x )  2  ( 2 x  k )
j/2 j

 ( x)   h (n )
n
 2 ( 2 x  n ) h ( n )  ( 1) n h (1  n )
Haar Wavelet Functions
Wavelet Series Expansion

f ( x)  c
k
j0 ( k ) j0 ,k ( x )   d (k )
j  j0 k
j j ,k ( x)

c j0 ( k )   f ( x ) j0 ,k ( x )dx

d j (k )   f ( x) j ,k ( x )dx
Harr Wavelet Series Expansion of y=x2
Discrete Wavelet Transform
1
W ( j0 , k ) 
M
 f ( x )
x
j0 ,k ( x)

1
W ( j, k ) 
M
 f ( x )
x
j ,k ( x)


1 1
f ( x) 
M
 W ( j , k )
k
 0 j0 ,k ( x) 
M
 W ( j, k )
j  j0 k
 j ,k ( x)
 The Continuous Wavelet Transform
 1 x 
W ( s, )   
f ( x ) s , ( x )dx  s , ( x ) 
s
(
s
)

  2
1  s , ( x )   (u )
f ( x) 
C  W ( s, )
s 2
dds C   u
du
0 
 Misc. Topics
The Fast Wavelet Transform
Wavelet Transform in Two Dimensions
Wavelet Packets