A Complexity Reduction Technique for Image Vector Quantization

A new technique for reduction of the complexity of spatial domain image vector quantization (VQ) is proposed. In the new technique, the conventional spatial domain distortion measure is replaced by a transform domain subspace distortion measure. Due to the energy compaction properties of image transforms, the dimensionality of the subspace distortion measure can be reduced drastically without significantly affecting the performance of the new quantizer. A modified LBG algorithm incorporating the new distortion measure is proposed. Unlike conventional transform domain VQ, the codevector dimension is not reduced and a better image quality is guaranteed. The performance and design considerations of a real-time image encoder using the new technique are investigated. Compared with spatial domain techniques, a four times speed up in both codebook design time and search time are obtained for mean residual VQ while at the same time reducing the size of fast RAM also by a factor of four. Degradation of image quality is less than 0.4 dB in PSNR. © 1992 IEEE