Fast finite-state codebook design algorithm for vector quantization

Ruey-Feng Chang; Wen-Tsuen Chen

doi:10.1117/12.50232

1 November 1991 Fast finite-state codebook design algorithm for vector quantization

Ruey-Feng Chang, Wen-Tsuen Chen

Proceedings Volume 1605, Visual Communications and Image Processing '91: Visual Communication; (1991) https://doi.org/10.1117/12.50232
Event: Visual Communications, '91, 1991, Boston, MA, United States

Abstract

The Linde-Buzo-Gray (LBG) algorithm is usually used to design a codebook for encoding images in the vector quantization. In each iteration of this algorithm, we must search the full codebook in order to assign the training vectors to their corresponding codewords. Therefore, the LBG algorithm needs large computation effort to obtain a good codebook from the training set. In this paper, we propose a finite-state LBG (FSLBG) algorithm for reducing the computation time. Instead of searching the whole codebook, we search only those codewords that are close to the codeword for a training vector in its previous iteration. In general, the number of these possible codewords can be very small without sacrificing performance. Because of searching only a small part of the codebook, the computation time is reduced. In our experiment, the performance of the FSLBG algorithm in terms of the signal-to-noise ratio is very close to that of the LBG algorithm. However, the computation time of the FSLBG algorithm is only about 10 percent of the time required by the LBG algorithm.

Citation Download Citation

Ruey-Feng Chang and Wen-Tsuen Chen "Fast finite-state codebook design algorithm for vector quantization", Proc. SPIE 1605, Visual Communications and Image Processing '91: Visual Communication, (1 November 1991); https://doi.org/10.1117/12.50232

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