6 Image Compression

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 45

IMAGE PROCESSING

IMAGE COMPRESSION
By
DR. FERDA ERNAWAN
Faculty of Computer Systems & Software Engineering
[email protected]

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Today’s Lesson
• Introduction to Image Compression
• General JPEG Image Compression
• Lossless & Lossy compression
• Data Redundancies
• Lossless Compression Methods
– Huffman Coding, Lossless Predictive Coding
• Lossy Compression Methods
– Block Transform Coding
• Learning Outcomes:
To understand image compression processing and the basic
operation
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Introduction
• Image compression is a method to reduce the redundancies in
image representation in order to decrease data storage
requirements (Gonzalez and Woods, 2013).
• It is a technique used to compress an image without visually
reducing the quality of the image itself.
• Data vs. Information.
• The goal of these processes is to represent an image with the
same quality level, but in a more solid form.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Why the image must be compressed?
• The large storage requirement of multimedia data.
• The video or image files consume large amount of data and it
always required very high bandwidth networks in transmission as
well as communication costs.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Aims of Image Compression
• Reduce the data storage and maintain the visual image quality (Gonzalez,
Woods and Eddins, 2017).

• Increase the speed of transmission by using the repetition property of data.

• The goal of these processes is to represent an image with the same quality
level, but in a more solid form.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
General JPEG Compression

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
General Image Compression Model
Images taken from Gonzalez & Woods, Digital Image Processing

Encoder

Decoder
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Image Compression (Encoder)

Image Image Entropy Coding


Transformati Quantizatio AC Huffman
Table
on n

Zig-zag Huffman
Reordering Coding

Color AC
Scalar
component 8x8 DCT Uniform Bit-
s (Y, Cb, Cr) Transform Quantizatio stream
n

Huffman
Difference Coding
Encoding

DC

Quantizatio DC
n Table Huffman
Table

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Block Transform Coding System

• An image is divided into 8x8 pixels of non-overlapping blocks.


• Each block is transformed by the transform function (e.g. DCT)
• Compression is achieved during the quantization of the transformed
coefficients.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
DCT Transformation
DCT of an input image A is defined as follows
M 1 N 1
 (2m  1) p  (2n  1)q
B pq   p  q   Amn cos 2M
cos
2N
,
m0 n 0

where  1  1
 ,p0  ,q  0
 M N
p   q  
 2 ,p0  2
,q  0

 M  N

The inverse of DCT is given as follows:


M 1 N 1
 (2m  1) p  (2n  1)q
Apq    p  q Bmn cos 2M
cos
2N
,
m0 n 0
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Quantization Process
The JPEG quantization are given as follows:
16 11 10 16 24 40 51 61  17 18 24 47 99 99 99 99 
12 55  18
 12 14 19 26 58 60
 21 26 66 99 99 99 99 
14 13 16 24 40 57 69 56   24 26 56 99 99 99 99 99 
   
14 17 22 29 51 87 80 62  47 66 99 99 99 99 99 99 
QCL  QCR 
18 22 37 56 68 109 103 77   99 99 99 99 99 99 99 99 
   
 24 35 55 64 81 104 113 92   99 99 99 99 99 99 99 99 
 49 64 78 87 103 121 120 101  99 99 99 99 99 99 99 99 
   
 72 92 95 98 112 100 103 99   99 99 99 99 99 99 99 99 

 c( i , j ) k 
u( i , j ) k  Round  
 Q( i , j )
 

Where c(i , j ) k is the frequency image signals at coordinates (i,j) in the


k block.
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Differential Pulse Code Modulation
(DPCM) for DC Coefficients
The DC coefficients of each block are encoded with a DPCM instead of
block-based prediction. The DC coefficients are coded by DPCM as
follows:

Diffi  DCi  DCi 1


Where DCi is the current block and DCi 1 represents the previous
block of DC coefficient.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Differential Pulse Code Modulation of DC
Coefficients
Diffi-1 = Diffi =
Diff1 = DC1 DCi-1 - DCi-2 DCi - DCi-1

DC0 DC1 ... DCi-1 DCi

0 ...

Block 1 Block i-1 Block i

Then the difference is encoded using Huffman coding together with


the encoding of AC coefficients.
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Zigzag Pattern for AC coefficients
The zigzag pattern is an important part of encoding process which gives
effect to the statistic of symbols used in entropy coding.

Zigzag order under regular of 8×8 discrete transform


OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
DCT as choice of Transform

Original Image
Compressed Image
JPEG image compression produces visible artifact image, less
computational complexity and it has a good energy compactness properties.
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Other Compression Method
• Symbol-based Coding – JBIG2 format compression for binary
images.
• LZW (Lempel-Ziv-Welch) Coding – integrated into GIF, TIFF,
PDF.
• Arithmetic Coding.
• Golomb Coding.
• Lossy Predictive Coding – DPCM (Differential pulse code
modulation).
• Wavelet Coding – Haar, Daubechies wavelets.
• JPEG-2000

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Compression Ratio (CR)
• Compression is measured in compression ratio denoted by:

Uncompressed File Size


Compressio n Ratio   CR
Compressed File Size

Example:
The original image is 256×256 pixels, 8-bits per pixel grayscale.
The file is 65536 bytes (64 kb) in size.
After compression the image file is 6554 bytes.
The compression ratio is 65536
compressio n Ratio   10
6554
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Relative Data Redundancy ()
The relative data redundancy, R can be determined as:
1
RD  1
CR
1
RD  1   0.9
10
This indicates that 90% of its data is redundant. The higher the
RD value, the more data is redundant and will be compressed. If
RD=0, (no redundant data)

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Redundancy

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Type of Redundancy
There are three types of redundancy:
• Coding redundancy
• Interpixel redundancy
• Psychovisual redundancy

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Coding Redundancy
A code is a symbol (letters, numbers, bits) used to represent a body of
information (Gonzalez and Woods, 2016). Each information is
assigned a sequence of code symbols, called a code word. The number
of symbols in each code word is its length.

Symbols with higher appearing probabilities are assigned with codes


of less amount of data.

Symbol: codes that human represent information


E.g., Chinese characters, English letters, …
Coding: transform symbols into more efficient codes
E.g., A: 00, B: 01, C: 10, …
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Coding Redundancy: Example

Average bit length (Lavg1)=3 bits, Average bit length (Lavg2)=2.7


bits, Compression ratio= 3/2.7=1.11, Relative Redundancy=0.099
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Inter-pixel Redundancy

 Also called spatial redundancy, geometric redundancy, inter-frame


redundancy.

 Results from structural or geometric relationships between objects and the


image.

 Adjacent pixels are usually highly correlated (pixel similar or very close
to neighboring pixels), thus information is unnecessarily replicated in the
representations.

 Neighboring pixels in a natural image are highly correlated. In natural


images, local area usually contains pixels of same or similar gray level.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Inter-pixel Redundancy: Example
Pixels of line 128 of Tiffany:

Pixels of line 128 of wheel:

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Inter-pixel Redundancy: Example
• Pixels of line 128 of wheel:

n1 represent data information and n2 is amounts of data to represent


the same information.
Similar segments (graylevel, Coding each segment with 16 bits:
number): (77, 1), (206, 30), CR=(256x8) / (7x16)=18.3
(121, 88), (77,18), (121, 88), RD=1-1/18.3=0.95
(206, 30), (77, 1)
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Psychovisual Redundancy
• For human visual perception, certain information has less relative
importance. E.g,: appropriate quantization of gray levels does not
impact its visual quality, e.g.,: Tiffany

Can be eliminated without significant quality loss.


Use Lossy compression or Irreversible compression.
“Quantization”.
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Information Theory

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Basic Information Theory

• Measuring amount of information: I(p) = log 1/p = – log p


– Average amount of information: entropy.
– Theoretically, the lowest average number of bits required to
represent one symbol.

H ( S )  i pi log pi

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example:

Symbol Probability
A 1/4
B 1/4 In average, minimum 2 bits required.
C 1/4
D 1/4 H (S )   (1 / 4) log 2 (1 / 4)  2

Symbol Probability
A ½
B 1/8
In average, minimum 1.75 bits required.
C 1/8
D 1/4

H (S )  (1 / 2) log 2 (1 / 2)  2(1 / 8) log 2 (1 / 8)  (1 / 4) log 2 (1 / 4)  1.75


OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Compression Method

There are two types of compression methods:


Lossy image compression
Lossless image compression

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Lossy Compression Methods
Lossy image compression methods are required to achieve high
compression ratios for complex images.
An image reconstructed Lossy compression can be performed in
both spatial or transform domains.
The process of quantization-dequantization introduces loss in the
reconstructed image and is inherently responsible for the “lossy”
nature of the compression scheme.
The quantized transform coefficient is computed by
 B pq 
T pq  Round  
Q 
 pq 
Where B pq is the frequency image signals at coordinates (i,j) in the
k block.
OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Lossy Compression Methods
During dequantization, approximate DCT coefficients are obtained by
multiplying the corresponding quantization threshold with the
quantized coefficient as follows:

B pq'  Tpq  Q pq

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Lossless Compression Methods
Lossless compression methods are needed in some digital imaging
applications, such as: medical images, x-ray images, etc.

Lossless compression techniques: run-length coding, Huffman coding,


lossless predictive coding etc.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Run-Length Encoding of AC
Coefficients
The frequency image signals after quantization process consist of
many zeros. Then, a special condition as known end-of-block
(EOB) is applied to get an efficient in the entropy code.
A symbol of EOB indicates that the rest of the coefficients in the
block are zero. Next, run-length encoding exploits the repeating
frequency image signals as the symbols in the sequence a set of the
AC coefficients.
The output of run-length encoding represents a sequence value with
the consecutive repetition as symbols and the length of occurrence
of the symbols

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Huffman Coding
■Huffmancoding is a famous method that uses variable-length
codes (VLC) tables for compressing data (Jayaraman,
Veerakumar, and Esakkirajan, 2017).

■Given a set of data symbols and their probabilities, the method


creates a set of variable-length codeword with the shortest
average length and assigns them to the symbols.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Huffman Coding (cont..)

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example I

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example I- Cont..

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example I- Cont..

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example II

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example II

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example II- Cont..

Binary coderwork tree representation


OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Example II- Cont..

Note: Log2 x = Log10 . Log2 (10) = 3.3219 Log10 x

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
Summary of Huffman Code
 Achieve minimal redundancy subject to the constraint that the
source symbols be coded one at a time.
 Sorting symbols in descending probabilities is the key in the step of
source reduction.
 The codeword assignment is not unique. Exchange the labeling of
“0” and “1” at any node of binary codeword tree would produce
another solution that equally works well.
 Only works for a source with finite number of symbols (otherwise,
it does not know where to start).

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.
References
• R.C. Gonzalez and R.E. Woods, 2016. Digital Image Processing,
Pearson Education India; Third edition.
• A.K. Jain, 2015. Fundamentals of Digital Image Processing, Pearson
Education India; First edition.
• R.C. Gonzalez, R.E. Woods and S.L. Eddins, 2017. Digital Image
Processing Using MATLAB. McGraw Hill Education; 2 edition.
• S. Jayaraman, T. Veerakumar, S. Esakkirajan, 2017.Digital Image
Processing, McGraw Hill Education; 1 edition.

OER Digital Image Processing by Ferda Ernawan (editor) work is under licensed Creative Commons Attribution-
NonCommercial-NoDerivatives 4.0 International License.

You might also like