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

Section 2.6. Intraframe Coding 31

attractive features, i.e., near-optimum energy-compaction, data-independent ba-
sis functions and fast algorithms, the DCT has become the “workhorse” of
most image and video coding standards.
The DCT was developed by Ahmed et al. in 1974 [32]. There are four
slightly di6erent versions of the DCT [33], but the one commonly used for
video coding is denoted by DCT-II. The 2-D DCT-II of an N × N block of
pels is given by

N −1 N −1
(2x +1)u'
(2y +1)v'

F(u; v)= C(u)C(v) f(x; y) cos 2N cos 2N ;
x=0 y=0
(2.21)

where f(x; y) is the pel value at location (x; y) within the block, F(u; v)is
the corresponding transform coeGcient, 0 ≤ u; v; x; y ≤ N − 1, and

 1 ;( =0;

C(()= N (2.22)
 2

N ; otherwise:
The transform coeGcient F (0; 0) at the top-left corner of the transformed block
is called the DC coeGcient because it contains the lowest frequencies in both
the horizontal and vertical dimensions. The corresponding inverse DCT trans-
form is given by

N −1 N −1
(2x +1)u'
(2y +1)v'
f(x; y)= C(u)C(v)F(u; v) cos 2N cos 2N :
u=0 v=0
(2.23)

It can be deduced from Equation (2.21) that the computational complexity
4
of an N × N 2-D DCT is of the order O(N ). However, one of the advantages
of the DCT is that it is separable. This means that a 2-D DCT can be separated
into a pair of 1-D DCTs. Thus, to obtain the 2-D DCT of an N × N block, a
1-D DCT is performed rst on each of the N rows of the block and then on
each of the N columns of the resulting block (or vice versa). The same applies
3
to the inverse DCT. This reduces the complexity to O(2N ). Further reductions
in complexity can be achieved using a number of fast DCT algorithms [31].
Beside transform selection, a signi cant factor that a6ects transform coding
performance and computational complexity is the block size. In general, the