chapter 12, Vector Quantization

In IV Lossy Compression Techniques from: Digital Image Compression Techniques

Author(s): Majid Rabbani, Paul W. Jones

Published: 01 February 1991

Chapter DOI: 10.1117/3.34917.ch12

Chapter Page Count: 26 pages

Previous Chapter | Next Chapter

Front Matter

I Background
1. Digital Images and Image Compression

References to Part 1

II Information Theory Concepts
2. Source Models and Entropy

3. Variable-Length Codes

4. Entropy Estimation and Lossless Compression

5. Rate-Distortion Theory and Lossy Compression

References to Part 2

III Lossless Compression Techniques
6. Bit Plane Encoding

7. Lossless Predictive Coding

8. Lossy Plus Lossless Residual Encoding

References to Part 3

IV Lossy Compression Techniques
9. Lossy Predictive Coding

10. Transform Coding

11. Block Truncation Coding

12. Vector Quantization

13. Subband Coding

14. Hierarchical Coding

15. Choosing a Lossy Compression Technique

References to Part 4

A. Compression of Color Images

Back Matter

Preview

Chapter Contents

12.1 Codebook Generation
12.1.1 Linde-Buzo-Gray (LBG) algorithm
12.1.2 Codebook initialization
12.2 Codebook Design: Tree-Structured Codebooks
12.3 Codebook Design: Product Codes
12.4 Mean/Residual VQ (M/RVQ)
12.5 Interpolative/Residual VQ (I/RVQ)
12.6 Gain/Shape VQ (G/SVQ)
12.7 Classified VQ (CVQ)
12.8 Finite-State VQ (FSVQ)
12.9 VQ Results
12.10 Implementation/Complexity of M/RTVQ and I/RTVQ

Excerpt

In vector quantization (VQ), the original image is first decomposed into n-dimensional image vectors. The vectors can be generated in a number of different ways. For example, an n = l×m block of pixel values can be ordered to form an n-dimensional vector, or a 3-dimensional vector can be formed from the RGB color components of an individual pixel. The image may also be modified prior to forming the vectors, e.g., by the application of a DCT with the transform coefficients used as the vector components.

Each image vector, X, is then compared with a collection of representative templates or codevectors, math _i,i = 1,…,N_c, taken from a previously generated codebook. The codevectors are also of dimension n. The best match codevector is chosen using a minimum distortion rule; i.e., choose math _k such that d(X, math _k) ≤ d(X, math _j) for all j = 1,…,N_c, where d(X, math ) denotes the distortion incurred in replacing the original vector X with the codevector math . Ideally, the distortion measure should be mathematically tractable and subjectively meaningful so that the quantitative distortion values correspond to perceived quality. The most common distortion measure used in image VQ is MSE, which corresponds to the square of the Euclidean distance between the two vectors; i.e.,