Image and Video Compression

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 Shannon’s 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.