Databases Reference
In-Depth Information
F I GU R E 13 . 3
Basis set for the discrete cosine transform. The numbers in the circles
correspond to the row of the transform matrix.
13.4.2 Discrete Cosine Transform
The discrete cosine transform (DCT) gets its name from the fact that the rows of the
N
×
N
transform matrix
C
are obtained as a function of cosines:
N
cos
(
2
j
+
1
)
i
π
⎧
⎨
i
=
0
,
j
=
0
,
1
,...,
N
−
1
2
N
[
C
]
i
,
j
=
(43)
N
cos
(
2
j
+
1
)
i
π
⎩
i
=
1
,
2
,...,
N
−
1
,
j
=
0
,
1
,...,
N
−
1
2
N
The rows of the transform matrix are shown in graphical form in Figure
13.3
. Notice how the
amount of variation increases as we progress down the rows; that is, the frequency of the rows
increases as we go from top to bottom.
The outer products of the rows are shown in Figure
13.4
. Notice that the basis matrices
show increased variation as we go from the top-left matrix, corresponding to the
θ
00
coefficient,
to the bottom-right matrix, corresponding to the
coefficient.
The DCT is closely related to the discrete Fourier transform (DFT) mentioned in Chapter 11
and, in fact, can be obtained from the DFT. However, in terms of compression, the DCT
performs better than the DFT.
To see why, recall that when we find the Fourier coefficients for a sequence of length
N
,
we assume that the sequence is periodic with period
N
. If the original sequence is as shown in
Figure
13.5
(a), the DFT assumes that the sequence outside the interval of interest behaves in the
manner shown in Figure
13.5
(b). This introduces sharp discontinuities at the beginning and the
θ
(
N
−
1
)(
N
−
1
)
