Share Email Print

Proceedings Paper

Efficient codebook search for vector quantization: exploiting inherent codebook structure
Author(s): Mohamed Qasem; Xun Du; Stanley C. Ahalt
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

A major problem associated with vector quantization is the complexity of exhaustive codebook search. This problem has hindered the use of this powerful technique for lossy image compression. An exhaustive codebook search requires that an input vector be compared against each code vector in the codebook in order to find the code vector that yields the minimum distortion. Because an exhaustive search does not capitalize on any underlying structure of the code vectors in hyperspace, other researchers have proposed technique that exploit codebook structure, but these technique typically result in sub-optimal distortion. We propose a new method that exploits the nearest neighbor structure of code vectors and significantly reduces the number of computations required in the search process. However, this technique does not introduce additional distortion, and is thus optimal. Our method requires a one time precomputation and a small increase in the memory required to store the codebook. In the best case, arising when the code vectors are largely dispersed in the hyperspace, our method requires only partial search of the codewords. In the worst case, our method requires a full search of the codebook. Since the method depends on the structure of the code vectors in the hyperspace, it is difficult to determine its efficiency in all cases, but test on typical image compression tasks have shown that this method offers on average an 81.16 percent reduction in the total number of multiples, additions and subtractions required as compared to full search.

Paper Details

Date Published: 21 July 1999
PDF: 6 pages
Proc. SPIE 3716, Visual Information Processing VIII, (21 July 1999); doi: 10.1117/12.354702
Show Author Affiliations
Mohamed Qasem, The Ohio State Univ. (United States)
Xun Du, The Ohio State Univ. (United States)
Stanley C. Ahalt, The Ohio State Univ. (United States)

Published in SPIE Proceedings Vol. 3716:
Visual Information Processing VIII
Stephen K. Park; Richard D. Juday, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?