|email@example.com (Mike Lyall)
|Posted: Mon Dec 02, 2002 1:27 pm
Subject: Reply: WD 3.16 (#9) (Parallel Discrete Wavelet Transform)
|Reply: WD 3.16 (#9) (Parallel Discrete Wavelet Transform)
I think I may have a simple answer for your question.
The algorithm you described in Wavelet Digest is known as the
tree algorithm, and uses a tree-structered filter bank to accomplish
this. This can be re-drawn into an M-channel filter bank by finding
the transfer function along each brach of the tree. This will
create an M=J+1 channel filter bank, where J is the number of levels in
For example, take a J=3 level tree. The eqivalent M=4 channel FB
will have the transfer functions:
A3(z) = H1(z) --> H
A2(z) = H0(z) H1(z^2) --> LH
A1(z) = H0(z) H0(z^2) H1(z^4) --> LLH
A0(z) = H0(z) H0(z^2) H0(z^4) --> LLL
where H0(z) is the lowpass analysis filter and H1(z) is the highpass
analysis filter. The sequence after the arrow denotes the path
through the filter bank. Each of the above filters Ai(z) are
octave band filters and will perform a DWT. The downsampling rate after
each of this filters is calculated by multiplying together the
downsamplers found along the particular branch. For the example above,
the downsampling rates would be 2,4,8,8 for A3(z) to A0(z) respectively.
All of this comes from the "noble multirate identities" discussed in
much of the FB literature.
A good source to find this is P.P. Vaidyanathan's book "Multirate
Systems and Filter Banks", Prentice-Hall, 1993. The information
I just gave you is in section 11.3.3, pp. 491-496.
I've done some computational analysis of these structures and the
tree algorithm is more efficient than this "composite", as I call
it, structure. The reason lies behind the sampling rate at which the
filtering operations take place. Overall, there are about the same
number of filter taps for each configuration. However, in the
tree-structure, many of these operations are performed at a lower
rate, thus creating a savings. With the composite structure, all
operations are done at the highest rate. Hence, there is a lot of
redundancy involved. Polyphase implementations eliminate redundancies
that exist in both structures. In the tree algorithm, the number of
computations is reduced by 1/2. I'm not sure what the polyphase
composite does yet, but it still looks like the polyphase tree beats it,
especially for large trees.
Hope this helps you out.
Michael J. Lyall firstname.lastname@example.org
Atlantic Aerospace Electronics Corp.
6404 Ivy Lane, Ste. 300 12534 Woodstock Dr.
Greenbelt, MD 20770 Upper Marlboro, MD 20772
Phone: (301) 982-5202 (301) 627-3228
FAX: (301) 982-5278