Hierarchical data compression.

Abstract

Data compression is the process of reducing the number of bits in a representation of some data. Since the advent of digital techniques for storage and transmission, data compression has received a great deal of attention. In this dissertation, three low complexity, high performance, hierarchical data compression algorithms are proposed. Two are image compression algorithms and one is a text compression algorithm. The first algorithm, called quadtree predictive image coding (QPC), is a hybrid of quadtree coding and DPCM. The overall effect of this algorithm is to segment an image into blocks of various sizes, and to represent each by a variable-length coded quantization index. Though this algorithm has very low complexity (approximately 15 encoding operations, 4 decoding operations, and almost no multiplications/divisions are required per pixel), its rate/distortion performance is significantly better than JPEG and other quadtree based image coders. For example, at rate 0.17 on the test image lena, its signal-to-noise ratio is 3.2 dB better than JPEG. Also, its predictive nature suppresses blocking artifacts. The second algorithm, called quadtree-guided wavelet image coding, is a hybrid of wavelet and quadtree image coding. It first decomposes an image into baseband and outerbands and then uses QPC to encode the baseband wavelet coefficients. The resulting quadtree segmented baseband is then used to guide the encoding of outerbands. Though a wavelet decomposition must be performed, the method is not much more complex than QPC, because only a one- or two-scale decomposition is needed, the quadtree method is applied only to baseband, and simple methods are used to encode the remaining subbands. The result is a coding method with performance comparable to that of the best known image coders, but with less complexity. The third algorithm is an improve N-gram algorithm for text compression. The N-gram algorithm as a hierarchical method invented by Bugajski and Russo for losslessly compressing data. Based on this method, several improvements are proposed. When applied to English text these result in an algorithm with comparable complexity and approximately 10 to 30% less rate than the commonly used COMPRESS algorithm.