Asymptotic quantization error and cell-conditioned two-stage vector quantization.

Abstract

An asymptotic formula is derived for the probability density of the error produced by scalar and vector quantization (VQ). The r-th moment of this density yields the generalized form of Bennett's formula. Like Bennett's formula, the density formula is an asymptotic result that holds for quantizers with many points. It also shows how the error density is determined by the distribution of quantization cell sizes and the distribution of quantization cell shapes. Moreover, this happens in a way that much about these distributions is revealed in the density itself. Consequently, one may use empirical measurements of the error density to expose geometrical characteristics of a quantizer whose cell sizes and shapes are otherwise unknown. We use the insight gained about the relationship between the error density and quantizer geometrical features to analyze two kinds of structured vector quantization--Tree-Structured Vector Quantization (TSVQ) and Two-Stage Vector Quantization (2VQ)--and to propose an improved version of the latter. For TSVQ, we find that empirical measurements of the error density support the hypothesis that the standard TSVQ design algorithm produces a quantizer whose cells are a mixture of various rectangular shapes with an essentially optimal size distribution. For 2VQ, using the error density formula, we derive asymptotic formulas for its distortion, and also for the increase in its distortion relative to single-stage quantization. We find that a one bit increase in either stage causes a 6 dB gain in the Signal-to-Noise Ratio, and propose a time saving method for designing the second stage. Lastly, we identify the cause of the performance loss of 2VQ and propose a modified form of 2VQ, called Cell-Conditioned Two-Stage Vector Quantization (CC2VQ), that corrects for such. We analyze CC2VQ by deriving an asymptotic formula for its distortion, and show that for high rates, CC2VQ gives as good a performance as single-stage VQ. Moreover, the second stage can be a low complexity lattice quantizer.