Multimedia

19L010 MULTIMEDIA COMPRESSION TECHNIQUES

INTRODUCTION : Compression Techniques - Overview of information theory

- lossless and lossy coding– Multimedia components and their characteristics
-Text, sound, images, graphics, animation, video- Huffman coding – Non-
Binary Huffman codes – adaptive Huffman coding (8)

ARITHMETIC CODING AND DICTIONARY TECHNIQUES :

Introduction- coding a sequence – generating deciphering the tag

– Generating a binary code –Static and Adaptive dictionary – LZ77, LZ78, LZW
approach – Applications - Facsimile encoding –
run length coding – MH, MR, MMR and JBIG. Scalar and Vector Quantization

2
AUDIO COMPRESSION : Audio compression techniques -
frequency domain and filtering - basic sub-band coding –
application to speech coding - G.722 - application to audio
coding - MPEG audio - silence suppression – speech
compression techniques –Vocoders. (10)

IMAGE COMPRESSION : Predictive techniques - DPCM, DM -

DCT,JPEG, Wavelet based compression: quad-trees, EZW,
SPIHT, JPEG-2000. (9)

VIDEO COMPRESSION : Video signal representation –Motion

compensation – MPEG standards - Motion estimation
techniques - H.261 family of standards - Motion video
compression
TEXT BOOKS:
1. Sayood Khaleed , "Introduction to data compression", 5th
Edition, Morgan Kauffman, 2017.
2. Yun Q. Shi, Huifang Sun , "Image and Video Compression for
Multimedia Engineering: Fundamentals, Algorithms, and
Standards", third Edition, CRC Press, 2019.

REFERENCES:
1. Salomon D , "Data Compression The Complete Reference",
Springer, 2014.
2. SalomonD , "A Guide to Data Compression Methods",
Springer, 2012.
 Table Contents
– Definition
– Introduction
– Categories of Multimedia
– Applications of Multimedia
– Components of Multimedia
– Conclusion

5
 Definition
The word multi and media are combined to form the
word multimedia. The word “multi” signifies “many.”
Multimedia is a type of medium that allows
information to be easily transferred from one
location to another.

6
 Introduction
• Multimedia is the presentation of text, pictures,
audio, and video with links and tools that allow the
user to navigate, engage, create, and communicate
using a computer.
• Multimedia refers to the computer-assisted
integration of text, drawings, still and moving
images(videos) graphics, audio, animation, and any
other media in which any type of information can
be expressed, stored, communicated, and
processed digitally.
7
8
 Categories of Multimedia
Linear Multimedia:
• It is also called Non-interactive multimedia. In
the case of linear multimedia, the end-user
cannot control the content of the application.
• It has literally no interactivity of any kind.
Some multimedia projects like movies in which
material is thrown in a linear fashion from
beginning to end.

●●●
9
 Categories of Multimedia
Non-Linear Multimedia:
• In Non-Linear multimedia, the end-user is
allowed the navigational control to rove
through multimedia content at his own desire.
The user can control the access of the
application. Non-linear offers user interactivity
to control the movement of data.
• For example computer games, websites, self-
paced computer-based training packages, etc.

10
 Applications of Multimedia
Education
• In the subject of education, multimedia is
becoming increasingly popular. It is often used
to produce study materials for pupils and to
ensure that they have a thorough
comprehension of various disciplines.
Edutainment, which combines education and
entertainment, has become highly popular in
recent years.

●●●
11
 Applications of Multimedia
Entertainment
• The usage of multimedia in films creates a
unique auditory and video impression.
Today, multimedia has completely
transformed the art of filmmaking around
the world. Multimedia is the only way to
achieve difficult effects and actions.

●●●
12
 Applications of Multimedia
Business
• Marketing, advertising, product demos,
presentation, training, networked
communication, etc. are applications of
multimedia that are helpful in many
businesses. The audience can quickly
understand an idea when multimedia
presentations are used.

●●●
13
 Applications of Multimedia
Technology & Science
• In the sphere of science and technology,
multimedia has a wide range of
applications. It can communicate audio,
films, and other multimedia documents in
a variety of formats. Only multimedia can
make live broadcasting from one location
to another possible.

●●●
14
 Applications of Multimedia
Fine Arts
• Multimedia artists work in the fine arts,
combining approaches employing many
media and incorporating viewer
involvement in some form. For example, a
variety of digital mediums can be used to
combine movies and operas.

●●●
15
 Applications of Multimedia
Engineering
• Multimedia is frequently used by software
engineers in computer simulations for
military or industrial training. It’s also used
for software interfaces created by creative
experts and software engineers in
partnership.

16
 Components of Multimedia
Text
• Characters are used to form words,
phrases, and paragraphs in the text. Text
appears in all multimedia creations of some
kind. The text can be in a variety of fonts
and sizes to match the multimedia
software’s professional presentation.

●●●
17
 Components of Multimedia
Graphics
• Non-text information, such as a sketch,
chart, or photograph, is represented
digitally. Graphics add to the appeal of the
multimedia application. In many
circumstances, people dislike reading big
amounts of material on computers

●●●
18
 Components of Multimedia
Animations
• A sequence of still photographs is being
flipped through. It’s a set of visuals that give
the impression of movement. Animation is
the process of making a still image appear
to move.

●●●
19
 Components of Multimedia
Video
• Photographic images that appear to be in
full motion and are played back at speeds of
15 to 30 frames per second. The term video
refers to a moving image that is
accompanied by sound, such as a television
picture.

●●●
20
 Components of Multimedia
Audio
• Any sound, whether it’s music, conversation,
or something else. Sound is the most serious
aspect of multimedia, delivering the joy of
music, special effects, and other forms of
entertainment. Decibels are a unit of
measurement for volume and sound pressure
level.

21
 Conclusion
 Multimedia is significant in our lives today
because if we connect and communicate with
more than just one medium, we can use more
than one of our senses.
 Using a variety of artistic or communicative media
like this helps to make an idea or presentation
fresh and interesting, and also allows for greater
insight

23
Objectives

 Distinguish between lossless and lossy compression.

 Describe run-length encoding and how it achieves compression.

 Describe Huffman coding and how it achieves compression.

 Describe Lempel Ziv encoding and the role of the dictionary in encoding and
decoding.

 Describe the main idea behind the JPEG standard for compressing still
images.

 Describe the main idea behind the MPEG standard for compressing video
and its relation to JPEG.

 Describe the main idea behind the MP3 standard for compressing audio.

15.
25
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.

Data compression methods

 LOSSLESS 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.

• This methods are normally used when we cannot

afford to lose any data.
 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.
• 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.
28
Run-length encoding example
15.
29
 Huffman coding

• Assigns shorter codes to symbols that occur more

frequently.
• For example, 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.

15.
30
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.

31
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.

32
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.

33
 Lempel Ziv encoding

• Lempel Ziv (LZ) encoding is an example of a category of

algorithms called dictionary-based encoding.
• The idea is to create a dictionary (a table) of strings used
during the communication session.
• If both the sender and the receiver have a copy of the
dictionary, then previously-encountered strings can be
substituted by their index in the dictionary to reduce the
amount of information transmitted.

15.
34
Compression
• There are two concurrent events:
• building an indexed dictionary
• compressing a string of symbols.
• The algorithm extracts the smallest substring that cannot
be found in the dictionary from the remaining
uncompressed string.
• It then stores a copy of this substring in the dictionary as a
new entry and assigns it an index value.
• Compression occurs when the substring, except for the last
character, is replaced with the index found in the dictionary.
• The process then inserts the index and the last character of
the substring into the compressed string.

15.
35
Figure 15.8 An example of Lempel Ziv encoding 15.
36
Decompression
o Decompression is the inverse of the compression process.
o The process extracts the substrings from the compressed
string and tries to replace the indexes with the
corresponding
entry in the dictionary, which is empty at first and built up
gradually.
oThe idea is that when an index is received, there is already
an entry in the dictionary corresponding to that index.

15.
37
 LOSSY COMPRESSION METHODS

Our eyes and ears cannot distinguish subtle changes.

In such cases, we can use a lossy data compression method.
o These methods are cheaper—they take less time and
space when it comes to sending millions of bits per second
for images and video.
o Several methods have been developed using lossy
compression techniques.
o JPEG (Joint Photographic Experts Group) encoding
is used to compress pictures and graphics.
o MPEG (Moving Picture Experts Group) encoding is
used to compress video,
oMP3 (MPEG audio layer 3) for audio compression. 15.
38
Figure 15.10 JPEG grayscale example, 640 × 480 pixels 15.
39
The whole idea of JPEG is to change the picture into a linear
(vector) set of numbers that reveals the redundancies. The
redundancies (lack of changes) can then be removed using
one of the lossless compression methods we studied
previously. A simplified version of the process is shown in
Figure 15.11.

Figure 15.11 The JPEG compression process 15.

40
 Discrete cosine transform (DCT)
In this step, each block of 64 pixels goes through a
transformation called the discrete cosine transform (DCT).
The transformation changes the 64 values so that the relative
relationships between pixels are kept but the redundancies
are revealed. The formula is given in Appendix G. P(x, y)
defines one value in the block, while T(m, n) defines the
value in the transformed block.

15.
41
To understand the nature of this transformation, let us show
the result of the transformations for three cases.

Figure 15.12 Case 1: uniform grayscale 15.

42
Figure 15.13 Case 2: two sections 15.
43
Figure 15.14 Case 3: gradient grayscale 15.
44
Quantization
After the T table is created, the values are quantized to
reduce the number of bits needed for encoding. Quantization
divides the number of bits by a constant and then drops the
fraction. This reduces the required number of bits even more.
In most implementations, a quantizing table (8 by 8) defines
how to quantize each value. The divisor depends on the
position of the value in the T table. This is done to optimize
the number of bits and the number of 0s for each particular
application.

15.
45
Compression
After quantization the values are read from the table, and
redundant 0s are removed. However, to cluster the 0s
together, the process reads the table diagonally in a zigzag
fashion rather than row by row or column by column. The
reason is that if the picture does not have fine changes, the
bottom right corner of the T table is all 0s.

JPEG usually uses run-length encoding at the compression

phase to compress the bit pattern resulting from the zigzag
linearization.

15.
46
Figure 15.15 Reading the table 15.
47
 Video compression – MPEG encoding

The Moving Picture Experts Group (MPEG) method is used

to compress video. In principle, a motion picture is a rapid
sequence of a set of frames in which each frame is a picture.
In other words, a frame is a spatial combination of pixels,
and a video is a temporal combination of frames that are sent
one after another. Compressing video, then, means spatially
compressing each frame and temporally compressing a set of
frames.

15.
48
Spatial compression
The spatial compression of each frame is done with JPEG, or
a modification of it. Each frame is a picture that can be
independently compressed.

Temporal compression
In temporal compression, redundant frames are removed.
When we watch television, for example, we receive 30
frames per second. However, most of the consecutive frames
are almost the same. For example, in a static scene in which
someone is talking, most frames are the same except for the
segment around the speaker’s lips, which changes from one
frame to the next.
15.
49
Figure 15.16 MPEG frames 15.
50
 Audio compression

Audio compression can be used for speech or music. For

speech we need to compress a 64 kHz digitized signal, while
for music we need to compress a 1.411 MHz signal. Two
categories of techniques are used for audio compression:
predictive encoding and perceptual encoding.

15.
51
Predictive encoding
In predictive encoding, the differences between samples are
encoded instead of encoding all the sampled values. This
type of compression is normally used for speech. Several
standards have been defined such as GSM (13 kbps), G.729
(8 kbps), and G.723.3 (6.4 or 5.3 kbps). Detailed discussions
of these techniques are beyond the scope of this book.

Perceptual encoding: MP3

The most common compression technique used to create
CD-quality audio is based on the perceptual encoding
technique. This type of audio needs at least 1.411 Mbps,
which cannot be sent over the Internet without compression.
MP3 (MPEG audio layer 3) uses this technique.
15.
52
Relations for relationship sets
For each relationship set in the E-R diagram, we create a
relation (table). This relation has one column for the key of
each entity set involved in this relationship and also one
column for each attribute of the relationship itself if the
relationship has attributes (not in our case).

15.
53