A tree-structured locally optimal vector quantizer

Author

Wu, Xiaolin

Author_Institution

Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada

Volume

ii

fYear

1990

fDate

16-21 Jun 1990

Firstpage

176

Abstract

A tree-structured VQ (vector quantizer) that performs the nearest-neighbor encoding based on a locally optimal codebook generated by the algorithm of Y. Linde, A. Buzo and R.M. Gray (1980) is proposed. A design method is given to organize the code words by a quasi-voronoi tree. This tree structure allows the nearest-neighbor encoding without an exhaustive search. For a codebook of size K, encoding an input vector takes an expected number of O(log K) distortion evaluations for dimensionalities below eight; that time complexity is O(K^1/2) in practice for higher dimensionalities. The tree-structured VQ achieves a good compromise between optimality and encoding speed

Keywords

computational complexity; encoding; optimisation; trees (mathematics); code words; locally optimal codebook; nearest-neighbor encoding; quasi-voronoi tree; time complexity; tree-structured locally optimal vector quantizer; Computer science; Decoding; Design methodology; Encoding; Hardware; Image coding; Nearest neighbor searches; Speech coding; Tree data structures; Vector quantization;

fLanguage

English

Publisher

ieee

Conference_Titel

Pattern Recognition, 1990. Proceedings., 10th International Conference on

Conference_Location

Atlantic City, NJ

Print_ISBN

0-8186-2062-5

Type

conf

DOI

10.1109/ICPR.1990.119350

Filename

119350