Fine-coarse vector quantization

A fast method for searching an unstructured vector quantization (VQ) codebook is introduced and analyzed. The method, fine-coarse vector quantization (FCVQ), operates in two stages: a `fine' structured VQ followed by a table lookup `coarse' unstructured VQ. Its rate, distortion, arithmetic complexity, and storage are investigated using analytical and experimental means. Optimality condition and an optimizing algorithm are presented. The results of experiments with both uniform scalar quantization and tree-structured VQ (TSVQ) as the first stage are reported. Comparisons are made with other fast approaches to vector quantization, especially TSVQ. It is found that when rate, distortion, arithmetic complexity, and storage are all taken into account, FCVQ outperforms TSVQ in a number of cases. In comparison to full search quantization, FCVQ has much lower arithmetic complexity, at the expense of a slight increase in distortion and a substantial increase in storage. The increase in mean-squared error (over full search) decays as a negative power of the available storage