.....last class we.......discussed on the
discrete wavelet transforms 
and also I will try to cover in this lecture
that how to use the discrete wavelet transform
in multi-resolution analysis.
Now before we begin this topic let us have
a look at what we did for the continuous wavelet
functions and the continuous scaling functions.
In fact this kind of a series that we had
realized we are calling that as the wavelet
series.
So essentially we are using this set of scaling
functions and the set of wavelet functions
in order to approximate a continuous valued
function f of x.
And what we did here is just how to compute
the coefficients a r 0, s and b r, s where
r happens to be greater than or equal to r
0 where the integral expressions are coming
in. Now the integral expressions are okay
as long as x is a continuous variable because
it is integrated with respect to x. But when
x is not a continuous variable, when we are
considering the signal itself to be discrete
in that case the functional form of this has
to change. So what we will be doing now is
that the definition of the signal now becomes
that we write the signal as s of n where n
is going be the samples of the signals and
we are going to have n as 0, 1 up to M minus
1 so where we are considering that there are
M number of samples in the signal, this is
s of n. Then what we are going to do is to.........
In fact although the image is a two dimensional
signal for the time being just for the sake
of simplicity I am considering one dimensional
signal because whatever theory we can develop
for one dimension would later on be easily
applicable to two dimensions. In fact it is
more so in the case of wavelets because wavelet
can be realized wavelet 2 D wavelet filters
can be realized as separable 1 D wavelet filters
so essentially it means to say that as if
to say cascading of two 1 D filters that is
what we can do. So the signal is s (n) and
the signal is discrete time signal where n
is the parameter of the time and it is defined
at some discrete points like 0, 1 up to M
minus 1.
Now whenever we are trying to compute this
a r 0, s and b r, s and we do not have the
f(x) anymore and instead of f(x) we are having
s of n in that case it will not be possible
for us to integrate. So the integration will
get replaced by a summation series and the
manner in which we can write is like this
that equivalently this a r 0, s...........
what was a? a is the coefficients that is
associated with the set of scaling functions
with the shifted versions of the scaling function.
so now instead of writing this as a, the scaling
function coefficients if we write as W and
as suffix I use phi, phi means that it is
it is associated with the scaling function
and let us say some scaling parameter I take
as j 0 just like the way we took r 0, in the
equivalent discrete version form I take it
as j 0 so W phi j 0, and the shifts that is
s I am writing that as k. just be comfortable
with the change of notation that I am applying
in this lecture So j 0 is what our r 0 was
and k is what our s was and W is what our
(a) was. So everything was in the continuous
domain and s of n is what our f of x was.
So in the discrete form I can write W phi
(j 0, k) as 1 upon root over M into a summation
series over n s of n into phi j 0, k of n.
Now naturally the phi of x we cannot write
anymore, we have to compute the value of the
wavelet function at also those specific points
n; n is equal to 0, 1, 2,............ etc
so we have to compute the scaling function
values and the wavelet function values at
those specific discrete points. This is the
equivalent form. So whatever I wrote for a
r 0, s as an integral expression now I am
writing the same thing W phi (j 0, k) as a
summation expression and this 1 by root over
M is actually a normalizing term that is coming
in because what we are essentially doing is
you can imagine that as if to say that from
this s of n which is the special domain I
am converting that to a new domain that is
given by this W phi j, k. So again when I
am transforming the signal to a new domain
like this I should be able to recover the
signal given some parameters of this domain
or when these when the signals are equivalently
transformed in this form then I should be
able to get back. But of course I have not
completed it because I have only written the
scaling function term so similarly I have
to write down the wavelet function term also.
So to write the wavelet function term I write
it as W psi. it is what I am going to write
as b r, s in the discrete form; b r, s I am
writing as W psi and the parameters I will
say as j, k now, where j is going to be greater
than or equal to j 0 just like the way I had
the condition that r is greater than or equal
to r 0 that is to say these scaling functions
are 0, in this case I have to make j greater
than or equal to j 0 and I can write W psi
j, k as 1 by root over M into summation over
n s (n) psi j, k (n). So I have got two equations
let us call this as equation 1 and this as
equation 2.
Any questions? Yes please..........
Why is this 1 by root over M? I will come
to this very shortly. See, 1 by root over
M is a normalizing term that is there because
I have transformed s (n) to this space and
I can get back s (n) from this space. Now
when I want to apply this transformation and
I want to get back the original signal from
reverse transformation this process of transformation
and reverse transformation that should not
introduce any scaling coefficient. The energy
of the signal in the s (n) domain and the
energy of signal in this W domain they have
to remain the same. So, to maintain that either
in the forward transformation we have to apply
a coefficient of 1 by M or in the inverse
transformation we apply a coefficient of unity
or otherwise an alternative form of doing
it is that have in the direct transformation
have a coefficient of 1 by root M, in the
inverse transformation also have a coefficient
of 1 by root M. The same thing is also applicable
to the Fourier transforms. Fourier transforms
also people are doing like this.
Even in continuous Fourier transform also,
if you remember, that some books will show
it as 1 by root over 2pi in the forward Fourier
transform and in the inverse Fourier transform
they will also show another 1 by root over
2pi. Some books mention 1 by 2pi in the forward
and unity in the inverse. It is a very similar
logic; this sort of normalization will be
there. In our case n is nothing but the number
of samples. So, this is conversion from the
s (n) domain to a new transform domain and
this new transform domain is also in the discrete
space.
Now what we should do is to get back this
s (n) given this W phi and W psi's and how
do we get back?
So again the functional form should be very
similar to this because in this case we could
obtain f of x from the coefficients a r 0,
s and b r, s. Now what is a r 0, s that is
our W phi and b r, s is nothing but our W
psi's. So given the W phi's and the W
psi's we should be able to get not f(x)
anymore but s of n in this case. So what we
obtain is this: s of n can be expressed as
1 by root over M summation over k W phi j
0, k into phi of j 0, k (n).
No major difference; f(x) is replaced by s
(n), this s now we are calling it as k; a
r 0, s; now we are calling it as W phi j 0,
k and phi r 0, x we are now calling as phi
j 0, k (n). So this is the scaling function
quantity and the wavelet function quantity
will be just like the way we had here a double
summation; in this case also we will continue
to have a double summation so it will be summation
j is equal to j 0 to infinity summation over
k the shift parameter W psi (j, k) psi j,
k of n. This is how we get back s of n from
W phi's and W psi's.
This one is our forward transformation or
we can say this as forward wavelet transformation.
we will not call it as wavelet transformation
we will specifically call it as forward discrete
wavelet transformation because the signal
itself is discrete so we are using the wavelet
functions and the scaling functions also in
its discrete time form so this is forward
discrete wavelet transform; the short form
of discrete wavelet transform is DWT so we
call this as the forward DWT.
And this will be the expression for the corresponding
inverse DWT.
So in this case........... okay, since you
are familiar with different types of transformation
now you can see that every transformation
has got two things: the original signal, the
transformed signal and also it has got a transformation
kernel. Now in this case what is the transformation
kernel? The transformation kernel is this
phi j 0, k and this psi j, k's these are
the transformation kernel and this is just
the inverse transformation kernel so in this
case the functional form of the inverse transformation
kernels are also the same so using this it
is possible for us to realize this s of n.
Now what we normally do is to choose j 0;
j 0 is chosen to be 0; normally we can choose
j 0 to be equal to 0 and select M as some
power of 2. So say if I have this as M as
M expressed as 2 to the power capital J where
capital J is an integer in that case the summations
are performed over this, j these summations
are performed over j is equal to 0, 1 up to
capital J minus 1 meaning that if I let us
say start with 64 samples so say n is equal
to 0, 1 up to 63 that means to say then M
is equal to 64, when I have M is equal to
64, 64 is nothing but 2 to the power 6 so
my J becomes equal to 6 and in that case in
the summation quantity summation term associated
with the wavelet function wavelet coefficient
that would be having six terms because there
can be six different wavelet six six k's
of wavelet function that is what we can choose
and that is why the summation will be in that
case from j is equal to 0 to j is equal to
5e because capital J being equal to 6 it is
0 to 5 yes, that is what it becomes.
Although in the general expression the summation
goes up to infinity but in the practical cases
this is not going up to infinity this will
be only up to the extent that you require.
Now, given this functional form we want to
just see what is the easy and convenient way
of computing a discrete wavelet transform.
You see that alright.............. you can
say that we should be able to get different
shifted versions of this and finally obtain
this W phi of j, k but is there any easy way;
is there any nice recursive way of computing
the discrete wavelet transforms so let us
have a look at that aspect.
Now just in order to do that let us again
go back to some of the continuous wavelet
transform expressions that we had derived
in the last lesson. Let us see this expression
Have a look at this expression: psi r, s;
we had said psi r, s of x was equal to 2 to
the power r by 2 psi of this 2 to the power
r, x minus s. Now in this case the nomenclatures
have changed; we are calling this s as k and
this x as n the discrete variable we are calling
it as n; this is as k and r we are calling
as j so this same expression it is possible
for us to write down this. In fact what we
do is that this psi r of s instead of psi
r, s if I now start writing psi j, k of n
in that case this equation 2 what I have written
as equation 2 W psi j, k is equal to this
the equation 2 can be rewritten by substituting
this psi j, k expression as we would obtain
from this. So let us first write down the
discrete form psi j, k so psi j, k first we
write down and then we will put that into
equation number 2.
So psi j, k I can write psi j, k n as 2 to
the power j by 2 into psi. Here I have to
write 2 the power j n minus k. now if I call
this as equation number 3 I will be applying
equation number 3 into equation number 2 means
this I will be substituting psi of j, k term.
So putting psi j, k in equation 2 what we
obtain; we will obtain this W psi j, k expression
so we can write W psi j, k as 1 by root over
M summation n s(n) 2 to the power j by 2 psi
(2 to power j n minus k).
Now, again just see, we have got another very
interesting relationship and what was that
where we had expressed the psi function as
a series summation of phi function. We had
an expression like this and this in the new
form in the in the in a in a in the new notation
we would like to write it like this: psi of
n I should be writing as the summation over...........
I cannot call this as n anymore because n
I am reserving for the sample number so n
is replacing this x so please do not get confused
with the earlier notation and this notation
I do not call it as n anymore but the shift
parameter I call that as r; so summation over
r h psi of r again do not confuse earlier
I was using r for the scaling term, now the
scaling term is j; shift parameter is k but
k I am writing in this case I am writing k
as r; if you are confused popular defend is
to have it as p okay let me write it as p.
So h psi of p and then I have to write it
as root 2 phi what am I going to write? 2
n minus you have introduced p so I write as
2 n minus p so this is psi of n that I now
have.
Now in this equation if I multiply this n
by a factor 2 to the power j that means to
say that if I scale it up by a factor 2 to
the power j and I give it a shift of k units;
because k already I am using as a shift parameter
that is why I wanted to give a different shift
parameter over here so that you do not get
confused with the 2 k's. Fine, you have
already told that it should be p. So now what
I want to do is that I want to get psi (2
to the power j n minus k). So if I want to
do that what I have to simply do is to replace
this n by 2 to the power j n minus k and put
it in this equation.
So what do we obtain? So if I say that this
is 4 then equation 4 can be rewritten as;
equation 4 may be rewritten as: let me write
down: psi (2 to the power j n minus k)) that
will be equal to summation over P h psi of
P root 2 phi 2 into this is not n anymore
n is replaced by (2 to the power j n minus
k)) so 2 into 2 to the power j n minus k and
this whole thing minus this was in our expression
this was 2 n minus P so this this will be,
n is this and P remains as before.
Now this can be represented as....... we can
now have a change of variable let's say
that h psi if I have a have a change of variable...........
just this P if it is changed to (m minus 2k)
so I introduce a new variable m so that (m
minus 2k) becomes equal to P so I sum up now
over m and with this new substitution what
results is root 2 phi and in this case it
is (2 to the power j plus 1 n (2 to the power
j plus 1 into n and here what I have is minus
2k minus P and according to our substitution
P is equal to m minus 2k so that 2k plus P
is equal to m. So in this case I am just going
to write (2 to the power j plus 1 n minus
m).
So now what I want to do is that I want to
substitute this h of......... okay, this psi
of (2 to the power j n minus k) is what we
actually required in this equation W psi j,
k just in this equation, yeah......
So let's call this as............ oh I did
not put any number let's call it as (3a).
Now in this equation (3a) what I want to do
is that whatever value of psi (2 to the power
j n minus k) I have got over here this value
I will substitute in equation number (3a)
in order to express this W psi j k in terms
of this phi's.
So what I am doing is that the wavelet coefficients
I am expressing in terms of the different
versions of the scaling functions. So let
us see that what results whether any interesting
thing results when I substitute psi (2 to
the power j n minus k) is equal to this into
equation (3a) so what we get is this: W psi
j, k should be obtained as 1 by root over
M summation n into s(n) 2 to the power j by
2 and now this expression that is to say instead
of psi 2 to the power j m just the new form
that we wrote that is to say [summation over
m h psi (m minus 2k) into root over 2 phi
(2 to the power j plus 1 n minus m)].
Now, interchanging the order of the summation;
if I interchange the order of the summation
what we should obtain is W psi (j, k) will
be given by summation over m into h psi (m
minus 2k) and then I am going to write 1 by
root over M summation over n s(n) 2 to the
power (j plus 1) by 2 because here it is 2
to the power j by 2; here there is a 2 to
the power half so it makes 2 to the power
(j plus 1) by 2 so 2 to the power (j plus
1) by 2 into phi of (2 to the power j plus
1 into n minus m) the quantity which we wrote
over here.
Now can you make out anything interesting
out of this; the term that I have written
within the square bracket?
W phi j plus 1m; this is very interesting,
yes. because if you just have a look at W
phi j 0, k W phi j 0, k makes the form of
s (n) phi j 0 k this expression........ no,
W yes W phi is like this and in this case
it becomes instead of j 0 it becomes j plus
1 so what results is W psi (j, k) becomes
equal to summation over m h psi (m minus 2k)
into W phi (j plus 1, k) this is a very interesting
relationship.
M? yeah, that is true because in the index
we are using as m; yeah. so this is one very
interesting relation that we have obtained
for W psi (j, k) and in a very similar way
we can obtain the expression for W phi (j,
k) also and W phi (j, k) W phi (j, k) in a
very similar way can be obtained as summation
over m h in this case phi of (m minus 2k)
into W phi (j plus 1, m) this is also a very
interesting expression.
which means to say what In fact you should
not be bothering about this m and the k; why
I am telling this is here k is a shift parameter
that we are considering in this case so essentially
whenever you are considering the summation
series from minus infinity to plus infinity
from m this is also what you will be obtaining
for the summation series over k because the
transformation is that m is equal to 2k plus
P.
Okay, I think things will become clear when
we talk about the further interpretation of
this equation. After all what is this; what
is the interpretation of this equation?
That means to say that if W phi (j plus 1,
m) is available with you, what you are essential
doing is you are convolving that with h psi.
It is a convolution with h psi function that
is what you are considering and in this case
it is convolution with h phi function. So
if you have two filters one with impulse response
h phi of m and the other with h psi of m,
at the input of the filter what you are giving
is that you are you are giving this quantity
and you are getting this quantity out of it
because it is a convolved from.
Therefore, in the block diagram form what
you can do is like this that W phi (j plus
1, n) if you take this as (j plus 1, n) then
as if to say that you can pass it through
two filters. You can call them as the analysis
filter, this one is given by h phi of minus
n because if you are using this as n then
this becomes (minus n) h phi of minus n and
this as h psi of minus n. So this one will
be the scaling analysis filter and this one
will be the wavelet analysis filter. In that
case from this you should be able to obtain
this W psi (j, n) and W phi (j, n)
there is a two factor........ I think, the
point what we have to solve is just some substitution
of variables that is what we might be missing
or I will.....Decimation by 2 is anyway needed,
yes; decimation part I have not yet included;
decimation part I mean since I have not explained
this I have not come to the decimation part;
yes, decimation part takes care of that two
term. And what we have to do is yes, so this
is two filters so this W phi (j plus 1, n)
if you are having as an input then you can
get W psi (j, n) and W phi (j, n) out of this
but essentially and as mathematically also
evolves that there is a decimation by 2 and
I did not talk about this decimation because
I want you to interpret the decimation in
a little different way and I am coming to
that point soon.
But if it is decimated by a factor of 2 decimated
by a factor of 2 means that you just take
the alternate samples and you drop the alternate
samples because what happens is that if you
are starting with m number of samples for
n is equal to 0 to m minus 1 so you are starting
with m number of samples in that case after
the low pass filtering also you get n number
of samples, after the high pass filtering
also you get m number of samples so your number
of samples are that way increasing.
In fact, on the other hand, your bandwidth
that gets halved because if you are realizing
the filter as something like this; see, h
phi of minus n is a low pass filter; h psi
of minus n is a high pass filter. So if I
have the filter responses like this, now I
cannot have an ideal filter that is not practically
realizable so if my LPF the low pass filter
is like this and if I am able to construct
the high pass filter in a manner that this
becomes my high pass filter and in that case
the overall filter characteristic should be.........
if this is equal to 1 then it should be able
to pass all the frequencies; I mean, together
the overall response should be this. So this
is what I want to achieve and here since the
bandwidth has become halved so if this is
my total so if this is my maximum frequency
then individually this band has got half of
the maximum frequency, this band has got another
half of this so the bandwidth is halved and
that is why we can reduce the sampling rate
also by half in the individual channels. So
that is what we achieve by the decimation
process.
Therefore, from W phi (j plus 1) it is possible
for us to get W psi (j, n) and W phi (j, n)
which means to say that I can do this further.
Using this W phi (j, n) it should be possible
for me to analyze it further and get W phi
(j minus 1, n) and W psi (j minus 1, n). So,
if I start with the highest scale the highest
scale means that where............. now what
is the maximum value of small j? The maximum
value of small j is equal to capital J minus
1. So, if I start with W phi capital J, n
which is nothing but our original image; if
you start with W phi or original signal; if
I start with W phi (j, n) which is our original
signal we can put it into this two kinds of
filter banks and we can obtain a low pass
filter version, we can obtain a high pass
filter. By the way I have written totally
wrong this should be W phi this should be
W phi, this should be W psi so this is the
low pass filter version and this is the high
pass filtered version and I can apply it iteratively.
So in that case what we need to do is to analyze
this low pass further.
Therefore, what it means to say is that, given
the original signal given the original signal
let us say that original signal is s of n
we are passing this s of n into two filters:
one is this h phi filter, the other is the
h psi filter and then we are decimating by
2 here, decimating by 2 here, this is our
low pass filtered version and this I am again
further analyzing h phi minus n, h psi minus
n again decimating by 2, decimating by 2 like
this.
So it is possible for us to obtain such bank
of analysis filters. And in terms of the frequency
response, the frequency response plots would
be like this that if this is the low pass
filter, this is the next band, this is the
next band so the low pass filter and a bank
of band pass filters that can be realized
using a system like this.
Yes please; Yes, yes, banks will not be having
the same bandwidth. In fact what happens is
the low pass filter bandwidth............
because you see that the ultimate low pass
filter is this which will have the one fourth
of the original bandwidth. In this case it
will be one fourth of the original bandwidth
this will be having one fourth of the original
bandwidth, this will be having half of the
original bandwidth. So the picture should
actually de drawn like this that if I want
to draw only these three in that case I should
draw it like this that this should be the
low pass filter, this should be the next band
pass filter which is this one and then this
should be two times; I mean this should be
equal to this which means to say that this
band should be this one. That means to say
that wavelet essentially permits us to realize
a bank of analysis filters which means to
say that we can obtain the original signal
back if we apply a corresponding bank of synthesis
filters.
Just if you analyze the signal, from s of
n you analyze it into three bands like this
how to get back the s of n?
You can obtain s of n back, you can call that
as s cap of n because you are not too sure
that whether you will get back the signal
exactly or not but you can obtain this s cap
of n by a process of synthesis filters. So
the synthesis filter would be just the opposite
of this.
Now since you have down-sampled by 2 you have
to correspondingly up sample by a factor of
2 over here. So this is up-sampled by 2, this
is up-sampled by 2 and then you have to apply
a synthesis filter so call that as g phi of
minus n, this you call as g psi of minus n
and then these two responses you just add
up and then what you do is that you 
up-sample this by 2, apply again g phi of
minus n and add up with this.
am talking of if you If you say that this
is s 1 of n, this is s 2 of n and this is
s 3 of n so this one is s 1 of n, this one
is s 2 of n and this is s 3 of n. Now s 3
of n this we will pass through g psi of minus
n; add it up and this will realize s cap of
n. So we can realize s cap of n using this.
This is the synthesis filter bank and this
is the analysis filter bank.
Now in the case of images what we have to
do is that we have to apply the wavelet transforms
in both the directions because then our signal
will not be represented as s of n but rather
it will be represented as s of (n 1, n 2)
so we have two directions (n 1) direction
and (n 2) direction and let us say that we
choose our convention like this that (n 1)
is the horizontal direction and (n 2) is the
vertical direction.
By having it like this we can define four
different filters which would be like this:
phi (n 1, n 2).... so we define a filter called
phi (n 1, n 2) which is nothing but a product
of phi (n 1) into phi (n 2) and then we define
another filter psi (n 1, n 2) but call this
as psi with a superscript H, what the superscript
H means I will define it shortly that becomes
psi (n 1) into phi (n 2) which means to say
that along the (n 1) direction that is along
the horizontal direction it is high pass filtered
but along the low pass filter but along the
(n 2) direction it is low pass filtered; phi
is the scaling function which is essentially
a low pass filter and psi is a wavelet function
which is essentially a high pass filter. So
it is along (n 1) it is high pass filtered
so we write it as s psi H along horizontal
so horizontally it is high pass and then I
define another filter psi v (n 1, n 2) and
what does it and what it should be; it should
be phi (n 1) into psi (n 2) and I should have
a fourth filter also possible which will be
just the product of psi (n 1) and psi (n 2)
so psi (n 1, n 2) I can write as a product
of psi (n 1) psi (n 2). That means to say,
what is the physical significance of psi (n
1) and psi (n 2)'s product; that means to
say that it is high pass filtered in both
horizontal and vertical direction. That means
to say that, in diagonal direction also it
is having a high pass filtering so we call
this as psi diagonal. So there are four filters
that we can have for the case of two dimensional
signals. So, when our signal, instead of one
dimensional is two dimensional s (n 1, n 2)
then we can use four different filters.
And you see, whenever I am applying phi (n
1) phi (n 2)'s products or any such product,
with every filter I have do a decimation by
a factor of 2. That means to say that in overall
I am doing a decimation by a factor of 4;
decimation by a factor of 2 in horizontal
direction and decimation by another factor
of 2 in the vertical direction so totally
a decimation by a factor of 4.
So if I start with an image; if this is my
image then I can split this image. Now when
I apply the four different wavelet filters,
when I apply filter 1, filter 2, filter 3
and filter 4 these individual filter responses
I can represent in my image space like this
that I can split the image space into four
quadrants and in this top left quadrant I
represent the image which is low pass filtered
horizontally and low pass filtered vertically.
Hence, I call this as low pass filtered horizontally
low pass filtered vertically I call it as
LL. So LL will occupy only one fourth of the
image space because it is decimated by a factor
of 2 in both horizontal and vertical direction.
Here what happens?
Here it is horizontally high passed but vertically
it is low passed. So I call it as horizontally
high passed, vertically low passed.
What is this one?
This one is horizontally low passed but vertically
high passed LH and this one, the last filter
is horizontal high passed vertically also
high passed so LL HL LH HH, so four different
filtered versions I am obtaining. And as I
was showing you, that it should be possible
for us to apply some further sub-divisions
like I can take this LL band and I can analyze
the signal further; just like the way I was
showing you that the low pass filtered version
signal I can further analyze I can further
split, there is no limitation on the on how
many analysis filter banks I can use. We will
discuss more about this in the coming lecture,
thank you.
