Parallel Algorithms for Wavelet-based Video Compression

The scientific field of the project is digital video compression using wavelet techniques. Contrasting to well-known standards for compressiong videos like MPEG-2 (as used on DVD) or MPEG-4 (as used in DIVX) or standards for videoconferencing like H.261, H.263, or H.264 which all use the discrete cosine transform (DCT) as the basic technology (which is also true for the JPEG format), video compression techniques exist which rely on the wavelet transform as underlying principle (as the recent standard for still image coding JPEG 2000 does). These techniques have not yet been standardized (apart from motion JPEG 2000), however, one of these algorithms is the most probable candidate for MPEG-21 SVC (scalable video coding). The main goal of this project was to investigate the possiblities of implementing wavelet-based video compression algorithms on special hardware. Target architectures are equipped with several compute units (i.e. processors) -- parallel algorithms need to be designed for this type of hardware. The aim was to significanlty reduce the time required for compression on the one hand, and to optimally make use of the parallel hardware platforms on the other hand. The following types of wavelet-based video coding have been considered: classical 2-D motion compensated wavelet and wavelet packet video coding, 3-D wavelet and wavelet packet video coding, Motion JPEG 2000, MPEG-4 VTC, Matching Pursuit. In particular, we have focussed onto the most expensive part of classical 2-D video coding: motion compensation. Most video compression technologies employ block-matching in this step, we investigate classical techniques and overlapped block matching. The results of the projects are very interesting. We have given a categorization and evaluation of different levels of granularity with respect to parallelism of classical 2-D motion compensated wavelet and wavelet packet video coding as well as of classical block matching. For 2-D and 3-D wavelet packet video coding we have developed an efficient way to handle data distribution on the one hand and zerotree coding on the other hand. Especially interesting was the discovery and correction of cass miss phenomena which led to poor execution performance in two reference implementations of JPEG 2000 and MPEG-4 VTC. For all other techniques not explicitly mentioned we have developed efficient parallel algorithms. During the project we have developed and theoretically analysed several parallel algorithms on the one hand, on the other hand these algorithms have been implemented on various hardware platforms using different programming paradigms: we have used several high perfomence computing target platforms (among them SGI Origin, Cray T3E, Hitachi SR8000, Linux Clusters, SGI Power Challenge) which have been programmed with software systems supporting high performance computing (like MPI, OpenMP, JAVA Threads, e.t.c.).