COL783: Digital Image Processing
Image Compression
Prem Kalra
pkalra@cse.iitd.ac.in
h4p://www.cse.iitd.ac.in/~pkalra/col783
Department of Computer Science and Engineering
Indian InsEtute of Technology Delhi
Recap
Some definitions Compression techniques
• Compression ratio • Loss-less and Lossy
• Fidelity criteria • Symmetric and Asymmetric
Data Redundancy Variable length coding
• Coding • Huffman Coding
• Interpixel • Information theoretic analysis
• Psychovisual Entropy
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Kraft’s inequality
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Lower Bound
Shannon’s Coding Theorem
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Lower Bound
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Efficiency of Huffman Coding
H(z)/L(z)
Variants of Huffman Coding
• Higher order estimate of entropy
• Truncated Huffman Coding
• Dynamic or Adaptive Huffman Coding
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Arithmetic Coding
Basic Idea:
a) Like Huffman coding requires prior knowledge of probabiliEes
b) Unlike Huffman coding, which assigns variable length codes to symbols arithmeEc
coding assigns codes to a variable group of symbols i.e. the message.
c) There is no one-to-one correspondence between the symbol and its
corresponding code word.
d) The code word itself defines a real number within the half-open interval [0,1) and
as more symbols are added, the interval is divided into smaller and smaller
subintervals, based on the probabiliEes of the added symbols.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Arithmetic Coding
End of message or length of message is known.
Source: Digital Image Processing, Gonzalez and Woods.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Arithmetic Coding
Final code 068
Source: Digital Image Processing, Gonzalez and Woods.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Arithmetic Decoding
Follows encoding procedure
Code 068 may be converted to the real number 0.068, which falls in the
first sub-interval [0,0.2) therefore first symbol is a1, and so on.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods
• Compressing mulEple strings can be more efficient than
compressing single symbols only (e.g. Huffman encoding).
• Strings of symbols are added to a dicEonary. Later occurrences
are referenced.
• StaEc dicEonary: Entries are predefined and constant according
to the applicaEon of the text
• AdapEve dicEonary: Entries are taken from the text itself and
created on-the-fly
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZ77
By Lempel and Ziv in 1977 about lossless compression with an adapEve
dicEonary.
• Runs through the text in a sliding window
• Two buffers are used - search (history) buffer and a look ahead buffer.
• The search buffer is used as dicEonary
• Sizes of these buffers are parameters of the design
Source: h4p://jens.jm-s.de/comp/LZ77-JensMueller.pdf
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZ77
Look-ahead
Search
Source: h4p://jens.jm-s.de/comp/
LZ77-JensMueller.pdf
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZ77
Decoding
Source: h4p://jens.jm-s.de/comp/
LZ77-JensMueller.pdf
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZW
Extended by Welch (Lempel, Ziv and Welch)
This coding scheme has been adopted in a variety of imaging file formats, such as
the graphic interchange format (GIF), tagged image file format (TIFF) and the
portable document format (PDF).
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZW
Extended by Welch (Lempel, Ziv and Welch)
• Unlike Huffman coding and arithmeEc coding, this coding scheme does
not require a priori knowledge of the probabiliEes of the source
symbols.
• The coding is based on a “dicEonary” or “codebook” containing the
source symbols to be encoded. The coding starts with an iniEal
dicEonary, which is enlarged with the arrival of new symbol sequences.
• There is no need to transmit the dicEonary from the encoder to the
decoder. The decoder builds an idenEcal dicEonary during the decoding
process
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZW
Extended by Welch (Lempel, Ziv and Welch)
Example: 32 32 34 32 34 32 32 33 32 32 32 34
Consider a dicEonary of size 256 locaEons (numbered 0 to 255) that contains
entries corresponding to each pixel intensity value in the range 0-255.
Source: h4ps://nptel.ac.in/courses/117/105/117105083/#
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Dictionary based methods: LZW
Extended by Welch (Lempel, Ziv and Welch)
Source: h4ps://
nptel.ac.in/courses/
117/105/117105083/#
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Run Length Coding
Run: a string of the same symbol
Example
input: AAABBCCCCCCCCCAA
output: A3B2C9A2
compression ratio = 16/8 = 2
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Predictive Coding
Basic premise: Current pixel is similar to the previous pixel
(coherence)
Differential Coding
d(x,y) = I(x,y) – I(x-1,y)
d(x,y) prediction error which is to be encoded.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Predictive Coding
Compression
Source: Digital Image Processing, Gonzalez and Woods.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Predictive Coding
Decompression
Source: Digital Image Processing, Gonzalez and Woods.
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
Image Compression
Predictive Coding
Digital Image Processing http://www.cse.iitd.ac.in/~pkalra/col783
