Fast nearest neighbor search for ECVQ and other modified distortion measures

Author

Johnson, Mary Holland ; Ladner, Richard ; Riskin, Eve A.

Author_Institution

Dept. of Electr. Eng., Washington Univ., Seattle, WA, USA

Volume

3

fYear

1996

fDate

16-19 Sep 1996

Firstpage

423

Abstract

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

Keywords

communication complexity; constraint theory; entropy codes; image coding; rate distortion theory; search problems; vector quantisation; Bayes-risk VQ; ECVQ; Euclidean distortion measure; Lagrangian distortion measure; annular constraint; double annulus; entropy constrained vector quantization; fast nearest neighbor search; full search VQ; image coding; image quality; modified distortion measures; spherical constraint; Costs; Distortion measurement; Electric variables measurement; Euclidean distance; Image coding; Image quality; Lagrangian functions; Nearest neighbor searches; Vector quantization; Velocity measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Image Processing, 1996. Proceedings., International Conference on

Conference_Location

Lausanne

Print_ISBN

0-7803-3259-8

Type

conf

DOI

10.1109/ICIP.1996.560521

Filename

560521