9/5/2013
Information Theory and Coding
ECE533
Overview
! Source Coding Techniques
Huffman Coding
Source Coding !
jaj
! Run Length
! Lempel-ziv
! Arithmetic
! Shannon-Fano
Nikesh Bajaj
nikesh.14730@[Link] ! Source Coding Theorem
Asst. Prof., ECE Dept.
Digital Signal Processing
! JPEG: Image Compression
Lovely Professional University 2 By Nikesh Bajaj
Source Coding
! Source Coding
! Aim ??
Ba !
!
!
Huffman Coding
David A. Huffman
August 9, 1925 – October 7, 1999
Ohio State University, MIT
sh
! X xi
! 1952 paper "A Method for the Construction of
Minimum-Redundancy Codes"
! Minimum number of bits that completely
represent the symbol.
3 By Nikesh Bajaj 4 By Nikesh Bajaj
ke
Huffman Coding Huffman Coding
Ni
! Algorithm
5 By Nikesh Bajaj 6 By Nikesh Bajaj
1
9/5/2013
Huffman Algorithm Source coding
! Observed Parameters
! Entropy H
jaj
! Average Length R
! Efficiency of the code !
! Classification of Source coding
! Fixed Length and Variable Length Coding
! Lossless and Lossy Compression.
! Prefix Code or Instantaneous Codes
7 By Nikesh Bajaj 8 By Nikesh Bajaj
Examples
Symbol
x1
x2
x3
Probability
0.37
0.33
0.16
Self-Information
1.4344
1.5995
2.6439
Code word
0
10
110
Ba Huffman Coding
!
!
VLC
Code is not unique
Efficiency near to 1
sh
x4 0.07 3.8365 1110
x5 0.04 4.6439 11110 ! Prefix Code
x6 0.02 5.6439 111110
! Loss less Coding
x7 0.01 6.6439 111111
H(X)=2.1152
R=2.1700
N=H/R=2.1152/2.1700=0.9747
9 By Nikesh Bajaj 10 By Nikesh Bajaj
ke
Problems Problem
Ni
! DAP for Huffman algorithm. Symbol Probability Self-Information Codeword
x1 0.5 1 1
! Take a page of english charactors and x2 0.3 1.737 00
compress it using Huffman algorithm then x3 0.2 2.3219 01
check all the quantitive parameters i.e. H, R,
! H(X)=1.4855, R =0.9903, !=0.9903
efficiency.
! Group two symbols, and calculate same
11 By Nikesh Bajaj 12 By Nikesh Bajaj
2
9/5/2013
Run Length Coding Run length Coding
! It is used when long sequence of Ones and Zeros ! FLC
comes in the signal
Loss less Coding
jaj
!
Example
! Good for certain applications only
! “ 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1”
! (7) (0) (3) (1) (6) (0) (0)
Or
! 11111111111111100000000000000000001111
! (15,1), (19,0), (4,1)
! (01111,1) , (10011,0), (00100,1)
13 By Nikesh Bajaj 14 By Nikesh Bajaj
!
Lemple-Ziv Algorithm (LZW) 1977
No need of symbol probability
Huffman is good for DMS, not for source with memory
No statistics require,
Ba !
!
Lemple-Ziv Algorithm (LZW) 1977
Lets consider
101011011010101011
Dict.
Location
000
001
Dict.
Content
1
-
FL-
Codeword
0001
sh
010 0 0000
011 10 0010
100 11 0011
101 01 0101
110 101 0111
111 010 1010
Abraham Lempel Jacob Ziv Terry A. Welch
- 1011 1101
15 By Nikesh Bajaj 16 By Nikesh Bajaj
ke
Lemple-Ziv Algorithm Source Coding Theorem
Ni
! .H ( X ) # R # H ( X ) " 1
! Proof:
!
17 By Nikesh Bajaj 18 By Nikesh Bajaj
3
9/5/2013
Arithmetic Coding
! +
! P(A) = 0.5 P(B) = P(C) = 0.25
jaj
! Msg = BACA
19 By Nikesh Bajaj 20 By Nikesh Bajaj
Problems: Encoding
!
!
P(1) = ¾ P(0) = ¼
Msg = 110101011010101…
Ba Problem: Decoding
!
!
P(A) =0.5 P(B) =0.2 P(C) =0.3
Code =0.21625
sh
21 By Nikesh Bajaj 22 By Nikesh Bajaj
ke
Image Compression
Image: dpi 4’x4’ image
Ni
! Redundancy?
! Spatial Correlation
! Spectral Correlation
! Temporal Correlation
By: Nikesh Bajaj
23 By Nikesh Bajaj 24
4
9/5/2013
RGB to YCrCb RGB image
jaj
25 By: Nikesh Bajaj
Ba YIQ or YUV color models
(Examples)
original
Y
sh
U V
27 By: Nikesh Bajaj
ke
Examples Comparison Example-1
Ni
Y : Luminance
Cb: Chrominance
Cr: Chrominance
5
9/5/2013
Comparison Example-2
Transform Coding
! Aim of Transforming
! To create a representation for the data in which
jaj
there is less correlation among the coefficient
value
! To have a representation in which it is possible
to quantize different coordinates with different
precision
By: Nikesh Bajaj
32
Transform Coding
Ba !
!
JPEG: Still Image Compression
Standard
JPEG: “Joint Photographic Experts Group”
Formally: ISO/IEC JTC1/SC29/WG1
International
organization for
Joint ISO/IEC
Working Group 1
(JBIG,JPEG)
sh
Standardization
Technical Sub-committee 29
International Committee (Coding of Audio,
Electro-technical (Information Picture, Multimedia
Commission Technology) and Hypermedia
information
! Work commenced in mid-1980’s.
! Draft international standard 1991.
! Widely used for image exchange, WWW, and digital photography.
ke
Image Compression Standard JPEG:Encoder and Decoder
Ni
By: Nikesh Bajaj
35
6
9/5/2013
JPEG: Image Partitioning JPEG:Basic Algorithm
jaj
JPEG: Quantization Table
Ba JPEG: Differential coding of DC
sh
ke
Entropy Coding for AC Comp. Image Compression
Run Length
Ni
! ! Introduction to image compression
! Huffman ! DCT Transform
N *1 M *1
) -k & ) -l &
y(k , l ) + ,, 4 I (i, j ) cos' (2i * 1) $ cos' (2 j * 1) $
i +0 j +0 ( 2N % ( 2M %
! JPEG standard
! For Lossless Compression
! For Lossy Compression
41 By Nikesh Bajaj 42 By Nikesh Bajaj
7
9/5/2013
DCT of an Image DCT
jaj
43 By: Nikesh Bajaj 44 By: Nikesh Bajaj
DCT of an Image
DCT
0
0
Ba 250
200
150
JPEG: Example
sh
100
0
50
45 By: Nikesh Bajaj
ke
JPEG: Example JPEG: Example
Ni
8
9/5/2013
JPEG: Decoding
JPEG: Example
! The DC coefficient is DPCM coded (difference
between the DC coefficient of the previous block
and current block)
jaj
! The AC coefficients are mapped to run-length
pairs: (run,value)
(0,5),(0, -3),(0, -1),(0,- 2),(0, -3),(0,1),
(0,1),(0, -1),(0, -1),(2,1),(0,2),(0,3),(0, -2),
(0,1),(0,1),(6,1),(0,1),(1,1), EOB
! These are then Huffman coded (codes are
specified in the JPEG scheme)
JPEG: Decoding
Ba JPEG: Original Vs reconstructed
Image
sh
ke
JPEG:
Example Image Compression
Ni
By: Nikesh Bajaj
54
9
9/5/2013
JPEG ITU T.81 Standard Shannon Fano-Elias Coding
! Different coding ! Pdf
! 8x8 block ! Cdf
jaj
! artifacts
By: Nikesh Bajaj
55 56 By Nikesh Bajaj
! Sym
Shannon Fano-Elias Coding
Prob F(x) F(x) F(x)bin l(x) codeword
Ba ! Sym
Shannon Fano-Elias Coding
Prob F(x) F(x) F(x)bin l(x) codeword
sh
! x1 ½ ! x1 ½ 0.5 0.25 0.01 2 01
! x2 ½^2 ! x2 ½^2 0.75 0.625 0.101 3 101
! x3 ½ ^3 ! x3 ½ ^3 0.875 0.8125 0.1101 4 1101
! x4 ½^ 4 ! x4 ½^ 3 1 0.9375 0.1111 4 1111
57 By Nikesh Bajaj 58 By Nikesh Bajaj
ke
Ni
10