Page 59 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

36 Chapter 2. Video Coding: Fundamentals

Input Reconstructed
Image Form input s Search for i i Table r i Merge Image
vectors best match lookup vectors

Codebook Codebook
, 1
i r i , = … , N i r i , = … , N
, 1
(a) Encoder (b) Decoder
Figure 2.13: A vector quantization system

rst decomposed into k-dimensional input vectors. Those input vectors can
be generated in a number of di6erent ways; they can refer to the pel val-
ues themselves or to some appropriate transformation of them. For example,
a k = M × M block of pels can be ordered to form a k-dimensional input
T
k
vector s =[s 1 ;:::;s k ] . In VQ, the k-dimensional space R is divided into
N regions, or cells, R i . Any input vector that falls into cell R i is repre-
T
sented by a representative codevector r i =[r 1 ;:::;r k ] . The set of codevec-
tors C = {r 1 ;:::; r N } is called the codebook. Thus, the function of the en-
coder is to search for the codevector r i that best matches the input vector
s according to some distortion measure d(s; r i ). The index i of this code-
vector is then transmitted to the decoder using at most I = log N bits. At
2
the decoder, this index is used to lookup the codevector from an identical
codebook. A block diagram of a vector quantization system is illustrated in
Figure 2.13.
Compression in VQ is achieved by using a codebook with relatively few
codevectors compared to the number of possible input vectors. The resulting
bit rate of a VQ is given by I=k bits=pel. In theory, as k →∞, the performance
of VQ approaches the rate-distortion bound. However, large values of k make
codebook storage and searching impractical. Values of k =4 × 4 and N = 1024
are typical in practical systems.
A very important problem in VQ is the codebook design. A commonly
used approach for solving this problem is the Linde-Buzo-Gray (LBG) algo-
rithm [45], which is a generalization of the Lloyd-Max algorithm for scalar
quantization. The LBG algorithm computes a codebook with a locally min-
imum average distortion for a given training set and given codebook size.
Entropy-constrained vector quantization (ECVQ) [46] extends the LBG al-
gorithm for codebook design under an entropy constraint. Another
important problem is the codebook search. A full search is usually imprac-
tical, and a number of fast-search algorithms have been proposed,
e.g., Ref. 47.