19ECS352 - Image Processing. Dr.

Justin Varghese Slide 1

Digital Image Processing

Justin Varghese, Ph.D. (Eng.), SM IEEE

Professor,
Department of Computer Science & Engineering,
Gitam (Deemed to be University)
GST, Bangalore Campus
Mobile: +91-9940955156
Email: [email protected], [email protected]

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 2

Image Compression

• The field of image compression continues to grow at

a rapid pace
• As we look to the future, the need to store and
transmit images will only continue to increase faster
than the available capability to process all the data
• The problem of reducing the amount of data required
to represent a digital image.
• From a mathematical viewpoint: transforming a 2-D
pixel array into a statistically uncorrelated data set.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 3

Image Compression

✓ Applications that require image compression are

many and varied such as:
Internet, Businesses, Multimedia, Satellite imaging,
Medical imaging

•For data STORAGE and data TRANSMISSION

•DVD
•Remote Sensing
•Video conference
•FAX
•Control of remotely piloted vehicle
•The bit rate of uncompressed digital cinema data
exceeds 1 Gbps
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 4

✓ Compression algorithm development starts with

applications to two-dimensional (2-D) still images

✓ After the 2-D methods are developed, they are often

extended to video (motion imaging)
✓ Image compression involves reducing the size of
image data files, while retaining necessary
information
✓ Retaining necessary information depends upon the
application
✓ Image segmentation methods, which are primarily a
data reduction process, can be used for compression

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 5

✓ The reduced file created by the compression process

is called the compressed file and is used to reconstruct
the image, resulting in the decompressed image
✓ The original image, before any compression is
performed, is called the uncompressed image file
✓ The ratio of the original, uncompressed image file
and the compressed file is referred to as the
compression ratio

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 6

✓The compression ratio is denoted by:

(c) Scott E Umbaugh, SIUE 6

Department of Computer Science & Engineering-Bangalore Campus
2005
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 7

✓ To understand “retaining necessary information”,

we must differentiate between data and information
1. Data:
• For digital images, data refers to the pixel gray
level values that correspond to the brightness of a
pixel at a point in space
• Data are used to convey information, much like the
way the alphabet is used to convey information via
words
2. Information:
• Information is an interpretation of the data in a
meaningful way
• Information is an elusive concept; it can be
application specific
(c) Scott E Umbaugh, SIUE 7
Department of Computer Science & Engineering-Bangalore Campus
2005
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 8

✓ There are two primary types of image compression methods:

1. Lossless compression methods:

• Allows for the exact recreation of the original image data,
and can compress complex images to a maximum 1/2 to 1/3
the original size – 2:1 to 3:1 compression ratios
• Preserves the data exactly
2. Lossy compression methods:
• Data loss, original image cannot be re-created exactly
• Can compress complex images 10:1 to 50:1 and retain high
quality, and 100 to 200 times for lower quality, but
acceptable, images

(c) Scott E Umbaugh, SIUE 8

Department of Computer Science & Engineering-Bangalore Campus
2005
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 9

Data compression implies sending or storing a smaller

number of bits. Although many methods are used for this
purpose, in general these methods can be divided into
two broad categories: lossless and lossy methods.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 10

Lossless data compression

In lossless data compression, the integrity of the data is preserved.

The original data and the data after compression and
decompression are exactly the same because, in these methods,
the compression and decompression algorithms are exact inverses
of each other: no part of the data is lost in the process.

Redundant data is removed in compression and added during

decompression. Lossless compression methods are normally used
when we cannot afford to lose any data.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 11

Lossy data compression

Our eyes and ears cannot distinguish subtle changes. In
such cases, we can use a lossy data compression method.
These methods are cheaper—they take less time and
space when it comes to sending millions of bits per
second for images and video. Several methods have been
developed using lossy compression techniques. JPEG
(Joint Photographic Experts Group) encoding is used
to compress pictures and graphics, MPEG (Moving
Picture Experts Group) encoding is used to compress
video, and MP3 (MPEG audio layer 3) for audio
compression.
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 12

Lossless & Lossy data compression

▪ Lossless compression
▪ lossless compression for legal and medical documents,
computer programs
▪ exploit only code and inter-pixel redundancy
▪ Lossy compression
▪ digital image and video where some errors or loss can be
tolerated
▪ exploit both code and inter-pixel redundancy and sycho-
visual perception properties

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 13

Types of redundancy
✓ Compression algorithms are developed by taking
advantage of the redundancy that is inherent in image
data

✓ Four primary types of redundancy that can be found in

images are:
1. Coding
2. Interpixel
3. Interband
4. Psychovisual redundancy

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 14

1. Coding redundancy
✓ Occurs when the data used to represent the image is not
utilized in an optimal manner
2. Interpixel redundancy
✓ Occurs because adjacent pixels tend to be highly correlated,
in most images the brightness levels do not change rapidly,
but change gradually
3. Interband redundancy
✓ Occurs in color images due to the correlation between bands
within an image – if we extract the red, green and blue bands
they look similar
4. Psychovisual redundancy
✓ Some information is more important to the human visual
system than other types of information
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 15

Interpixel redundancy
• Interpixel redundancy implies that pixel values are
correlated (i.e., a pixel value can be reasonably predicted
by its neighbors).
histograms

auto-correlation


f ( x) o g ( x) =  f ( x) g ( x + a)da
−

auto-correlation: f(x)=g(x)
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 16

Interpixel redundancy (cont’d)

• To reduce interpixel redundancy, some kind of transformation
must be applied on the data (e.g., thresholding, DFT, DWT)

Example:

threshold
original

11 ……………0000……………………..11…..000…..

thresholded
(1+10) bits/pair
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 17

Psychovisual redundancy

• The human eye is more sensitive to the lower

frequencies than to the higher frequencies in
the visual spectrum.

• Idea: discard data that is perceptually

insignificant!

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 18

Psychovisual redundancy (cont’d)

Example: quantization

256 gray levels 16 gray levels 16 gray levels + random noise

add a small pseudo-random number

C=8/4 = 2:1 to each pixel prior to quantization
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 19

Compression System Model

• The compression system model consists of two parts:

1. The compressor
2. The decompressor

• The compressor consists of a preprocessing stage and

encoding stage, whereas the decompressor consists
of a decoding stage followed by a postprocessing
stage

(c) Scott E Umbaugh, SIUE 19

Department of Computer Science & Engineering-Bangalore Campus
2005
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 20

Compression System Model

Reduce inter-pixel Reduce psycho- Reduce coding
redundancy visual redundancy redundancy
(Reversible) (Irreversible) (Reversible)

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 21

Coding - Definitions
• Code: a list of symbols (letters, numbers, bits etc.)
• Code word: a sequence of symbols used to represent
some information (e.g., gray levels).
• Code word length: number of symbols in a code
word.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 22

Coding Redundancy
Let us assume, that a discrete random variable rk in the interval [0,1]
represent the gray level of an image:
nk
pr (rk ) = k = 0,1, 2,, L − 1
n
If the number of bits used to represent each value of rk is l(rk), then the
average number of bits required to represent each pixel:
L −1
Lavg =  l (rk ) pr (rk )
k =0
The total number bits required to code an MxN image:

M .N .Lavg

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 23

Variable Length Coding

Takes advantage of the probabilistic nature of information.
◼ Unlike fixed length codes like ASCII, variable length codes:
◼ Assign the longest codes to the most infrequent events.

◼ Assign the shortest codes to the most frequent events.

◼ Each code word must be uniquely identifiable regardless of

length.
◼ Examples of Variable Length Coding
◼ Morse Code

◼ Huffman Coding

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 24

Huffman coding
Huffman coding assigns shorter codes to symbols that
occur more frequently and longer codes to those that
occur less frequently. For example, imagine we have a
text file that uses only five characters (A, B, C, D, E).
Before we can assign bit patterns to each character, we
assign each character a weight based on its frequency of
use. In this example, assume that the frequency of the
characters is as shown in Table 15.1.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 25

Figure 15.4 Huffman coding

15.25 Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 26

A character’s code is found by starting at the

root and following the branches that lead to that
character. The code itself is the bit value of each
branch on the path, taken in sequence.

Figure 15.5 Final tree and code

15.26 Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 27

Encoding
Let us see how to encode text using the code
for our five characters. Figure 15.6 shows the
original and the encoded text.

Figure 15.6 Huffman encoding

15.27 Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 28

Decoding

The recipient has a very easy job in decoding the data

it receives. Figure 15.7 shows how decoding takes
place.

Figure 15.7 Huffman decoding

15.28 Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 29

Huffman Encoding (Example)

Step 1 : Sort all Symbols according to their probabilities
(left to right) from Smallest to largest
these are the leaves of the Huffman tree

P(B) = 0.51

P(C) = 0.09 P(E) = 0.11 P(D) = 0.13 P(A)=0.16

CS 414 - Spring
Department of Computer Science & Engineering-Bangalore Campus
2012
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 30

Huffman Encoding (Example)

Step 2: Build a binary tree from left to
Right P(CEDAB) = 1
Policy: always connect two smaller nodes
together (e.g., P(CE) and P(DA) had both
Probabilities that were smaller than P(B),
Hence those two did connect first

P(CEDA) = 0.49 P(B) = 0.51

P(CE) = 0.20
P(DA) = 0.29

P(C) = 0.09 P(E) = 0.11 P(D) = 0.13 P(A)=0.16

CS 414 - Spring
Department of Computer Science & Engineering-Bangalore Campus
2012
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 31

Huffman Encoding (Example)

Step 3: label left branches of the tree
P(CEDAB) = 1
With 0 and right branches of the tree
With 1
0 1

P(CEDA) = 0.49 P(B) = 0.51

0 1

P(CE) = 0.20
P(DA) = 0.29
0 1
0 1

P(C) = 0.09 P(E) = 0.11 P(D) = 0.13 P(A)=0.16

CS 414 - Spring
Department of Computer Science & Engineering-Bangalore Campus
2012
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 32

Huffman Encoding (Example)

Step 4: Create Huffman Code
P(CEDAB) = 1
Symbol A = 011
Symbol B = 1
0 1
Symbol C = 000
Symbol D = 010
Symbol E = 001
P(CEDA) = 0.49 P(B) = 0.51

0 1

P(CE) = 0.20
P(DA) = 0.29
0 1
0 1

P(C) = 0.09 P(E) = 0.11 P(D) = 0.13 P(A)=0.16

CS 414 - Spring
Department of Computer Science & Engineering-Bangalore Campus
2012
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 33

Huffman Decoding

• Assume Huffman Table

• Symbol Code
X 0
Y 10
Z 11
Consider encoded
bitstream:
000101011001110 What is the decoded string?

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 34

Huffman Example
• Construct the Huffman
Symbol (S) P(S)
coding tree (in class)
A 0.25

B 0.30

C 0.12

D 0.15

E 0.18

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 35

Characteristics of Solution

Symbol (S) Code

A 01

B 11

C 100

D 101

E 00

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 36

Example Encoding/Decoding

Encode “BEAD” Symbol (S) Code

110001101
A 01

B 11

C 100
Decode “0101100”
D 101

E 00

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 37

Entropy (Theoretical Limit)

N
H =  − p( si ) log 2 p( si ) Symbol P(S) Code
i =1 A 0.25 01

= -.25 * log2 .25 + B 0.30 11

-.30 * log2 .30 + C 0.12 100
-.12 * log2 .12 +
-.15 * log2 .15 + D 0.15 101
-.18 * log2 .18 E 0.18 00

H = 2.24 bits

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 38

Average Codeword Length

N
L =  p( si )codelength( si ) Symbol P(S) Code
i =1 A 0.25 01

= .25(2) + B 0.30 11
.30(2) + C 0.12 100
.12(3) +
.15(3) + D 0.15 101
.18(2) E 0.18 00

L = 2.27 bits

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 39

Code Length Relative to Entropy

N N
L =  p( si )codelength( si ) H =  − p( si ) log 2 p( si )
i =1 i =1

• Huffman reaches entropy limit when all

probabilities are negative powers of 2
– i.e., 1/2; 1/4; 1/8; 1/16; etc.

• H ≤Code Length ≤ H + 1

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 40

Example

H = -.01*log2.01 + Symbol P(S) Code

-.99*log2.99 A 0.01 1
= .08 B 0.99 0

L = .01(1) +
.99(1)
=1

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 41

Group Exercise
• Compute Entropy (H) Symbol (S) P(S)

A 0.1
• Build Huffman tree B 0.2

C 0.4
• Compute average D 0.2
code length
E 0.1

• Code “BCCADE”
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 42

Limitations
• Diverges from lower limit when probability of
a particular symbol becomes high
– always uses an integral number of bits

• Must send code book with the data

– lowers overall efficiency

• Must determine frequency distribution

– must remain stable over the data set
CS 414 - Spring
Department of Computer Science & Engineering-Bangalore Campus
2012
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 43

Run-length encoding

Run-length encoding is probably the simplest method of

compression. It can be used to compress data made of any
combination of symbols. It does not need to know the
frequency of occurrence of symbols and can be very
efficient if data is represented as 0s and 1s.
The general idea behind this method is to replace
consecutive repeating occurrences of a symbol by one
occurrence of the symbol followed by the number of
occurrences.

15.43 Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 44

Run-length encoding
The method can be even more efficient if the data uses only two symbols (for
example 0 and 1) in its bit pattern and one symbol is more frequent than the
other.

15.44 Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 45

Run-length encoding

15.45 Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 46

Arithmetic Coding

• Unlike the variable-length codes described previously,

arithmetic coding generates nonblock codes.
• In arithmetic coding, which can be traced to the work of Eli
as (see Abramson [1963]) , a one-to-one correspondence
between source symbols and code words do es not exist.
• Instead, an entire sequence of source symbols (or message) is
assigned a single arithmetic codeword. The code word itself
defines an interval of real numbers between 0 and 1.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 47

Arithmetic Coding

• Optimal algorithm as Huffman coding wrt

compression ratio
• Better algorithm than Huffman wrt transmitted
amount of information
– Huffman – needs to transmit Huffman tables with
compressed data
– Arithmetic – needs to transmit length of encoded
string with compressed data

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 48

Arithmetic Coding

• Each symbol is coded by considering the prior data

• Encoded data must be read from the beginning, there
is no random access possible
• Each real number (< 1) is represented as binary
fraction
– 0.5 = 2-1 (binary fraction = 0.1); 0.25 = 2-2 (binary fraction
= 0.01), 0.625 = 0.5+0.125 (binary fraction = 0.101) ….

CS 414 - Spring 2012

Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 49

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 50

DepartmentCS 414 - SpringScience

of Computer 2012 & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 51

Encoding a1 a2 a3 a3 a4

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 52

Lempel-Ziv-Welch (LZW) Compression Algorithm

• Introduction to the LZW Algorithm

• LZW Encoding Algorithm

• LZW Decoding Algorithm

• LZW Limitations

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 53

LZW Encoding Algorithm

• If the message to be encoded consists of only one character, LZW outputs the
code for this character; otherwise it inserts two- or multi-character, overlapping*,
distinct patterns of the message to be encoded in a Dictionary.

*The last character of a pattern is the first character of the next pattern.

• The patterns are of the form: C0C1 . . . Cn-1Cn. The prefix of a pattern consists of
all the pattern characters except the last: C0C1 . . . Cn-1

LZW output if the message consists of more than one character:

➢ If the pattern is not the last one; output: The code for its prefix.
➢ If the pattern is the last one:
• if the last pattern exists in the Dictionary; output: The code for the pattern.
• If the last pattern does not exist in the Dictionary; output: code(lastPrefix) then
output: code(lastCharacter)
Note: LZW outputs codewords that are 12-bits each. Since there are 212 = 4096 codeword
possibilities, the minimum size of the Dictionary is 4096; however since the Dictionary is
usually implemented as a hash table its size is larger than 4096.
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 54

LZW Encoding Algorithm (cont’d)

Initialize Dictionary with 256 single character strings and their corresponding ASCII codes;

Prefix  first input character;

CodeWord  256;
while(not end of character stream){
Char  next input character;
if(Prefix + Char exists in the Dictionary)
Prefix  Prefix + Char;
else{
Output: the code for Prefix;
insertInDictionary( (CodeWord , Prefix + Char) ) ;
CodeWord++;
Prefix  Char;
}
}

Output: the code for Prefix;

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 55

LZW Encoding Algorithm (cont’d)

• A high-level view of the encoding algorithm is shown here:

• Initialize the dictionary to contain all strings of length one.
• Find the longest string W in the dictionary that matches the
current input.
• Emit the dictionary index for W to output and remove W from
the input.
• Add W followed by the next symbol in the input to the
dictionary.
• Go to Step 2.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 56

Example 1: Compression using LZW

Encode the string BABAABAAA by the LZW encoding algorithm.

1. BA is not in the Dictionary; insert BA, output the code for its prefix: code(B)
2. AB is not in the Dictionary; insert AB, output the code for its prefix: code(A)
3. BA is in the Dictionary.
BAA is not in Dictionary; insert BAA, output the code for its prefix: code(BA)
4. AB is in the Dictionary.
ABA is not in the Dictionary; insert ABA, output the code for its prefix: code(AB)
5. AA is not in the Dictionary; insert AA, output the code for its prefix: code(A)
6. AA is in the Dictionary and it is the last pattern; output its code: code(AA)

The compressed message is: <66><65><256><257><65><260>

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 57

Example 2: Compression using LZW

Encode the string BABAABRRRA by the LZW encoding algorithm.

1. BA is not in the Dictionary; insert BA, output the code for its prefix: code(B)
2. AB is not in the Dictionary; insert AB, output the code for its prefix: code(A)
3. BA is in the Dictionary.
BAA is not in Dictionary; insert BAA, output the code for its prefix: code(BA)
4. AB is in the Dictionary.
ABR is not in the Dictionary; insert ABR, output the code for its prefix: code(AB)
5. RR is not in the Dictionary; insert RR, output the code for its prefix: code(R)
6. RR is in the Dictionary.
RRA is not in the Dictionary and it is the last pattern; insert RRA, output code for its prefix:
code(RR), then output code for last character: code(A)

The compressed message is: <66><65><256><257><82><260> <65>

Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 58

LZW: Number of bits transmitted

Example: Uncompressed String: aaabbbbbbaabaaba
Number of bits = Total number of characters * 8
= 16 * 8
= 128 bits
Compressed string (codewords): <97><256><98><258><259><257><261>
Number of bits = Total Number of codewords * 12
= 7 * 12
= 84 bits
Note: Each codeword is 12 bits because the minimum Dictionary size is taken
as 4096, and
212 = 4096

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 59

Example 1: LZW Decompression

Use LZW to decompress the output sequence <66> <65> <256> <257> <65> <260>

1. 66 is in Dictionary; output string(66) i.e. B

2. 65 is in Dictionary; output string(65) i.e. A, insert BA
3. 256 is in Dictionary; output string(256) i.e. BA, insert AB
4. 257 is in Dictionary; output string(257) i.e. AB, insert BAA
5. 65 is in Dictionary; output string(65) i.e. A, insert ABA
6. 260 is not in Dictionary; output
previous output + previous output first character: AA, insert AA
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 60

Example 2: LZW Decompression

Decode the sequence <67> <70> <256> <258> <259> <257> by LZW decode algorithm.

1. 67 is in Dictionary; output string(67) i.e. C

2. 70 is in Dictionary; output string(70) i.e. F, insert CF
3. 256 is in Dictionary; output string(256) i.e. CF, insert FC
4. 258 is not in Dictionary; output previous output + C i.e. CFC, insert CFC
5. 259 is not in Dictionary; output previous output + C i.e. CFCC, insert CFCC
6. 257 is in Dictionary; output string(257) i.e. FC, insert CFCCF

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 61

LZW: Limitations
• What happens when the dictionary gets too large?

• One approach is to clear entries 256-4095 and start building the dictionary again.

• The same approach must also be used by the decoder.

Exercises

• Use LZW to trace encoding the string ABRACADABRA.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 62

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 63

LZW Coding (cont’d)

Example:
As the encoder examines image pixels,
39 39 126 126 gray level sequences (i.e., blocks) that are
39 39 126 126 not in the dictionary are assigned to a new
39 39 126 126 entry.
39 39 126 126

Dictionary Location Entry

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 -

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 64

Example
39 39 126 126
39 39 126 126
Concatenated Sequence: CS = CR + P
39 39 126 126 (CR) (P)
39 39 126 126

CR = empty
repeat
P=next pixel
CS=CR + P
If CS is found:
(1) No Output
(2) CR=CS
else:
(1) Output D(CR)
(2) Add CS to D
(3) CR=P

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 65

Decoding LZW

• Use the dictionary for decoding the “encoded output”

sequence.
• The dictionary need not be sent with the encoded
output.
• Can be built on the “fly” by the decoder as it reads the
received code words.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 66

Lossless predictive coding

The lossless predictive coding, is based on eliminating the
interpixel redundancies of closely spaced pixels by extracting
and coding only the new information in each pixel.
The new information of a pixel is defined as the difference
between the actual and predicted value of that pixel.
The system consists of an encoder and a decode, each containing
an identical predictor.
As each successive pixel of the input image, denoted f, is
introduced to the encoder, the predictor generates the anticipated
value of that pixel based on some number of past inputs.
Prediction error is given by

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 67

Block Diagram of lossless predictive coding

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 68

Predictive Coding Example loss less JPEG

Lossless Mode:
• Truly lossless
• It is a predictive coding mechanism as opposed to the baseline
mechanism which is based on DCT and quantization(the source of the
loss).
• Here is the simple block diagram of the technique:

Predictive
Difference

Huffman
EnCoder Lossless
Coding

68
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 69

Wavelet Transform

Wavelets vs. Fourier Transform

◼ In Fourier transform (FT) we represent a
signal in terms of sinusoids
◼ FT provides a signal which is localized only in
the frequency domain
◼ It does not give any information of the signal
in the time domain

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 70

Wavelet Transform

Wavelets vs. Fourier Transform

◼ Basis functions of the wavelet transform (WT)
are small waves located in different times
◼ They are obtained using scaling and translation
of a scaling function and wavelet function
◼ Therefore, the WT is localized in both time
and frequency

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 71

Wavelet Transform

Wavelets vs. Fourier Transform

• In addition, the WT provides a multiresolution
system
• Multi-resolution is useful in several
applications
• For instance, image communications and
image data base are such applications

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 72

Wavelet Transform

◼ Wavelet
◼ Small wave
◼ Means the window function is of finite length
◼ Mother Wavelet
◼ A prototype for generating the other window functions
◼ All the used windows are its dilated or compressed and shifted
versions

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 73

Wavelet Transform

◼ Wavelet Transform
◼ An alternative approach to the short time Fourier transform to
overcome the resolution problem
◼ Similar to STFT: signal is multiplied with a function
◼ Multiresolution Analysis
◼ Analyze the signal at different frequencies with different
resolutions
◼ Good time resolution and poor frequency resolution at high
frequencies
◼ Good frequency resolution and poor time resolution at low
frequencies
◼ More suitable for short duration of higher frequency; and longer
duration of lower frequency components

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 74

Wavelet Transform
Haar Wavelet

◼ Haar expansion is a two-point avarage

and difference operation
◼ The basis functions are given as
 1 2 , n = 2k
1 2 , n = 2k , 2k + 1 
 2 k [ n] =  2 k +1[n] = −1 2 , n = 2k + 1
 0, otherwise  0, otherwise

◼ It follows that
2k [n] = 0[n − 2k ], 2k +1[n] = 1[n − 2k ]
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 75

Fast Wavelet Transform

◼ Mallat was the first to implement this scheme, using a well

known filter design called “two channel sub band coder”,
yielding a ‘Fast Wavelet Transform’
◼ This scheme is also called Mallat* Filter Scheme
◼ The process involves in separating high and low
frequencies by filter banks

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 76

Fast Wavelet Transform

◼ Approximations: High-scale, low-frequency components
of the signal
◼ Details: low-scale, high-frequency components

LPF

Input Signal
HPF

◼ The former process produces twice the data it began with: N input
samples produce N approximations coefficients and N detail
coefficients.
◼ To correct this, we Down sample (or: Decimate) the filter output by
two, by simply throwing away every second coefficient.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 77

Fast Wavelet Transform

Sub band coding

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 78

Fast Wavelet Transform

Decomposition

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 79

Fast Wavelet Transform

Reconstruction

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 80

Wavelet Based Image Coding

The wavelet transform, which localizes information in both the spatial and
frequency domain

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 81

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 82

Wavelet Based Image Coding

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 83

Wavelet Based Image Coding

• “Modern” lossy wavelet coding exploits multi-resolution and
self-similar nature of wavelet decomposition
– Energy is compacted into a small number of coeff.
– Significant coeff. tend to cluster at the same spatial location in
each frequency subband

• Two set of info. to code:

– Where are the significant
coefficients?
– What values are the significant
coefficients?

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 84

Wavelet Based Image Coding

• Parent-children relation among coeff.
– Each parent coeff at level k spatially correlates
with 4 coeff at level (k-1) of same orientation
– A coeff at lowest band correlates with 3 coeff.
• Coding significance map via zero-tree
– Encode only high energy coefficients
• Need to send location info.
➔ large overhead
– Encode “insignificance map” w/ zero-trees
• Successive approximation quantization
– Send most-significant-bits first and
gradually refine coeff. value
– “Embedded” nature of coded bit-stream
• get higher fidelity image by adding
extra refining bits
Department of Computer Science & Engineering-Bangalore Campus
 19ECS352 - Image Processing. Dr. Justin Varghese Slide 85

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 86

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 87

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 88

Contour tracing and coding

Relative address coding is one approach for representing intensity transitions
that make up the contours in a binary image. Another approach is to represent each
contour by a set of boundary points or by a single boundary point and a set of
directionals. The latter sometimes is referred to as direct contour tracing.
The predictive differential quantizing (PDQ), which demonstrates the essential
characteristics of both approaches. It is a scan-line-oriented contour tracing
procedure.
In predictive differential quantizing, the front and back contours of each object of an
image are traced simultaneously to generate a sequence of pairs (Δ', Δ").

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 89

Contour tracing and coding

The term Δ' is the difference between the starting coordinates of the front contours on
adjacent lines, and Δ" is the difference between the front to-back contour lengths.
These differences, together with special messages that indicate the start of new
contours (the new start message) and the end of old contours (the merge message),
represent each object. 1f Δ" is replaced by the difference between the back contour
coordinates of adjacent lines, denoted Δ"', the technique is referred to as double delta
coding (DOC).
The new start and merge messages allow the (Δ ', Δ ") or (Δ ', Δ "') pairs generated on a
scan line basis to be linked properly to the corresponding pairs in the previous and
next rows. Without these messages, the decoder would be unable to reference one
difference pair to another or to position correctly the contours within the image.
To avoid encoding both the row and column coordinates of each new start and merge
message, a unique code often is used to identify scan lines that do not contain object
pixels. The final step in both PDQ and DOC coding is to represent Δ ', Δ " or Δ “’, and the
coordinates of the new starts and merges with a suitable variable-length code.

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 90

Questions?

Department of Computer Science & Engineering-Bangalore Campus

 19ECS352 - Image Processing. Dr. Justin Varghese Slide 91

Thank You

Department of Computer Science & Engineering-Bangalore Campus