Abstract

Image data compression is concerned with the minimization of the volume of data used to represent an image. In recent years, image compression algorithms using Vector Quantization (VQ) have been receiving considerable attention. Unstructured vector quantizers, i.e., those with no restriction on the geometrical structure of the codebook, suffer from two basic drawbacks, viz., the codebook search complexity and the large storage requirement. This explains the interest in the structured VQ schemes, such as lattice-based VQ and multi-stage VQ. The objective of this thesis is to devise techniques to reduce the complexity of vector quantizers. In order to reduce the codebook search complexity and memory requirement, a universal Gaussian codebook in a residual VQ or a lattice-based VQ is used. To achieve a better performance, a part of work has been done in the frequency domain. Specifically, in order to retain the high-frequency coefficients in transform coding, two methods are suggested. One is developed for moderate to high rate data compression while the other is effective for low to moderate data rate. In the first part of this thesis, a residual VQ using a low rate optimal VQ in the first-stage and a Gaussian codebook in the other stages are introduced. From rate distortion theory, for most memoryless sources and many Gaussian sources with memory, the quantization error under MSE criterion, for small distortion, is memoryless and Gaussian. For VQ with a realistic rate, the error signal has a non-Gaussian distribution. It is shown that the distribution of locally normalized error signals, however, becomes close to a Gaussian distribution. In the second part, a new two-stage quantizer is proposed. The function of the first stage is to encode the more important low-pass components of the image and that of the second is to do the same for the high-frequency components ignored in the first stage. In one scheme, a high-rate lattice-based vector quantizer is used as the quantizer for both stages. In another scheme, the standard JPEG with a low rate is used as the quantizer of the first stage, and a lattice-based VQ is used for the second stage. The resulting bit rate of the two-stage lattice-based VQ in either scheme is found to be considerably better than that of JPEG for moderate to high bit rates. In the third part of the thesis, a method to retain the high-frequency coefficients is proposed by using a relatively huge codebook obtained by truncating the lattices with a large radius. As a result, a large number of points fall inside the boundary of the codebook, and thus, the images are encoded with high quality and low complexity: To reduce the bit rate, a shorter representation is assigned to the more frequently used lattice points. To index the large number of lattice points which fall inside the boundary, two methods that are based on grouping of the lattice points according to their frequencies of occurrence are proposed. For most of the test images, the proposed methods of retaining high-frequency coefficients is found to outperform JPEG