lOMoARcPSD|58243556

BEC613A MMC Module 3 Notes

Computer science and engineering (Bahubali College of Engineering Shravanabelagola)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

DEPARTMENT OF
ELECTRONICS AND COMMUNICATION ENGINEERING
Accredited by NBA, New Delhi

MULTIMEDIA COMMUNICATION
BEC613A
VI SEMESTER
MODULE 3 NOTES
Prepared by,
Mrs. MEGHANA M N
Assistant Professor
Dept. of ECE
MIT Thandavapura

A Unit of Maharaja Education Trust®

MAHARAJA INSTITUTE OF TECHNOLOGY

THANDAVAPURA

NH 766, Nanjangud Taluk, Mysuru- 571 302

(Affiliated to VTU, Belagavi and approved by AICTE, New Delhi)

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

DEPARTMENT OF
ELECTRONICS AND COMMUNICATION ENGINEERING
Accredited by NBA, New Delhi

MODULE 3 CONTENTS

TEXT AND IMAGE COMPRESSION

• Introduction
• Compression principles
• text compression
• image Compression (Chapter 3 of Text1)
Text Book 1: Multimedia Communications –Fred Halsall, Pearson Education,2001,ISBN-978813170994

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

MODULE 3
TEXT AND IMAGE COMPRESSION

1. INTRODUCTION
• Compression: Compression in multimedia refers to the process of reducing the size of digital
multimedia files, which is first applied to the source information prior to its transmission.
• Compression is done to:
1. Reduce the volume of information to be transmitted text, fax, and images.
2. Reduce the bandwidth required for the transmission of speech, audio, and video.

2. COMPRESSION PRINCIPLES
• Based on the following compression principles there are 5 compression algorithms:
1. Source encoders and destination decoders
2. Lossless and lossy compression
3. Entropy encoding
4. Source encoding

2.1 SOURCE ENCODERS AND DESTINATION DECODERS

• Compression algorithm is applied to the source information relating to a particular multimedia
application prior to transmitting.
• Decompression algorithm must be applied to reproduce the original source information or nearly exact
copy of it.
• Source encoder is used for the application of the compression algorithm and destination decoder is
used for the application of decompression algorithm.
• In application where two computers communicating, time required to perform the compression and
decompression is not always critical. Hence both algorithms are implemented in software within the
two computers.
• Other communication cases in compression and decompression algorithm in software forms are not
acceptable. Two algorithms here, must be performed by special processors in separate units as shown
in figure 1.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure 1: Source encoder / destination decoder (a) Software only; (b) Special processor hardware

2.2 LOSSLESS AND LOSSY COMPRESSION ALGORITHMS

• The compression techniques can be either lossless or lossy:
1. Lossless compression algorithm:
• To reduces the amount of source information to be transmitted in such a way that in destination when
decompressed there is no loss of information.
• Reversible compression is another name of lossless compression.
• Ex.: Text file transfer over the network where no part of the source information is lost during either
the compression or decompression operations.
2. Lossy compression algorithm:
• It will not produce the exact copy of the source information after decompression, but to produce
ideally a close approximation of the original data.
• Ex.: Transfer of digitized images and audio and video streams.
• Since human eyes or ears are sensitive, such that any fine details may be missing from the original
source signal after decompressions are not detected.

2.3 ENTROPY ENCODING

• Entropy encoding in multimedia is a lossless and independent data compression technique that reduces
the size of multimedia data by assigning shorter codes to frequently occurring symbols or data
patterns.
• Examples of entropy encoding are:
1. Run length encoding and
2. Statistical encoding

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

2.3.1 RUN LENGTH ENCODING

• When source information comprises long substrings of the same character or binary digit run length
encoding is used.
• Here, instead of transmitting source string in the form of independent codewords or bits source string
is transmitted in the form of different set of codewords which indicate:
1. Particular character being transmitted and
2. Number of characters in the substring.
• Destination simply, interprets each codeword received and outputs the appropriate number of
characters.
• Ex: Application involves transmission of long strings of binary bits that comprise limited number of
substrings each substring can be assigned a separate codeword.
• Total bit string is then, transmitted in the form of the string of codewords selected from the codeword
set.
• Ex: Transmission of the binary strings produced by the scanner in a facsimile machine.
• When scanning of typed documents scanner produces long substrings of either binary 0s or 1s are
transmitting directly.
• Instead, they are sent in the form of a string of codewords each indicating both the bit 0 or 1 and the
number of strings in the substring.
• Consider the output of the scanner was:
000000011111111110000011… can be represented as 0,7 1,10 0,5 1,2 …
Since, only the two binary digits 0 and 1 are involved and if, first substring always comprises binary
0s then, the string could be represented as 7, 10, 5, 2 …
• To send this in the digital form individual decimal digits would be sent in their binary form.
• Assuming the fixed number of bits per codeword number of bits per codeword would be determined
by the largest possible substring.

2.3.2 STATISTICAL ENCODING

• In many applications it uses a set of codewords to transmit the source information.
• Ex: Set of ASCII codewords which is of 7 bits are often used for the transmission of strings of
characters. Normally, all the codewords in the set comprise a fixed number of binary bits.
• In many applications, symbols and codewords that are present in the source information do not occur
with the same frequency.
• Ex: String of text in character A may occur more frequently than character P which again, will occur
more frequently than character Z, and so on.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

• Statistical encoding uses this property by using the set of variable length codewords with the shortest
codewords used to represent the most frequently occurring symbols.
• When variable-length codewords used in order for the decoding operation to be carried out correctly it
is necessary to ensure that a shorter codeword in the set does not form the start of a longer codeword
otherwise, the decoder will interpret the string on the wrong codeword boundaries.
• Prefix property in the codeword set avoids the above problem.
• Example of encoding scheme to use prefix property is Huffman encoding algorithm.
• The theoretical minimum average number of bits that are required to transmit a particular source
stream is known as the Entropy of the source and computed using Shannon formula:
#

𝐸𝑛𝑡𝑟𝑜𝑝𝑦: 𝐻 = − , 𝑃! 𝑙𝑜𝑔" 𝑃!
!$%

Where n = Number of different symbols in the source stream

Pi = Probability of occurrence of symbol i
• Average number of bits per codeword is given by:
#

, 𝑁! 𝑃!
!$%

• Efficiency is calculated by ratio of the entropy of the source to the average number of bits per
codeword.

1 PROBLEM
A statistical encoding algorithm is being considered for the transmission of a large number of long text
files over a public network. Analysis of the file contents has shown that each file comprises only the six
different characters M, F, Y, N, 0, and 1 each of which occurs with a relative frequency of occurrence of
0.25, 0.25, 0.125, 0.125, 0.125, and 0.125 respectively. If the encoding algorithm under consideration uses
the following set of codewords:
M = 10, F = 11, Y= 010, N = 011, 0 = 000, 1 = 001
compute:
(i) the average number of bits per codeword with the algorithm,
(i) the entropy of the source,
(iii) the minimum number of bits required assuming fixed-length codewords.

Solution:
(i) Average number of bits per codeword is given by:

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

# &

, 𝑁! 𝑃! = , 𝑁! 𝑃! = 22(2 𝑋 0.25) + 4(3 𝑋 0.125)> = 𝟐. 𝟓

!$% !$%

(ii) Entropy of source is given by:

𝐻 = − ∑#!$% 𝑃! 𝑙𝑜𝑔" 𝑃! = − ∑&!$% 𝑃! 𝑙𝑜𝑔" 𝑃! = − B220.25 𝑙𝑜𝑔" (0.25)> + 4(0.125 𝑙𝑜𝑔" (0.125)C =

2.5

(iii) Since there are 6 different characters, using fixed-length code-words would require a
minimum of 3 bits (8 combinations).

2.4 SOURCE ENCODING

• The 2 widely used example of source encoding are:
1. Differential encoding
2. Transform encoding

2.4.1 DIFFERENTIAL ENCODING

• In differential encoding, small codewords are used, each of which indicates only the difference in
amplitude between the current value/signal being encoded and the immediately preceding value/signal.
• To use this property of the source information, a set of smaller codewords can be used each of which
indicates only difference in amplitude between the current value/signal being encoded and the
immediately preceding value/signal instead, of using a relatively large codewords to represent the
amplitude of each value/signal.
• Ex.: If the digitization of analog signal requires 12 bits to obtain the required dynamic range but, the
maximum difference in amplitude between successive samples of the signal requires only 3 bits then,
by using only the difference values a saving of 75% on transmission bandwidth can be obtained.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

2.4.2 TRANSFORM ENCODING

• Transform encoding involves transforming the source information from one form into another which
is more readily compressible where there is no loss of information.
• This technique is used in many applications of both image and video.
• Ex: Digitization of a continuous tone monochromatic image produces a 2-D matrix of pixel values
each of which represents the level of gray in a particular position of the image.
• Moving from one position in the matrix to the next magnitude of each pixel value can vary from 0.
Some examples are shown in figure 2(a).

(b)

Figure 2: Transform coding: (a) Example pixel pattern (b) DCT transform principles
• Spatial frequency is a rate of change in magnitude as one traverses the matrix. For any particular
image, there will be a mix of different spatial frequencies whose amplitudes are determined by the
relate changes in magnitude of the pixels.
• It is true if, matrix been scanned in either, the horizontal or vertical direction, which provides the
horizontal and vertical frequency components of the image.
• In practice, Human eye is less sensitive to the higher spatial frequency components associated with an
Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

image, the lower frequency components.

• If the amplitude of the higher frequency components falls below a certain amplitude threshold they
will not be detected by the eye in terms of compression.
• If we can transform the original spatial form of representation into an equivalent representation
involving spatial frequency components then, more readily identifying and eliminating those higher
frequency components, which the eye cannot detect. It reduces the volume of information to be
transmitted without degrading the perceived quality of the original image.
• DCT (Discrete Cosine Transform): Transformation of 2-D matrix of pixel values into an equivalent
matrix of spatial frequency components can be carried out from this mathematical technique.
• The basic principle behind DCT is shown in figure 2(b). Transformation using DCT is lossless apart
from small rounding errors in the mathematics.
• Once the equivalent matrix of spatial frequency components known as coefficients then any frequency
components in the matrix whose amplitude is less than a defined threshold can be dropped it is at this
point DCT operation will become lossy.

3. TEXT COMPRESSION
• 3 different types of text – Unformatted, formatted and hypertext are represented as strings of
characters from selected a defined set of strings and alphanumeric characters are distributed with
additional control characters.
• Since compression algorithm involved with the text must be lossless, Entropy encoding (statistical
encoding) methods are used compression.
• Statistical encoding method: There are 2 types of coding used for texts:
1. Use single character as the basis of deriving an optimum set of codewords.
Ex.: Huffman and arithmetic coding algorithm
2. Use variable-length strings of characters
Ex.: Lempel-Ziv (LZ) algorithm
• There are 2 types of coding of text:
1. Static coding: Using static coding an optimum set of variable length codewords is derived with
the shortest codewords used to have more frequently occurring characters. Using this information,
instead of using fixed-length codewords, an optimum set of variable-length codewords is derived
with the shortest codewords used; to represent the most frequently occurring characters. The
resulting set of codewords are then used for all subsequent transfers involving this particular type
of text. This approach is known as static coding.
2. Dynamic coding (adaptive coding): optimum set of codewords likely to vary from one transfer to
another. To allow for this possibility, the codeword set that is used to transfer a particular text
Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

string is derived as the transfer takes place. This is done by building up knowledge of both the
characters that are present in the text and their relative frequency of occurrence dynamically as the
characters are being transmitted. This approach is known as dynamic or adaptive coding.
• Text compression algorithms using statistical encoding technique are as follows:
1. Static Huffman coding
2. Dynamic Huffman coding
3. Arithmetic coding
4. Lempel-Ziv coding
5. Lempel-Ziv-Welsh coding

3.1 STATIC HUFFMAN CODING

• With static Huffman coding, 2 operations are performed:
1. Character string to be transmitted is first analyzed
2. Character types and their relative frequency determined.
• Coding operation involves creating an unbalanced tree with some branches shorter than others. Degree
of imbalance is a function of relative frequency of occurrence of the characters: larger the spread,
more unbalanced the tree. Resulting tree is known as Huffman code tree.
• Huffman code tree is a binary tree with branches assigned a value 0 of 1.
• There are 3 types of nodes:
1. RN – Root Node: Base of the tree, the geometric top in practice is known as root node.
2. BN – Branch Node: Point at which the branch divides is known as branch node.
3. LN - Leaf Node: Termination point of a branch for which the symbols being encoded are assigned.
• An example of Huffman code tree for a string of character AAAABBCD is as shown in the figure 3.
• Fig: Example of Huffman code tree - corresponding to string of characters - AAAABBCD branch as
divides - binary value 0 of 1 - assigned to each new branch - 0 for left and 1 for right.
• Codewords used for each character (shown in leaf nodes) - are got by tracing the path from root node
to each leaf node and forming a string of binary values - associated with each branch traced.
• Set of codes associated with this tree - 4*1+2*2+1*3+1*3 = 14 bits - to transmit the complete string
AAAABBCD.
• Shorter codeword will never form the start of a longer codeword - prefix property.
• Received bitstream can be decoded by carrying recursive search bit by bit until each valid codeword
is found.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Consider the string of character: AAAABBCD

(a)

(b)

Figure 3: Huffman tree code construction (a) Final tree with codes (b) Tree derivatives

• To illustrate how the Huffman code tree in Figure 3(a) is determined, we must calculate the frequency
of occurrence of each character.
• Figure 3(b) shows the characters listed in a column in decreasing (weight) order. We derive the tree as
follows:
Ø The first two leaf nodes at the base of the list - Cl and D1 - are assigned to the (1) and (0)
branches respectively of a branch node.
Ø The two-leaf node are then replaced by a branch node whose weight is the sum of the weights of
the two leaf nodes ie. 2.
Ø A new column is then formed containing the new branch node combined with the remaining
nodes from the first column, again arranged in their correct weight order. This procedure is
repeated until only two nodes remain.
• To derive the resulting codewords for each character, we start with the character in the first column
and then proceed to list the branch numbers. 0 or 1 - as they are encountered. Thus, for character A the

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

first (and only) branch number is (1) in the last column while for C the first is (1) then (0): branch
node 2 and finally (0) at branch node 4.
• The actual codewords, however, start at the root and not the leaf node hence they are the reverse these
bit sequences. The Huffman tree can then be readily constructed from the set of codewords.

HUFFMAN DECODING ALGORITHM

• Table of codewords are available at the receiver and also had corresponding ASCII codeword received
bit stream is held in the variable BIT-STREAM.
• Variable CODEWORD are used to hold the bits in each codeword while it is being constructed.
• From the flow chart as shown in figure 4, once the codeword is identified corresponding ASCII
codeword is written into the variable RECEIVE_BUFFER.
• Procedure - repeats until all the bits in the received string have been processed.

Figure 4: Decoding of a received bitstream: Decoding algorithm and example

1 PROBLEM
A series of message is to be transferred between two computers over a PSTN. The message comprises
just the character A to H with the probability of each character is as follows: A, B = 0.25, C, D
=0.14, E, F, G and H= 0.055.
a) Use Shannon’s formula to derive the minimum average number of bits per character.
b) Use Huffman coding to derive a codeword set.
c) Derive the average number of bits per codeword set and compare it with
1. Entropy of the message
Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

2. Fixed length binary codeword

3. 7-bit ASCII codeword

Solution:
a) Shannon’s formula states:
Entropy: 𝐻 = − ∑(!$% 𝑃! 𝑙𝑜𝑔" 𝑃! 𝑏𝑖𝑡𝑠 𝑝𝑒𝑟 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑
H = - (2(0.25 log2 0.25) + 2(0.14 log2 0.14) + 4(0.055 log2 0.055))
H = 2.714 bits per codeword

b) Huffman codeword (Tree derivative)

(b)

c) Average number of bits per codeword using Huffman coding is:

2 (2*0.25) + 2(3*0.14) + 4(4*0.055) = 2.72 bits per codeword
1. Entropy of the message
𝐸𝑛𝑡𝑟𝑜𝑝𝑦 𝑓𝑟𝑜𝑚 𝑠ℎ𝑎𝑛𝑛𝑜𝑛! 𝑠𝑓𝑜𝑟𝑚𝑢𝑙𝑎 2.714
= = 0.997 = 99.7%
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑛𝑜. 𝑜𝑓 𝑏𝑖𝑡𝑠 𝑝𝑒𝑟 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑 2.72
2. Fixed length binary codeword
There are 8 characters: A – H and hence 3 bits per codeword is sufficient
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑛𝑜. 𝑜𝑓 𝑏𝑖𝑡𝑠 𝑝𝑒𝑟 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑 2.72
= = 0.906 = 90.6%
𝑁𝑜. 𝑜𝑓 𝑓𝑖𝑥𝑒𝑑 𝑏𝑖𝑡𝑠 3
3. 7-bit ASCII codeword
7 bits per codeword
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑛𝑜. 𝑜𝑓 𝑏𝑖𝑡𝑠 𝑝𝑒𝑟 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑 2.72
= = 0.388 = 38.8%
𝐴𝑆𝐶𝐼𝐼 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑 𝑏𝑖𝑡𝑠 7

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

3.2 DYNAMIC HUFFMAN CODING

• The basic Huffman coding method requires both the transmitter and the receiver to know the table of
codewords relating to the data being transmitted.
• With dynamic Huffman coding, however, the transmitter (encoder) and receiver (decoder) build the
Huffman tree and hence codeword table dynamically as the characters are being transmitted/received.
• With this method, if the character to be transmitted is currently present in the tree its codeword is
determined and sent in the normal way.
• If the character is not present that is, it is its first occurrence the character is transmitted in its
uncompressed form.
• The encoder updates its Huffman tree either by incrementing the frequency of occurrence of the
transmitted character or by introducing the new character into the tree.
• The receiver being able to determine the character that is received, can also carry out the same
modifications to its own copy of the tree so that it can interpret the next codeword received according
to the new updated tree structure.
• Refer class notes for problem solving Ex: This is simple….

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure : Dynamic Huffman encoding algorithm

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

3.3 ARITHMETIC CODING

• No. of decimal digits in the final codeword increases linearly with the number of characters in the
string to be encoded.
• Max. no. of characters in a string is determined by the precision with which floating-point numbers are
represented in the source and destination computers.
• Complete message may be first fragmented into multiple smaller strings.
• Each string is then encoded separately and the resulting set of codewords sent as a block of floating-
point numbers each in a known format.
• Alternatively binary arithmetic coding can be used.
• Example for arithmetic coding is considered to be: “went.” and the arithmetic coding principle is as in
the figure 6. (refer notes for problem solving procedure).

Figure 5: Arithmetic coding principle

3.4 LEMPEL-ZIV (LZ) CODING

• Lempel-Ziv compression algorithm uses strings of characters as the basis of the coding algorithm. Ex.:
For compression of text -Table containing all the possible character strings. Words that occur in the
text to be transferred is held by both encoder and decoder
• Instead of sending the word as a set of individuals say ASCII codewords the encoder ends only the
index of where the word is stored in the table.
• Word processing packages had dictionary associated text around 25000 words will be hence 15 bits
which has 32768 combinations are required to encode the index.
• To send "multimedia" just 15 bits needed instead 70 bits with 7-bit ASCII codewords.
• Compression ratio 4.7:1. Shorter words will have lower compression ratio, longer words a higher ratio.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Requirement
• Copy of the dictionary is held by both the encoder and the decoder standard word processing package
to be used.
• For transmission of text can be relatively inefficient if the text to be transmitted comprises only a
small subset of the words stored in the dictionary.

1 PROBLEM

The LZ algorithm is to be used to compress a text file prior to its trans-mission. If the average number
of characters per word is 6, and the dictionary used contains 4096 words, derive the average
compression ratio that is achieved relative to using 7-bit ASCIl codewords.

Solution:

• In general, a dictionary with an index of n bits can contain up to 2n entries. Now 4096 = 212 and hence
an index of 12 bits is required.

• Using 7-bit ASCIl codewords and an average of 6 characters per word requires 7 * 6 = 42 bits.

• Hence compression ratio = 42/12 = 3.5 : 1

3.5 LEMPEL-ZIV-WELSH (LZW) CODING

• Principle for encoder and decoder to build the contents of the dictionary dynamically as the text is
being transferred.
• Dictionary held by both the encoder and decoder contains only the character set. Ex: ASCII that has
been used to create the text. Remaining entries in the text are used to build up dynamically by both the
encoder and decoder and contain the words that occur in the text.
q Ex.: If the character set comprise 128 characters, Dictionary is limited to 4096 entries. First 128
entries contain single characters that make up the character set. Remaining 3968 entries would
each contain strings of two or more characters that make up the words in the text being
transferred.
• In order to describe how the dictionary is built up, consider a text to be compressed starts with the
string: This is simple as it is ....
• Since the idea is for the dictionary to contain only words, then only strings of characters that consist of
alphanumeric characters are stored in the dictionary and all the other characters in the set are
interpreted as word delimiters.
• Initially, the dictionary held by both the encoder and decoder containing only the individual characters
from the character set being used.
Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

• Hence the first word in the example text is sent by the encoder using the index of each of the four
characters T, h, i, and s.
• At this point, when the encoder reads the next character from the string - the first space (SP) character -
it determines that this is not an alphanumeric character.
• Similarly, the decoder, on receipt of the first indices/codewords, reads the character stored at each
index and commences to reconstruct the text.
• When it determines that the fifth character is a space character, it interprets this as a word delimiter and
proceeds to store the word This in its dictionary. The content in the dictionary of encoder and decoder
is as shown in the figure 6 (a).
• For example, in an application that uses 128 characters in the basic character set, then both the encoder
and decoder would start with, say, 256 entries in the dictionary. This requires an index/codeword
length of 8 bits and the dictionary would provide space for the 128 characters in the character set and a
further 128 locations for words that occur in the text.
• Should this number of locations become insufficient, on detecting this the encoder and decoder would
double the size of their dictionary to 512 locations. Clearly, this necessitates an index length of 9 bits
codewords.
• The procedure is shown in diagrammatic form in Figure 6 (b). In this example it is assumed that the
last entry in the existing table at location 255 is the word fish and the next word in the text that is not
currently in the dictionary is pond.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure 6: LZW compression algorithm (a)Basic operation (b) Dynamically extending the no. of entries in the dictionary

4. IMAGE COMPRESSION
• Images can be:
Ø Computer generated graphical images
Ø Digitized Images

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

4.1 GIF (GRAPHICS INTERCHANGE FORMAT)

• GIF is used with the Internet for the representation and compression of graphical images.
• Color images have 3 basic colors: R, G, and B each of which is represented by 8bits, so total bit pixel
is 8 x 3 = 24bits pixels hence it has 224 colors combinations.
• Each primary color has 256 colors choosing by GIF (reduces no of possible colors that are present)
which matches most closely those used in original image.
• Resulting table of colors consists of 256 entries each of which contains a 24-bit color value.
• At the decoder, instead of sending 24-bit value over the channel 8-bit index value of the table entry
that contains closest match color to the original is sent.
• Hence the compression ratio using GIF is obtained to be 3:1 and the principles of the scheme is shown
in figure 7.
• There are 2 types of color table:
1. Global color table: If is a table of colors can relate to the whole image.
2. Local color table: If table of colors relate to a portion of the image.
• As shown in figure 7(b) the LZW coding used for further levels of compression. It can be done by
extending the basic color table dynamically as the compressed image data is being encoded and
decoded.

Figure 7: GIF compression principles (a)Basic operational mode (b) Dynamic mode using LZW coding

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

• GIF allows the image transfer over the network in an interlaced mode.
• This can be used to transfer images over either low bit rate channels or the Internet which provides a
variable transmission rate.
• From this the compressed image data is organized, so that decompressed image is built up in a
progressive way as the data arrives this is done by dividing the compressed data by 4 groups as shown
in figure 8:
1. Contains 1/8 of total compressed image data
2. Contains a further 1/8
3. Contains a further 1/4
4. Contains the last remaining 1/2

Figure 8: GIF interlaced mode

4.2 TIFF (TAGGED IMAGE FILE)

• Color images have 3 basic colors: R, G, and B each of which is represented by 16bits, so total bit pixel
is 16 x 3 = 48bits pixels hence it has 248 colors combinations.
• TIFF is intended for transfer of both images and digitized documents.
• Image data can be stored and transferred over the network in a number of different formats and
particular format being use is indicated by a code number:

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

1. Uncompressed format (code number 1)

2. Digitized documents (code number 2, 3 and 4)
3. LZW compressed (code number 5)
• TIFF compression algorithms are same as used with i.e LZW. It starts with the basic color table which
contains 256 colors and table can be extended to contain up to 4096 entries containing common strings
of pixels in the image being transferred.

4.3 DIGITIZED DOCUMENTS

• In digital representation of scanned page - one single binary bit is used to represent each picture
element - with the resolutions of needed - uncompressed bit stream of the order of 2Mbits
• Most of the cases in - this must be transferred using modems and PSTN
• If the relatively low bit rate modems and PSTN used it will costly and time consuming to transfer a
total document comprising many pages in the basic form.
• In most documents - many scanned lines consist only of long strings of white pels. While - others
comprise - a mix of long strings of white and long strings of black pels. Normally - facsimile machines
are used with - public carrier networks.
• ITU-T standards - for facsimile machines are
1. T2 (Group 1)
2. T3 (Group 2)
3. T4 (Group 3)
4. T6 (Group 4)
• T2 and T3 - are earlier standards - now rarely, used - both operate digitally
• T4 (Group 3):
Ø Uses modems for use with analog PSTN.
Ø Time taken to transmit a page is reduced to less than a minute with these machines. Uses no error-
correction protocol.
Ø It is a one-dimensional coding scheme since each scanned line is encoded independently.
Ø Scanned image contains significant areas of white or black pels for ex. which occur where
documents consist of letters and line drawings.
Ø T4 works for documents containing photographic images but it is not satisfactory as the different
shades of black and white are represented by varying densities of black and white pels.
• T6:
Ø Used with digital networks such as ISDN. Higher transmission rate of 64kbps is used.
Ø Time taken to transmit a page is less than a few second.
Ø Compulsory feature in Group 4 machines.
Downloaded by Nimisha Alex (alexnimisha1997@[Link])
 lOMoARcPSD|58243556

Ø Optional feature for Group 3 facsimile machines when used here, EOL code at the end of each
(compressed) line has an additional tag bit added.
Ø If, it is a binary 1, then the next line has been encoded using T4 coding scheme.
Ø If, it is a binary 0, then the next line has been encoded using T6 coding scheme (known as MMR
coding). 2-D coding: Alternative name is MMR coding (Modified Modified READ coding) since,
it identifies black and white run-lengths by comparing adjacent scan lines.
• T4 and T6:
Ø Use data compression technique with the compression ratios in excess of 10:1 are common with
most document pages.
Ø There are 2 tables of codewords produced based on the relative frequency of occurrence of the
number of contiguous white and black pels found in a scanned line.
1. Termination-codes table: contains codeword for white or black run-lengths of from 0 to 63
pels in steps of 1 pel.
2. Make-up codes table: contains codewords for white or black run-lengths that are multiples of
64 pels.
• Over scanning technique used in which all lines start with a minimum of one white pel so, here
receiver knows the first codeword always relates to white pels and then alternates between black and
white.
• EOL (End-of-line) code is used to enable the receiver to regain synchronism each scanned line is
transmitted with EOL code.

MMR (MODIFIED MODIFIED READ) CODING

• It is known as 2D coding scheme since it identifies black and white run-lengths by comparing adjacent
scan lines.
• READ stands for Relative Element Address Designated and is the modified version of earlier scheme.
• It uses the fact that most scanned lines differ from the previous line by only a few pels.
• Ex.: If a line contains a black-run hen the next line will normally contain the same run plus or minus
up to 3 pels.
• Run-lengths associated with a line are identified by comparing the line contents known as coding line
(CL) with the immediately Preceding line is known as the reference line (RL).
• Assumption: First reference line is assumed to be an imaginary all-white line and the first lien proper
is encoded relative to this.
• Run lengths associated with a coding line can be identified as one of 3 possibilities of modes relative
to the reference line.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

• 3 modes are identified by the position of the next run-length - in the reference line (b1b2) relative to
the start and end of the next pair of run-lengths in the coding line (a0a1 and a1a2).
• The 3 modes are:
1. Pass mode
2. Vertical mode
3. Horizontal mode

1. Pass mode

• Run-length in the reference line (b1b2) is to the left of the next run-length in the coding line (a1a2)
i.e., b2 is to the left of a1.
• For this mode - run-length b1b2 is coded using the codewords. It is as shown in figure 9(a).

2. Vertical mode

• Run-length in the reference line (b1b2) overlaps the next run-length in the coding line (a1a2) by a
maximum of plus or minus 3 pels.
• For this mode just the difference run-length a1b1 is coded Most codewords are in this category. It is as
shown in figure 9(b).

3. Horizontal mode

• Run-length - in the reference line (b1b2) overlaps the run-length (a1a2) by more than plus or minus 3
pels.
• For this mode two run-lengths a0a1 and a1a2 are coded using the codewords. It is as shown in figure
9(c).

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure 9: Run-length possibilities: (a) Pass mode. (b) Vertical mode. (c) Horizontal mode.

MODIFIED-MODIFIED READ (MMR) CODING PROCEDURE FLOWCHART

• A flowchart of the coding procedure is shown in Figure 10. The first a0 is set to an imaginary white
pel before the first pel of the line and hence the first a0a1, run-length will be a0a1 - 1.
• If during the coding of a line a1, a2, b1, or b2 are not detected, then they are set to an imaginary pel
positioned immediately after the last pel on the respective line.
• Once the first/next position of a0 has been determined, the positions of a1, a2, b1 and b2 for the next
codeword are located.
• The mode is then determined by computing the position of b2 relative to a1. If it is to the left, this
indicates pass mode.
• If it is not to the left, then the magnitude of a1 b1 is used to determine whether the mode is vertical or
horizontal.
• The codeword for the identified mode is then computed and the start of the next codeword position, a0
updated to the appropriate position.
• This procedure repeats alternately between white and black runs until the end of the line is reached.
• This is an imaginary pel positioned immediately after the last pel of the line and is assumed to have a
different color from the last pel.
• The current coding line then becomes the new reference line and the next scanned line the new coding
line.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure 10: Modified – Modified READ coding procedure

4.4 DIGITIZED PICTURES

• Digitization can be carried out for both continuous tone monochromatic pictures and color pictures.
• Amount of memory needed to store and display these pictures ranges from 307kbyte to 2.4 Mbytes.
• For many interactive applications there will be a unacceptable long delays in some low bit rate
networks that might cause problem.
• Time to transmit digital pictures can be reduced by applying compression to a 2D pixel array.
• The most widely used standards relating to the compression of digital picture is developed by an
international standard body known as the JPEG (Joint Photographic Experts Group).
• JPEG also forms the basis for most of the video compression algorithms.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

4.5 JPEG ENCODER

• JPEG is defined in the international standard IS 10918.
• The standard defines a range of different compression modes, each of which is intended for use in a
particular application domain.
• Lossy Sequential Mode/ Base Mode is intended for the compression of both monochromatic and color
digitized pictures/ images as used in multimedia communication applications.
• There are 5 main stages associated with this mode which is the encoder part of JPEG:
1. Image/ block preparation.
2. Forward DCT
3. Quantization
4. Entropy encoding
5. Frame Building

Figure 11: JPEG encoder schematic

1. Image/ block preparation

• The source image is made up of one or more 2D matrices of values.
• In the case of a continuous-tone monochrome image, a single 2D matrix is used to store 8-bit gray-level
values that represent the image.
• In case of color image, if a CLUT is used just a single matrix of values is required and if the image is
represented in an R, G, B format three matrices are required, one each for the R, G, and B quantized
values.
• The color images alternative form of representation known as Y, G, C, can also be used. This is done to
exploit the fact that the two chrominance signals, G and C, require half the bandwidth of the luminance
signal, Y.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

2. Forward DCT
• Normally, each pixel value is quantized using 8 bits which produces a value in the range 0 to 255 for
the intensity/luminance values - R, G, B, or Y and a value in the range -128 to +127 for the two
chrominance values - Cb and Cr.
• In order to compute the (forward) DCT, however, all the values are first centered around zero by
subtracting 128 from each intensity/luminance value.
• Then, if the input 2D matrix is represented by: P[x, y] and the transformed matrix by F[i, j], the DCT of
each 8 x 8 block of values is computed using the expression:
) )
1 (2𝑥 + 1)𝑖𝜋 (2𝑦 + 1)𝑗𝜋
𝐹 [𝑖, 𝑗] = 𝑐(𝑖)𝑐(𝑗) ,. , 𝑃[𝑥, 𝑦]𝑐𝑜𝑠 . 𝑐𝑜𝑠
4 16 16
*$+ ,$+

Where c(i) and c(j) = 1/√2 for i, j = 0

= 1 for all other values of i and j
and x, y, i, and j vary from 0 - 7
• All 64 values in the input matrix; P[x, y] contribute to each entry in the transformed matrix, F[i, j].
• For i= j=0, the two cosine terms (and hence horizontal and vertical frequency coefficients) are both 0.
Also, since cos(0) = 1, the value in location F [0,0] of the transformed matrix is simply a function of the
summation of all the values in the input matrix. Essentially, it is the mean of all 64 values in the matrix
and is known as the DC coefficient.

3. Quantization
• Quantization is the process of mapping continuous or large sets of values to a smaller, discrete set of
values.
• The JPEG standard includes two default quantization table values: one for use with the luminance
coefficients and the other for use with the two sets of chrominance coefficients it also allows for
customized table to be used and sent with the compressed image.
4. Entropy encoding

• The entropy encoding stage comprises 4 steps: vectoring, differential encoding, run-length encoding,
and Huffman encoding.
1. Vectoring: The various entropy encoding algorithms operate on a 1D string of values. Hence before
we can apply any entropy encoding to the set of values in the matrix, we must first represent the
values in the form of a 1D vector. This operation is known as vectoring. If we scanned the matrix
using a line-by-line approach, the presence of the large number of zeros in the quantized matrix, a
zig-zag scan of the matrix is used.
2. Differential encoding: The most efficient type of compression with the information structure is
differential encoding since this encodes only the difference between each pair of values in a string
rather than their absolute values.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

3. Run-length encoding: To exploit this feature, the AC coefficients are encoded in the form of a string
of pairs of values. Each pair is made up of (skip, value) where skip is the number of zeros in the run
and value the next non-zero coefficient. Also, that the value field is encoded in the form SSS/ value.
4. Huffman encoding: when we described the encoding of digitized documents, significant levels of
compression can be obtained by replacing long strings of binary digits by a string of much shorter
codewords, the length of each codeword being a function of its relative frequency of occurrence.
Normally, a table of codewords is used with the set of codewords precomputed using the Huffman
coding algorithm.

5. Frame building
• The role of the frame builder is to encapsulate all the information relating to an encoded image/picture
in the frame format is hierarchical. At the top level, the complete frame-plus-header is encapsulated
between a start-of-frame and an end-of-frame delimiter which allows the receiver to determine the start
and end of all information relating to a complete image / picture.
• The frame header contains a number of fields that include:
Ø The overall width and height of the image in pixels
Ø The type of components that are used to represent the image (CLUT, R/G/B, Y/ Cb/Cr)
Ø The digitization format used (4:2:2, 4:2:0)
• At the second level, a frame consists of a number of components each of which is known as a scan.
These are also preceded by a header which contains fields that includes:
Ø The identity of the components (R/G/B)
Ø the number of bits used to digitize each component
Ø The quantization table of values that have been used to encode each component.

4.5.1 JPEG DECODER

• A JPEG decoder schematic is as shown in figure 12 and is made up of a number of stages which are
simply the corresponding decoder sections of those used in the encoder.

Figure 12: JPEG decoder schematic

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

• Hence the time to carry out the decoding function is similar to that used to perform the encoding.
• On receipt of the encoded bitstream the frame decoder first identifies the control information and tables
within the various headers.
• It then loads the contents of each table into the related table and passes the control information to the
image builder.
• It then starts to pass the compressed bitstream to the Huffman decoder which carries out the
corresponding decompression operation using either the default or the preloaded table of codewords.
• The two decompressed streams containing the DC and AC coefficients of each block are then passed to
the differential and run-length decoders respectively.
• The resulting matrix of values is then dequantized using either the default or the preloaded values in the
quantization table.
• Each resulting block of 8 x 8 spatial frequency coefficients is passed in turn to the inverse DCT which
transforms them back into their spatial form using the expression:
) )
1 (2𝑥 + 1)𝑖𝜋 (2𝑦 + 1)𝑗𝜋
𝐹 [𝑖, 𝑗] = 𝑐(𝑖)𝑐(𝑗) ,. , 𝑃[𝑥, 𝑦]𝑐𝑜𝑠 . 𝑐𝑜𝑠
4 16 16
*$+ ,$+

Where c(i) and c(j) = 1/√2 for i, j = 0

= 1 for all other values of i and j

• The image builder then reconstructs the original image from the blocks using the control information
passed to it by the frame decoder.
• Finally, as with the GIF, it is also possible to encode and rebuild the images in a progressive way by
first sending an outline of the image and then progressively adding more detail to it.
• This can be achieved in the following ways:
1. progressive mode: in this mode, first the DC and low-frequency coefficients of each block are sent
and then the higher-frequency coefficients.
2. Hierarchical mode: in this mode, the total image is first sent using a low resolution - for example
320 x 240 then at a higher resolution such as 640 x 480.

IMAGE/ BLOCK PREPARATION

• The source image is made up of one or more 2D matrices of values.
• In the case of a continuous-tone monochrome image, a single 2D matrix is used to store 8-bit gray-level
values that represent the image.
• In case of color image, if a CLUT is used just a single matrix of values is required and if the image is
represented in an R, G, B format three matrices are required, one each for the R, G, and B quantized
values.
• The color images alternative form of representation known as Y, G, C, can also be used. This is done to
exploit the fact that the two chrominance signals, G and C, require half the bandwidth of the luminance

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

signal, Y.
• The four alternative forms of representation are shown in Figure 13.

Figure 13: Image/block preparation (a) Image preparation (b) Block preparation
• Once the source image format has been selected and prepared, the set of values in each matrix are
compressed separately using the DCT.
• Before performing the DCT on each matrix, however, a second step known as block preparation is
carried out.
• This is necessary since to compute the transformed value for each position in a matrix requires the
values in all the locations of the matrix to be processed.
• It would be too time consuming to compute the DCT of the total matrix in a single step so each matrix
is first divided into a set of smaller 8 x 8 submatrices.
• Each is known as a block and, as we can see in part (b) of the figure, these are then fed sequentially to
the DCT which transforms each block separately.

FORWARD DCT
• Normally, each pixel value is quantized using 8 bits which produces a value in the range 0 to 255 for
the intensity/luminance values - R, G, B, or Y and a value in the range -128 to +127 for the two
chrominance values - Cb and Cr.
• In order to compute the (forward) DCT, however, all the values are first centered around zero by
subtracting 128 from each intensity/luminance value.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

• Then, if the input 2D matrix is represented by: P[x, y] and the transformed matrix by F[i, j], the DCT of
each 8 x 8 block of values is computed using the expression:
) )
1 (2𝑥 + 1)𝑖𝜋 (2𝑦 + 1)𝑗𝜋
𝐹 [𝑖, 𝑗] = 𝑐(𝑖)𝑐(𝑗) ,. , 𝑃[𝑥, 𝑦]𝑐𝑜𝑠 . 𝑐𝑜𝑠
4 16 16
*$+ ,$+

Where c(i) and c(j) = 1/√2 for i,j = o

= 1 for all other values of i and j
and x, y, i, and j vary from 0 - 7
• All 64 values in the input matrix; P[x, y] contribute to each entry in the transformed matrix, F[i, j].
• For i= j=0, the two cosine terms (and hence horizontal and vertical frequency coefficients) are both 0.
Also, since cos(0) = 1, the value in location F [0,0] of the transformed matrix is simply a function of the
summation of all the values in the input matrix. Essentially, it is the mean of all 64 values in the matrix
and is known as the DC coefficient.
• Since the values in all the other locations of the transformed matrix have frequency coefficient
associated with them - either horizontal (x= 1-7 for y = 0), vertical (x= 0 for y = 1-7) or both (x= 1-7
for y = 1-7) they are known as AC coefficients.
• For j= 0, only horizontal frequency coefficients are present which increase in frequency for i = 1-7.
• For i = 0, only vertical frequency coefficients are present which increases in frequency for j = 1-7.
• In all other locations in the transformed matrix, both horizontal and vertical frequency coefficients are
present to varying degrees as shown in figure 13.

Figure 13: DCT computation features

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

QUANTIZATION
• Quantization is the process of mapping continuous or large sets of values to a smaller, discrete set of
values.
• The JPEG standard includes two default quantization table values: one for use with the luminance
coefficients and the other for use with the two sets of chrominance coefficients it also allows for
customized table to be used and sent with the compressed image.
• An example set of threshold values is given in the quantization table shown in Figure 14 together with
set of DCT coefficients and their corresponding quantized values.

• The computation of the quantized coefficients involves rounding the quotients to the nearest integer
value.
• The threshold values used, in general, increase in magnitude with increasing spatial frequency.
• The DC coefficient in the transformed matrix is largest.
• Many of the higher frequency coefficients are zero.

ENTROPY ENCODING
• The entropy encoding stage comprises 4 steps: vectoring, differential encoding, run-length encoding,
and Huffman encoding.
1. Vectoring: The various entropy encoding algorithms operate on a 1D string of values, that is, a
vector. The output of the quantization stage is a 2D matrix of values. Hence before we can apply any
entropy encoding to the set of values in the matrix, we must first represent the values in the form of
a 1D vector. This operation is known as vectoring. If we scanned the matrix using a line-by-line
approach, the presence of the large number of zeros in the quantized matrix, a zig-zag scan of the
matrix is used as shown in Figure 15.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Figure 15: Vectoring using a zig-zag scan

2. Differential encoding: The most efficient type of compression with the information structure is
differential encoding since this encodes only the difference between each pair of values in a string
rather than their absolute values. Hence in this application, only the difference in magnitude of the
DC coefficient in a quantized block relative to the value in the preceding block is encoded. In this
way, the number of bits required to encode the relatively large magnitudes of the DC coefficients is
reduced.
For example, if the sequence of DC coefficients in consecutive quantized blocks one per block was:
12, 13, 11, 11, 10, ...
the corresponding difference values would be:
12, 1, -2, 0, -1, ...
the first difference value always being encoded relative to zero. The difference values are then
encoded in the form (SSS, value) where the SSS field indicates the number of bits needed to encode
the value and the value field the actual bits that represent the value.

3. Run-length encoding: The remaining 63 values in the vector are the coefficients and, because of
the zig-zag scan, the vector contains long strings of zeros Within it. To exploit this feature, the AC
coefficients are encoded in the form of a string of pairs of values. Each pair is made up of (skip,
value) where skip is the number of zeros in the run and value the next non-zero coefficient. Hence
the 63 values in the vector would be encoded as:
(0,6) (0,7) (0,3) (0,3) (0,3) (0,2) (0,2) (0,2) (0,2) (0,0)
Note that the final pair (0,0) indicates the end of the string for this block and that all the remaining
coefficients in the block are zero. Also, that the value field is encoded in the form SSS/ value.

4. Huffman encoding: when we described the encoding of digitized documents, significant levels of
compression can be obtained by replacing long strings of binary digits by a string of much shorter
codewords, the length of each codeword being a function of its relative frequency of occurrence.

Downloaded by Nimisha Alex (alexnimisha1997@[Link])

 lOMoARcPSD|58243556

Normally, a table of codewords is used with the set of codewords precomputed using the Huffman
coding algorithm. The same approach is used to encode the output of both the differential and run-
length encoders.

FRAME BUILDING
• The JPEG standard includes a definition of the structure of the total bitstream relating to a particular
image/picture. This is known as a frame and its outline structure is shown in Figure 16.

• The role of the frame builder is to encapsulate all the information relating to an encoded image/picture
in the frame format is hierarchical. At the top level, the complete frame-plus-header is encapsulated
between a start-of-frame and an end-of-frame delimiter which allows the receiver to determine the start
and end of all information relating to a complete image / picture.
• The frame header contains a number of fields that include:
Ø The overall width and height of the image in pixels
Ø The type of components that are used to represent the image (CLUT, R/G/B, Y/ Cb/Cr)
Ø The digitization format used (4:2:2, 4:2:0)
• At the second level, a frame consists of a number of components each of which is known as a scan.
These are also preceded by a header which contains fields that includes:
Ø The identity of the components (R/G/B)
Ø the number of bits used to digitize each component
Ø The quantization table of values that have been used to encode each component.

Refer class notes for all problem from image block preparation to run-length coding

Downloaded by Nimisha Alex (alexnimisha1997@[Link])