Data compression: Algorithms and architectures

by Markas, Tassos, Ph.D., Duke University, 1993, 170 pages; AAT 9405986

Abstract (Summary)

This dissertation presents the design of efficient lossy data compression for stand-still and multispectral images, as well as the design of high-performance parallel architectures suitable for compression of image and textual data. This dissertation is organized in three parts. The first part (chapter one) deals with some basic concepts of data compression; it describes the motivation factors that led me to pursue this work, it gives a brief description of the contributions of each research effort, and it concludes with an overview of existing distortion measures used to measure the loss of information in compressed images.

The second part is focused on the development of lossy compression algorithms for image data and it contains three independent research efforts. The first effort (chapter two) deals with a class of distortion controlled compression algorithms, where an image is encoded in such a way that the loss of information in the reconstructed image satisfies certain user requirements. An efficient encoding of the discrete wavelet transform, based on multidimensional bitmap trees, is presented in chapter three. This method has shown better compression/distortion performance compared to other existing compression methods, including the JPEG standard. Chapter four is devoted to the compression of multispectral images. A hybrid data compression algorithm that is based on histogram equalization and transform/subband coding has been designed. This algorithm takes into consideration the spectral and spatial redundancies found in multispectral images, and it outperforms existing methods. Its compression performance varies from 20-30:1 for perceptually lossless quality, to ratios exceeding 100:1 suitable for browsing type applications.

The third part of this dissertation is devoted in the development of high-performance parallel architectures, suitable for real-time compression of image and text data. For image data, a shared-memory parallel architecture that implements a fast version of the tree-structured vector quantization algorithm will be presented in chapter five. The last chapter presents a systolic-type parallel architecture that is capable of compressing text data at high-speeds without any loss of information. This architecture implements a parallel version of the textual substitution algorithm, which is a variation of the compression algorithm found in UNIX systems.

Indexing (document details)