Sign in

Not a member? | Forgot your Password?

Search compdsp

Search tips

Free PDF Downloads

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

C++ Tutorial

Introduction of C Programming for DSP Applications

Fixed-Point Arithmetic: An Introduction

Cascaded Integrator-Comb (CIC) Filter Introduction

Discussion Groups

IIR Filter Design Software

Free Online Books

See Also

Embedded SystemsFPGA

Discussion Groups | Comp.DSP | 1D Discrete wavelet transform(DWT)

There are 13 messages in this thread.

You are currently looking at messages 1 to .


Is this discussion worth a thumbs up?

-6

1D Discrete wavelet transform(DWT) - Umutesi Faith - 2005-11-14 15:02:00



Re: 1D Discrete wavelet transform(DWT) - Jani Huhtanen - 2005-11-15 01:17:00



Re: 1D Discrete wavelet transform(DWT) - Umutesi Faith - 2005-11-16 07:44:00

Thanks for the reply!
So do u mean that the further we do the decomposition the higher gets the
scale! The downsampling changes the scale,right! So what is affecting the
resolution then, in the DWT?
Actually this Nyquist rule refers especially to the discrete signal that
we are using and i think it makes sense, since we are sampling it
according the Nyquist theorem!!

************************************************************
>Consider an analogy: Take a photograph of the ground when you're standing
on
>it. Your photograph covers 1 m^2. Now go up x meters and take another
photo
>and the new image cover 4 m^2. Because the resolution of the image stays
>the same, you have discarded every other pixel from rows and every other
>from the columns of the image. But now you see the ground in a bigger
>scale.
>
>Oh, and there's no need for wavelets to comply with Nyquist rule. And
they
>usually don't (really short FIRs). Aliasing happens but it cancels out
at
>the syntesis end.
>
>-- 
>----
>Jani Huhtanen
>Tampere University of Technology, Pori
>


Re: 1D Discrete wavelet transform(DWT) - Jani Huhtanen - 2005-11-16 11:04:00

Umutesi Faith wrote:

> Thanks for the reply!
> So do u mean that the further we do the decomposition the higher gets the
> scale! The downsampling changes the scale,right! So what is affecting the
> resolution then, in the DWT?

Downsampling changes the scale, right. I'm not exactly sure what you mean by
the term scale. In my previous post scale meant "how much more you see"
when you downsample. So in this sence scale doubles when you downsample by
two. You "see" twice as long signal.

But in wavelet literature the term scale often refers to the level of
decomposition and there is different ways of numbering the different
scales. One may start with scale 0 as the original signal and scale 1 as
the first decomposition level. Or scale K as original and K-1 as first
level and 0 as the final level of decomposition. 

Resolution clearly gets lower each time we do the downsampling. This is
because we loose the details in favor of seeing more of the signal. From
dyadic decomposition (the basic DWT), we get "details" from every scale
(level) and if the decomposition is carried infinitely far we could
reconstruct the original signal from the details. 


> Actually this Nyquist rule refers especially to the discrete signal that
> we are using and i think it makes sense, since we are sampling it
> according the Nyquist theorem!!
> 

The downsampling by two in DWT doesn't require that the incoming
coefficients (or the signal at scale j) are bandlimited to fs/4, where fs
is the sampling rate before downsampling. Take for example the simplest
possible wavelet transform, lazy wavelet (use monospace font):

x --->|D2|--w1-->|U2|---
   |                    |
  |z^-1|              |z^-1|
   |                    |
   -->|D2|--w2-->|U2|-> + -----> x

D2 is downsampling by two (ie. discard every other sample) and U2 is
upsampling by two. The diagram shows wavelet transform (analysis and
synthesis) with only one level. 

Filters are only unit-delays so it's clear that frequency content stays
intact. Signals w1 and w2 are highly aliased due to the downsampling. But
at the summation alias components cancel out, resulting in perfect
reconstruction altough the signals were not bandlimited.

--
Jani Huhtanen
Tampere University of Technology, Pori


Re: 1D Discrete wavelet transform(DWT) - Jani Huhtanen - 2005-11-17 03:58:00

Sorry if this post comes twice. I sent the same post yesterday but it never
appeared on the comp.dsp group, so perhaps I have better luck this time.

Umutesi Faith wrote:
> Thanks for the reply!
> So do u mean that the further we do the decomposition the higher gets the
> scale! The downsampling changes the scale,right! So what is affecting the
> resolution then, in the DWT?

Downsampling changes the scale, right. I'm not exactly sure what you mean by
the term scale. In my previous post scale meant "how much more you see"
when you downsample. So in this sence scale doubles when you downsample by
two. You "see" twice as long signal.

But in wavelet literature the term scale often refers to the level of
decomposition and there is different ways of numbering the different
scales. One may start with scale 0 as the original signal and scale 1 as
the first decomposition level. Or scale K as original and K-1 as first
level and 0 as the final level of decomposition. 

Resolution clearly gets lower each time we do the downsampling. This is
because we loose the details in favor of seeing more of the signal. From
dyadic decomposition (the basic DWT), we get "details" from every scale
(level) and if the decomposition is carried infinitely far we could
reconstruct the original signal from the details. 


> Actually this Nyquist rule refers especially to the discrete signal that
> we are using and i think it makes sense, since we are sampling it
> according the Nyquist theorem!!
> 

The downsampling by two in DWT doesn't require that the incoming
coefficients (or the signal at scale j) are bandlimited to fs/4, where fs
is the sampling rate before downsampling. Take for example the simplest
possible wavelet transform, lazy wavelet (use monospace font):

x --->|D2|--w1-->|U2|---
   |                    |
  |z^-1|              |z^-1|
   |                    |
   -->|D2|--w2-->|U2|-> + -----> x

D2 is downsampling by two (ie. discard every other sample) and U2 is
upsampling by two. The diagram shows wavelet transform (analysis and
synthesis) with only one level. 

Filters are only unit-delays so it's clear that frequency content stays
intact. Signals w1 and w2 are highly aliased due to the downsampling. But
at the summation alias components cancel out, resulting in perfect
reconstruction altough the signals were not bandlimited.

--
Jani Huhtanen
Tampere University of Technology, Pori


Re: 1D Discrete wavelet transform(DWT) - Umutesi Faith - 2005-11-20 10:36:00

In my previous post scale meant "how much more you see"
>when you downsample. So in this sence scale doubles when you downsample

- - - - - - - - - - - - - - - - - - - - - - - - - - - -
Exactly, this was the point i wanted to understand,and i think you
explained it well but it is really hard to see it when having 1D signal
for instance of 64 samples and the downsampling gives 32 samples, this
means then that we see " twice" as long signal, How??


The downsampling by two in DWT doesn't require that the incoming
>coefficients (or the signal at scale j) are bandlimited to fs/4, where
fs
>is the sampling rate before downsampling.

- - - - - - - - - - - - - - - - - - - - - 
As far as i know, while doing 1D DWT ,the original signal has to be
sampled according the Nyquist theorem ( fs = 2fmax)

 - - - - -- - - - -- - - - - - - -- - - - -
By the way, i would like to load the daubechies decomposition filters
coefficients, i have perfomed the following command
load db4 ( in matlab command windonw)

db4 
  Columns 1 through 7 

    0.1629    0.5055    0.4461   -0.0198   -0.1323    0.0218    0.0233

  Column 8 

   -0.0075

I got the result above. Are these coefficients for lowpass or highpass
filters and how to find out what are the decomposition and synthesis
coefficients. Is it correct to say the the lowpass filter is actually the
scaling function and the highpass filter the wavelet function??

Kiitos!


Re: 1D Discrete wavelet transform(DWT) - Jani Huhtanen - 2005-11-20 12:00:00



Re: 1D Discrete wavelet transform(DWT) - Umutesi Faith - 2005-11-22 08:13:00

>More info: http://www.math.hmc.edu/faculty/ward/wavelets/pdfs/m185l2.pdf

I have been at this link, well i guess the calculations of these
coefficients are not as easy as i thought. It shows quite simple way of
getting the scaling and wavelet coefficients instead

S = (h0,h1,h2,h3)
W = (h3,-h2,h1,-h0)

So, does it mean that when i perform load dbN in matlab command window ,
what i get are the coefficients of the scaling function and from this i
can obtain the coefficients of the wavelet function just according to the
statement above.i have checked the freq(db4) it is a lowpass filter as you
said!

Once we have obtained a plot of DWT of a certain signal, where actually do
we see this time-frequency representation? I hope you don't get bored with
my questions.

you really have a good knowledge about the wavelets! Is it possible for me
to come to Tampere university to learn more about the wavelets?
kiitos again!


Re: 1D Discrete wavelet transform(DWT) - Jani Huhtanen - 2005-11-22 10:25:00

Umutesi Faith wrote:
>>More info: http://www.math.hmc.edu/faculty/ward/wavelets/pdfs/m185l2.pdf
> 
> I have been at this link, well i guess the calculations of these
> coefficients are not as easy as i thought. It shows quite simple way of
> getting the scaling and wavelet coefficients instead
> 
> S = (h0,h1,h2,h3)
> W = (h3,-h2,h1,-h0)
> 

I assumed that you were familiar with z-transform. Sorry about that. I'll
try to explain what I meant. Here are the equations again (without the typo
in H1): 

H0(z), analysis scaling filter (ie. S)
H1(z) = (-z)^-N*H0(-z^-1), analysis wavelet filter (ie. W)
F0(z) = H1(-z), synthesis scaling filter
F1(z) = -H0(-z), synthesis wavelet filter

Now lets say that the scaling coefficients are h0,h1,h2, and h3. 
Then the z-transform of the filter is

H0(z) = h0 + h1*z^-1 + h2*z^-2 + h3*z^-3.

OK, not let's use the equations above to derive the coefficients for other
filters. First analysis wavelet:

In our case N is 3 so,
H1(z) = (-z)^-3 * H0(-z^-1) = (-z)^-3 * (h0 - h1*z^1 + h2*z^2 - h3*z^3)
      = -h0*z^-3 + h1*z^-2 - h2*z^-1 + h3.
If you wonder why the signs change like that, it is simply because for
example (-z)^-2 = z^-2 and (-z)^-1 = -z^-1. The exponent of the z tells us
the place of the coefficient (0 corresponds to first coefficient and -1 to
the second).
=> H1 = (h3, -h2, h1, -h0). Which is exactly the same that you said.

> So, does it mean that when i perform load dbN in matlab command window ,
> what i get are the coefficients of the scaling function and from this i
> can obtain the coefficients of the wavelet function just according to the
> statement above

Yes. Oh, and if you're confused why db4 has more than 4 coefficients (as
Daubechies 4 should have) it is because in matlab the number after db
refers to the number of vanishing moments of the wavelet.

> Once we have obtained a plot of DWT of a certain signal, where actually do
> we see this time-frequency representation? I hope you don't get bored with
> my questions.

I assume you use dyadic-decomposition. Something like this (use monospace
font):

x---->|S|--a0------>|S|---a1------>|S|-->a2
   |             |              |
   -->|W|->b0    -->|W|-->b1    -->|W|-->b2

That should look like three level dyadic decomposition. S is scaling filter
and W is wavelet filter. For clarity I didn't include downsampling to the
ASCII art. 

Output from the filter bank are the signals b0,b1,b2 and a2. If x is N
samples long, then there is N/2 b0 samples, N/4 b1 samples, B/8 b2 and a2
samples (in total N samples of output). Samples of b0 are in time order
(not in any mixed order). So are b1, b2 and a2. So clearly you have time
representation.

Further every time the signal goes through S it gets lowpass filtered. That
is, it loses high-frequencies. This means that a2 contains low-frequency
information from x. Another way of saying is that a2 is an approximation of
x. b2 contains high frequency info of a1 which in turn is low frequency
info of x. So b2 is a frequency band and so is b1. b0 has gone trough only
highpass filter so it's the high-frequency info of x. One can think bs as
the details of the x, which are added in synthesis to the approximation aN.

Note that because of downsampling the bandwidth of b0 is fs/4 (where fs is
sampling rate of x) and b1 is fs/8, b2 and a2 are fs/16. This is why this
tree is also called octave decomposition (or something close to that, i'm
not sure about the exact english term).

So in this case when you plot the signals you should have plot like this:
    -------------------------
b0: | | | | | | | | | | | | |
    | | | | | | | | | | | | |
    | | | | | | | | | | | | |
    | | | | | | | | | | | | |
    -------------------------
b1: |   |   |   |   |   |   |
    |   |   |   |   |   |   |
    -------------------------
b2: |       |       |       |
    -------------------------
a2: |       |       |       |
    -------------------------

The | marks are borders of one sample and - are borders of one "band". Now
the time goes from left to right and frequency from top to bottom. 

Now its also easy to verify that low-frequency components (b2,a2) have lower
time resolution than b1 or b2 but higher frequency resolution and
vice-versa.

> Is it possible for me
> to come to Tampere university to learn more about the wavelets?

Yes, if you are a citizen of Finland. Perhaps through some exchange program
otherwise (or if you are planning on moving to Finland). Check from here to
be sure:
http://www.tut.fi/public/index.cfm?MainSel01&Sel01&Show97&Siteid2

-- 
Jani Huhtanen
Tampere University of Technology, Pori


Re: 1D Discrete wavelet transform(DWT) - Umutesi Faith - 2005-11-23 12:34:00

>http://www.tut.fi/public/index.cfm?

Thanks for the link , i'll try to get more information about it! I have
found some good books about the wavelets, maybe they are already familiar
to you :
Wavelet applications in Engineering Electromagnetics by Tapan K.
Sarkar...
Wavelet and filters banks by Gilbert Strang /Truong Nguyen
I will now keep reading...


| 1 | |