Fast search algorithms for vector quantization of images using multiple triangle inequalities and wavelet transform.

Abstract

The encoding of vector quantization (VQ) needs expensive computation for searching the closest codevector to the input vector. This paper presents several fast encoding algorithms based on multiple triangle inequalities and wavelet transform to overcome this problem. The multiple triangle inequalities confine a search range using the intersection of search areas generated from several control vectors. A systematic way for designing the control vectors is also presented. The wavelet transform combined with the partial distance elimination is used to reduce the computational complexity of the distance calculation of vectors. The proposed algorithms provide the same coding quality as the full search method. The experimental results indicate that the new algorithms perform more efficiently than existing algorithms.