Data

Compression
Objectives
After studying this chapter, the student should be able to:
 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.2
 COMPRESSION PRINCIPLES

 Compression desirable to compress

digital audio, image, and video so that
their bit rates or storage requirements
become manageable.
 We achieve data compression by
exploiting two major factors:
 redundancy existing in digital audio, image,
and video data
 the properties of human perception.

15.3
 Data Redundancy
 digital audio is a series sample values.
 An image is a rectangular array of
sample values (pixel values)
 video is a sequence of images played
out at a certain rate.
 Nilai-nilai diatas berkorelasi dengan nilai
sampel yg berdekatan . Korelasi ini
disebut redundancy.
 Removal of redundancy does not
change the meaning of the data.
15.4
 Redundancy in Digital
 Audio
In most cases, adjacent audio samples are
similar.
 The next sample value can be predicted to
some extent based on the current sample
value.
 Compression techniques that use this feature are
called predictive coding.
 During a normal conversation, we talk for only
a very small percentage of time. Between
talking spurts, there is silence. Samples
corresponding to this silence can be removed
without affecting the meaning of the speech.
 Compression techniques that use this feature are
15.5
 Redundancy in Digital
Images
 In a digital image, neighboring samples
on a scanning line are normally similar.
 Neighboring samples on adjacent lines
are also similar. These similarities are
called spatial redundancy.
 Spatial redundancies can be removed
using predictive coding techniques and
other techniques (such as transform
coding).
15.6
 Redundancy in Digital
Video
 Digital video is a sequence of
images, thus it also has spatial
redundancies.
 Neighboring images in a video
sequence are normally similar.
 This similarity is called temporal
redundancy and can be removed by
applying predictive coding between
images.
15.7
 Human Perception
Properties
 End users audio digital, image, dan video
adalah manusia.
 Manusia dapat mentoleransi information error
atau loss tanpa mempengaruhi keefektifan
komunikasi.
 This means that the compressed version does not need
to represent the original information samples exactly.
 This is in contrast to the conventional alphanumeric
data where any data loss or error is normally not
allowed, especially for computer programs.
 The above feature indicates that human
perception is generally not sensitive to small

15.8
Classifications of Compression
Techniques
 can be classified in many ways according
to different criteria.
 classify them based on the results of the
compression techniques.
 Two classifications we will consider are
whether the original data can be
reconstructed exactly after using a
compression technique, and whether the
output of a compression system is of
constant bit rate.
15.9
Data Compression Techniques/methods can be
divided into two broad categories: lossless and lossy
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
o The simplest method of compression.
o 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.
12
Run-length encoding example
15.
13
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.
14
Figure 15.4 Huffman coding 15.
15
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.

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

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

18
LATIHAN :

 Tentukanlah kode huffman dari masing-

masing karakter pada Text berikut :
 before we can assign bit patterns to each
character
 Solusi :
 Hitung frekuensi kejadian masing-masing
Karakter pada Text.
 Buat pohon huffman
 Tentukan kode masing-masing Karakter
Lempel Ziv encoding
•called dictionary-based encoding.
• Membuat dictionary (a table) of strings
used during the communication session.
• Bila sender dan receiver mempunyai
copy of the dictionary, maka dapat
disubstitusi dengan indexnya di dalam
dictionary untuk mengurangi jumlah
informasi yg ditransmisikan.

15.
20
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.
21
Figure 15.8 An example of Lempel Ziv encoding 15.
22
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.
23
Figure 15.9 An example of Lempel Ziv decoding 15.
24
 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
othey 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,
15.
o MP3 (MPEG audio layer 3) for audio compression. 25
Image compression – JPEG encoding
• an image can be represented by a two-dimensional array
(table) of picture elements (pixels).
• A grayscale picture of 307,200 pixels is represented by
2,457,600 bits, and
• a color picture is represented by 7,372,800 bits.

15.
26
In JPEG,
-a grayscale picture
dibagi menjadi
blok2 dengan
ukuran block 8 × 8
pixel, untuk
mengurangi jumlah
kalkulasi.
- jumlah operasi
matematik masing
gambar adalah the
square of the
number JPEG
of units.
grayscale example, 640 × 480 pixels 15.
27
• JPEG merubah picture menjadi seperangkat vektor yang
menimbulkan redundansi.
• The redundancies can then be removed using one of the
lossless compression methods we studied previously.

Figure 15.11 The JPEG compression process 15.

28
Discrete cosine transform (DCT)
• Setiap block 64 pixels ditransformasi oleh discrete cosine
transform (DCT).
• The transformation changes the 64 values so that the
relative relationships between pixels are kept but the
redundancies are revealed.

15.
29
The transform coding process using DCT.
We apply a two-dimensional DCT on an image block of 8-
by-8 elements.
For forward transform, from definition [6] we have
C = BABT

where :
• C is a transformed coefficient matrix of 8-by-8 elements.
• B the DCT transform matrix whose entries are defined
below.
•A an image data matrix of 8-by-8 elements to be coded.
•BT denotes the transpose of B.

15.
30
For inverse DCT (IDCT), we
have
A = BT CB

15.
31
For two-dimensional DCT with block size of 8-
by-8, we denote the entries of B by B(i, j),
where i is the row index from 0 to 7 and j the
column index from 0 to 7.
According to the definition, we have

15.
32
15.
33
15.
34
Notice that after the transformation, most
energy is packed at the top left corner of C.
This means that image data are decorrelated
after the transform.
15.
35
After quantization of the coefficients (here
each entry is divided by 30 and results are
rounded off to the nearest integer), we obtain

15.
36
15.
37
15.
38
15.
39
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.

40
Figure 15.13 Case 2: two sections 15.
41
Figure 15.14 Case 3: gradient grayscale 15.
42
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.
43
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.
44
Figure 15.16 MPEG frames 15.
45
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.
46
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.
47
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.
48
 TUGAS
 Jelaskan perbedaan antara kompresi lossless dan kompresi lossy.

 Jelaskan teknik koding berikut dan bagaimana kompresi dapat dicapai pada teknik berikut:

 teknik run-length encoding

 Huffman coding .

 Lempel Ziv encoding

 Jelaskan idea yang mendasari :

 standar JPEG untuk kompresi still images.

 Standar MPEG untuk kompresi video.

 Standar MP3 untuk kompresi audio.