An effective codebook search algorithm for vector quantization

Abstract

A new scheme that aims to cut down on the computational cost of the vector quantization (VQ) encoding procedure is proposed in this paper. In this scheme, the correlation between the codewords in the codebook is exploited and three test conditions are designed to filter out the impossible codewords in the codebook. The design of test conditions is based on the concept of integral projection.

From the experimental results, it is shown that the new scheme outperforms all the other schemes proposed so far in speeding up the VQ encoding procedure. When the codebook of 1024 codewords is used in the proposed scheme, the execution time it consumes is less than 2 per cent of that needed by the full search algorithm. The average time reduction rate is approximately 97.7 per cent compared to the execution time for the full search algorithm. In other words, the proposed scheme indeed provides an effective approach to speed up the VQ encoding procedure.

Keywords:

• image processing
• image compression
• vector quantization