Entropy-constrained vector quantization (ECVQ) offers substantially improved image quality over vector quantization (VQ) at the cost of additional encoding complexity. We extend results in the literature for fast nearest neighbor search of VQ to ECVQ. We use a new, easily computed distance that successfully eliminates most codewords from consideration.

Many variants of vector quantization offer substantially improved image quality at the cost of additional complexity in encoding. Algorithms for increased speed in nearest neighbor searches for full search VQ using the Euclidean distortion measure have been presented previously with excellent results. We extend these results to any variant of VQ such as entropy constrained vector quantization (ECVQ), and Bayes-risk VQ, which uses a Lagrangian distortion measure. Additionally we introduce a variation of the existing techniques which provides additional speedup for full search VQ using Euclidean distortion as well as for those VQs using modified distortion measures.