DCT Image Compression: D. Bhavsingh EC94001 M.Tech, E.I

DCT Image Compression
D. BHAVSINGH
EC94001
M.TECH ,E.I
What is Compression?
• The goal of image compression is to reduce the amount of data

required to represent a digital image.
• i.e., remove redundant data
• Image compression is very important for image storage and image

transmission.
Why Transform ?
• the transform throws away correlations
• if you make a plot of the value of a pixel as a function of one of its
neighbors
• you will see that the pixels are highly correlated (i.e. most of the
time they are very similar)
• this is just a consequence of the fact that surfaces are smooth
Contd..
• the transform eliminates these correlations
• – this is best seen by considering the 2-pt transform
• – note that the first coefficient is always the DC-value
• X[0]= x[0]+ x[1]
• an orthogonal transform can be written in matrix form as
• – i.e. T has orthogonal columns
• this means that

THE DISCRETE COSINE TRANSFORM
• the Discrete Cosine Transform (DCT) attempts to decorrelate the

image data
• decorrelation each transform coefficient can be encoded
independently without losing compression efficiency
• important properties.
• One-Dimensional DCT
• Two-Dimensional DCT
JPEG Compression
(Sequential DCT-based encoding)
DCT
• Forward
• Inverse
Lossy Image Compression (JPEG)
Block-based Discrete Cosine Transform (DCT)

THE DCT MATRIX
• the matrix form of Equation (1), we will use the following equation
• 8x8 block it results in this matrix

DCT ON AN 8x8 BLOCK
• the pixel values of a black-and-white image range from 0 to

255
• Pure black is represented by 0,
• Pure white by 255
• This particular block was chosen from the very upper- left-hand
corner of an image
• the DCT is designed to work on pixel values ranging from -128 to
127
• the original block is “leveled off“ by subtracting 128 from each
entry.
• This results in the following matrix
• The discrete Cosine Transform, is accomplished by matrix
multiplication
D = TMT’-----(5)
• This block matrix now consists of 64 DCT coefficients

c (i, j) i and j range from 0 to 7
QUANTIZATION
8x8 block of DCT coefficients is compression by quantization
Its decide on quality levels ranging from 1 to 100,

• 1 gives the poorest image quality and highest compression,
• 100 gives the best quality and lowest compression
• Quantization is achieved by dividing each element in the
transformed image matrix D by corresponding element in the
quantization matrix
CODING
• Before storage, all coefficients of C are converted by an encoder to a
stream of binary data (01101011...).
• JPEG takes advantage of this by encoding quantized coefficients in
the zig-zag sequence
DECOMPRESSION:
• Reconstruction of our image begins by decoding the bit stream

representing the Quantized matrix C.
R i, j =Q i, j ×C i, j
The IDCT is next applied to matrix R, which is rounded to the nearest

integer. Finally, 128 is added to each element of that result, giving us
the decompressed JPEG version N of our original 8x8 image block M
Lossy DCT Image Compression
•The lossy DCT method compression
method is widely used in current Lossless
standards. For example, JPEG images
and MPEG-1 and MPEG-2 (DVD)
videos.
Lossy
•As we can see here, heavily DCT-
compressed images contain blocking
artefacts. Ringing artefacts can also be
seen around edges.
Rate/Distortion
•As we have seen, quality can fall rapidly a) Original b) DCT : QF 3 : CR 8:1
as shown by the steep slope of rate/
distortion graph.
•DCT methods typically* work well up to c) DCT : QF 10 : CR 11.6:1 d) DCT : QF 20 : CR 13.6:1

around 10:1 compression ratios and
then quality falls rapidly beyond this.
e) DCT : QF 25 : CR 14.2:1 f) Difference a-e

DCT Compression
DCT QF 3 image (CR=8:1)

DCT Compression
DCT QF 15 image (CR=12:1)

DCT Compression
DCT QF 25 image CR=14:1

DCT Compression
•The philosophy behind DCT
image compression is that
the human eye is less
sensitive to higher-frequency
information and also more
sensitive to intensity than to
colour. Original (100%) 0.5 UV (25%) 0.25 UV (6.25%)
•The examples shown here

are from Dr Flowers’ MPEG
slides showing the effects of
percentage reduction of
colour.
0.2 UV (4%) 0.1 UV (1%) 0.0 UV (0%)
•The Discrete Cosine Method uses continuous cosine waves,
like cos(x) below, of increasing frequencies to represent the
image pixels.
•The bases are the set of 64 frequencies that can be combined

to represent each block of 64 pixels.
•Firstly, the image must be transformed into the frequency

domain. This is done in blocks across the whole image.
The Discrete Cosine Transform Bases
Low frequency
High frequency
•The DCT method is an example of a transform method.
Rather than simply trying to compress the pixel values
directly, the image is first TRANSFORMED into the frequency
domain. Compression can now be achieved by more coarsely
quantizing the large amount of high-frequency components
usually present.
•Firstly, the image must be transformed into the frequency

domain. This is done in blocks across the whole image.
•The JPEG* standard algorithm for full-colour and grey-scale

image compression is a DCT compression standard that uses
8x8 blocks.
•It was not designed for graphics or line drawings and is not
suited to these image types.
•The DCT itself does not achieve compression, but
rather prepares the image for compression.
•Once in the frequency domain the image's high-

frequency coefficients can be coarsely quantised so
that many of them (>50%) can be truncated to zero.
•The coefficients can then be arranged so that the

zeroes are clustered (zig-zag collection) and Run-Length
Encoded.
THE DCT MATRIX
Summary of DCT Stages
Blocking (8x8)
DCT (Discrete Cosine Transformation)
Quantization
Zigzag Scan
DPCM* on the dc value (the average value in the top left)
RLE on the ac values (all 63 values which aren’t the dc/ average)
Huffman Coding
* DPCM – Differential Pulse Code Modulation – Instead of

sending the value send the difference from the previous
value.
The DCT
•Take each 8x8 pixel block and
represent it as amounts
(coefficients) of the basis functions
(the frequency set).
• represent the 8x8 pixels as

amounts of lowest frequency
(the average or DC value)
through to the highest
frequency
• 64 pixels values are

TRANSFORMED into 64
coefficients which represent the
amount of each frequency.
DCT Mathematics
•The Discrete Cosine Transform below takes the pixels(x,y) and

generates DCT(i,j) values.
•The pixel values can be calculated as shown in the 2nd line, where
DCT(i,j) values are used to calculate pixel(x,y) values.
1 N 1 N 1
 (2 x  1)   (2 y  1) 
DCT (i, j )  C (i )C ( j ) pixel ( x, y ) cos
2N x 0 y 0  2 N   2 N 
1 N 1 N 1
 (2 x  1)   (2 y  1) 
pixel ( x, y ) 
2N

i 0 j 0
C (i ) C ( j ) DCT ( i , j ) cos  2 N   2 N 
1
C ( x)  if x is 0, else 1 if x  0
2
The Baseline JPEG Standard Quantization Matrix
- determined by subjective testing -
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
Nelson’s Simpler Linear Quantizer
The Nelson DCT implementation (this is the DCT compressor
used in the laboratory) uses a very simple linear quantization
strategy.
Q = quality or quantization factor
The higher Q the LOWER the image quality.
Where each DCT coefficient (i,j) is quantised as
For (i=0;i<N;i++)
For (j=0;j<N;j++)
quantised[i,j]=1+((1+i+j)*Q);
• For (i=0;i<N;i++) and for (j=0;j<N;j++)
• quantised[i,j]=1+((1+i+j)*Q);
Nelson Quanitizer for Q=2
3 5 7 9 11 13 15 17
5 7 9 11 13 15 17 19
7 9 11 13 15 17 19 21
9 11 13 15 17 19 21 23
11 13 15 17 19 21 23 25
13 15 17 19 21 23 25 27
15 17 19 21 23 25 27 29
17 19 21 23 25 27 29 31
Before and After Quantization
PROPERTIES OF DCT
• Decorrelation
• Energy Compaction
• Separability
• Symmetry
Thank
You

DCT Image Compression: D. Bhavsingh EC94001 M.Tech, E.I

Uploaded by

Copyright:

Available Formats

DCT Image Compression: D. Bhavsingh EC94001 M.Tech, E.I

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DCT Image Compression: D. Bhavsingh EC94001 M.Tech, E.I

Uploaded by

Copyright:

Available Formats

DCT Image Compression

• The goal of image compression is to reduce the amount of data

• Image compression is very important for image storage and image

• – i.e. T has orthogonal columns

• this means that

• the Discrete Cosine Transform (DCT) attempts to decorrelate the

Block-based Discrete Cosine Transform (DCT)

• 8x8 block it results in this matrix

• the pixel values of a black-and-white image range from 0 to

• This block matrix now consists of 64 DCT coefficients

8x8 block of DCT coefficients is compression by quantization

Its decide on quality levels ranging from 1 to 100,

• Reconstruction of our image begins by decoding the bit stream

The IDCT is next applied to matrix R, which is rounded to the nearest

•DCT methods typically* work well up to c) DCT : QF 10 : CR 11.6:1 d) DCT : QF 20 : CR 13.6:1

e) DCT : QF 25 : CR 14.2:1 f) Difference a-e

DCT QF 3 image (CR=8:1)

DCT QF 15 image (CR=12:1)

DCT QF 25 image CR=14:1

•The examples shown here

•The bases are the set of 64 frequencies that can be combined

•Firstly, the image must be transformed into the frequency

•Firstly, the image must be transformed into the frequency

•The JPEG* standard algorithm for full-colour and grey-scale

•Once in the frequency domain the image's high-

•The coefficients can then be arranged so that the

* DPCM – Differential Pulse Code Modulation – Instead of

• represent the 8x8 pixels as

• 64 pixels values are

•The Discrete Cosine Transform below takes the pixels(x,y) and

You might also like