MMC Notes Module 3

S J P N Trust's ECE Dept.
Hirasugar Institute of Technology, Nidasoshi MMC_Notes

Inculcating Values, Promoting Prosperity
Approved by AICTE, Recognized by Govt. of Karnataka and Affiliated to VTU Belagavi. Module-3
Accredited at 'A' Grade by NAAC
Programmes Accredited by NBA: CSE, ECE, EEE & M E 2021-22
Module 3
Text and Image Compression
3.1 Introduction
 Compression is generally applied in multimedia communication to reduce the volume

of information to be transmitted or to reduce the bandwidth that is required for its
transmission.
3.2 Compression principles

 Source Encoders and Destination decoders
 Lossless and losy Compression
 Entropy Encoding
 Source Encoding
3.2.1 Source Encoders and Destination decoders:
Figure 3.1 Source encoder/destination decoder alternatives: a) software only; b) Special

processors/ Hadrware
 Transmitting the information relating to a particular multimedia application, a
compression algorithm is applied to it.
SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

Engineering Department, Hirasugar Institute of Technology Nidasoshi
1
 This denotes that in order for the destination to reproduce the original source
information nearly exact copy it, a matching decompression algorithm must be
applied to it.
 The application of the compression algorithm is the main fuction carried out by the
source encoder and the decompression algorithm is carried out by destination decoder.
 In the above figure two computers communicating with each other, the time required
to perform the compression and decompression algorithms is not always critical.
 Therefore both algorithms are normally implemented in software within two
computers.
 The general scheme is shown in part (a) of the above Figure 3.1.
 It is an example application which uses this approach is the compression of text or
image files.
 In some application time required to perform compression and decompression
algorithms in software is not acceptable and instead of two algorithms must be
performed by special processors in separate units as shown in part (b).
3.2.2 Lossless and Lossy Compression:

Compression algorithms can be classified into
 Lossless compression:
 The aim is to reduce the number of bits used to represent the source information in
such a way that there is no loss of information.
 Reversible
 Lossy compression:
 The aim is to reduce the number of bits used to represent the source information by
introducing acceptable loss of information.

2
3.2.3 Entropy Encoding:

 Entropy encoding is lossless and independent of the type of information that is being
compressed.
 e.g. run-length encoding
00000001111100011  7,5,3,2  111,101,011,010
Statistical Encoding
 Statistical encoding uses a set of variable-length codewords with the shorter
codewords used to represent the more frequently occurring symbols.
 The theoretical minimum average number of bits that are required to transmit a
particular source stream is known as the Entropy of the source.
 Entropy is defined as
where n is the number of different symbols in the source stream and Pi is the
probability of occurrence of symbol i.
 For a particular codebook, the average number of bits per codeword is given by ,
where Ni is the bit length of the ith codeword of the codebook.

3

4
3.2.4 Source Encoding:

 It exploits a particular property of the source information in order to produce an
alternative form of representation that is either a compressed version of the original
form or is more amenable to the application of compression.
 e.g. Differential or Predictive encoding.
 e.g. Transform encoding.
Differential Encoding
 Instead of using a set of relatively large codewords to represent the amplitude of each
value/signal, a set of smaller codewords can be used each of which indicates only the
difference in amplitude between the current value/signal being encoded.
 For example, 12 bits to obtain the required dynamic range but the maximum
difference in amplitude between successive samples of the signal requires only 3-bits.
Transform Encoding
 As we scan across a set of pixel locations the rate of change in magnitude will vary
from zero, if all the pixel values remain the same.
 A high rate of change it each pixel magnitude changes from one location to the next.
 The rate of change in magnitude as one traverses the matrix gives rise to a term
known as spatial frequency.

5
Figure 3.2 Transform Coding: (a) Example pixel Patterns; (b) DCT transform Principles
 The human eye is less sensitive to the higher spatial frequency components.
 If we can transform the original spatial form of representation into an equivalent
representation involving spatial frequency components, then we can more readily
identify and eliminate those higher frequency components which the eye cannot
detect thereby reducing the volume of information.
 The transformation of a two-dimensional matrix of pixel values into an equivalent
matrix of spatial frequency components discrete cosine transform(DCT) which is
shown in Figure 3.2 (b).

6
3.3 Text compression

 Any compression algorithm associated with text must be lossless since the loss of just
a single character could modify the meaning of a complete string.
 In static coding, the set of codewords does not change for all subsequent transfer. In
dynamic coding, it does.
3.3.1 Static Huffman coding

 First analyzed and the character types and their relative frequency determined.
 An example of a Huffman code tree is AAAABBCD.
 A binary 0 for the left branch and a binary 1 for the right branch.
Figure 3.3 Huffman Code Tree Construction: (a) Final tree with Codes; (b) Tree
Derivation

7
 Listing the resulting weights of all the leaf and branch nodes in the tree starting with
the smallest weight and proceeding from left to right and from bottom to top.
 4 × 1 + 2× 2 + 1×3 + 1×3 = 14 bits
 Figure 3.4 shows the example of Huffman encoding example.
 Huffman codewords have the unique property that a shorter codeword will never form
the start of a longer codeword prefix property.

8

9

10
3.3.2 Dynamic Huffman coding

 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.
3.3.3 Arithmatic Encoding

 Arithmetic coding yields a single codeword for each encoded string of characters.
 The first step is to divide the numeric range from 0 to 1 into a number of different
characters present in the message to be sent.
 The size of each segment by the probability of the related character.
Figure 3.7 Arithmatic Coding Principles: (a) Example Character set and their range
Assignments; (b) Encoding of the string went..
 The first character to be encoded w is in the range 0.8 To 0.9, then itself subdivided
into five further segments.
 The segment for the character e, is from 0.8 to 0.83(0.8 + 0.3× 0.1).

11
 Character n from 0.83 to 0.86 (0.83 + 0.3× 0.1) and so on.

 The character e has a range from 0.8 to 0.809 (0.8+ 0.3× 0.03).
 The character n from 0.809 to 0.818 (0.809 + 0.3× 0.03) and so on.
 This procedure continues until the termination character . is encoded.
 At this point, the segment range of . is from 0.81602 to 0.8162 and hence the
codeword for the complete string is any number within the range
0.81602  codeword  0.8162
 The maximum number of characters in a string is determined by the precision with
which floating-point numbers.
3.3.4 Lempel-Ziv coding

 The Lempel-Ziv (LZ) compression algorithm, instead of using single characters as the
basis of coding operation, uses strings of characters.
 For example , for the compression of text, a table containing all the possible of
character strings.
 The encoder sends only the index of where the word is stored in the table and, on
receipt of each index, the decoder uses this to access the corresponding word/string of
characters from the table.
 Thus the table is used as a dictionary and the LZ algorithm is known as a Dictionary
based compression algorithm.
3.3.5 Lempel-Ziv Welsh coding

 Initially, the dictionary held by both the encoder and decoder contains only the
character set.
 The remaining entries in the dictionary are then built up dynamically by both the
encoder and decoder and contain the words that occur in the text.

12
Figure 3.8 LZW Compression algorithm: (a) Basic operation; (b) Dynamically extending
the number of entries in the dictionary
 The encoder prior to sending each word in the form of single characters, first checks
to determine if the word is currently stored in its dictionary and, if it is, it sends only
the index for the word.
 The available space become full, then the number of entries is allowed to increase
incrementally.

13
3.4 Image compression

 A lossless compression algorithm must be used when transferring graphical images.
 Two different schemes are used for the compression of bit-map images:
1) Based on a combination of run-length and statistical encoding (lossless).
(e.g. fax).
2) Based on a combination of transform, differential and, run-length encoding
(loss). (e.g. JPG)
 The most widely adopted image coding standard has been developed by an
international standards body known as the Joint Photographic Experts Group (JPEG).
3.4.1 Graphic interchange format(GIF)
 The resulting table of colors therefore consists of 256 entries, each of which contains
a 24-bit color value.
 Hence instead of sending each pixel as a 24-bit value, only the 8-bit index to the table
entry that contains the closest match color to the original is sent.
 This results in a compression ratio 3:1.
 The table of colors can relate either to the whole image in which case it is reffered to
as the Global color table or to a proportion of the image , when it is reffered to as
Local color table.
 The principles of scheme are shown in Figure 3.9 (a).
 As shown in Figure 3.9 (b), the LZW coding algorithm can be used to obtain further
levels of compression.
 GIF also allow an image to be stored and subsequently transferred over the network in
an interlaced mode.
 To achieve the compressed image the data is divided into four groups as shown in
Figure 3.10. Here the first contains 1/8 of the total compressed image data, the second
a further 1/8, the third a further 1/4 , and the last the remaining 1/2.

14
Figure 3.9 GIF compression principles: (a) Basic operational mode; (b) Dynamic mode
using LZW coding
Figure 3.10: GIF Interlaced mode

15
3.4.2 Tagged image file format

 The supports pixel resolutions of up to 48 bits-16 bits each for R, G, and B.
 The LZW compression algorithm that is used.
3.4.3 Joint Photographic Experts Group(JPEG)
There are five main stages associated with this mode:
i) Image/block preparation
ii) Forward DCT,
iii) Quantization,
iv) Entropy encoding, and
v) Frame building
JPEG Encoding
i) Image/block preparation
 The four alternative forms of representation are shown in Figure 3.15 (a).
 Once the source image format has been selected and prepared, the set of values in
each matrix are compressed separately using the DCT.

16
 Before performing the DCT on each matrix, however a second step known as Block
preparation is carried out.
 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 set of smaller 8× 8 submatrics as a block
which is shown in part (b).

17
ii) Forward DCT

 The source image is divided into 8x8 blocks, and transformed into the frequency
domain using the FDCT.
 Forward Discrete cosine transform (FDCT)
 F(0,0) is known as DC coefficient.

 Others are known as AC coefficients.
 Most AC coefficients have zero or near-zero values.
 All 64 DCT coefficients are quantized using a 64- element quantization table.
 Discards information which is not visually significant.

18
 where Q(u,v) are quantization coefficients specified by a quantization table.

 The above points are summarized in Figure 3.16.
iii) Quantization
 The human eye responds primarily to the DC coefficient and the lower spatial
frequency coefficients.
 Quantization phase by dropping-in practice, setting to zero-those spatial frequency
coefficients in the transformed matrix whose amplitudes are less than a defined
threshold value.
 The quantization process aims to reduce the size of the DC and AC coefficients so
that less bandwidth is required.
 A division operation is performed using the defined threshold value as the divisor.
 The quantization table with the threshold value to be used with a particular DCT
coefficient in the corresponding position in the matrix.
 An example set of threshold values is given in the quantization tableshown in Figure
3.17.

19
 An example set of threshold values is given in the quantization table , it can

conclude a number of points:
 The computation of the quantized coefficients involves rounding the
quotients to the nearest integer value.
 The threshold values used, increase in magnitude with increasing spatial
frequency.
 The DC coefficient in the transformed matrix is largest.
 Many of the higher-frequency coefficients are zero.
Figure 3.17: Example computation of a set of quantized DCT coefficients.

iv) Entropy Encoding
 It provides additional compression by encoding the quantized DCT coefficients into
more compact form.
 There are four steps in entropy encoding: vectoring, differential encoding, run-length
encoding, and Huffman encoding.
 Vectoring
 Represent the values in the form of a single- dimension vector as
vectoring.

20
 Zig-zag scan
 The DC coefficient and lower-frequency AC coefficients-both
horizontal and vertical-are scanned first.
 After quantization, the 63 AC coefficients are ordered into the “zig-
zag” sequence (for entropy encoding) as shown in Figure 3.18.
 The probability of coefficients being zero is an increasing monotonic
function of the index.
 The dc coefficients are encoded using the predictive coding techniques.
 There is usually a strong correlation between dc coefficients of
adjacent 8x8 blocks.
 Differential Encoding
 The first element in each transformed block is the DC coefficient which
is a measure of the average color/luminance/chrominance.
 The DC coefficient varies only slowly from one block to the next.
 Differential encoding since this encodes only the difference between
each pair of values.

21
 Runlength Encoding
 The remaining 63 values in the vector are the AC coefficients.
 Each pair is made up of (skip, value) where skip is the number of zeros
in the run.
 Figure 3.18 would be encoded as: (0,6) (0,7) (0,3) (0,3) (0,3) (0,2)
(0,2) (0,2) (0,2) (0,0).
 Final pair (0,0) indicates the end of the string for this block and that all
the remaining coefficients in the block are zero.
 Huffman Encoding
 Significant levels of compression can be obtained by replacing long
string of binary digits by a string of much shorter codewords
 The length of each codeword being a function of its relative frequency
of occurrence
v) Frame Building
 The frame builder is to encapsulate all the information relating to an encoded
image/picture in this format.
 This is shown in Figure 3.20.

22
JPEG Decoding
 As we can see in Figure 3.21, a JPEG decoder is made up of a number of stages which
are simply the corresponding decoder sections of those used in the encoder.
 On reciept of the encoded bitstream the frame decoder first identifies the control
information and tables within the various headers. Then control information passes
through the image builder.
 The compressed bitstream it start pass to the Huffman decoder which carries out the
corresponding decompressed streams containing DC and AC coefficients of each
block are then passed to the diffential and run length decoders respectively.
 Then the resulting values is then dequantized using either default or preloaded values
in the quantization table.
 Each resulting block of 8 X 8 spatial frequency coeffients is passed in turn to the
inverse DCT which transforms them back into their spatial form.

23
 In order to reduce delay, an image can be encoded in a way that it can be

reconstructed in a progressive way by first sending an outline of the image and then
progressively adding more detail to it.
 Progressive mode: in this mode, first the DC and lowfrequency coefficients of each
block are sent and then the higher-frequency coefficients.
 Hierarchical mode: in this mode, the total image is first sent using a lower resolution
then at a higher resolution.

24

MMC Notes Module 3

Uploaded by

Copyright:

Available Formats

MMC Notes Module 3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MMC Notes Module 3

Uploaded by

Copyright:

Available Formats

S J P N Trust's ECE Dept.

Hirasugar Institute of Technology, Nidasoshi MMC_Notes

 Compression is generally applied in multimedia communication to reduce the volume

3.2 Compression principles

3.2.1 Source Encoders and Destination decoders:

Figure 3.1 Source encoder/destination decoder alternatives: a) software only; b) Special

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.2.2 Lossless and Lossy Compression:

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.2.3 Entropy Encoding:

where Ni is the bit length of the ith codeword of the codebook.

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.2.4 Source Encoding:

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.3 Text compression

3.3.1 Static Huffman coding

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.3.2 Dynamic Huffman coding

3.3.3 Arithmatic Encoding

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

 Character n from 0.83 to 0.86 (0.83 + 0.3× 0.1) and so on.

3.3.4 Lempel-Ziv coding

3.3.5 Lempel-Ziv Welsh coding

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.4 Image compression

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

Figure 3.10: GIF Interlaced mode

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

3.4.2 Tagged image file format

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

ii) Forward DCT

 F(0,0) is known as DC coefficient.

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

 where Q(u,v) are quantization coefficients specified by a quantization table.

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

 An example set of threshold values is given in the quantization table , it can

Figure 3.17: Example computation of a set of quantized DCT coefficients.

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

 In order to reduce delay, an image can be encoded in a way that it can be

SHREEVIJAY ITTANNAVAR, Assistant Professor ,Electronics and Communication

You might also like