Methods and design algorithms for predictive quantization of signals and images.
Kevin M. Holt · Deep Blue (University of Michigan) · 2004
This dissertation is concerned with methods for predictive quantization of signals and images, as well as code design algorithms for these methods. Our first contribution is a careful treatment of the technique of deterministic annealing for entropy-constrained quantizer design. Deterministic annealing helps avoid local optima by optimizing a probabilistic quantizer model while encouraging randomness. With no rate (or entropy) constraint, deterministic annealing has shown great promise, but for entropy constrained design, numerous problems arise due to the contrary goals of small index entropy and large quantization randomness. We point out specific problems (which lie with the choices of cost function and splitting method) along with how they can be addressed. Our contributions allow improved training algorithms which, in simulations, improve up to 1.5 dB over some existing methods. Next, we give a new predictive coding method, Coding by Selective Prediction (CSP). Whereas a memoryless vector quantizer can be characterized by a codebook of possible reproduction vectors, CSP is characterized by a codebook of possible affine predictor functions. For images, these predictors may be tailored to different edges or textures, allowing CSP to outperform conventional predictive VQ typically by 0.35 dB. We present both Lloyd-style and DA training algorithms for predictor design. Lastly, we present Quadtree Coding by Selective Prediction (QCSP), a new method intended specifically for image coding. In QCSP, we divide an image into blocks, segment each block using quadtrees, and use CSP to code each segment. The method performs rather well, achieving PSNR values typically 2--4 dB better than those of JPEG and similar to those of JPEG 2000 at equivalent rates. Furthermore, because QCSP employs spatial prediction, it does not suffer the ringing and blurring effects that are common in low-rate transform coding, and due to the tailored predictors of CSP, QCSP generally reproduces edges well and produces perceptually sharp images even at low rates.