A fast search algorithm for vector quantization using a directed graph

Author

Cao, Hugh Q. ; Li, Weiping

Author_Institution

Dept. of Electr. Eng. & Comput., Lehigh Univ., Bethlehem, PA, USA

Volume

10

Issue

4

fYear

2000

fDate

6/1/2000 12:00:00 AM

Firstpage

585

Lastpage

593

Abstract

A fast search algorithm for vector quantization (VQ) is presented. This approach provides a practical solution to the implementation of a multilevel search based on a special designed directed graph (DG). An algorithm is also given of the optimal DG for any given practical source. Simulation results obtained from applying this approach to still images have shown that it can reduce the searching complexity to 3% of the exhaustive search vector quantization (ESVQ) while introducing only negligible searching errors. It has also been shown that the searching complexity is close to a linear growth with the bit rate rather than an exponential growth in ESVQ,

Keywords

computational complexity; directed graphs; image coding; search problems; vector quantisation; ESVQ; VQ; bit rate; directed graph; exhaustive search vector quantization; fast search algorithm; image coding; linear searching complexity; multilevel search; optimal directed graph; optimisation; searching complexity reduction; searching errors; simulation results; still images; vector quantization; Bit rate; Computational complexity; Degradation; Encoding; Nearest neighbor searches; Tree data structures; Vector quantization; Video compression; Video sequences;

fLanguage

English

Journal_Title

Circuits and Systems for Video Technology, IEEE Transactions on

Publisher

ieee

ISSN

1051-8215

Type

jour

DOI

10.1109/76.845003

Filename

845003