Digital Image Processing
Image Compression
Mohamed N. Ahmed, Ph.D.
Software Research
Digital Image Processing
Image Compression
• Everyday an enormous amount of information is stored,
processed, and transmitted 100
80
60
East
• Financial data 40
West
• Reports 20 North
0
• Inventory 1st Qtr 2nd 3rd Qtr4th Qtr
Qtr
• Cable TV
• Online Ordering and tracking
Software Research
Digital Image Processing
Image Compression
• Because much of this information is graphical or pictorial in nature, the
storage and communications requirements are immense.
• Image compression addresses the problem of reducing the amount of data
requirements to represent a digital image.
• Image Compression is becoming an enabling technology: HDTV.
• Also it plays an important role in Video Conferencing, remote sensing, satellite
TV, FAX, document and medical imaging.
Software Research
Digital Image Processing
Image Compression
• We want to remove redundancy from the data
• Mathematically
2D array Statistically
Transformation Uncorrelated data
Of pixels
Software Research
Digital Image Processing
Day4 : Image Compression
Outline:
1. Fundamentals
Coding Redundancy
Interpixel Redundancy
Psychovisual Redundancy
Fidelity Criteria
2. Error-Free Compression
Variable-length Coding
LZW Coding
Predictive Coding
3. Lossy Compression
Transform Coding
Wavelet Coding
4. Image Compression Standards
Software Research
Digital Image Processing
Fundamentals
• The term data compression refers to the process of reducing the
amount of data required to represent a given quantity of information
• Data Information
• Various amount of data can be used to represent the same information
• Data might contain elements that provide no relevant information :
data redundancy
• Data redundancy is a central issue in image compression. It is not an
abstract concept but mathematically quantifiable entity
Software Research
Some Images are adopted from R. C. Gonzalez & R. E. Woods
Digital Image Processing
Data Redundancy
• Let n1 and n2 denote the number of information carrying units in two
data sets that represent the same information
• The relative redundancy RD is define as :
1
RD 1
CR
where CR, commonly called the compression ratio, is
n1
CR
n2
Software Research
Digital Image Processing
Data Redundancy
• If n1 = n2 , CR=1 and RD=0 no redundancy
• If n1 >> n2 , CR and RD 1 high redundancy
• If n1 << n2 , CR 0 and RD undesirable
• A compression ration of 10 (10:1) means that the first data set has 10
information carrying units (say, bits) for every 1 unit in the second
(compressed) data set.
• In Image compression , 3 basic redundancy can be identified
» Coding Redundancy
» Interpixel Redundancy
» Psychovisual Redundancy
Software Research
Digital Image Processing
Coding Redundancy
• Recall from the histogram calculations
h(rk ) nk
p(rk )
n n
where p(rk) is the probability of a pixel to have a certain
value rk
If the number of bits used to represent rk is l(rk), then
L 1
Lav l (rk )( p(rk )
k 0
Software Research
Digital Image Processing
Coding Redundancy
• Example:
7
Lav l (rk )( p(rk )
k 0
2(019) 2(0.25) 3(0.16) ... 6(0.02)
2.7 bits
3
C R 1.11
2
1
RD 1 0.099
1.11
Software Research
Digital Image Processing
Coding Redundancy
Variable-Length
Coding
Software Research
Digital Image Processing
Inter-pixel Redundancy
Here the two pictures have
Approximately the same
Histogram.
We must exploit Pixel
Dependencies.
Each pixel can be estimated
From its neighbors.
Software Research
Digital Image Processing
Run-Length Encoding
Example of Inter-pixel
Redundancy removal
Software Research
Digital Image Processing
Psycho-visual Redundancy
The human visual system is more
sensitive to edges
Middle Picture:
Uniform quantization from 256 to
16 gray levels
CR= 2
Right picture:
Improved gray level quantization
(IGS)
CR= 2
Software Research
Digital Image Processing
Fidelity Criteria
The error between two functions is given by:
e( x, y ) f ( x, y ) f ( x, y )
So, the total error between the two images is
M 1 N 1
[ f ( x, y) f ( x, y)]
x 0 y 0
The root-mean-square error averaged over the whole image is
1
erms [ f ( x, y ) f ( x, y )]2
MN
Software Research
Digital Image Processing
Fidelity Criteria
• A closely related objective fidelity criterion is the mean
square signal to noise ratio of the compressed-
decompressed image
M 1 N 1
x 0 y 0
f ( x, y ) 2
SNRms
M 1 N 1
[ f ( x
x 0 y 0
, y ) f ( x , y )] 2
Software Research
Digital Image Processing
Fidelity Criteria
Software Research
Digital Image Processing
Compression Model
The source encoder is responsible for removing redundancy
(coding, inter-pixel, psycho-visual)
The channel encoder ensures robustness against channel noise.
Software Research
Digital Image Processing
Compression Types
Compression
Error-Free Compression
Lossy Compression
(Loss-less)
Software Research
Digital Image Processing
Error-Free Compression
• Some applications require no error in compression
(medical, business documents, etc..)
• CR=2 to 10 can be expected.
• Make use of coding redundancy and inter-pixel
redundancy.
• Ex: Huffman codes, LZW, Arithmetic coding, 1D
and 2D run-length encoding, Loss-less Predictive
Coding, and Bit-Plane Coding.
Software Research
Digital Image Processing
Huffman Coding
• The most popular technique for removing coding
redundancy is due to Huffman (1952)
• Huffman Coding yields the smallest number of code
symbols per source symbol
• The resulting code is optimal
Software Research
Digital Image Processing
Huffman Codes
Software Research
Digital Image Processing
Huffman Codes
Lavg 1(0.4) 2(0.3) 3(0.1) 4(0.1) 5(0.06) 5(0.04)
2.2 bits
Software Research
Digital Image Processing
Workshop
Obtain the Huffman codes for the following sequence:
– 5555884277722224477772222222222
222222444
– What is the average code length with and without
compression ?
Software Research
Digital Image Processing
Fixed Length: LZW Coding
• Error Free Compression Technique
• Remove Inter-pixel redundancy
• Requires no priori knowledge of probability distribution of
pixels
• Assigns fixed length code words to variable length
sequences
• Patented Algorithm US 4,558,302
• Included in GIF and TIFF and PDF file formats
Software Research
Digital Image Processing
LZW Coding
• Coding Technique
– A codebook or a dictionary has to be constructed
– For an 8-bit monochrome image, the first 256 entries are assigned
to the gray levels 0,1,2,..,255.
– As the encoder examines image pixels, gray level sequences that
are not in the dictionary are assigned to a new entry.
– For instance sequence 255-255 can be assigned to entry 256, the
address following the locations reserved for gray levels 0 to 255.
Software Research
Digital Image Processing
LZW Coding
• Example
Dictionary Location Entry
Consider the following 4 x 4 8 bit image
0 0
39 39 126 126
1 1
39 39 126 126 . .
39 39 126 126 255 255
256 -
39 39 126 126
511 -
Initial Dictionary
Software Research
Digital Image Processing
LZW Coding
39 39 126 126
39 39 126 126
•Is 39 in the dictionary……..Yes
39 39 126 126 •What about 39-39………….No
39 39 126 126 •Then add 39-39 in entry 256
•And output the last recognized symbol…39
Dictionary Location Entry
0 0
1 1
. .
255 255
256 -
39-39
511 -
Software Research
Digital Image Processing
Workshop
• Code the following image using LZW codes
39 39 126 126
39 39 126 126
39 39 126 126
39 39 126 126
* How can we decode the compressed sequence to obtain the original image ?
Software Research
Digital Image Processing
LZW Coding
Software Research
Digital Image Processing
Bit-Plane Coding
• An effective technique to reduce inter pixel redundancy is
to process each bit plane individually
• The image is decomposed into a series of binary images.
• Each binary image is compressed using one of well known
binary compression techniques.
Software Research
Digital Image Processing
Bit-Plane Decomposition
Software Research
Digital Image Processing
Bit-Plane Encoding
Constant Area Coding
One Dimensional Run Length coding
1b 2w 1b 3w 4b 1w
Two Dimensional Run Length coding
12 w
Software Research
Digital Image Processing
Loss-less Predictive Encoding
Software Research
Digital Image Processing
Loss-less Predictive Encoding
Software Research
Digital Image Processing
Lossy Compression
Quantizer
Software Research
Digital Image Processing
Lossy Compression
Software Research
Digital Image Processing
DPCM
Software Research
Digital Image Processing
DPCM
Software Research
Digital Image Processing
Transform Coding
• A reversible linear transform (such as Fourier
Transform) is used to map the image into a set of
transform coefficients
• These coefficients are then quantized and coded.
• The goal of transform coding is to decorrelate
pixels and pack as much information into small
number of transform coefficients.
• Compression is achieved during quantization not
during the transform step
Software Research
Digital Image Processing
Transform Coding
Software Research
Digital Image Processing
2D Transforms
• Energy packing
– 2D transforms pack most of the energy
into small number of coefficients located
at the upper left corner of the 2D array
Energy
Packing
Software Research
Digital Image Processing
2D Transforms
• Consider an image f(x,y) of size N x N
Forward transform
N 1 N 1
T (u, v) f ( x, y ) g ( x, y, u, v)
x 0 y 0
u, v 0, 1, 2,..., N 1.
g(x,y,u,v) is the forward transformation kernel or basis functions
Software Research
Digital Image Processing
2D Transforms
• Inverse transform
N 1 N 1
f ( x, y ) T (u, v)h( x, y, u, v)
u 0 v 0
x, y 0, 1, 2,..., N 1.
h(x,y,u,v) is the inverse transformation kernel or basis functions
Software Research
Digital Image Processing
Discrete Cosine Transform
• One of the most frequently used
transformations for image compression is
the DCT.
g ( x, y , u , v ) h ( x, y , u , v )
(2 x 1)u (2 y 1)v
(u ) (v) cos cos 2N
2N
1 for u=0
N
(u )
2 for u=1, 2, …, N-1
N
Software Research
Digital Image Processing
Discrete Cosine Transform
Software Research
Digital Image Processing
2D Transforms
Software Research
Digital Image Processing
Effect of Window Size
Software Research
Digital Image Processing
Quantization
Quantizer
Software Research
Digital Image Processing
Quantization
• Each transformed coefficient is quantized
ˆ T (u, v)
T (u, v) round
Z (u, v)
Software Research
Digital Image Processing
Quantization
Software Research
Digital Image Processing
Bit allocation and Zig Zag Ordering
Software Research
Digital Image Processing
DCT and Quantization
T (u, v)
Tˆ (u, v) round
Right Column
Z (u, v)
T (u, v)
Tˆ (u, v) round
4 Z (u , v )
Software Research
Digital Image Processing
Wavelet Coding
Software Research
Digital Image Processing
Wavelet Transform
1 2
3 4
Put a pixel in each quadrant- No size change
Software Research
Digital Image Processing
Wavelet Transform
a b
c d
• Now let
» a = (x1+x2+x3+x4)/4
» b =(x1+x2-x3-x4)/4
» c =(x1+x3-x2-x4)/4
» d =(x1+x4-x2-x3)/4
a 1 1 1 1 x1 x1 1 1 1 1 a
b 1 1 1 1 x 2 x 2 1 1 1 1 b
1
c 4 1 1 1 1 x3 x3 1 1 1 1 c
d 1 1 1 1 x 4
x 4 1 1 1 1 d
Software Research
Digital Image Processing
Wavelet Transform
Software Research
Digital Image Processing
Wavelet Transform
Software Research
Digital Image Processing
Wavelet Transform
Software Research
Digital Image Processing
Wavelet Coding
• High Frequency coefficients tend to be very
small --- 0
• They can be quantized very effectively
without distorting the results
Software Research
Digital Image Processing
Wavelet Transform
Wavelet DCT
Software Research
Digital Image Processing
Wavelet Transform
Software Research
Digital Image Processing
Image Compression Standards
• Binary Compression Standards
• CCITT G3 -> 1D Run Length Encoding
• CCITT G4 -> 2D Run Length encoding
• JBIG1 -> Lossless adaptive binary compression
• JBIG2 -> Lossy/Lossless adaptive binary
compression
Software Research
Digital Image Processing
JBIG/JBIG2
Software Research
Digital Image Processing
Image Compression Standards
• Continuous Tone Still Image Compression
Standards
• JPEG
• JPEG 2000
• Mixed Raster Content (MRC)
Software Research
Digital Image Processing
MRC
Software Research
Digital Image Processing
Video Compression
Software Research