As an efficient technique for data compression, vector quantization (VQ) has been successfully used for various applications involving VQ-based encoding and VQ-based recognition. The response time of encoding and recognition is a very important factor to be considered for real-time applications. The codeword search problem (i.e., the encoding problem) in VQ is to assign one codeword to the input vector in which the distortion between this codeword and the test vector is the smallest among all codewords. The encoding process is a computationally intensive procedure. This limits the applicability of VQ in practical considerations. Many fast algorithms using the squared Euclidean distortion measure have been proposed for reducing the computational complexity of the full search encoding. The threshold decomposition technique is an important technique for stack filter. By decomposing a vector into binary vectors based on the threshold decomposition technique of stack filter, a new distortion measure based on the decomposed binary vectors can be derived. This distortion measure needs to multiplication operations but some XOR operations and a counter. This distortion measure is suitable for VLSI implementation. Experiments were carried out to test the performance of the proposed encoding algorithm and the conventional full-search encoding algorithm using the squared Euclidean Distortion measure. From the experimental results, we see that the proposed algorithm is faster than the conventional full-search encoding algorithm. Especially, the encoding time will be much shorter than the conventional full-search encoding algorithm and the encoding structure will be much simpler if we use the hardware to encode the image. The PSNR of the proposed algorithm is only a little worse than that of the conventional algorithm and the new encoding algorithm is also faster than the conventional full-search encoding algorithm by software.
|