Efficient codebook search for vector quantization: exploiting inherent codebook structure

Mohamed Qasem; Xun Du; Stanley C. Ahalt

doi:10.1117/12.354702

21 July 1999 Efficient codebook search for vector quantization: exploiting inherent codebook structure

Mohamed Qasem, Xun Du, Stanley C. Ahalt

Proceedings Volume 3716, Visual Information Processing VIII; (1999) https://doi.org/10.1117/12.354702
Event: AeroSense '99, 1999, Orlando, FL, United States

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.

Citation Download Citation

Mohamed Qasem, Xun Du, and Stanley C. Ahalt "Efficient codebook search for vector quantization: exploiting inherent codebook structure", Proc. SPIE 3716, Visual Information Processing VIII, (21 July 1999); https://doi.org/10.1117/12.354702

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available