Lifting factorization-based discrete wavelet transform architecture design

In this paper, two new system architectures, overlap-state sequential and split-and-merge parallel, are proposed based on a novel boundary postprocessing technique for the computation of the discrete wavelet transform (DWT). The basic idea is to introduce multilevel partial computations for samples near data boundaries based on a finite state machine model of the DWT derived from the lifting scheme. The key observation is that these partially computed (lifted) results can also be stored back to their original locations and the transform can be continued anytime later as long as these partial computed results are preserved. It is shown that such an extension of the in-place calculation feature of the original lifting algorithm greatly helps to reduce the extra buffer and communication overheads, in sequential and parallel system implementations, respectively. Performance analysis and experimental results show that, for the Daubechies (see J.Fourier Anal. Appl., vol.4, no.3, p.247-69, 1998) (9,7) wavelet filters, using the proposed boundary postprocessing technique, the minimal required buffer size in the line-based sequential DWT algorithm is 40% less than the best available approach. In the parallel DWT algorithm we show 30% faster performance than existing approaches.

I. Introduction

Efficient system architecture design for the discrete wavelet transform (DWT) has received a lot of attention recently [2]–[4], [1], [5]–[8] due to the success of DWT-based techniques in areas as diverse as signal processing, digital communications, numerical analysis, computer vision and computer graphics [9]. Two important parameters have been used to measure the efficiency of practical DWT system designs: 1) the memory necessary for the DWT computation (mostly in sequential algorithms) and 2) the communication overhead required by parallel DWT algorithms. As a matter of fact, memory efficiency is one major design factor for wavelet-based image compression applications in printers, digital cameras and space-borne instruments where large size memory leads to high cost and demands more chip design area [1], [10], [11]. Similarly, communication efficiency is critical to the success of parallel DWT systems built upon the network of workstations (NOWs) or local area multicomputers (LAMs), since in these systems cheap but slower communication links are used (as compared with dedicated parallel systems) [12], [8], [13], [14].