Chapter 18

Discrete Cosine Transform

 Learning Objectives
 Introduction to the DCT and IDCT.
 Decomposition of a 2-D DCT to two 1-D
DCTs.
 Implementation of a 2-D DCT using a 1-
D DCT.

hapter 18, Slide 2 Dr. Nai

 Introduction 8 pixels

8 pixels
An
8x8
block

Im age

E n tro p y
DCT Q u an tiser zig zag
E n co d er

C h an n el
or
S to rag e

reverse E n tro p y
ID C T D eq u an tiser
zig zag D eco d er

 To perform the JPEG coding, an image (in colour or grey scales) is first
subdivided into blocks of 8x8 pixels.
 The Discrete Cosine Transform (DCT) is then performed on each block.
 This generates 64 coefficients which are then quantised to reduce their
magnitude.

hapter 18, Slide 3 Dr. Nai

 Introduction 8 pixels

8 pixels
An
8x8
block

Im age

E n tro p y
DCT Q u an tiser zig zag
E n co d er

C h an n el
or
S to rag e

reverse E n tro p y
ID C T D eq u an tiser
zig zag D eco d er

 The coefficients are then reordered into a one-dimensional array in

a zigzag manner before further entropy encoding.
 The compression is achieved in two stages; the first is during
quantisation and the second during the entropy coding process.
 JPEG decoding is the reverse process of coding.

hapter 18, Slide 4 Dr. Nai

 Implementation of the DCT
 DCT-based codecs use a two-
dimensional version of the transform.
 The 2-D DCT and its inverse (IDCT) of
an N x N block are shown below:
2 N1 N1
(2 x  1)u (2 y  1)v
 2-D DCT: F (u , v)  C (u )C (v)  f ( x, y ) cos[ ] cos[ ]
N y 0 x 0 2N 2N

 2 N1 N1
(2 x  1)u (2 y  1)v
2-D IDCT: f ( x, y ) 
N
  C (u )C (v) F (u, v) cos[
v 0 u 0 2N
] cos[
2N
]

 Note: The DCT is similar to the DFT

since it decomposes a signal into a series
of harmonic cosine functions.
hapter 18, Slide 5 Dr. Nai
 2-D DCT using a 1-D DCT Pair
 One of the properties of the 2-D DCT is that it is separable meaning
that it can be separated into a pair of 1-D DCTs.
 To obtain the 2-D DCT of a block a 1-D DCT is first performed on the
rows of the block then a 1-D DCT is performed on the columns of the
resulting block.
 The same applies to the IDCT.
 This process is illustrated on the following slide.

hapter 18, Slide 6 Dr. Nai

 2-D DCT using a 1-D DCT Pair
C olum ns (256 pixels )
R aw B loc k of P ixels
128 127 130 128 134 130 128 1

128 127 130 128 134 130 128 1

A n 8x8
Rows (256 pixels) bloc k 125 126 130 127 130 131 128 1

124 128 127 126 129 130 127 1

131 132 130 129 132 128 129 1

pixel[n] 129 131 134 131 133 129 131 1

129 134 134 136 136 137 134 1

pixel
[256+ n] 133 135 136 138 137 140 135 1

pixel[n+ 1]

P art of a pic ture

F inal res ult after D C T by c olum ns R es ult after D C T by row s

1024 -4 -1 1 0 -4 -6 0 1 365 -1 -4 1 1 -3 1

-1 8 -1 1 0 2 -2 2 4 365 -1 -4 1 1 -3 1

11 -1 -5 2 0 0 1 -1 362 -3 -4 0 -3 -1 2

0 2 2 -3 3 -2-1 -2 3 359 -3 -3 0 -3 -3 0

0 1 1 1 0 -1 -1 -2 368 1 1 -1 1 -3 -2

-4 -3 -3 -1 -3 -1 0 -2 370 0 -3 -3 -1 -1 -1

-2 0 -1 -2 -1 1 1 0 378 -3 -6 0 -3 -2 -1

2 0 1 0 0 -1 -1 -1 383 -1 -6 2 -3 0 0

hapter 18, Slide 7 Dr. Nai

 2-D DCT using a 1-D DCT Pair

 2 N1
(2i  1)k
1-D DCT: X (k )  C (k ) x(i ) cos[ ]
N i 0 2 N

N1
 ( 2i  1) k
1-D IDCT: x (i ) 
2
N  C ( k ) X ( k ) cos[ 2N
]
k 0

k = 0, 1, 2, …, N-1.
and i = 0, 1, 2, …, N-1.

hapter 18, Slide 8 Dr. Nai

 Implementation Issues
 Precalculate the DCT coefficients and
scale them (see \Links\DCT [Link]).
( 2i + 1) kp
2 * coef (i , k ) =cos[ ]
16
0 .7 0 7 0 .7 0 7 0 .7 0 7 0 .7 0 7 0 .7 0 7 0 .7 0 7 0 .7 0 7 0 .7

0 .9 8 1 0 .8 3 1 0 .5 5 6 0 .1 9 5 -0 .1 9 5 0 .5 5 6 -0 .8 3 1 -.9
+ 0 .3 8
0 .9 2 4 0 .3 8 3 -0 .3 8 3 -.0 9 2 4 -0 .9 2 4 -0 .3 8 3 0 .9
3
0 .8 3 1 -0 .1 9 5 -0 .9 8 1 -0 .5 5 6 0 .5 5 6 0 .9 8 1 0 .1 9 5 -0 .8

0 .7 0 7 -0 .7 0 7 -.7 0 7 0 .7 0 7 0 .7 0 7 -0 .7 0 7 -0 .7 0 7 0 .7

0 .5 5 6 -0 .9 8 1 0 .9 8 1 0 .8 3 1 -0 .8 3 1 -0 .1 9 5 0 .9 8 1 0 .5

0 .3 8 3 -0 .9 2 4 0 .9 2 4 0 .3 8 3 -0 .3 8 3 0 .9 2 4 -0 .9 2 4 0 .3

0 .1 9 5 0 .5 5 6 0 .8 3 1 -0 .9 8 1 0 .9 8 1 -0 .8 3 1 0 .5 5 6 -0 .1

M u ltip lie d b y 2 1 1
c o e f(i, k ) in Q 1 2 fo rm a t
1448 1448 1448 1448 1448 1448 1448 14

2008 1702 1137 399 -3 9 9 -1 1 3 7 -1 7 0 2 -2 0

1892 783 -7 8 3 -1 8 9 2 -1 8 9 2 -7 8 3 783 18

1702 -3 9 9 -2 0 0 8 -1 1 3 7 1137 2008 399 -1 7

1448 -1 4 4 8 -1 4 4 8 1448 1448 -1 4 4 8 -1 4 4 8 14

1137 -2 0 0 8 399 1702 -1 7 0 2 -3 9 9 2008 -1 1

783 -1 8 9 2 1892 -7 8 3 -7 8 3 1892 -1 8 9 2 78

hapter 18, Slide 9 Dr. Nai
 Block-based DCT and IDCT in C
 The most straightforward way of implementing a DCT and
an IDCT is to use the 1-D DCT and IDCT.
 The following C code shows how to translate the 1-D
equations for the DCT and IDCT into C code.
 The program also takes into account the numerical issues
associated with fixed-point processors.

hapter 18, Slide 10 Dr. Nai

 Implementation Issues
(1) The program runs on the DSK with the C6711 and does not use any communication with the host.
(2) The scenary.h file is quite large (256x256 8-bit pixels or 65536 bytes) and therefore needs to be located in a
specific memory location in the DSK. By using the #pragma DATA_SECTION (…) directive the picture can be
located in the DRAM (origin address 0x0800 0000).
(3) For example, #pragma DATA_SECTION (image_in, “ext_sdram”) allows the image_in data array to be
loaded into the section called “ext_sdram” which is defined in the command file. The same applies to image_out.
(4) The directory:
..\ Chapter 18 - Discrete Cosine transform\DCT_C_Fixed
contains the entire source and executable files required. The program can be loaded into the DSK and by using the
display feature of the CCS as shown below the contents of image_in and image_out can be displayed and
compared.

hapter 18, Slide 11 Dr. Nai

 Implementation Issues

Graph properties for image_in image_in

Graph properties for image_out image_out

hapter 18, Slide 12 Dr. Nai
 DCT Code and Links
 Code location:
 …\Chapter 18 - Discrete Cosine transform\DCT_C_Fixed

 Projects:
 Fixed Point in C language: dct_c_fixed.pjt

 Links:
 \Links\Imaging [Link]

hapter 18, Slide 13 Dr. Nai

 Chapter 18
Discrete Cosine Transform
- End -