Parallelization of the 2D fast wavelet transform with a space-filling curve image scan
Gauthier Lafruit, Jan P. Cornelis · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1995
The classical raster (i.e. row by row) image scan does not match the data processing flow, internal to the pyramid structure obtained by the 2D fast wavelet transform of a 2N X 2N image with a (2(gamma ) + 1) X (2(gamma ) + 1) mother wavelet, therefore introducing large latencies, important memory requirements, and irregular processor activities in parallelized implementations. A new algorithm is proposed in which all image data are scanned following a fractal, space-filling curve, which, compared to the raster image scan, offers the following advantages: i) it reduces the calculation memory with almost a factor 2, while maintaining a simple address calculation scheme, ii) the latency in the first N-(gamma) -3 levels of the pyramid, which contain a high percentage of the pyramid data, is minimized, leading to improved block-oriented post-processing capabilities (e.g. vector quantization for image compression), iii) the calculations are spread out more uniformly over one frame slot, and iv) the process is naturally subdivided into similar subproblems, increasing the granularity of the algorithm, without introducing severe communication bottle-necks for parallel architectures.