© 2000 by CRC Press LLC
Section IV
Video Compression

15

© 2000 by CRC Press LLC

Fundamentals of Digital
Video Coding

In this chapter, we introduce the fundamentals of digital video coding which include digital video
representation, rate distortion theory, and digital video formats. Also, we give a brief overview of
image and video coding standards which will be discussed in the subsequent chapters.

15.1 DIGITAL VIDEO REPRESENTATION

As we discussed in previous chapters, a digital image is obtained by quantizing a continuous image
both spatially and in amplitude. Digitization of the spatial coordinates is called image sampling,
while digitization of the amplitude is called gray-level quantization. Suppose that a continuous
image is denoted by

g

(

x

,

y


o

are the origin of image plane,

m

and

n

are the discrete
values 0, 1, 2, …, and

D

x

and

D

y

are the sampling intervals in the horizontal and vertical directions,
respectively. If the sampling process is extended to a third temporal direction (or the original signal
in the temporal direction is a discrete format), a sequence,

f


of the digitized image sequence.
fmn Qgx mxy ny
oo
,,,
()
=+ +
()
[]
DD
fmnt Qgx mxy n yt t t
ooo
,, , , ,
()
=+ ++
()
[]
DDD

© 2000 by CRC Press LLC

15.2 INFORMATION THEORY RESULTS (IV): RATE DISTORTION
FUNCTION OF VIDEO SIGNAL

The principal goal in the design of a video-coding system is to reduce the transmission rate
requirements of the video source subject to some picture quality constraint. There are only two
ways to accomplish this goal: reduction of the statistical redundancy and psychophysical redundancy
of the video source. The video source is normally very highly correlated, both spatially and
temporally; that is, strong dependence can be regarded as statistical redundancy of the data source.
If the video source to be coded in a transmission system is viewed by a human observer, the
perceptual limitations of human vision can be used to reduce transmission requirements. Human


© 2000 by CRC Press LLC

by the complexity, this separation may not be possible (Viterbi and Omura, 1979). There is still
some work on the joint optimization of the source and channel coding (Modestino et al., 1981;
Sayood and Borkenhagen, 1991). Returning to rate–distortion theory, the problem addressed here
is the minimizing the channel capacity requirement, while maintaining the average distortion at or
below an acceptable level.
The rate distortion function

R

(

D

) is the minimum average rate (bits/element), and hence
minimum channel capacity, required for a given average distortion level

D

. To make this more
quantitative, we suppose that the source is a sequence of pixels, and these values are encoded by
successive blocks of length

N

. Each block of pixels is then described by one of a denumerable set
of messages, {



(

Y

j

/

X

i

).
Therefore, the probability of the output message is
(15.3)
The information transmitted is called the average mutual information between

Y

and

X

and is
defined for a block of length

N

as follows:


X

) bits to code the data source without any information loss. In other words, the optimal error-
free encoder requires

H

N

(

X

) bits for the given data source. In the most general case, noise in the
communication channel will result in error at least some of the time, causing

Y

π

X

. As a result,
(15.7)
where

H

N

=
()
()
()
()
ÂÂ
2
QY X
ji
ji
TY TY
ji j i
()
=
=
π
Ï
Ì
Ó
()
=
()
1
0
,
,
. and
IXY PX PX HX
Nii
ji

(

X

,

Y

) be the average distortion between

X

and

Y

. Then, the average distortion per pixel is
defined as
(15.9)
The set of all conditional probability assignments,

Q

(

Y

/

X

(15.12)
It should be clear from the above discussion that the Shannon rate distortion function is a lower
bound on the transmission rate required to achieve an average distortion

D

when the block size is
infinite. In other words, when the block size is approaching infinity, the correlation between all
elements within the block is considered as the information contained in the data source. Therefore,
the rate obtained is the lowest rate or lower bound. Under these conditions, the rate at which a data
source produces information, subject to a requirement of perfect reconstruction, is called the entropy
of the data source, i.e., the information contained in the data source. It follows that the rate distortion
function is a generalization of the concept of entropy. Indeed, if the distortion measure is a perfect
reproduction, it is assigned zero distortion. Then,

R

(0) is equal to the source entropy

H

(

X

).
Shannon’s coding theorem states that one can design a coding system with rate only negligibly
greater than

R

) specifies the minimum achievable transmission rate required to transmit a data with average
distortion level

D

. The main value of this function in a practical application is that it potentially
gives a measure for judging the performance of a coding system. However, this potential value has
not been completely realized for video transmission. There are two reasons for this. First of all,
there currently does not exist tractable and faithful mathematical models for an image source. The
rate distortion function for Gaussian sources under the squared error distortion criterion can be found,
but it is not a good model for images. The second reason is that a suitable distortion measure,

D

,
which matches the subjective evaluation of image quality, has not been totally solved. Some results
have been investigated for this task such as

JND

(just noticeable distortion) (

see

www.sar-
noff.com/tech_realworld/broadcast/jnd/index.html). The issue of subjective and objective assess-
ment of image quality has been discussed in Chapter 1. In spite of these drawbacks, the rate
distortion theorem is still a mathematical basis for comparing the performance of different coding
systems.
DQ

,.
()
=
()
()
£
Min
1
RD R D
N
N
**
.
()
=
()
Æ•
Lim

© 2000 by CRC Press LLC

15.3 DIGITAL VIDEO FORMATS

In practical applications, most video signals are color signals. Various color systems have been
discussed in Chapter 1. A color signal can be seen as a summation of light intensities of three
primary wavelength bands. There are several color representations such as

YC

b

b

and

C

r
components specify the color information. Conversion between the

YC

b

C

r
and

RGB

formats can be accomplished with the following transformations, respectively.
(15.13)
(15.14)


CCIR

— According to CCIR601 (

see

CCIR Recommendation 601-1) (CCIR is now known
as ITU-R, International Telecommunications Union-R), a color video source has three components:
a luminance component (

Y

) and two-color difference or chrominance components (

C

b

and

C

r

or

U

and



¥

288 pixels/frame for the 4:2:0 format, both at 25 frames/second.

SIF (source input format)

— SIF has luminance resolution of 360

¥

240 pixels/frame at 30
frames/second or 360

¥

288 pixels/frame at 25 frames/second. For both cases, the resolution of the
chrominance components is half of the luminance resolution in both horizontal and vertical dimen-
sions. SIF can easily be obtained from a CCIR format using an appropriate antialiasing filter
followed by subsampling.

CIF (common intermediate format)

— CIF is a noninterlaced format. Its luminance resolution
has 352

¥

288 pixels/frame at 30 frames/second and the chrominance has half the luminance
resolution in both vertical and horizontal dimensions. Since its line value, 288, represents half the

˙
È
Î
Í
Í
Í
˘
˚
˙
˙
˙
+
È
Î
Í
Í
Í
˘
˚
˙
˙
˙
0 257 0 504 0 098
0 148 0 291 0 439
0 439 0 368 0 071
16
128
128
˙
-
-
-
È
Î
Í
Í
Í
˘
˚
˙
˙
˙
1 164 0 000 1 596
1 164 0 392 0 813
1 164 2 017 0 000
16
128
128
.

.
.
© 2000 by CRC Press LLC
NTSC television signal, it is a common intermediate format for both PAL or PAL-like systems and
NTSC systems. In the NTSC systems, only a line number conversion is needed, while in the PAL
or PAL-like systems only a picture rate conversion is needed. For low-bit-rate applications, the
quarter-SIF (QSIF) or quarter-CIF (QCIF) formats may be used since these formats have only a
quarter the number of pixels of SIF and CIF formats, respectively.

Recently, with advances in data compression and VLSI (very large scale integrated) techniques,
the data compression techniques have been extensively applied to video signal compression. Video
compression techniques have been under development for over 20 years and have recently emerged
as the core enabling technology for a new generation of DTV (both SDTV and HDTV) and
multimedia applications. Digital video systems currently being implemented (or under active
consideration) include terrestrial broadcasting of digital HDTV in the U.S. (ATSC, 1993), satellite
DBS (Direct Broadcasting System) (Isnardi, 1993), computer multimedia (Ada, 1993), and video
via packet networks (Verbiest, 1989). In response to the needs of these emerging markets for digital
video, several national and worldwide standards activities have been started over the last few years.
These organizations include ISO (International Standards Organization), ITU, formally known as
CCITT, International Telegraph and Telephone Consultative Committee), JPEG (Joint Photographic
© 2000 by CRC Press LLC
Experts Group), and MPEG (Motion Picture Experts Group) as shown in Table 15.1. The related
standards include JPEG standards, MPEG-1,2,4 standards, and H.261 and H.263 video teleconfer-
encing coding standards as shown in Table 15.2. It should be noted that the JPEG standards are
usually used for still image coding, but they can also be used to code video. Although the coding
efficiency would be lowered, they have been shown to be useful in some applications, e.g., studio
editing systems. Although they are not video-coding standards and were discussed in Chapters 7
and 8, respectively, we include them here for completeness of all international image and video
coding standards.
• JPEG Standard: Since the mid-1980s, the ITU and ISO have been working together
to develop a joint international standard for the compression of still images. Officially,
JPEG (ISO/IEC, 1992a) is the ISO/IEC international standard 10918-1, “Digital Com-
pression and Coding of Continuous-Tone Still Images,” or the ITU-T recommendation
T.81. JPEG became an international standard in 1992. JPEG is a DCT-based coding
algorithm and continues to work on future enhancements, which may adopt wavelet-
based algorithms.
• JPEG-2000: JPEG-2000 (see Joint Photographic Experts Group) is a new type of image
coding system under development by JPEG for still image coding. JPEG-2000 is consid-
ering using the wavelet transform as its core technique. This is because the wavelet

encing. Its technical content was completed in late 1995 and the standard was approved
in early 1996. It is based on the H.261 standard with several added features: unrestricted
© 2000 by CRC Press LLC
motion vectors, syntax-based arithmetic coding, advanced prediction, and PB-frames.
The H.263 version 2 video-coding standard, also known as “H.263+,” was approved in
January 1998 by the ITU-T. H.263+ includes a number of new optional features based
on the H.263. These new optional features are added to provide improved coding effi-
ciency, a flexible video format, scalability, and backward-compatible supplemental
enhancement information. H.263++ is the extension of H.263+ and is currently scheduled
to be completed in the year 2000. H.26L is a long-term project which is looking for
more efficient video-coding algorithms.
The above organizations and standards are summarized in Tables 15.1 and 15.2, respectively.
It should be noted that MPEG-7 in Table 15.2 is not a coding standard; it is ongoing work of
MPEG. It is also interesting to note that in terms of video compression methods, there is a growing
convergence toward motion-compensated, interframe DCT algorithms represented by the video
coding standards. However, wavelet-based coding techniques have found recent success in the
compression of still image coding in both the JPEG-2000 and MPEG-4 standards. This is because
it posseses unique features in terms of high coding efficiency and excellent spatial and quality
scalability. The wavelet transform has not successfully been applied to video coding due to several
difficulties. For one, it is not clear how the temporal redundancy can be removed in this domain.
Motion compensation is an effective technique for DCT-based video coding; however, it is not so
effective for wavelet-based video coding. This is because the wavelet transform uses large block
TABLE 15.1
List of Some Organizations for Standardization
Organization Full Name of Organization
CCITT International Telegraph and Telephone Consultative Committee
ITU International Telecommunication Union
JPEG Joint Photographic Experts Group
MPEG Moving Picture Experts Group
ISO International Standards Organization

i
, (i = 0, 1, 2, …). If we use the first-order linear predictor to predict
the current component value with the previous component, such as: X¢
i
= a X
i-1
+ b,
where a and b are two parameters for this linear predictor, and if we want to minimize
the mean-squared error of the prediction E{(X
i
– X
i
¢ )
2
}, what a and b do we have to
choose? Assuming that E{X
i
} = m, E{X
i
2
} = s
2
and E{X
i
X
i-1
} = r, (for i = 0, 1, 2, …),
where m, s, and r are constant.
15-2. To get a 128 ¥ 128 or 256 ¥ 256 digital image, write a program to use two 3 ¥ 3
operators (Sobel operator) such as:

-
È
Î
Í
˘
˚
˙
141
253
11
11
.
010
14 1
010
-

-
È
Î
Í
Í
Í
˘
˚
˙
˙
˙
,
© 2000 by CRC Press LLC

ISO/IEC JTC1 IS 11172, Coding of Moving Picture and Coding of Continuous Audio for Digital Storage
Media up to 1.5 Mbps, 1992b.
ISO/IEC JTC1 IS 13818, Generic Coding of Moving Pictures and Associated Audio, 1994.
ISO/IEC JTC1 FDIS 14496-2, Information Technology — Generic Coding of Audio-Visual Objects, Nov. 19,
1998.
Just Noticeable Distortion (JND) www.sarnoff.com/tech_realworld/broadcast/jnd/index.html.
Joint Photographic Experts Group (JPEG), ISO/IEC IS 11544, ITU-T Rec. T.81, 1992a.
Modestino, J. W., D. G. Daut, and A. L. Vickers, Combined source-channel coding of image using the block
cosine transform, IEEE Trans. Commun., COM-29, 1262-1274, 1981.
Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, Englewood Cliffs, NJ,
1989.
Sayood, K. and J. C. Borkenhagen, Use of residual redundancy in the design of joint source/channel coders,
IEEE Trans. Commun., 39(6), 838-846, 1991.
Shannon, C. E. A mathematical theory of communication, Bell Syst. Tech. J., 27, 379-423, 623-656, 1948.
Verbiest, W. and L. Pinnoo, A variable bit rate video codec for asynchronous transfer mode networks, IEEE
JSAC, 7(5), 761-770, 1989.
Viterbi, A. J. and J. K. Omura, Principles of Digital Communication and Coding, New York: McGraw-Hill,
New York, 1979.
Hpp
kk
k
M
=-
=
Â
log ,
2
1
Hp p p p=- - -
()