Parallel computation of 3D wavelets

The Discrete Wavelet Transform (DWT) is becoming a widely used tool in image processing and other data analysis areas. A non-conventional variation of a spatiotemporal 3D DWT has been developed in order to analyze motion in time-sequential imagery. The computational complexity of this algorithm is Θ(n³), where n is the number of samples in each dimension of the input image sequence. Methods are needed to increase the speed of these computations for large data sets. Fortunately, wavelet decomposition is very amenable to parallelization. Coarse-grained parallel versions of this process have been designed and implemented on three different architectures: a distributed network represented by a distributed network of Sun SPARCstation 2 workstations: two Intel hypercubes (an iPSC/2 and an iPSC/860); and a Thinking Machines Corporation CM-5, a massively parallel SPMD. This non-conventional 3D wavelet decomposition is very suitable for coarse-grain implementation on parallel computers with proper load balancing. Close to linear speedup over serial implementations has been achieved using a distributed network. Near-linear speedup was obtained on the hypercubes and the CM-5 for a variety of image-processing applications