Computation of the complexity of vector quantizers by affine modeling

Several methods for evaluation of the complexity of data compression systems and for including complexity measures in the traditional rate-distortion analysis have been published in recent works. In this work, we indicate that the relationship between rate-distortion performance and complexity for some practical coding schemes-entropy-constrained vector quantization (ECVQ) and interpolative vector quantization (IVQ)-can be represented by affine models. For the same rate-distortion performance, the complexity of an interpolative vector quantizer is known to be significantly smaller than the complexity of a full-search entropy constrained vector quantizer, and this complexity difference is a suitable illustration for the rate-distortion-complexity framework. We use high-resolution theory arguments to derive the affine models for ECVQ and IVQ. The proposed affine complexity modeling successfully predicts the cost of vector quantizers designed from data sets that were not used to generate the models.