Conditional and unconditional entropy-constrained vector quantization: High-rate theory and design algorithms

Entropy-constrained vector quantization is one of the most powerful compression techniques available nowadays for source coding designers. In this thesis new algorithms for design of entropy-constrained vector quantizers are presented. The algorithms presented here belong to a family of algorithms called constrained pairwise nearest neighbor (CPNN). These algorithms design codebooks by merging the pair of Voronoi regions which gives the least increase of distortion for a given decrease in entropy. We have developed three different algorithms called: entropy-constrained pairwise nearest neighbor (ECPNN), alphabet- and entropy-constrained pairwise nearest neighbor (AECPNN) and conditional entropy-constrained pairwise nearest neighbor (CECPNN). The first two algorithms AECPNN and ECPNN produce memoryless vector quantizers and the last algorithm CECPNN produces non-memoryless vector quantizers. This CPNN family of algorithms produces vector quantizers that are very competitive with the algorithms that are produced by the Lloyd's method I for vector quantizer design. The advantages that we can cite are: fast design, fast operation and user friendly. The degradation of rate-distortion performance presented by the codebooks developed by our algorithms are very small when compared with the codebooks produced by the Lloyd's method I. We also present a generalization of the high-rate quantization theory. This theory establishes analytically the operational rate-distortion performance of vector quantizers. We have derived new performance bounds for the conditional entropy-constrained vector quantizers that can be designed for example by the CECPNN algorithm. We link the results of the conditional high-rate quantization theory with the results of the conditional rate-distortion theory. Since we also have practical interests, we have used the quantizers developed by our techniques for compression of image subbands for a still image coder. We have also compressed displaced frame differences subband signals using our quantizers for a video coder. The rate-distortion performance results can be considered of high-quality.