Not a member?

# DSP Blogs > David Valencia > Discrete Wavelet Transform Filter Bank Implementation (part 2)

David Valencia
David studies in the Instituto Politécnico Nacional (IPN) at México, with a major in Telematics. Interests in signal transmission, telecommunications, encryption and networking. He has worked in several areas, including fuzzy control, signal processing, digital communications, etc.

Would you like to be notified by email when David Valencia publishes a new blog?

Pageviews: 655

# Discrete Wavelet Transform Filter Bank Implementation (part 2)

Posted by David Valencia on Dec 5 2010 under Matlab | Basics | Academia / Research | wavelet

Following the previous blog entry: http://www.dsprelated.com/showarticle/115.php

Difference between DWT and DWPT

Before getting to the equivalent filter obtention, I first want to talk about the difference between DWT(Discrete Wavelet Transform) and DWPT (Discrete Wavelet Packet Transform). The latter is used mostly for image processing.

While DWT has a single "high-pass" branch that filters the signal with the h1 filter, the DWPT separates branches symmetricaly: this means that one gets equal frequency resolution for high and low parts of the signal.

There is also a "reverse-DWPT" filter structure, called Transmultiplexer (short TMX) that has its very own particular details, but I'll talk about it later, as it requires to understand well the programs used for DWT and DWPT.

A DWT filter bank sketch:

A DWPT filter bank sketch:

So, for a 2-level bank, DWT gets 3 branches (2 low-pass, 1 high-pass), while DWPT gets 4 (2 low-pass, 2 high-pass).

And, for a 3-level bank, DWT gets 5 branches (4 low-pass, 1 high-pass), while DWPT gets 8 (4 low-pass, 4 high-pass).

Noble identities

The mathematical tool we can use to reduce these equivalent filters is known as "Noble Identities", which can be reviewed in the following link:

http://cnx.org/content/m10432/latest/

With this, one gets a filter that lets us do one single convolution instead of convoluting with each filter when moving along the branches. Simply put, it is faster and easier to compute.

First, a sketch on how the branches of a DWT filter bank look when converted to their equivalent pairs.

Then, a sketch on how the branches of a DWPT filter bank looks when converted to their equivalent pairs.

Result computation

Well, now we know how equivalent filters look like. Now, ¿How can we compute the results?

There are 2 possible ways of working this out:

1. With a convolution matrix (block processing)

2. Using chain-processing convolution

Convolution matrix (block processing)

In the first option one builds a matrix with the g or h filter coefficients, with a series of shiftings so that each output value is the sum of the products of each input value against its corresponding filter coefficient. This means, that for a given input of N samples, and a filter with L coefficients one must build a matrix of N columns with N+L-1 rows.

After that, multiply the input vector with the matrix and get the results. If the input has more samples, an even bigger matrix must be built. The problem here is that using a matrix the process gets very computing intensive, with all these sum and multiplication operations between vectors and matrices. It can work nicely with short filters, but as its lenght increases, the number of operation increases exponentially as the matrix grows.

When using a convolution matrix, one can use linear or circular convolution. Both options are implemented in code.

To see how a convolution matrix is built and how results are computed, check the code snippet at the bottom of this blog post.

Chain processing

On the other hand, another paradigm is to employ chain-processing, which is actually the most natural way to calculate a convolution. First, take the filter vector and transpose it, then sequentially multiply each of the filter's coefficients against the ones of the input, to get an output value. To get the remaining values, one must shift the input vector one position at a time.

This way, we can compute the transform of a real-time signal, when we don't know the size of the input (which we must know to build the matrix), as input data are taken sequentially.

Also -as we have seen before-, we have equivalent filters, this means that we only have to compute a single convolution and we're done. Furthermore, as there is a downsample stage, we only compute one of each N results (the one that we need), and therefore the computational time is greatly reduced against block (matrix) processing.

Later, I'll go into detail on how to work with chain processing, signaling rates, concurrency, synchronization (vital) and other programming issues I had to deal with.

In the meanwhile, you can check the code at the end of this blog post.

MATLAB Implementations (DWT, DWPT)

Summing up, the code for all the programs related to DWT, DWPT and TMX are listed below:

DWT - Linear convolution matrix: http://www.dsprelated.com/showcode/11.php

DWT - Circular convolution matrix: http://www.dsprelated.com/showcode/23.php

DWT - Linear Chain processing: http://www.dsprelated.com/showcode/47.php

Important, to run the DWT chain processing version you also need:

recorreder.m - http://www.dsprelated.com/showcode/43.php

formfilter.m (chain version) - http://www.dsprelated.com/showcode/44.php

formfilterdwt.m (chain version) - http://www.dsprelated.com/showcode/45.php

getsincdwt.m (chain version) - http://www.dsprelated.com/showcode/46.php

DWPT - Linear convolution matrix: coming soon!

DWPT - Circular convolution matrix: coming soon!

DWPT - Linear convolution Chain processing: coming soon!

4.5

posted by David Valencia
David studies in the Instituto Politécnico Nacional (IPN) at México, with a major in Telematics. Interests in signal transmission, telecommunications, encryption and networking. He has worked in several areas, including fuzzy control, signal processing, digital communications, etc.

Previous post by David Valencia: Discrete Wavelet Transform Filter Bank Implementation (part 1)
all articles by David Valencia

Would you like to be notified by email when David Valencia publishes a new blog?

stephaneb
Said:
Dear David, please try to limit the width of the images to 600 pixels. Thanks!
3 years ago
0
Sorry, you need javascript enabled to post any comments.
David VP
Replied:
@stephane: Thanks for the advice! I stretched the pictures to less than 600 px.
3 years ago
0
riksa.uhdiar
Said:
great,thx
2 years ago
0
Sorry, you need javascript enabled to post any comments.
wolf99
Said:
Kills me, did final year thesis on wavelets 3 yrs ago in MatLab, and there was hardly a scrap of understandable information about, now the net is overflowing with it... nice articles
2 years ago
0
Sorry, you need javascript enabled to post any comments.
David VP
Replied:
@Wolf99: Yes, in fact I had to implement the TMX filter bank as a project for a mid college course project, among other projects. I couldn't find information comprehensive enough so I had to figure it out from scratch. After some scrapping on paper and diagrams, here's the product. As I had a hard time solving the problem, I wanted to share it with the community, because I'm sure another person in the world will find it useful and it will save him time to use it in more important or complex stuff. Thanks for your comment ;)
2 years ago
+1
Digdarsan
Said:
thanks.It''s very useful.Plz send the code of DWPT using circular convolution.It is urgently required for my thesis.Thanks
5 months ago
+1