81
5
Image Compression Using
Vector Quantization
Vector quantization is an efcient technique used for compressing images. It
is based on the Shannon rate distortion theory, which says that better com-
pression is achieved if samples are coded using vectors instead of scalars.
The nite vectors of pixels are stored in a memory called codebook, which
is used for coding and decoding the images. The image to be compressed is
divided into blocks and called input vectors and are compared with vectors
in memory called codevectors for matches based on some distance criteria.
If the codevector matches the input vector, an index or address of memory
location is stored or transmitted. Because the address has less bits than the
codevector, compression is achieved. The decoding or decompression is the
inverse of encoding. The quality of the reconstructed images depends upon
proper design of the codebook. The algorithms used for the design of vec-
tor quantizers (VQs) (encoder and decoder), such as the oldest and famous
Linde-Buzo-Gray (LBG) algorithm, are discussed in detail. Various types of
VQs such as mean-removed, gain-shape, multistep, and others are presented.
The VQ designs using image transforms such as discrete cosine and wavelet
transforms are illustrated. The use of articial neural networks in VQ design
is also discussed. The performance of all designed codebooks are compared.
5.1 Introduction
In previous chapters, we studied the discrete cosine transform (DCT) and
wavelet-based image compression schemes in detail. The main part of all
lossy compression techniques is the quantizer. Quantization represents ne-
resolution data by a coarse approximation. Therefore, the difference between
ne and coarse resolution is quantization error, which is loss of information
or distortion. In all compression schemes studied so far, scalar quantization
is used. Scalar quantization takes place on a single sample followed by cod-
ing. This process may not involve memory. For example, pulse code modula-
tion (PCM) does not require memory, whereas predictive quantization does.
An important result of Shannons rate-distortion theory says that a good
compression ratio is achieved if samples are coded using vectors instead of
82 Image and Video Compression
scalars. Even input data are random, instead of encoding the sequence of
samples individually, coding using vectors provides an efcient code.
Quantization is a technique in which large sequences of samples or pixels
are mapped into very small sequence or code. This is suitable for efcient
storage or communication over the channel. Thus, the aim of the data com-
pression is to reduce the bit rate/bits per pixel in order to minimize the stor-
age requirements or bandwidth of the network. Data compression using VQ
may be applied to any one-, two-, or three-dimensional data.
This chapter deals with the theory of VQ and how it is applied for image
compression. Algorithms used for the design of VQs—that is, encoders and
decoders used in VQ—will be presented. The different types of VQs used
for efcient image compression are explained and compared. Before image
compression, VQ was used for speech compression and recognition.
5.2 Theory of Vector Quantization
In VQ, if the source is a one-dimensional signal, then it is grouped into L
consecutive samples; for a two-dimensional signal, which is an image, then
it is divided into n × n subimages or blocks of L pixels. Thus, as shown in
Figure5.1, the dimension of a vector is L. This vector or block is an input to
VQ. The complete VQ system consists of an encoder and a decoder. This is
merely a memory, which stores a vector whose size is the same as that of an
input vector. These encoders/decoders make up the codebook, and the vec-
tors stored are called codevectors. The code words are selected or designed
to be representative of the input vectors or blocks in an image to be com-
pressed. Each codevector is assigned a binary index that is an address of
Nearest
Neighborhood
Codebook
(Encoder)
VQ
Channel Lookup Table
Output
Vectors
Input
Vectors
Codebook
(Decoder)
FIGURE 5.1
Block diagram of the vector quantizer process.

Get Image and Video Compression now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.