12/3/2013
Advance Transform Techniques
Course Code: ECE408
Where are we?
Introduction to Subject, Signal & System
Fourier Series, Fourier Transform & Its Limitations
Short Time Fourier Transform & its Limitations, with MATLAB
Image Compression and Coding Window Functions, with MATLAB
Fractional Fourier Transform
Introduction to Wavelet
Haar Wavelet
Daubechies Wavelet
Wavelet Packet Analysis
Nikesh Bajaj M-Band Wavelets
DWT and Filter bank
[email protected] jaj
Denoising, Coding and
Electronics & Communication Dept. Other Transforms
1
2 Nikesh Bajaj
Overview
Ba Motivation
Huffman codes Compression??
Run Length coding Why?
sh
JPEG Coding Types
ITU T.81 Algos
Quantization, A-law and -law
EZW coding
ke
3 By: Nikesh Bajaj 4 Nikesh Bajaj
Ni
Huffman Coding Huffman Algorithm
By
Nik
esh
Baj
5 By: Nikesh Bajaj aj6
1
12/3/2013
Huffman Coding Huffman Coding
Computation VLC
Huffman Code of given symbols
Code is not unique
Encoded Message
Entropy H(x) = - P(xi) log2 (P(xi)) Efficiency near to 1
Average Length R = ni P(xi) Prefix Code
Efficiency = R/H
Loss less Coding
Example x = [A B C D E]
P(x) = [0.5 0.2 0.1 0.05 0.15]
jaj
Message M = ABABDBABEC
7 Nikesh Bajaj 8 Nikesh Bajaj
Run Length Coding
Ba Image Compression
It is used when long sequence of Ones and Zeros Image: dpi 4x4 image
comes in the signal Redundancy?
Example Spatial Correlation
sh
0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 Spectral Correlation
Temporal Correlation
(7) (0) (3) (1) (6) (0) (0)
Or
11111111111111100000000000000000001111
ke
(15,1), (19,0), (4,1)
(01111,1) , (10011,0), (00100,1)
9 Nikesh Bajaj 10 By: Nikesh Bajaj
Ni
RGB to YCrCb RGB image
By: Nikesh Bajaj 11
2
12/3/2013
Transform Coding
Aim of Transforming
To create a representation for the data in which
there is less correlation among the coefficient
value
To have a representation in which it is possible
to quantize different coordinates with different
precision
jaj
By: Nikesh Bajaj 13
14 By: Nikesh Bajaj
Transform Coding
Ba What transform should have??
Properties of Transform
sh
Fourier Transform??
Spectral correlation but time?
STFT or
Wavelet Transform by Best Basis Selection process
ke
16 By: Nikesh Bajaj
Ni
JPEG: Still Image Compression
Image Compression Standard Standard
JPEG: Joint Photographic Experts Group
Formally: ISO/IEC JTC1/SC29/WG1
Working Group 1
International
(JBIG,JPEG)
organization for
Standardization Joint ISO/IEC
Technical Sub-committee 29
International Committee (Coding of Audio,
Electro-technical (Information Picture, Multimedia
Commission Technology) and Hypermedia
information
Work commenced in mid-1980s.
Draft international standard 1991.
Widely used for image exchange, WWW, and digital photography.
17 By: Nikesh Bajaj
3
12/3/2013
JPEG:Encoder and Decoder JPEG:Basic Algorithm
jaj
JPEG: Image Partitioning
Ba
JPEG: Quantization Table
sh
ke
Ni
JPEG: Differential coding of DC DCT of an Image
By: Nikesh Bajaj 24
4
12/3/2013
jaj
By: Nikesh Bajaj 25 By: Nikesh Bajaj 26
JPEG: Example Ba
JPEG: Example
sh
ke
Ni
JPEG: Example
JPEG: Example
The DC coefficient is DPCM coded (difference
between the DC coefficient of the previous block
and current block)
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)
5
12/3/2013
JPEG: Decoding JPEG: Decoding
jaj
JPEG: Original Vs reconstructed
Image
Ba JPEG: Example
sh
ke
Ni
Image Compression JPEG ITU T.81 Standard
Different coding
8x8 block
artifacts
35 By: Nikesh Bajaj 36 By: Nikesh Bajaj
6
12/3/2013
Quantization Quantization
jaj
37 Nikesh Bajaj 38 By: Nikesh Bajaj
Uniform Quantizer
Ba Uniform & Nonuniform Q
Subband Uniform quantization
Uniform Dead zone quantization
sh
ke
39 By: Nikesh Bajaj 40 By: Nikesh Bajaj
Ni
Mid-tread & Mid Rise A-Law & -Law
41 Nikesh Bajaj 42 Nikesh Bajaj
7
12/3/2013
A-Law & -Law Non Uniform Quatizer
A-Law
-Law
jaj
43 Nikesh Bajaj 44 By: Nikesh Bajaj
Computation
Ba EZW Coding
Step size Progressive Encoding
Quantization noise Qnois = 2 /12 Embedded Encoding
Number of levels L = 2n = (Amx-Amn)/ Any bit rate
sh
Lossy
Number of bits per sample n = log2L Lossless
EZW
1. Natural Images
2. Large coff. are more
ke
important than small
Each Pass
45 Nikesh Bajaj 46 By: Nikesh Bajaj
Ni
P +ve Significant
N ve Significant
T zerotree
Z isolated tree
47 By: Nikesh Bajaj 48 By: Nikesh Bajaj
8
12/3/2013
jaj
49 By: Nikesh Bajaj 50 By: Nikesh Bajaj
Ba
sh
ke
51 By: Nikesh Bajaj
Ni
