Abstract
Data compression is a challenging process with important practical applications. Specialized techniques for lossy and lossless data compression have been the subject of numerous investigations during last several decades. These general data compression algorithms were used also for compression of images with considerable success. However, with recent developments of new lossy and lossless data compression algorithms designed specifically for images, researchers have begun to achieve impressive gains in image compression efficiency. Lossy image compression tolerates compromising quality and information loss at the expense of compression gain. Lossless compression, in contrast, preserves image integrity fully, which is an important consideration in certain critical applications such as medical image processing. In this thesis we present a new technique for lossless compression of images based on the pseudo-distance technique proposed by Kuroki et al. We improve their algorithm by using a dynamic pseudo-distance matrix, context-models, and utilizing block-sorting transformations before the entropy coder. While their algorithm outperformed GIF by 16%, our algorithm achieves gains of 54% over GIF and 6% over PNG. We also present a parallelized implementation of our algorithm, which results in substantial gains in compression time while providing the desired compression efficiency. We demonstrate the efficiency of our compression algorithm on standard test image sets, including non-dithered and dithered color palette, and microarray images.