Contractive encoding for arbitrary vector quantizers
This work introduces a variable-computation algorithm, called contractive encoding, for nearest neighbor encoding with an arbitrary vector quantization (VQ) codebook Y. The average number of distortion calculations required by a contractive-encoded vector quantizer (CVQ) with an M-dimensional codebook of rate R bits per sample is shown to be bounded above by MR. The number of compare operations is observed empirically to grow roughly as $M\sp3R$. Experimental results are presented for a memoryless Laplacian and a Gauss-Marko source, and for two different distortion metrics. For vectors of small to moderate dimension, CVQ may be an attractive alternative to binary tree-structured VQ (TSVQ). We also show how CVQ can be combined with direct-sum-codebooks to provide a simple and affordable methodology for the design of TCVQs, and illustrate the use of CVQ in the vector quantization of wavelet transforms of still image.
0984: Computer science