21 July 1999 Efficient codebook search for vector quantization: exploiting inherent codebook structure
Author Affiliations +
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.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Mohamed Qasem, Mohamed Qasem, Xun Du, Xun Du, Stanley C. Ahalt, Stanley C. Ahalt, "Efficient codebook search for vector quantization: exploiting inherent codebook structure", Proc. SPIE 3716, Visual Information Processing VIII, (21 July 1999); doi: 10.1117/12.354702; https://doi.org/10.1117/12.354702

Back to Top