文档介绍：Recursive Merge-Filter Algorithm for
Computing the Discrete Wavelet Transform
Kunal Mukherjee and Amar Mukherjee
Abstract We present a new wavelet transform algorithm with a data flow that can fully exploit the
locality property of wavelets. This leads to highly optimized fine grained wavelet coding algo-
rithms, in terms of pipelining performance, flexible data granularity and reliability of transmis-
sion. It can be used by all wavelet coding methods, and has been demonstrated to improve the
performance of the most essful ones. We propose a new bottom-up Embedded Zerotree
Wavelet (EZW) image coding algorithm, and demonstrate a 5-10% speedup over EZW, by means
of close coupling between the new wavelet transform algorithm and the EZW encoding. The
Recursive Merge Filter (RMF) operator introduced in this paper reduces plexity of creat-
ing larger DWTs of size 2N, from smaller ones of size N, by O(logN). Because this is a frequent
operation in the training process of the wavelet based hierarchical vector quantization (W-HVQ)
method, the result is a significant speedup overall. The RMF algorithm facilitates new fine
grained wavelet codecs, based on EZW encoding of sub-images using our new bottom-up algo-
rithm - this can give rise to future standards along the lines of “wavelet JPEG” and “wavelet
MPEG”.
Keywords: recursive merge filter, wavelet transform, hierarchical vector quantization,
zero tree
1
Introduction
In current wavelet-based codecs (. [1], [3], [8]) the discrete wavelet transform (DWT)
is treated as a “black box” which cannot start generating the code until the entire image has been
transformed. This gives rise to several limitations, such as:
• performance - putations in these codecs cannot be pipelined until after the entire trans-
form puted;
• functionality - it is impossible to generate code at the sub-image level, . fine-grained coding
is not possible; and
• reliability - monolithic code, code for t