Image Compression
Goal of Image Compression
The goal of image compression is to reduce
the amount of data required to represent a
digital image,while retaining the necessary
information.
Data ≠ Information
Data and information are not synonymous terms!
• Data is the means by which information is
conveyed.In digital images data refers to the pixel
grey level values that corresponds to the
brightness of a pixel at a point.
• Information is an interpretation of data in a
meaningful way.
Data compression aims to reduce the amount of
data required to represent a given quantity of
information while preserving as much information
as possible.
Data vs Information (cont’d)
The same amount of information can be
represented by various amount of data,
e.g.:
Ex1: Your wife, Helen, will meet you at Logan
Airport in Boston at 5 minutes past 6:00
pm tomorrow night
Ex2: Your wife will meet you at Logan Airport at 5
minutes past 6:00 pm tomorrow night
Ex3: Helen will meet you at Logan at 6:00 pm
tomorrow night
Definitions: Compression Ratio
compression
Compression ratio:uncompressed file size/compressed file size
Approaches
• Lossless
Information preserving
Low compression ratios
• Lossy
Not information preserving
High compression ratios
Trade-off: image quality vs compression ratio
Definitions: Data Redundancy
Relative data redundancy:
RD = 1-1/CR
Types of Data Redundancy
(1) Coding Redundancy
(2) Interpixel Redundancy(spatial and temporal )
(3) Psychovisual Redundancy(Irrelavent
information)
Compression attempts to reduce one or
more of these redundancy types.
Coding Redundancy
Code: a list of symbols (letters, numbers, bits
etc.)
Code word: a sequence of symbols used to
represent a piece of information or an event
(e.g., gray levels).
Code word length: number of symbols in each
code word
Coding Redundancy (cont’d)
N x M image
rk: k-th gray level Pr(rk) = nk/NxM
P(rk): probability of rk
K=0,1,2,...L-1)
l(rk): no of bits for rk
Where L is the number of gray levels
Nk is the number of times kth gray level
appears in the image.
If the image has 8bits/pixel ie 256 gray levels...but it has only 16 gray
levels ,so only actually 4bits are required . So this is suboptimal coding.
Coding Redundancy (con’d)
Case 1: l(rk) = constant length
Example:
Coding Redundancy (cont’d)
Case 2: l(rk) = variable length
Consider the probability of the gray levels:
variable length
Interpixel redundancy
Interpixel redundancy implies that any pixel value can be
reasonably predicted by its neighbors (i.e., correlated).
In order to reduce inter pixel redundancies 2D
pixel array must be transformed in to an efficient
format. For e.g difference between adjacent pixels
can be used to represent an image. These
transformations are called mappings.
Run Length Coding
The gray scale image
of size 343x1024 pixels
Binary image
= 343x1024x1 = 351232 bits
Line No. 100
Run length coding
Line 100: (1,63) (0,87) (1,37) (0,5) (1,4) (0,556) (1,62) (0,210)
Total 12166 runs, each run use 11 bits Total = 133826 Bits
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Psychovisual redundancy
The human eye does not respond with equal
sensitivity to all visual information.
It is more sensitive to the lower frequencies
than to the higher frequencies in the visual
spectrum.
Idea: discard data that is perceptually
insignificant!
The eye doesn't respond with equal sensitivity to
all visual information. Certain information has less
relative importance than other information.
This information is said to be psycho visually
redundant. This can be eliminated without
significantly impairing the quality of the image.
Psychovisual Redundancy
8-bit gray scale 4-bit gray scale 4-bit IGS
image image image
False
contours
The eye does not response with equal sensitivity to all visual
information.
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Improved Gray Scale Quantization
Pixel Gray level Sum IGS Code
i-1 N/A 0000 0000 N/A
+
i 0110 1100 0110
0110 1100
i+1 1000 1011 1001 0111 1001
i+2 1000 0111 1000 1110 1000
i+3 1111 0100 1111 0100 1111
Algorithm
1. Add the least significant 4 bits of the previous value of Sum to
the 8-bit current pixel. If the most significant 4 bit of the pixel is
1111 then add 0000 instead. Keep the result in Sum
2. Keep only the most significant 4 bits of Sum for IGS code.
Fidelity Criteria
• How close is to ?
• Criteria
– Subjective: based on human observers
– Objective: mathematically defined criteria Objective Fidelity Criterion
RMSE, PSNR
Subjective Fidelity Criterion:
Human Rating
Subjective Fidelity Criteria
Objective Fidelity crieterion :
when the information loss can be expressed as a
mathematical function of the input and output of a
compression process ,it is based on objective.
Objective Fidelity Criteria
• Root mean square error (RMS)
• Mean-square signal-to-noise ratio (SNR)
Objective Fidelity Criteria (cont’d)
RMSE = 5.17 RMSE = 15.67 RMSE = 14.17
A subjective evaluation of the
three images
Excellent rating for a
Passable rating for b
Unusable rating for c
Image Compression Models
Reduce data Increase noise
redundancy immunity
f ( x,y) Source encoder Channel encoder
Noise Channel
f^ ( x,y ) Source decoder Channel decoder
Source Encoder and Decoder Models
Source encoder
f ( x,y) Mapper Quantizer Symbol encoder
Reduce Reduce Reduce
interpixel psychovisual coding
redundancy redundancy redundancy
Source decoder
f^ ( x,y ) Inverse mapper Symbol decoder
Lossless Compression
Huffman Coding (coding redundancy)
• A variable-length coding technique.
• Symbols are encoded one at a time!
– There is a one-to-one correspondence between source symbols and
code words
• Optimal code (i.e., minimizes the number of code
symbols per source symbol).
Huffman Coding (cont’d)
• Forward Pass
1. Sort probabilities per symbol
2. Combine the lowest two probabilities
3. Repeat Step2 until only two probabilities remain.
Huffman Coding (cont’d)
• Backward Pass
Assign code symbols going backwards
Huffman Coding (cont’d)
• Lavg assuming Huffman coding:
• Lavg assuming binary codes:
Huffman Coding/Decoding
• Coding/decoding can be implemented using a look-up
table.
• Decoding can be done unambiguously.
Arithmetic (or Range) Coding
(coding redundancy)
• Sequences of source symbols are encoded together
(instead of one at a time).
• No one-to-one correspondence between source
symbols and code words.
• Slower than Huffman coding but typically achieves
better compression.
Arithmetic Coding (cont’d)
• A sequence of source symbols is assigned a single
arithmetic code word which corresponds to a sub-
interval in [0,1).
arithmetic code
α1 α2 α3 α3 α4 [0.06752, 0.0688) 0.068
• We start with the interval [0, 1) ; as the number of
symbols in the message increases, the interval used to
represent it becomes smaller.
• Smaller intervals require more information units (i.e.,
bits) to be represented.
Example
Encode
α1 α2 α3 α3 α4
[0.06752, 0.0688)
or
0.068
Arithmetic Coding
Nonblock code: one-to-one correspondence between source symbols
And code words does not exist.
Concept: The entire sequences of source symbols is assigned a single
arithmetic code word in the form of a number in an interval of real
number between 0 and 1.
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Arithmetic Coding Example
0.2x0.4 0.04+0.8x0.04 0.056+0.8x0.016
The number
between 0.0688
and 0.06752
can be used to
represent the
sequence
a1 a2 a3 a3 a4
0.2x0.2 0.04+0.4x0.04 0.056+0.4x0.016
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
Example (cont’d)
• The messageα1 α2 α3 α3 α4 is encoded using 3 decimal
digits or 3/5 = 0.6 decimal digits per source symbol.
• The entropy of this message is:
-(3 x 0.2log10(0.2)+0.4log10(0.4))=0.5786 digits/symbol
Note: finite precision arithmetic might cause problems
due to truncations!
Arithmetic Decoding
1.0 0.8 0.72 0.592 0.5728
α4
0.8 0.72 0.688 0.5856 0.57152
Decode 0.572
α3
0.4 0.56 0.624 0.5728 056896
α2
α3 α3 α1 α2 α4
0.2 0.48 0.592 0.5664 0.56768
α1
0.0 0.4
0.56 0.56 0.5664
LZW Coding (interpixel
redundancy)
Requires no prior knowledge of pixel
probability distribution values.
Assigns fixed length code words to variable
length sequences.
Included in GIF, TIFF and PDF file formats
LZW Coding
A codebook (or dictionary) needs to be
constructed.
Initially, the first 256 entries of the dictionary are assigned
to the gray levels 0,1,2,..,255 (i.e., assuming 8 bits/pixel)
Initial Dictionary
Consider a 4x4, 8 bit image Dictionary Location Entry
39 39 126 126 0 0
39 39 126 126 1
.
1
.
39 39 126 126 255 255
256 -
39 39 126 126
511 -
LZW Coding (cont’d)
As the encoder examines image pixels, gray level sequences (i.e.,
blocks) that are not in the dictionary are assigned to a new entry.
39 39 126 126
39 39 126 126
39 39 126 126
Dictionary Location Entry 39 39 126 126
0 0
1 1 - Is 39 in the dictionary? Yes
.
255
.
255
- What about 39-39? No
256 -
39-39
* Add 39-39 at location 256
511 -
Example
39 39 126 126 Concatenated Sequence: CS = CR + P
39 39 126 126 (CR) (P)
39 39 126 126
39 39 126 126
CR = empty
If CS is found:
(1) No Output
(2) CR=CS
else:
(1) Output D(CR)
(2) Add CS to D
(3) CR=P
LZW Coding
Lempel-Ziv-Welch coding : assign fixed length code words to
variable length sequences of source symbols.
24 Bits
9 Bits
(Images from Rafael C. Gonzalez and Richard E.
Wood, Digital Image Processing, 2nd Edition.
LZW Coding Algorithm
. Initialize a dictionary by all possible gray values (0-255)
. Input current pixel
. If the current pixel combined with previous pixels
form one of existing dictionary entries
Then
2.1 Move to the next pixel and repeat Step 1
Else
2.2 Output the dictionary location of the currently recognized
sequence (which is not include the current pixel)
2.3 Create a new dictionary entry by appending the currently
recognized sequence in 2.2 with the current pixel
2.4 Move to the next pixel and repeat Step 1
LZW Coding Example
Dictionary Currently
Location Entry Input recognized Encoded
0 0 pixel Sequences Output (9 bits)
1 1 39 39
… … 39 39 39
255 255 126 126 39
256 39-39 126 126 126
257 39-126 39 39 126
258 126-126 39 39-39
259 126-39 126 126 256
260 39-39-126 126 126-126
261 126-126-39 39 39 258
262 39-39-126-126 39 39-39
126 39-39-126
126 126 260