ECE359 SIGNAL PROCESSING FOR

MULTIMEDIA

IMAGE COMPRESSION

Prof. Fatma Newagy

Prof. of Communications Engineering
Fatma_newagy@eng.asu.edu.eg
Relative Data Redundancy
• Let b and b’ denote the number of bits in two representations of the
same information, the relative data redundancy R is

R = 1-1/C

C is called the compression ratio, defined as

C = b/b’

e.g., C = 10, the corresponding relative data redundancy of the larger

representation is 0.9, indicating that 90% of its data is redundant
Why do we need compression?
• Data storage

• Data transmission
How can we implement compression?
Three principal types of data redundancies:
• Coding redundancy
Most 2-D intensity arrays contain more bits than are
needed to represent the intensities

• Spatial and temporal redundancy

Pixels of most 2-D intensity arrays are correlated
spatially and video sequences are temporally correlated

• Irrelevant information
Most 2-D intensity arrays contain information that is
ignored by the human visual system
Examples of Redundancy
Coding Redundancy

The average number of bits required to represent each pixel is

L −1
Lavg =  l (rk ) pr (rk ) = 0.25(2) + 0.47(1) + 0.24(3) + 0.03(3) = 1.81bits
k =0

8
C=  4.42
1.81
R = 1 − 1/ 4.42 = 0.774
Spatial and Temporal Redundancy
1. All 256 intensities are equally probable.
2. The pixels along each line are identical.
3. The intensity of each line was selected randomly.
Spatial and Temporal Redundancy
1. All 256 intensities are equally probable.
2. The pixels along each line are identical.
3. The intensity of each line was selected randomly.
Run-length pair specifies the start of a new intensity and the
number of consecutive pixels that have that intensity.
Each 256-pixel line of the original representation is replaced
by a single 8-bit intensity value and length 256 in the run-length
representation.

The compression ratio is

256  256  8
= 128 :1
(256 + 256)  8
Irrelevant Information

256  256  8 / 8
= 65536 :1
Measuring Image Information

A random event E with probability P(E) is said to contain

1
I ( E ) = log = -log P( E )
P( E )
units of information.
Measuring Image Information

Given a source of statistically independent random events from a

discrete set of possible events {a1 , a2 , ..., aJ } with associated
probabilities {P(a1 ), P(a2 ), ..., P(aJ )}, the average information
per source output, called the entropy of the source
J
H = - P (a j ) log P (a j )
j =1

a j is called source symbols. Because they are statistically independent,

the source called zero − memory source.
Measuring Image Information

If an image is considered to be the output of an imaginary zero-memory

"intensity source", we can use the histogram of the observed image to
estimate the symbol probabilities of the source. The intensity source's
entropy becomes
L −1
H = - pr (rk ) log pr (rk )
k =0

pr (rk ) is the normalized histogram.

Measuring Image Information

For the fig.8.1(a),

H=
−[0.25log 2 0.25 + 0.47 log 2 0.47 + 0.25log 2 0.25 + 0.03log 2 0.03]
 1.6614 bits/pixel
Fidelity Criteria


Let f ( x, y ) be an input image and f ( x, y ) be an approximation
of f ( x, y ). The images are of size M  N .

The root - mean - square error is

2 1/2
 1 M −1 N −1
 
 
erms =   
x =0 y =0 
f ( x, y ) − f ( x, y )  
 
 MN
Fidelity Criteria

The mean - square signal - to - noise ratio of the output image,

denoted SNR ms

M −1 N −1 2
 

  
x =0 y =0 
f ( x , y ) 
SNR ms = M −1 N −1 2
 

  
x =0 y =0 
f ( x , y ) − f ( x , y ) 
RMSE = 5.17 RMSE = 15.67 RMSE = 14.17
Image Compression Models

mapper : transforms f(x,y) into a (usually nonvisual) format designed to reduce

spatial and temporal redundancy. This operation generally is reversible and may
or may not reduce directly the amount of data required to represent the image as
Run-length coding that normally yields compression in the first step of the
encoding process.
quantizer : reduces the accuracy of the mapper’s output in accordance with
a pre-established fidelity criterion. The goal is to keep irrelevant information
out of the compressed representation. This operation is irreversible. It must
be omitted when error-free compression is desired.

symbol coder : generates a fixed- or variable-length code to represent the

quantizer output and maps the output in accordance with the code. In many
cases, a variable-length code is used. The shortest code words are assigned
to the most frequently occurring quantizer output values—thus minimizing
coding redundancy. This operation is reversible.
Image Compression Standards
Some Basic Compression Methods:
Huffman Coding
Some Basic Compression Methods:
Huffman Coding

The average length of this code is

Lavg = 0.4*1 + 0.3* 2 + 0.1*3 + 0.1* 4 + 0.06*5 + 0.04*5
= 2.2 bits/pixel
Some Basic Compression Methods:
Golomb Coding
Given a nonnegative integer n and a positive integer divisor m  0,
the Golomb code of n with respect to m, denoted Gm (n), constructed
as follows:

Step 1. Form the unary code of quotient  n / m 

(The unary code of integer q is defined as q 1s followed by a 0)
Step2. Let k= log 2 m  , c = 2k − m, r = n mod m, and compute truncated
remainder r ' such that
r truncated to k -1 bits 0r c
r'=
 r + c truncated to k bits otherwise
Step 3. Concatenate the results of steps 1 and 2.
 Some Basic Compression Methods:
Golomb Coding
Step 1. Form the unary code of quotient  n / m  G4 (9) :
(The unary code of integer q is defined as
q 1s followed by a 0) 9 / 4  = 2,
the unary code is 110
Step2. Let k= log 2 m  , c = 2 k − m, r = n mod m,
and compute truncated remainder r ' such that k= log 2 4  = 2, c = 22 − 4 = 0,
r = 9 mod 4 = 1.
r truncated to k -1 bits 0rc
r'= 
 r + c truncated to k bits otherwise r ' = 01

Step 3. Concatenate the results of steps 1 and 2. G4 (9) = 11001

 Some Basic Compression Methods:
Golomb Coding
Step 1. Form the unary code of quotient  n / m  G4 (9) :
(The unary code of integer q is defined as
q 1s followed by a 0) 9 / 4  = 2,
the unary code is 110
Step2. Let k= log 2 m  , c = 2 k − m, r = n mod m,
and compute truncated remainder r ' such that k= log 2 4  = 2, c = 22 − 4 = 0,
r = 9 mod 4 = 1.
r truncated to k -1 bits 0rc
r'= 
 r + c truncated to k bits otherwise r ' = 01

Step 3. Concatenate the results of steps 1 and 2. G4 (9) = 11001

 Some Basic Compression Methods:
Golomb Coding
Step 1. Form the unary code of quotient  n / m 
(The unary code of integer q is defined as
q 1s followed by a 0)

Step2. Let k= log 2 m  , c = 2 k − m, r = n mod m,

and compute truncated remainder r ' such that G4 (7)?

r truncated to k -1 bits 0rc

r'= 
 r + c truncated to k bits otherwise

Step 3. Concatenate the results of steps 1 and 2.

Some Basic Compression Methods:
Arithmetic Coding
Some Basic Compression Methods:
Arithmetic Coding

How to encode a2a1a2a4?

Decode 0.572. The length of the message is 5.
Since 0.8>code word > 0.4, the first symbol should be a3.

1.0 0.8 0.72 0.592 0.5728

0.8 0.72 0.688 0.5856 0.57152

Therefore, the
message is
a3a3a1a2a4
0.4 0.56 0.624 0.5728 056896

0.2 0.48 0.592 0.5664 0.56768

0.0 0.4
0.56 0.56 0.5664
 LZW (Dictionary coding)

LZW (Lempel-Ziv-Welch) coding, assigns fixed-length code

words to variable length sequences of source symbols, but
requires no a priori knowledge of the probability of the source
symbols.
LZW is used in:
•Tagged Image file format (TIFF)
•Graphic interchange format (GIF)
•Portable document format (PDF)

LZW was formulated in 1984

The Algorithm:
•A codebook or “dictionary” containing the source
symbols is constructed.
•For 8-bit monochrome images, the first 256 words of
the dictionary are assigned to the gray levels 0-255
•Remaining part of the dictionary is filled with
sequences of the gray levels
 Important features of LZW

1. The dictionary is created while the data are being

encoded. So encoding can be done “on the fly”
2. The dictionary is not required to be transmitted. The
dictionary will be built up in the decoding
3. If the dictionary “overflows” then we have to reinitialize
the dictionary and add a bit to each one of the code words.
4. Choosing a large dictionary size avoids overflow, but
spoils compressions
Example:
39 39 126 126
39 39 126 126
39 39 126 126
39 39 126 126
Some Basic Compression Methods:
LZW Coding
39 39 126 126
39 39 126 126
39 39 126 126
39 39 126 126
 Decoding LZW

Let the bit stream received be:

39 39 126 126 256 258 260 259 257 126

In LZW, the dictionary which was used for encoding

need not be sent with the image. A separate dictionary
is built by the decoder, on the “fly”, as it reads the
received code words.
Recognized Encoded pixels Dic. address Dic. entry
value
39 39
39 39 39 256 39-39
39 126 126 257 39-126
126 126 126 258 126-126
126 256 39-39 259 126-39
256 258 126-126 260 39-39-126

258 260 39-39-126 261 126-126-39

39-39-126-
260 259 126-39 262
126
259 257 39-126 263 126-39-39
257 126 126 264 39-126-126
Some Basic Compression Methods:
Run-Length Coding
1. Run-length Encoding, or RLE is a technique used to reduce
the size of a repeating string of characters.

2. This repeating string is called a run, typically RLE encodes a

run of symbols into two bytes , a count and a symbol.

3. RLE can compress any type of data

4. RLE cannot achieve high compression ratios compared to

other compression methods
Some Basic Compression Methods:
Run-Length Coding

5. It is easy to implement and is quick to execute.

6. Run-length encoding is supported by most bitmap file formats

such as TIFF, BMP and PCX
Some Basic Compression Methods:
Run-Length Coding

WWWWWWWWWWWWBWWWWWWWWWWWWBBBW
WWWWWWWWWWWWWWWWWWWWWWWBWWWW
WWWWWWWWWW

RLE coding:

12W1B12W3B24W1B14W